《改进K均值聚类的不平衡数据欠采样算法》-工学论文，软件工程论文-论文范文参考-科学狗论文网

标题

改进K均值聚类的不平衡数据欠采样算法

范文

于艳丽江开忠王珂盛静文

摘要：传统欠采样方法在处理不平衡数据问题时只考虑多数类样本的绝对位置而忽略了其相对位置，从而使产生的平衡数据集存在边界模糊问题。提出一种改进K均值聚类的不平衡数据欠采样算法（UD-PK）。该算法首先利用改进的PSO算法迭代寻找全局最优解作为K-means聚类所需初始值，然后通过K-means进行聚类，再按照每个类别中多数类与少数类的比例定义所取多数类样本个数，并根据多数类样本与簇心距离择优选择参与平衡数据集构造。在UCI数据集上的对比试验表明，该算法在少数类准确率上较一些经典算法有很大提升。

关键词：不平衡数据集;欠采样算法;K均值聚类;粒子群算法

DOI：10.11907/rjdk.192153开放科学（资源服务）标识码（OSID）：

中图分类号：TP312文献标识码：A 文章编号：1672-7800（2020）006-0205-05

0 引言

在机器学习中，不平衡数据集指不同类别的样本分布不均衡，即出现某一类别的样本远远多于另一类别的样本。这在现实生活中随处可见，如医疗领域、征信领域、信息安全领域等。其中，医疗领域患重大疾病的人、征信领域中信用不良的人、信息安全领域中的不安全信息等样本因其数量明显少于其它类别，因而都属于少数类样本。错分少数类样本的代价远大于多数类样本，因此提高少数类分类精度是不平衡数据的研究重点。

现有不平衡数据处理方法主要有两类：一是算法层面的处理，通过改变算法，如在分类算法中加入代价敏感因子，从而提高少数类的识别效果，如代价敏感决策树、代价敏感支持向量机等，集成学习算法使用一系列弱分类器进行学习，通过整合各分类器，从而产生很好的性能，如Adaboos算法等;二是数据层面的处理，通过改变两类数据样本数量构造平衡数据集，主要有过采样和欠采样方法，过采样就是增加少数类数量，欠采样就是减少多数类数量，都能达到平衡数据集的作用。

过采样算法如Smote算法，主要通过两点连线中插值以增加样本。Borderline-SMOTE算法主要根据K近邻中异类样本数目，确定出边界集，对边界集样本进行插值。还有很多在两者基础上的一些算法，如Random-smote、R-smote、SD-Ismote、CB-Smote等。

欠采样算法如US_DD算法，主要是将数据分成高密度簇和低密度簇，对两者采取不同的欠采样策略。KACbag算法将Adacost权重放人样本更新中，最后根据权重选择样本与少数类进行组合;One-side-selection算法主要是去除多数类中的干扰样本;SBC算法根据聚类后正负样本比例确定抽样比例参数;USCL算法是对多数类样本采用聚类方法，用聚类中心作为多数类样本。Lin提出了两种基于聚类的欠采样方法：①使多数类聚类数量等于少數类样本数量;②用每一个聚类中心附近的样本作为多数类样本。上述算法大多只对多数类样本进行处理，找出多数类样本中心，排除噪声样本，从而获取更多的多数类信息，但是没有考虑多数类相对于少数类的位置问题，因此容易选择边界多数类样本，使构造的平衡数据集产生模糊边界问题，导致少数类精度下降。

根据以上研究，本文提出一种改进的K均值聚类的不平衡数据欠采样算法（Improved Unbalanced Data Undersampiing Algorithm for K-means Clustering，UD-PK）。首先，通过PSO适应度函数寻找周围多数类样本点密集少数类样本点稀疏的聚类簇心，对静态的惯性权重进行动态调整，加快收敛速度，并提高寻优精度，通过计算每个粒子的适应度值更新粒子速度与位置，寻找全局最优解的聚类簇心;然后，将全局最优解作为K-means的初始聚类中心进行聚类;再根据每个类中多数类样本与少数类样本比例确定选取多数类样本数量;最后，根据样本与簇心距离，从中选择靠近簇心的多数类样本点加入最后平衡数据集。

1 相关知识

1.1 分类基础

即分类器的超平面法向量和常数是使得F1（F-Score值）取最大值时的（w1，w2，…，Wp，c）。

在实际问题中，往往两类C（0）/与C（1）的个体数量极度不平衡，将个体数量多的一类，比如C（0），称为多数类，另一类C（1）则称为少数类。

1.2 粒子群优化算法

粒子群优化算法（PSO）是一种基于群体智能的进化方法。优化问题的每一个潜在解都是搜索空间中的粒子，每一个粒子有其相应的速度、位置和一个由目标函数决定的适应度，算法通过适应度评价粒子优劣。

PSO算法流程：①算法首先随机挑选n个粒子作为初始位置;②通过适应度函数计算每个粒子的适应度值;③寻找并更新每个粒子的个体极值pBesti和全局最优值gBest，以及它们对应的粒子位置xBesti和xgBest;④根据每个粒子的个体极值位置与全局最优值位置，按式（4）、式（5）更新粒子当前速度和位置;⑤如果满足终止条件，则算法结束，否则转向步骤②。

其中，w、c1和c2分别是惯性权重与约束因子，p1和p2为[0，1]之间的随机数，式（4）中第2部分为认知分量（即自身作用），第3部分为社会分量（群体中其它粒子的作用），式（5）中T通常取l。

1.3 最小距离判别法

已知类C及其中心u，个体x到类C的距离定义为：

1.4 K-means聚类

由MacQueen提出的K均值算法是一种经典算法，在数据挖掘和知识发现领域应用较广。

随便看

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。