I-Miner环境下多种聚类质量评价方法的实现

1、I-Miner环境下多种聚类质量评价方法的实现随着存储技术的进步和人们对海量信息的需求，数据挖掘取得了极大的 发展。通过数据挖掘，人们可以从大量的数据库中提取对其有用的信息, 并可以根据这些信息作出预测。数据挖掘技术集数理理论、专家系统、 人工智能、神经网络、图形图象设计等多门学科于一身，其发展速度必将 大大影响全球信息化的进程，对其进行系统、深入、全面、详尽地研究是 信息化发展的客观需要。聚类分析是数据挖掘技术的重要手段和工具，在工程和技术等领域具有 广泛的应用背景。它可以发现隐含在数据集中的簇，标识出感兴趣的分 布或模式。聚类问题是将一组对象分成若干簇或聚类，使簇类的对象尽 可能具有最大的

2、相似性，不同簇之间的对象尽可能具有最大的相异性。 聚类过程可以看成是一种无监督的学习过程。即依靠聚类算法进行的聚 类分析大都是靠假设和猜测进行的。正是由于聚类分析的这种假设性和 结果的不确定性使得在数据挖掘领域迫切需要一种客观公正的质量评 价方法来评判聚类结果的有效性。目前常用的聚类有效性评价算法有外部评价法、内部评价法、相对评价 法和模糊评价法等。本文通过重点学习聚类评价算法的原理，并利用S 语言实现了外部评价法中的F-measures Rand指数与Jaccard系数算 法以及相对评价法中的SD有效性指数、基于聚类分布的有效性度量 Ocqs基于多代表点的有效性指数CDbw算法。最后，在对大

3、量的数 从统计学的观点看，聚类分析是通过数据建模简化数据的一种方法。传 统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、 有序样品聚类、有重叠聚类和模糊聚类等。采用k-均值、k-中心点等算 法的聚类分析工具已被加入到许多著名的统计分析软件包中，如SPSS、 SAS 等。从机器学习的角度讲，簇相当于隐藏模式。聚类是搜索簇的无监督学习 过程。与分类不同，无监督学习不依赖预先定义的类或带类标记的训练 实例，需要由聚类学习算法自动确定标记，而分类学习的实例或数据对 象有类别标记。聚类是观察式学习，而不是示例式的学习。从实际应用的角度看，聚类分析是数据挖掘的主要任务之一。就数据挖 掘功能

4、而言，聚类能够作为一个独立的工具获得数据的分布状况，观察 每一簇数据的特征，集中对特定的聚簇集合作进一步地分析。聚类分析还可以作为其他数据挖掘任务（如分类、关联规则）的预处理 步骤。作为数据挖掘的一个很重要的功能，聚类分析能作为一个独立的 工具来获得数据分布的情况，它是模糊集理论的重要应用，主要是将实 际中模糊性问题同过数学手段实现一定的归类分析。同时它又是一种数 据简化技术，它把基于相似数据特征的变量和个案组合在一起，这对发 现基于相似特征（如人口统计信息、财政信息或购买行为客户细分）非常应用聚类算法 聚类分析是数据挖掘中的一个很活跃的研究领域，并提出了许多聚类算 法。这些算法可以被分为划分

5、方法、层次方法、基于密度方法、基于网 格方法和基于模型方法。划分方法(PAM:PArtitioning method)首先创建k个划分，k为要创建的划分个数；然后利用一个循环定位技 术通过将对象从一个划分移到另一个划分来帮助改善划分质量。典型的 划分方法包括k-means,k-medoids,CLARA(ClusteringLARgeApplication),CLARA NS(Clustering Large Application based upon RANdomized Search)0这里重点介绍一下k-means算法，本文所采用的聚类算法均 为 k-means.K-Means算法试图

6、确定最小化平方误差函数的k个划分。当结果簇是 紧凑的，并且簇与簇之间明显分离时，它的效果较好。对处理大数据集， 该算法是相对可伸缩的和有效率的。因为它的计算复杂度是0 ( nkt), 其中n是对象的总数，k是簇个数，t是迭代的次数。通常地,kn, 并且tc,贝!c寸否则转S8S8:若ip,则p = i,否则转S9S9:k+1S10:若 1max,max=Fi jS17:j+1S18:若卜二c,转S14,否则转S19S19:Fil = maxS20:i + lS21:若 iv = p , max=O ,转 S13 ,否则转 S22S22:i=l,count=0,F=0S23:F=F+Fil *N

