·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-meansthe 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 期