控制与决策  2019, Vol. 34 Issue (6): 1219-1226  
0

引用本文 [复制中英文]

杨华晖, 孟晨, 王成, 姚运志. 基于目标特征选择和去除的改进K-means聚类算法[J]. 控制与决策, 2019, 34(6): 1219-1226.
[复制中文]
YANG Hua-hui, MENG Chen, WANG Cheng, YAO Yun-zhi. Improved K-means clustering algorithm based on feature selection and removal on target point[J]. Control and Decision, 2019, 34(6): 1219-1226. DOI: 10.13195/j.kzyjc.2017.1548.
[复制英文]

基金项目

国家自然科学基金项目(61501493)

作者简介

杨华晖(1992-), 男, 博士生, 从事装备测试及数据挖掘的研究, E-mail: yanghuahui1991@163.com;
孟晨(1963-), 男, 教授, 博士生导师, 从事装备保障网络化、装备全寿命周期管理等研究, E-mail: mengchen63@163.com;
王成(1980-), 男, 讲师, 博士, 从事装备全生命周期管理、测试系统软件体系的研究, E-mail: 32626364@qq.com;
姚远志(1988-), 男, 工程师, 博士, 从事复杂装备维修策略、装备MRO关键技术的研究, E-mail: yaoyunzhi@vip.qq.com

通讯作者

杨华晖, E-mail: yanghuahui1991@163.com

文章历史

收稿日期:2017-11-15
修回日期:2018-04-12
基于目标特征选择和去除的改进K-means聚类算法
杨华晖 , 孟晨 , 王成 , 姚运志     
陆军工程大学 导弹工程系,石家庄 050003
摘要:针对高维数据聚类中K-means算法无法有效抑制噪声特征、实现不规则形状聚类的缺点, 提出一种基于目标点特征选择和去除的改进K-均值聚类算法.该算法使用闵可夫斯基规度作为评价距离进行目标点的分类, 增设权重调节参数a、重置权重系数α进行特征选择和去除, 可有效减小非聚类指标特征带来的噪声影响.算法验证实验选取UCI真实数据集和人工数据集进行聚类分析, 验证改进算法对抑制噪声特征的有效性, 与WK-means、iMWK-means算法进行实验对比, 分析聚类学习时特征选择的适用性, 同时寻找最优的距离系数β和权重系数α.
关键词K-均值算法    特征选择    高维数据聚类    特征赋权    数据去噪    
Improved K-means clustering algorithm based on feature selection and removal on target point
YANG Hua-hui , MENG Chen , WANG Cheng , YAO Yun-zhi     
Department of Missile Engineering, Army Engineering University, Shijiazhuang 050003, China
Abstract: Aiming at the weakness that the K-means algorithm cannot effectively suppress the noise attributes and realize irregular shape clustering on high-dimensional data, an improved K-means clustering algorithm based on feature selection and removal on target point is proposed. In the improved K-means algorithm, the Minkowski metric is adopted as the evaluation of distance for the classification of the target point. The weighting adjustment parameter a is added and the weighting coefficient α is reset for feature selection and removal, which can reduce the effect of non-clustering index noise features. The UCI real datasets and artificial datasets are used for clustering analysis in the algorithm validation experiment. And the effectiveness of suppressing the noise features is validated. Compared with the WK-means and iMWK-means algorithms in the validation experiment, the applicability of feature selection in clustering learning process is analyzed. At the same time, the optimal distance coefficient β and the weighting coefficient α are found.
Keywords: K-means algorithm    feature selection    high-dimensional data clustering    feature weighting    data denoising    
0 引言

K-means聚类算法是一种简单高效、易于实现的统计分析方法, 在模式识别、机器学习、数据挖掘等领域被广泛应用, 且在工程实践中具有很强的实用性[1-3].在知识发现和信息挖掘过程中, 常常需要对数据库进行数据聚类分析, 由于样本数据大, 特征分量多, 运用K-means算法仅对特征进行权重赋值[4-6], 则无法对噪声特征进行有效抑制, 因此需要在权重赋值之前对特征进行选择.