7、i ,count= count+NiS24:若 ip , i=i+L转 S23,否则转 S25S25:总评价值 F=F/countS26:退出423算法流程图图4-4 F-measure算法流程图Rand 与 Jaccard 算法算法原理 设数据集X的一个聚类结构为，数据集已知的划分为，可通过比较C 和P以及邻近矩阵与P来评价聚类的质量。对数据集中任一对点(Xv, Xu),计算下列项：SS :如果两个点属于C中同一簇，目P中同一组；SD :如果两个点属于C中同一簇，但P中不同组；DS :如果两个点不属于C中同一簇,而P中属同一组;DD :如果两个点不属于C中同一簇，且P中不同组。设a、b、c、

8、d分别表示SS、SD、DS、DD的数目，则为数据集中所 有对的最大数，即，N为数据集中点的总数。则C与P之间的相似程 度可由如下有效性指数定义Rand指数:.(4) Jaccard系数：.(5)上述两指数取值范围均为。1,当m二s时，有最大值。算法实现步骤S1:导入F-measure算法中间过程产生的Nij文件,读取行数row,列 数colS2:a=0,b=0,c=0,d=0S3:i=lS4:j=lS5:a=(Nij-l)*Nij/2+aS6:若j=col , j=j + 1,转 S3,否贝胜专 S5S7:若 i =row,i=i+l,转 S3,否则转 S7S8:j = l,p=0S9:i=l

9、,sum=0S10:sum=sum + (Nij-l)*Nij /2,p=p+ NijSU:若 i=row,i=i+1,转 S10,否则转 SilS12:p=p*(p-l)/2,b=b+p-sumS13:若j =col , j=j+l,p=O,转 S9,否贝！转 S14S14:i = l,p=OS15j = l,sum=0S16:sum=sum + (Nij-l)*Nij /2,p=p+ NijS17:若j =col , j=j + l,转 S16,否则转 S17S18:p=p*(p-l)/2zc=c+p-sumS19:若 i = row,i = i+l,p=O,转 S15,否贝脖专 S20S

10、20:sum = row*(row-l)/2,d=sum-a-b-cS21:R=(a+d)/M,J=a/(a + b+c)S22输出RJS23:结束算法流程图图4-4 Rand与Jaccard算法流程图4.4SD算法 算法原理SD有效性指数是基于聚类平均散布性(Average scattering for clusters )和聚类间总体分离性(Total separation between clusters ) 的一种相对度量方法。已知数据集X的方差为，其第p维方差定义为(6)其中是第p维均值.聚类i的方差为，其第p维方差定义为.则聚类的平均散布性定义为. (9)聚类的平均散布性所反映的是

11、聚类内的数据代表点的分布，聚类的平均 散布性的值越小，说明聚类内的数据代表点的分布越集中，聚类的效果 也就越好。聚类间总体分离性定义为(10)聚类的总体分离性所反映的是聚类间的数据代表点的分布情况，它的值 越大表明不同聚类间的数据代表点的越靠近，反而，如果聚类总体分离 性的值越小则说明聚类间的数据代表点的分布就越远离。其中，分 别是聚类中心间的最大和最小距离，C为聚类个数。最后可得到质量指数.(11)其中加权因子，cmax为输入聚类的最大数目。SD的值所反映 的是基于聚类平均散布性和聚类间总体分离性的综合指标。SD计算是要分 别在Cmax取不同值的情况下进行，因此，最后得到的SD是Cmax 不

12、同时，聚类个数c从指定最小值Cmin到Cmax的值，SD取最小值 时所对应的划分个数即为最优的聚类划分数目。算法实现步骤S1：导入数据集合聚类后的文件，并获取聚类个数cS2:计算数据集方差。(X)S3:计算每个聚类的均值和方差o(Vi),然后可以计算聚类的平均散布性 Scat(c)S4:,设定聚类中心间的最大距离Dmax=O和最小距离Dmin = 1000S5:i=lj = lS6:若 j!二i 转 S7于多代表的有效性指数CDbw等评价方法；模糊评价法则是由划分系 数、划分烯、划分模糊度指数等方法。当前的聚类评价算法的研究基本 上都是在以上四种方法基础上进行的，由于大多数聚类算法中，需要用

13、户输入希望产生的簇的个数，这样的话，聚类结果带有一定的主观和人 为误差。聚类评价就是对聚类结果进行评价，最后给出一个合适的聚类 参数。然而，聚类评价方法往往与特定的问题和所采用的聚类算法等因 素有关，对于不同的数据集采用的聚类算法不一样，最后所采用的评价 方法也不一样。由于聚类分析广泛应用于医疗、分子学、天体物理学和 市场学各个方面，找到一个合适的聚类算法对提取人们所需要的信息显 得十分重要，因此，研究聚类评价算法对于数据挖掘领域而言是十分必 要和重要的，好的聚类评价方法可以为人们提供直接的聚类分析模型, 从而更好的揭示大量数据库中数据的相似性和分离性。找到一个更加成熟的聚类有效性度量方法仍然

