大数据环境下基于改进网格单元的DBSCAN算法  

Improved DBSCAN Algorithm Based on Grid Cell in Big Data Environment

作　　者：杨旭辉 张帆[2,3] 胡涛 YANG Xuhui;ZHANG Fan;HU Tao(Zhongyuan Network Security Research Institute,Zhengzhou University,Zhengzhou 450000,China;Information Engineering University,Zhengzhou 450001,China;Network Communication and Security Purple Mountain Laboratory,Nanjing 211189,China)

机构地区：[1]郑州大学中原网络安全研究院,河南郑州450001 [2]信息工程大学,河南郑州450001 [3]网络通信与安全紫金山实验室,江苏南京211189

出　　处：《信息工程大学学报》2021年第3期351-358,共8页Journal of Information Engineering University

基　　金：国家自然科学基金面上项目(61572520);国家自然科学基金创新研究群体项目(61521003)。

摘　　要：近年来,在HDFS上的小文件聚类存储问题引起了广泛关注。针对传统聚类算法DBSCAN在聚类过程中,出现数据密度不均匀时造成聚类效果粗糙及时间开销较大等问题,提出了一种基于经改进网格单元的DBSCAN聚类算法。该算法首先使用网格单元划分及爬山法辨别出局部次优区域来缩小搜索范围,进而再从所选局部次优区域执行宽度优先搜索法,遍历数据点并将其聚类成簇,有效地提高了数据聚类的精确度,显著降低了时间成本。实验结果表明,在数据集较小的情况下,该算法在聚类精度和运行时间上与传统算法接近。当数据集较大时,与传统算法相比,该算法的聚类精度有明显提高,具有更高的时间效率,满足了大数据环境下的小文件处理需求。In recent years,the problem of small file clustering storage on HDFS has attracted much attention.To overcome the roughed clustering result and the time overhead in the clustering of density based spatial clustering of applications with noise algorithm(DBSCAN),a clustering algorithm based on improved grid cells is proposed.Firstly,the algorithm adopts the grid cells division and mountain climbing algorithm to identify the locally suboptimal region to reduce the search scope.Then it finds clusters from these locally suboptimal regions by breadth-first search(BFS).The experimental results show that G-DBSCAN(the grid of DBSCAN)is comparable to the traditional DBSCAN algorithm in accurate and timely clustering on the small data set,but has a great improvement in accurate and time efficiency on the big data set.It meets the requirements of small file processing in the big data environment.

关 键 词：聚类 密度 网格单元 爬山法 宽度优先搜索 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]