一种新的聚类算法：等密度线算法

２００２年６月　第２５卷第２期　北京邮电大学学报　Ｊｏｕｒｎａｌ　ｏｆ　Ｂｅｉｉｉｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｐｏｓｔｓ　ａｎｄ　Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ　Ｊｕｎ．２００２　Ｖｏ１．２５　Ｎｏ．２　文章编号：１００７—５３２１（２００２）０２—０００８　０６　一种新的聚类算法：等密度线算法　赵艳厂，　谢　帆，　宋俊德　（北京邮电大学电子工程学髋，北京１００８７６）　摘要　提出了一种新的聚类算法　等密度线聚类算法该算法从样本分布等密度线图的思想出发，　从图中找出样本分布比鞍集中的区域，从而发现隐含在样本集中的类．等密度线聚类算法不需要　输入任何参数，是一种无监督式聚类．它能皓自动发现任意形状的类，并且能有效地排除噪声干　扰．实验结果表明，等密度线聚类算法具有鞍快的聚类速度和较好的聚类效果．　关键词：数据挖掘－聚类；等密度线聚类　文献标识码：Ａ　中国分类号：ＴＰ１８１　Ｆ　Ｏ　２３５　ＤＩＬＣ：Ａ　Ｃｌｕｓｔｅｒｉｎｇ　Ａｌｇｏｒｉｔｈｍ　Ｂａｓｅｄ　ｏｎ　Ｄｅｎｓｉｔｙ—ｉｓｏｌｉｎｅ　ＺＨＡＯ　Ｙａｈ—ｃｈａｎｇ，ＸＩＥ　Ｆａｎ，　ＳＯＮＧ　Ｊｕｎ—ｄｅ　（Ｅｌｅｃｔｒｏｎｉｃ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｓｃｈｏｏｌ，Ｂｅｉｊｉｎｓ　Ｕｎｌｖｅｒｓｆｆｙ　ｏｆ　Ｐｏｓｔｓ　ａｎｄ　Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｂｅｉｊｉｎｓ　１００８７６　ｒ　Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ａ　ｎｅｗ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍ，ｄｅｎｓｉｔｙ—ｉｓｏｌｉｎｅ　ｃｌｕｓｔｅｒｉｎｇ（ＤＩＬＣ）ａｌｇｏｒｉｔｈｍ　ｉｓ　ｐｕｔ　ｆｏｒｗａｒｄ　ｉｎ　ｔｈｉｓ　ｐａｐｅｒ．ＤＩＬＣ　ｓｔａｒｔｓ　ｆｒｏｍ　ｔｈｅ　ｄｅｎｓｉｔｙ—ｉｓｏ１ｉｎｅ　ｆｉｇｕｒｅ　ｏｆ　ｓａｍｐｌｅｓ，　ａｎｄ　ｆｉｎｄｓ　ｒｅｌａｔｉｖｅｌｙ　ｄｅｎｓｅ　ｒｅｇｉｏｎｓ，ｗｈｉｃｈ　ａｒｅ　ｃｌｕｓｔｅｒｓ．ＤＩＬＣ　ｉｓ　ｃａｐａｂｌｅ　ｏｆ　ｅｌｉｍｉｎａｔｉｎｇ　ｏｕｔｌｉｅｒｓ　ａｎｄ　ｄｉｓｃｏｖｅｒｉｎｇ　ｃｌｕｓｔｅｒｓ　ｏｆ　ｖａｒｉｏｕｓ　ｓｈａｐｅｓ．Ｉｔ　ｉｓ　ａｎ　ｕｎｓｕｐｅｒｖｉｓｅｄ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｂｅｃａｕｓｅ　ｉｔ　ｒｅｑｕｉｒｅｓ　ｎｏ　ｉｎｔｅｒａｃｔｉｏｎ．Ｔｈｅ　ｈｉｇｈ　ａｃｃｕｒａｃｙ　ａｎｄ　ｅｆｆｉｃｉｅｎｃｙ　ｏｆ　ＤＩＬＣ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍ　ａｒｅ　ｓｈｏｗｎ　ｉｎ　ｏｕｒ　ｅｘｐｅｒｉｍｅｎｔｓ．　Ｋｅｙ　ｗｏｒｄｓ：ｄａｔａ　ｍｉｎｉｎｇ；ｃｌｕｓｔｅｒｉｎｇ；ｄｅｎｓｉｔｙ—ｉｓｏｌｉｎｅ　ｃｌｕｓｔｅｒｉｎｇ　近几年来，数据挖掘成为越来越热的一个研究方向，而聚类算法作为数据挖掘的主要方法　之一，也越来越引起人们的关注．所谓聚类，就是把大量的ｄ维数据样本（”个）聚集成ｋ个类　（　《一），使同一类内样本的相似性最大，而不同类内样本的相似性最小．本文中提出的等密度　线聚类ＤＩＬＣ（ｄｅｎｓｉｔｙ　ｉｓｏｌｉｎｅ　ｃｌｕｓｔｅｒｉｎｇ）算法，从等高线图的思想出发，根据样本分布密度生　成等密度线图，从图中找到样本分布比较集中的区域，从而得到较佳的聚类结果．　１传统的聚类算法及其局限性　目前．已经提出的聚类算法有很多，但是，其中很多算法都对样本数据的分布进行了一定　收稿日期：２００１—０６—２５　作者简升；赵艳厂（１８７　７），男，博士研究生　维普资讯 http://www.cqvip.com

