聚类算法中的相似性度量方法研究

心智与计算176心智与计算,Vol.2，No.2(2008),176-181文章编号：MC-2008-18收稿日期：2008-07-30出版日期：2008-09-30©2007MC–厦门大学信息与技术学院聚类算法中的相似性度量方法研究赖桃桃，冯少荣（厦门大学计算机科学系，福建厦门361005）[e-mail]摘要：针对传统的欧氏距离计算相异度的不足,在研究已有的相似性度量方法的基础上提出一种新的相似性计算方法，对此进行分析，说明了该度量方法有更好的可解释性；把它用于k-means聚类算法中跟欧氏距离进行比较，在UCI基准数据集上的实验表明,该方法有更稳定的聚类结果，且提高了聚类准确率，是一种有效的聚类度量方法。关键词：相似性；度量方法；聚类算法中图法分类号:TP391文献标识码:AResearchonSimilarityMetricsMethodforClusteringAlgorithmLAITao-tao,FENGShao-rong(DepartmentofComputerScience,XiamenUniversity,Xiamen361005,China)[e-mail]:AccordingtothedisadvantagesofcalculatingdissimilaritybasedontraditionalEuclideandistance,presentedanewsimilaritymetricsmethodafterstudiedtheexistingmethodofthesimilaritymeasure,Analysisshowedthatthemetricsmethodcanbebetterinterpretative;Useditinthek-meansclusteringalgorithmwithEuclideandistancecomparison,theexperimentsbasesonUCIbenchmarkdatasetsshowedthatthismethodhasmorestableclusteringresults,andimprovedtheaccuracyofclustering,itisaneffectiveclusteringmetrics.Keywords:similarity;metricsmethod;clusteringalgorithm.1引言聚类分析已经成为数据挖掘研究领域的一个非常活跃的研究课题，聚类就是一个将数据集划分为若干组或类的过程，通过聚类使得同一组内的数据对象具有较高的相似度，而不同组中的数据对象则是不相似[1]。没有任何一种聚类算法可普遍适用于揭示各种多维数据集所呈现出的多种多样的结构。根据数据在聚类算法中的相似性度量方法研究177聚类中的积聚规则以及应用这些规则的方法,有多种聚类算法。通常将聚类算法分成层次化聚类算法、划分式聚类算法、基于密度和网格的聚类算法和其他聚类算法4个类别[2]。K-means是昀常用的聚类算法之一，它能对大型数据集进行高效分类，其计算复杂度为O(t*K*M*N)，其中，t为迭代次数，K为聚类数，M为特征属性数，N为待分类的对象数，通常，K，M，tN。在对大型数据集聚类时，K-means算法比层次聚类算法快得多[2]。研究人员已对其进行了大量研究与改进。对K-means的改进，大量工作是从它的初始化中心入手的，如：Bradley和Fayyad提出的迭代初始点集求精算法[3]；钱线等人提出的初始化K-means的谱方法[4]；袁方等人提出的根据数据的自然分布选取初始聚类中心的方法[5]等等。本文从另一个角度，从距离函数入手，用本文提出的相似度函数代替传统的距离函数欧氏距离，实验证明,该方法提高了聚类质量。2数据对象之间的相似性度量数据对象之间的相关性可以用它们之间的相似度或相异度来描述。2.1数据对象间的相异度度量方法[6]假设每个对象有M个属性，可以把一个对象视为M维空间的一个点。定义两个M维的数据对象),,,(21iMiiixxxxL=和),,,(21jMjjjxxxxL=。昀常用的相异度度量方法是欧几里德距离，它的定义如下：∑=−=Mkjkikjixxxxd12)(),((1)2.2数据对象之间的相似性度量方法[7]相似系数与距离相反，相似系数越大，对象间的相似性越大。令∑==MkikixMx11，∑==MkjkjxMx11，则xi，xj的相似性系数为),(11),(jijixxdxxs+=(2)3新的相似性度量方法传统的聚类分析中，把对象中每个属性在聚类过程中的贡献看作是相同的，受式（2）的启发，本文为把对象中每个属性的值规范化到(0，1]，提出如下距离计算公式：聚类算法中的相似性度量方法研究178∑=−+=Mkjkikjixxxxs111),((3)在式(2)中，先算出数据xi，xj的距离，然后加1取倒数，计算得到xi，xj相似系数。式(3)中，两个对象(每个对象有M个属性)间的相似系数等于M对属性间相似系数之和，每对属性间的相似系数等于每对属性曼哈顿距离加1的倒数。式(3)把两个对象间每个属性的相似系数都映射到(0，1]，在每个属性的贡献相同的假设下，更好的可解释性；而欧氏距离，有时某个属性的影响会远远大于其它属性甚至其它所有属性之和。易知(3)满足以下三个数学要求。1)0),(≥jixxd：相似系数是一个非负数。2)),(),(ijjixxdxxd=：相似系数具有对称性。3)1),(),(==iiiixxdxxd：相似系数具有自反性。欧氏距离是常用的而且较为有效的一个距离度量方法，K-means是一种常用简单易于实现的聚类算法；下文在K-means聚类算法框架下用本文提出的相似性度量方法式(3)与欧氏距离作比较。用本文提出的相似性度量方法（3）改进的随机划分K-means算法描述如下：输入：N个数据对象输出：K个类把N个数据对象随机划分成K个类，计算这些类的质心。1)根据新的相似性度量方法计算相似性，把每个数据对象分配到与它相似性昀大的一个类，公式如下：∑=−+=Mkjkikjixxxxs111),(2)计算被分配到每个类的数据的均值，作为新的类的质心。3)重复2)，3)直到K个类的质心点不再发生变化、目标函数收敛或达到昀大迭代次数。下文称以上算法为改进算法，称经典k-means算法为原算法。4实验及其分析实验的硬件环境是P42.93GHzCPU、主存为1G、硬盘为80G；软件环境是：操作系统为MicrosoftWindowsXP，算法采用Java编写。本文采用UCI上的四个真实数据集:Iris,，Wine，Soybean(small)，Vehicle。表1给出这些数据集的描述。基于欧氏距离的相似性度量方法(2)与欧氏距离是等价的；另欧氏距离是一个经典、常用且相对有效的距离函数，故下文将本文提出的新的相似性试题方法式(3)与欧氏距离作比较等价于与相似性度量方法（2）作比较。对上述四个数据集用随机划分K-means进行聚类,分别进行50次实验平均正确率的计算[8]。它们的聚类结果比较如图1。聚类算法中的相似性度量方法研究179表1数据集描述Tab.1Thedescriptionofdataset数据集维数p类的个数属性特征数据点总数nIris43数值型150Wine133数值型178Soybean354分类属性47Vehicle184数值型8460.00%20.00%40.00%60.00%80.00%100.00%IrisWineSoybeanVehicle原算法改进算法图1实验结果1Fig.1Experimentresult1从上述实验结果可以看出改进算法对数据集Wine及Soybean的平均聚类准确率有大幅的提高，均提高了20%。而另外两个数据集Irish，Vehicle只有很小变化。Wine数据集有178个数据，分成3类，每个数据项有14个属性，各个属性的取值范围差距较大。应用决策树进行分析发现：Alcohol(属性1)，Flavanoids(属性8)，Color_intensity(属性11)这3个属性对分类昀为重要，它们的取值范围分别为：(0.34~5.08)，(1.28~13)，(11.03~14.83)，而对分类贡献不大的属性Proline（属性13）的取值范围是(278~1680)，在计算距离时，属性Proline起到了绝对的作用[5]；导致使用欧氏距离聚类时严重降低了，而使用本方提出的相似度量方法式(3)能明显的减弱Proline（属性13）的影响，提高聚类的准确率。数据集Soybean的分布跟Wine相似，故用式（3）后能大幅提高聚类准确率。由文[9]可知，数据集Iris的两个重要属性1(sepallength)，属性2(sepalwidth)的取值都较属性3(petallength)和属性4(petalwidth)大或相当，所以在这个数据集上并没有体现出本文提出的度量方法的优势。数据集Vehicle的分布跟Iris相似，故聚类准结果没有大的变化。聚类算法中的相似性度量方法研究180因为对数据进行标准化后，每个属性的值也在区间(0,1]，所以为了作进一步的比较，本文做了另外一组实验。先对实验数据进行标准化,然后分别用K-means分别进行50次实验，实验结果如图2：0.00%20.00%40.00%60.00%80.00%100.00%IrisWineSoybeanVehicle原算法改进算法图2实验结果2Fig.2Experimentresult2从图2可以得到如下结论：在四个数据集上用改进算法较原算法都得到略好的聚类的结果。联合图1、图2及实验中得到数据可以知道：1)数据标准化后用原算法进行聚类，数据集Wine，Soybean上的聚类正确率有大幅的提高，分别提高25和11.9个百分点；而在数据集Vehicle上，下降了6.9个百分点。2)数据标准化后和数据不标准化用改进算法进行聚类，聚类正确率有升有降，不过波动不大，都不超过5个百分点。故改进算法相对于原算法有较为稳定的聚类结果。由于用原算法对进行标准化处理后的数据聚类，聚类的结果有大幅的变差或变坏的可能，而你又不可能通过目标函数值来判断数据标准化后进行聚类还不标准化直接进行聚类哪个聚类得到的结果更好，因为数据标准化后，与原数据极有可能不是在一个数量级，计算出来的目标函数值根本无可比性。而改进算法对数据标不标准化进行聚类，得到的结果波动不大，且它较原算法有普遍好的聚类结果。所以在不知道聚类类标的实际应用中，本文改进的K-means算法有更强的实用性。另外，若各维属性的权重不相同，可以参照文献[9]把式(3)进行扩展，得到加权的相似性度量方法如下：∑=−+=pkjkikkjixxwxxs111),((4)5结论本文提出了一种新的相似性度量方法。由于它把每个属性的相似系数都映射到(0，1]之间，对于传统的聚类算法把对象中每个属性在聚类过程中的贡献看作是相同的假设，有更好的可解释性。把它用于聚类算法中的相似性度量方法研究181K-means算法，实验表明用此函数得出的聚类结果通常要优于欧氏距离，当某个无关属性影响很大时，更是明显的改进聚类效果。当每个属性的权重不一致时，可以给它赋以相应的权重然后按式(4)计算，将得到更佳的聚类效果。参考文献：[1]HanJ,KamberM.数据挖掘概念与技术[M].第2版.范明,孟小峰,译.北京:机械工业出版社,2006.[2]孙吉贵,刘杰,赵连宇.聚类算法研究[J].软件学报,2008,19(1):48−61.[3]Bradley,FayyadM.Refininginitialpointsfork-meansclustering[C]//Proc.ofthe15thInternetConf.onMachineLearning.SanFrancisco:MorganKaufmannPublishers,1998.727:91−99.[4]钱线