一种基于属性值权重的k-modes聚类分析算法.pdf

2023 年第 5 期计算机与数字工程收稿日期：2022年11月11日，修回日期：2022年12月21日作者简介：郝荣丽，女，硕士研究生，研究方向：数据挖掘。胡立华，女，博士，副教授，研究方向：数据挖掘。一种基于属性值权重的 k-modes 聚类分析算法郝荣丽胡立华（太原科技大学计算机科学与技术学院太原030024）摘要针对k-modes方法未考虑各属性值在属性空间的分布特征而导致分类变量间差异性度量不准确的问题，提出了一种基于属性值权重的k-modes聚类分析算法。该算法利用属性值之间的差异和属性值的权重，重新定义了相异度度量公式；采用属性值频率和各属性值的权重，给出一种聚类中心更新迭代公式，有效地体现了属性值在属性空间中的分布特征和属性之间的重要性差异；采用UCI数据集，验证了算法的有效性。关键词聚类分析；k-modes；属性值权重；属性值频率；相异度度量中图分类号TP311DOI：10.3969/j.issn.1672-9722.2023.05.005A K-modes Clustering Algorithm Based on Attribute Value WeightHAO RongliHU Lihua（School of Computer Science and Technology，Taiyuan University of Science and Technology，Taiyuan030024）AbstractAiming at the problem that the k-modes method does not consider the distribution characteristics of each attributevalue in the attribute space，which leads to the inaccurate measurement of the difference between categorical variables，a k-modesclustering analysis algorithm based on attribute value weights is proposed.The algorithm uses the difference between attribute valuesand the weight of the attribute value to redefine the dissimilarity measurement formula，adopts the frequency of the attribute valueand the weight of each attribute value to give an iterative formula for updating cluster centers，which effectively reflects the distribution characteristics of attribute values in the attribute space and the importance difference between attributes.UCI data set is used toverify the effectiveness of the algorithm.Key Wordsclustering analysis，k-modes，attribute value weight，attribute value frequency，dissimilarity measureClass NumberTP3111引言聚类分析是数据挖掘和机器学习等领域中的主要研究内容之一，它是将物理或抽象的数据对象根据某种相似准则划分成多个对象类的过程，使得同一个类中的对象之间具有较高的相似性，而不同簇中的对象具有较高的相异性1，并已经广泛地应用在基因分类2、股市波动的特征分析3、天光光谱特征分析4、文档的分类5、图像处理6等许多领域。聚类分析主要分为划分聚类7、层次聚类8、密度聚类9和网格聚类10。k-means算法11是一种经典、常用的划分聚类算法，具有简单高效，易于理解和实现等优点，但在实际应用中，由于存在大量的分类型数据，k-means方法不能处理包含分类属性的数据集，限制了其实际应用领域。k-modes12作为k-means聚类分析算法的一种扩展，可适用于含有分类属性的数据集，具有计算简单、复杂度低等优点，但该聚类算法采用简单匹配差异法，未能充分体现数据集的分布特征，将所有属性视为同等地位，忽略了属性之间的重要性差异，若频率最高的属性值有多个，传统k-modes算法无法选出最恰当的属性值作为该簇模式。本文利用粗糙集中的等价类计算属性值权重的思想，提出了一种k-modes聚类分析算法。由于该算法充分利用了属性值在数据集中的分布特征与属性值自身的差异，有效地解决了属性值之间的差异性度量，并利用属性值频率和各属性值的权重，给出一种聚类中心更新途径，从而有效地提高了聚类分析总第 403期2023 年第 5期计算机与数字工程Computer&Digital EngineeringVol.51No.51001第 51 卷的效果。本文主要贡献为1）利用属性值之间的差异和属性值的权重，重新定义了相异度度量公式；2）采用属性值频率和各属性值的权重，给出了一种聚类中心更新迭代公式；3）提出了一种基于属性值权重的 k-modes聚类算法。2相关工作k-modes作为k-means算法的一种扩展，根据分类数据的特点，采用简单的0-1匹配法来度量分类数据间的距离，用模式代替均值，但是这种采用简单匹配差异法忽略了属性之间的差异性，导致差异性度量不准确。对k-modes改进的典型成果为：He13等使用属性值在类内出现的频率提出新的类内属性距离计算公式；Hsu14等提出一种基于概念层次的方法来计算属性值之间的距离，但该方法需要专家经验；贾彬15等使用信息熵为属性加权来解决属性之间的差异问题，但是该方法在确定属性权重时只考虑了某一属性的分布，没有考虑相关属性对其的影响；白亮16等利用粗糙集中的上、下近似提出了一种新的相似性度量，改善了聚类效果，却提高了计算的复杂度；赵亮17等基于朴素贝叶斯分类器中间运算结果计算属性值之间的距离；黄苑华18等基于相互依存的冗余理论提出一种新的距离公式，采用内部距离和外部距离共同衡量两个对象属性值之间的距离，在进行外部距离计算时，仅从相关属性的角度对属性值在整个数据集上的分布情况进行描述，导致差异性度量不准确，这些算法不能够准确应用属性空间中数据间的关系，因而会丢失数据间的相似关系。针对传统k-modes算法中的模式问题，贾彬15提出了多属性值modes的相异度度量方法，每个属性都保留全部属性值和其出现频率，但这样也使得数据对象与modes之间的距离计算变得复杂化。综上所述，k-modes虽然将k-means聚类分析算法应用范围扩展到了分类数据集，但其多种距离度量都无法有效地度量分类数据之间的距离，未能充分体现分类变量间的差异，以及在整个数据集中的分布特征。3聚类目标函数与多属性权重为适用于分类数据的聚类分析，Huang 等于1998年提出了k-modes聚类算法，给定一组分类数据对象X=x1x2xn和整数k（kn），数据集随机初始划分成k个互斥的簇，对数据对象迭代重定位簇，最终搜索得到使簇内平方误差和，即目标函数F最小化的k个互斥的簇，参照文献 12，其目标函数定义如下：聚类目标函数为F()WZ=l=1ki=1nwild()xi，zl（1）在式（1）中，W是一个nk的01矩阵，n表示数据集U中数据点的个数，k表示聚类的个数，Z=z1z2zk，zl为第 l 个类的中心点，zl=zl1zl2zlm，zlm是第l个类的第m个属性上出现频率最高的属性值，d()xi，zl为简单的0-1匹配计算得出的分类变量间的距离。多属性值权重是属性值在属性空间中分布特征的体现，可从本地属性和相关属性两个角度，来有效地刻画属性值在属性空间上的分布特征。则参照文献 19，相关概念如下：对于任意 aiA，设xkiVai，从本地属性ai的角度度量xki的单属性权重为Wai()xki=|xkainlg|xkai1-|xkain+1（2）从相关属性aj的角度度量xki的多属性权重为Waj()xki=|xkaj xkai|xkai（3）结合本地属性和相关属性定义属性值的权重为W()xki=Wai()xki j=1jidWaj()xki2k=1nWai()xki j=1jidWaj()xki2（4）其中：xkai表示数据对象xk在属性ai的等价类，|xkaj xkai表示属性值xki和xkj的共现次数。属性值权重W()xki体现了属性值在整个属性空间中的分布特征。4基于属性值权重的 k-mode 聚类分析两个数据对象同一属性下两个值之间是否相郝荣丽等：一种基于属性值权重的k-modes聚类分析算法10022023 年第 5 期计算机与数字工程似既取决于属性值本身，又取决于其所处的环境，即属性值所处的属性空间16。可利用属性值的权重来表示属性空间的分布特征对属性值相异度的影响，即外部相异度；同时，也需考虑属性值本身之间的差异性，即内部相异度。因此，数据对象属性值之间的相异度是由外部相异度和内部相异度共同决定，其相异度越大，距离也越大。设xi和xj为数据集中的任意两个数据对象，at为任一属性，则参照文献 18，数据对象xi和数据对象xj在属性at上的相异度度量公式重新定义如下：d()xitxjt=12d1()xitxjt+12d2()xitxjt（5）在式（5）中，d1()xitxjt表示两个数据对象属性值本身的差异度，即内部相异度；d2()xitxjt表示两个数据对象在整个属性空间中分布的差异度，即外部相异度；12表示两种差异度的重要性相当，共同决定了属性值之间的距离，差异度越高，距离越远。参照文献 18，数据对象xi和数据对象xj在属性at上的内部相异度的度量公式如下：d1()xitxjt=1xitxjt0 xit=xjt（6）在式（6）中，使用简单0-1匹配来计算两个属性值间的内部相异度。由式（4）引入的属性值权重，可得出第i个数据对象和第j个数据对象在属性at上的外部相异度的度量公式如下：d2()xitxjt=|W()xit-W()xjt（7）式中W()xit，W()xjt分别代表属性值xit和xjt对应的权重，用权重的差值来表示他们之间的外部相异度。传统的 k-modes算法在每个簇的每个属性上选择出现次数最多的属性值作为该簇中心点在该属性上的值，但是属性上出现频率高的属性值有多个的话难以获得最合适的中心点，因此，利用属性取值的频率以及属性值的权重，重新描述类中心，并找出类中心对应的平均权重，从而可有效提高聚类精度。聚类族中心和对应的平均权重定义如下：定义1 类l中某属性at上某一属性值的平均权重为该类中属性at对应的该属性值的所有权重之和的平均值。定义2 类l的中心为zl=zl1zl2zlm，其中zlm为类l中数据对象在属性am上出现频率最高的，且具有最高平均权重w 的属性值。每一个中心点对应一个平均权重集-wl=-wl1-wl2-wlm平均权重集代表模式中每个属性值在属性空间中的分布情况。5基于属性值权重的 k-mode 聚类算法根据第3节和第4节的描述，在分类型数据集中，采用重新定义的相异度度量方式以及聚类簇中心选择的聚类分析基本步骤为利用粗糙集中的等价类，计算数据集中所有数据对象的属性值的属性权重；随机选择数据集U中k个数据点作为初始的聚类中心；计算数据集中所有数据对象与k个聚类中心之间的相异度，然后将每个对象分配到与其相异度最小的聚类中心所在的簇中；在得到的k个簇中，更新簇的中心点及其对应的权重；重复上述两个步骤，直到目标函数达到最小值，k个簇的类中心不再发生变化为止。算法伪代码描述如下：算 法：MCAMAW（K-modes clustering algorithm basedon multiple attribute weights）输入：分类数据集，簇的个数k输出：聚类簇1）for（int i=0；in；i+）2）for（int j=0；jm；j+）3）利用xit在属性at上的等价类，根据式（2）（4）计算出属性值xit的属性权重W()xit。4）5）6）随机初始找出k个簇中心，平均权重集为其对应的属性值的权重7）for（int i=0；in；i+）8）for（int cu=0；cuk；cu+）9）for（int j=0；jm；j+）10）根据式（5）（7）计算出所有数据对象与簇中心之间的距离，然后将各个数据对象11）分配到离其最近的簇中。12）13）for（int cu=0；cuk；cu+）14）根据定义1和定义2更新各个簇的中心及其平均权重集15）16）重复第7）步到第17）步，直至式（3）达到最小值，k个簇的类中心不再发生变化为止17）返回聚类簇1003第 51 卷6实验结果及分析为了验证所提 MCAMAW 算法的有效性，从UCI数据集中选取Mushroom、Vote、Breast-cancer三个数据集，详见表1所示。采用python语言实现了MCAMAW 算法、传统 k-modes算法12和基于相互依存冗余度量k-modes算法18，并分别从分类正确率、分类精度和召回率三个指标进行评价。表1UCI数据集数据集MushroomVoteBreast-cancer数据对象数8124435699属性个数22169类别数222表2Mushroom数据集评估指标ACPEREHuangsk-modes0.71640.73790.7129基于相互依存冗余度量k-modes0.75490.77490.7512MCAMAW算法0.79110.80820.7916表3Vote数据集评估指标ACPEREHuangsk-modes0.86050.85620.8742基于相互依存冗余度k-modes0.86520.86070.8795MCAMAW算法0.86550.95610.8799表4Breast-cancer数据集评估指标ACPEREHuangsk-modes0.81600.83410.8041基于相互依存冗余度k-modes0.86340.86900.8435MCAMAW算法0.87530.89340.8633表24给出了MCAMAW算法与传统k-modes算法12和基于相互依存冗余度量k-modes算法18的实验比较结果。可以看出在 Mushroom、Vote、Breast-cancer数据集上MCAMAW算法的三个指标均有所提高，聚类效果也优于其他两个算法。其主要原因是 MCAMAW 算法充分利用数据对象在数据集中的空间特征，准确地描述了数据对象之间的关系，有效地避免了其他两个对比算法中分类数据对象之间距离度量不准确的问题。7结语本文采用多属性权重，提出了一种k-modes聚类算法。该算法从本地属性和相关属性两个角度，描述了数据对象的属性空间分布特征。在度量数据对象间的距离时，不仅考虑了数据对象本身的差异性，而且考虑了数据对象在整个属性空间结构中的差异性。此外，在属性值分布过于分散或相对均等时，可以根据属性值的平均权重进一步确定模式中的属性值，以便能够找到更恰当的属性值作为该类的模式，从而有效地提高聚类效果。参 考 文 献1Jain A K，Murty M N，Flynn P J.Data clustering：a review J.ACM Computing Surveys，1999，31（3）：264-323.2贾瑞玉，宋飞豹，汤深伟.双精英遗传策略的基因聚类算 法J.小 型 微 型 计 算 机 系 统，2020，41（07）：1375-1380.JIA Ruiyu，SONG Feibao，TANG Shenwei.Gene clustering algorithm based on double-elite genetic strategyJ.Small Microcomputer System，2020，41（07）：1375-1380.3王峥，温光洒，邱秀连.基于粗糙集和动态模糊神经网络的股市预测研究 J.计算机与数字工程，2020，48（03）：517-522.WANG Zheng，WEN Guangsa，QIU Xiulian.Research onstock market forecasting based on rough set and dynamicfuzzy neural networkJ.Computer and Digital Engineering，2020，48（03）：517-522.4蔡江辉，杨雨晴，杨海峰，等.基于轨迹聚类的天光光谱特征分析J.光谱学与光谱分析，2019，39（04）：311-316.CAI Jianghui，YANG Yuqing，YANG Haifeng，et al.Characteristic analysis of skylight spectrum based on trajectory clusteringJ.Spectroscopy and Spectral Analysis，2019，39（04）：311-316.5Yan W，Zhang B，Ma S，et al.A novel regularized concept factorization for document clusteringJ.Knowledge-Based Systems，2017，135：147-158.6孟磊，张素兰，胡立华，等.基于低秩稀疏分解优化的图像标签完备 J.计算机辅助设计与图形学学报，2020，32（01）：36-44.MENG Lei，ZHANG Sulan，HU Lihua，et al.Completeimage labeling based on low-rank sparse decompositionoptimizationJ.Journal of Computer Aided Design andGraphics，2020，32（01）：36-44.7赵文冲，蔡江辉，赵旭俊，等.一种影响空间下的快速K-means聚类算法 J.小型微型计算机系统，2016，37（09）：2060-2064.ZHAO Wenchong，CAI Jianghui，ZHAO Xujun，et al.Afast K-means clustering algorithm under influence spaceJ.Small Microcomputer System，2016，37（09）：（下转第1119页）郝荣丽等：一种基于属性值权重的k-modes聚类分析算法10042023 年第 5 期计算机与数字工程pact in Steganography Using Trellis-Coded QuantizationA.Proceedings of SPIE，Media Forensics and Security II C.2010，SPIE 7541：501-514.13Pevn T，Filler T，Bas P.Using High-Dimensional Image Models to Perform Highly Undetectable SteganographyA.Proceedings of the 12th International Workshop on Information HidingC.2010，Springer LNCS6387：161-177.14Pevn T，Bas P，Fridrich J.Steganalysis by SubtractivePixel Adjacency Matrix J.IEEE Transactions on Information Forensics and Security，2009，5（2）：215-224.15Lee S E.Essays About Computer SecurityM.Cambridge：University of Cambridge Computer Laboratory，1999.2060-2064.8Perret B，Cousty J，Silvio Jamil Ferzoli Guimares，et al.Removing non-significant regions in hierarchical clustering and segmentationJ.Pattern Recognition Letters，2019，128：433-439.9刘亚梅，闫仁武.一种基于密度聚类的分布式离群点检测 算 法J.计 算 机 与 数 字 工 程，2019，47（06）：1320-1325.LIU Yamei，YAN Renwu.A distributed outlier detectionalgorithm based on density clusteringJ.Computer anddigital engineering，2019，47（06）：1320-1325.10聂瑶瑶，胡立华，张继福，等.基于网格多密度的古建筑图像特征匹配方法 J.计算机辅助设计与图形学学报，2020，32（03）：437-444.NIE Yaoyao，HU Lihua，ZHANG Jifu，et al.An ancientarchitectural image feature matching method based ongrid multi-densityJ.Journal of Computer Aided Design and Graphics，2020，32（03）：437-444.11周爱武，于亚飞.K-Means聚类算法的研究 J.计算机技术与发展，2011，21（2）：62-65.ZHOU Aiwu，YU Yafei.Research on K-Means Clustering AlgorithmJ.Computer Technology and Development，2011，21（2）：62-65.12Huang Z.Extensions to the K-means algorithm for clustering large data sets with categorical valuesJ.DataMining and Know ledge Discovery，1998，2（3）：283-304.13He Z，Deng S，Xu X.Improving k-modes algorithm considering frequencies of attribute values in mode C/International Conference on Computational Intelligenceand Security，LNAI3801，2005：157-162.14Hsu C C，Chen C L，Su Y W.Hierarchical clustering ofmixed data based on distance hierarchy J.InformationSciences，2007，177（20）：4474-4492.15贾彬，梁毅，苏航.一种改进的 K-Modes 聚类算法J.软件导刊，2019，18（06）：60-64.JIA Bin，LIANG Yi，SU Hang.An improved K-Modesclustering algorithm J.Software Guide，2019，18（06）：60-64.16白亮，梁吉业，曹付元.基于粗糙集的改进K-modes聚类算法 J.计算机科学，2009，36（1）：162-164.BAILiang，LIANGJiye，CAOFuyuan.ImprovedK-modes clustering algorithm based on rough setJ.Computer Science，2009，36（1）：162-164.17赵亮，刘建辉，张昭昭.基于贝叶斯距离的K-modes聚类 算 法J.计 算 机 工 程 与 科 学，2017，39（01）：188-193.ZHAO Liang，LIU Jianhui，ZHANG Zhaozhao.K-modesclustering algorithm based on Bayesian distanceJ.Computer Engineering and Science，2017，39（01）：188-193.18黄苑华，郝志峰，蔡瑞初，等.基于相互依存冗余度量的 k-modes 算法 J.小型微型计算机系统，2016，37（08）：1790-1793.HUANG Yuanhua，HAO Zhifeng，CAI Ruichu，et al.K-modes algorithm based on interdependence redundancy measure J.Small Microcomputer System，2016，37（08）：1790-1793.19庞宁，张继福，秦啸.一种基于多属性权重的分类数据子空间聚类算法J.自动化学报，2018，44（03）：517-532.PANG Ning，ZHANG Jifu，QIN Xiao.A subspace clustering algorithm for categorical data based on multi-attribute weightsJ.Acta Automatica Sinica，2018，44（03）：517-532.（上接第1004页）1119