K-means特征赋值方法中, 文献[4]首先进行了研究并提出了WK-means算法, 在目标函数中给出了特征权值参数w, 通过分步更新目标点分类矩阵、簇中心点和特征权值w迭代求解最优收敛点; 其后, 文献[7-10]采用iMWK-means算法对初始聚类中心和特征权重调节系数进行了优化, 能够对目标特征进行组合处理, 允许存在不同距离的评价标准(β≠2), 对不规则形状的簇能有效初始化.另外, 还有文献[11]提出的FWSA算法、文献[12]提出的FGK算法, 文献[13]提出的IK-P算法等.这些方法都是在WK-means算法的基础上提出的, 且都能做到对所有特征进行赋权值, 但并没有在赋权值之前对特征进行选择.针对此问题, 本文提出一种基于目标特征选择和去除的改进K-means算法, 该算法给出目标函数, 对迭代过程进行讨论, 并给出最优参数选取值.最后选取UCI机器学习真实数据集和人工数据集进行实验评估, 验证算法对噪声的抑制效果, 对比WK-means、iMWK-means算法分析特征选择的优势和适用性.

1 K-means特征赋权问题

K-means特征赋权值算法的应用是当前面对数据“维度灾难”问题的真实反映, 现行聚类算法处理的数据早已超出传统单一数值的概念, 每个目标点不仅含有多维数值[14], 而且还有分类属性[15].在计算机中需要多个数据类型共同描述某个目标点[16], 传统的K-means算法已经不能满足当前数据处理的要求.处理多类型数据, 需要对不同特征维进行分组处理和权值分配.运用K-means算法对工程实践问题进行模式识别或数据挖掘时, 还要注意以下3个问题:

1) 避免噪声特征的干扰;

2) 允许同一簇中的各特征权值不同;

3) 允许同一特征在不同簇中具有不同权值.

为直观描述上述K-means特征赋权问题, 列举来自某工程测试领域的数据库聚类问题, 如表 1所示.

表 1 某测试数据库的取样目标值

表 1中:X1 ~ X9选自某测试数据库中的9个目标点, X1 ~ X3, X4 ~ X6, X7 ~ X9分别表达了被测对象的3种工作状态.为直观观测目标点位置, 每个目标点用3个数据特征值进行描述, 如图 1所示.

图 1 数据X1 ~ X9三维分布

对上述目标点进行聚类, 给定聚类簇数K=3, 随机选择初始聚类中心, 分别使用K-means算法、WK-means算法和iMWK-means算法迭代求解最优收敛点, 得到图 2所示的聚类效果图, 符号“×”表示迭代后输出的聚类中心.

图 2 3种算法聚类效果(二维)

对3种算法得到的聚类结果分析可知, 由于K-means随机选取了初始点且无法对目标特征进行权重判断, K-means算法易陷入局部收敛, 从而无法得到正确的聚类结果, 即K=3簇内目标点个数为零. WK-means(β=1.8)和iMWK-means(β=2)可以实现正确聚类, 但最后得到的聚类中心效果有所差别, 即对目标特征值的权重判断有偏差, 且就最后迭代求解的次数而言: WK-means在设置实验中的迭代更新次数NWK-means=23次, 计算时间TWK-means=0.14 ms; iMWK-means迭代更新次数NiMWK-means=7次, 计算时间TiMWK-means=0.05 ms.在计算效率上iMWK-means更高.

通过表 1分析的3个簇的数值描述可以判断:簇1的第3维特征、簇2的第2维特征、簇3的第1维特征相比其他特征的簇内散度较小、簇间散度大, 因此可以很快实现数据的归类判断, 得到正确的聚类结果.

针对上述问题, 本文提出一种基于目标特征选择和去除的改进K-means算法(Feature selection K-means, FSK-means), 主要针对高维数据聚类中的特征选择问题进行研究, 给出需要优化的目标函数以及迭代过程中各分量的求解公式, 最后使用UCI机器学习数据集和随机数据集进行验证, 对比分析K-means算法、WK-means算法、iMWK-means算法, 验证特征选择对噪声去除的有效性和算法自身的适用性.

2 特征赋权的K-means算法 2.1 WK-means算法

WK-means算法是在K-means算法基础上对目标点的不同特征类型、不同特征权重进行描述的改进算法, K-means算法给出的目标函数为

(1)

