高维数据的高密度子空间聚类算法  

High Density Subspace Clustering Algorithm for High Dimensional Data

作　　者：万静[1] 郑龙君 何云斌[1] 李松[1] WAN Jing;ZHENG Long-jun;HE Yun-bin;LI Song(School of Computer Science and Technology, Harbin University ofScience and Technology, Harbin 150080,China)

机构地区：[1]哈尔滨理工大学计算机科学与技术学院,哈尔滨150080

出　　处：《哈尔滨理工大学学报》2020年第4期84-94,共11页Journal of Harbin University of Science and Technology

基　　金：国家自然科学基金(61872105);黑龙江教育厅科学技术研究项目(1253lz004);黑龙江省留学归国人员科学基金(LC2018030).

摘　　要：高维数据具有稀疏性与易受维度灾难影响的特点,这使高维数据聚类的精度与的效率一直难以得到保证,因此采用子空间聚类的方式减小稀疏性与维度灾难对聚类结果的影响。首先采用随机抽样的方式从高维数据中挑选出适合聚类的维度生成子空间,并结合hoeffding界保证抽样结果的有效性。其次利用网格的邻接性,在子空间内生成混合网格,即可以保证数据的完整性也可以提高子空间密度。最后根据子空间的相似度与相异度,对维度剪枝,再次提高子空间密度。算法在加州大学欧文分校数据集(University of California-Irvine,UCI)上能够取得较好的结果,而且算法在的伸缩性以及抗噪声能力上有较好的表现。High-dimensional data have the characteristics of sparsity and vulnerability to dimension disaster,which makes it is difficult to ensure the precision and efficiency of high dimensional data clustering.Therefore the method of subspace clustering is adopted to reduce the impact of sparsity and dimension disaster on the clustering results.Firstly,random sampling is adopted to select the dimension which is suitable for clustering from high-dimensional data to generate subspace,and the hoeffding bound is combined to ensure the validity of sampling results.Secondly,by using the adjacency of the grid,mixed grids are generated in the subspace,which can guarantee the integrity of data and improve the density of the subspace.Finally,according to the similarity and dissimilarity of subspace,the dimension pruning is carried out to improve the subspace density again.The algorithm can achieve better results on UCI data set,and it has better performance in scalability and anti-noise ability.

关 键 词：子空间 高维 Clustering in quest(Clique) 样本分析 网格 

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