基于外点检测的加权k-means算法

时间：2024-12-22

胡豪杰,陈辉,穆婷婷,姚敏立,何芳,张峰干

(1.火箭军工程大学,陕西西安 710025) (2.中国航天科技集团有限公司第四研究院,陕西西安 710025) (3.北京新时代环球进出口有限公司,北京 100027)

聚类是将物理或抽象对象的集合划分成多个类簇,使得簇内样本相似度较高,而簇间样本的相似度较低[1-2]. 作为一种基本的数据分析方法,聚类在数据挖掘、模式识别、信息检索等领域得到了广泛应用[3]. 在众多聚类算法中,k-means算法以其简单高效的优点成为最具代表性的聚类方法之一. 然而众多实验结果表明,k-means对外点或离群点很敏感,这限制了聚类效果的进一步提升. 针对此问题,通常有两种方法来处理,一是使用诸如1-norm之类的特定范数来削弱外点的影响[4-5];另一种方法是将外点检测引入聚类算法中,直接消除外点[6-8],这种方法更为直接有效.

近年来,已有许多基于外点检测的聚类算法被提出. Hautamäki等[9]提出了ORC(outlier removal clustering)算法,该算法包括两个阶段,第一阶段即原始的k-means聚类过程,第二阶段是迭代移除离簇中心较远的样本点. Ahmed等[10]提出了一种改进的结合外点检测与聚类的方法,该算法首先将每个样本点分配到距其最近的簇,然后计算SSE(sum of squared error)/SST(total sum of squares)以检测异常点,若检测到任何异常值,则从数据集中删除,重复该过程直至算法收敛. Whang等[11]提出了一种非穷尽的重叠k-means 算法,该算法假设数据点可能不属于任一簇,或者属于多个簇. Gan等[12]提出了KMOR(k-means with outlier removal)算法,该算法引入了一个额外的簇,该簇包含所有外点. 根据Holoentropy在外点检测中的应用,Liu等[13]提出了COR(clustering with outlier removal)算法,在实现外点检测的同时达到了良好的聚类效果.

以上方法虽然都在一定程度上对算法的聚类结果进行了优化,但都遵循一个理想的假设,即每个样本点严格属于某一簇[14],否则即是外点. 而在但实际数据集中,外点的分布是模糊的. 为使聚类效果更加理想,本文计算数据点与最近簇中心的欧式距离并分配不同的权重,以此计算加权后的簇中心,并采用交替最小化优化算法求解该模型,其中权重为零的样本点被认为是外点. 实验结果表明,本文算法提高了外点检测的精确度,优化了聚类效果.

1 k-means算法

k-means算法是一种经典的聚类算法. 给定数据集X={x1,x2,…,xn}∈Rd×n,k-means的基本思路是将这n个样本点划分成k个簇,使得每一簇内的样本点具有较高的相似度,簇与簇间具有较低的相似度,相似度通过样本间的欧式距离来测算.k-means的目标函数可表示为:

(1)

(1)从数据集中随机选取k个样本点作为初始簇中心;

(2)计算每个样本点到各个簇中心的欧式距离,并将其赋给最近的簇;

(3)计算每个簇的平均值,作为新的簇中心;

(4)不断重复步骤2与步骤3,直至聚类结果不再发生变化.

图1 聚类结果示意图Fig.1 Schematic diagram of clustering results

2 基于外点检测的加权k-means算法

本节提出一种改进的基于外点检测的加权k-means算法,并采用迭代优化算法来解决该模型.

2.1 模型介绍

外点或离群点是指明显偏离数据集中其他样本对象的样本点.k-means算法中基于欧式距离的损失函数对异常值极为敏感,具体来说,若xi是一个外点,会使簇中心的位置严重偏离其真实位置,导致较差的聚类性能. 图1(a)为正确的无外点的数据分布. 如图1(b)所示,k-means算法将6个样本点错误归类,无法正确恢复图1(a)所示的正确数据分布. 如图1(c)所示,将聚类与外点检测相结合,可以清楚地区分不同的簇.

为消除外点的影响,本文引入权重向量s∈Rn×1,使得距簇中心越远的样本点具有越小的权重,并满足‖s‖0=m和sT1=1,其中0≤m

(2)

式中,Ind∈Rn×k为聚类指示矩阵,表示矩阵每一行只有1个元素为1,其余为0. 权重向量中s中有n-m个零元素,对损失没有贡献,而相应的样本点被视为外点. 式(2)中的第二项是正则化项,其中γ是正则化参数. 注意到若γ取值足够大,则式(2)等价于k-means算法.

2.2 优化求解

式(2)中有三个变量(Y,C和s)需要优化,本文采用迭代优化算法求解该问题.

固定C和s,求解Y,则问题(2)转化为求解

(3)

固定s和Y,求解C,则计算式(2)对cj的导数并将其设置为零,可得

(4)

固定C和Y,求解s,则问题(2)等效于求解

(5)

(6)