其中: yiv表示各目标点, ckv表示各聚类中心, K表示簇数, Sk表示各聚类簇, M表示数据维数.

改进的WK-means算法对各维特征进行权重赋值后, 增加了ωkv参数, 对不同簇的不同特征进行了权重分配, 给出的目标函数是

(2)

其中: β表示权重调节系数, 经讨论后得到β≥1的取值范围.已有文献验证了β=1.8时聚类计算的良好效果, 但在实际运用算法进行聚类学习时仍需要对β的值进行多次试验.另外, 文献[4]给出了在目标特征为分类属性和数值类型时的ωkv取值情况.

2.2 iMWK-means算法

iMWK-means算法给出的目标函数为

(3)

就给定的目标函数而言, iMWK-means算法使用闵可夫斯基规度作为评价距离, 拓展了欧氏距离的限制.另外, iMWK-means对不规则的簇形状有较好的聚类效果, 是因为在进行聚类迭代之前对数据进行预处理, 智能选取初始聚类中心[17], 给定初始中心点ckv的位置.但从K-means算法实现的步骤上分析, 使用搜索算法预选聚类中心与迭代分配权值是两个不相关的步骤, 初始中心选择可作为K-means算法的另外研究内容[18-19], 因此下述算法仅从特征维度的权重分配进行探讨.

3 FSK-means算法 3.1 基本思路

基于目标特征选择的K-means算法, 基本实现思路是将特定簇内的某特征的权重系数置为零, 即

(4)

因此, 应当给出某判别标准, 用以判定是否实现算法中权重系数ωkv的置零, FSK-means算法给出的目标函数为

(5)

且满足

(6)
(7)

其中: yiv为各目标点; ckv为聚类中心点; Rik为目标点分配矩阵, Rik=1表示第i个目标点聚类在k簇内; N为目标点总数; a为特征的选择判断参数; w为权重系数; αβ分别为权重和距离的调节系数.与iWMK-means给出的式(3)相比, 上述目标函数添加了特征选择的判断阈值a, 并使用“±”运算对不同簇内不同特征权重进行调节.对于小于特征选择阈值a的权重w, 通过比较后在算法实现中将w置零, 从而实现去除聚类高维数据中的噪声特征分量.另外, 式(5)将权重与距离调节参数分离, 以满足不同数据形状、不同数据结构的聚类要求.上述目标函数的最优求解采用分步求最优值的方法, 主要分为3个优化步骤:

1) 固定权重参数ωkv和聚类中心ckv, 更新目标点分配Rik;

2) 固定分配矩阵Rik和权重参数wkv, 更新聚类中心ckv;

3) 固定聚类中心ckv和分配矩阵Rik, 更新权重参数ωkv.

定理1  目标点分配矩阵Rik由下式更新:

(8)

证明   目标点分配到定义距离最小的聚类簇内, 当yick的距离最小时, yi被分配到k簇内[4].

定理  聚类中心ckv更新公式为

(9)

证明   聚类中心更新由各簇内所有目标点求取各维度的均值得到[7].

定理3  权重参数ωkv由下式给出:

(10)

其中

(11)

证明   由式(5)和条件(6)构建新目标函数, 即

(12)

(13)

采用式(12)对参量ω求偏导数, 可得

(14)

将式(14)置零可得

(15)

设此时迭代次数为x, 则有如下情况.

情况1   若Wkv(x-1) < a, 则表明k簇内v特征的权重分量ωkv小于设定阈值a, 此时Wkv(x)a取“-”号, 有Wkv(x-1)-a < 0, 又由于权重分量不能取负值, 此时置ωkv=0;

情况2   若Wkv(x-1)a, 则表明k簇内v特征的权重分量ωkv大于设定阈值a, 此时Wkv(x)a取“+”号, 此时式(15)有

(16)

整理可得

(17)

式(17)两边对簇内所有特征v取和可得

(18)

对式(17)和(18)整理可得

(19)

且此时恒存在ωkv≥0.

3.2 算法迭代过程

输入:数据集Y=y1, y2, ..., yn, 目标点维度V, 聚类簇数K;

初始化设置:权重系数α、距离系数β、权重选择参数a、随机聚类中心c1, c2, ..., cK, 初始权重ω= 1/V, 最大迭代次数Xmax, 收敛值ε;

