基于区域密度的山峰聚类算法

摘 要：在确定聚类初始值的问题上，山峰聚类算法是一种简捷有效的算法，它既是一种对样本集进行近似聚类的算法，又可以作为其他聚类分析的基础，为其他聚类算法提供所需的初始聚类中心。但面对高维度数据具有局限性，为此，提出了基于区域密度的山峰聚类算法，试验结果证明，该算法适应性较强，聚类准确率和聚类的速度都有所提高。

关键词：区域；属性加权；密度；山峰聚类

中图分类号：TP911

聚类分析是数据挖掘中常用的方法，它的作用是将数据划分成有意义或有用的组（簇），即将特性相似的样本进行划分归类的过程[1，2]。作为数据挖掘其他方向的一个基点，在心理学、社会科学、生物学、统计学、模式识别、信息检索等许多领域都扮演着重要的角色。此外在高维空间也很容易找到聚类分析应用的例子。但多数聚类算法都存在以下几个问题：（1）需要事先聚类个数、初始聚类中心，人为的确定这些参数具有主观性、不确定性。（2）对于海量样本集或高维属性样本集，聚类分析的时间和空间开销大，聚类的结果差。（3）孤立点、噪音数据等对目标函数的影响不容忽视。文中提出一种基于区域密度的山峰聚类算法，用此算法既避免了原山峰聚类算法中随样本维数增加，时间复杂度呈指数增长的弊端，也避免了减法聚类在面对大量数据集时效率低下的问题。

1 山峰聚类法

山峰聚类法是由Yager和Filev在1994年提出的一种大致估计聚类中心的有效的聚类方法。它的思想是[3]将数据样本空间划分成有限的网格，并将所有网格的交叉点作为聚类中心的候选中心点，为每个交叉点构造山峰函数及计算其值，然后不断地修改山峰函数获取函数值最大的网格交叉点作为聚类中心。

2 基于区域密度的山峰聚类算法

现存的聚类算法在处理高维数据时，效果并不是很理想。主要的瓶颈在于不能确定聚类的类别数目和初始化聚类中心。随机的选取初始聚类中心或者采用基于谱系的方法，对于小量样本集而言，聚类效果不错。随着样本集的增加，前者往往陷入局部最优，后者运行效率明显下降。本文对数据进行预处理，增强了数据的可用性，引入了样本加权的思想，避免了山峰聚类中出现的计算量随样本维数呈指数增长的情况，是一种简捷有效的聚类算法。

2.1 数据预处理

样本集可能包含大量属性，随着数据属性个数（即维度）增加，许多数据分析变得非常困难，导致许多分类和聚类算法的分类准确率降低，聚类质量下降。特别是在高于三维以上的数据分析时，就需要进行必要的处理，将其降低到三维属性，使对样本集划分的区域相对合理。在文中算法里，主要采取了以下两种策略：

（1）属性加权。属性加权是一种保留或删除属性的可供选择的方法。属性越重要，所赋予的权值越大，而次要的属性赋予较小的权值。对于主要属性和次要属性泾渭分明的样本集，可以提取三个主要属性作为降维后的属性。

（2）维归约。维归约即通过创建新属性，将一些旧属性合并在一起来降低数据集的维度。对于不容易区分主要和次要属性的样本数据，可以对属性进行归约处理。如果属性较多，可以删除不相关的属性，把具有一定相似度的属性归为一类，从而将数据归约到较低维度。

2.2 相关概念和公式

（1）区域。以d为边长的正方形面积或正方体空间。如果样本点为2维属性，则为正方形面积；如果样本点为3维以上（含三维）属性，则为正方体空间。

（2）密度区域。在给样本点加权时，是基于密度加权的。所以这个区域是以r为半径的圆形面积或球形体积。 ，以保证所有的密度区域覆盖整个样本集区域。

（3）样本集区域。设a和b是样本集中所有任意两点之间相距最远的两点。以这两点之间的距离d作为边长，以两点之间的中心点作为样本集区域的中心点，以中心点对应的坐标值减去d/2的值作为样本集左上方的坐标，求得正方形的面积或正方体的体积。在划分样本集时，设所划分区域为：A1，A2，A3…An。要满足A1∪A2∪…An>=样本集区域，任意i，j∈n，Ai∩Aj=0。

（4）样本权值。在某样本密度区域内，给样本点赋予一定的权值，其公式为：

Di为每个密度区域内样本点Xi的样本权值；r为样本区域半径；k为样本区域内的所有样本点的数目。

2.3 算法的步骤

步骤1：确定样本集区域大小，设定相关参数k，ц等；

步骤2：对样本区域进行划分。所划分区域设为A1，A2，…An；

步骤3：对每个样本区域依次执行以下步骤：（1）对样本区域内的每个样本点依据密度区域为该样本点加权；（2）求出该样本区域权值最大的样本点，作为聚类中心。记为：Akk；k代表样本区域的标号。同时也作为候选聚类中心Vk。

步骤4：当不满足终止条件时，执行下面步骤：

步骤5：在聚类中心候选集V中选取山峰函数值最大的点作为第一个聚类中心（如果存在多个最大值点，任选其一作为第一个聚类中心。即公式 ；

步骤6：下一个聚类中心的获取需要消除已经辨别过的聚类中心的影响。可以通过修改山峰函数来实现上述要求，即公式 ；

步骤7：调整后，选择V中具有最大新山峰函数值的点为第二个聚类中心。

步骤8：不满足条件，跳到步骤5继续执行。满足终止条件时，结束算法。

3 仿真实验

3.1 实验及结果分析

仿真数据集在ASD数据集上进行了测试，结果如下。

选取不同的k和ц，分别进行聚类实验。当k=4，ц=0.5时，聚类结果如图2所示，样本集被划分为16个区域，图上符号“+”为聚类中心，共求得16个聚类中心，符号“o”表示聚类初始中心。当k=5，ц=0.5时，结果如图3所示，把样本集划分为25个区域，得到17个聚类。可见，k越大，划分的区域越多，聚类数目越多，聚类就越精确。

4 结束语

文中将样本权值引人山峰聚类算法，有效解决了聚类初始点的问题，而且对于多维数据进行了预处理，克服了大维度数据聚类的难度，降低了算法的时间复杂度，取的了较优的聚类精度。接下来的工作是将其进一步优化，应用到存在高维数据聚类的实际场合，验证其有效性和可移植性。

参考文献

[1]HANDD，MANNILAH，SMYTHP.Principlesofdatamining[M].CambridgeMA：MITPress，2001.

[2]JAINAK，DUBESRC.Algorithmsforclusteringdata[M].Engle2woodCliffs：PrenticeHall，1988.

[3]Pang-NingTan，MichaelSteinbach，VpinKumar.数据挖掘导论[M].范明，范宏建，译.北京：人民邮电出版社，2006：327-330.

[4]陈晓云，敏玉芳，郑良仁.一种快速山峰聚类算法[J].计算机应用研究，2008，25（7）.

[5]张，湛成伟，邓辉文.一种快速减法聚类算法[J].西南师范大学学报，2006.

作者简介：邓青（1983.6-），女，山西省大同市硕士研究生，毕业于辽宁工程技术大学计算机应用技术专业，研究方向：计算机网络，现职务：助教，单位：山西轻工职业技术学院。

作者单位：山西轻工职业技术学院信息工程系，太原 030013