| 标题 | 基于改进核可能性C均值类间极大化聚类算法 |
| 范文 | 林嘉炜 祁云嵩 陈晓利 凡甲甲 关键词： 核可能性C均值; 边界模糊; 聚类算法; 类间极大惩罚项; 调控因子; 类内元素 中图分类号： TN919.1?34; TP391.41 ? ? ? ? ? ? 文献标识码： A ? ? ? ? ? ? ? ? ?文章编号： 1004?373X（2018）24?0117?04 An improved kernel maximum center interval possibilitic C?means clustering algorithm LIN Jiawei， QI Yunsong， CHEN Xiaoli， FAN Jiajia （Jiangsu University of Science and Technology， Zhenjiang 212000， China） Abstract： The kernel possibilitic C?means （KPCM） clustering algorithm only considers the relationships between intra?class elements but ignores the relationships between classes， as a result， the phenomena of too small clustering center interval and even clustering center overlap may occur during the clustering of data sets with fuzzy boundaries. Therefore， an improved kernel maximum center interval possibilitic C?means （KMPCM） clustering algorithm is proposed. In the algorithm， an inter?class maximum penalty term of high?dimensional feature space and regulating factor λ are introduced into the KPCM clustering algorithm， so as to construct a new objective function， which can appropriately expand intervals between class centers to effectively avoid the phenomena of too small clustering center interval and even overlap， make samples near the boundaries better classified， and consider the relationships between intra?class elements to maintain better robustness on noise points and outliers. The results of a large number of experiments show that the improved algorithm has a more obvious superiority in clustering effect on data sets with fuzzy boundaries than the traditional clustering algorithm. Keywords： kernel possibilitic C?means; fuzzy boundary; clustering algorithm; inter?class maximum penalty term; regulating factor; intra?class element0 ?引 ?言 模糊聚类是采用模糊数学语言对事物按照一定的要求进行描述和分类的数学方法[1]。经典的模糊聚类算法有模糊C均值（FCM）算法[2]，FCM的目标函数相对简单，运行效率较高，但其有隶属度和为1的约束条件，因此受噪声点和野值点的影响较大。为解决此问题，提出可能性C均值（PCM）算法[3]，其打破隶属度和为1的约束条件，使得噪声点和野值点的隶属度值较小，噪声点和野值点对最终的聚类效果影响不大。而PCM相对FCM存在的缺陷在于最终结果会使得聚类中心距离较近甚至出现重合现象。FCM与PCM的共同缺陷在于处理高维度数据集时往往运行效率低下，数据集得不到好的划分，而核的引入解决了上述问题，进而提出核模糊性C均值（KFCM）算法[4]和核可能性C均值聚类（KPCM）算法[5]。KPCM算法虽然在处理噪声点和野值点时性能有所提升，但依旧存在两点缺陷：缺乏考虑类与类之间的联系，而在实际情况中，类与类之间是有联系的;容易造成聚类中心距离过小甚至重合的现象。 针对上述问题，本文在KPCM的基础上引入类间极大惩罚项以及调控因子λ构造新的目标函数，提出一种基于改进核可能性C均值类间极大化聚类（KMPCM）算法，极大惩罚项考虑类与类之间的联系，通过拉大聚类中心距离，使得边界模糊的数据集能得到较好的划分。1 ?改进的基于核可能性C均值聚类算法 设[X=x1，x2，…，xn?Rs]表示给定的样本集合，[s]是样本空间的维数，[n]是样本个数。定义一个非线性映射[Φ：X→Φ（X）∈F]是从[X]到特征空间[F]的映射，[F]是映射[Φ]对应的核函数。KPCM的目标函数如下：[JKPCM（U，V）=2i=1Cj=1numij1+K（xj，vi）+ ? ? ? ? ? ? ? ? ? ? ? ? ?i=1Cηij=1n（1-uij）m] （1） 高维特征空间的类间极大惩罚项表达形式如下： [q=λC-1i=1Ck=1，k≠iCvi-vk2] ?（2） 式中：[m>1]是模糊系数;[CC>1]是对聚类的个数;[V]表示聚类中心且[V=v1，v2，…，vC];[U=uij]是一个[C×n]的模糊划分矩阵;[uij]是第[j]个样本[xj]属于第[i]类的隶属度值;[ηi]是惩罚因子，建议取值为： [ηi=K2j=1nuij（1-K（xj，vi））j=1nuijm， K>0，一般取1] （3） 式中，[m]是加权指数，[m]的取值如下： [m=min（n，p）min（n，p-1）-2 或 m=2] ? ? ? ? ? （4） 则KMPCM的目标函数为： [JKMPCM（U，V）=2i=1Cj=1numij1-Kxj，vi+ ? ? ? ? ?i=1Cηij=1n（1-uij）m-2λC-1i=1Ck=1，k≠iC1-Kvi，vk] ? ? ?（5） 根据拉格朗日求极值法，当目标函数式（5）取得极小值时，其对应的必要条件为： [uij=11+21-K（xj，vi）-2λk=1，k≠iC1-K（vi，vk）ηi1m-1] （6） [vi=j=1nuijKxj，vixj-λC-1k=1，k≠iCKvi，vkvkj=1numijKxj，vi-λC-1k=1，k≠iCKvi，vkvi] ?（7） 可得KMPCM算法的具体执行步骤如下： 1） 设定核函数参数[σ]，聚类个数c，模糊指数m，收敛精度ε，初始化调控因子[λ=1n]，最大迭代次数tmax，令迭代次数k=0。 2） 用FCM算法初始化中心矩阵[V（0）]。 3） 用式（6）计算[U（k+1）]。 4） 用式（7）计算[V（k+1）]。 5） 如果[U（k）-U（k+1）≤ε]，停止迭代;否则，[k=k+1]，转到步骤2）。 当满足终止条件时，隶属度矩阵[U]和聚类中心矩阵[V]为算法的最优解。2 ?实 ?验 本文实验是使用Matlab R2012a的编程环境。为说明本文提出的算法具有较好的有效性，本文拟通过与经典的算法，例如FCM，PCM以及一些改进的经典算法KPCM，KFCM进行比较，主要是在模拟数据集和UCI真实数据集上进行对比试验。 2.1 ?评价指标 本文将选用国际常用的归一化互信息（Normalized Mutual Information，NMI）[6]和芮氏（Rand Index，RI）[7]两个指标来评价本文算法的性能。这两个评价指标的取值范围均为[0，1]，且随着数值的增大，显示出算法的性能更加优越。 2.2 ?带噪声和野值点的模拟数据实验 为验证KMPCM算法是否依旧保留对噪声点和野值点具有良好的鲁棒性，进行噪声点和野值点的模拟数据实验。在这部分实验中，采用原始数据集中具有噪声点和野值点的Square数据集[8]和边界模糊的高斯数据集[9]。 2.2.1 ?Square数据集实验 Square数据集由三部分组成：一大一小两个正方形数据集以及噪声点。图1和表1分别给出实验结果图和实验数据表。 通过图1、表1得知，KMPCM算法最终聚类效果最佳，使得聚类中心偏离距离最小，对噪声点和野值点具有更好的鲁棒性。 2.2.2 ?边界模糊的模拟数据实验 人造高斯数据集可以根据实验需求进行构造，因此本文在选取数据集来进行算法对边界模糊处的处理时采用人造高斯数据集。构造高斯数据集时，将高斯核函数的类中心、类方差，以及数据样本数设定好，再随机生成。本文采用两组数据集的相关参数如图2，图3，表2，表3所示。 从图2、图3以及表2、表3可以看出，在处理边界模糊数据集时，FCM，PCM，KFCM和KPCM容易造成误分的问题，而KMPCM因为考虑到类与类间的联系，并且没有放弃原来类内元素的关系，所以使得边界处的模糊数据得到了较好的划分，分类性能也较其他4种算法有了一定的提高。 2.3 ?UCI真实数据集实验 上述实验均为模拟数据集，为更加全面地验证本文算法的有效性，采用6个经典的UCI[10]真实数据集进行实验，并与其他4种算法进行对比实验。实验结果如表4所示。通过表4可以看出，KMPCM在对高维数据集进行聚类实验时，其效果相对其他4种聚类算法有所提升。上述实验数据从模拟数据集到真实数据集再到UCI数据集，全面地验证了算法的有效性。在模拟数据集中，先是对有噪声点和野值点的数据集进行试验。试验结果表明，KMPCM依旧保存着PCM和KPCM抗噪声性能良好的特性，并且由于考虑到类间关系，从而使得聚类效果更佳。在边界模糊的数据集中采用人造高斯核函数随机生成的数据集。由于其他4个聚类算法只是考虑类内关系，因此在处理具有这类特性的数据集时，效果不是很理想。反观本文提出的KMPCM算法，考虑类间关系，适当拉大类中心距离，从而使得聚类效果有所提升。但是本文的算法还是存在一些缺点，在对初始化的参数如何选取时并没有一个很好的方法来选取。3 ?结 ?论 PCM对于高维数据集的处理显得效率低下且得不到好的划分。在引入核函数后，提出KPCM较好地解决了高维数据集的聚类问题，但是保留了PCM的缺陷：聚类结果往往使得聚类中心距离较小甚至出现重合现象，使得边界模糊的数据集得不到好的聚类效果。针对上述问题，本文引入类间极大惩罚项和调控因子λ，考虑类与类之间的关系，提出一种基于改进型核可能性C均值类间极大化聚类（KMPCM）算法。在实验部分，采用带噪声和野值点的模拟数据实验、边界模糊的高斯数据集和UCI真实数据集進行对比实验。最终的实验结果表明，KMPCM相对其他4种聚类算法具有更好的抗噪声能力，对于边界模糊的数据集具有更好的聚类效果，以及处理高维数据集的优越性。但是该算法依旧存在现有聚类算法普遍存在的问题：没有一个好的选取机制选取算法的初始化参数。以后的研究方向是如何选取参数使得聚类算法达到最优的、稳定的聚类效果。 参考文献 [1] LZAKIAN H， PEDRYCZ W， JAMAL I. Fuzzy clustering of time series data using dynamic time warping distance [J]. Engineering applications of artificial intelligence， 2015， 39： 235?244. [2] 孙如英，韩荣苍.基于FCM的模糊粗糙属性约简[J].现代电子技术，2009，32（17）：194?196. SUN Ruying， HAN Rongcang. Attribute reduction approach based on fuzzy rough set and FCM [J]. Modern electronics technique， 2009， 32（17）： 194?196. [3] LIU Z M， LI S Z， LIN D Z， et al. Blog community discovery based on PCM clustering algorithm [J]. Journal of Xiamen University， 2009， 48（4）： 508?513. [4] WANG X. KFCM algorithm based on the source code mining method study [C]// Proceedings of 5th International Conference on Intelligent Systems Design and Engineering Applications. Changsha： IEEE， 2014： 586?588. [5] MA Z T， GAO J W， QIN Y， et al. Fault diagnosis of metro vehicle auxiliary inverter based on PSO?KPCM algorithm [J]. Applied mechanics & materials， 2013， 385： 593?596. [6] LIU J， MOHAMMED J， CARTER J， et al. Distance?based clustering of CGH data [J]. Bioinformatics， 2006， 22（16）： 1971?1978. [7] PAL N R， PAL K， KELLER J M， et al. A possibilistic fuzzy C?means clustering algorithm [J]. IEEE transactions on fuzzy systems， 2005， 13（4）： 517?530. [8] ZADEH L A. Fuzzy sets [J]. Information and control， 1965， 8（3）： 338?353. [9] YOSHIKAWA Y， IWATA T， SAWADA H. Non?linear regression for bag?of?words data via Gaussian process latent variable set model [C/OL]. [2015?02?21]. https：//www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9796. [10] LIANG G E， LANG J T， TANG H， et al. Clustering high?dimensional data using PCA?Hubness [J]. Modern computer， 2017（11）： 52?55. |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。