1212 工程科学学报，第42卷.第9期 2之间发生了“均匀效应”.对于对象，根据 (1)查找类别待定集中每个数据对象在类别确定 MCK算法定义的模糊工作集的构造规则，其与 集中的最近邻居，这些最近邻居数据对象构成一 初次聚类结果中类中心c3、c4的距离差值最小，若 个集合，称之为最近邻居集；(2)依据距离最近邻 此距离差值小于预设阈值可将数据对象：归入模 居距离最小原则，确定类别待定集的边界对象，并 糊工作集.但实际上对象x1与初次聚类结果中最 将边界对象归入其最近邻居所在类别中：(3)将已 近的两个类中心为C1、c2,且距离c1、c2的距离差 经重新划分过类别的边界对象从类别待定集中删 值较大，这种情况下可以把对象x直接归入距离 除，并添加到类别确定集中，动态调整类别待定 最近的类别c2中，不属于模糊工作集.因此， 集；(4)重复第(2)、(3)步，直到类别待定集为空 MCK算法定义的构造规则会导致部分对象被误 在上述规则中可以看出，CABON算法在实现 分到模糊工作集，影响算法的聚类效果 过程中，类别待定集中的对象不是固定不变的，因 因此，在MCK算法定义的模糊工作集的基 为类别待定集固定的思路仍会导致数据对象类别 础上，本文将数据集中所属类别有待进一步核定 错分的情况，利用上述规则中类别待定集的动态 的数据对象构成的集合定义为类别待定集，构造 调整机制可以避免这一情况的发生.如图4所示， 规则为：使用K-means算法对数据对象进行聚类 三角形和圆圈分别代表初始聚类得到的两种类 得到初始聚类结果后，对于任意一个数据对象，若 别，虚线内对象代表已构造好的类别待定集.按照 与初始聚类结果中最近的两个类中心距离差小于 上述类别待定集中数据对象的划分规则，随着类 预设阈值（即类别待定集构造阈值），则将此数据 别待定集的动态调整，对象，应归入大类Cluster1 对象归入类别待定集.图3(a)为用K-means算法 中.若类别待定集是固定的，即虚线内对象在算法 对原始数据对象聚类得到的初始聚类结果，产生 的迭代过程中不发生变化，CABON算法在计算类 了“均匀效应”：图3(b)根据本文定义的构造规则 别待定集中数据对象与类别确定集中数据对象之 确定了类别待定集，虚线内数据对象距离最近的 间的距离时，对象1与对象3的距离略大于对象 两个类中心距离差小于预设阈值6，构成了类别待 1与对象的距离(dx,3)Pdx1,x2),且dx1, 定集.相比于MCIK算法中定义的模糊工作集， )为距离集合里的最小值，因此对象：的最近邻 本文提出的类别待定集构造方法可以有效避免归 居为小类中的对象2，其类别也将与对象x2一致 属类别确定的数据对象被错分到类别模糊不确定 如此一来，类别待定集中原本应归入大类中的对 的集合里的情形，能够准确识别可能被错分的数 象会被错分到小类中.故在此基础上，我们定义类 据对象，为后续数据对象的重新划分打好基础 别待定集和类别确定集是动态变化的：当类别待 1.3类别待定集中数据对象的划分规则 定集中的边界对象类别确定后，将此边界对象从 初始类别待定集构造完成后，为了将该集合 类别待定集中别除并添加至类别确定集中，此对 中数据对象准确地划分到正确的类中，CABON算 象的类别确定后就有可能成为类别待定集其他数 法定义了一种新的类的划分规则.规则描述如下： 据对象的最近邻居.将类别待定集的每一数据对 △Cluster1 P 0 (a) A Cluster 1 (b) 35 O Cluster 2 35 O Cluster 2 ▣Cluster3 0xg马 ▣Cluster3 ◆Cluster4 ◆Cluster4 阳马 30 Centroids 30 Centroids 25 25 099 女 20 20 15 15 o89 0o80 △会△ 10 △△ 0 A△ 0 0 5 1015202530 3540 45 50 0 5 10 15202530 35404550 Attribute 1 Attribute 1 图3类别待定集的构造过程示意图.(a)K-means算法对数据集的初始聚类结果：(b)CABON算法构造类别待定集图示 Fig.3 Schematic of the construction process of the undetermined-cluster set:(a)initial clustering result of the K-means algorithm on data sets;(b) undetermined-cluster set constructed by the CABON algorithm2 之间发生了 “ 均匀效应 ” . 对于对 象 x1， 根 据 MC_IK 算法定义的模糊工作集的构造规则，其与 初次聚类结果中类中心 c3、c4 的距离差值最小，若 此距离差值小于预设阈值可将数据对象 x1 归入模 糊工作集. 但实际上对象 x1 与初次聚类结果中最 近的两个类中心为 c1、c2，且距离 c1、c2 的距离差 值较大，这种情况下可以把对象 x1 直接归入距离 最近的类 别 c2 中 ，不属于模糊工作集 . 因此 ， MC_IK 算法定义的构造规则会导致部分对象被误 分到模糊工作集，影响算法的聚类效果. 因此，在 MC_IK 算法定义的模糊工作集的基 础上，本文将数据集中所属类别有待进一步核定 的数据对象构成的集合定义为类别待定集，构造 规则为：使用 K–means 算法对数据对象进行聚类 得到初始聚类结果后，对于任意一个数据对象，若 与初始聚类结果中最近的两个类中心距离差小于 预设阈值 δ（即类别待定集构造阈值），则将此数据 对象归入类别待定集. 图 3（a）为用 K–means 算法 对原始数据对象聚类得到的初始聚类结果，产生 了“均匀效应”；图 3（b）根据本文定义的构造规则 确定了类别待定集，虚线内数据对象距离最近的 两个类中心距离差小于预设阈值 δ，构成了类别待 定集. 相比于 MC_IK 算法中定义的模糊工作集， 本文提出的类别待定集构造方法可以有效避免归 属类别确定的数据对象被错分到类别模糊不确定 的集合里的情形，能够准确识别可能被错分的数 据对象，为后续数据对象的重新划分打好基础. 1.3    类别待定集中数据对象的划分规则 初始类别待定集构造完成后，为了将该集合 中数据对象准确地划分到正确的类中，CABON 算 法定义了一种新的类的划分规则. 规则描述如下： （1）查找类别待定集中每个数据对象在类别确定 集中的最近邻居，这些最近邻居数据对象构成一 个集合，称之为最近邻居集；（2）依据距离最近邻 居距离最小原则，确定类别待定集的边界对象，并 将边界对象归入其最近邻居所在类别中；（3）将已 经重新划分过类别的边界对象从类别待定集中删 除，并添加到类别确定集中，动态调整类别待定 集；（4）重复第（2）、（3）步，直到类别待定集为空. 在上述规则中可以看出，CABON 算法在实现 过程中，类别待定集中的对象不是固定不变的，因 为类别待定集固定的思路仍会导致数据对象类别 错分的情况，利用上述规则中类别待定集的动态 调整机制可以避免这一情况的发生. 如图 4 所示， 三角形和圆圈分别代表初始聚类得到的两种类 别，虚线内对象代表已构造好的类别待定集. 按照 上述类别待定集中数据对象的划分规则，随着类 别待定集的动态调整，对象 x1 应归入大类 Cluster1 中. 若类别待定集是固定的，即虚线内对象在算法 的迭代过程中不发生变化，CABON 算法在计算类 别待定集中数据对象与类别确定集中数据对象之 间的距离时，对象 x1 与对象 x3 的距离略大于对象 x1 与 对 象 x2 的 距 离 (d(x1 , x3 )>d(x1 , x2 ))， 且 d(x1 , x2 ) 为距离集合里的最小值，因此对象 x1 的最近邻 居为小类中的对象 x2，其类别也将与对象 x2 一致. 如此一来，类别待定集中原本应归入大类中的对 象会被错分到小类中. 故在此基础上，我们定义类 别待定集和类别确定集是动态变化的：当类别待 定集中的边界对象类别确定后，将此边界对象从 类别待定集中剔除并添加至类别确定集中，此对 象的类别确定后就有可能成为类别待定集其他数 据对象的最近邻居. 将类别待定集的每一数据对 (a) Attribute 2 Attribute 1 35 0 30 40 5 25 10 20 15 15 20 10 25 5 30 0 35 40 45 50 Cluster 1 Cluster 2 Cluster 3 Cluster 4 Centroids (b) Attribute 2 Attribute 1 35 0 30 40 5 25 10 20 15 15 20 10 25 5 30 0 35 40 45 50 Cluster 1 Cluster 2 Cluster 3 Cluster 4 Centroids 图 3    类别待定集的构造过程示意图. （a）K–means 算法对数据集的初始聚类结果；（b）CABON 算法构造类别待定集图示 Fig.3     Schematic  of  the  construction  process  of  the  undetermined-cluster  set:  (a)  initial  clustering  result  of  the  K-means  algorithm  on  data  sets;  (b) undetermined-cluster set constructed by the CABON algorithm · 1212 · 工程科学学报，第 42 卷，第 9 期