基于多核的改进模糊聚类算法

贺艳芳　陈晓纯

摘要：为了对含有噪声和离群点的多特征类样本数据进行有效的聚类，提出了一种基于多核的改进模糊聚类算法。该算法选取子核函数构造多核函数，将输入的样本经多核函数进行映射，增加了不同类别样本间的区分度，提高核函数的学习能力和泛化能力。实验结果表明，该算法对于多样本数据具有比单核更好的聚类效果。

关键词：聚类；核函数；多核函数

中图分类号：TP181 文献标识码：A 文章编号：1009-3044（2018）15-0007-03

Improved Fuzzy Clustering Algorithm Based On Multiple Kernel

HE Yan-fang，CHEN Xiao-chun

（Department of Information Engineering， Guangdong Polytechnic College， Zhaoqing 526100， China）

Abstract： For the effective clustering of multi -feature sample data that contain noise and outliers， an improved fuzzy clustering algorithm based on multi-core is proposed. The algorithm selected sub kernel function to construct multi-core function， and mapped the input samples by multi-core function， which increases the distinguish of different categories of samples， and improves the learning ability and generalization ability of kernel function. The experimental results have show that the algorithm has a better clustering effect than single core for multi sample data.

Key words： multi-view； clustering； spectral clustering

聚类分析在数据挖掘研究中占有重要地位，它将具有相似性的对象划分为同一簇中，不同的对象划分为不同的簇中 [1]。和经典的聚类算法相比，引入模糊理论的模糊聚类算法[2]能够对样本属性进行不确定性描述，具有更好的聚类效果。其中，模糊C均值聚类算法[3-4]对噪声点和野值点较敏感，具有计算简单，聚类效果较好的特点，但聚类效果主要根据样本点的分布情况进行聚类。当各类样本的边界值受噪声干扰较大且边界点差异较大时，模糊聚類算法的聚类效果较差。故在模糊聚类中引用核方法[5]，核方法通过选取合适的核函数将输入空间的特征数据非线性映射到高维特征空间，增大数据间的差异性，同时提高数据点可线性分类的比例。目前的核模糊聚类虽然能够处理噪声干扰点对聚类的影响问题，但是该算法研究主要集中在单核的构造。

针对目前提出的多数据样本数据集的聚类问题，文献[6]提出了把多个核组合一起的多核学习概念。多核模型是一种基于不同核学习的模型。对于多特征数据来说，它具有比单核模型更优的性能和精确度。文献[7]把多核模型主要应用于医学的生物序列数据分类的领域，解决了医学的基因序列问题。本文借鉴多核函数进行多种数据源分类的模型，将多核学习引入到模糊C均值聚类中，解决模糊聚类中的多种数据源的问题，同时引入非欧式距离，将离中心近的点对聚类贡献大，而稍远的点贡献小的问题降低到最低，这样能更好地解决受噪声和离群点的数据的问题，让算法更有效。

1相关研究

1.1核函数

假设将输入空间数据样本[xk∈RN，K=1，2，…，l]，，非线性映射到高维特征H得到[H（x1），H（x2），…，H（xl）]，那么输入特征空间的数据用Mercer核点积形式来描述为：

[K（xi，xj）=（H（xi）·H（xj））] （1）

由所有样本组成核函数矩阵[Ki，j=K（xi，xj）]。它将原始样本数据从低维特征空间映射到高维特征空间，由于经过核函数的映射能使数据隐藏特征显示出来，进行更好的聚类。

定理[8]1 如果[K（x，y）]是一个连续的对称核，则[x，y∈X]核[K（x，y）]可以展开为：

[K（x，y）=i=1∞λiφi（x）φi（y） λi>0] （2）

式（2）绝对一致收敛的充要条件是[babaK（x，y）g（x）g（y）dxdy≥0]对于所有满足条件的[g（x）g（y）dx<∞，g（x）≠0]成立。相应核函数K的特征函数和特征值为[（φi（x），λi）]。任意函数只要具备Mercer特性，就能当作Mercer核，下面给出常用Mercer核函数：

多项式核[K（x，y）=（x?y+1）d]，其中d是整数，为自定义参数；

高斯核函数[K（x，y）=exp（-β||x-y||2/2δ2）]，其中[δ]为高斯函数的宽度；

神经网络 sigmoidal核函数[K（x，y）=tanh（-b（x?y）-c]，其中b，c是自定义的常数。

在选用合适的核函数时，可以利用先验知识选取符合数据分布的核函数；也可采用交叉验证的方法来选择合适的核函数，误差小的为最好的核函数。

1.2多核函数

