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