2. 遵义师范学院 物理与电子科学学院, 贵州 遵义 563002
2. School of Physics and Electronics, Zunyi Normal University, Zunyi Guizhou 563002, China
作为数据挖掘和人工智能领域的重要研究内容,聚类是一种无监督模式识别方法,即在没有任何先验信息的指导下,从一个数据集中发现潜在的相似模式,对数据集进行分组,以使得同一类内的相似性尽可能大,同时不同类之间的差异性尽可能大。近年来,数据挖掘在许多领域有广泛的应用,例如:图像[1]、医药[2]、航空[3]等领域。近年来,从卫星、影像和其他资源中获取的巨大的空间数据急速增长。由于巨大的数据数量级和数据类型的复杂度,提升数据挖掘的效率成为数据挖掘的重要挑战。随着数据规模和维度的增长,传统的聚类算法不能满足实际应用的要求。对于大规模数据来说,如何在聚类过程中快速寻找聚类中心以及如何合理合并子划分数据,从而得到高效、准确的聚类结果,是目前大规模数据乃至大数据聚类算法存在的问题之一[4-6]。
由于自顶向下的网格划分方法采取分而治之的策略,根据数据的分布对空间进行划分,受到数据空间维度的影响较小,可以快速地将大型高维数据集中的簇分隔开,使问题规模不断减小。基于网格的聚类算法包括:统计信息网格法(Statistical Information Grid, STING)[7]、小波聚类(WaveCluster)[8]、查询聚类(Clustering in Quest, CLIQUE)[9], 以及其他改进的网格聚类算法(Statistical Information Grid+, STING+)[10]、基于层次方法的平衡迭代规约和聚类(Balanced Iterative Reducing and Clustering Using Hierarchies, BIRCH)[11-12]等算法。其中STING算法利用存储在网格单元中的统计信息聚类;WaveCluster利用一种小波转换方法来聚类;CLIQUE是一种在高纬数据空间中基于网格和密度的聚类方法。通常聚类使用的数据集中,各个类的密度差别很大,网格聚类中通常使用密度阈值来控制网格划分的大小,从而导致网格聚类对于不同密度的数据聚类的效果不理想。
近年来,在《Science》上发表的密度峰值聚类(Density Peak Clustering, DPC)算法能够有效、快速地发现任意形状的簇[13]。该方法同时具有K中心点算法(K-medoids)[14-16]、基于密度的空间聚类(Density-Based Spatial Clustering of Applications with Noise, DBSCAN)算法[17-18]和均值漂移(Mean-Shift)[19]聚类的特点,简洁新颖。DPC的核心思想在于对聚类中心点的计算,聚类中心点具有本身密度大和与其他密度更大的数据点之间的距离相对更大的特点。但密度峰值聚类算法是个典型的密度聚类算法,无法处理大规模数据集。
本文基于密度峰值聚类快速寻找中心的思想,提出一种网格粒化的聚类算法,通过网格对数据进行粒化,采用网格内样本点的频度作为每个网格的密度,避免了局部密度公式带来的选取中心点失效的问题。由于采用网格化对数据进行统计频度,即可以看成是将每一个网格内的样本点进行粒化,因此适合于处理大规模数据。
1 相关定义 1.1 DPC聚类算法密度峰值聚类算法的思想简单新颖,首先计算每个点的两个变量:局部密度和与高密度点之间的距离。对于聚类中心的选取是基于两个基本假设:1)聚类中心的密度高于其邻近的样本点的密度;2)聚类中心与比其密度还高的聚类中心的距离相对较大。显然,聚类中心点是局部密度和与高密度点之间的距离均较大的点,聚类过程中的聚类中心的数目可以很直观地选取。在这样的模型中,密度峰值聚类主要有两个需要计算的量:局部密度ρ和相对距离δ。局部密度和相对距离的定义分别如下:
定义1[7] 样本点i的局部密度定义如下:
$ {\rho _i} = \sum\limits_j {\chi ({d_{ij}} - {d_c})} $ | (1) |
其中
定义2[7] 样本点i的相对距离:
$ {\delta _i} = \left\{ {\begin{array}{*{20}{c}} {\mathop {\min }\limits_{j \in I_S^i} \{ {d_{ij}}\} ,}&{I_S^i \ne \emptyset }\\ {\mathop {\max }\limits_{j \in I_S^i} \{ {d_{ij}}\} ,}&{I_S^i = \emptyset } \end{array}} \right. $ | (2) |
其中,指标集
图 1(a)所示,为二维散点图,其中样本点编号代表自身的局部密度,不同的颜色代表不同的类。图 1(b)为以局部密度ρ为横坐标和相对距离δ为纵坐标产生的图 1(a)的数据集对应的决策图,决策图为本文提供了一种手动选取聚类中心的启发式方法。在图 1(b)中选择同时具有较大局部密度和相对距离的点(矩形虚线框内的点),由于这些点的密度较大,邻域中的邻居点较多,并且与比它密度更大的点的距离较远,所以将这些点标记聚类中心。密度峰值聚类算法具体步骤如下。
算法1 密度峰值聚类算法[13]。
输入 数据样本集,样本点之间的距离矩阵;
输出 聚类个数M,Ck(k=1, 2, …, M)。
1) 输入距离矩阵;
2) 初始化参数dc;
3) 计算每个点的局部密度ρ,相对距离δ以及邻居点;
4) 输出决策图,并选取聚类中心;
5) 将非聚类中心进行归类;
6)将剩下数据分为cluster core和cluster halos,并检测噪声点。
由于算法在计算局部密度时,需要计算距离矩阵,假设有个N个数据样本点,则计算和存储这些距离的时空复杂度均为O(N2);随着数据量的增长,仅就计算和存储距离矩阵而导致的巨大时空复杂度就变得难以接受,导致了该算法不适用于大规模数据。
1.2 STING网格聚类STING聚类算法是一种典型的基于网格的聚类算法。文献[7]将数据空间划分为层次结构,也就是使用一个多级多层次的空间结构。空间的顶层是第一层,它的下一层是第二层,依此类推。第i层中的一个单元与它的第i+1层的子空间单元的集合保持一致。除了底层网格都有4个子空间单元,而子空间单元都是父单元的1/4。如图 2所示,为STING网络结构,其顶层网格单元与全局数据空间的信息相一致。底层网格的大小依赖于网格数据的密度。根据经验来选择的尺寸,例如数据的平均数目,但是每个单元存在的数据数目从几十到上千不等。此外,数据空间的层数可以改变,通过修改上一层单元的数目。除非特殊情况下,将使用4作为默认参数。文献[7]假设空间为两维空间,因为这样比较容易推广到高维模型层次结构。
STING聚类可以快速查询网格区域的信息,包括相应区域的密度、面积、数据个数等。一般在空间数据集中,数据挖掘和知识发现是对隐藏知识、空间关系、那些并不明显的兴趣特征和模型的发掘。不管是理解空间数据,还是捕获空间和非空间数据的本质问题,STING算法都具有很好的效果。此外,这种关系发现能以简单的方式去展示数据,通过重组数据空间来认识数据含义,使算法达到高效的表现。
2 基于密度峰值的网格聚类基于当前对大规模数据进行聚类存在的问题,本文基于密度峰值聚类快速寻找中心的思想,提出一种新的网格聚类思想,用于处理大规模数据。该思想主要分为以下3个方面。
2.1 数据空间的网格粒化首先利用如算法2所示的STING网格划分对数据进行粒化,以网格单元数据的统计信息代替原始的数据点,从而达到数据压缩的目的。
算法2 STING网格划分。
输入 数据样本集X={x1, x2, …, xn}。
输出 网格单元集合G={g1, g2, …,gn}。
1) 归一化到D={d1, d2, …, dk}维数据空间中,使得[0, 1]d⊂D,其中d是D的维度;
2) 计算划分的尺度参数ε,使用式(3)求出,并使用式(4)进行维度划分,进而进行数据空间的网格划分;
3) 扫描整个数据集,把数据集中的每个点都放入网格划分后的数据空间中,并记录网格单元的信息(如:网格空间的数据点个数等),记录网格单元的个数为n。
其中参数ε为网格划分尺度。网格划分的粒度不同会影响数据聚类的效果,不能太大也不能太小:太大会丢失大多网格单元的数据,导致精确度不够;网格单元太小,会导致每个网格密度相似,不能区分稠密网格单元,同时,网格太小,如每个网格一个数据,就会导致跟原数据处理效果类似,达不到快速处理数据的目的。参数ε根据数据空间中的数据个数求得:
$ \varepsilon = N/k $ | (3) |
$ \mathop {\lim }\limits_{N \to \infty } k = \infty $ | (4) |
$ \mathop {\lim }\limits_{N \to \infty } {N^{ - 1}}k = 0 $ | (5) |
$ \mathop {\lim }\limits_{N \to \infty } {({\rm{lb}}\;N)^{ - 1}}k = \infty $ | (6) |
可以得出
$ \varepsilon = \sqrt N $ | (7) |
假设数据集为X={x1, x2, …, xN}是在D={d1, d2, …, dk}维空间的数据,其中N是数据集合中数据点的个数,k是数据空间维度的个数(数据属性的个数), 则每个维度被分为ε等分,所以每个维度划分为:
$ {d_i} = \{ {c_1},{c_2},{c_3},...,{c_\varepsilon }\} $ | (8) |
该步骤的目的是在粒化后的所有网格单元中快速找出符合假设条件的中心点。首先,扫描整个数据集,即将网格单元中数据点的个数作为网格单元的频度;然后,利用聚类中心网格单元与其他聚类中心网格单元的距离大,而与其网格单元类簇中其他网格单元的距离小的思路,求出各个网格单元的相对距离。算法步骤如下。
算法3 快速寻找中心单元算法。
输入 网格单元集合G={g1, g2, …, gn}。
输出 中心单元Centerk(k=1, 2, …, M)。
1) 计算网格单元的密度ρi,即网格单元i中的数据点个数。
2) 计算网格单元的距离δi。将网格单元按照频度的大小降序排序,并记录其标序,即:{qi}i=1n为{ρi}i=1n的降序排列的标号,降序排列为ρq1≥ρq2≥…≥ρqn。则相对距离δi的定义为:
$ {\delta _{qi}} = \left\{ {\begin{array}{*{20}{l}} {\mathop {{\rm{min}}}\limits_{j < i} \{ dis{t_{{q_i}{q_j}}}\} ,}&{i \ge 2;}\\ {\mathop {{\rm{max}}}\limits_{j \ge 2} \{ {\delta _{qj}}\} ,}&{i = 1} \end{array}} \right. $ | (9) |
其中distqiqj代表网格单元qi和qj的欧氏距离。公式如下:
$ \begin{array}{l} dis{t_{ab}} = \\ \quad \sqrt {{{({a_{d1}} - {b_{d1}})}^2} + {{({a_{d2}} - {b_{d2}})}^2} + ... + {{({a_{dk}} - {b_{dk}})}^2}} \end{array} $ | (10) |
其中:a、b分别为两个网格空间单元;di为空间单元的维度。
3) 得出决策图,并选择中心单元。
例1 如图 3所示,通过网格粒化后,大部分数据点(除中心网格单元)重合在一起。这是因为非中心网格单元离它们最近的网格单元一般为相邻网格,这就导致许多网格单元重合在一起,这也方便我们选取中心网格单元。图 4为利用密度峰值的思想,得到的网格单元对应的决策图,很明显,有7个中心网格单元。
定义{ci}i=1Center为各个中心网格单元的编号,则Gci为第i个中心网格单元。按照其他各个非中心网格单元与中心网格单元的距离,将各个网格划分到相应的类簇中。同时,为每个类簇设置一个平局频度上限,这样就将类簇中其他网格单元分为核心网格单元和边界网格单元。综合上面的分析,给出提出的网格聚类算法的总体步骤,算法如下:
算法4 基于密度峰值的网格聚类。
输入 数据样本集X={x1, x2, …,xn}。
输出 聚类结果。
1) 数据预处理,为了统一量纲,本文对数据集进行归一化处理[0, 1],得出归一化后的数据集Data={x1, x2, …, xN};
2) 调用算法2,根据网格划分技术,将数据空间划分为均匀的网格空间;
3) 扫描数据集X={x1, x2, …,xN},将数据点分配到相应的网格单元中,并统计各个网格单元的密度信息;
4) 设置密度阈值τ把噪声网格单元剔除,网格密度小于τ的网格单元标记为无效网格单元;
5) 调用算法3计算网格中心单元,得出决策图并选取出中心单元:
6) 分配各个网格单元到各个类簇中,扫描整个数据空间,将网格单元中的数据点标记为相应的类别。
3 算法分析本文提出算法的时间开销包括计算网格粒化、网格单元的统计信息、网格单元的相对距离和分配到各个类簇中。其中花销最大的就是求网格单元的距离。STING划分网格时间复杂度为O(n),其行为花销在于统计数据集中数据点的个数。求网格单元的统计信息的时间花销也仅仅在于扫描一次数据,更新每个网格单元的统计信息,其时间复杂度也为O(n)。将网格单元的分配到各个类簇中仅与网格单元的个数相关,需要扫描整个网格空间,得到网格单元到每个聚类中心的距离,然后分配到相离最近的中心网格单元,其时间复杂度仅为O(R), 其中R为网格单元个数。本算法最大的开销在于求网格单元之间的距离,根据网格的个数,求除网格单元之间的距离,时间复杂度为O((n/ε)2),其中n为数据点数,ε为划分网格的参数。因此,算法的总的时间复开销为:
$ {T_{{\rm{all}}}} = O\left( n \right) + O\left( n \right) + O\left( {n/\varepsilon } \right) + O{\left( {n/\varepsilon } \right)^2} $ | (11) |
由式(4)可以看出,本文算法的时间复杂度为O((n/ε)2)。而DPC却需要求出整个点与点之间的距离,其时间复杂度为O(n2)。同理,由文献[13]可知,由于DPC的空间复杂度为O(n2),而本文算法空间复杂度只跟网格单元的个数相关,因此其空间复杂度为O((n/ε)2)。
4 实验仿真本文实验所采用的计算机硬件配置为Intel Core i5处理器(主频3.3 GHz)、8 GB内存;实验的软件环境为Windows10操作系统,采用Matlab编译环境。为了证明相对于DPC本文算法具有优越性,设计了实验1来进行对比验证。因为在DPC中,Matlab所处理的数据不能超过7000条,因此本文采用小规模数据集来与DPC进行对比实验。
实验1 采用UCI上面的4个人工数据集(Aggregation、Compound、Flame和Moons)进行实验,其中图 5分别为4个数据集的数据分布。
图 6为网格粒化后的数据分布,由图 6可以看出,聚类结果基本符合图 5中的数据分布情况。
表 1分别给出了本文提出的聚类算法与原始密度峰值算法的时间和准确率对比情况。
通过表 1可知,本文算法虽然时间上远少于DPC聚类算法,但是精确度却比DPC差,根本原因是本文算法通过网格粒化减小数据规模的同时也减小网格分辨率,从而降低了精度,即通过牺牲精度来换取时间的减少。相对于STING聚类来说,在图 5的4个数据集上本文算法的时间较少,在Aggregation、Compound、Flame三个数据集上准确率相对较高,而且由表 1可知,STING聚类算法稳定性较差。综合考虑,本文算法虽然精确度有所不足,但在粗粒度情形下可以处理大型数据集,处理速度快。而DPC不能处理大型数据集,处理速度缓慢成为它致命的缺点。因此,在对精确度要求不太高的情况下,本文算法还是有一定的价值。
实验2将采用大规模的数据集来测试本文算法在处理大规模数据上的性能。
实验2 如图 7(a)所示,为本文实验采用的测试数据集,使用人工生成的Moons数据集,共100万条数据。
图 7(b)为网格粒化后的数据分布,由图 8可以看出,聚类结果基本符合图 7中的数据分布情况。
通过仿真发现,本文提出的基于密度峰值的网格粒化算法在100万条数据的Moons数据集上总运行时间为15.435665 s,准确率为92.5%。由实验2可以发现,本文算法对处理大规模数据有着明显的优势,但是因为基于网格的算法,准确率会有明显下降的趋势。
5 结语基于密度峰值聚类算法可以发现任意簇且可以快速寻找聚类中心点的优点,本文提出了一种改进的网格聚类方法,既有DPC算法的优点,也具有网格聚类可以处理大规模数据的优点,同时在满足一定的时限约束条件下,本文算法取得了较满意的效果,初步实现了一种快速处理大规模数据的聚类算法模型。下一步工作需要研究在不同网格粒度对聚类结果的影响,以及结合Spark平台将算法推广到处理大数据上。
[1] | KITAMOTO A. Data mining for typhoon image collection[C]//Proceedings of the 2nd International Workshop on Multimedia Data Mining. New York:ACM, 2002:68-77. |
[2] | BELLAZZI R, ZUPAN B. Predictive data mining in clinical medicine:current issues and guidelines[J]. International Journal of Medical Informatics, 2008, 77(2): 81-97. DOI:10.1016/j.ijmedinf.2006.11.006 |
[3] | MATTHEWS B, DAS S, BHADURI K, et al. Discovering anomalous aviation safety events using scalable data mining algorithms[J]. Journal of Aerospace Computing Information and Communication, 2014, 11(7): 482-482. |
[4] | TAKIZAWA H, KOBAYASHI H. Hierarchical parallel processing of large scale data clustering on a PC cluster with GPU co-processing[J]. Journal of Supercomputing, 2006, 36(3): 219-234. DOI:10.1007/s11227-006-8294-1 |
[5] | CUI X, CHARLES J S, POTOK T E. The GPU enhanced parallel computing for large scale data clustering[J]. Future Generation Computer Systems, 2013, 29(7): 1736-1741. DOI:10.1016/j.future.2012.07.009 |
[6] | LI Y, YANG G, HE H, et al. A study of large-scale data clustering based on fuzzy clustering[J]. Soft Computing, 2016, 20(8): 3231-3242. DOI:10.1007/s00500-015-1698-1 |
[7] | WANG W, YANG J, MUNTZ R R. STING:a statistical information grid approach to spatial data mining[C]//Proceedings of the 23rd International Conference on Very Large Data Bases. San Francisco, CA:Morgan Kaufmann, 1997:186-195. |
[8] | CHEN L, YU T, CHIRKOVA R. Wave cluster with differential privacy[C]//Proceedings of the 24th ACM International on Conference on Information and Knowledge Management. New York:ACM, 2015:1011-1020. |
[9] | DUAN D, LI Y, LI R, et al. Incremental K-clique clustering in dynamic social networks[J]. Artificial Intelligence Review, 2012, 38(2): 129-147. DOI:10.1007/s10462-011-9250-x |
[10] | WANG W, YANG J, MUNTZ R. STING+:an approach to active spatial data mining[C]//Proceedings of the 15th International Conference on Data Engineering. Washington, DC:IEEE Computer Society, 1999:116. |
[11] | ZHANG T, RAMAKRISHNAN R, LIVNY M. BIRCH:an efficient data clustering method for very large databases[J]. ACM SIGMOD Record, 1996, 25(2): 103-114. DOI:10.1145/235968 |
[12] | HODGE V J, AUSTIN J. A survey of outlier detection methodologies[J]. Artificial Intelligence Review, 2004, 22(2): 85-126. DOI:10.1023/B:AIRE.0000045502.10941.a9 |
[13] | RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492-1496. DOI:10.1126/science.1242072 |
[14] | PARK H, JUN C. A simple and fast algorithm for K-medoids clustering[J]. Expert Systems with Applications, 2009, 36(2): 3336-3341. DOI:10.1016/j.eswa.2008.01.039 |
[15] | 马箐, 谢娟英. 基于粒计算的K-medoids聚类算法[J]. 计算机应用, 2012, 32(7): 1973-1977. (MA Q, XIE J Y. New K-medoids clustering algorithm based on granular computing[J]. Journal of Computer Applications, 2012, 32(7): 1973-1977.) |
[16] | 张雪萍, 龚康莉, 赵广才. 基于MapReduce的K-Medoids并行算法[J]. 计算机应用, 2013, 33(4): 1023-1025. (ZHANG X P, GONG K L, ZHAO G C. Parallel K-Medoids algorithm based on MapReduce[J]. Journal of Computer Applications, 2013, 33(4): 1023-1025.) |
[17] | ESTER B, KRIEGEL H, SANDER J, et al. A density based algorithm for discovering clusters in large spatial databases[C]//Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. Menlo Park, CA:AAAI Press, 1996:226-231. |
[18] | 周水庚, 周傲英, 金文, 等. FDBSCAN:一种快速DBSCAN算法[J]. 软件学报, 2000, 15(6): 735-744. (ZHOU S G, ZHOU A Y, JIN W, et al. FDBSCAN:a fast DBSCAN algorithm[J]. Journal of Software, 2000, 15(6): 735-744.) |
[19] | SARAGIH J, LUCEY S, COHN J F. Deformable model fitting by regularized landmark mean-shift[J]. International Journal of Computer Vision, 2011, 91(2): 200-215. DOI:10.1007/s11263-010-0380-4 |