输出:目标分配矩阵Rik, 最终聚类中心ck(k=1, 2, ..., K).

Step 1: Repeat

Step 2: for i=1 to N

Step 3: for k=1 to K

Step 4:

Step 5: end

Step 6: end

Step 7: for k=1 to K

Step 8:

Step 9: end

Step 10: for k=1 to K

Step 11: for v=1 to M

Step 12: if Wkv(x-1)=0

Step 13: set Wkv(x)=0

Step 14: else

Step 15: end

Step 16: end

Step 17: until C(x)-C(x-1) < ξ or xXmax,

Step 18: return Rik and Ck

4 实验评估

实验评估主要考察算法在下述方面的聚类有效性:

1) 对于添加了噪声维度的不同数据集, 考察FSK-means与K-means算法的聚类恢复效果;

2) 对于相同的无噪声数据集, 比较FSK-means算法与K-means、WK-means、iWMK-means算法的聚类恢复情况;

3) 对相同的无噪声数据集, 考察不同αβ参数取值下的算法聚类恢复效果, 寻找最优参数取值.

在算法复杂度方面, WK-means、iWMK-means、FSK-means算法在循环嵌套和迭代方法上具有一致性, 因此本节实验评估不予特别考虑.

4.1 数据集选择

实验评估所用的数据集为UCI数据库中7组真实数据集和5组人工随机生成的高斯数据集, 其中真实数据集Wine、Iris、Heart disease、glass数据集已经被文献[4, 7]验证过, 另外选取Libras movement、gesture phase、MFCCs高维数据集对聚类有效性的2)和3)进行验证.在添加噪声方面, 每组真实数据集添加均值为0、方差为0.1的1 ~ 5列不等的噪声维度.人工数据集方面, 每组数据集目标数为500, 维度为5, 均值为0, 方差为0.3, 聚类数为5, 各数据集目标数与维数情况如表 2所示.

表 2 各数据集目标数与维数
4.2 标准化初始聚类中心

在对每组数据集进行聚类分析前, 需要初始化聚类中心.为了更真实地体现算法的聚类效果, 排除初始聚类中心不同对算法性能造成的影响.本文在实验评估时均使用iK-means方法选取的初始聚类中心[17], 即后续实验比较的是iK-means、iWK-means、iMWK-means、iFSK-means算法使用相同聚类中心恢复得到的正确率.

4.3 有无噪声情况下的比较

运用iK-means算法和iFSK-means算法对是否添加了噪声维度的真实数据集进行聚类, 得到结果如表 3所示.

表 3 有无噪声情况下数据集聚类准确率

分析表 3所示的结果可以得出: 1)添加了噪声的数据集在运行iK-means算法时聚类正确率下降很大, 即不能区分噪声维度和真实维度; 而iFSK-means算法在特征选择时可去除噪声维度的干扰, 减小噪声对聚类结果的影响. 2)Heart disease、Libras movement、gesture phase、MFCCs相对Wine、Iris、glass是高维数据集, iK-means算法对噪声没有辨别, 因此在各个数据集添加噪声时均下降很快, iFSK-means算法对噪声维度的去除, 在高维数据时比低维度数据更有效.

4.4 特征赋权算法的比较

特征赋权的算法, 在iWK-means、iMWK-means、iFSK-means算法中因权重系数α与距离系数β的取值差异而得到不同的聚类结果, iWK-means、iMWK-means算法参数值选择参考文献[4, 6-7]的不同数据集的最优取值实验, iFSK-means在a=1/N时不同αβ系数取值下的聚类结果如表 4 ~ 表 10所示.

表 4 Iris数据集聚类结果
表 5 Wine数据集聚类结果
表 6 Heart disease数据集聚类结果
表 7 glass数据集聚类结果
表 8 Libras movement数据集聚类结果
表 9 gesture phase数据集聚类结果
表 10 MFCCs数据集聚类结果

从实验呈现的结果看, 在权重系数和距离系数确定的情况下, 其算法恢复正确率为

上述规律可以体现出特征赋权的K-means算法相比于传统K-means算法的聚类更具有效性, 尤其是在高维数据集Heart disease、Libras movement、gesture phase、MFCCs中, 聚类性能提高得更为明显.其次, 对比iFSK-means与iMWK-means算法的恢复准确率, 如表 11所示.

