一种改进密度峰值聚类的欠采样算法
时间：2022-11-19 12:45:04 来源：柠檬阅读网 本文已影响 人 
李鑫
（首都经济贸易大学，北京 100026）
作为数据挖掘领域的研究热点之一，分类问题的研究已发展得非常成熟，诸多的分类算法被提出，如：决策树、支持向量机、逻辑回归等。这些算法在传统的分类问题中通常都具有良好的表现效果。在实际应用中，数据不平衡现象出现的频率越来越高，很多情况下少数类样本具有更高的研究价值。比如在癌细胞检测、信用卡欺诈检测、网络入侵检测等领域都存在着数据不平衡问题，如果错分少数类将带来严重的后果。而传统的分类方法很少顾及少数类的分类精度。因此，针对不平衡数据研究如何提高少数类样本的分类精度具有重要的意义。目前，针对不平衡数据分类问题的研究主要分为数据层面和算法层面两大方向。数据层面是通过对数据集进行重抽样来构建平衡数据集，主要有欠采样和过采样两大类。算法层面主要是通过改变少数类样本的权重来提高分类器对少数类样本预测的精度。本文基于数据层面的欠采样方法开展研究，提出了一种新颖的平衡数据集获取方法以提高分类器对少数类的预测精度。
最简单的欠采样方法是随机欠采样（RUS），它是在多数类数据集中随机地删除一部分样本。编辑最近邻规则（ENN）考虑了样本重要性，在少数类的邻近样本中删除一部分多数类；
压缩最近邻规则（CNN）在ENN 的基础上对决策边界上的样本点给予了更多地关注。后来又有学者提出TomekLinks算法，利用Tomek 对来识别数据集中对分类造成干扰的噪声点。聚类算法能够根据相似性对样本进行划分，YEN 等将K-means 聚类算法应用到欠采样中，先对多数类样本进行聚类，再从每个簇中按照一定比例进行抽样，从而减少冗余样本。由于K-means 算法假设较强，仅适用于超球形簇，并且对异常值敏感，崔彩霞等将密度峰值聚类应用到欠采样并取得了良好的效果。密度峰值聚类算法是一种基于密度的聚类方法，它根据样本的密度分布来进行聚类，不仅可以检测到噪声点而且适用于任意形状的簇。
基于以上研究，本文提出一种改进密度峰值聚类的欠采样算法（Udersamp lingbasedon Density Peak Entropy Clustering,DPEC），首先利用信息熵对密度峰值聚类算法进行改进，优化聚类效果；
然后用改进算法对多数类聚类，将少数类样本数量作为聚类中心数，并选取密度距离较大的样本点作为聚类中心；
最后用所有聚类中心代替原始多数类数据集，既保留了样本重要信息又可以消除噪声样本从而提高数据集的质量，优化不平衡数据的分类性能。
1.1 密度峰值聚类
密度峰值聚类算法（Density Peak Clustering,DPC）是利用样本的密度分布来进行聚类，适用于任意形状的簇，该算法的核心思想建立在两个假设上：簇类中心的局部密度大于其邻近样本点的局部密度；
簇类中心点之间有着相对较大的距离。通过计算每个样本的局部密度和偏移距离对每个点进行簇的划分，聚类中心的选取通常通过绘制以局部密度为横轴，偏移距离为纵轴的决策图来人为主观选取。当聚类中心后，剩余样本点将分配给与其最近且具有更高密度的簇中。假设数据集为={，，…，x}T，其中为数据集的样本数，对于每一个样本x，其局部密度ρ为：
其中d是样本x与样本x的欧氏距离；
d为截断距离，需要人为事先设定，通常d设置为将样本点间距离进行降序后排列在2%的值。
样本点x的偏移距离δ被定义为该样本点到具有更高局部密度的点的最小距离：
1.2 信息熵
熵是信息论中量化系统信息含量的指标，熵越大，系统的不确定性越大。信息熵通常用来衡量数据所含信息量的大小，事件发生的概率越高，其携带的信息量越低。信息熵定义为：
1.3 改进密度峰值聚类的欠采样算法
聚类算法能够将相似样本尽可能地分在同一个簇，且不同簇的差异性尽可能大。将聚类算法应用到不平衡数据集的欠采样中，能够抽取到更具有代表性的样本，消除冗余样本。密度峰值聚类算法利用数据集的密度分布进行聚类，该算法思想简单，算法复杂度低，并且不易受异常值的干扰。但其截断距离和聚类中心都需要人为主观选取，聚类效果还有待提升。本文对其进行优化，使其应用在能够在不平衡数据集上取得更好的效果，提出了改进密度峰值聚类的过采样算法（Udersamplingbasedon Density Peak Entropy Clustering,DPEC）。
本文将信息熵与DPC 算法相结合，使算法能够自动寻找最优截断距离。信息熵越大，数据分布越混乱，故聚类的效果越差；
相反，信息熵越小，聚类效果就越好。因此，使信息熵（d）达到最小时的d就是最优截断距离，此时的局部密度和偏移距离达到最优值，聚类效果最好。最优截断距离定义如下：
其 中，ρ和δ是ρ和δ归一化后的值，
1.4 方法步骤
我们将本文提出的改进密度峰值聚类的欠采样算法（DPEC）的具体步骤总结为算法1，具体为：
算法1 DPEC
输入：原始数据集；
输出：新的平衡数据集´。
步骤1：将数据集分为多数类和少数类，计算少数类样本个数=||；
步骤2：计算每个多数类样本点x的局部密度ρ和偏移距离δ；
步骤8：将γ最大的前（=||）个样本点作为聚类中心，选取这些样本作为新的多数类样本，并与少数类数据集合并构成平衡数据集´。
2.1 性能评估指标
对于二分类问题，通常用混淆矩阵来作为进行评估，其表示如表1所示。
表1 混淆矩阵
对于不平衡数据分类问题，将少数类记为正类，多数类记为负类。本文用F1-score和AUC两个指标来评估算法效果。
2.2 实验设置与结果分析
为验证DPEC 欠采样算法效果，本文采UCI 数据库的Abalone 数据集进行实验。该数据集是UCI 数据库提供的标准机器学习分类问题数据集，通过利用鲍鱼的长度、直径、内脏重量等属性来预测鲍鱼的性别。该数据集共含有4 177 个样本，特征数为8 个，其中多数类样本量为2 870 个，少数类样本量为1 307 个，不平衡比率为2.2。选择DPC、K-means、TomekLinks、CNN、NearMiss、RUS 六种欠采样算法与本文算法进行对比，并在决策树（CART）、逻辑回归、支持向量机三种单分类器，随机森林、Adaboost 两种集成算法上进行实验测试其提升效果。本文实验的运行环境为Jupyter Notebook 软件，选择75%为训练集，选择25%为测试集进行模型训练，参数均使用默认参数设置，选择F1-score 和AUC 值作为评价指标来判断模型效果。表2 是不同欠采样方法在各个分类器上模型训练得出的F1-score 和AUC 值。
表2 DPEC 与其他采样方法在不同分类器上的效果对比
采样算法 CART Logistic SVM RF AdaBoost F1 AUC F1 AUC F1 AUC F1 AUC F1 AUC DPEC 0.529 0.634 0.566 0.714 0.569 0.674 0.563 0.709 0.570 0.718 DPC 0.430 0.550 0.496 0.699 0.475 0.617 0.473 0.662 0.483 0.680 K-means 0.403 0.528 0.501 0.694 0.500 0.583 0.508 0.665 0.518 0.659 TomekLinks 0.435 0.581 0.392 0.716 0.125 0.520 0.440 0.708 0.445 0.710 CNN 0.463 0.582 0.556 0.714 0.547 0.638 0.544 0.692 0.557 0.703 NearMiss 0.473 0.576 0.543 0.714 0.527 0.645 0.495 0.664 0.509 0.646 RUS 0.448 0.578 0.545 0.711 0.569 0.672 0.529 0.694 0.557 0.714不采样 0.387 0.553 0.256 0.715 0.000 0.499 0.373 0.707 0.369 0.721
从表2 可以看出，相比于用原始的密度峰值聚类算法（DPC）进行欠采样，本文改进后的算法（DPEC）在F1 和AUC 值上都有明显提高。相比于不对数据进行任何处理，本文提出的欠方法（DPEC）显著提高了少数类的F1 值。与K-means、TomekLinks、CNN、NearMiss 和随机欠采样五种常用的欠采样方法相比，本文算法也有着不错的效果。总体而言，DPEC 有效提升了不平衡数据集的分类性能。
欠采样是不平衡数据分类常用的重采样方法之一。本文提出了一种改进密度峰值聚类的不平衡数据欠采样算法。该算法利用信息熵确定全局最优截断距离，为克服量纲影响，对局部密度和偏移距离进行归一化后相乘并进行排序，将少数类数据集的样本数量作为多数类聚类的聚类中心数，选择密度距离较大的点作为聚类中心。用这些聚类中心样本代表整个多数类数据集，从而去除冗余数据保留多数类数据集的重要信息。将本文算法与其他欠采样算法进行对比实验，并在决策树（CART）、逻辑回归、支持向量机三种单分类器，随机森林、Adaboost 两种集成算法上进行实验测试其提升效果，结果表明，本文算法在一定程度上提高了少数类样本的预测精度。后续可考虑与过采样结合对不平衡数据集的混合采样展开研究。
猜你喜欢 信息熵峰值聚类 犊牛生长发育对成年奶牛高峰奶产量和峰值日的影响中国畜牧杂志(2022年10期)2022-10-12基于数据降维与聚类的车联网数据分析应用汽车实用技术(2022年4期)2022-03-07基于模糊聚类和支持向量回归的成绩预测华东师范大学学报（自然科学版）(2019年5期)2019-11-11近似边界精度信息熵的属性约简华东师范大学学报（自然科学版）(2018年3期)2018-05-14云南省民用汽车保有量峰值预测价值工程(2017年11期)2017-04-18基于密度的自适应搜索增量聚类法电子技术与软件工程(2016年23期)2017-03-06基于信息熵的承运船舶短重风险度量与检验监管策略研究中国水运(2016年11期)2017-01-04信息熵及其在中医“证症”关联中的应用研究电脑知识与技术(2016年27期)2016-12-15论犯罪信息犯罪研究(2016年5期)2016-12-01