SVM能用于分类和回归分析，它将向量映射到更高维空间进行分类，常用的SVM分类函数为：

[f（x）=sign（i=1Nαiyik（xi，x）+b）] （3）

式中：[xi]是N个有标志的训练样本；[yi∈{+1，-1}]，[k（xi，x）]是核函数，它描述了样本[xi]和x的相似性，其中的权重[α]可以通过二次优化问题来求解。

而多核函数通过某种形式将多个子核函数组合在一起如下所示：

[K（xi，xj）=i=1KβkKk（xi，xj） βk≥0，k=1，2，…，K] （4）

其中[Kk]是满足Mercer条件的核函数。由Mercer条件可知，如果子核函数[Kk（xi，xj）]满足条件为核函数，那么多核[K（xi，xj）]在一定条件下仍满足核函数的条件。

每个子核[Kk]可以根据对样本的贡献度来选择合适的子核[Kk]和权重系数[βk]，这种组合的多核函数[K（x，y）]具有更强划分性能。且多核函数能有效地拉大各个样本在特征空间的距离，从而加大各个样本的差异性，进而克服其他算法忽略微弱差别的样本，最终能更好地进行聚类。

和单核函数一样，多核聚类算法经过非线性映射，将输入空间Rm中的N个样本[x1，x2，…，xN]映射到高维特征空间得到[Φ（x1），Φ（x2），…，Φ（xN）]，最后在该特征空间中对特征矢量[Φ（xi），（i=1，…，N）]进行聚类，得到聚类结果。多核函数在高维特征空间欧式距离表示为：

[d（xi，xj）=||Φ（xi）-Φ（xj）||2=Φ（xi）?Φ（xi）-2Φ（xj）?Φ（xj）+Φ（xj）?Φ（xj）=K（xi，xi）-2K（xi，xj）+K（xj，xj）] （5）

2 基于多核的改进模糊聚类算法

2.1模糊核函数

设[U=（uij）C×N]为聚类算法中的模糊矩阵（其中，N为样本个数，C为类别数，[uij]是第i个类中第j个样本的模糊度），模糊聚类中心为[vi（i=1，2，…，C）]，又设[X={x1，x2，…，xn}]为输入样本数据集合，其中每个数据[xi]均有m个特性指标，即[xi=（xi1，xi2，…，xim）]。则该算法的目标函数为：

[Jm=i=1Cj=1Numij||Φ（xj）-Φ（vi）||2] （6）

式中：[Φ（xj）]和[Φ（vi）]分别为原始样本数据和聚类中心在高维特征空间H中映射的像。

[||Φ（xi）-Φ（vi）||2=K（xi，xi）+K（vi，vi）-2K（xj，vi）]

（7）

2.1.1 一种新的非欧式聚类

上述模糊核聚类算法目标函数通过欧式距离来度量，算法的非线性处理能力不够，不能很好地处理强噪声点和离群点的情况。为了解决噪声点和离群点，使用非欧式距离[9-10]，该距离函数如下：

[d2（x，y）=1-exp（-β||x-y||2）] （8）

式中：x，y为向量；参数[β]为常数，且

[β=（（j=1N||xj-x||）/N）-1] （9）

[x=j=1Nxj/N]

函数[d2（x，y）]是关于范数[||x-y||]的单调递减函数。该非欧式距离函数在[0，1]范围内取值，这样在一定程度上减少了计算量且易于进行分类。容易看出，当存在离群点（即[||x-y||]很大）时，[d2（x，y）]的函数值很大，使用该距离的目标函数值也很大。而模糊聚类方法是通过极小化目标函数来求解的，故离群点对该新距离构造的模糊聚类算法基本无影响，特别是对分布散乱的样本数据具有较好的聚类效果。

因此将非欧式距离和多核函数同时应用于模糊聚类算法，得到改进的模糊核聚类算法，其目标函数如下：

