| 标题 | 基于多属性模糊C均值聚类的属性约简算法 |
| 范文 | 李诗瑾 李倩 徐桂琼 摘 要： 模糊C均值聚类算法在处理高维数据集时，存在计算复杂度高，算法泛化能力差，计算精度低等问题。考虑到特征属性对聚类的贡献程度的差异，在多属性模糊C均值聚类的思想上，提出一种基于属性重要性的约简算法。为验证有效性，在UCI数据集上，将新算法与因子分析法和粗糙集理论约简方法进行比较分析。实验结果表明，该方法具有更好的泛用性，在平均标准差大或类间中心距离较远的数据集上具有更好的性能。 关键词： 数据挖掘； 模糊C均值聚类； 属性约简； 聚类效果 中图分类号： TN911.1?34； TP391 文献标识码： A 文章编号： 1004?373X（2017）21?0112?05 Attribute reduction algorithm based on multiattribute fuzzy C?means clustering LI Shijin， LI Qian， XU Guiqiong （School of Management， Shanghai University， Shanghai 200444， China） Abstract： The fuzzy C?means clustering algorithm used to process the high?dimensional datasets has the problems of high computational complexity， poor algorithm generalization ability and low calculation accuracy. Considering the difference of feature attribute for clustering contribution， a new reduction algorithm based on attribute importance is proposed on the basis of the thought of multiattribute fuzzy C?means clustering. In order to verify its validity， the comparative analysis was performed in UCI datasets for the proposed algorithm， factor analysis method and reduction method based on rough set theory. The experimental results show this method has wider application range， and better performance on the datasets whose average standard deviation is large or the inter?class centre distance is far. Keywords： data mining； fuzzy C?means clustering； attribute reduction； clustering effect 0 引 言 随着大数据时代的到来，各行各业中都累计了海量和高维度的数据资料。数据挖掘技术可以从这些大量的数据中挖掘出有价值的信息[1]，而这些高维度的数据资料却对目前大多数数据挖掘算法的效果造成了严重的阻碍， 这种阻碍被称之为 “维数灾难”[2]。数据降维，又称属性约简，是一种有效解决维数灾难的方法，它将原有高维空间上的点映射到低维空间，在不降低精度的前提下剔除冗余属性对挖掘所造成的误差，提高挖掘任务的效率与精度。常见的方法有主成分分析（PCA）、因子分析、线性判别分析（LDA）、局部线性嵌入算法（LLE）和粗糙集理论等[3?4]。因子分析可以看作是 PCA 的进一步推广，它从研究变量内部依赖关系出发，把一些具有错综复杂关系的变量归结为少数几个综合因子的一种多变量统计分析方法，能在损失很小信息的前提下减小维数。但是在使用前需要进行KMO统计量检验，当KMO小于0.6时，数据集不适合通过因子分析进行属性重要性排序[5]。粗糙集理论最早由Pawlak提出，是一种处理不确定信息的数据分析方法[6]。它根据已有的信息或知识对论域进行划分，在保证知识库的分类能力不变的条件下，剔除冗余与不相关的特征。然而，大多数据集具有连续属性值，若通过离散化方法来构造等价类，往往无法得到较合理的划分[7]。另外，粗糙集是一种监督的属性约简算法，在决策属性缺失的情况下并不适用。 模糊C均值聚类（FCM）最早由Bexdek提出，是聚类分析中最流行的算法之一，其主要思想是将数据集中的样本划分成为不同的子集，使得相似的样本尽可能划分到同一类，不相似的样本则归为不同类[8]。最早的FCM通过欧式距离度量样本与原型之间的相似性，未考虑到样本的不同属性之间有差别，无法检测超球体。文献[9]提出用马氏距离替代欧式距离，可以满足不同度量单位数据的要求。文献[10]在传统目标函数聚类方法的思想上提出基于统计特征加权的FCM算法。文献[11]针对FCM算法容易陷入局部极值等缺陷，提出了基于改进QPSO的FCM方法。虽然这些优化算法能有效地解决传统FCM在度量相似性上的缺陷，但是它们却没有考虑不同属性对簇划分的贡献是不同的。 文献[12]提出一种多属性FCM算法（MFCM），它从数据集中提取了更多属性对于聚类的信息，提高了聚类质量。受该研究工作的启发，本文在MFCM算法的基础上，提出一种基于属性重要性的约简算法（ARI）。该算法通过对属性重要性进行排序，剔除对聚类无关或贡献较小的属性，从而提高二次聚类的精度。实验证明，ARI算法可以有效剔除冗余属性，并且其属性约简效果随着平均类间距离和平均类间标准差的增大而上升。 1 模糊C均值聚类 FCM的基本思想是将[n]个样本[X=x1，x2，…，xn]分为[c]个簇，簇心用[V=v1，v2，…，vc]表示。通过建立表示样本数据点与聚类簇心之间加权相似性测度的目标函数，并对其进行迭代最小化，最终确定最佳的聚类结果。聚类结果通过模糊隶属度矩阵[U=uik∈R，][i=1，2，…，c；][k=1，2，…，n]表示。FCM算法的目标函数[J]可由式（1）给出[13?14]： [minJ（U，V）=i=1c k=1numikxk-vi2] （1） 其中：[uik]表示样本点[xk]属于第[i]个类的隶属程度，它反映了样本点与簇的相似程度，若接近1，表示属于此类的程度高；若接近0，表示属于此类的程度低。[m]代表加权指数（模糊指标），[1 （2） [0 在满足条件（3）的前提下，根据Lagrange乘子法，可以得到目标函数取得极小值的必要条件为： [uik=j=1cxk-vixk-vj2m-1-1， i≠j] （2） [vi=k=1nuikmxkk=1nuikm] （3） FCM算法的具体步骤如下： 输入：数据集、聚类个数[c、]模糊度[m、]迭代阈值[ε、]最大迭代次数[T] 输出：[U，V] 步骤一：随机初始化聚类中心[V，]令[t=0。] 步骤二：根据式（2）更新隶属度矩阵[U，]代入式（3）更新聚类簇心[V。] 步骤三：若[t=T]或[vi，t-vi，t-1≤ε，]则停止；否则，重复步骤二，并且置[t=t+1。] 2 基于MFCM的属性约简算法 2.1 属性重要性 FCM算法以样本点与聚类中心之间的欧式距离作为相似性指标，默认每一个属性对聚类作出的贡献相等。图1包含10个样本点，该图直观地表现出不同属性对于聚类的贡献程度不同：假设样本1～5属于第一个簇，样本6～10属于第二个簇。通过FCM算法得样本5隶属于簇2的程度却要高于簇1。分别考虑属性[x]和[y]可以发现，当仅考虑属性[x]时，样本5属于簇1的程度高；当仅考虑属性[y]时，样本5属于簇2的程度高。由此可见，不同属性对于聚类有着不同的贡献程度，样本的每个特征属性并不都对聚类结果起决定性作用[11]。 2.2 MFCM算法 Pimentel和Souza考虑到FCM算法在计算隶属度时，默认样本的每个属性对于聚类的贡献均相同。因此需要进一步细化在数据样本中每个属性对于分簇的贡献程度。假设数据集[X]中的每个样本包含[p]个特征属性，样本点可记作[xk=x1k，x2k，…，xpk，k∈1，2，…，n，] 簇心记为[vi=vi1，vi2，…，vip， i∈1，2，…，c]。目标函数[J]则调整为： [minJU，V=i=1c k=1n j=1pumijkxjk-vij2] （4） 此时的目标函数考虑到每一个属性的累计贡献，通过基于属性[j]计算样本[xk]距离簇心[vi]的距离。考虑到不同属性对于聚类的贡献程度，基于每一个属性计算对象的隶属度： [uijk=h=1cl=1pxjk-vijxlk-vhlA2m-1 -1，i≠h，j≠l] （5） 式中[uijk]代表样本[xk]在属性[j]上隶属于簇[vi]的程度，需要满足以下限制条件： （1）[uijk∈[0，1]， i=1，2，…，c； k=1，2，…，n； j=1，2，…，p；] （2） [0 此时，簇心可由式（6）计算得出： [vij=k=1nuijkmxkjk=1nuijkm] （6） MFCM算法实则是将传统的FCM中的样本属于不同簇的隶属度拓展成一个样本基于每个属性在不同簇的隶属度，将传统FCM隶属度矩阵的每个行向量替换为一个[p×c]矩阵，如式（7）所示，MFCM累加所有属性的隶属度得到每个样本的隶属度用于分簇。 [uik=j=1puijk] （7） 2.3 基于MFCM的屬性约简算法 MFCM算法虽然考虑了不同属性对于聚类的贡献程度，但仍保留了所有属性，冗余属性的存在影响了聚类的效率和精度。由此，本文在MFCM的基础上提出一种属性约简算法，计算每一个样本的不同属性对整体聚类的重要性，并根据重要性大小，在不降低聚类精度的条件下，选择剔除对聚类贡献程度较低的几个属性，用于属性约简。 ARI属性约简算法的具体步骤如下： 输入：数据集[X、]聚类数量[c、]模糊度参数[m、]迭代阈值[ε、]最大迭代次数[T] 输出：[U，V，A，]约简后的数据集指标 步骤一：随机初始化隶属度矩阵[U=uijk，]满足限制条件[i=1c j=1puijk=1，uijk∈[0，1]]。 步骤二：固定[uijk，]根据式（6）更新原型矩阵[V=vij]。 步骤三：固定[vij，]根据式（5）更新隶属度矩阵[U=uijk]。 步骤四：当[t=T]或[Jt-Jt-1≤ε]时执行步骤五；否则，重复步骤二和步骤三，并且置[t=t+1。] 步骤五：通过式（8）计算[A=[aj]，j=1，2，…，]其中[aj]表示属性[j]对聚类的重要性。 [aj=k=1n i=1cuijk] （8） 步骤六：对属性的重要性[aj]进行降序排列，排序高的属性对FCM聚类时的重要性高，反之，对聚类重要性低。 步骤七：剔除若干个排序较低的[aj]属性，只留下[y]个对聚类有意义的属性，使得属性约简后的聚类有效性指数最高。本文ARI算法选取RI指数[15]作为有效性指标，比较计算删除[y]个属性后二次聚类的RI值，选择使得RI值最大的[y]个属性作为约简结果。具体属性约简方法可参照实验3.2节，以数据集wine为例介绍属性筛选的过程。 3 实验与结果分析 3.1 实验数据集 为测试算法的有效性和泛用性，本文选取UCI公开数据库中的五个带标签的具有连续属性的数据集，即Wine，Iris，Seeds，Pima Indians diabetes，Abalone。数据集分簇后的平均类间中心距离和平均标准差可以表示数据集的分布特点。五个数据集及聚类特征分布如表1所示。 3.2 ARI属性约简 实验通过参考FCM并使用Matlab软件编写ARI算法，这里以Wine数据集为例说明ARI属性约简算法，表2给出属性重要性排序结果。 选择排序较高的[y]个属性做二次聚类，并计算聚类精度，本文利用RI指数作为聚类有效性指标，结果如表2所示，通过计算取不同属性个数的聚类结果的RI值，如图2所示，发现当筛选的属性个数[y=3]时，聚类效果最好。对于Wine数据集，选择Nonflavanoid phenols，Ash和Hue三个属性做二次聚类时的精度最高，ARI算法能起到属性约简的作用。 3.3 不同属性约简算法的对比实验 本文运用ARI算法与因子分析法、粗糙集理论进行属性约简，三种算法的比较结果如表3所示。 从表3中可以发现，由于因子分析与粗糙集理论自身的缺陷，无法绝对地对连续的数据集进行属性约简。在Iris数据集中，KMO统计量为0.536，不适合作因子分析；在Seeds和Pima数据集中，对数据离散化之后，无法通过粗糙集理论找到等价条件，删除冗余属性。ARI方法能够通过计算每个属性在聚类时的贡献度，剔除重要性较低的属性，留下能使得聚类精度最高的[y]个属性，不受到方法自身缺陷的约束。 对约简后的五个数据集进行二次聚类，并利用Rand指数比较聚类结果的有效性，结果如图3所示。实验结果表明，对于每一个数据集，对其中4个数据集基于ARI算法的聚类效果均有一定的提升，仅对于Iris数据集，新算法相比于粗糙集约简结果略差，原因在于属性个数较小，易于数据的离散化，而对于属性个数较多的数据集，该方法使用范围有限。 3.4 实验结果分析 从图4可以看出，当数据集的连续属性平均标准差较小，即属性分布差别不大的情况下，通过因子分析和粗糙集理论得到的约简属性用于聚类效果要优于本文提出的ARI约简算法，但是随着数据集的属性平均标准差的增大，粗糙集和因子分析法的聚类效果要逐渐劣于本文算法。依据RI的提升率趋势发现，ARI的聚类效果随着数据集平均标准差的增大而增大。 从图5可以看出，当数据集类间平均中心距离较小的情况下，通过因子分析和粗糙集理论得到的属性约简后的聚类效果要优于ARI约简算法，但是随着类间中心距离的增大，其属性约简的效果要逐渐劣于本文算法。随着类间中心距离的增大，ARI聚类效果有所提升。因此，在平均类间中心距离较大的情况下可以考虑本文的算法做属性约简。 雖然粗糙集约简对于某些数据集可以筛选出有意义的特征属性，但是由于只能对带有标签的数据集进行约简，并且对于连续性属性需要先进行离散化，因此使用范围有限。虽然因子分析能筛选出具有连续性属性且无标签的数据集中有意义的特征属性，但是当KMO值接近0时，意味着样本间的相关性越弱，数据集越不适合做因子分析。ARI虽然在某些时候表现劣于前两者，但是无其他使用限制条件，且当数据集的平均标准差与类间中心距离较大时，属性约简效果更好。因此，在这种情况下可以考虑采用本文提出的ARI算法。 4 结 论 在数据挖掘中，FCM算法是一种经典的聚类分析方法，广泛应用于诸多领域。为了克服传统FCM算法的局限性，本文在多属性模糊C均值聚类的基础上，提出一种属性约简算法。为验证有效性，在UCI的五个数据集上，将新算法与因子分析法和粗糙集理论约简方法进行比较分析。实验结果表明，该方法具有更好的泛化作用。特别地，当数据集的平均类间距离和标准差较大的情况下，聚类效果优于常用的粗糙集和因子分析属性约简方法。 在实际应用问题中，数据集不仅有连续属性，还有离散型属性的数据，如何将ARI算法进一步完善，使之应用于离散型数据的处理，是值得继续研究的工作。 参考文献 [1] HAN Jiawei， KAMBER Micheline.数据挖掘：概念与技术[M].北京：机械工业出版社，2012. [2] WANG J. Geometric structure of high?dimensional data and dimensionality reduction [M]. Berlin： Springer Berlin Heidelberg， 2011. [3] 约翰逊.实用多元统计分析[M].北京：清华大学出版社，2008. [4] 周志华.机器学习[M].北京：清华大学出版社，2016. [5] 王学民.因子分析和因子分析应用中值得注意的问题[J].统计与决策，2007（11）：142?143. [6] PAWLAK Z. Rough sets [J]. International Journal of computer & information sciences， 1982， 11（5）： 341?356. [7] 廖启明，龙鹏飞.基于属性重要性的粗糙集属性约简方法[J].计算机工程与应用，2013，49（15）：130?132. [8] BEZDEK J C. Pattern recognition with fuzzy objective function algorithms [M]. New York： Plenum Press， 1981. [9] GROENEN PJ F， JAJUGAB K. Fuzzy clustering with squared Minkowsky distances [J]. Fuzzy sets and systems， 2001， 120（2）： 227?237. [10] 叶海军.基于统计特征加权的模糊聚类方法及其应用[J].现代电子技术，2009，32（12）：99?102. [11] 杨照峰，时合生.基于改进QPSO的模糊C?均值聚类算法[J].现代电子技术，2014，37（7）：118?120. [12] PIMENTEL B A， SOUZA R M C R. A multivariate fuzzy C?means method [J]. Applied soft computing， 2013， 13（4）： 1592?1607. [13] 高新波.模糊聚类分析及其应用[M].西安：西安电子科技大学出版社，2004. [14] KANNAN S R， RAMATHILAGAM S， CHUNG P C. Effective fuzzy C?means clustering algorithms for data clustering problems [J]. Expert systems with applications， 2012， 39（7）： 6292?6300. [15] 杨燕，靳蕃，KAMEL Mohamed.聚类有效性评价综述[J].计算机应用研究，2008，25（6）：1630?1632. |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。