第２期　赵艳厂等：一种新的聚类算法：等密度线算法　的假设，如球状分布（Ｋ—ｍｅａｎｓ算法　）、线形分布、平面分布（Ｋ—ｐｌａｎｅ算法Ｅ２］），等等．而层次　型聚类算法（如ＢＩＲＣＨ算法口　）中，由于用类的质心（ｃｅｎｔｒｏｉｄ）来代表类内的所有点，则将引起　更大的问题，很容易把比较细长的线形分布分割成好几个部分而分别归入别的类．　Ｊａｉｎ曾经提出了一种基于密度的聚类方法［４］，把样本集分割成互不重叠的一些区域，然后　计算每个区域中所含的样本数目，画出密度直方图，图中密度较大的区域就是类的中心．该算　法中，区域大小的选取对聚类结果有很大影响，区域过大就得不到有意义的类，而区域过小，算　法的时间复杂度和空间复杂度都将急剧增加　在参考文献［５］中也给出了一种基于密度的聚类算法，把“密度可达　和“密度连接”的点归　为一类　该算法不适用于高维的样本集，此外，还要输入邻域半径及密度阈值等参数，而邻域半　径需要经过复杂的计算并通过人工观察图形来确定，所以很难找到合适的参数值．　２等密度线聚类算法　聚类是指从输入的样本中找出一些类，使类内样本之间的相似度尽可能大，而类与类之间　样本的相似度尽可能小　换个角度来讲，也就是找出样本比较密集的部分，每一个密集部分就　是一个类．从这个角度出发，就可以设计一个密度函数，计算出每个样本附近的密度，从而根据　每个样本附近的密度值来找出那些样本相对比较集中的区域，这些区域就是我们要找的类．按　照聚类的第二种定义，这样生成的聚类，效果应该是最佳的．　等密度线聚类算法是从基于密度的聚类算法出发，结合等高线图的思想而提出的一种新　的聚类算法．在等高线图中，根据等高线不但可以确定那些是高山，还可以根据需要找出海拔　高于一定高度的山峰．同样，对于样本聚类，可以先计算出样本的分布密度，画出样本分布密度　的等高线图（即等密度线图）．然后，从图中选择合适　的等密度线，这些等密度线所包围的部分就是样本分　布比较密集的部分，也就是要发现的类．而且，还可以　根据不同要求，相应地找出不同密集程度的类，如图１　所示．如果要找出所有密度大于５的类，那么能得到　和Ｅ　２个类ｊ如果要找出所有密度大于３的类，则　将会得到４个类：　、Ｂ、ｃ、Ｅ；如果再放宽范围，那么　和ｃ将合并为一个类．　等密度线聚类算法根据等高线图的思想，根据样　本相互之间的距离和给定邻域半径大小ＲＴ，计算出　每个样本的密度值，然后根据给定的密度阈值ＤＴ，找　出所有密度大于ＤＴ的样本，以及与这些样本的距离　小于门限距离Ｒ丁的样本集，并把相互有重叠部分的样本集进行合并，这样就得到了原始样本　的一组聚类．而不属于任何一个类的样本和样本极少的类，由于其分布极为稀疏，称之为噪声　（ｎｏｉｓｅ或ｏｕｔｌｉｅｒ）．　圉１等密度线图　在等密度线算法中，要求所有样本数据是经过预处理的，样本每个属性的取值范围都是　［ｏ，１］．这样是为了便于计算距离矩阵，并便于采用合理的公式计算门限距离的大小．　２．１密度函数的定义　该算法的关键在于怎幺计算密度，并进一步由各个样本的密度得到等密度线．在等密度线　维普资讯 http://www.cqvip.com