首先仅考虑权重向量s的前两个约束条件,上述问题的拉格朗日函数为

(7)

式中,θ与ζ≥0是拉格朗日乘数. 根据KKT条件,有

(8)

不失一般性,假设d1,d2,…,dn从大到小排序. 根据约束‖s‖0=m,则sm>0,sm+1=0. 由此可得

(9)

根据约束sT1=1,有

(10)

结合式(9)和式(10),参数γ满足以下不等式

(11)

因此,为了获得满足所有约束条件的权重向量s,可将γ设置为

(12)

根据式(8)、(10)和(12),s可计算如下

(13)

权重向量s中零元素对应的样本点被视为外点,而向量s是不断更新迭代的,外点亦会不断更新直至算法收敛,于是算法自适应地移除了离群点. 本文算法的具体流程如下所示:

算法1基于外点检测的加权k-means算法.

输入:数据集X∈Rd×n,类簇数k,有效样本点数m;

输出:聚类指示矩阵Y.

Step 2 Repeat;

Step 3 通过求解公式(3)更新聚类指示矩阵;

Step 5 通过公式公式(13)更新权重向量s;

Step 6 Until convergence.

3 实验与结果

为检验算法的有效性,将本文算法与k-mean,NEO-k-means及COR进行比较. 实验环境为:Intel(R)Core(TM)i7-10700K CPU,内存32GB,操作系统Microsoft Windows 10,算法编写环境为MatlabR2020b.

3.1 评价指标

本文采用4个评估指标来衡量所提算法在聚类有效性和外点检测两方面的性能,其中NMI与Rn是两种常用的聚类评价指标,分别定义为

(14)

(15)

式中,nij表示既属于聚类算法结果的第i簇也属于真实类别的第j簇的样本数;ni+和n+j分别是聚类算法得到的第i簇的样本数以及真实类别第j簇的样本数.

为了衡量外点检测的性能,采用Jaccard指数和F-measure两种评价方法,分别定义为:

(16)

(17)

式中,O和O*分别是算法得到的外点集合以及真实的外点集合;F-measure是外点准确率和召回率的调和平均值.

3.2 数据集

表1 数据集描述Table 1 Characteristics of datasets

为测试本文算法的有效性,选择在一组合成数据及多组取自UCI中的数据集进行实验. 合成数据集是由高斯分布函数在二维空间中随机生成的包含90个样本点的9个主要类簇,每个类簇包含10个样本点,数据集添加了6个具有较大偏差的外点,分布在(1.5,1.5),(2.5,2.5),(3,2.5),(1.5,2.5),(1,2.5),(2.5,1.5)的位置. 4组真实数据集为UCI中的ecoli数据集、glass数据集、yeast数据集和zoo数据集,将每个数据集中最小类的样本点视为外点. 表1描述了每个真实数据集的具体信息.

3.3 实验和结果

实验首先对本文方法与k-means算法在合成数据集上的输出进行分析,然后在实际数据集上定量地比较所提出的方法和几种竞争方法. 在合成数据集上得到的聚类结果如图2所示. 图2(a)和图2(b)分别显示了k-means算法与本文算法得到的聚类效果,其中每种颜色表示算法得到的不同类簇,外点由黄色菱形表示,簇中心用星号显示. 可以看出,本文算法可完全区分9个类簇和6个外点,得到聚类中心也更接近真实的聚类中心. 图2(c)显示利用本文算法得到的所有数据点的权重分配,可明显看出真实聚类中心区域附近的数据点分配了较大的权重,而离实聚类中心较远的数据点分配了较小的权重,因此可以学习到更精确的簇中心,从而实现了更好的聚类性能.

图2 合成数据上的聚类效果Fig.2 Performance on the toy dataset

表2和表3所示为在4组数据集上不同算法的实验结果. 由于所比较的算法易受初始化的影响,因此将每个算法随机初始化运行100次,并记录平均结果.

表2 不同算法在4组真实数据集上NMI与Rn取值Table 2 NMI and Rn of different approaches on four real-world datasets

表3 不同算法在4组真实数据集上Jaccard与F-measure取值Table 3 Jaccard and F-measure of different approaches on four real-world datasets

从表2可以看出,本文所提出的方法在NMI指标中均达到了最好效果,在glass和zoo数据集中,比第二好的方法实现了超过4%的增益. 在另一指标Rn中,虽然本文方法在glass数据上并未达到最优,但在其他3个数据上实现了最好效果,这是由于本文算法根据数据点与最近簇中心的欧式距离分配不同的权重获得了更为精确的簇中心,因此实现了更好的聚类效果. 表3通过Jaccard和F-measure两个指标定量体现各个算法在不同数据集上外点的检测性能. 本文所提出的算法在所有数据集上的检测性能均明显优于k-means,NEO-k-means和COR. 在数据集glass与yeast上,指标Jaccard和F-measure均超过对比方法的20%. 结果显示,本文算法不仅优化了聚类效果,还提高了外点检测的精确度.