针对高维数据的动态网格子空间聚类算法HDGCLUS  

Dynamic Grid Based Subspace Clustering Algorithm HDGCLUS for High Dimensional Data

作　　者：刘晨赫 刘小晴 刘青[1] 苏蕉 杨楠 肖林 LIU Chen-he;LIU Xiao-qing;LIU Qing;SU Jiao;YANG Nan;XIAO Lin(Department of Computer,Information School,Renmin University of China,Beijing 100872,China)

机构地区：[1]中国人民大学信息学院计算机系,北京100872

出　　处：《小型微型计算机系统》2018年第9期1895-1899,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(31670725)资助

摘　　要：目前涌现出大量高维的基因表达数据、图像、文本数据,高维数据对传统的聚类分析方法提出挑战.CLIQUE是最早提出在子空间中搜索稠密簇的聚类算法,它综合了基于网格聚类和基于密度聚类的算法特点,从单一维度开始自底向上地搜索子空间中的簇.但由于算法复杂度与参数敏感度较高,同时它采用的固定网格划分、MDL剪枝等技术,容易破坏密集区域的边缘或者丢失一些有用信息,使得算法在处理高维数据时不能满足效率、准确率等方面的性能要求.本文基于CLIQUE提出了改进的HDGCLUS(High-Dimensional Genomic data subspace CLUStering)算法,HDGCLUS采用基于稀疏区域的动态网格划分技术,实现了网格的动态划分和稠密区域的动态合并,并加入了边界调整技术,减少了初始候选密集单元个数,避免了人工输入网格参数和边界数据信息的丢失,提高了聚类质量和算法效率.同时HDGCLUS采用静态剪枝和信息增量动态剪枝相结合的技术,进一步降低了算法复杂度,优化了算法性能,并在真实数据集上取得良好的实验效果.A tremendous amount of high-dimensional images，texts，and microarray data emerge in various application fields.The high dimensionality of data brings about great challenge on clustering method.CLIQUE is the first algorithm attempting to find clusters in the subspace，it combines the feature of grid-based clustering and density based clustering.However，CLIQUE has high complexity of time and high sensitivity parameters.The fixed grid and MDL pruning techniques of CLIQUE are easy to destroy the edge of dense regions or lose some useful information.This paper proposes an improved algorithm based on CLIQUE，called HDGCLUS（High-Dimensional Genomic data subspace CLUStering）.HDGCLUS uses dynamic grid technology based on sparse regions to achieve a dynamic partitioning and merging dense area of the grid.HDGCLUS uses a boundary adjustment technology to improve the clustering quality，meanwhile it uses the combined technologies of static pruning and information incremental dynamic pruning to optimize the efficiency and reduce the complexity of algorithm.Finally，a series of comparative experiments have verified the superior performance of HDGCLUS on dealing with highdimensional data.

关 键 词：子空间聚类 高维数据 动态网格 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]