北京邮电大学学报　第２５卷　算法中采用了邻域分布密度的概念，一个样本的邻域是指到该样本的距离小于某个定值的区　域，而该邻域中所包含的样本数目，就是该样本的邻域分布密度．　计算邻域样本分布密度的一般公式如下：　Ｄｅｎ（Ａ）＝ｓｉｚｅ（｛Ｂｌ，（Ｂ，Ａ）≤Ｔ））　其中，Ａ、Ｂ为输入的样本｝Ｄ　ＨＭ）为样本Ａ附近的样本分布密度，ｓｉｚｅ（ｘ）为集合ｘ中的样本　的数目，即集合ｘ的大小．ｆ（Ｂ，Ａ）是样本Ａ和样本Ｂ一个相似性度量函数，ｒ，是给定阈值．　下面给出采用不同度量函数，的两种密度计算方法．　方法１：以到某样本的距离，ｊ、于给定值ｒ，的样本的数目作为该样本的密度．　Ｄｅｎ（Ａ）：ｓｉｚｅ（｛Ｂ　ｌＤｉｓｔ（Ｂ，Ａ）＜ｒ，））　上式中，距离函数的取法有多种，一般采用明氏（Ｍｉｎｋｏｗｓｋｙ）距离：　Ｄｉｓｔ＾（Ｘ，Ｙ）　其中，　为正整数．最常用的距离度量取　＝２，即欧式（ｅｕｃｌｉｄｅａｎ）距离．　方法２：以与某样本的相似度大于给定值ｒ，的样本的数目作为该样本的密度，如样本向量　间夹角的余弦等．　Ｄｅｎ（Ａ）＝ｓｉｚｅ（　Ｂｌ　ｓｉｍ（Ｂ，Ａ）７＞Ｔ｝）　在等密度线聚类算法中，采用第一种密度计算方法，并用欧式距离作为样本间的距离度　量．　２．２算法详细过程　等密度线聚类算法的详细过程如下：　（１）计算出任意两个样本间的距离，得到距离矩阵Ｄｉｓｔ：Ｄｉｓｔ（ｉ，　）一Ｄ（ｘ（　），ｘ（ｆ））．　（２）根据距离矩阵确定邻域的大小：ＲＴ＝ｍｅａｎ（Ｄｉｓｔ）／　ｃｏｅｆＲ丁）．　（３）计算密度矩阵Ｄｅｎ：即给定半径ＲＴ范围内的样本点的数目．对于矩阵中的每一行，　找出其中距离小于门限距离ＲＴ的数目，该数目就是对于该行所对应的样本的邻域样本分布　密度．根据得出的分布密度可以画出样本等密度线图（该等密度线图在实际聚类过程中是不需　要画出来的，它隐含在密度矩阵中）．　（４）根据密度矩阵确定密度圈值；ＤＴ一［ｍｅａｎ（Ｄｅｎ）／ｃｏｅｆＤＴ］．（符号　］”表示取整操　作．）　（５）合并：对于每一个密度大于ＤＴ的样本Ａ，如果样本Ｂ和Ａ的距离小于Ｒｒ，，并且Ｂ　的密度也大于ＤＴ，则把Ａ所在的类和Ｂ所在的类合并为一个类．把所有这样的类都进行合　并，最后就可得到聚类结果、　（６）如果聚类结果不太理想，则可以通过ｃｏｅｆＤＴ来调整密度阚值ＤＴ，从而对聚类结果　进行优化．　其中，Ｘ为样本集，”是样本数目，ｃｏｅｆＤＴ和ｃｏｅｆＲＴ是可调系数．　２．３邻域大小ＲＴ和密度阐值ＤＴ的选择　从等密度线图得到各个聚类是很简单的，所以等密度线图算法的关键在于怎样得到最佳　的等密度线图，实际上就是如何确定邻域大小ＲＴ．如果邻域过小，那么每个样本的邻域分布　密度都很小，聚类的结果将会是有很多类，而每个类只包含很少的样本．极端情况是邻域小于　所有样本间距离的的最小值，那么每个样本密度都是１，各自属于一类，类的数目等于样本数　维普资讯 http://www.cqvip.com

