.1214 工程科学学报，第42卷，第9期 算法具有两个显著特点：(1)从计算数据对象与其 上界均为1，指标值越接近1，聚类效果越好 最近的两个类中心距离差的角度，提出了类别待 设k为聚类个数，N为数据集中数据对象的个 定集的构造方法，弥补已有研究构造模糊工作集 数，P={P1,P2,P为数据集的实际类分布，C= 时部分对象被误分这一不足；(2)基于近邻思想， (C1,C2,Ck为数据集的聚类结果，=C:nP伪 为类别待定集中对象重新定义一种新的类的划分 C,和P的共同部分的基数，则聚类精度(Accuracy) 规则.利用类别待定集对象的最近邻居作为确定 的公式如(1)所示： 其类别的参照依据，可以更精确地划分类别待定 I k 集对象所归属的类别，并且CABON算法中类别待 Accuracy N乙mx (1) 定集的动态调整机制大大降低了对象归属类别错 分的概率，从而保证聚类结果的质量 F-measure的计算公式如(2)所示： F-measure= (1+B2).Recall.Precision 3实验分析 (2) B2.Recall+Precision 3.1实验数据 其中：Recall和Precision分别表示数据集中真实聚 为了验证CABON算法解决K-means“均匀效 类结果与聚类结果相比的召回率和准确率；B表 应”问题的有效性，实验分别在6个人工数据集和 示Recall和Precision的相对重要性，通常设为1. 4个UCI(University of California Irvine)真实数据集 NMI的计算公式如(3)所示： 上进行，详细信息见表1，编号1~6为人工数据集 ln(N)/mnj)》 具体信息，真实分布如图6所示，其中编号1~3描 述的是测试聚类常用的Flamel9、Aggregation2o、 NMI= (3) Jain2数据集，编号4~6描述的是Python合成的 3个数据集，分别为DS1、DS2、DS3.另外，表1编 号7~10为真实数据集的具体信息，实验采用了 其中：N为数据集的数据对象数量，n:为属于类的 加州大学欧文分校提出的UCI标准数据库中的 数据对象数量；n为属于类的数据对象数量：为 Wine2a、Newthyroid!、Ionospherel2和Heart这 真实数据集中类与聚类结果类相一致的数据对 4个数据集. 象数量；R、K分别对应真实数据集和聚类结果类 3.2评价指标 中的类个数 为了评估CABON算法及对比算法的聚类效 RI的计算公式如(4)所示： 果，本文引入了4个评价指标，分别是聚类精度 RI= a+b (Accuracy)2a、F值(F-measure)图、标准化互信息 a+b+h+8 (4) Normalized mutual information,NMI)5.27.281 其中：α表示被聚类结果和真实结果判定为同一类 德指数(Rand index,RI)2930,4个评价指标的取值 别的数据对(，x)的数目；b表示聚类结果和真实 表1数据集参数信息 Table 1 Parameter information for the data set No Datasets Data Sources Distribution Dimension Class Instance Flame Synthesis 147:93 2 2 240 2 Aggregation Synthesis 272:170:127:105:45:35:34 2 7 788 3 Jain Synthesis 276:97 2 2 373 4 DSI Synthesis 1000:200 2 2 1200 5 DS2 Synthesis 2823:529 2 2 3352 6 DS3 Synthesis 1000:500:400:200:200 2 5 2300 7 Wine UCI 59:71:48 13 3 178 8 Newthyroid UCI 150:35:30 5 3 215 9 Ionosphere UCI 225:126 2 351 10 Heart UCI 150:120 13 2 270算法具有两个显著特点：（1）从计算数据对象与其 最近的两个类中心距离差的角度，提出了类别待 定集的构造方法，弥补已有研究构造模糊工作集 时部分对象被误分这一不足；（2）基于近邻思想， 为类别待定集中对象重新定义一种新的类的划分 规则. 利用类别待定集对象的最近邻居作为确定 其类别的参照依据，可以更精确地划分类别待定 集对象所归属的类别，并且 CABON 算法中类别待 定集的动态调整机制大大降低了对象归属类别错 分的概率，从而保证聚类结果的质量. 3    实验分析 3.1    实验数据 为了验证 CABON 算法解决 K–means“均匀效 应”问题的有效性，实验分别在 6 个人工数据集和 4 个 UCI（University of California Irvine）真实数据集 上进行，详细信息见表 1，编号 1～6 为人工数据集 具体信息，真实分布如图 6 所示，其中编号 1～3 描 述的是测试聚类常用的 Flame[19]、 Aggregation[20]、 Jain[21] 数据集，编号 4～6 描述的是 Python 合成的 3 个数据集，分别为 DS1、DS2、DS3. 另外，表 1 编 号 7～10 为真实数据集的具体信息，实验采用了 加州大学欧文分校提出的 UCI 标准数据库中的 Wine[22]、 Newthyroid[23]、 Ionosphere[24] 和 Heart[25] 这 4 个数据集. 3.2    评价指标 为了评估 CABON 算法及对比算法的聚类效 果，本文引入了 4 个评价指标，分别是聚类精度 （Accuracy） [26]、F 值（F-measure） [8]、标准化互信息 （ Normalized mutual information， NMI） [15, 27, 28] 和 兰 德指数（Rand index，RI） [29−30] ，4 个评价指标的取值 上界均为 1，指标值越接近 1，聚类效果越好. P = {P1, P2,...Pk} C = {C1,C2,...,Ck} ni j = |Ci ∩ Pj | Ci Pj 设 k 为聚类个数，N 为数据集中数据对象的个 数 ， 为数据集的实际类分布 ， 为数据集的聚类结果， 为 和 的共同部分的基数，则聚类精度（Accuracy） 的公式如（1）所示： Accuracy = 1 N ∑ k i=1 k max j=1 ni j （1） F-measure 的计算公式如（2）所示： F−measure = (1+β 2 )·Recall·Precision β 2 ·Recall+Precision （2） 其中：Recall 和 Precision 分别表示数据集中真实聚 类结果与聚类结果相比的召回率和准确率；β 表 示 Recall 和 Precision 的相对重要性，通常设为 1. NMI 的计算公式如（3）所示： NMI = ∑ R i=1 ∑ K j=1 ni j ln((N · ni j)/(ni · nj)) vut∑ R i=1 ni ln( ni N ) · ∑ K j=1 nj ln( nj N ) （3） ni i nj j ni j i j 其中：N 为数据集的数据对象数量， 为属于类 的 数据对象数量； 为属于类 的数据对象数量； 为 真实数据集中类 与聚类结果类 相一致的数据对 象数量；R、K 分别对应真实数据集和聚类结果类 中的类个数. RI 的计算公式如（4）所示： RI = a+b a+b+h+g （4） (xi , x j) 其中：a 表示被聚类结果和真实结果判定为同一类 别的数据对 的数目；b 表示聚类结果和真实 表 1 数据集参数信息 Table 1 Parameter information for the data set No Datasets Data Sources Distribution Dimension Class Instance 1 Flame Synthesis 147∶93 2 2 240 2 Aggregation Synthesis 272∶170∶127∶105∶45∶35∶34 2 7 788 3 Jain Synthesis 276∶97 2 2 373 4 DS1 Synthesis 1000∶200 2 2 1200 5 DS2 Synthesis 2823∶529 2 2 3352 6 DS3 Synthesis 1000∶500∶400∶200∶200 2 5 2300 7 Wine UCI 59∶71∶48 13 3 178 8 Newthyroid UCI 150∶35∶30 5 3 215 9 Ionosphere UCI 225∶126 34 2 351 10 Heart UCI 150∶120 13 2 270 · 1214 · 工程科学学报，第 42 卷，第 9 期