武森等：基于近邻的不均衡数据聚类算法 1215 28 688 30 26 Cluster 2 25 25 94 24 20 449 15 10 16 5 (a) (c) 1 0 0 0 5 10 15 0 510152025 303540 0 10 2030 4050 Attribute I Attribute 1 Attribute】 20 20 20 10 0 0 5 0 0 -10 -20 5 -20 -10 -30 (d) Cluster 2 ( -15 -30 (e) -40 10 0 10 15 -20 -10 0 10 20 15 -10 10 15 Attribute 1 Attribute 1 Attribute 1 图6人工数据集真实分布.(a)Flame:(b)Aggregation:(c)Jain:(d)DS1:(e)DS2:(f)DS3 Fig.6 True distribution of synthetic data sets:(a)Flame;(b)Aggregation;(c)Jain;(d)DS1;(e)DS2;(f)DS3 结果都将(，x)判定为不同类别的数据对的数目； 01为步长确定一个最优取值区间后，缩短步长为 h表示聚类结果认为同类，但真实结果认为不同类 0.01,在此区间内再次选择一个最优值作为此数据 的数据对的数目；g表示聚类结果认为不同类，但 集的类别待定集构造阈值 真实结果认为同类的数据对的数目 3.4实验结果 3.3实验设计 (1)人工数据集实验结果 实验将CABON算法与K-means、MC IK和 表2~表5给出了CABON、K-means、MCIK和 CVCNUS算法进行对比.K-means算法是经典的 CVCN算法对人工数据集的聚类结果.从表2 聚类算法，作为对比算法可比较不同算法降低“均 表5中可以看出，CABON算法在大多数情况下明显 匀效应”影响的程度：MCIK和CVCN算法分别从 优于其他三种算法，这在一定程度上说明CABON 多中心和优化目标函数的角度有效降低了不均衡 算法能够消减K-means算法产生的“均匀效应” 数据聚类中“均匀效应”问题的影响.对比实验通 对于Flame、Aggregation数据集，CABON的各个指 过将CABON算法和这些算法进行对比，以衡量 标值均优于对比算法，但是CABON在处理Jain数 CABON算法处理不均衡数据聚类问题降低“均匀 据集时的F-measure、NMl值略低于CVCN算法， 效应”影响的能力.在设定实验参数方面，参数 其原因在于Jain为非球形不均衡数据集，CABON k是输入的聚类个数，可参考实验数据集类的数量 对部分此类数据集中的数据对象聚类时无法准确 设定.6为构造类别待定集事先设定的参数，取值 表2人工数据集不同算法聚类结果(Accuracy指标) 范围根据数据集的大小而确定.在本实验中，若数 Table 2 Clustering results of artificial data set with different 据集较小，阈值6的取值范围设定为0.5~1.5，以 algorithms(Accuracy indicators) 0.5为初始值、0.1为步长确定一个最优取值区间， Index Datasets CABON K-means MC IK CVCN 表现为阈值δ在此区间内时聚类评价指标值最 Flame 0.985 0.8292 0.82420.8583 高；最优取值区间确定后，缩短步长为0.01，在此 Aggregation 0.9505 0.9156 0.93640.9010 区间内选择一个最优值作为此数据集的类别待定 Jain 0.8801 0.7819 0.7943 0.8729 Accuracy 集构造阈值，表现为阈值δ取到此参数值时聚类 DSI 0.9817 0.8628 0.8724 0.866 评价指标值最高.同样地，若数据集较大，阈值 DS2 0.9852 0.8422 0.8640 0.8765 DS3 0.9917 0.9032 0.92120.6687 δ的取值范围设定为1.0~2.0，以1.0为初始值、(xi 结果都将 , x j) 判定为不同类别的数据对的数目； h 表示聚类结果认为同类，但真实结果认为不同类 的数据对的数目；g 表示聚类结果认为不同类，但 真实结果认为同类的数据对的数目. 3.3    实验设计 实验将 CABON 算法与 K–means、MC_IK[14] 和 CVCN[15] 算法进行对比. K–means 算法是经典的 聚类算法，作为对比算法可比较不同算法降低“均 匀效应”影响的程度；MC_IK 和 CVCN 算法分别从 多中心和优化目标函数的角度有效降低了不均衡 数据聚类中“均匀效应”问题的影响. 对比实验通 过将 CABON 算法和这些算法进行对比，以衡量 CABON 算法处理不均衡数据聚类问题降低“均匀 效应”影响的能力. 在设定实验参数方面，参数 k 是输入的聚类个数，可参考实验数据集类的数量 设定. δ 为构造类别待定集事先设定的参数，取值 范围根据数据集的大小而确定. 在本实验中，若数 据集较小，阈值 δ 的取值范围设定为 0.5～1.5，以 0.5 为初始值、0.1 为步长确定一个最优取值区间， 表现为阈值 δ 在此区间内时聚类评价指标值最 高；最优取值区间确定后，缩短步长为 0.01，在此 区间内选择一个最优值作为此数据集的类别待定 集构造阈值，表现为阈值 δ 取到此参数值时聚类 评价指标值最高. 同样地，若数据集较大，阈值 δ 的取值范围设定为 1.0～2.0，以 1.0 为初始值、 0.1 为步长确定一个最优取值区间后，缩短步长为 0.01，在此区间内再次选择一个最优值作为此数据 集的类别待定集构造阈值. 3.4    实验结果 （1）人工数据集实验结果. 表2～表5 给出了CABON、K–means、MC_IK 和 CVCN 算法对人工数据集的聚类结果. 从表 2～ 表 5 中可以看出，CABON 算法在大多数情况下明显 优于其他三种算法，这在一定程度上说明 CABON 算法能够消减 K–means 算法产生的“均匀效应”. 对于 Flame、Aggregation 数据集，CABON 的各个指 标值均优于对比算法，但是 CABON 在处理 Jain 数 据集时的 F-measure、NMI 值略低于 CVCN 算法， 其原因在于 Jain 为非球形不均衡数据集，CABON 对部分此类数据集中的数据对象聚类时无法准确 28 0 26 24 Attribute 1 (a) Attribute 2 22 5 20 10 18 15 16 14 20 −10 15 −5 10 0 Attribute 1 (d) Attribute 2 5 5 0 10 −5 15 −10 −15 20 −20 −10 10 0 Attribute 1 (e) Attribute 2 0 10 −10 20 −20 −30 20 −15 −10 −5 10 0 Attribute 1 (f) Attribute 2 0 5 −10 10 −20 15 −30 −40 Cluster 1 Cluster 2 Cluster 1 Cluster 2 (c) Attribute 2 Attribute 1 0 30 25 10 20 15 20 10 5 30 0 40 50 (b) Attribute 2 Attribute 1 0 30 5 25 10 20 15 15 20 10 25 5 30 0 35 40 Cluster 1 Cluster 2 Cluster 3 Cluster 4 Cluster 5 Cluster 6 Cluster 7 Cluster 1 Cluster 2 Cluster 1 Cluster 2 Cluster 1 Cluster 2 Cluster 3 Cluster 4 Cluster 5 图 6    人工数据集真实分布. （a） Flame；（b） Aggregation；（c） Jain；（d） DS1；（e） DS2；（f） DS3 Fig.6    True distribution of synthetic data sets: (a) Flame; (b) Aggregation; (c) Jain; (d) DS1; (e) DS2; (f) DS3 表 2    人工数据集不同算法聚类结果（Accuracy 指标） Table 2    Clustering  results  of  artificial  data  set  with  different algorithms (Accuracy indicators) Index Datasets CABON K–means MC_IK CVCN Accuracy Flame 0.985 0.8292 0.8242 0.8583 Aggregation 0.9505 0.9156 0.9364 0.9010 Jain 0.8801 0.7819 0.7943 0.8729 DS1 0.9817 0.8628 0.8724 0.866 DS2 0.9852 0.8422 0.8640 0.8765 DS3 0.9917 0.9032 0.9212 0.6687 武    森等： 基于近邻的不均衡数据聚类算法 · 1215 ·