工程科学学报.第42卷，第9期：1209-1219.2020年9月 Chinese Journal of Engineering,Vol.42,No.9:1209-1219,September 2020 https://doi.org/10.13374/j.issn2095-9389.2019.10.09.003;http://cje.ustb.edu.cn 基于近邻的不均衡数据聚类算法 武森，汪玉枝，高晓楠⑧ 北京科技大学经济管理学院.北京100083 ☒通信作者，E-mail:gaoxiaonan(0001@163.com 摘要针对经典K-meas算法对不均衡数据进行聚类时产生的“均匀效应”问题，提出一种基于近邻的不均衡数据聚类算 法(Clustering algorithm for imbalanced data based on nearest neighbor,.CABON).CABON算法首先对数据对象进行初始聚类，通 过定义的类别待定集来确定初始聚类结果中类别归属有待进一步核定的数据对象集合：并给出一种类别待定集的动态调整 机制.利用近邻思想实现此集合中数据对象所属类别的重新划分，按照从集合边缘到中心的顺序将类别待定集中的数据对象 依次归入其最近邻居所在的类别中，得到最终的聚类结果.以避免“均匀效应”对聚类结果的影响.将该算法与K-meas、多 中心的非平衡K均值聚类方法(Imbalanced K-means clustering method with multiple centers,MCIK)和非均匀数据的变异 系数聚类算法(Coefficient of variation clustering for non--uniform data,CVCN)在人工数据集和真实数据集上分别进行实验对比， 结果表明CABON算法能够有效消减K-means算法对不均衡数据聚类时所产生的“均匀效应”，聚类效果明显优于 K-means、MC_IK和CVCN算法 关键词K-means;均匀效应：类别待定集：近邻：基于近邻的不均衡数据聚类算法 分类号TP311.13 Clustering algorithm for imbalanced data based on nearest neighbor WU Sen,WANG Yu-zhi,GAO Xiao-nan School of Economics and Management,University of Science and Technology Beijing.Beijing 100083.China Corresponding author,E-mail:gaoxiaonan0001@163.com ABSTRACT Clustering is an important task in the field of data mining.Most clustering algorithms can effectively deal with the clustering problems of balanced datasets,but their processing ability is weak for imbalanced datasets.For example,K-means,a classical partition clustering algorithm,tends to produce a"uniform effect"when dealing with imbalanced datasets,i.e.,the K-means algorithm often produces clusters that are relatively uniform in size when clustering unbalanced datasets with the data objects in small clusters "swallowing"the part of the data objects in large clusters.This means that the number and density of the data objects in different clusters tend to be the same.To solve the problem of "uniform effect"generated by the classical K-means algorithm in the clustering of imbalanced data,a clustering algorithm based on nearest neighbor (CABON)is proposed for imbalanced data.Firstly,the initial clustering of data objects is performed to obtain the undetermined-cluster set,which is defined as a set that consists of the data objects that must be checked further regarding the clusters in which they belong.Then,from the edge to the center of the set,the nearest- neighbor method is used to reassign the data objects in the undetermined-cluster set to the clusters of their nearest neighbors.Meanwhile the undetermined-cluster set is dynamically adjusted,to obtain the final clustering result,which prevents the influence of the "uniform effect"on the clustering result.The clustering results of the proposed algorithm is compared with that of K-means,the imbalanced K-means clustering method with multiple centers(MC_IK),and the coefficient of variation clustering for non-uniform data(CVCN)on synthetic and real datasets.The experimental results reveal that the CABON algorithm effectively reduces "uniform effect"generated by 收稿日期：2019-10-09 基金项目：国家自然科学基金资助项目(71971025,71271027)
基于近邻的不均衡数据聚类算法 武 森，汪玉枝，高晓楠苣 北京科技大学经济管理学院，北京 100083 苣通信作者，E-mail: gaoxiaonan0001@163.com 摘 要 针对经典 K–means 算法对不均衡数据进行聚类时产生的“均匀效应”问题，提出一种基于近邻的不均衡数据聚类算 法（Clustering algorithm for imbalanced data based on nearest neighbor，CABON）. CABON 算法首先对数据对象进行初始聚类，通 过定义的类别待定集来确定初始聚类结果中类别归属有待进一步核定的数据对象集合；并给出一种类别待定集的动态调整 机制，利用近邻思想实现此集合中数据对象所属类别的重新划分，按照从集合边缘到中心的顺序将类别待定集中的数据对象 依次归入其最近邻居所在的类别中，得到最终的聚类结果，以避免“均匀效应”对聚类结果的影响. 将该算法与 K–means、多 中心的非平衡 K_均值聚类方法（Imbalanced K–means clustering method with multiple centers，MC_IK）和非均匀数据的变异 系数聚类算法（Coefficient of variation clustering for non-uniform data，CVCN）在人工数据集和真实数据集上分别进行实验对比， 结果表明 CABON 算法能够有效消减 K –means 算法对不均衡数据聚类时所产生的“均匀效应” ，聚类效果明显优于 K–means、MC_IK 和 CVCN 算法. 关键词 K–means；均匀效应；类别待定集；近邻；基于近邻的不均衡数据聚类算法 分类号 TP311.13 Clustering algorithm for imbalanced data based on nearest neighbor WU Sen，WANG Yu-zhi，GAO Xiao-nan苣 School of Economics and Management, University of Science and Technology Beijing, Beijing 100083, China 苣 Corresponding author, E-mail: gaoxiaonan0001@163.com ABSTRACT Clustering is an important task in the field of data mining. Most clustering algorithms can effectively deal with the clustering problems of balanced datasets, but their processing ability is weak for imbalanced datasets. For example, K–means, a classical partition clustering algorithm, tends to produce a “uniform effect” when dealing with imbalanced datasets, i.e., the K–means algorithm often produces clusters that are relatively uniform in size when clustering unbalanced datasets with the data objects in small clusters “swallowing” the part of the data objects in large clusters. This means that the number and density of the data objects in different clusters tend to be the same. To solve the problem of “uniform effect” generated by the classical K–means algorithm in the clustering of imbalanced data, a clustering algorithm based on nearest neighbor (CABON) is proposed for imbalanced data. Firstly, the initial clustering of data objects is performed to obtain the undetermined-cluster set, which is defined as a set that consists of the data objects that must be checked further regarding the clusters in which they belong. Then, from the edge to the center of the set, the nearestneighbor method is used to reassign the data objects in the undetermined-cluster set to the clusters of their nearest neighbors. Meanwhile the undetermined-cluster set is dynamically adjusted, to obtain the final clustering result, which prevents the influence of the “uniform effect” on the clustering result. The clustering results of the proposed algorithm is compared with that of K –means, the imbalanced K–means clustering method with multiple centers (MC_IK), and the coefficient of variation clustering for non-uniform data (CVCN) on synthetic and real datasets. The experimental results reveal that the CABON algorithm effectively reduces “uniform effect” generated by 收稿日期: 2019−10−09 基金项目: 国家自然科学基金资助项目（71971025, 71271027） 工程科学学报，第 42 卷，第 9 期：1209−1219，2020 年 9 月 Chinese Journal of Engineering, Vol. 42, No. 9: 1209−1219, September 2020 https://doi.org/10.13374/j.issn2095-9389.2019.10.09.003; http://cje.ustb.edu.cn
·1210 工程科学学报，第42卷，第9期 the K-means algorithm on imbalanced data,and its clustering result is superior to that of the K-means,MC IK,and CVCN algorithms. KEY WORDS K-means;uniform effect;undetermined-cluster set;neighbor:clustering algorithm for imbalanced data based on nearest neighbor(CABON) 聚类分析是数据挖掘领域最为常见的技术之一， 法的有效性降低.第三类方法是优化目标函数的 用于发现数据集中未知的对象类四聚类分析在客 方法，此类方法从目标函数优化的角度提出新的 户细分)、模式识别阗、医疗决策、异常检测阿等 算法，通过推导出相应的聚类优化目标函数，以解 诸多领域有着广泛的应用前景.传统的聚类算法 决“均匀效应”问题，如杨天鹏通过优化数据离散 能够很好地处理均衡数据的聚类问题，但是现实 程度进而优化目标函数，提出了一种基于变异系 生活中存在许多不均衡数据，例如医疗诊断阿、故 数的聚类算法(CVCN)阿这类方法从目标函数直 障诊断)等领域的数据中表现正常的数据量要远 接切入，相比于之前的聚类算法是一种较为直接 远大于表现异常的数据量，这类不均衡数据集的 的新方法且有一定的实用性，但是此类方法一般 特点是同一数据集中归属于某一类别的数据对象 涉及目标函数参数的求解，属于非线性函数优化 的数量和密度与其他类别数据对象的数量和密度 问题，难以得到全局最优解，这决定了该类算法的 有较大差异，通常数据对象数量较多的类称之为 聚类结果具有相对较大的随机性，影响算法的聚 大类，数据对象数量较少的类称之为小类.对于不 类精度 均衡数据的聚类问题，传统的聚类算法处理能力 针对上述问题，本文借助近邻思想，提出基于 较弱.以著名的K-means算法为例，K-means算 近邻的不均衡数据聚类算法(CABON).首先运用 法是经典的划分式聚类算法，在处理不均衡数据 K-means算法对数据对象进行初始聚类，针对聚 集时，容易出现“均匀效应”图，即聚类时往往会产 类结果中部分数据对象类别可能划分错误的问 生相对均匀尺寸的类，小类中的数据对象会“吞 题，从数据对象与其最近的两个类中心距离差值 掉”大类中的部分数据对象，造成聚类结果中不同 的计算出发，给出了类别待定集的定义及构造规 类的数据对象数量和密度趋于一致. 则，用以确定初始聚类结果中类别归属有待进一 为解决不均衡数据的聚类问题，研究者从不 步核定的数据对象集合.其次针对类别待定集中 同角度提出了多种方法，大致可以分成以下三类： 数据对象所属类别的重新划分问题，提出了一种 (1)数据预处理21：(2)多中心点-：(3)优化目 新的类的划分规则，通过查找类别待定集中每个 标函数6第一类方法是数据预处理，此类方法 数据对象的最近邻居，借助近邻思想，将类别待定 对数据集进行欠采样和过采样处理后再进行聚 集的数据对象按照从集合边缘到中心的顺序依次 类，但是欠采样方法仅仅采用了属于大类中的一 归入其最近邻居所在的类别中，能够将初次聚类 部分具有代表性的子集，导致大类中大量的有效 结果中类别错分的数据对象校正回正确的类，并 信息被忽略，影响了聚类效果；过采样方法通过 且定义了一种类别待定集的动态调整机制，提高 增加小类中对象数量来进行数据分析，使原有数 数据对象类别划分的准确率，从而进一步消减K-means 据集达到均衡状态，但是这样做一方面可能导致 算法的“均匀效应”，得到最终的聚类结果 过拟合，另一方面也可能给数据集带来噪声.第二 1相关概念与规则 类方法是多中心点的方法，此类方法基于多中心 的角度解决K-means的“均匀效应”问题，其思想 1.1K-means算法的“均匀效应” 是用多个类中心代替单个类中心代表一个类，在 K-means算法是划分式聚类的经典算法，在 某些情况下，借助该思想，K-means算法在迭代过 K-means算法迭代过程中，采用一个类中所有对 程中根据距离“中心”最近的原则，能够让部分被 象的平均值作为该类新的中心，然后根据距离“中 错分到小类中的数据对象校正回大类中.如亓慧 心”最近原则，重新确定所有对象的类别，这会导 提出了一种多中心的不均衡K均值聚类方法 致K-means算法在处理不均衡数据集时，出现部 (MCK),具有一定的有效性和可行性.但此类 分数据对象与多个类中心距离相近的情况，从而 方法对于一些大类分布极其不均匀的不均衡数据 导致这部分的数据对象归属类别被错分.文献[8] 聚类问题，不能全面地反映数据分布特征，导致算 介绍了K-means算法的“均匀效应”，即K-means
the K–means algorithm on imbalanced data, and its clustering result is superior to that of the K–means, MC_IK, and CVCN algorithms. KEY WORDS K –means； uniform effect； undetermined-cluster set； neighbor； clustering algorithm for imbalanced data based on nearest neighbor (CABON) 聚类分析是数据挖掘领域最为常见的技术之一， 用于发现数据集中未知的对象类[1] . 聚类分析在客 户细分[2]、模式识别[3]、医疗决策[4]、异常检测[5] 等 诸多领域有着广泛的应用前景. 传统的聚类算法 能够很好地处理均衡数据的聚类问题，但是现实 生活中存在许多不均衡数据，例如医疗诊断[6]、故 障诊断[7] 等领域的数据中表现正常的数据量要远 远大于表现异常的数据量. 这类不均衡数据集的 特点是同一数据集中归属于某一类别的数据对象 的数量和密度与其他类别数据对象的数量和密度 有较大差异，通常数据对象数量较多的类称之为 大类，数据对象数量较少的类称之为小类. 对于不 均衡数据的聚类问题，传统的聚类算法处理能力 较弱. 以著名的 K–means 算法为例，K–means 算 法是经典的划分式聚类算法，在处理不均衡数据 集时，容易出现“均匀效应” [8] ，即聚类时往往会产 生相对均匀尺寸的类，小类中的数据对象会“吞 掉”大类中的部分数据对象，造成聚类结果中不同 类的数据对象数量和密度趋于一致. 为解决不均衡数据的聚类问题，研究者从不 同角度提出了多种方法，大致可以分成以下三类： （1）数据预处理[9−12] ；（2）多中心点[13−14] ；（3）优化目 标函数[15−16] . 第一类方法是数据预处理，此类方法 对数据集进行欠采样和过采样处理后再进行聚 类，但是欠采样方法仅仅采用了属于大类中的一 部分具有代表性的子集，导致大类中大量的有效 信息被忽略，影响了聚类效果[17] ；过采样方法通过 增加小类中对象数量来进行数据分析，使原有数 据集达到均衡状态，但是这样做一方面可能导致 过拟合，另一方面也可能给数据集带来噪声. 第二 类方法是多中心点的方法，此类方法基于多中心 的角度解决 K–means 的“均匀效应”问题，其思想 是用多个类中心代替单个类中心代表一个类，在 某些情况下，借助该思想，K–means 算法在迭代过 程中根据距离“中心”最近的原则，能够让部分被 错分到小类中的数据对象校正回大类中. 如亓慧 提出了一种多中心的不均 衡 K_均值聚类方 法 (MC_IK)[14] ，具有一定的有效性和可行性. 但此类 方法对于一些大类分布极其不均匀的不均衡数据 聚类问题，不能全面地反映数据分布特征，导致算 法的有效性降低. 第三类方法是优化目标函数的 方法，此类方法从目标函数优化的角度提出新的 算法，通过推导出相应的聚类优化目标函数，以解 决“均匀效应”问题. 如杨天鹏通过优化数据离散 程度进而优化目标函数，提出了一种基于变异系 数的聚类算法（CVCN） [15] . 这类方法从目标函数直 接切入，相比于之前的聚类算法是一种较为直接 的新方法且有一定的实用性，但是此类方法一般 涉及目标函数参数的求解，属于非线性函数优化 问题，难以得到全局最优解，这决定了该类算法的 聚类结果具有相对较大的随机性，影响算法的聚 类精度. 针对上述问题，本文借助近邻思想，提出基于 近邻的不均衡数据聚类算法（CABON）. 首先运用 K–means 算法对数据对象进行初始聚类，针对聚 类结果中部分数据对象类别可能划分错误的问 题，从数据对象与其最近的两个类中心距离差值 的计算出发，给出了类别待定集的定义及构造规 则，用以确定初始聚类结果中类别归属有待进一 步核定的数据对象集合. 其次针对类别待定集中 数据对象所属类别的重新划分问题，提出了一种 新的类的划分规则，通过查找类别待定集中每个 数据对象的最近邻居，借助近邻思想，将类别待定 集的数据对象按照从集合边缘到中心的顺序依次 归入其最近邻居所在的类别中，能够将初次聚类 结果中类别错分的数据对象校正回正确的类，并 且定义了一种类别待定集的动态调整机制，提高 数据对象类别划分的准确率，从而进一步消减K–means 算法的“均匀效应”，得到最终的聚类结果. 1 相关概念与规则 1.1 K–means 算法的“均匀效应” K–means 算法是划分式聚类的经典算法，在 K–means 算法迭代过程中，采用一个类中所有对 象的平均值作为该类新的中心，然后根据距离“中 心”最近原则，重新确定所有对象的类别，这会导 致 K–means 算法在处理不均衡数据集时，出现部 分数据对象与多个类中心距离相近的情况，从而 导致这部分的数据对象归属类别被错分. 文献 [8] 介绍了 K–means 算法的“均匀效应”，即 K–means · 1210 · 工程科学学报，第 42 卷，第 9 期
武森等：基于近邻的不均衡数据聚类算法 ·1211 习惯于将大类中的部分对象划分到小类中，从而 据对象进行聚类，得到初始聚类结果.由于传统的 使获得的类拥有相对均匀的尺度.如图1(a)所示， K-means算法不能很好地处理不均衡数据的聚类 展示了一个由Python人工合成的二维不均衡数据 问题，因此在初始聚类结果中会造成部分数据对象 集的真实分布，两个类的数据对象的数量和密度 在算法迭代过程中与多个类中心距离都较为相近， 有较大差别：图1(b)为K-means算法对图1(a)中 以至于无法准确确定其类别，出现类别错分的情况. 数据集的聚类结果，可以看到，聚类后小类“吞掉”了 基于此，本文定义了一种构造规则来确定类别待定 大类中的部分数据对象，使得两个类的数据对象的 集，并进一步提出一种新的类的划分规则实现对 数量和密度趋于相近，此为K-means算法所产生 类别待定集中数据对象的重新划分，得到最终聚 的“均匀效应”现象.从类中心的角度来说，因为单 类结果，从而处理不均衡数据的“均匀效应”问题. 个类中心不能充分反映一个大类的特征，导致大类 已有研究MCIK算法提出过一种模糊工作集 中的部分数据对象被划分到小类中l]在K-means 的定义：对于任意一个数据对象，若与初次聚类结 算法迭代过程中，当大类中心与小类中心的距离 果中任意两类或两类以上的类中心距离差小于预 越来越近，大类中的部分对象极易被错分到小类 设阈值，则将此数据对象归入模糊工作集4但 中，最终的聚类结果产生的“均匀效应”就越显著 是，这种构造方法可能将普通数据对象划归到模 1.2类别待定集 糊工作集中，存在模糊工作集构造不精准的缺点， 类别待定集是数据集中所属类别有待进一步 影响算法的聚类效果.如图2(a)所示，三角形、圆 核定的数据对象构成的集合，对应地，数据集中所 圈、正方形和四角星分别代表了四种类别，其类中 属类别确定的数据对象构成的集合称之为类别确 心分别是c1、c2、c3、c4,图2(b)是图2(a)中数据集 定集.在CABON算法中，首先运用K-means对数 的初次聚类结果，可以看到，Cluster1和Cluster 30 20 a (b) 15 15 10 10 5 5 0 A Cluster 1 Cluster 1 口Cluster2 Cluster 2 -5 0 10 15 10 0 5 10 15 Attribute I Attribute】 图1二维不均衡数据集的真实分布和K-means的聚类结果.(a)数据集真实分布：(b)K-means的聚类结果 Fig.1 Real distributions of two-dimensional unbalanced data sets and clustering results of the K-means algorithm:(a)real distribution of datasets,(b)the clustering result of the K-means algorithm (a) b A 35 ◆ 009 % 25 0 3 20 15 A Cluster A Cluster 1 O Cluster 2 10 O Cluster 2 ■luster5 ▣Cluster3 5 ◇Cluster4 Centroids 8 品 51015202530354045505560 0 51015202530354045505560 Attribute 1 Attribute 1 因2MCK算法中模糊工作集构造规则存在缺陷示意图.(a)数据集真实分布：(b)MCIK对数据集初次聚类结果 Fig.2 Schematic diagram of the defects in the construction rules of the MC IK algorithm's fuzzy working set:(a)real distribution of data sets;(b)initial clustering result of the MC IK algorithm on datasets
习惯于将大类中的部分对象划分到小类中，从而 使获得的类拥有相对均匀的尺度. 如图 1（a）所示， 展示了一个由 Python 人工合成的二维不均衡数据 集的真实分布，两个类的数据对象的数量和密度 有较大差别；图 1（b）为 K–means 算法对图 1（a）中 数据集的聚类结果，可以看到，聚类后小类“吞掉”了 大类中的部分数据对象，使得两个类的数据对象的 数量和密度趋于相近，此为 K–means 算法所产生 的“均匀效应”现象. 从类中心的角度来说，因为单 个类中心不能充分反映一个大类的特征，导致大类 中的部分数据对象被划分到小类中[18] . 在 K–means 算法迭代过程中，当大类中心与小类中心的距离 越来越近，大类中的部分对象极易被错分到小类 中，最终的聚类结果产生的“均匀效应”就越显著. 1.2 类别待定集 类别待定集是数据集中所属类别有待进一步 核定的数据对象构成的集合，对应地，数据集中所 属类别确定的数据对象构成的集合称之为类别确 定集. 在 CABON 算法中，首先运用 K–means 对数 据对象进行聚类，得到初始聚类结果. 由于传统的 K–means 算法不能很好地处理不均衡数据的聚类 问题，因此在初始聚类结果中会造成部分数据对象 在算法迭代过程中与多个类中心距离都较为相近， 以至于无法准确确定其类别，出现类别错分的情况. 基于此，本文定义了一种构造规则来确定类别待定 集，并进一步提出一种新的类的划分规则实现对 类别待定集中数据对象的重新划分，得到最终聚 类结果，从而处理不均衡数据的“均匀效应”问题. 已有研究 MC_IK 算法提出过一种模糊工作集 的定义：对于任意一个数据对象，若与初次聚类结 果中任意两类或两类以上的类中心距离差小于预 设阈值，则将此数据对象归入模糊工作集[14] . 但 是，这种构造方法可能将普通数据对象划归到模 糊工作集中，存在模糊工作集构造不精准的缺点， 影响算法的聚类效果. 如图 2（a）所示，三角形、圆 圈、正方形和四角星分别代表了四种类别，其类中 心分别是 c1、c2、c3、c4，图 2（b）是图 2（a）中数据集 的初次聚类结果 ，可以看到 ，Cluster 1 和 Cluster 20 −10 15 −5 10 0 Attribute 1 (a) Attribute 2 5 5 0 10 −5 15 −10 −15 20 −10 15 −5 10 0 Attribute 1 (b) Attribute 2 5 5 0 10 −5 15 −10 −15 Cluster 1 Cluster 2 Cluster 1 Cluster 2 图 1 二维不均衡数据集的真实分布和 K–means 的聚类结果. （a）数据集真实分布；（b） K–means 的聚类结果 Fig.1 Real distributions of two-dimensional unbalanced data sets and clustering results of the K–means algorithm: (a) real distribution of datasets; (b) the clustering result of the K–means algorithm (a) Attribute 2 Attribute 1 35 0 30 5 25 10 20 15 15 20 10 25 5 30 0 35 40 45 50 55 60 (b) Attribute 2 Attribute 1 35 0 30 5 25 10 20 15 15 20 10 25 5 30 0 35 40 45 50 55 60 c1 c1 x1 c2 c2 c4 c4 c3 c3 Cluster 1 Cluster 2 Cluster 3 Cluster 4 Centroids Cluster 1 Cluster 2 Cluster 3 Cluster 4 Centroids 图 2 MC_IK 算法中模糊工作集构造规则存在缺陷示意图. （a）数据集真实分布；（b）MC_IK 对数据集初次聚类结果 Fig.2 Schematic diagram of the defects in the construction rules of the MC_IK algorithm’s fuzzy working set: (a) real distribution of data sets; (b) initial clustering result of the MC_IK algorithm on datasets 武 森等： 基于近邻的不均衡数据聚类算法 · 1211 ·
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 algorithm
2 之间发生了 “ 均匀效应 ” . 对于对 象 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 期
武森等：基于近邻的不均衡数据聚类算法 ·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 undeterminedcluster 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 ·