傅立伟等：基于属性值集中度的分类数据聚类有效性内部评价指标 ·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·