基于属性值集中度的分类数据聚类有效性内部评价指标

工程科学学报，第41卷，第5期：682-693,2019年5月 Chinese Joural of Engineering,Vol.41,No.5:682-693,May 2019 D0L:10.13374/j.issn2095-9389.2019.05.015;htp:/journals.usth.edu.cm 基于属性值集中度的分类数据聚类有效性内部评价 指标 傅立伟，武森四 北京科技大学东凌经济管理学院，北京100083 区通信作者，E-mail:wusen@manage.ustb.cd.cn 摘要针对分类数据，通过数据对象在属性值上的集中程度定义了新的基于属性值集中度的类内相似度(similarity based on concentration of attribute values,CONC),用于衡量聚类结果中类内各数据对象之间的相似度；通过不同类的特征属性值的差 异程度定义了基于强度向量差异的类间差异度(dissimilarit的y based on discrepancy of SVs,DCRP),用于衡量两个类之间的差异 度.基于CONC和DCRP提出了新的分类数据聚类有效性内部评价指标(clustering validation based on concentration of attribute vues,CVC),它具有以下3个特点：(1)在评价每个类内相似度时，不仅依靠类内各数据对象的特征，还考虑了整个数据集的 信息：(2)采用几个特征属性值的差异评价两个类的差异度，确保评价过程不丢失有效的聚类信息，同时可以消除噪音的影 响：(3)在评价类内相似度及类间差异度时，消除了数据对象个数对评价过程的影响.采用加州大学欧文分校提出的用于机 器学习的数据库(UCI)进行实验，将CVC与类别效用(category utility,CU)指标、基于主观因素的分类数据指标(categorical data clustering with subjective factors,CDCS)指标和基于信息熵的内部评价指标(information entropy,E)等内部评价指标进行对比， 通过外部评价指标标准交互信息(normalized mutual information,NMI)验证内部评价效果.实验表明相对其他内部评价指标， CVC指标可以更有效地评价聚类结果.此外，CVC指标相对于NMⅡ指标，不需要数据集以外的信息，更具实用性 关键词聚类分析；聚类内部有效性评价指标；分类数据：高维数据；相似度：差异度 分类号TP301 A new internal clustering validation index for categorical data based on concentration of attribute values FU Li-wei,WU Sen Donlinks School of Economics and Management,University of Science and Technology Beijing,Beijing 100083,China Corresponding author,E-mail:wusen@manage.ustb.edu.cn ABSTRACT Clustering is a main task of data mining,and its purpose is to identify natural structures in a dataset.The results of cluster analysis are not only related to the nature of the data itself but also to some priori conditions,such as clustering algorithms,sim- ilarity/dissimilarity,and parameters.For data without a clustering structure,clustering results need to be evaluated.For data with a clustering structure,different results obtained under different algorithms and parameters also need to be further optimized by clustering validation.Moreover,clustering validation is vital to clustering applications,especially when external information is not available.It is applied in algorithm selection,parameter determination,number of clusters determination.Most traditional internal clustering valida- tion indices for numerical data fail to measure the categorical data.Categorical data is a popular data type,and its attribute value is discrete and cannot be ordered.For categorical data,the existing measures have their limitations in different application circumstances. In this paper,a new similarity based on the concentration ratio of every attribute value,called CONC,which can evaluate the similarity 收稿日期：2018-04-18 基金项目：国家自然科学基金资助项目(71271027)

工程科学学报,第 41 卷,第 5 期:682鄄鄄693,2019 年 5 月 Chinese Journal of Engineering, Vol. 41, No. 5: 682鄄鄄693, May 2019 DOI: 10. 13374 / j. issn2095鄄鄄9389. 2019. 05. 015; http: / / journals. ustb. edu. cn 基于属性值集中度的分类数据聚类有效性内部评价 指标 傅立伟,武 森苣 北京科技大学东凌经济管理学院, 北京 100083 苣通信作者, E鄄mail: wusen@ manage. ustb. edu. cn 摘 要 针对分类数据,通过数据对象在属性值上的集中程度定义了新的基于属性值集中度的类内相似度( similarity based on concentration of attribute values,CONC),用于衡量聚类结果中类内各数据对象之间的相似度;通过不同类的特征属性值的差 异程度定义了基于强度向量差异的类间差异度(dissimilarity based on discrepancy of SVs,DCRP),用于衡量两个类之间的差异 度. 基于 CONC 和 DCRP 提出了新的分类数据聚类有效性内部评价指标( clustering validation based on concentration of attribute values,CVC),它具有以下 3 个特点:(1)在评价每个类内相似度时,不仅依靠类内各数据对象的特征,还考虑了整个数据集的 信息;(2)采用几个特征属性值的差异评价两个类的差异度,确保评价过程不丢失有效的聚类信息,同时可以消除噪音的影 响;(3)在评价类内相似度及类间差异度时,消除了数据对象个数对评价过程的影响. 采用加州大学欧文分校提出的用于机 器学习的数据库(UCI)进行实验,将 CVC 与类别效用(category utility,CU)指标、基于主观因素的分类数据指标(categorical data clustering with subjective factors,CDCS)指标和基于信息熵的内部评价指标(information entropy,IE)等内部评价指标进行对比, 通过外部评价指标标准交互信息(normalized mutual information,NMI)验证内部评价效果. 实验表明相对其他内部评价指标, CVC 指标可以更有效地评价聚类结果. 此外,CVC 指标相对于 NMI 指标,不需要数据集以外的信息,更具实用性. 关键词 聚类分析; 聚类内部有效性评价指标; 分类数据; 高维数据; 相似度; 差异度 分类号 TP301 收稿日期: 2018鄄鄄04鄄鄄18 基金项目: 国家自然科学基金资助项目(71271027) A new internal clustering validation index for categorical data based on concentration of attribute values FU Li鄄wei, WU Sen 苣 Donlinks School of Economics and Management, University of Science and Technology Beijing, Beijing 100083, China 苣Corresponding author, E鄄mail: wusen@ manage. ustb. edu. cn ABSTRACT Clustering is a main task of data mining, and its purpose is to identify natural structures in a dataset. The results of cluster analysis are not only related to the nature of the data itself but also to some priori conditions, such as clustering algorithms, sim鄄 ilarity / dissimilarity, and parameters. For data without a clustering structure, clustering results need to be evaluated. For data with a clustering structure, different results obtained under different algorithms and parameters also need to be further optimized by clustering validation. Moreover, clustering validation is vital to clustering applications, especially when external information is not available. It is applied in algorithm selection, parameter determination, number of clusters determination. Most traditional internal clustering valida鄄 tion indices for numerical data fail to measure the categorical data. Categorical data is a popular data type, and its attribute value is discrete and cannot be ordered. For categorical data, the existing measures have their limitations in different application circumstances. In this paper, a new similarity based on the concentration ratio of every attribute value, called CONC, which can evaluate the similarity

傅立伟等：基于属性值集中度的分类数据聚类有效性内部评价指标 ·683· of objects in a cluster,was defined.Similarly,a new dissimilarity based on the discrepancy of characteristic attribute values,called DCRP,which can evaluate the dissimilarity between two clusters,was defined.A new internal clustering validation index,called CVC,which is based on CONC and DCRP,was proposed.Compared to other indices,CVC has three characteristics:(1)it evaluates the compactness of a cluster based on the information of the whole dataset and not only that of a cluster;(2)it evaluates the separation between two clusters by several characteristic attributes values so that the clustering information is not lost and the negative effects caused by noise are eliminated;(3)it evaluates the compactness and separation without influence from the number of objects.Further- more,UCI benchmark datasets were used to compare the proposed index with other internal clustering validation indices (CU,CDCS, and IE).An external index (NMI)was used to evaluate the effect of these internal indices.According to the experiment results,CVC is more effective than the other internal clustering validation indices.In addition,CVC,as an internal index,is more applicable than the NMI external index,because it can evaluate the clustering results without external information. KEY WORDS cluster analysis;interal clustering validation index;categorical data;high dimensional data;similarity;dissimi- larity 聚类分析结果除与数据本身性质有关外，还与 NMI)[8,12,16].内部评价指标依靠数据集本身提供的 一些先验的选择有关，比如算法的选择、相似度或差 信息，通过类内的紧密程度和类间的分离程度评价 异度的选择、参数设定等).不论数据本身是否具 聚类的结果.类内紧密度和类间分离度越大，聚类 有聚类倾向性，聚类算法都能给出一个聚类结果，因 效果越好.相对指标用于评价聚类的不同结果，从 此需要对聚类结果进行有效性进行判断.另一方 而选择最优结果 面，即使是针对具有聚类结构的数据，在不同算法及 1.1聚类内部有效性评价指标 参数的设定下得出的不同结果也需要通过聚类评价 令X={x1,x2,…,xn}为一个有n个对象的m 进一步比选择优.针对数值型数据的聚类有效性内 维分类数据集，x,={x,,…,x},1≤i≤n,其中分 部评价的研究已经取得丰富的成果].但是，在实 类属性为A={A1,A2,…,An}.V为属性A,的属性 际应用中，针对离散型的分类数据的聚类算法及评 值集合，y={,,…,.其中，为属性4，的可 价方法仍有不足[).聚类分析的一个基础问题是定 取值个数，1≤j≤m.假设数据集的一个聚类结果为 义相似度或差异度，不同的定义对聚类算法以及评 T={C1,C2,…,Cm{,其中nc为类个数，记类C中 价方式等各环节和结果起着决定性作用4).有学 数据对象的个数为ICI,1≤k≤nc.按照数据对象 者[]指出聚类分析研究中的5个问题，其中定义分 之间差异度/相似度度量方式划分，常用的分类数据 类数据的差异度、识别分类数据的类个数、数据集结 聚类有效性内部评价指标通常可以分为基于简单匹 构等问题都可以通过合适的聚类有效性评价解决. 配(Simple matching)的指标、基于概率模型的指标 此外，聚类集成技术(clustering ensemble selection) 以及基于嫡的指标 综合利用多个聚类结果完成聚类分析，从而提升聚 (1)基于简单匹配的指标.很多分类数据的内 类结果的准确性和稳定性).大量聚类集成研究通 过选择多个内部评价指标实现优化聚类结果[8-】， 部评价指标基于针对数值型数据的评价指标思想， 通过用简单匹配方式度量数据对象之间的差异度， 因此内部评价指标的评价能力是解决这些问题的重 如均方根标准差(root-mean-square standard devia- 要基础.本文基于数据对象在分类属性上的集中程 度和特征属性值差异提出新的类内相似度CONC和 tion,RMSSTD)指标和戴维森堡丁(Davies--Bouldin, 类间差异度DCRP,并通过CONC和DCRP定义了 DB)指标.简单匹配方式是针对分类数据最基本的 新的分类数据聚类有效性内部评价指标CVC. 差异度的度量方式，数据对象x,和x,简单匹配指标 表达式如下： 1分类数据的内部有效性评价的研究 dist(x,)= ∑6，) (1) 聚类有效性评价主要有外部评价指标、内部评 i=1 价指标和相对评价指标.外部指标依靠数据集以外 1,≠ 6(,)= (2) 的信息，通过外部信息与聚类结果的匹配程度评价 0,x=x 聚类效果，常见的外部评价指标有F-measure), k-modes算法采用众数概念定义类中心，令c rand index、Jaccard系数I)以及被广泛应用的标 表示类C的中心，c4={c4,c2,…,},将各类中对 2 准交互信息（normalized mutual information, 象到类中心距离作为目标函数，表达式为