[][Jm（U，V）=i=1Cj=1Numij{1-exp（-β||Φ（xj）-Φ（vi）||2）}=i=1Cj=1Numij{1-exp（-β（K（xj，xj）-=2K（xj，vi）+K（vi，vi））=i=1Cj=1Numij{1-exp（-β||d2（xj，vi）||}] （10）

满足如下约束条件：

[i=1Cj=1Nuij=1， 1≤j≤Nuij∈[0，1]， 1≤j≤N， 1≤i≤C] （11）

[0

由于把多核函数作用于改进的模糊聚类算法，根据式（4）的多核函数可得到以下：

[K（xi，vj）=Φ（xi）?Φ（vj）=k=1N（ujk）mK（xk，xi）/k=1N（ujk）m] （12）

[K（vj，vj）=Φ（vj）?Φ（vj）=k=1Nl=1N（ujk）m（ujl）mK（xi，xl）/k=1N（ujk）m] （13）

根据拉格朗日优化算法导出基于多核的改进模糊聚类算法的模糊值[uij]和聚类中心[vi]如下：

[uij=（1-exp（-β（2-2K（xk，vi））））-1m-1i=1Cj=1N（1-exp（-β（2-2K（xk，vi））））-1m-1] （14）

[vi=j=1Numijexp（-β（2-2K（xj，vi）））K（xj，vi）xjj=1Numijexp（-β（2-2K（xj，vi）））K（xj，vj）））K（xj，vi）] （15）

根據上述优化标准和方法，基于多核的改进模糊聚类算法描述如下：

步骤1：初始化参数。设定聚类分类数C、模糊指数m，尺度参数[δ]、迭代停止条件[ε]和迭代次数T；

步骤2：按照数据集特性选择较好的子核和权值来构造多核函数。

步骤3：构造多核函数映射，将输入空间的多特征数据样本[x1，x2，…，xN]映射到高维特征空间得

[Φ（x1），Φ（x2），…，Φ（xN）]

步骤4：初始化类中心[vi]

步骤5：初始化各个样本在特征空间的隶属度[uij]

步骤6：计算目标函数值并按照式（14）更新隶属度[uij]

步骤7：若[max||uji-uji||<ε]算法停止，否则转到步骤5。

3 仿真实验与分析

实验采用UCI真实数据集，为了防止数据计算误差大，需要对数据集进行归一化处理，将各个特征集都规划在区间[0，1]之间。

3.1数据介绍

实验数据采用Iris（鸢尾花）数据，该数据分别属于三个不同类别的鸢尾花。该数据集是多特征数据集。它有150个样本组成，每类样本50，分别在3个类中分布，其中一类别样本和另外两类样本线性划分，另外两类样本数据有部分重叠。此数据集在数据挖掘、数据分类中常常用到的测试集、训练集，也是目前模式识别中最好的测试数据集。

对于本文的算法来说，选择不同的子函数来构造多核函數。目前聚类算法中的核函数一般用高斯函数，本文在算法中利用高斯核构造多核函数，其中权重系数为[β1=0.6]，[β2=0.3]，模糊聚类参数为m=2，[ε=10-5]，迭代次数T=50，实验结果如下：

表1是单核模糊聚类和基于多核的改进模糊聚类在鸢尾花（Iris）数据集中的实验结果，从实验中可以看出多核聚类算法的平均分错个数有明显的降低，说明多核算法在处理多特征数据集时，聚类效果更好。表2表明核参数对聚类算法的影响，通过实验数据可以看出，整体上多核聚类算法在不同的参数下分错个数明显降低，且不同的参数会影响多核聚类算法的分错个数。

4总结

本文将多核函数引入到改进的模糊聚类算法中，该算法利用改进的模糊聚类算法对噪声离群点和不平衡数据有较好的的区分，得到较好的聚类效果。

参考文献：

[1] 邱保志， 贺艳芳， 申向东. 熵加权多视角核K-means法[J]. 计算机应用， 2016， 36（6）：1619-1623.

[2] 陈海鹏， 申铉京， 龙建武，等. 自动确定聚类个数的模糊聚类算法[J]. 电子学报， 2017， 45（3）：687-694.

[3] Dave R N. Generalized fuzzy C-shell clustering and detection of circular and elliptical boundaries [J]. Pattern Recognition， 1992， 25（7）：639-641.

[4] Bezdek J C. Pattern Recognition with FuzzyObjective Function Algorithms [M]. New York： Plenum Press， 1981.

[5] Girolami M. Mercer Kerne-l based Clustering in Feature Space [J].IEEE Trans. on Neural Networks， 2002， 13（3）： 780-784.

[6] Sonnenburg S， Atsch G R， Afer S， et al. Large Scale Multiple KernelLearning [J] . Machine Learning Research， 2006， （7）： 1531-1565.

[7] Atsch G R， Sonnenburg S. Learning Interpretable SVMs for Biolog-ical Sequence Classfication [J]. BCM Bioinformatics 2004， 7（Suppl. ）： 39.

[8] 张莉， 周伟达， 焦李成. 核聚类算法[J]. 计算机学报，2002，25（6）：587-590.

[9] WU K L，YANG M S. Alternative c-means clustering algorithms[J].Pattern Recognition，2002，35 （ 10 ） ：2267-2278.

[10] HANG Dao-qiang，CHEN Song-can. A comment on“Alternative c-means clustering algorithms[J].Pattern Recognition，2004，37（ 2） ： 173-174.