表 11 iMWK-means与iFSK-means恢复准确率比较

表 11中: MFCCs数据集通过iFSK-means算法所得结果的提高并不是十分明显, 原因是iFSK-means的参数取值与iMWK-means的相近, 其中α值均取1.2, β值分别取1.2和1.8, 因此在特征维度的选择和去除上并不能取得明显效果. gesture phase数据集正确率由iMWK-means的80.9 %提高到iFSK-means的81.4%, 仅就正确率变化而言, 聚类效果提升并不明显, 但由于数据集本身数据量大, 数据恢复的正确个数实际增加了168个点, 因此可以认为iFSK-means算法是能够在特征赋权前对特征进行有效选择和去除的. Heart disease数据集恢复率提高相对多, 但实际目标点数并不多, 且在该数据集中数值差异较大, 维度V大、聚类簇数K小, 在不同类簇中很多维数据是相同的, 因此iFSK-means在实际选择时可以较好地对其进行去除, 从而留下在不同簇差异较大的特征进行聚类恢复. Glass数据集的数据差异也很大, 目标点较少, 因此相对恢复的目标点数提高也并不是十分明显.

就iMWK-means算法和iFSK-means算法恢复效果而言, 当维度较大且数据点差异明显时, 特征选择和去除的方法更能取得良好效果, 实际原理就是在特征赋权之前对其进行判定选择.而在低维数据或数据差异不大时, 特征选择会起到相反的效果.

4.5 最佳参数取值

iFSK-means算法共给出aαβ三个参数取值, 实验中均取a=1/N, 下面主要针对权重和距离系数的不同取值进行实验和讨论, 实验结果如表 12所示.

表 12 不同αβ系数下iFSK-means聚类实验结果

在表(12)中, GM给出的是5个数据集聚类恢复率的平均值, 可以看到系数的最佳取值集中在α=1.2, β=1.8和α=1.6, β=2.5两组取值之间, 因为真实数据集的差异较大, 不能够有效辨别系数的最佳取值, 所以给出GM数据集的聚类恢复结果.从随机数据的恢复结果可以看出, α=1.2, β=1.8情况略显优势, 但在实际问题中还需要根据数据集形状和数据特点进行参数选择.其次, 权重调节参数a在同组实验中的取值没有变过, 主要是依据不同数据集的维度而固定设置的, 该参数是否对聚类结果产生较大影响, 需要进行后续验证.

5 结论

特征赋权的K-means算法是一种有效处理混合噪声维度、不规则形状类簇、高维数据集聚类的有效方法.本文提出了基于特征选择和去除的改进K-means算法, 通过与WK-means、iMWK-means算法的聚类恢复性进行比较, 探讨了带噪声情况下的聚类效果; 对比了同一数据集下不同特征赋权算法的聚类结果, 分析了在特征赋权之前对其进行选择和去除的必要性; 给出了FSK-means的最佳参数选择值.实验结果表明了该算法在处理高维数据和特征差异度较大时聚类性能的优势.但是, 本文算法还有需要探讨和改进的方面:

1) 在处理数据的分类属性特征时, 并没有给出具体方法, 算法实验前只是进行了人工筛选.

2) 在参数a的取值上没有进行探讨, 没有验证其他给定值能否进行有效的特征选择.另外, 使用(w± a)的方法对特征进行选择和去除, 使得算法略显粗糙和简单, 需要改进后实现对特征权重更加灵活地处理.

3) 改进算法对簇间散度信息利用不充分, 对噪声维度和数据不规则维度的分辨力有限.