傅立伟等: 基于属性值集中度的分类数据聚类有效性内部评价指标 of objects in a cluster, was defined. Similarly, a new dissimilarity based on the discrepancy of characteristic attribute values, called DCRP, which can evaluate the dissimilarity between two clusters, was defined. A new internal clustering validation index, called CVC, which is based on CONC and DCRP, was proposed. Compared to other indices, CVC has three characteristics: (1) it evaluates the compactness of a cluster based on the information of the whole dataset and not only that of a cluster; (2) it evaluates the separation between two clusters by several characteristic attributes values so that the clustering information is not lost and the negative effects caused by noise are eliminated; (3) it evaluates the compactness and separation without influence from the number of objects. Further鄄 more, UCI benchmark datasets were used to compare the proposed index with other internal clustering validation indices (CU, CDCS, and IE). An external index (NMI) was used to evaluate the effect of these internal indices. According to the experiment results, CVC is more effective than the other internal clustering validation indices. In addition, CVC, as an internal index, is more applicable than the NMI external index, because it can evaluate the clustering results without external information. KEY WORDS cluster analysis; internal clustering validation index; categorical data; high dimensional data; similarity; dissimi鄄 larity 聚类分析结果除与数据本身性质有关外,还与 一些先验的选择有关,比如算法的选择、相似度或差 异度的选择、参数设定等[1] . 不论数据本身是否具 有聚类倾向性,聚类算法都能给出一个聚类结果,因 此需要对聚类结果进行有效性进行判断. 另一方 面,即使是针对具有聚类结构的数据,在不同算法及 参数的设定下得出的不同结果也需要通过聚类评价 进一步比选择优. 针对数值型数据的聚类有效性内 部评价的研究已经取得丰富的成果[2] . 但是,在实 际应用中,针对离散型的分类数据的聚类算法及评 价方法仍有不足[3] . 聚类分析的一个基础问题是定 义相似度或差异度,不同的定义对聚类算法以及评 价方式等各环节和结果起着决定性作用[4鄄鄄5] . 有学 者[6]指出聚类分析研究中的 5 个问题,其中定义分 类数据的差异度、识别分类数据的类个数、数据集结 构等问题都可以通过合适的聚类有效性评价解决. 此外,聚类集成技术( clustering ensemble selection) 综合利用多个聚类结果完成聚类分析,从而提升聚 类结果的准确性和稳定性[7] . 大量聚类集成研究通 过选择多个内部评价指标实现优化聚类结果[8鄄鄄12] , 因此内部评价指标的评价能力是解决这些问题的重 要基础. 本文基于数据对象在分类属性上的集中程 度和特征属性值差异提出新的类内相似度 CONC 和 类间差异度 DCRP,并通过 CONC 和 DCRP 定义了 新的分类数据聚类有效性内部评价指标 CVC. 1 分类数据的内部有效性评价的研究 聚类有效性评价主要有外部评价指标、内部评 价指标和相对评价指标. 外部指标依靠数据集以外 的信息,通过外部信息与聚类结果的匹配程度评价 聚类效果,常见的外部评价指标有 F鄄measure [13] , rand index [14] 、Jaccard 系数[15] 以及被广泛应用的标 准 交 互 信 息 ( normalized mutual information, NMI) [8,12,16] . 内部评价指标依靠数据集本身提供的 信息,通过类内的紧密程度和类间的分离程度评价 聚类的结果. 类内紧密度和类间分离度越大,聚类 效果越好. 相对指标用于评价聚类的不同结果,从 而选择最优结果. 1郾 1 聚类内部有效性评价指标 令 X = {x1 , x2 , …, xn }为一个有 n 个对象的 m 维分类数据集,xi = {x 1 i ,x 2 i ,…,x m i },1臆i臆n,其中分 类属性为 A = {A1 , A2 , …, Am }. Vj为属性 Aj的属性 值集合,Vj = {v j 1 ,v j 2 ,…,v j r j }. 其中,rj为属性 Aj的可 取值个数,1臆j臆m. 假设数据集的一个聚类结果为 仔 = {C1 ,C2 ,…,Cnc },其中 nc 为类个数,记类 Ck中 数据对象的个数为 | Ck | ,1臆k臆nc. 按照数据对象 之间差异度/ 相似度度量方式划分,常用的分类数据 聚类有效性内部评价指标通常可以分为基于简单匹 配( Simple matching) 的指标、基于概率模型的指标 以及基于熵的指标. (1)基于简单匹配的指标. 很多分类数据的内 部评价指标基于针对数值型数据的评价指标思想, 通过用简单匹配方式度量数据对象之间的差异度, 如均方根标准差 ( root鄄mean鄄square standard devia鄄 tion,RMSSTD)指标和戴维森堡丁(Davies鄄鄄 Bouldin, DB)指标. 简单匹配方式是针对分类数据最基本的 差异度的度量方式,数据对象 xs 和 xt 简单匹配指标 表达式如下: dist(xs,xt) = 移 m j = 1 啄(x j s,x j t) (1) 啄(x j s,x j t) = 1, x j s屹x j t 0, x j { s = x j t (2) k鄄modes 算法采用众数概念定义类中心,令 ck 表示类 Ck的中心,ck = { c 1 k,c 2 k,…,c m k } ,将各类中对 象 到 类 中 心 距 离 作 为 目 标 函 数, 表 达 式 为 ·683·

.684. 工程科学学报，第41卷，第5期 各个类中各属性取值的情况，而不是单纯考虑两个 F(π)= 立∑dis(x,).k-mdes算法的目标 对象的取值的异同).但是，对于一个确定的数据 函数也可以作为内部评价指标. 集的每个属性，P(A=)都是一个定值，因此CU RMSSTD指标常用来判断数据集的类个数，最 在引用整个数据集信息时并未结合各个类的具体情 初是用来度量层次聚类中得到的每个类的同质性， 况.此外，CU计算了各个属性所有属性值的概率， 这和聚类分析为了得到同质的类的目的相一致，所 容易受到噪音的影响.CU取值越高，同一类中在同 以一个类的RMSSTD值应该越小越好，RMSSTD指 一属性上取值相同概率越大，聚类效果越好 标表达式为： 基于主观因素的分类数据(categorical data clus- tering with subjective factors,.CDCS)指标l)基于类 ∑dist(x:,ce) 内相似度和类间差异度定义，其表达式如下： RMSSTD(T)= k=1xECA (3) m x Σ4G.1-1) inter() DB指标表达式为： [mag,P(A,=,1C)]}/ De名gg ne max [S(C)+S(C,)]) (4) dist(c,c,） sim(c,c,)1C,UG,1 其中，S(C,)= 是 1 dist(x,c,),S(C）= 6 n×(nc-1) 白三(，6)，表示类内的松放程度哪指 其中，sim(c.C)={三mim[P(4=1c,), i=1 标通过任意两个类的类内平均距离之和与两个类中 P(4=,IC,)]+s,e为样本中数据对象的个数的 心距离之比的最大值衡量聚类结果，DB指标越小表 示类内越紧密，类间差异度越大，聚类效果越好.通 倒数.类内相似度intra(π)通过各类中每个属性取 过基于简单匹配的内部评价指标计算简便、易于理 值概率最高的属性值计算得出，类间相似度inter 解，其主要弊端为：通过数据对象与其类中心的匹配 (π)通过任意两个类的重合度综合计算得出. 程度评价聚类效果，而类中心本身并不能体现类中 CDCS越大，聚类效果越好.CDCS在计算intra(π) 的主要信息：通过简单匹配判断数据对象之间的差 和Sim(C,C,)时，分别专注于各类内最高取值概率 和任意两个类中最小的属性值概率，因此CDCS指 异程度，没有综合考虑整个数据集的信息：简单匹配 标容易受到噪音影响 的本质是计量取值相同的属性的个数，评价聚类效 (3)基于信息嫡的内部评价指标.嫡的概念来 果时受数据对象个数影响很大.基于以上原因，该 自统计热力学，在聚类有效性评价中，信息嫡通过衡 类指标在评价聚类有效性时受到很大的局限. 量数据对象分布的混乱程度评价聚类效果.信息熵 (2)基于概率模型的评价指标.相对于简单匹 (information entropy,.IE)指标2o]通过信息嫡理论度 配方式，基于概率模型的差异度并不是直接判断数 量聚类结果.E与聚类结果优劣呈负相关，即E值 据对象在同一属性上取值是否相同，其主要思想是 越大，聚类效果越差.E表达式如下： 衡量数据对象取值相同的概率 类别效用(category utility,CU)指标[]除作为 E(π)=L 聚类有效性评价指标外，也应用于部分分类数据聚 P(A;=C)log[P(A;=C)] (7) 类算法，表达式如下： 文献[21]指出嫡指标无法客观应对聚类算法 CU(m)=⊥ 的均匀效应.均匀效应指部分聚类算法倾向于生成 数据对象数量比较均匀的类.嫡指标能揭示每个类 [P(4=IC)2-P(4=)2] 5) 的纯粹程度，但在面对均匀效应时不一定能如实反 其中，P(A=IC:)为类C中在属性A上数据对象 映整个结果的优劣.此外，E指标在计算各类的混 取值为。的概率，P(A=。)表示在数据集X中数 乱程度时，未考虑整个数据集的信息. 据对象在属性A,上取值为，概率.CU通过同一类 1.2聚类外部有效性评价指标 中在一个属性上两个数据对象取值相同的概率，评 通常情况下，外部评价指标通过将聚类结果与 价聚类效果，在计算过程中考虑到了整个数据集和 “真实”的类标签对比衡量聚类效果.NMI指标由于

工程科学学报,第 41 卷,第 5 期 F(仔) = 移 nc k = 1 x移i沂Ck dist(xi,ck) . k鄄modes 算法的目标 函数也可以作为内部评价指标. RMSSTD 指标常用来判断数据集的类个数,最 初是用来度量层次聚类中得到的每个类的同质性, 这和聚类分析为了得到同质的类的目的相一致,所 以一个类的 RMSSTD 值应该越小越好,RMSSTD 指 标表达式为: RMSSTD(仔) = 移 nc k = 1 x移i沂Ck dist(xi,ck) m 伊 移 nc k = 1 (| Ck | - 1) (3) DB 指标表达式为: DB(仔) = 1 nc 移 nc s = 1 max nc t = 1,t屹 {s [S(Cs) + S(Ct)] dist(cs,ct } ) (4) 其中, S ( Cs ) = 1 | Cs | x移i沂Cs dist ( xi, cs ), S ( Ct ) = 1 | Ct | x移i沂Ct dist( xi,ct),表示类内的松散程度. DB 指 标通过任意两个类的类内平均距离之和与两个类中 心距离之比的最大值衡量聚类结果,DB 指标越小表 示类内越紧密,类间差异度越大,聚类效果越好. 通 过基于简单匹配的内部评价指标计算简便、易于理 解,其主要弊端为:通过数据对象与其类中心的匹配 程度评价聚类效果,而类中心本身并不能体现类中 的主要信息;通过简单匹配判断数据对象之间的差 异程度,没有综合考虑整个数据集的信息;简单匹配 的本质是计量取值相同的属性的个数,评价聚类效 果时受数据对象个数影响很大. 基于以上原因,该 类指标在评价聚类有效性时受到很大的局限. (2)基于概率模型的评价指标. 相对于简单匹 配方式,基于概率模型的差异度并不是直接判断数 据对象在同一属性上取值是否相同,其主要思想是 衡量数据对象取值相同的概率. 类别效用( category utility,CU) 指标[17] 除作为 聚类有效性评价指标外,也应用于部分分类数据聚 类算法,表达式如下: CU(仔) = 1 nc 移 nc k = 1 | Ck | n 移 m j = 1 移 r j p = 1 · [P(Aj = v j p | Ck) 2 - P(Aj = v j p) 2 ] (5) 其中,P(Aj = v j p | Ck)为类 Ck中在属性 Aj上数据对象 取值为 v j p 的概率,P( Aj = v j p )表示在数据集 X 中数 据对象在属性 Aj上取值为 v j p 概率. CU 通过同一类 中在一个属性上两个数据对象取值相同的概率,评 价聚类效果,在计算过程中考虑到了整个数据集和 各个类中各属性取值的情况,而不是单纯考虑两个 对象的取值的异同[18] . 但是,对于一个确定的数据 集的每个属性,P( Aj = v j p ) 都是一个定值,因此 CU 在引用整个数据集信息时并未结合各个类的具体情 况. 此外,CU 计算了各个属性所有属性值的概率, 容易受到噪音的影响. CU 取值越高,同一类中在同 一属性上取值相同概率越大,聚类效果越好. 基于主观因素的分类数据(categorical data clus鄄 tering with subjective factors,CDCS) 指标[19] 基于类 内相似度和类间差异度定义,其表达式如下: CDCS(仔) = intra(仔) inter(仔) = { 移 nc k = 1 | Ck | n 移 m j = 1 1 m · [max r j p = 1P(Aj = v j p | Ck)] } é ë ê ê 3 移 nc-1 t = 1 移 nc s = 1 Sim(Ct,Cs) 1 m | Ct 胰 Cs | n 伊 (nc - 1 ù û ú ) ú (6) 其中,Sim( Ct,Cs ) = 仪 m j = { 1 移 r j p = 1 min [ P( Aj = v j p | Ct ), P(Aj = v j p | Cs)] + 着 } ,着 为样本中数据对象的个数的 倒数. 类内相似度 intra(仔)通过各类中每个属性取 值概率最高的属性值计算得出,类间相似度 inter (仔) 通 过 任 意 两 个 类 的 重 合 度 综 合 计 算 得 出. CDCS 越大,聚类效果越好. CDCS 在计算 intra(仔) 和 Sim(Ct,Cs)时,分别专注于各类内最高取值概率 和任意两个类中最小的属性值概率,因此 CDCS 指 标容易受到噪音影响. (3)基于信息熵的内部评价指标. 熵的概念来 自统计热力学,在聚类有效性评价中,信息熵通过衡 量数据对象分布的混乱程度评价聚类效果. 信息熵 (information entropy,IE)指标[20] 通过信息熵理论度 量聚类结果. IE 与聚类结果优劣呈负相关,即 IE 值 越大,聚类效果越差. IE 表达式如下: IE(仔) = 1 nc 移 nc k = 1 | Ck | n 移 m j = 1 移 r j p = 1 · P(Aj = v j p | Ck)log[P(Aj = v j p | Ck)] (7) 文献[21]指出熵指标无法客观应对聚类算法 的均匀效应. 均匀效应指部分聚类算法倾向于生成 数据对象数量比较均匀的类. 熵指标能揭示每个类 的纯粹程度,但在面对均匀效应时不一定能如实反 映整个结果的优劣. 此外,IE 指标在计算各类的混 乱程度时,未考虑整个数据集的信息. 1郾 2 聚类外部有效性评价指标 通常情况下,外部评价指标通过将聚类结果与 “真实冶的类标签对比衡量聚类效果. NMI 指标由于 ·684·

傅立伟等：基于属性值集中度的分类数据聚类有效性内部评价指标 .685· 计算简便且拥有良好的效果，是常用的外部评价方 其中，I{x:∈C4l=}I为该类中取值为，的数据 式.对于有n个数据对象的数据集，令π，={C, 对象的个数，记特征属性值的个数为n,(Ck,A). C2,…C}和π2={C,C,…C2}为其两个划分， 特征属性值的搜索方法为：对于类C,在属性A,将 nc,和nc2为类个数.对于两个划分中的类C和类 DV(C4,A)中各元素从大到小的顺序重新排列得 C,IC∩C1为两个类共同的对象的个数，1C1和 到DVm(Ck,A)=(d1,d2,…,d,…),l,为重新 IC2I分别为两个类的对象个数.记两个划分的NMI 排序后的角标.对DV(Ck,A)逐项求差后，得到 值为NMI(π1，T2),则 eDVm(C,4y)=(,,…,）,其中n=dn1- NMI(π1，T2)= ,·搜索eDVm(C,A)中的最大值，取其角标 c:nCIxlog 2 n xl C n C2 I la在DVm(Ck,A)中搜索不小于dn的元素， I C I xI C2 I 这些元素对应的属性值为该类的特征属性值.搜索 I C I I C I 21C21×1og 特征属性值的过程如图1，其中灰色的属性值为特 n 征属性值.与DV不同，SV作用主要体现在两个方 (8) 面：(1)标识特征属性值，即SV并不描述每个属性 值的取值情况，它只表示特征属性值的取值，对于其 2 聚类内部评价指标CVC相关定义 他属性值，SV中对应元素取值为0，从而消除了噪 聚类分析的主要思想是将相似的数据对象划分 音影响：(2)SV在描述特征属性值取值情况时，采 到同一个类中，从而使同一个类中的数据对象尽可 用标准化方式进行处理，从而突出了类的特征属性 能相似，不同类中的数据对象尽可能不同.对于分 值强度 类数据，相似度越高的类在各属性上取相同属性值 的数据对象的个数越多.对于一个类的某一属性， 属性可取值 可以用属性值的集中程度表示数据对象之间的相似 度，即集中程度越高，类内相似度越大.本节基于各 DV(C A 属性的集中程度，提出分类数据聚类内部有效性评 价指标.对于数据集X的一个类C:的属性A:,记属 DV(C 性分布向量(DV)是一个有，个元素的向量，令 eDV(C.A DV(Ck,4)=(d,,…,d。,…),其中d=1{x:∈ Ck=}I,即d为属性A上取值为的数据对 最大值 象的个数，且立4，=1C1.当没有数据对象在该属 图1特征属性值搜索示意图 p=l Fig.1 Schematic diagram for selecting the characteristic attribute 性上取值为时，d。=0. values 2.1基础定义 2.2类内相似度CONC 定义I:强度向量SV(strength of concentration 定义2：基于集中度的绝对类内相似度(absolute vector for a cluster).对于数据集X的任意一个类Ce similarity based on concentration,ACONC).C 的任意一个属性A,若数据对象的取值集中在某几 在属性A,上取各属性值的数据对象个数越接近，即 个属性值上，即DV(C,A)中存在明显较大的几个 DV(Ck,A)中的各个元素大小越接近，则类C在属 元素，这些元素对应的属性值体现了类C:在A,上的 性A表现出的相似度越差.反之，若类C,在属性A 主要特征，定义其为该类的特征属性值.为进一步 上取某些属性值的数据对象越集中，即DV(Ck,A) 衡量各特征属性值的强度，定义类C在A,上的强度 中的某几个元素明显大于其他元素，则类内的各数 向量SV(Ck,A)为： 据对象之间越相似，类C在属性A,上表现的类内相 SV(C4,A)=(,,…,2,…） (9) 似度越高.ACONC是通过衡量这个集中程度，判断 = 类内相似度.令Q(C,A)和M(C,A)分别为 I{x:∈C4l=}I ,,是该类特征属性值 DV(C,A)中各元素的平方平均数和算术平均数， ICl (10) 则该类在属性A,上的类内绝对相似度ACONC定义 0 ,。非该类特征属性值 如下：

傅立伟等: 基于属性值集中度的分类数据聚类有效性内部评价指标 计算简便且拥有良好的效果,是常用的外部评价方 式. 对于有 n 个数据对象的数据集,令 仔1 = { C 1 1 , C 1 2 ,…C 1 nc1 } 和 仔2 = {C 2 1 ,C 2 2 ,…C 2 nc2 }为其两个划分, nc1和 nc2为类个数. 对于两个划分中的类 C 1 t 和类 C 2 s , | C 1 t 疑C 2 s | 为两个类共同的对象的个数, | C 1 t | 和 | C 2 s |分别为两个类的对象个数. 记两个划分的 NMI 值为 NMI(仔1 ,仔2 ),则 NMI(仔1 ,仔2 ) = 移 nc1 t = 1 移 nc2 s = 1 | C 1 t 疑 C 2 s | 伊 log n 伊| C 1 t 疑 C 2 s | | C 1 t | 伊| C 2 s | 移 nc1 t = 1 | C 1 t | 伊 log | C 1 t | n 伊 移 nc2 s = 1 | C 2 s | 伊 log | C 2 s | n (8) 2 聚类内部评价指标 CVC 相关定义 聚类分析的主要思想是将相似的数据对象划分 到同一个类中,从而使同一个类中的数据对象尽可 能相似,不同类中的数据对象尽可能不同. 对于分 类数据,相似度越高的类在各属性上取相同属性值 的数据对象的个数越多. 对于一个类的某一属性, 可以用属性值的集中程度表示数据对象之间的相似 度,即集中程度越高,类内相似度越大. 本节基于各 属性的集中程度,提出分类数据聚类内部有效性评 价指标. 对于数据集 X 的一个类 Ck的属性 Aj,记属 性分布向量( DV) 是一个有 rj 个元素的向量,令 DV(Ck,Aj) = (a j 1 ,a j 2 ,…,a j p,…a j r j ),其中 a j p = | {xi 沂 Ck | x j i = v j p} | ,即 a j p 为属性 Aj上取值为 v j p 的数据对 象的个数,且 移 r j p = 1 a j p = | C | . 当没有数据对象在该属 性上取值为 v j p 时,a j p = 0. 2郾 1 基础定义 定义 1:强度向量 SV( strength of concentration vector for a cluster). 对于数据集 X 的任意一个类 Ck 的任意一个属性 Aj,若数据对象的取值集中在某几 个属性值上,即 DV(Ck, Aj)中存在明显较大的几个 元素,这些元素对应的属性值体现了类 Ck在 Aj上的 主要特征,定义其为该类的特征属性值. 为进一步 衡量各特征属性值的强度,定义类 Ck在 Aj上的强度 向量 SV(Ck, Aj)为: SV(Ck,Aj) = (s j 1 ,s j 2 ,…,s j p,…s j r j ) (9) s j p = | {xi沂Ck | x j i = v j p} | | Ck | ,v j p 是该类特征属性值 0 ,v j p ì î í ïï ïï 非该类特征属性值 (10) 其中, | {xi沂Ck | x j i = v j p} | 为该类中取值为 v j p 的数据 对象的个数,记特征属性值的个数为 ns (Ck, Aj ). 特征属性值的搜索方法为:对于类 Ck在属性 Aj,将 DV(Ck, Aj)中各元素从大到小的顺序重新排列得 到 DVsort(Ck,Aj) = (a j l1 ,a j l2 ,…,a j lp ,…a j l r j ),l p为重新 排序后的角标. 对 DVsort(Ck, Aj)逐项求差后,得到 eDVsort(Ck,Aj) = ( e j 1 ,e j 2 ,…,e j l r j - 1 ),其中e j lp = a j lp + 1 - a j lp . 搜索 eDVsort ( Ck, Aj ) 中的最大值,取其角标 l target . 在 DVsort(Ck, Aj)中搜索不小于 a j l target的元素, 这些元素对应的属性值为该类的特征属性值. 搜索 特征属性值的过程如图 1,其中灰色的属性值为特 征属性值. 与 DV 不同,SV 作用主要体现在两个方 面:(1)标识特征属性值,即 SV 并不描述每个属性 值的取值情况,它只表示特征属性值的取值,对于其 他属性值,SV 中对应元素取值为 0,从而消除了噪 音影响;(2) SV 在描述特征属性值取值情况时,采 用标准化方式进行处理,从而突出了类的特征属性 值强度. 图 1 特征属性值搜索示意图 Fig. 1 Schematic diagram for selecting the characteristic attribute values 2郾 2 类内相似度 CONC 定义2:基于集中度的绝对类内相似度(absolute similarity based on concentration,ACONC). 若类 Ck 在属性 Aj上取各属性值的数据对象个数越接近,即 DV(Ck, Aj)中的各个元素大小越接近,则类 Ck在属 性 Aj表现出的相似度越差. 反之,若类 Ck在属性 Aj 上取某些属性值的数据对象越集中,即 DV(Ck, Aj) 中的某几个元素明显大于其他元素,则类内的各数 据对象之间越相似,类 Ck在属性 Aj上表现的类内相 似度越高. ACONC 是通过衡量这个集中程度,判断 类内相似度. 令 Q( Ck, Aj ) 和 M( Ck, Aj ) 分别为 DV(Ck, Aj)中各元素的平方平均数和算术平均数, 则该类在属性 Aj上的类内绝对相似度 ACONC 定义 如下: ·685·

·686· 工程科学学报，第41卷，第5期 ACONC(C,A,)= (C,A）=0.若d。=|C41,d==…=d。-1= 产[0G4-MG4月 (11) 心1=…=心=0，即全部数据对象取相同属性值， 此时ACONC(C,A)取值最大，类C中数据对象在 属性A,上集中程度最高，记此时ACONC为ACONC 其中，Q(Ck,A)= M(C,A)= (C4,A). 三号ACONC(C,)表示DvV(C,)中任意两 定理2：对于类C:上的任意一个属性A,所有数 据对象取值相同时ACONC取最大值. 项差的平方和的均值，即DV(Ck,A)反映了各元素 证明： 之间的差异情况，体现了属性A,上各属性值上数据 对于类C:上的任意一个属性A,令，为可取值 对象的集中程度.当ACONC(C:,A;)越大，DV(C, 个数.记其ACONC为ACONC(C4,A),d为其DV A)中各元素大小相差越大，属性值集中度越高.反 向量的任意一个元素，I≤p≤r其DV向量各元素 之，属性值集中度越低.因此，ACONC(Ce,A)越 的平方平均数和算数平均数为Q,M.当类中所有数 大，类内相似度越高. 据对象取值相同时，记此时ACONC为ACONC 定理1：AC0NC(Ck,A)为类Ck属性A,上 (C4,A),其DV向量各元素的平方平均数和算数 DV(C:,A)中任意两项差的平方和的均值 平均数为Qr,M故Q2=（∑d.）, 证明： M=M=(∑d),则 ACONC(C,A)-ACONC(C,A)= 名4-（三4+三至川 Q--Q-r1= 2(Σ°-（∑）°- %-n会听-2三三4小 Σ(d)+(Σd)]= 至立d-川 2I(4)-(a] 式中，么(a,-a,)尸为C=[巧×(-1)] 三+ ÷(军三dd)0 2项的和. 故ACONC(C,A)≥ACONC(C,A,),即类 ACONC(C:,A,)= C:中所有数据对象取值相同时，ACONC取最大值. 产[0G4r-G- 证明完毕 定义3：基于属性值集中度的类内相似度(simi- 产引层三以川 larity based on concentration of attribute values, CONC).将ACONC标准化处理后得到CONC,令 至龙d- CONC(C:,A)表示类C,在属性A,上的相似度.在 [巧×(-1)]/2= 综合考虑特征属性值个数n,(C:,A,)和类中数据对 象个数比重后，定义类的类内相似度CONC(C:),则 至2d-d小： CONC(C,A,)= 5=1t=s+1 C ACONC(Ck,A)子×Q(Ck,A)2-1Ck2 ACONC(Ck,A)为类C.在属性A上DV(Ck, ACONC(C,A (5,-1)×1C42 4)中任意两项差的平方和的均值.证明完毕 (12) 由均值不等式可得Q(C,A)≥M(Ck,A),当 ICCONC(CA (13) 且仅当d==…=d时，Q(Ck,A)=M(C4,A). C0NC(C)=xI-m名n,(CA） 此时，数据对象在各属性值上平均分布，即ACONC CONC在衡量每个类的类内相似度时，统筹考

工程科学学报,第 41 卷,第 5 期 ACONC(Ck,Aj) = 2rj rj - 1 [Q(Ck,Aj) 2 - M(Ck,Aj) 2 ] (11) 其 中 , Q ( Ck , Aj ) = 移 r j p = 1 (a j p) 2 rj , M(Ck,Aj) = 移 r j p = 1 a j p rj . ACONC(Ck, Aj)表示 DV(Ck, Aj)中任意两 项差的平方和的均值,即 DV(Ck, Aj)反映了各元素 之间的差异情况,体现了属性 Aj上各属性值上数据 对象的集中程度. 当 ACONC(Ck, Aj)越大,DV(Ck, Aj)中各元素大小相差越大,属性值集中度越高. 反 之,属性值集中度越低. 因此,ACONC(Ck, Aj ) 越 大,类内相似度越高. 定理 1: ACONC ( Ck, Aj ) 为 类 Ck 属 性 Aj 上 DV(Ck, Aj)中任意两项差的平方和的均值. 证明: Q(Ck,Aj) 2 - M(Ck,Aj) 2 = 移 r j p = 1 a j2 p rj æ è ç - ç 移 r j p = 1 a j p r ö ø ÷÷ j 2 = 1 r 2 [ j rj 移 r j p = 1 a j2 p - ( 移 r j p = 1 a j2 p + 2 移 r j-1 s = 1 移 r j t = s+1 a j s·a ) ] j t = 1 r 2 [ j (rj - 1) 移 r j p = 1 a j2 p - 2 移 r j-1 s = 1 移 r j t = s+1 a j s·a ] j t = 1 r 2 [ j 移 r j-1 s = 1 移 r j t = s+1 (a j s - a j t) ] 2 上式中, 移 r j-1 s = 1 移 r j t = s+1 (as - at) 2 为 C 2 r j = [rj 伊 (rj - 1)] / 2 项的和. ACONC(Ck,Aj) = 2rj rj - 1 [Q(Ck,Aj) 2 - M(Ck,Aj) 2 ] = 2rj rj - 1 · 1 r 2 [ j 移 r j-1 s = 1 移 r j t = s+1 (a j s - a j t) ] 2 = 移 r j-1 s = 1 移 r j t = s+1 (a j s - a j t) 2 [rj 伊 (rj - 1)] / 2 = 移 r j-1 s = 1 移 r j t = s+1 (a j s - a j t) 2 C 2 r j ACONC(Ck, Aj ) 为类 Ck 在属性 Aj 上 DV(Ck, Aj)中任意两项差的平方和的均值. 证明完毕. 由均值不等式可得 Q(Ck, Aj)逸M(Ck, Aj),当 且仅当 a j 1 = a j 2 = … = a j r j时,Q(Ck, Aj) = M(Ck, Aj). 此时,数据对象在各属性值上平均分布,即 ACONC (Ck, Aj ) = 0. 若 a j p = | Ck | ,a j 1 = a j 2 = … = a j p - 1 = a j p + 1 = … = a j r j = 0,即全部数据对象取相同属性值, 此时 ACONC(Ck, Aj)取值最大,类 Ck中数据对象在 属性 Aj上集中程度最高,记此时 ACONC 为ACONCmax (Ck, Aj). 定理 2:对于类 Ck上的任意一个属性 Aj,所有数 据对象取值相同时 ACONC 取最大值. 证明: 对于类 Ck上的任意一个属性 Aj,令 rj为可取值 个数. 记其 ACONC 为 ACONC(Ck, Aj),a j p 为其 DV 向量的任意一个元素,1臆p臆rj . 其 DV 向量各元素 的平方平均数和算数平均数为 Q,M. 当类中所有数 据对象取值相同时,记此时 ACONC 为 ACONCmax (Ck, Aj),其 DV 向量各元素的平方平均数和算数 平均 数 为 Qmax, Mmax . 故 Q 2 max = ( 移 a ) j p 2 / rj, Mmax = M = ( 移 a ) j p / rj,则 ACONCmax(Ck,Aj) - ACONC(Ck,Aj) = 2rj rj - 1 [Q 2 max - M 2 max) - (Q 2 - M 2 )] = 2 rj [ ( - 1 移 a ) j t 2 - ( 移 a ) j t 2 / rj - 移 (a j t) 2 + ( 移 a ) j t 2 / rj ] = 2 rj [ ( - 1 移 a ) j t 2 - 移 (a j t) ] 2 = 4 rj ( - 1 移 r j-1 s = 1 移 r j t = s+1 a j s 伊 a ) j t 逸0 故 ACONCmax(Ck, Aj)逸ACONC(Ck, Aj),即类 Ck中所有数据对象取值相同时,ACONC 取最大值. 证明完毕. 定义 3:基于属性值集中度的类内相似度(simi鄄 larity based on concentration of attribute values, CONC). 将 ACONC 标准化处理后得到 CONC,令 CONC(Ck, Aj)表示类 Ck在属性 Aj上的相似度. 在 综合考虑特征属性值个数 ns(Ck, Aj)和类中数据对 象个数比重后,定义类的类内相似度 CONC(Ck),则 CONC(Ck,Aj) = ACONC(Ck,Aj) ACONCmax(Ck,Aj) = r 2 j 伊 Q(Ck,Aj) 2 - | Ck | 2 (rj - 1) 伊 | Ck | 2 (12) CONC(Ck) = | Ck | | X |·m 移 m j = 1 CONC(Ck,Aj) ns(Ck,Aj) (13) CONC 在衡量每个类的类内相似度时,统筹考 ·686·

傅立伟等：基于属性值集中度的分类数据聚类有效性内部评价指标 ·687· 虑数据集各属性上的所有属性值，充分利用了整个2.4聚类内部评价指标CVC 数据集的信息，反映了类C中各属性值的集中 CONC体现了类中各属性值的集成程度，从而 程度 衡量类内各数据对象的相似度，DCRP依托SV的差 2.3类间差异度DCRP 异衡量类间的差异度.基于CONC和DCRP,构建基 特征属性值体现了类的主要信息，因此对于数 于属性值集中度的内部评价指标(clustering valida- 据集X任意两个类，类间差异度主要体现在两个类 tion based on concentration of attribute values,CVC). 在各特征属性值的差异程度，即强度向量SV的差 令Sim(π)为各个类的类内相似度，dis(π)为类间 异程度. 差异度，w为一个整数参数则 定义4：基于强度向量差异的类间差异度(ds- CVC(r)=Sim(π)×dis(π) (16) similarity based on discrepancy of SVs,DCRP).DCRP 通过两个类特征属性值的差异衡量两个类的类间差 Sim(r)=台 coxc(C) (17) 异度.令DCRPA,(C,C,)为类C和类C,在属性A,上 ne lo 的差异度，DCRP(C,C,)表示类C,和类C,的差异 2"2芝DCRP(C,C,) 度，两个类的强度向量分别为SV(C,A)=(,, dis(π）=白e1 nc×(nc-1) (18) …,小，…，)和SV(C,A)=(,,…,,…, 其中，当类内相似度Sim(π)或类间差异度dis(π) ),则 越大，即CVC越大时，聚类效果越好 DCRP,(C,,C,)= (14) 3示例及特性 n=1 3.1CONC及DCRP示例及特性 DCRP(C.,C,)= ∑DCRP,(C,C,)(I5) 假设C1、C2、C3、C4、C5、C6为6个一维分类数据 其中，I3-|为s与sm差的绝对值.通过对比不 子集，属性均记为A,属性的可取值分别用J、K、L、 同类的强度向量差异，DCRP聚焦两个类特征属性 M、N、O、P标识.各子集的属性分布向量DV见表 值，选择性地忽略了其他属性值的影响，从而有效避 1,其中C,、C,来自同一个数据集，C,∩C2=0.数据 免了噪音的影响 对象分布图见图2. 表16个子集的DV向量表 Table 1 Distribution vector for six subsets 子集 属性取值 C C2 C3 Ca Cs Cs 5 3 6 6 14 140 K 8 5 5 1 10 L 1 3 5 5 1 10 M 10 N 0 10 0 1 10 P 1 10 域值个数 4 7 7 数据对象个数 公 15 之 21 20 200 ACONC 23.17 16.5 11.4 0.5 48.29 4828.57 ACONC- 112.5 112.5 176.4 220.5 114.29 11428.57 属性的CONC 0.2059 0.1467 0.0646 0.0023 0.4225 0.4225 各子集的强度向量为SV(C1,A1)=(0.33, 0),SV(C6,A1)=(0.70,0,0,0,0,0,0).以子集C1 0.53,0,0),SV(C2,A1)=(0,0.53,0,0),SV(C3, 为例计算CONC,以C,和C,为例，计算DCRP如下： A1)=(0.29,0.24,0.24,0.24,0),SV(C4,A1)= ACONC(C,A) (0.29,0,0,0,0),SV(C5,A1)=(0.70,0,0,0,0,0, CONC(C,)=CONC(C)=ACONC(C)=

傅立伟等: 基于属性值集中度的分类数据聚类有效性内部评价指标 虑数据集各属性上的所有属性值,充分利用了整个 数据集的信息, 反映了类 Ck 中各属性值的集中 程度. 2郾 3 类间差异度 DCRP 特征属性值体现了类的主要信息,因此对于数 据集 X 任意两个类,类间差异度主要体现在两个类 在各特征属性值的差异程度,即强度向量 SV 的差 异程度. 定义 4:基于强度向量差异的类间差异度( dis鄄 similarity based on discrepancy of SVs,DCRP). DCRP 通过两个类特征属性值的差异衡量两个类的类间差 异度. 令DCRPAj (Cs,Ct)为类 Cs和类 Ct在属性 Aj上 的差异度,DCRP(Cs, Ct) 表示类 Cs和类 Ct 的差异 度,两个类的强度向量分别为 SV(Cs,Aj) = (s j 1s,s j 2s, …,s j ps,…,s j r j s ) 和 SV( Ct,Aj ) = ( s j 1t,s j 2t,…,s j pt,…, s j r j t),则 DCRPAj (Cs,Ct) = 移 r j p = 1 |s j ps - s j pt | (14) DCRP(Cs,Ct) = 移 m j = 1 DCRPAj (Cs,Ct) (15) 其中, |s j ps - s j pt | 为 sps与 spt差的绝对值. 通过对比不 同类的强度向量差异,DCRP 聚焦两个类特征属性 值,选择性地忽略了其他属性值的影响,从而有效避 免了噪音的影响. 2郾 4 聚类内部评价指标 CVC CONC 体现了类中各属性值的集成程度,从而 衡量类内各数据对象的相似度,DCRP 依托 SV 的差 异衡量类间的差异度. 基于 CONC 和 DCRP,构建基 于属性值集中度的内部评价指标( clustering valida鄄 tion based on concentration of attribute values,CVC). 令 Sim(仔)为各个类的类内相似度,dis(仔) 为类间 差异度,棕 为一个整数参数则 CVC(仔) = Sim(仔) 伊 dis(仔) (16) Sim(仔) = 移 nc k = 1 CONC(Ck) nc 1 / 棕 (17) dis(仔) = 2 移 nc - 1 s = 1 移 nc t = s + 1 DCRP(Cs,Ct) nc 伊 (nc - 1) (18) 其中,当类内相似度 Sim(仔)或类间差异度 dis(仔) 越大,即 CVC 越大时,聚类效果越好. 3 示例及特性 3郾 1 CONC 及 DCRP 示例及特性 假设 C1 、C2 、C3 、C4 、C5 、C6为 6 个一维分类数据 子集,属性均记为 A1 ,属性的可取值分别用 J、K、L、 M、N、O、P 标识. 各子集的属性分布向量 DV 见表 1,其中 C1 、C2来自同一个数据集,C1疑C2 = 芰. 数据 对象分布图见图 2. 表 1 6 个子集的 DV 向量表 Table 1 Distribution vector for six subsets 属性取值 子集 C1 C2 C3 C4 C5 C6 J 5 2 6 6 14 140 K 8 8 5 5 1 10 L 1 3 5 5 1 10 M 1 2 5 5 1 10 N 0 1 10 O 1 10 P 1 10 域值个数 4 4 5 4 7 7 数据对象个数 15 15 21 21 20 200 ACONC 23郾 17 16郾 5 11郾 4 0郾 5 48郾 29 4828郾 57 ACONCmax 112郾 5 112郾 5 176郾 4 220郾 5 114郾 29 11428郾 57 属性的 CONC 0郾 2059 0郾 1467 0郾 0646 0郾 0023 0郾 4225 0郾 4225 各子集的强度向量为 SV( C1 , A1 ) = (0郾 33, 0郾 53,0,0),SV(C2 , A1 ) = (0,0郾 53,0,0),SV(C3 , A1 ) = (0郾 29,0郾 24,0郾 24,0郾 24,0),SV( C4 , A1 ) = (0郾 29,0,0,0,0),SV(C5 , A1 ) = (0郾 70,0,0,0,0,0, 0),SV(C6 , A1 ) = (0郾 70,0,0,0,0,0,0). 以子集 C1 为例计算 CONC,以 C1和 C2为例,计算 DCRP 如下: CONC(C1 ) = CONC(C1 ,A1 ) = ACONC(C1 ,A1 ) ACONCmax(C1 ,A1 ) = ·687·

.688· 工程科学学报，第41卷，第5期 (a) (b) M 2 4 6 2 4 6 2 数据对象个数 数据对象个数 数据对象个数 d (e) ) M 01 0 N N■ M M■ 恒K L K K 2 10 50 100 150 数据对象个数 数据对象个数 数据对象个数 图2子集的属性值分布图.(a)子集C,的属性值分布图；(b)子集C2的属性值分布图：()子集C,的属性值分布图：(d)子集C,的属 性值分布图：（©）子集C,的属性值分布图：()子集C,的属性值分布图 Fig.2 Distribution of attribute values for six subsets:(a)distribution of subset C(b)distribution of subset C2(e)distribution of subset C (d)distribution of subset C(e)distribution of subset Cs;(f)distribution of subset C 2×4 [52+82+12+12 5+8+1+1 别，但其所属数据集的可取值个数不同，C,的属性域 4-1 4 4 有5个属性值：C的属性域有4个属性值.由图2 2×4 152+02+02+02 15+0+0+0 4-1× (c)和图2(d)可得，C,中的数据对象分布在全部可 4 4 取值上，而C,中各数据对象集中在5个可取值中的 0.2059, 4个属性值上，因此C,中各数据对象分布相对于C4 DCRP(C ,C2)=DCRPA,(CI,C2)= 更加集中，即从集中程度的角度判断，C3中各数据对 10.33-01+10.53-0.531+ 象的相似度更高.k-modes算法由于没有考虑到原 10-01+10-01=0.33. 数据集的全部信息，得到两子集的所有对象到类中 对比子集C,和C2,由于来自同一数据集，子集 心差异度和均为15，未识别出两子集的差异.但此 C,和C,在该属性上域是相同的.由图2(a)图2(b) 时CONC(C3,A,)>CONC(C4,A,),CONC更真实 可以看出C,中各属性值分布比C,更集中，且CONC 的反映了两个子集的不同.CONC可以综合考虑子 (C1,A,)>C0NC(C2,A1).但在k-modes算法中， 集所处的数据集本身的结构，即CONC在衡量类内 两数据集的各对象到类中心差异度和均为7，由于 相似性时不局限与类本身的信息，而是综合考虑了 此时判断类中的差异度时只衡量各数据对象和类中 整个数据集的全部信息.同理，对于CU指标，两个 心的差异度，故不能区分子集C,和C,的类内相似 子集P(A=IC)的计算结果也全部相同：对于 度.CONC不仅考虑到属性取值为K的数据对象， CDCS指标，两个子集的intra(π)值同为10.2857； 还综合考虑到其他取值.此外，由强度向量SV可以 对于E指标，两子集的E指标取值同为1.3734. 发现，子集C,中除了有8个数据对象取值为K,取 因此，F指标、CU指标、CDCS指标和E指标在评价 值为J的5个对象由于比例较高，不应被忽略.取 过程中未考虑整体数据集信息，在一定程度影响了 值为L和M的数据对象由于数量明显较低，在计算 评价效果 DCRP时不予考虑，从而消除了噪音影响.同理，对 对比子集C,和C6,由表1可知C6在所有属性值 于CDCS指标，两子集的intra(π)值同为34.1333； 上的数据对象同C,相比扩大了10倍.由图2(e)和 CU指标、CDCS指标、IE指标可以区分此情况.因 图2(d)可以发现，C,和C。的各属性值的集中程度相 此，F指标和CDCS指标受类中心影响很大，在一定 同.对于k-modes算法，两子集中各对象到类中心差 程度影响了评价效果 异度和分别为6和60，但此时CONC(C5,A,)= 对比子集C,和C4,由表1可知两子集本身无差 CONC(C6,A).此外，两子集的强度向量也相同.因

工程科学学报,第 41 卷,第 5 期 图 2 子集的属性值分布图. (a) 子集 C1的属性值分布图; (b) 子集 C2的属性值分布图; (c) 子集 C3的属性值分布图; (d) 子集 C4的属 性值分布图; (e) 子集 C5的属性值分布图; (f) 子集 C6的属性值分布图 Fig. 2 Distribution of attribute values for six subsets: (a) distribution of subset C1 ; (b) distribution of subset C2 ; ( c) distribution of subset C3 ; (d) distribution of subset C4 ;(e) distribution of subset C5 ; (f) distribution of subset C6 2 伊 4 4 - 1 伊 [ 5 2 + 8 2 + 1 2 + 1 2 4 - ( 5 + 8 + 1 + 1 ) 4 ] 2 2 伊 4 4 - 1 伊 [ 15 2 + 0 2 + 0 2 + 0 2 4 - ( 15 + 0 + 0 + 0 ) 4 ] 2 = 0郾 2059, DCRP(C1 ,C2 ) = DCRPAj (C1 ,C2 ) = |0郾 33 - 0 | + |0郾 53 - 0郾 53 | + |0 - 0 | + |0 - 0 | = 0郾 33. 对比子集 C1和 C2 ,由于来自同一数据集,子集 C1和 C2在该属性上域是相同的. 由图 2(a)图 2(b) 可以看出 C1中各属性值分布比 C2更集中,且 CONC (C1 , A1 ) > CONC(C2 , A1 ). 但在 k鄄modes 算法中, 两数据集的各对象到类中心差异度和均为 7,由于 此时判断类中的差异度时只衡量各数据对象和类中 心的差异度,故不能区分子集 C1 和 C2 的类内相似 度. CONC 不仅考虑到属性取值为 K 的数据对象, 还综合考虑到其他取值. 此外,由强度向量 SV 可以 发现,子集 C1中除了有 8 个数据对象取值为 K,取 值为 J 的 5 个对象由于比例较高,不应被忽略. 取 值为 L 和 M 的数据对象由于数量明显较低,在计算 DCRP 时不予考虑,从而消除了噪音影响. 同理,对 于 CDCS 指标,两子集的 intra(仔)值同为 34郾 1333; CU 指标、CDCS 指标、IE 指标可以区分此情况. 因 此,F 指标和 CDCS 指标受类中心影响很大,在一定 程度影响了评价效果. 对比子集 C3和 C4 ,由表 1 可知两子集本身无差 别,但其所属数据集的可取值个数不同,C3的属性域 有 5 个属性值;C4 的属性域有 4 个属性值. 由图 2 (c)和图 2(d)可得,C4中的数据对象分布在全部可 取值上,而 C3中各数据对象集中在 5 个可取值中的 4 个属性值上,因此 C3中各数据对象分布相对于 C4 更加集中,即从集中程度的角度判断,C3中各数据对 象的相似度更高. k鄄modes 算法由于没有考虑到原 数据集的全部信息,得到两子集的所有对象到类中 心差异度和均为 15,未识别出两子集的差异. 但此 时 CONC(C3 , A1 ) > CONC(C4 , A1 ),CONC 更真实 的反映了两个子集的不同. CONC 可以综合考虑子 集所处的数据集本身的结构,即 CONC 在衡量类内 相似性时不局限与类本身的信息,而是综合考虑了 整个数据集的全部信息. 同理,对于 CU 指标,两个 子集 P( Aj = v j p | Ck) 的计算结果也全部相同;对于 CDCS 指标,两个子集的 intra(仔) 值同为 10郾 2857; 对于 IE 指标,两子集的 IE 指标取值同为 1郾 3734. 因此,F 指标、CU 指标、CDCS 指标和 IE 指标在评价 过程中未考虑整体数据集信息,在一定程度影响了 评价效果. 对比子集 C5和 C6 ,由表 1 可知 C6在所有属性值 上的数据对象同 C5相比扩大了 10 倍. 由图 2(e)和 图 2(d)可以发现,C5和 C6的各属性值的集中程度相 同. 对于 k鄄modes 算法,两子集中各对象到类中心差 异度和分别为 6 和 60,但此时 CONC (C5 , A1 ) = CONC(C6 , A1 ). 此外,两子集的强度向量也相同. 因 ·688·

傅立伟等：基于属性值集中度的分类数据聚类有效性内部评价指标 .689· 此数据量等比例扩大时，CONC和DCRP不变，即 综上，根据各指标公式、本节示例以及大量实验 CONC和DCRP在一定程度上消除了类内数据对象 结果得到指标特性，见表2. 个数的影响.同理，对于CU指标，两个子集P(A= 3.2CVC示例 ,IC)的计算结果也全部相同：对于CDCS指标，两 假设一个拥有60个数据对象的2维分类数据 子集的intra(π)值分别为0.2857和2.8571：对于E 集X存在一个划分π={C1,C2},两个属性的可取 指标，两子集的E指标取值同为1.148. 值分别为K1、LM,和K2L2、M2、N2,详见表3 表2聚类内部有效性评价指标特征 Table 2 Characteristics of intemal clustering validation indices 指标特征 指标 考虑整体分布 受类中心影响 受类个数影响 数据规模影响 其他特性 CVC指标 是 否 本 否 可消除噪音影响 CU指标 否 否 冲 否 未考虑类间分离度 CDCS指标 香 冷 8 是 不能消除噪音影响 E指标 否 体 是 本 无法应对均匀效应：未考虑类间分离度 F指标 否 是 思 不能消除噪音影响：未考虑类间分离度 表3数据集X中的2个类的DV向量表 Table 3 Distribution vector for two clusters of X 4 实验及结果分析 属性A 属性A2 4.1实验设计及结果 壁 取值个数 戟 取值个数 本文从加州大学欧文分校提出的用于机器学 K 3 K 10 L 5 L 1 习的数据库(UCI machine learning repository,UCI) M 12 M2 6 中选取Small Soybean、Chess和Mushroom作为实验 N2 3 数据集，采用基于熵优化后的k-modes算法[2]对 K 30 K2 3 数据进行聚类.针对每次聚类结果，分别计算CU、 L > 20 CDCS、E和CVC等内部指标及外部指标NMI,其 M, 3 M N2 15 中CVC参数w区间为[1,8].为消除算法的随机 性影响，采用多次实验的平均值作为实验结果.实 令参数w=4,则CVC(π)=Sim(π)×dis(T)= 验数据及参数设置如表4，实验结果见表5、表6和 0.1675+0.1974×2×2.185 =0.6705 表7. 迈 表4实验数据集及实验参数设置 Table 4 Datasets and parameters for experiments 数据集 对象个数 维度数 原始类个数 缺失值 聚类算法参数范围 CVC参数范围 Small Soybean 47 5 No 2~10 1~8 Chess 3196 36 No 2~20 1~8 Mushroom 8124 21 Yes 2~20 1-8 4.2指标参数对实验结果的影响分析 聚类结果的集合，max(result)和min(result)分别为 为研究CVC中参数对指标的影响，将CVC结 result中的最大值和最小值，Indexom为标准化后的 果及NM结果按照式(19)进行标准化后得到各指 实验结果 标随类个数变化的趋势图，见图3. 如图3(a)所示，对于数据集Small Soybean,当 Index-min(result) ω≥2时，CVC总体趋势相同，且与外部评价指标 IndexNorm max(result)-min(result) (19) NMI保持良好的一致性，最大值及局部最大值一致， 其中，Index表示待处理实验结果，result不同条件下 参数w最佳取值为3或4.如图3(b)所示，对于数

傅立伟等: 基于属性值集中度的分类数据聚类有效性内部评价指标 此数据量等比例扩大时,CONC 和 DCRP 不变,即 CONC 和 DCRP 在一定程度上消除了类内数据对象 个数的影响. 同理,对于 CU 指标,两个子集 P(Aj = v j p |Ck)的计算结果也全部相同;对于 CDCS 指标,两 子集的 intra(仔)值分别为 0郾 2857 和 2郾 8571;对于 IE 指标,两子集的 IE 指标取值同为 1郾 148. 综上,根据各指标公式、本节示例以及大量实验 结果得到指标特性,见表 2. 3郾 2 CVC 示例 假设一个拥有 60 个数据对象的 2 维分类数据 集 X 存在一个划分 仔 = {C1 ,C2 },两个属性的可取 值分别为 K1 、L1 、M1和 K2 、L2 、M2 、N2 ,详见表 3. 表 2 聚类内部有效性评价指标特征 Table 2 Characteristics of internal clustering validation indices 指标 指标特征 考虑整体分布 受类中心影响 受类个数影响 数据规模影响 其他特性 CVC 指标 是 否 否 否 可消除噪音影响 CU 指标 否 否 否 否 未考虑类间分离度 CDCS 指标 否 是 是 是 不能消除噪音影响 IE 指标 否 否 是 否 无法应对均匀效应;未考虑类间分离度 F 指标 否 是 是 不能消除噪音影响;未考虑类间分离度 表 3 数据集 X 中的 2 个类的 DV 向量表 Table 3 Distribution vector for two clusters of X 类 属性 A1 属性 A2 域 取值个数 域 取值个数 K1 3 K2 10 C1 L1 5 L2 1 M1 12 M2 6 N2 3 K1 30 K2 3 C2 L1 7 L2 20 M1 3 M2 2 N2 15 令参数 棕 =4, 则 CVC(仔) = Sim(仔) 伊 dis(仔) = 0郾 1675 + 0郾 1974 4 2 伊 2 伊 2郾 185 2 = 0郾 6705. 4 实验及结果分析 4郾 1 实验设计及结果 本文从加州大学欧文分校提出的用于机器学 习的数据库(UCI machine learning repository,UCI) 中选取 Small Soybean、Chess 和 Mushroom 作为实验 数据集,采用基于熵优化后的 k鄄modes 算法[22] 对 数据进行聚类. 针对每次聚类结果,分别计算 CU、 CDCS、IE 和 CVC 等内部指标及外部指标 NMI,其 中 CVC 参数 棕 区间为[1, 8] . 为消除算法的随机 性影响,采用多次实验的平均值作为实验结果. 实 验数据及参数设置如表 4,实验结果见表 5、表 6 和 表 7. 表 4 实验数据集及实验参数设置 Table 4 Datasets and parameters for experiments 数据集 对象个数 维度数 原始类个数 缺失值 聚类算法参数范围 CVC 参数范围 Small Soybean 47 35 4 No 2 ~ 10 1 ~ 8 Chess 3196 36 2 No 2 ~ 20 1 ~ 8 Mushroom 8124 21 2 Yes 2 ~ 20 1 ~ 8 4郾 2 指标参数对实验结果的影响分析 为研究 CVC 中参数对指标的影响,将 CVC 结 果及 NMI 结果按照式(19)进行标准化后得到各指 标随类个数变化的趋势图,见图 3. IndexNorm = Index - min(result) max(result) - min(result) (19) 其中,Index 表示待处理实验结果,result 不同条件下 聚类结果的集合,max(result)和 min( result)分别为 result 中的最大值和最小值,IndexNorm为标准化后的 实验结果. 如图 3( a)所示,对于数据集 Small Soybean,当 棕逸2 时,CVC 总体趋势相同,且与外部评价指标 NMI 保持良好的一致性,最大值及局部最大值一致, 参数 棕 最佳取值为 3 或 4. 如图 3(b)所示,对于数 ·689·

.690. 工程科学学报，第41卷，第5期 表5 Small Soybean数据集指标参数实验结果平均值 Table 5 Average of clustering results for dataset Small Soybean with various parameters CVC/10-1 CDCS/ NMI/ 类个数 CU E/10-2 w=1 w=2 w=3 w=4 w=5 仙=6 w=7 w=8 104 10-1 2 1.44962.05012.30122.43802.5240 2.58302.62602.6587 1.38531.6332 24.64962.8077 3 1.2041 2.0856 2.50472.7448 2.8998 3.0079 3.0876 3.1488 1.5081 1.399611.2830 4.7695 4 1.2060 2.4120 3.0389 3.4110 3.6559 3.8288 3.9572 4.0564 1.4370 1.1956 6.2084 7.7629 5 1.1923 2.66623.4864 3.98694.3209 4.5591 4.73724.8753 1.4368 0.9450 2.8487 7.5003 6 0.92932.2764 3.06863.5628 3.8967 4.1365 4.3168 4.45721.2951 0.8182 2.2805 6.3634 7 0.8872 2.3472 3.2464 3.8179 4.2080 4.4900 4.7030 4.8693 1.2176 0.7458 1.6786 4.8953 8 0.7921 2.2404 3.1684 3.7678 4.1807 4.4807 4.7082 4.8863 1.1380 0.6320 1.1927 4.0136 9 0.7221 2.1663 3.12433.7521 4.1878 4.50604.74804.9380 1.07240.6412 0.9919 4.6183 100.69122.1857 3.20813.88674.36104.70894.97425.18301.03000.56660.86014.3090 表6 Chess数据集指标参数实验结果平均值 Table 6 Average of clustering results for dataset Chess with various parameters CVC/10-1 CU/ CDCS/ IE/ NMI/ 类个数 u=1 w=2 w=3 u=4 w=5w=6 u=7 u=8 10-4 108 102 10-2 2 0.54040.76420.8578 0.90880.9409 0.9629 0.9789 0.9911 3.06169.1075 2.5055 0.2903 3 0.5418 0.9385 1.1271 1.2351 1.3049 1.3536 1.3894 1.4170 3.6258 8.3664 1.6218 1.3391 4 0.4359 0.8718 1.0984 1.2330 1.3215 1.3840 1.4304 1.4663 4.2637 3.9811 1.0895 1.6117 5 0.37790.8451 1.1050 1.2636 1.3695 1.44501.5015 1.5452 3.46023.8622 0.8798 1.2910 6 0.35110.8599 1.1592 1.3459 1.4720 1.5626 1.6307 1.6837 3.39153.1607 0.6528 1.8689 0.31730.8395 1.16111.3656 1.5051 1.6060 1.6821 1.7416 3.28042.6272 0.5062 1.6133 8 0.28120.7953 1.1247 1.3375 1.4840 1.5905 1.6713 1.7345 3.0207 2.3623 0.4474 2.2785 9 0.2663 0.7990 1.1523 1.3838 1.5445 1.6619 1.7512 1.8212 2.91941.9676 0.3970 2.3652 10 0.23480.7425 1.0898 1.3204 1.4815 1.5996 1.6898 1.7607 2.72561.7890 0.3700 2.0684 11 0.2214 0.7344 1.0952 1.3374 1.5077 1.6332 1.7292 1.8048 2.5746 1.8519 0.3187 1.6655 12 0.2100 0.7276 1.1009 1.3542 1.5333 1.6658 1.7673 1.8475 2.5005 1.5328 0.2896 2.3751 13 0.20220.7290 1.1179 1.3843 1.5737 1.7142 1.82211.9075 2.39701.3409 0.2637 3.4893 14 0.1871 0.7000 1.0866 1.3539 1.5449 1.6870 1.7964 1.8831 2.2667 1.2827 0.2394 3.0853 15 0.1737 0.6726 1.0563 1.3238 1.5157 1.6589 1.7694 1.8570 2.1884 1.1587 0.2150 2.4495 16 0.16340.6537 1.0377 1.3074 1.5018 1.6472 1.7596 1.8489 2.0798 1.2610 0.2086 1.5850 17 0.15920.6563 1.0523 1.3326 1.5354 1.6874 1.8052 1.8989 2.05240.9038 0.1913 2.1058 18 0.15200.64481.0438 1.32811.5346 1.6898 1.81021.90611.98300.8960 0.1743 3.1087 19 0.1457 0.6349 1.0371 1.3255 1.5358 1.6942 1.8172 1.9153 1.8953 0.7658 0.1625 2.2609 20 0.14380.64311.05961.36001.5798 1.74571.87471.97771.83640.77780.16603.8407 据集Chess,.当w≥3时，CVC总体趋势相同，且与外 据集Mushroom,当w≥3时，CVC总体趋势相同，且 部评价指标NMI保持良好的一致性，局部最大值的 与外部评价指标NMI保持良好的一致性，局部最大 位置基本相同，最大值位置有差异.当ω≥4时，随 值的位置相同，最大值位置有差异.当ω≥4时，随 着类个数增加，CVC指标一致性趋于明显，当类个 着类个数增加，标准化后的CVC指标一致性趋于明 数nc≥14时，指标值趋于重合.当w≥6时，最大值显，当类个数nc≥11时，指标值趋于重合.当w≥5 和局部最大值保持一致.对于Chess数据集，参数w 时，最大值位置不再变化.对于Mushroom数据集， 的最佳取值区间是[5,8].如图3(c)所示，对于数 参数最佳取值为3或4

工程科学学报,第 41 卷,第 5 期 表 5 Small Soybean 数据集指标参数实验结果平均值 Table 5 Average of clustering results for dataset Small Soybean with various parameters 类个数 CVC/ 10 - 1 棕 = 1 棕 = 2 棕 = 3 棕 = 4 棕 = 5 棕 = 6 棕 = 7 棕 = 8 CU CDCS / 10 4 IE / 10 - 2 NMI/ 10 - 1 2 1郾 4496 2郾 0501 2郾 3012 2郾 4380 2郾 5240 2郾 5830 2郾 6260 2郾 6587 1郾 3853 1郾 6332 24郾 6496 2郾 8077 3 1郾 2041 2郾 0856 2郾 5047 2郾 7448 2郾 8998 3郾 0079 3郾 0876 3郾 1488 1郾 5081 1郾 3996 11郾 2830 4郾 7695 4 1郾 2060 2郾 4120 3郾 0389 3郾 4110 3郾 6559 3郾 8288 3郾 9572 4郾 0564 1郾 4370 1郾 1956 6郾 2084 7郾 7629 5 1郾 1923 2郾 6662 3郾 4864 3郾 9869 4郾 3209 4郾 5591 4郾 7372 4郾 8753 1郾 4368 0郾 9450 2郾 8487 7郾 5003 6 0郾 9293 2郾 2764 3郾 0686 3郾 5628 3郾 8967 4郾 1365 4郾 3168 4郾 4572 1郾 2951 0郾 8182 2郾 2805 6郾 3634 7 0郾 8872 2郾 3472 3郾 2464 3郾 8179 4郾 2080 4郾 4900 4郾 7030 4郾 8693 1郾 2176 0郾 7458 1郾 6786 4郾 8953 8 0郾 7921 2郾 2404 3郾 1684 3郾 7678 4郾 1807 4郾 4807 4郾 7082 4郾 8863 1郾 1380 0郾 6320 1郾 1927 4郾 0136 9 0郾 7221 2郾 1663 3郾 1243 3郾 7521 4郾 1878 4郾 5060 4郾 7480 4郾 9380 1郾 0724 0郾 6412 0郾 9919 4郾 6183 10 0郾 6912 2郾 1857 3郾 2081 3郾 8867 4郾 3610 4郾 7089 4郾 9742 5郾 1830 1郾 0300 0郾 5666 0郾 8601 4郾 3090 表 6 Chess 数据集指标参数实验结果平均值 Table 6 Average of clustering results for dataset Chess with various parameters 类个数 CVC/ 10 - 1 棕 = 1 棕 = 2 棕 = 3 棕 = 4 棕 = 5 棕 = 6 棕 = 7 棕 = 8 CU/ 10 - 1 CDCS / 10 8 IE/ 10 - 2 NMI/ 10 - 2 2 0郾 5404 0郾 7642 0郾 8578 0郾 9088 0郾 9409 0郾 9629 0郾 9789 0郾 9911 3郾 0616 9郾 1075 2郾 5055 0郾 2903 3 0郾 5418 0郾 9385 1郾 1271 1郾 2351 1郾 3049 1郾 3536 1郾 3894 1郾 4170 3郾 6258 8郾 3664 1郾 6218 1郾 3391 4 0郾 4359 0郾 8718 1郾 0984 1郾 2330 1郾 3215 1郾 3840 1郾 4304 1郾 4663 4郾 2637 3郾 9811 1郾 0895 1郾 6117 5 0郾 3779 0郾 8451 1郾 1050 1郾 2636 1郾 3695 1郾 4450 1郾 5015 1郾 5452 3郾 4602 3郾 8622 0郾 8798 1郾 2910 6 0郾 3511 0郾 8599 1郾 1592 1郾 3459 1郾 4720 1郾 5626 1郾 6307 1郾 6837 3郾 3915 3郾 1607 0郾 6528 1郾 8689 7 0郾 3173 0郾 8395 1郾 1611 1郾 3656 1郾 5051 1郾 6060 1郾 6821 1郾 7416 3郾 2804 2郾 6272 0郾 5062 1郾 6133 8 0郾 2812 0郾 7953 1郾 1247 1郾 3375 1郾 4840 1郾 5905 1郾 6713 1郾 7345 3郾 0207 2郾 3623 0郾 4474 2郾 2785 9 0郾 2663 0郾 7990 1郾 1523 1郾 3838 1郾 5445 1郾 6619 1郾 7512 1郾 8212 2郾 9194 1郾 9676 0郾 3970 2郾 3652 10 0郾 2348 0郾 7425 1郾 0898 1郾 3204 1郾 4815 1郾 5996 1郾 6898 1郾 7607 2郾 7256 1郾 7890 0郾 3700 2郾 0684 11 0郾 2214 0郾 7344 1郾 0952 1郾 3374 1郾 5077 1郾 6332 1郾 7292 1郾 8048 2郾 5746 1郾 8519 0郾 3187 1郾 6655 12 0郾 2100 0郾 7276 1郾 1009 1郾 3542 1郾 5333 1郾 6658 1郾 7673 1郾 8475 2郾 5005 1郾 5328 0郾 2896 2郾 3751 13 0郾 2022 0郾 7290 1郾 1179 1郾 3843 1郾 5737 1郾 7142 1郾 8221 1郾 9075 2郾 3970 1郾 3409 0郾 2637 3郾 4893 14 0郾 1871 0郾 7000 1郾 0866 1郾 3539 1郾 5449 1郾 6870 1郾 7964 1郾 8831 2郾 2667 1郾 2827 0郾 2394 3郾 0853 15 0郾 1737 0郾 6726 1郾 0563 1郾 3238 1郾 5157 1郾 6589 1郾 7694 1郾 8570 2郾 1884 1郾 1587 0郾 2150 2郾 4495 16 0郾 1634 0郾 6537 1郾 0377 1郾 3074 1郾 5018 1郾 6472 1郾 7596 1郾 8489 2郾 0798 1郾 2610 0郾 2086 1郾 5850 17 0郾 1592 0郾 6563 1郾 0523 1郾 3326 1郾 5354 1郾 6874 1郾 8052 1郾 8989 2郾 0524 0郾 9038 0郾 1913 2郾 1058 18 0郾 1520 0郾 6448 1郾 0438 1郾 3281 1郾 5346 1郾 6898 1郾 8102 1郾 9061 1郾 9830 0郾 8960 0郾 1743 3郾 1087 19 0郾 1457 0郾 6349 1郾 0371 1郾 3255 1郾 5358 1郾 6942 1郾 8172 1郾 9153 1郾 8953 0郾 7658 0郾 1625 2郾 2609 20 0郾 1438 0郾 6431 1郾 0596 1郾 3600 1郾 5798 1郾 7457 1郾 8747 1郾 9777 1郾 8364 0郾 7778 0郾 1660 3郾 8407 据集 Chess,当 棕逸3 时,CVC 总体趋势相同,且与外 部评价指标 NMI 保持良好的一致性,局部最大值的 位置基本相同,最大值位置有差异. 当 棕逸4 时,随 着类个数增加, CVC 指标一致性趋于明显,当类个 数 nc逸14 时,指标值趋于重合. 当 棕逸6 时,最大值 和局部最大值保持一致. 对于 Chess 数据集,参数 棕 的最佳取值区间是[5,8]. 如图 3(c)所示,对于数 据集 Mushroom,当 棕逸3 时,CVC 总体趋势相同,且 与外部评价指标 NMI 保持良好的一致性,局部最大 值的位置相同,最大值位置有差异. 当 棕逸4 时,随 着类个数增加,标准化后的 CVC 指标一致性趋于明 显,当类个数 nc逸11 时,指标值趋于重合. 当 棕逸5 时,最大值位置不再变化. 对于 Mushroom 数据集, 参数最佳取值为 3 或 4. ·690·

傅立伟等：基于属性值集中度的分类数据聚类有效性内部评价指标 ·691· 表7 Mushroom数据集指标参数实验结果平均值 Table 7 Average of clustering results for dataset Mushroom with various parameters CVC/10-1 CU/ CDCS/ IE/ NMI/ 类个数 w=1 w=2 =3 w=4 w=5 =6 =7 =8 10-1 109 10-1 10-1 2 1.130 1.598 1.7931.8999 1.967 2.013 2.0462.072 5.5295 5.4395 7.2900 1.513 3 1.066 1.847 2.218 2.4306 2.568 2.664 2.734 2.788 8.3726 2.9593 4.3948 1.568 4 0.852 1.704 2.147 2.4094 2.582 2.704 2.795 2.865 7.5823 3.3869 3.1450 0.462 5 0.847 1.895 2.477 2.8330 3.070 3.240 3.366 3.464 8.1918 1.8485 2.2165 2.307 6 0.726 1.779 2.397 2.7836 3.044 3.232 3.373 3.482 7.5752 1.7727 1.8483 2.100 7 0.640 1.692 2.341 2.7526 3.034 3.237 3.391 3.511 7.2510 1.0476 1.4268 2.145 8 0.596 1.685 2.383 2.7980 3.144 3.370 3.541 3.675 6.6447 1.1869 1.2363 1.374 9 0.519 1.556 2.244 2.6950 3.008 3.237 3.410 3.547 6.1161 0.9955 1.0594 0.964 10 0.480 1.517 2.227 2.6975 3.027 3.268 3.452 3.597 5.6701 0.8328 0.9542 1.708 11 0.437 1.450 2.162 2.6405 2.977 3.225 3.414 3.563 5.3697 0.5910 0.8196 1.634 12 0.414 1.436 2.172 2.6723 3.026 3.287 3.487 3.646 5.0980 0.4543 0.7651 1.190 0.406 1.465 2.247 2.7823 3.163 3.445 3.662 3.834 5.0402 0.4729 0.6505 1.547 14 0.381 1.424 2.211 2.7545 3.143 3.432 3.655 3.831 4.7980 0.3362 0.5851 1.135 15 0.354 1.369 2.150 2.6946 3.085 3.377 3.602 3.780 4.4620 0.3761 0.5321 1.276 16 0.343 1.373 2.179 2.7450 3.153 3.458 3.695 3.882 4.2832 0.2973 0.4927 1.077 17 0.335 1.381 2.215 2.8051 3.232 3.552 3.800 3.997 4.3443 0.1894 0.4490 1.681 18 0.3111.320 2.137 2.7188 3.142 3.459 3.706 3.902 3.9230 0.3621 0.4277 1.584 19 0.309 1.347 2.200 2.8112 3.257 3.593 3.854 4.062 4.0827 0.1911 0.3681 1.429 20 0.287 1.285 2.118 2.7185 3.158 3.489 3.747 3.953 3.7305 0.1268 0.3684 1.715 1.0g 1.0g 0.8 0.8 Q 0.6 0.6 0.4 0.4 0.2 8-0 2 6 10 20 类个数 类个数 (a) (b) 1.0g R 08 0.6 0.4 0.2 S-ap.be-k 10 15 类个数 -NMI-G CVC(@=1)-bCVC(@=2)CVC(@=3)-CVC(@=4)*CVC(@=5)--CVC(@=6)-+CVC(@=7)--CVC(@=8) 图3CVC随参数变化实验结果.(a)数据集Small Soybean结果：(b)数据集Chess结果；(c)数据集Mushroom结果 Fig.3 Results of CVC with parameters:(a)results of dataset Small Soybean;(b)results of dataset Chess;(c)results of dataset Mushroom

傅立伟等: 基于属性值集中度的分类数据聚类有效性内部评价指标 表 7 Mushroom 数据集指标参数实验结果平均值 Table 7 Average of clustering results for dataset Mushroom with various parameters 类个数 CVC/ 10 - 1 棕 = 1 棕 = 2 棕 = 3 棕 = 4 棕 = 5 棕 = 6 棕 = 7 棕 = 8 CU/ 10 - 1 CDCS / 10 9 IE/ 10 - 1 NMI/ 10 - 1 2 1郾 130 1郾 598 1郾 793 1郾 8999 1郾 967 2郾 013 2郾 046 2郾 072 5郾 5295 5郾 4395 7郾 2900 1郾 513 3 1郾 066 1郾 847 2郾 218 2郾 4306 2郾 568 2郾 664 2郾 734 2郾 788 8郾 3726 2郾 9593 4郾 3948 1郾 568 4 0郾 852 1郾 704 2郾 147 2郾 4094 2郾 582 2郾 704 2郾 795 2郾 865 7郾 5823 3郾 3869 3郾 1450 0郾 462 5 0郾 847 1郾 895 2郾 477 2郾 8330 3郾 070 3郾 240 3郾 366 3郾 464 8郾 1918 1郾 8485 2郾 2165 2郾 307 6 0郾 726 1郾 779 2郾 397 2郾 7836 3郾 044 3郾 232 3郾 373 3郾 482 7郾 5752 1郾 7727 1郾 8483 2郾 100 7 0郾 640 1郾 692 2郾 341 2郾 7526 3郾 034 3郾 237 3郾 391 3郾 511 7郾 2510 1郾 0476 1郾 4268 2郾 145 8 0郾 596 1郾 685 2郾 383 2郾 7980 3郾 144 3郾 370 3郾 541 3郾 675 6郾 6447 1郾 1869 1郾 2363 1郾 374 9 0郾 519 1郾 556 2郾 244 2郾 6950 3郾 008 3郾 237 3郾 410 3郾 547 6郾 1161 0郾 9955 1郾 0594 0郾 964 10 0郾 480 1郾 517 2郾 227 2郾 6975 3郾 027 3郾 268 3郾 452 3郾 597 5郾 6701 0郾 8328 0郾 9542 1郾 708 11 0郾 437 1郾 450 2郾 162 2郾 6405 2郾 977 3郾 225 3郾 414 3郾 563 5郾 3697 0郾 5910 0郾 8196 1郾 634 12 0郾 414 1郾 436 2郾 172 2郾 6723 3郾 026 3郾 287 3郾 487 3郾 646 5郾 0980 0郾 4543 0郾 7651 1郾 190 13 0郾 406 1郾 465 2郾 247 2郾 7823 3郾 163 3郾 445 3郾 662 3郾 834 5郾 0402 0郾 4729 0郾 6505 1郾 547 14 0郾 381 1郾 424 2郾 211 2郾 7545 3郾 143 3郾 432 3郾 655 3郾 831 4郾 7980 0郾 3362 0郾 5851 1郾 135 15 0郾 354 1郾 369 2郾 150 2郾 6946 3郾 085 3郾 377 3郾 602 3郾 780 4郾 4620 0郾 3761 0郾 5321 1郾 276 16 0郾 343 1郾 373 2郾 179 2郾 7450 3郾 153 3郾 458 3郾 695 3郾 882 4郾 2832 0郾 2973 0郾 4927 1郾 077 17 0郾 335 1郾 381 2郾 215 2郾 8051 3郾 232 3郾 552 3郾 800 3郾 997 4郾 3443 0郾 1894 0郾 4490 1郾 681 18 0郾 311 1郾 320 2郾 137 2郾 7188 3郾 142 3郾 459 3郾 706 3郾 902 3郾 9230 0郾 3621 0郾 4277 1郾 584 19 0郾 309 1郾 347 2郾 200 2郾 8112 3郾 257 3郾 593 3郾 854 4郾 062 4郾 0827 0郾 1911 0郾 3681 1郾 429 20 0郾 287 1郾 285 2郾 118 2郾 7185 3郾 158 3郾 489 3郾 747 3郾 953 3郾 7305 0郾 1268 0郾 3684 1郾 715 图 3 CVC 随参数变化实验结果. (a) 数据集 Small Soybean 结果; (b) 数据集 Chess 结果; (c) 数据集 Mushroom 结果 Fig. 3 Results of CVC with parameters: (a) results of dataset Small Soybean; (b) results of dataset Chess; (c) results of dataset Mushroom ·691·