第２期　赵艳厂等：一种新的聚类算法：等密度线算法　目，这样的聚类结果是毫无意义的．与此相反，如果邻域过大，那么每个样本的邻域分布密度都　很大，而且密度值比较接近，由此画出的等密度线很难反映出样本的真正分布情况，不能分清　距离比较近的两个类，聚类结果中距离比较近的类往往被合并为一个类．极端情况是邻域大于　所有样本间距离的最大值，那么每个样本的密度都是　（　为样本数目），那么所有的样本都台　并到一个类中，这种聚类结果也是毫无意义的．　由以上分析可以看出，邻域的大小应介于所有样本间距离的最小值与最大值之间，即　ｍｉｎ（Ｄｉｓｔ）≤尺丁≤ｍａｘ（Ｄ／ｓｔ）．总的说来，邻域的取值除了要满足上述条件以外，还要使得到的　邻域密度的分布尽可能均匀，分布范围尽可能广，这样得到的等密度线能够反映出各个密度等　级的样本分布，从而有利于找出隐藏在其中的各个类．在等密度线聚类算法中，作者给出了一　种根据样本数目和样本分布的密集程度来动态确定邻域大小和密度阈值的方法．邻域大小的　取值用下面公式计算：　ｓｔ）　ＲＴ：—ｍｅ—ａ　ｎ（　Ｄ／ｒ其中，ｍｅａｎ（Ｄｉｓｔ）表示所有样本间距离的平均值，ｎ是样本数目，ｅｏｅｆＲＴ是邻域半径调节系　数，取值在０到１之间．经过多次实验表明，ｃｏｅｆＲＴ取０．３时，在很多情况下都能得到很好的　聚类效果．　密度阈值ＤＴ的大小，将决定聚类的最终结果．如果密度阈值过小，那么将会导致距离较　近的类的台并；如果密度阑值过大，将会使一个类为多个类，或者把很大一部分样本都归　为噪声＋这样，就不能很好地利用样本中携带的信息，在等密度线算法中，密度阚值的取值用下　面公式计算：　ｒ　２　＜ｌ　０００　一１　塑　Ｌ　ｔＯｇｔ￣Ｌｎ　×ｃ。ｅｆＤＴ　≥１　０００　其中，ｃｏｅｆＤＴ是密度调节系数，取值在０．７到１之间．多次实验结果表明，当ＤＴ取０．９５时，　在大部分情况下都能取得很好的聚类效果．　对于给定样本集，邻域大小和密度阚值都由算法根据上面的公式自动得出．此外，还可以　根据聚类的结果调整密度阈值ＤＴ的大小，从而对聚类结果进行调整．如果事先知道样本集中　类的数目，或者预先确定了要得到几个类，那么可以对邻域大小及密度阚值计算公式中的可调　参数进行调整，从而得到更佳的聚类效果．　３性能分析　算法中每次文件读写操作都以距离矩阵中的一行为单位进行，这样可以大大减少Ｉ／Ｏ操　作次数，从而提高算法的速度．该算法的时间主要用于计算距离矩阵，时间复杂度为Ｏ（ｎ　）．由　于该算法过程中要用到样本间的距离矩阵，其大小为”　，这是一个不小的数目．为了节省存储　空间，对距离矩阵进行整数化，即把每一个距离都用一个长度为２个字节的整数来表示．此外，　还把距离矩阵存储到硬盘上以节省内存空间．总共所需硬盘空间为２×　字节，　对于维数ｄ大于２的情况，除了计算样本间距离矩阵Ｄｉｓｔ的时间会随着ｄ的增大而增　加，而等密度线聚类算法中其他部分的计算，都不需要进行任何变化，时间复杂度和空间复杂　度都不受ｄ的影响．也就是说，等密度线算法中除了距离计算之外的其它部分，是与维数　没　维普资讯 http://www.cqvip.com

