武森等：基于近邻的不均衡数据聚类算法 ·1213 30 O Cluster 1 有数据对象已实现了类别的重新划分，得到了最 25 △Cluster2 后的聚类结果 00 。 Centroids 2 CABON算法过程 0 15 CABON算法的输入数据包括数据集X={xI 10 88 △△ 聚类个数参数k、类别待定集界定阈值6，输出数 3 △A 据为数据集X的聚类标签Label..CABON算法具 X △ 体步骤如下： 10 152025 0 3540 Step 1:对数据集X用经典的K-means算法聚 Attribute 1 类，得到初始聚类结果； 图4 CABON算法固定类别待定集的情况示意图 Step2:构造类别待定集.对于任意一个数据 Fig.4 Schematic of the CABON algorithm's fixed of the undetermined- 对象xi=1,2,,n),选择距离最近的两个类X,与X cluster set (s,仁1,2，，k,s≠)，且它们的类中心为c和c,若与 象按照从集合边缘到中心的顺序依次归入其最近 数据对象x的距离符合如下关系： 邻居所在的类别中，实现类别待定集动态调整的 d(xi,cs)-d(xi.c)<6 过程，以避免上述类别待定集固定所导致的数据 则将对象x归入类别待定集心={二m是类 对象类别错分的后果 别待定集中数据对象的数量)：数据集X中别除类 图5展示了类别待定集中数据对象根据CABON 别待定集后的对象构成了类别确定集； 算法所定义的类划分规则实现类划分的过程.首 Step3:查找最近邻居集.根据类别待定集 先，图5(a)在图3(b)构造的类别待定集的基础上， 中数据对象与类别确定集中数据对象的距离大 确定了类别待定集中每一个数据对象在类别确定 小，在类别确定集中选取距离最小的对象集合作 集中的最近邻居；其次，根据二者距离的大小选择 为x的最近邻居集X=(对应类别待定集 距离最小的数据对象作为边界对象，即图5(a)中 中数据对象x在类别确定集中的最近邻居)： 虚线内有颜色填充的对象为此次迭代中的边界对 Step4:确定边界对象.查找到距离最近邻居 象，而虚线外有相同颜色填充的对象为边界对象 x(p=1,2,,m)最小的数据对象xp,确定xp为类别 对应的最近邻居：最后，根据近邻思想将边界对象 待定集的边界对象，将此边界对象x归入其最 归入其最近邻居所在的类中，由此确定边界对象 近邻居x所在的类别中；同时将边界对象x从类别 的类别，进而将边界对象由类别待定集划分到类 待定集x中别除并添加到类别确定集中； 别确定集中（图5(b)).图5展示了类别待定集中 Step5:重复Step3至Step4,直到类别待定集 数据对象类别重新划分的一次迭代过程，经过多 为空集、类别确定集为全集时停止 次迭代后，类别待定集中的数据对象为空，表示所 由CABON算法的具体实现步骤可知CABON 40 40 △Cluster (a) A Cluster (b) 35 OCluster 2 O Cluster 2 口Cluster3 35 ▣Cluster3 30 ◆Cluster4 阳B 品 ◆Cluster4 0始马 Centroids 30 Centroids 品 25 25 个 0 15 15 ǒ9 10 44 A△ △会△ 10 94 A△ △△ 5 A△ X△△ A△ △ 0 0 5 10 15202530 3540 4550 5 10 15202530 35 40 4550 Attribute 1 Attribute 1 图5类别待定集中数据对象类别重新划分过程示意图.(a)边界对象确定过程：(b)类别待定集调整过程 Fig.5 Schematic of the reclassification process of data objects in the undetermined-cluster set:(a)determination of boundary objects;(b)the adjustment process of undetermined-cluster set象按照从集合边缘到中心的顺序依次归入其最近 邻居所在的类别中，实现类别待定集动态调整的 过程，以避免上述类别待定集固定所导致的数据 对象类别错分的后果. 图 5 展示了类别待定集中数据对象根据 CABON 算法所定义的类划分规则实现类划分的过程. 首 先，图 5（a）在图 3（b）构造的类别待定集的基础上， 确定了类别待定集中每一个数据对象在类别确定 集中的最近邻居；其次，根据二者距离的大小选择 距离最小的数据对象作为边界对象，即图 5（a）中 虚线内有颜色填充的对象为此次迭代中的边界对 象，而虚线外有相同颜色填充的对象为边界对象 对应的最近邻居；最后，根据近邻思想将边界对象 归入其最近邻居所在的类中，由此确定边界对象 的类别，进而将边界对象由类别待定集划分到类 别确定集中（图 5（b））. 图 5 展示了类别待定集中 数据对象类别重新划分的一次迭代过程，经过多 次迭代后，类别待定集中的数据对象为空，表示所 有数据对象已实现了类别的重新划分，得到了最 后的聚类结果. 2    CABON 算法过程 X = {xi} n CABON 算法的输入数据包括数据集 i=1、 聚类个数参数 k、类别待定集界定阈值 δ，输出数 据为数据集 X 的聚类标签 Label. CABON 算法具 体步骤如下： Step 1：对数据集 X 用经典的 K–means 算法聚 类，得到初始聚类结果； xi Xs Xt cs ct xi Step 2：构造类别待定集. 对于任意一个数据 对象 (i =1,2,…,n)，选择距离最近的两个类 与 (s, t=1,2,…,k, s≠k)，且它们的类中心为 和 ，若与 数据对象 的距离符合如下关系： |d(xi ,cs)−d(xi ,ct)| < δ xi X 0 = { x 0 i }m 则将对象 归入类别待定集 i=1 (m 是类 别待定集中数据对象的数量)；数据集 X 中剔除类 别待定集后的对象构成了类别确定集； X 0 X 0 X 1 = { x 1 i }m i=1 x 1 i x 0 i Step 3：查找最近邻居集. 根据类别待定集 中数据对象与类别确定集中数据对象的距离大 小，在类别确定集中选取距离最小的对象集合作 为 的最近邻居集 ( 对应类别待定集 中数据对象 在类别确定集中的最近邻居)； x 1 p (p = 1,2,...,m) xp xp X 0 xp x 1 p xp X 0 Step 4：确定边界对象. 查找到距离最近邻居 最小的数据对象 ，确定 为类别 待定集 的边界对象，将此边界对象 归入其最 近邻居 所在的类别中；同时将边界对象 从类别 待定集 中剔除并添加到类别确定集中； X 0 Step 5：重复 Step 3 至 Step 4，直到类别待定集 为空集、类别确定集为全集时停止. 由 CABON 算法的具体实现步骤可知 CABON Attribute 2 Attribute 1 0 30 5 25 10 20 15 15 20 10 25 5 30 0 35 40 x1 x2 x3 Cluster 1 Cluster 2 Centroids 图 4    CABON 算法固定类别待定集的情况示意图 Fig.4    Schematic of the CABON algorithm’s fixed of the undetermined￾cluster set (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 图 5    类别待定集中数据对象类别重新划分过程示意图. （a）边界对象确定过程；（b）类别待定集调整过程 Fig.5    Schematic of the reclassification process of data objects in the undetermined-cluster set: (a) determination of boundary objects; (b) the adjustment process of undetermined-cluster set 武    森等： 基于近邻的不均衡数据聚类算法 · 1213 ·