14、是该研究领域的热点和方向。13本文研究内容本文主要是在学习数据挖掘原理的基础上，重点学习聚类评价方法，并 掌握数据挖掘工具I-Miner，然后用S语言实现（外部评价法）F-meaure 算法、Rand指数与（相对评价法）Jaccard系数算法以及SD有效性指数 算法、基于聚类分布的有效性度量算法、基于多代表的有效性指数 CDbw算法。然后，在对用大量的数据集（包括web文档）进行聚类后, 通过以上聚类评价算法对聚类的结果进行分析和测试，进而对比各种评 价算法的结果。各章节安排如下：S7:计算聚类i和聚类j的中心点的距离S8若jc , j=j + 1，转 S6S9:若 ckDmin 则 Dmin

15、二d,否则转 S10S10:Dmax=dSil:计算总体分离性Dis=Dis+l/dS12:若 ic , i=i+1,转 S6S13:Dis=Dis*Dmax/Dmin ,可以计算出 SDS14: S15:退出算法流程图图4-4 SD算法流程图4.5 Ocq算法算法原理 用聚类结果分布的自然属性来评价聚类内(Intra-cluster)的同一性和 聚类间(Inter-cluster)的分离性与最大化聚类内相似性和最小化聚类 间相似性这一聚类目标是相符的。聚类密集性是一种有关聚类内方差的 测量，方差越小说明数据集的同一性越高。给定一个数据集X,其簇内 方差被定义为其中是矢量与之间的距离，N是X的

16、总个数，是X的均值对聚类输出结果cl, c2，,cC,聚类密集性被定义为其中C为聚类个数, var(ci)是簇ci的方差。因为每个聚类内的成员应 尽可能地接近，所以聚类密集性越小越好。但是在极端情况下，当每个 输入矢量被分为单独的类时，聚类密集性有最小值0。聚类邻近性被定义为：其中。为高斯常数，为简化计算，取2。2=1.0。是聚类ci的中心，为 聚类ci中心与cj中心之间的距离。因为各聚类应有效地分开，且聚类 邻近性反比于聚类间距离，所以聚类邻近性越小越好。然而，当整个输 入矢量被聚为一个类时，聚类邻近性有最小值0o为了评价一个聚类系统的综合质量，可将上述聚类密集性与聚类邻近性 组合为一种评价

17、方法，称作聚类综合质量(Overall cluster quality ), 它被定义为其中是平衡聚类密集性与聚类邻近性的权值，例如，Ocq(0.5)表示两 种评价有相等的权值。显然，聚类综合质量越大越好。算法实现步骤S1:导入数据集文件和聚类后的文件，并获取聚类个数cS2:计算数据集的方差Var(X)S3:根据聚类文件计算每个聚类i的均值和方差Var(ci)S4:i = l,Cmp=0S5:聚类密集性 Cmp= Var(ci)/ Var(X)+CmpS6:若 ic , i=i + L转 S5 ,否则转 S7S7:Cmp=Cmp/cS8:i = l,j = l,Prox=0S9 若 j!=i

18、,转 S10S10:计算聚类ij中心点距离d, Prox=Prox+exp(d)S11:若jc,j=j + 1,转 S9,否则，转 S12S12 若 il) 时，其聚类间密度定义为,(21)其中closejep(i)和close_rep(j)是第i和j簇间最近的代表点，uij为 close_rep(i)和 close_rep(j)连线的中点，项 density(uij)被定义为.(22)它表示在第i和j簇中属于uij邻域的点的百分数，uij的邻域定义为以 uij为中心、平均方差为半径的超球体，故函数被定义为(23)很显然，如果一个数据点到uij的距离小于簇的平均标准方差，它必然 属于uij的邻

19、域。在每个点被分为一个簇的极端情况下，即c二n时， stdev(Vi)=0 , =0 ,于是,Inter_dens(n)=0o聚类分离性(ClustersSeparation )与最近聚类间的距离和聚类间密度有关。希望聚类间的距离大而密度低，故聚类分离性定义为. (24)最后，有效性指数CDbw定义为(25) 算法实现步骤si：导入数据集和聚类后文件并获取聚类个数c和每个聚类i的对象的个数 p(i)S2:根据聚类文件计算每个聚类i的标准方差Stdev(Vi)S3:i=lS4:j = 1S5:k=lS6:计算第i簇的第j个代表点与第i簇第k数据点的距离dS7:若 d 二Stdev(Vi),转 S