北京邮电大学学报　第２５卷　有任何关系的，只与样本数目ｎ有关　４实验结果　等密度线聚类算法在ＰＣ机上进行了实验．ＰＣ机的配置如下：ＣＰＵ为ＡＭＤ　Ａｔｈｌ。ｎ　Ｋ７　７００　ＭＨｚ，内存２５６　ＭＢ．作者用不同大小多种分布的数据集对算法进行了仿真，限于篇幅，下　面仅介绍其中的一组实验数据及其聚类结果．　实验数据如图２所示，共有１　４００个点，根　据一定的分布形状随机产生．其中，左边呈折线　状均匀分布的点占３Ｏ　，中间呈球状正态分布　的点占３０　，右边的半圆形均匀分布的点和线　状均匀分布的点各占ｌ５　，其余的１ｏ　为均匀　分布的噪声．　算法根据公式计算出得邻域半径大小为　０．０４４　３，得到的样本分布等密度线图如图３所　示．该图很明显的画出了样本分布比较集中的　几个区域．根据公式计算出的密度阈值为ＤＴ　１０，由此而得到的聚类结果中有４个类，如图　４所示．样本集中的形状各异的４个密集样本　分布区域都能正确的找出，最后４个类包　一圈２样本图　含样本１　２７０个．而其他样本因为分布密度极小而视为噪声，共有１３０个，占原有样本总数的　０．０９３　．由此可以看出，等密度线聚类算法不但能够发现球状分布的区域，也能发现线状区　域，也能发现非凸样本分布（如图４中的折线和半圆形分布），同时对于距离比较近的类，如图　４右边的两个类，也能够正确地分辨出来．此外，还有效的排除了噪声的干扰．　圈３样本分布等密度线圈　图４聚类结果　此外，对算法在不同样本数目的情况下进行了实验，实验结果如表１所示　维普资讯 http://www.cqvip.com

