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

工程科学学报，第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·