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

《I-Miner环境下多种聚类质量评价方法的实现.docx》由会员分享，可在线阅读，更多相关《I-Miner环境下多种聚类质量评价方法的实现.docx（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

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

5、方法、层次方法、基于密度方法、基于网 格方法和基于模型方法。1 划分方法(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

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

8、。设a、b、c、d分别表示SS、SD、DS、DD的数目，则为数据集中所 有对的最大数，即，N为数据集中点的总数。则C与P之间的相似程 度可由如下有效性指数定义Rand指数:.(4) Jaccard系数：.(5)上述两指数取值范围均为。1,当m二s时，有最大值。4.1.4 算法实现步骤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

9、 = l,p=0S9:i=l,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,转

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

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

12、进行，因此，最后得到的SD是Cmax 不同时，聚类个数c从指定最小值Cmin到Cmax的值，SD取最小值 时所对应的划分个数即为最优的聚类划分数目。4.4.2 算法实现步骤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

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

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

17、时，聚类邻近性有最小值0o为了评价一个聚类系统的综合质量，可将上述聚类密集性与聚类邻近性 组合为一种评价方法，称作聚类综合质量(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转 S

18、5 ,否则转 S7S7:Cmp=Cmp/cS8:i = l,j = l,Prox=0S9 若 j!=i ,转 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为中心、平均方差为半径的超球体

19、，故函数被定义为(23)很显然，如果一个数据点到uij的距离小于簇的平均标准方差，它必然 属于uij的邻域。在每个点被分为一个簇的极端情况下，即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:

20、k=lS6:计算第i簇的第j个代表点与第i簇第k数据点的距离dS7:若 d 二Stdev(Vi),转 S8,否则转 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 =

21、 lS16:若 j!二i 转 S17S17:k=lS18:计算第ij簇的第k个代表点与Uij的距离dS19: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,否

22、贝脖专29S28:聚类间密度 Intejdens = Inter_dens+Lij*Density(Uij)/( 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:结束算法流程图

23、图4-6CDbw算法流程图第五章算法测试及结果5.1 测试数据集本文测试所涉及到的有iris数据集（有150个数据，分为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评价法测试5.1.1 程序运行情况下图为用s语言

24、编写的F-measure算法在S-PLUS下运行情况：第1章:绪论，介绍该论文研究背景和国内外研究现状第2章:介绍数据挖掘的背景和概念，然后引入聚类分析的概念，同时 对聚类方法做介绍，重点讲述了 k-means算法。最后介绍了聚类评价 的概念和当前聚类评价算法的概况以及本文所要实现的聚类评价算法。第3章:主要介绍数据挖掘工具I-Miner以及S语言和S-PLUS第4章:首先介绍建立聚类过程的模型以及评价过程的建立。然后详细 介绍了内部评价法里的F-measure算法、Rand指数和Jaccard系数算法以及 相对评价法里的SD有效性指数算法、基于聚类分布有效性度量指数Ocq 算法、基于多代表点

25、的有效性指数CDbw算法的原理、实现步骤、流 程图等内容。第5章:介绍本文实现的各种算法的程序运行情况和不同数据集进行测 试后的结果以及各种算法内部与相互间的对比情况。第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算法测试结果从图