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