一种带权的混合数据聚类个数确定算法
李顺勇 张苗苗
【摘 要】摘 要 混合数据的聚类过程中通常面临一个不可回避的问题：聚类个数的确定。基于Liang k-prototype算法引入属性权重，重新定义混合数据缺失某类的类间熵和(SBAE_M)、有效性指标(CUM) 及相异性度量。提出一种带权的混合数据聚类个数确定算法。该算法的基本思想是：用newk-prototype算法将混合数据进行聚类，计算其聚类结果的CUM及SBAE_M，将最坏的类剔除，并将该类中的对象用新的相异性度量进行重新分配，CUM最大时包含的类别数即为聚类个数。在5个UCI数据集上验证了该算法的有效性。 【期刊名称】计算机应用与软件 【年(卷),期】2019(036)001 【总页数】7
【关键词】关键词 聚类个数 混合数据 属性权重 有效性指标
国家自然科学基金项目(61573229)；山西省基础研究计划项目(201701D121004)；山西省回国留学人员科研项目(2017-020)；山西省高等学校教学改革创新项目(J2017002)。
0 引 言
聚类分析是一种无监督学习，聚类个数是提前不确定的。因此，确定聚类个数是聚类分析的一个重要课题。针对数值型数据，文献[1]是基于FCM算法[2]的自动确定聚类个数的算法，通过比较不同参数下的有效性指标的大小来确定类别个数。文献[3]提出一种基于层次划分的最佳聚类数确定方法，该算法通过寻找一条聚类质量曲线的极值点来估计最佳聚类个数，并提出一种新的有效性指
标。文献[4]提出了一种用于数值数据的凝聚的模糊k-means聚类算法，是对标准模糊k-means算法的扩展，通过在目标函数中引入惩罚项来使聚类过程对数据不敏感。文献[5]提出了一种利用信息论和自上而下的层次聚类算法在数据集中查找聚类数的新方法。该算法从大量集群开始，在每次迭代中减少一个集群，然后将其数据点分配给其余集群。最后，通过测量信息势，检测所需数据集中的确切类别数。针对分类型数据，文献[6]通过研究分类型数据的熵特性提出一种确定类别数的层次聚类算法。实验结果表明，该方法能够有效地识别显著的聚类结构。文献[7-8]也是对分类型数据聚类个数的研究。
但日常生活中我们接触的数据大部分是混合数据，即数据集中既有数值型数据也有分类型数据。文献[9-13]对混合型数据进行了聚类，但都得预先设定聚类个数。而对混合型数据集聚类个数的研究就相对发展得慢了一些，文献[14]基于信息熵提出了确定聚类最佳个数的算法，该算法提出了改进的k-prototype，并通过将类内熵[15]与类间熵[16]结合建立了一种广义机制，最后定义了有效的聚类有效性指标。但Liang的算法中目标函数只考虑了数值型属性、分类型属性以及总的属性个数，而没有反映各个属性的重要度。文献[17]提出的是基于属性加权的分类数据聚类算法。而本文改进了Liang k-prototype聚类算法，在其基础上考虑属性重要度，通过加权方式提出了混合数据聚类个数算法，并在4个UCI数据集上验证了k-prototype聚类改进算法的有效性。
1 相关研究
本节是对Huang[18] k-prototype聚类算法及Liang等[19]改进的k-prototype算法的回顾。
Huang较早提出了k-prototype 算法来处理混合型数据集。该算法融合了k-
means算法和k-modes算法，其中k-modes算法中对分类型数据的处理采用了0、1匹配的方式。该算法使得以下目标函数达到最小： (1) 式中：
为了方便研究，本文对Huang的目标函数进行重新改写： D(x,y)=DAnum(x,y)+γDAcat(x,y) (2)
式中：DAnum(x,y)代表数值型属性的值，DAcat(x,y)代表分类型属性的值。 文献[19]实质上也是γ的变异。首先，他将Renyi熵[15]与互补熵[19]整合起来，提出了一个可以将最坏类剔除的广义性机制；其次，为了评价聚类结果的好坏，定义了一个聚类有效性指标CUM；最后，在改进的k-prototype算法[14]基础上提出了混合数据聚类个数确定算法。其相关概念定义如下：
定义1 设NDIS=
BE_N(Ci,Cj)表示不同类Ci,Cj的类间熵，熵越大表示类间不确定性越大，分散度越大。因此，定义的SBAE_N值越大，表示缺失一类后的类间分散度越大，聚类效果越好。而类间熵又由Renyi熵[15]来定义，Renyi熵可通过Parzen窗
一种带权的混合数据聚类个数确定算法