第０期　赵艳厂等：一种新的聚类算法：等密度线算法　１３　从实验数据中可以看出，该算法所需的内存很少，随样本数目　的增加而成线性增长．算　法的时间复杂度与　成正比，在样本数目为５０　０００时，处理时间约为１９分钟．所用的硬盘空　间也和　ｚ成正比，在样本数目为５０　０００时，需要约４　ＧＢ的硬盘空间．当样本数目大于１∞０００　时，算法所需的硬盘空间及处理时问都较长，需要进行进一步的改进．　５总结　等密度线聚类算法从样本分布的等密度线图出发，把某个等密度线所分割成的区域各自　归为一类，从而可以找出样本中分布比较密集的部分，这正好满足了聚类的要求．在一定意义　上来说，等密度线算法得出的聚类结果应该是最佳的．当然，要得到最佳的聚类结果，首先要得　到比较好的等密度线图，然后根据等密度线图选取合适的密度阈值，最后把选定的等密度线包　围的点合并，得到各个聚类．该算法虽然要计算样本邻域密度，但是不需要任何的人工输入，算　法可以根据样本的分布情况自动地确定邻阈的大小，所以该算法可以说是完全无监督式聚类．　从实验结果可以看出，等密度线聚类算法不但能够发现各种形状的样本密集区域，而且能够有　效地排除噪声的干扰，得到较好的聚类效果．　等密度线聚类算法仅在实验数据下进行了测试，以后的研究中，将对于实际数据集进行测　试，并测试实际的运算时间．此外，由于条件的，算法中对于邻域大小及密度阈值的计算公　式仅是针对样本数目不超过５０　０００的情况下总结出来的，对于更多的样本集（如１００　０００乃至　１　０００　０００个样本），该公式中的参数是否需要进行调整，有待以后进一步研究．　参考文献：　［１］Ａｌｓａｂｔｉ　Ｋ，Ｒａｎｋａ　Ｓ，Ｓｉｎｇｈ　Ｖ．Ａｎ　ｅｆｆｉｃｉｅｎｔ　ｋ－ｍｅａｎｓ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍｉＣ］．ＩＰＰｓ　９８，Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｆｉｒｓｔ　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｈｉｇｈ　Ｐｅｒｆｏｒｍａｎｃｅ　Ｄａｔｅ　Ｍｉｎｉｎｇ，Ｏｒｌａｎｄｏ，Ｆｌｏｒｉｄａ，ＵＳＡｔ　１９９８．　１２］Ｂｒａｄｌｅｙ　Ｐ　Ｓ．Ｍａｎｇａｓａｒｉａｎ　Ｌ．ｋ－ｐｌａｎｅ　Ｃｌｕｓｔｅｒｉｎｇ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｇｌｏｂａｌ　Ｏｐｔｉｍｉｚａｔｉｏｎ．２０００，１６（１）：２３　３２．　［３］Ｚｈａｎｇ　Ｔ，Ｒａｍａｋｒｉｓｈｎａｎ　Ｒ．Ｌｉｖｎｙ　Ｍ．ＢＩＲＣＨ：ａｎ　ｅｆｆｉｃｉｅｎｔ　ｄａｔａ　ｃｌｕｓｔｅｒｉｎｇ　ｍｅｔｈｏｄ　ｆｏｒ　ｖｅｒｙ　ｌａｒｇｅ　ｄａｔａｂａｓｅｓⅢＡ］．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　１９９６　ＡＣＭ—ＳＩＧＭＯＤ　Ｉｎｔ．Ｃｏｎｆ．ｏｎ　Ｍａｎａｇｅｍｅｎｔ　ｏｆ　Ｄａｔａ［Ｃ］．Ｍｏｎｔｒｅａｌ，　Ｑｕｅｂｅｃ：１９９６　［４：Ｊａ＿ｎ　Ａｎｉｌ　Ｋ．Ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　Ｃｌｕｓｔｅｒｉｎｇ　Ｄａｔａ［Ｍ］．Ｐｒｅｎｔｉｃｅ　Ｈａｌｌ，１９９８．　［５７　Ｅｓｔｅｒ　Ｍ，Ｋｒｌｅｇｅｌ　Ｈ　Ｐ，Ｓａｎｄｅｒ　Ｊ．ｅｔ　ａ１．Ａ　ｄｅｎｓｉｔｙ－ｂａｓｅｄ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｄｉｓｃｏｖｅｒｉｎｇ　ｃｌｕｓｔｅｒｓ　ｉｎ　ｌａｒｇｅ　ｓｐａｔｉａｌ　ｄａｔａｂａｓｅｓ　ｗｉｔｈ　ｎｏｉｓｅ［Ｃ］．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２ｒｉｄ　Ｉｎｔ．Ｃｏｎｆ．ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ，Ｐｏｒｔｌａｎｄ，Ｄｒｅｇｏｎ，１９９６．