参考文献
[1]
Bai L, Cheng X Q, Liang J Y, et al. Fast density clustering strategies based on the k-means algorithm[J]. Pattern Recognition, 2017, 71(3): 375-386.
[2]
Jiang X P, Li C H, Sun J. A modified K-means clustering for mining of multimedia databases based on dimensionality reduction and similarity measures[J]. Cluster Computing, 2017, 20(10): 1-8.
[3]
黄月, 吴成东, 张云洲, 等. 基于K均值聚类的二进制传感器网络多目标定位方法[J]. 控制与决策, 2013, 28(10): 1497-1501.
(Huang Y, Wu C D, Zhang Y Z, et al. Multi-objective localization method based on K-means clustering in binary sensor network[J]. Control and Decision, 2013, 28(10): 1497-1501.)
[4]
Chan E Y, Ching W K, Ng M K, et al. An optimization algorithm for clustering using weighted dissimilarity measures[J]. Pattern Recognition, 2004, 37(5): 943-952.
[5]
Huang J Z, Ng M K, Rong H, et al. Automated variable weighting in k-means type clustering[J]. IEEE Trans on Pattern Analysis and Machine Learning, 2005, 27(5): 657-668. DOI:10.1109/TPAMI.2005.95
[6]
Chen E Y, Ye Y, Xu X, et al. A feature group weighting method for subspace clustering of high-dimensional data[J]. Pattern Recognition, 2012, 45(1): 434-446.
[7]
Amorim R C, Mirkin B. Minkowski metric, feature weighting and anomalous cluster initializing in K-means clustering[J]. Pattern Recognition, 2012, 45(3): 1061-1075.
[8]
Amorim R C D, Komisarczuk P. On initializations for the minkowski weighted k-means[C]. Int Conf on Advances in Intelligent Data Analysis. Helsinki: IEEE, 2012: 45- 55. https://www.researchgate.net/publication/232713222_On_Initializations_for_the_Minkowski_Weighted_K-Means
[9]
Amorim R C D, Hennig C. Recovering the number of clusters in data sets with noise features using feature rescaling factors[J]. Information Science, 2015, 324: 126-245.
[10]
Amorim R C D, Mirkin B. Selecting the Minkowski exponent for intelligent K-means with feature weighting[M]. Clusters, Orders, Trees: Methods and Applications, Optimization and its Applications. Berlin: Springer, 2014: 103-117.
[11]
Tsai C Y, Chui C C. Developing a feature weight self-adjustment mechanism for a K-means clustering algorithm[J]. Computational Statistics Data Analysis, 2008, 52(10): 4685-4672. DOI:10.1016/j.csda.2008.03.020
[12]
Chen X, Ye X, Xu X, et al. A feature group weighting method for subspace clustering of high-dimensional data[J]. Pattern Recognition, 2012, 45(1): 434-446.
[13]
Ji J C, Bai T, Zhou C G, et al. An improved K-prototypes clustering algorithm for mixed numeric and categorical data[J]. Neurocomputing, 2013, 120(22): 590-596.
[14]
陈爱国, 王士同. 基于多代表点的大规模数据模糊聚类算法[J]. 控制与决策, 2016, 31(12): 2122-2130.
(Chen A G, Wang S T. Fuzzy clustering algorithm based on multiple medoids for large-scale data[J]. Control and Decision, 2016, 31(12): 2122-2130.)
[15]
李向丽, 耿鹏, 邱保志. 混合属性数据集的聚类边界检测技术[J]. 控制与决策, 2015, 30(1): 171-175.
(Li X L, Geng P, Qiu B Z. Clustering boundary detection technology for mixed attribute data set[J]. Control and Decision, 2015, 30(1): 171-175.)
[16]
Anaraki F P, Becker S. Preconditioned data sparsification for big data with applications to PCA and K-means[J]. IEEE Trans on Information Theory, 2017, 63(5): 2954-2974.
[17]
Chiang M M, Mirkin B. Intelligent choice of the number of clusters in k-means clustering: An experimental study with different cluster spreads[J]. J of Classification, 2010, 27(1): 1-38.
[18]
李武, 赵娇燕, 严太山. 基于平均差异度优选初始聚类中心的改进K-均值聚类算法[J]. 控制与决策, 2017, 32(4): 759-762.
(Li W, Zhao J Y, Yan T S. Improved K-means clustering algorithm optimizing initial clustering centers based on average difference degree[J]. Control and Decision, 2017, 32(4): 759-762.)
[19]
王莉, 周献中, 沈捷. 一种改进的粗K均值聚类算法[J]. 控制与决策, 2012, 27(11): 1711-1719.
(Wang L, Zhou X Z, Shen J. An improved rough K-means clustering algorithm[J]. Control and Decision, 2012, 27(11): 1711-1719.)