一种基于密度的快速聚类算法的改进

第７卷第４期　太原师范学院学报（自然科学版）　２００８年１２月　ＪＯＵＲＮＡＬ　ＯＦ　ＴＡＩＹＵＡＮ　ＮＯＲＭＡＬ　ＵＮＩＶＥＲＳＩＴＹ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ）Ｖｏ１．７　Ｎｏ．４　Ｄｅｃ．２００８　一种基于密度的快速聚类算法的改进　孙凌燕杨　明　（中北大学数学系，山西太原０３００５１）　［摘要］ＦＤＢＳＣＡＮ算法是对典型密度聚类算法ＤＢＳＣＡＮ的一个改进算法，在一定程度上加　快了聚类速度，但其在聚类过程中容易丢失一部分对象，成为噪声，影响了聚类结果．文章针对　ＦＤＢＳＣＡＮ算法存在的问题进行了深入的研究，提出从核心领域中的核心点中选择代表对象的方　法，在一定程度上解决了丢失点的问题．　（关键词］　快速算法；密度；核心点；代表对象　［文章编号］１６７２—２０２７（２００８）０４—０００５—０３［中图分类号］ＴＰ３１１．１３；ＴＰ３９１［文献标识码］Ａ　０　引言　在数据挖掘领域中，聚类分析是一项重要的研究课题，其聚类方法和算法设计在国内外得到了非常广泛　的研究［１　］．与分类不同，聚类的目标是在没有任何先验知识的前提下，根据数据的相似性将数据聚合成不　同的簇，使得相同簇中的元素尽可能相似，而不同簇中的元素差别尽可能大，因此又称为非监督分类．没有任　何一种聚类技术（聚类算法）可普遍适用于揭示各种多维数据集所呈现出来的多种多样的结构ｆ８］．因此根据　数据在聚类中的集聚规则以及应用这些规则的方法，聚类算法大致可以分为以下几类：层次聚类算法、划分　聚类算法、基于密度的聚类算法、基于网格的聚类算法和基于模型的聚类算法　］．　１基于密度的聚类算法ＤＢＳＣＡＮ　Ｅｓｔｅｒ　Ｍａｒｔｉｎ等人提出的ＤＢＳＣＡＮ算法是一个基于高密度连接区域的密度聚类方法，它能够发现任意　形状簇，并能有效地处理噪声点Ｉｖ．　ＤＢＳＣＡＮ的算法思想是：从数据集Ｄ中的任意一个点Ｐ开始，查找Ｄ中所有关于Ｅｐｓ和ＭｉｎＰｔｓ的从　Ｐ密度可达的点．若Ｐ是核心点则其邻域内的所有点和Ｐ同属于一个簇，这些点将作为下一轮的考察对象　（即种子点），并通过不断查找从种子点密度可达的点来扩展它们所在的簇，直至找到一个完整的簇；若Ｐ不　是核心点即没有对象从Ｐ密度可达，则Ｐ被暂时地标注为噪声．然后，算法对Ｄ中的下一个对象重复上述过　程……当所有种子点都被考察过，一个簇就扩展完成了．此时，若Ｄ中还有未处理的点，算法则进行另一个　簇的扩展；否则，Ｄ中不属于任何簇的点即为噪声　９］．　２快速聚类算法ＦＤＢＳＣＡＮ　ＤＢＳＣＡＮ算法将区域查询得到的所有未被处理过的点都作为种子点，留待下一步扩展处理．对于大规　模数据集中的较大簇而言，这种策略会使种子点的数目不断膨胀，算法所需的内存空间也会快速增加．为了　解决这个问题，周水庚等人提出了ＦＤＢＳＣＡＮ（Ｆａｓｔ　ＤＢＳＣＡＮ）算法ｍ　．该算法通过选用核心点邻域中的部　分点作为种子点来扩展簇，从而大大减少区域查询的次数，降低Ｉ／Ｏ开销，实现快速聚类．　对某一个核心点Ｐ来说，其邻域中的各个点的邻域会互相覆盖．因此，对Ｐ的邻域中的所有点都执行区　域查询操作，会造成部分对象被重复查询，极大地浪费了计算资源．为了减少浪费，可以只选择核心点邻域中　收稿日期：２００８—０９—１１　基金项目：国家自然基金三维ＣＴ的统计重建算法研究（６０７７２１０２）；山西省研究生创新项目（２００６１０２４）．　作者简介：孙凌燕（１９８２一），女，山西大同人，中北大学数学系在读硕士研究生，主要从事聚类分析及图像处理方面的研究　６　太原师范学院学报（自然科学版）　第７卷　的部分代表点用于簇的扩展，这样只有这些代表点需要进行区域查询操作，因此区域查询的次数大大减少，　算法的速度也大大加快了．　选择代表点需要考虑两个问题：１）代表点的个数；２）选择哪些点作代表点．该算法采用如下规则：对于　维空间，选择２　个代表点，也就是说，在每一维上，选择两个点作为代表点用于簇的扩展．另外，选择处于邻　域边沿的点作为代表点．因为对于靠近邻域内部的点来说，其邻域往往被靠近邻域边沿的点的邻域所覆盖，　所以，其邻域中的点可以通过对靠近邻域边沿的点进行区域查询来获得．如图１所示，二维空间中，核心对象　Ｐ的邻域被其四个代表对象Ｐ　，Ｐ　，Ｐ。，Ｐ　的邻域所覆盖．　３　ＦＤＢＳＣＡＮ算法的不足与改进　文献［１０］中给出了从核心对象的邻域中选择代表种子对象的算法．其基本思想是：首先选出一个与核心对象被选出的代表对象最远的对象作为下一个代表对象，直　到选出所需的全部代表对象为止．该文献中并未指出找　●　●　●　●　●●　●　・－　・　・　最远的对象作为第１个代表对象；随后则选出离所有已　－　离所有已被选出的代表对象最远的对象时最远怎样衡　量，本文采用距离和最大作为衡量最远的一个标准，也就　是找离所有已被选出的代表对象距离和最大的点作为下　一图１二维空间中的邻域及代表对象　Ｆｉｇ．１　Ｎｅｉｇｈｂｏｒｈｏｏｄ　ａｎｄ　ｒｅｐｒｅｓｅｎｔａｔｉｖｅ　ｏｂｊｅｃｔｓ　个代表对象．　该方法在选出一个代表对象以后，先要查询该代表对象是否为核心点，若是核心点，继续寻找该核心点　邻域中的代表对象；若不是，则不进行任何操作．如此就可能出现一种情况：若一个核心对象的代表对象中有　非核心点，则不考虑非核心点代表对象．那么该核心对象的邻域就变成被其他三个甚至两个核心点代表对象　的邻域所覆盖，这样核心对象的邻域就不能被完全覆盖，从而　出现丢失点的情况．当出现极端情况，也就是所有代表对象均　・　为边界点时，该类将不再扩展．　我们仍以二维空间为例，对于二维空间，代表对象数为　４．图２为核心对象Ｐ的邻域未被完全覆盖的情况：　Ｐ　，Ｐ　，Ｐ。，Ｐ　为以Ｐ为核心对象时选出的代表对象，其　中Ｐ　，Ｐ　，Ｐ　是核心点，Ｐ。为非核心点，根据算法要查询代表　对象是否为核心点，若是核心点，则将其看作核心对象进行下　一轮查询，若不是则不作任何查询．因此要寻找以Ｐ　，Ｐ　，Ｐ　●　为核心对象的邻域内的代表对象，而Ｐ。为边界点，对其不做　任何操作也不查询其邻域内的点．这样核心对象Ｐ的邻域相　当于只有Ｐ　，Ｐ　，Ｐ　三个代表对象的邻域覆盖，不能将Ｐ的邻　图２核心对象Ｐ的邻域及其代表对象　Ｆｉｇ．２　Ｎｅｉｇｈｂｏｒｈｏｏｄ　ａｎｄ　ｒｅｐｒｅｓｅｎｔａｔｉｖｅ　ｏｂｊｅｃｔｓ　ｏｆ　ｐｏｉｎｔ　Ｐ　域全部覆盖，引起一些对象的丢失．例如图２中显示的未覆盖邻域中的对象ｑ　，ｑ。．虽然这些丢失对象已经作　为点Ｐ邻域内的点而与点Ｐ归为一类，但若有一些点唯一地从这些点密度可达，则会引起点甚至是类的丢　失．例如小方形邻域中的点为丢失对象．　针对以上这种情况，本文提出在选择代表对象时直接从核心对象邻域中的核心点集中选择，这样不仅保　证了核心对象邻域被四个代表对象邻域完全覆盖，也减少了下一步是否是核心点的查询．因为减少了多次查　询核心点的步骤，从而在一定程度上也加快了运算速度．　４　实验结果　对于图２中的核心对象户，改用本文所提出的方法以后，代表对象就变成了四个核心点Ｐ　，户ｚ，Ｐ　和ｑ　．　这样核心对象Ｐ的邻域被四个核心代表对象邻域完全覆盖，而且小方形邻域中的点在ｑ　邻域内，因此与ｇ　同属一类，进而与Ｐ属于同一类．聚类结果如图３．　第４期　ｌ　孙凌燕等：一种基于密度的快速聚类算法的改进　ｌｌ　　ｎ　ｌ　｝ｌ　ｌ　ｎ　ｎ　Ｉ　ｌ　ｌ　ｌ　ｌ　ｎ　ｌ　ｌｌ　９　２　２　２　２　２　：２　ｚ２　ｚｌ　１　ｌ　ｌ　ｌ　１　ｎ　２　２　２　２２２　２　２　２　２，　２　＇　ｚ　＇　１　２。２　“　ｌ　ｌ　２　２　２　２　２　２２　“　ｎ　ｌ　ｍ　ｎ　ｎ　ｎ　ｎ　图３－ａ　ＦＤＢＳＣＡＮ算法　Ｆｉｇ．３－ａ　ＦＤＢＳＣＡＮ　ａｌｇｏｒｉｔｈｍ　图３－ｂ　改进后的聚类结果　Ｆｉｇ．３－ｂ　Ｉｍｐｒｏｖｅｄ　ｃｌｕｓｔｅｒｉｎｇ　ｒｅｓｕｌｔ　５　结论　本文在对快速聚类算法ＦＤＢＳＣＡＮ进行深入研究的基础上，具体提出了一种选最远距离核心对象的方　法，并且针对其核心对象是非核心点就不作查询，以至于丢失点的情况作了详细讨论，并提出了改进方法．在　一定程度上解决了丢失点的情况，同时也加快了聚类速度．　参考文献：　［１］Ｅｓｔｅｒ　Ｍ，Ｋｒｉｅｇｅｌ　Ｈ　Ｐ，Ｓａｎｄｅｒ　Ｊ，ｅｔ　ａ１．Ａ　ｄｅｎｓｉｔｙ—ｂａｓｅｄ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｄｉｓｃｏｖｅｒｉｎｇ　ｃｌｕｓｔｅｒｓ　ｉｎ　ｌａｒｇｅ　ｓｐａｔｉａｌ　ｄａｔａｂａｓｅｓ　ｗｉｔｈ　ｎｏｉｓｅ　ｒＣ］．Ｉｎ：Ｐｒｏｃ．２ｎｄ　Ｉｎｔ．Ｃｏｎｆ．ｏｎ　Ｋｎｏｗ　ｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ，Ｐｏｒｔｌａｎｄ．ＯＲ，１９９６：２２６—２３１　　Ｍ．Ｂｒｅｕｎｉｇ　Ｍ，Ｋｒｉｅｇｅｌ　Ｈ—Ｐ，ｅｔ　ａ１．ＯＰＴＩＣＳ：ｏｒｄｅｒｉｎｇ　ｐｏｉｎｔｓ　ｔｏ　ｉｄｅｎｔｉｆｙ　ｔｈｅ　ｃｌｕｓｔｅｒｉｎｇ　ｓｔｒｕｃｔｕｒｅ［Ｃ＇］．Ｉｎ：Ｐｒｏｃ．ＡＣＭ　Ｓ　［２３　Ａｎｋｅｒｓｔ１ＧＭＯＤ’９９．Ｉｎｔ．Ｃｏｎｆ．ｏｎ　Ｍａｎａｇｅｍｅｎｔ　ｏｆ　Ｄａｔａ．Ｐｈｉｌａｄｅｌｐｈｉａ，ＰＡ，１９９９：４９—６０　［３］　Ｂｒｅｕｎｉｇ　Ｍ，Ｋｒｉｅｇｅｌ　Ｈ—Ｐ，Ｎ　ｇ　Ｒ　Ｔ，ｅｔ　ａ１．ＬＯＦ：ｉｄｅｎｔｉｆｙｉｎｇ　ｄｅｎｓｉｔｙ—ｂａｓｅｄ　ｌｏｃａｌ　ｏｕｔｌｉｅｒｓ［Ｃ］．Ｉｎ：Ｐｒｏｃ．ＡＣＭ　ＳＩＧＭＯＤ　２０００　Ｉｎｔ．　Ｃｏｎｆ．Ｏｎ　Ｍａｎａｇｅｍｅｎｔ　ｏｆ　Ｄａｔａ．Ｄａｌｌｅｓ，ＴＸ，２０００：９３—１０４　［４］　Ｚｈｏｕ　Ｙｏｎｇ—ｆｅｎｇ．Ｌｉｕ　Ｑｉｎｇ—ｂａｏ，ｅｔ　ａ１．Ａｎ　ｉｎｃｒｅｍｅｎｔａｌ　ｏｕｔｌｉｅｒ　ｆａｃｔｏｒ　ｂａｓｅｄ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍｉＣ］．Ｉｎ　ｔｈｅ　Ｆｉｒｓｔ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ　ａｎｄ　Ｃｙｂｅｒｎｅｔｉｃｓ．Ｃｈｉｎａ，Ｎｏｖ，２００２：１　３５８—１　３６１　ｎ，Ａｎｔｈｏｎｙ　Ｋ，Ｈａｎ　Ｊｉａ—ｗｅｉ．Ｍｉｎｉｎｇ　ｔｏｐ—ｎ　ｌｏｃａｌ　ｏｕｔｌｉｅｒｓ　ｉｎ　ｌａｒｇｅ　ｄａｔａｂａｓｅｓ［Ｃ］．Ｉｎ：Ｐｒｏｃ．ＡＣＭ　ＫＤＤ　２００１　Ｓａｎ　Ｆｒａｎｃｉ—　［５］　Ｗｅｎ　ＪｉＳＣＯ，Ｃａｌｉｆｏｒｎｉａ　ＵＳＡ，２００１：２９３—２９８　［６］　Ｉ　ｉｕ　Ｑｉｎｇｂａｏ，Ｓｕ　Ｄｅｎｇ，Ｌｕ　Ｃｈａｎｇｈｕｉ，ｅｔ　ａ１．Ｒｅｌａｔｉｖｅ　ｄｅｎｓｉｔｙ　ｂａｓｅｄ　Ｋ—ｎｅａｒｅｓｔ　ｎｅｉｇｈｂｏｒｓ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍｉＣ］．Ｉｎ：Ｐｒｏｃ．２００３　Ｉｎｔ．Ｃｏｎｆ．ｏｎ　Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ　ａｎｄ　Ｃｙｂｅｒｎｅｔｉｃｓ．Ｘｉ’ａｎ，Ｃｈｉｎａ，２００３：１３３—１３７　［７］　张西芝，姬波，邱保志．基于网格的多密度聚类算法［Ｊ］．微计算机信息，２００５，２１（１２－３）：１０１—１Ｏ３　［８］　Ｓａｍｂａｓｉｖａｍ　Ｓ，Ｔｈｅ０ｄｏｓｏｐ０ｕｌ０ｓ　Ｎ．Ａｄｖａｎｃｅｄ　ｄａｔａ　ｃｌｕｓｔｅｒｉｎｇ　ｍｅｔｈｏｄｓ　ｏｆ　ｍｉｎｉｎｇ　ｗｅｂ　ｄｏｃｕｍｅｎｔｓ＿Ｊ］．Ｉｓｓｕｅｓ　ｉｎ　Ｉｎｆｏｒｍｉｎｇ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ，２００６（３）：５６３—５７９　［９］　栾丽华，吉根林．一种基于四叉树的快速聚类算法［Ｊ］．计算机应用，２００５，２５（５）：１　００１一ｌ　００３　［１Ｏ］　周水庚，周傲英，曹晶，等．一种基于密度的快速聚类算法［Ｊ］．计算机研究与发展，２０００，３７（１１）：１　２８７—１　２９２　Ｉｍｐｒｏｖｅｄ　Ｆａｓｔ　Ｃｌｕｓｔｅｒｉｎｇ　Ａｌｇｏｒｉｔｈｍ　Ｂａｓｅｄ　ｏｎ　Ｄｅｎｓｉｔｙ　Ｓｕｎ　Ｌｉｎｇｙａｎ　Ｙａｎｇ　Ｍｉｎｇ　（Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｍａｔｈｅｍａｔｉｃｓ，Ｎｏｒｔｈ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｃｈｉｎａ，Ｔａｉｙｕａｎ　０３００５１，Ｃｈｉｎａ）　￣Ａｂｓｔｒａｃｔ３　Ｔｈｅ　ＦＤＢＳＣＡＮ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ａｎ　ｉｍｐｒｏｖｅｍｅｎｔ　ａｌｇｏｒｉｔｈｍ　ｔｏ　ｔｈｅ　ｔｙｐｉｃａｌ　ｄｅｎｓｉｔｙ—　ｂａｓｅｄ　ｃｌｕｓｔｅｒ　ａｌｇｏｒｉｔｈｍ　ＤＢＳＣＡＮ，ｗｈｉｃｈ　ｐｉｃｋｓ　ｕｐ　ｔｈｅ　ｓｐｅｅｄ　ｏｆ　ｔｈｅ　ｃｌｕｓｔｅｒ　ｉｎ　ｓｏｍｅ　ｄｅｇｒｅｅ，ｂｕｔ　ｉｔ　ｓ　ｅａｓｙ　ｔｏ　ｌｏｓｅ　ａ　ｐａｒｔ　ｏｆ　ｔｈｅ　ｏｂｊｅｃｔｓ　ｉｎ　ｔｈｅ　ｐｒｏｃｅｓｓ　ｏｆ　ｃｌｕｓｔｅｒｉｎｇ　ａｎｄ　ｂｅｃｏｍｅ　ｎｏｉｓｅ，ｉｍｐａｃｔ　ｔｈｅ　ｒｅｓｕｌｔｓ　ｏｆ　ｃｌｕｓｔｅｒｉｎｇ．Ｔｈｅ　ａｒｔｉｃｌｅ　ｈａｓ　ｃｏｎｄｕｃｔｅｄ　ａｎ　ｉｎ—ｄｅｐｔｈ　ｒｅｓｅａｒｃｈ　ｔｏ　ａｉｍ　ａｔ　ｔｈｅ　ｅｘｉｓｔｅｎｔ　ｐｒｏｂｌｅｍｓ　ｏｆ　ｔｈｅ　ＦＤＢＳＣＡＮ　ａｌｇｏｒｉｔｈｍ，ｐｒｏｐｏｓｅｄ　ａ　ｍｅｔｈｏｄ　ｔｈａｔ　ｃｈｏｉｃｅ　ｒｅｐｒｅｓｅｎｔａｔｉｖｅ　ｏｂｊｅｃｔｓ　ｆｒｏｍ　ｃｏｒｅ　ｐｏｉｎｔｓ　ｉｎ　ｔｈｅ　ｃｏｒｅ　ｆｉｅｌｄｓ，ｒｅｓｏｌｖｅｓ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｏｆ　ｌｏｓｓ　ｐｏｉｎｔｓ　ｔｏ　ａ　ｃｅｒｔａｉｎ　ｅｘｔｅｎｔ．　［Ｋｅｙ　ｗｏｒｄｓ］　ｆａｓｔ　ａｌｇｏｒｉｔｈｍ；ｄｅｎｓｉｔｙ；ｃｏｒｅ　ｐｏｉｎｔ；ｒｅｐｒｅｓｅｎｔａｔｉｖｅ　ｏｂｊｅｃｔｓ