20、8,否则转 S9S8:density(Vij )= density(Vij ) + 1S9:若 kp(i),k=k+L转 S6 ,否则，转 S10S10:若 jp(i),i = i + L 转 S6,否则转 SilSU:若 ivc,i=i+L转 S4,否则，转 S12S12:聚类内平均密度 Intra_dens=Intra_dens+ density(Vij)/Stdev(Vi)S13:计算第i簇和第j簇代表点最近距离保存在Lij中，两点的中点保存 在Uij中S14:i = lS15:j = lS16:若 j!二i 转 S17S17:k=lS18:计算第ij簇的第k个代表点与Uij的距离dS1

21、9:gd=(Stdev(Vi)+ Stdev(Vj )/2 转 S20 ,否则,转 S21S20:Density(Uij )= Density(Uij )+1S21:若 kp(i)+p(j),k=k+L转 S18 ,否则转 S22S22:Density(Uij )= Density(Uij )/(p(i)+p(j)S23:若 jc,j=j + 1,转 S17 ,否则转 S24S24:若 ic,i=i + 1,转 S15,否则转 S25S25:i=lS26:j=lS27:若j!二i转S28,否贝脖专29S28:聚类间密度 Intejdens = Inter_dens+Lij*Density(Ui

22、j)/( Stdev(Vi)+ Stdev(Vj)S29:若 jc,j =j + 1,转 S27S30:若 ic,i=i+L转 S26 ,否则转 S31S31:i=lS32:j=lS33:若j!二i转S34否则转35S34:聚类间分离性 Sep=Sep+Lij/( 1+Inter_dens)S35:若 jc,j =j + 1,转 S33S36:若 ivc,i=i+L转 S32 ,否则转 S37S37:有效性指数 CDbw=Intra_dens*SepS38输出 CDbwS39:结束算法流程图图4-6CDbw算法流程图第五章算法测试及结果测试数据集本文测试所涉及到的有iris数据集（有150个数

23、据，分为3个类别，每 个数据有4种属性）、glass数据集（有214个数据，分为7个类别, 每个数据有9种属性）、wine数据集（有178个数据，分为3个类别， 每个数据有13个属性）、zoo数据集（有125个数据，分为7个类别， 每个数据有16个属性）,具体情况如表5-1所示：表5-1数据集概况领域 iris glass zoo wine数据大小150 214 125 178分类数3 67 3属性数4 9 16 13F-measure评价法测试程序运行情况下图为用s语言编写的F-measure算法在S-PLUS下运行情况：第1章:绪论，介绍该论文研究背景和国内外研究现状第2章:介绍数据挖掘的

24、背景和概念，然后引入聚类分析的概念，同时 对聚类方法做介绍，重点讲述了 k-means算法。最后介绍了聚类评价 的概念和当前聚类评价算法的概况以及本文所要实现的聚类评价算法。第3章:主要介绍数据挖掘工具I-Miner以及S语言和S-PLUS第4章:首先介绍建立聚类过程的模型以及评价过程的建立。然后详细 介绍了内部评价法里的F-measure算法、Rand指数和Jaccard系数算法以及 相对评价法里的SD有效性指数算法、基于聚类分布有效性度量指数Ocq 算法、基于多代表点的有效性指数CDbw算法的原理、实现步骤、流 程图等内容。第5章:介绍本文实现的各种算法的程序运行情况和不同数据集进行测 试

25、后的结果以及各种算法内部与相互间的对比情况。第2章数据挖掘2.1数据挖掘图5-1 F-measure程序运行结果测试结果根据F-measure算法的思想,在每次通过k-means进行聚类，聚类的 所设定的个数C不同时，质量评价的结果F-measure值也不同,这些 不同的F-measure值中的最大值所对应的C就是我们所要寻找的最佳 聚类个数。图5-2以iris数据集为例，反映出F-measure值随聚类个 数C的变化情况：图5-2 iris数据集F-measure算法测试结果从图中我们可以看出对iris数据集聚类后的结果在C=3时取得最大值, 而从表5-1中我们看到iris数据集的分类数为3

26、 ,这说明我们通过评价 算法所得到的最优划分数与原来的数据集的划分数目是一致的。同时我 们也对其他数据集进行了和iris数据集一样的测试，其结果如表5-2所 示：表5-2不同数据集的F-measure评价结果数据集 Iris wine glass zoo数据集划分数3 3 6 7F-measure 最大值 0.833 0.952 0.491 0.821对应聚类个数C 3 3 6 7 从表中我们可以看出其他数据集的评价结果与iris数据集的评价结果是 一致的，而且我们可以看出F-measure的值都在。1之间，如果我们 横向比较，发现wine数据集的F-measure评价值最高为0.952 ,这

27、也 说明一个问题，那就是通过该评价算法得出的结果对于wine数据集而 言是最佳的，也就是说wine数据集的事先划分达到了最优的效果，而 对于glass而言，它的评价值仅有0.49L相对于其他数据集在k-means 下的聚类结果而言并不是很好。这也从侧面反映出一个问题，我们的评 价算法是针对聚类评价结果而进行的，但在本文中我们所采用的聚类算 法均为k-means ,它有可能并不适合于所有的数据集，因此对聚类的 结果而言是有影响，从而我们对聚类结果的评价也存在一定的缺陷。但 就算法本身而言，我们达到了预期的效果。小结F-meaure评价算法是与原始数据集预先的划分个数c相关的， F-measure

28、评价结果的最大值是与c 一致的，但是F-mesure算法的 评价结果受到聚类算法的影响，本文所采用的k-means算法并不可能 全部适用于所有数据集，因此聚类的效果并不会是最好，这样导致我们 的聚类评价结果在达到最大值时所对应的划分数有可能并不是数据集 的最优聚类个数m ,这个m的值并不一定针对k-means算法。此外, F-measure的值是在0.1之间，越接近1说明数据集在k-means下的 聚类效果越好，我们所得到的最优划分数目的可信度也越高。当然， F-measure算法的思想导致了我们测试结果的局限性，当这并不影响 我们从该评价算法中所得出的结论:F-measure的值越大，聚类的

29、效果 越好;F-measure最大值所对应的划分个数与数据集事先的划分个数 一致。Rand与Jaccard算法测试程序运行情况下图为Rand与Jaccard算法程序运行情况，运行环境为S-PLUS图5-3 Rand与Jaccard算法程序运行结果测试结果Rand指数和Jaccard系数所反映的均为聚类后数据集和聚类前数据集 的相似程度。对于Rand算法，R的值为，这里M是一定的，a是同 簇同组的数据点对的总数，d是不同簇不同组的数据点对的总数，我们 知道，在聚类划分最优时，a应该最大，d应该最小，而在小于最优划 分或者大于最优划分时,a和d的值也都是此消彼长的。对于而言，并 不一定在取得最优划

30、分时获得了最大值，因此，R的值也就未必是最大 的，对于Jaccard算法，同理,a虽然在取得最优划分是最大，但是 d同时也应该是最小的，这样的话J的值也取决于a的增加的幅度与d 减少的幅度那个大，若前者大则J的值就相对大，反之亦然。这就说明 我们并不能够从得到的R和J的值来判定最优的划分数目，它们仅仅反 映了聚类前后数据点分布的变化情况。下图为我们通过同样以iriss数 据集为例，通过多次k-means聚类后，用该算法进行评价的R值和J 系数值随聚类个数clusternumber变化情况：图5-4 iris数据集Rand算法测试结果图5-5 iris数据集Jaccard算法测试结果从图中我们可

31、以看出R的最大值在聚类个数c=5时出现，而J的最大 值出现在c=2这与iris数据集的划分个数并不一致，我们也无法从图 中找到一个合适的划分个数。但是，从图的走向情况，我们可以看出 Rand指数值和Jaccard值在c=3后大幅度下降，在c=4后又出现大幅 度的上升，这说明在这前后的聚类效果有很大的变化。下表我们对其他 数据集的Rand算法和Jaccard算法测试结果作了一个统计，希望可以 从中发现某些规律：表5-2不同数据集的Rand算法与Jaccard算法评价结果数据集 iris wine glass zoo原始划分个数3 3 6 7Rand 最大值 0.837 0.934 0.694 0

32、.918对应聚类个数5 3 7 5Jaccard 最大值 0.592 0.824 0.305 0.705对应聚类个数2 34 5Rand临界下降聚类数3 3 7 5Rand临界上升聚类数4246Jaccard临界下降聚类数3 3 4 5Jaccard临界上升聚类数42 7 6从表中我们看不出划分个数和评价指数最大值所对应的聚类个数之间 有任何的联系，但是，我们发现在Rand和Jaccard值发生大幅度变化 时所对应的聚类个数总是在划分个数的附近，以zoo数据集为例，它 在c=5后突然下降，而在c=6后突然上升，这种变化情况至少说明在 聚类个数为5,6前后的聚类质量发生了明显的变化，变化的区间也

33、在划 分个数7的附近，这正是由算法的原理所决定，因为R的值和J的值都 受到划分个数的影响。再以glass数据集为例，它在c=7后突然下降, 然后一直到c=4后又突然上升，在4,7这个区间前后聚类的质量有明 显变化。这种变化并不会直接告诉我们最优的划分个数是多少，但至少 我们可以根据这种区间的变化来决定我们在进行聚类的时候聚类个数 的选择应该以变化区间前后为准，这样，我们的聚类效果就应该是比较 好的。小结Rand算法和Jaccard算法都是通过比较聚类前后数据集中代表点的分 布情况来获取一定的评判值，评判值的范围在区间，它的大小受到 数据集划分个数的影响，但与F-measure算法的不同之处在于

34、，根据 该算法并不能直接得到最优划分个数。不过，通过两个评价值的变化区 间，我们可以得到一个最佳聚类划分可能的存在范围，即最好的聚类质 量结果所对应的划分个数应该在评价值的变化区间前后。因此，Rand 算法和Jaccard算法能够提供给我们最佳聚类数目的存在区间，这对于 我们在进行k-means聚类时同样具有一定的指导价值。总体来说，根 据Rand算法与Jaccard算法得到的最大值所对应的划分数目并不是我 们寻找的最优划分数目，通过该算法也得不到最优划分数目，但它可以 给我们提供这个最优划分数目的存在区间，这对于如何聚类同样具有一 定的指导意义。SD算法测试程序运行情况下图为SD算法程序在S

35、-PLUS下的运行情况：图5-6 SD算法程序运行结果测试结果SD算法是基于聚类平均散布性Scat和聚类总体分离性Dis的一种相对度量法，对于每一次k-means聚类，都会得到一个Scat和一个Dis, 假定我们对k-means从3,10进行了聚类那就对应8组Scat和Dis , 之后，我们需要指定Cmax即最大输入聚类个数,Cmax的值应该在 3,10这个范围内然后对应于每一个Cmax，我们都要计算从Cm ax 的SD指数,因此，假如我们指定了 Cmax的值为4,5,6,那么我们就要 计算3次从Cmax的SD指数。最后我们通过比较SD的大小，SD 最小时所对应的聚类个数就是我们要寻找的。下图

36、以iris数据集为例, 描述了 iris数据集在聚类后Cmax不同情况下SD算法评价结果，每一 条线对应于一定的Cmax下的结果：图5-7 iris数据集SD算法测试结果从图所反映的情况来看，在c=3时,SD的值最小，即在此时聚类的平 均散布性和总体分离性出在最佳的平衡位置。它与数据集的划分数是一 致的，但是仅仅通过这一个数据集是不能够说明问题的，我们还需要对其他的数据集进行测试，下表为其他数据集的SD算法测试情况： 表5-3不同数据集SD算法测试结果 数据集 iris wine glass zoo原始划分个数3 3 6 7SD 最小值 2.87 0.0001 9.95 1.724对应划分数目

37、3 8 6 3从表5-3反映的情况来看，除了 iris数据集的评判结果所得到的最优划 分数与原始划分数目一致外，其余数据集都没有达到一致。其实，这个结果 应该是可以预料的，因为SD算法并没有涉及事先划分的相关概念，它 是针对聚类后结果的自然属性来评判的，应此我们得到的最优划分数目 也不一定与原有划分数目一直。同时，也从侧面说明一个问题，也就是 说如果基于此种评判方法而言我们原有的划分方法并不好。小结通过SD算法，我们从聚类后结果的自然属性出发，以聚类平均散布性 Scat和聚类总体分离性Dis作为综合评判标准，SD最小值时所对应的 划分个数就是我们所要寻找的最佳划分数目，我们可以发现SD的值是

38、一个大于0的数，并没有像前面的算法那样被限定在。1区间。实际上, SD的评价结果也是受聚类结果即我们所采用的聚类算法的影响，这种 影响就敲好体现在不同数据集的SD值得差异性上，或许某些数据集我 们并不适合用k-means进行聚类，这样的聚类结果对SD算法本身而 言就有一定的缺陷。当然，尽管如此，但是，我们所关心的是通过该算 法找出一个合适的划分数，而这个划分数就恰好是SD最小时所对应的 聚类个数。Ocq算法测试程序运行情况图5-8为S语言编写的Ocq算法程序在S-PLUS下的运行情况：图5-8 Ocq算法程序运行结果算法测试结果Ocq算法是用聚类结果的自然属性来评价聚类内的同一性和聚类间的 分

39、离性，它与SD同属相对评价法范畴，因此其算法思想也有相似之处， Ocq的值所反映的是聚类密集性Cmp和聚类临近性Prox的平衡程度, 它的值受到平衡因子W的影响，值越大，说明两者的整体平衡效果也就 越好，即聚类内的密度和聚类间的临近性出在一个最合适的位置。下图 以iris数据集为例，它是在已0.5 ,即我们认为聚类密集性和聚类临近性 这两种评价具有相等的权值时所得到的Ocq值。图5-9 iris数据集Ocq算法测试结果从图5-9中所反映出的数据,我们发现综合质量最大时所对应的划分数 目与原始划分数目也是毫无关联，而Ocq的值的范围是处在之间 的，这一点从它的定义也是可以预知的。实际上，从该表所

40、得到划分数 目并不能说是最优划分数目，因为Ocq的值受到国勺影响。因此，我们 还需要对其他值对应的Ocq值做对比统计，以及对其他数据集进行测 试然后看是否能从中找出我们需要的最优划分数目。下图就从其他数据 集在旧的不同值下的Ocq值做出了统计从中我们不难发现对数据集的评价结果的值Ocq确实是受到了W的影响, W不同我们所得到的对于划分数目也会有所不同，因此，Ocq算法是一 个建立在人为指定平衡因子基础上的评价算法，我们所要寻找的最优划 分数目与我们所设定的2的值有关，当我们认为聚类密集性和聚类临近 性具有相等的权值时，我们得到的Ocq最大值所对应的划分个数c仅 仅是在该情况下的最优值,不同的W

41、会导致不同的最好划分数目。当然， 如果我们综合所有的值来考虑Ocq最大时所对应的划分数目，那么iris 数据集、wine数据集、glass数据集、zo。数据集所对应的划分数就应 该是3 , 9 , 10 , 6。从该表中我们也可以发现Ocq的值确实是在。1 区间，而且Ocq算法与数据集的预先划分结构也是毫无关系的。小结Ocq算法是基于对聚类内和聚类间的数据点分布来评判的，它与数据点 的预先制定结构没有关系，Ocq的值是平衡了聚类密集性Cmp和聚类 临近性Prox而得到的。同时它受到权衡Cmp与Prox的因子E大小的 影响，对某一特定2下的Ocq而言,Ocq最大值所对应的划分个数就是 对我们有用

42、的聚类适合划分数目。但是，这个结果并能说明它就是最佳 聚类划分数目，不同E会产生不同的最大Ocq值所对应的戈吩数。Ocq 评判算法是建立在人为指定基础上的，因此如何找到一个合适的W值对 该算法至关重要。如果从整体上来看，我们可以暂时将所有W下的综合 最大Ocq值所对应的划分数目作为我们进行k-means聚类时的合适划 分数目来考虑。综合起来将，Ocq算法是根据评判值来寻找好的划分数数据挖掘的背景及概念 随着网络和存储技术迅猛发展，数据的传播和积累速度不断提高，却发 现新的数据处理和提炼技术非常匮乏。面对日益庞大的数据资源，人们 迫切需要更强有力的工具来挖掘其中有用的信息。数据挖掘就是针 对这一

43、需求而发展起来的一门新兴学科。数据挖掘(Data Mining),又称为数据库中的知识发现(Knowledge Discovery in Database, KDD),就是从大量数据中获取有效的、新颖的、潜在有用的、最终可理解的模式的非平凡过程，简单的说，数据挖 掘就是从大量数据中提取或挖掘知识。并非所有的信息发现任务都 被视为数据挖掘。例如，使用数据库管理系统查找个别的记录，或通过 因特网的搜索引擎查找特定的Web页面，则是信息检索(information retrieval)领域的任务。虽然这些任务是重要的,可能涉及使用复杂的 算法和数据结构，但是它们主要依赖传统的计算机科学技术和数据的明

44、 显特征来创建索引结构，从而有效地组织和检索信息。尽管如此，数据 挖掘技术也已用来增强信息检索系统的能力。数据挖掘的功能1分类首先从数据中选出已经分好类的训练集，在该训练集上运用数据挖掘分 类的技术，建立分类模型，对于没有分类的数据进行分类。注意:类的个 数是确定的，预先定义好的.例如：目，但它同时又受到平衡因子a的影响，因此我们不可能说根据该算法 能够找到最优划分数目，但它可以提供给我们能够进行选择和参考的适 合k-means算法的划分数目。CDbw 算法程序运行情况由于在S-PLUS下运行比较慢,所以改为在C环境下运行。图5-10为 CDbw算法在C环境下的程序运行情况：图5-10 CDb

45、w程序运行结果算法测试结果CDbw算法是通过寻找多个具有代表性点的结构来表达聚类后的数据 点分布情况。它仍然是根据聚类后的自然属性来评判聚类效果的好坏。 它受到聚类内密度和聚类间分离性的制约，这一点与SD有效性指数很 相似,CDbw的值越大说明聚类内的数据点分布和聚类间的数据点分布 刚好合适，该情况下所对应的聚类个数也就是我们所要寻找的划分数目。 下图以iris数据集为例反映了 CDbw指数值随聚类个数不同的变化情 况： 图5-11 iris数据集CDbw算法测试结果 从图5-11中我们不难发现CDbw的值在聚类个数c=6时最大，这个 值就是我们所要寻找的聚类最优划分数目。我们还可以通过测试其

46、他数 据集来观察CDbw的值以及其最大时所对应的划分数目，下表就是对 iris以外的数据集测试后的结果统计情况不同的k-means聚类个数对 应不同的CDbw值。表5-5不同数据集CDbw测试结果数据集 iris wine glass zoo原始划分个数3 3 6 7CDbw 最大值 681.4 31.6 727.3 153.6对应划分数目6747从表5-5中，我们可以看出Ocq评价算法与数据集的预先制定结构也 没有必然的联系，它的值并不局限在区间。CDbw的值越大，说明 聚类的效果相对越好。根据CDbw的值我们是可以找到最优划分数目 的，当然这个最优划分数目是针对k-means算法而言的，这

47、种局限性 也是本文所有算法的缺陷。但就算法本身而言，我们还是达到了通过评 价算法寻找合适划分数目的目的。小结CDbw算法以选取多个代表点表达聚类后的数据集结构，然后通过对这 些代表点在聚类内的分布和聚类间的分布情况做一个评判，以此结果来 评价聚类结果的好坏，这与SD有效性指数、聚类综合质量等算法都有 着相似的特点，而且CDbw的值也不受预先指定结构或者说事先划分 数目的影响。通过k-means下的不同聚类我们可以寻找到CDbw最大 时所对应的最佳划分数目。小结最后我们可以对所有的聚类评价算法做一个小结，通过对比各个算法的 特点以及所寻找到的最优划分数目来得出一定的结论，下表反映了各个 算法的聚

48、类质量评价情况。表5-6不同数据集-不同评价算法对比数据集算法 iris（3 类）zoo （ 7 类）wine （3 类）glass （6 类）F-measure最优划分最优划分7最优划分3最优划分6是否能找到最优划分是 是否与原有划分相关是 Rand最优划分/最优划分/最优划分/最优划分/是否能找到最优划分否 是否与原有划分相关是Jaccard最优划分/最优划分/最优划分/最优划分/是否能找到最优划分数否是否与原有划分相关是SD最优划分3最优划分3最优划分最优划分6是否能找到最优划分数是是否与原有划分相关否Ocq最优划分/最优划分/最优划分/最优划分/是否能找到最优划分数否是否与原有划分相关

49、否CDbw最优划分最优划分7最优划分7最优划分4是否能找到最优划分数是 是否与原有划分相关否 从表5-6中，我们不难发现外部评价法都与实现划分的结构有关，因此 评价的结果也受到其影响，而相对评价法则都是基于聚类自然结果属性 的分析和评判，因此跟数据集的原始划分度并无关联，同时，我们发现， 在这些评价法当中，只有F-measure算法给出的最优划分数目和原始 划分数目一致，其余的都不具备这种条件。在这些评价算法当中，具有 找到最优划分数目功能的算法有F-measure、SD、CDbwo能够给出 聚类最优划分数目可能存在范围的评价算法有Rand. Jaccardo受到人 为条件设定的评价算法是Oc

50、q。此外，我们也可以发现同一个数据集， 同一个聚类结果（k-means下）,在不同的评价算法下，所找到的聚类最 佳划分数目并不是一致的。以iris数据集为例，F-measure给出的最优 划分数目为3 , SD给出的也是3 ,而CDbw给出的却是60这就是不 同的评价结果导致了不同的最佳聚类划分数目。实际上，CDbw评价算 法对于球形数据结构比较适用，但是在整个聚类环节，我们所采用的都 是k-means聚类，我们并没有考虑数据集的特点，因此也就必然导致 用某种评价算法会存在一定的缺陷，因为聚类结果本身对评价算法的适 用度不一定是最好的。当然，这并不影响我们对算法的验证和对结果的 讨论与分析。总

51、体来说，对于已经划分好的数据集我们可以采用外部评 价法来评价其聚类的结果,而对于未划分的我们则可以用相对评价法对 聚类结果的质量进行评价。结束语聚类评价算法能够对给定数据集通过k-means聚类后对结果进行评价。 这里的评价算法包含两大板块:一个是外部评价法，一个是相对评价法。 对于外部评价法有两种即F-measure算法、Rand指数与Jaccard系 数评价法。相对评价法有三种即SD有效性指数、基于聚类分布有效性 度量、基于多代表点有效性指数CDbw算法。外部评价法是与实现指 定的划分结构相关联的算法，通过该算法得到的最优聚类划分数目往往 与事先已经划分好的数目有关。相对评价法测试通过对结果的自然属性 如聚类间密度分布和聚类内密度分布来评