基于多核的改進(jìn)模糊聚類算法

賀艷芳　陳曉純

摘要：為了對(duì)含有噪聲和離群點(diǎn)的多特征類樣本數(shù)據(jù)進(jìn)行有效的聚類，提出了一種基于多核的改進(jìn)模糊聚類算法。該算法選取子核函數(shù)構(gòu)造多核函數(shù)，將輸入的樣本經(jīng)多核函數(shù)進(jìn)行映射，增加了不同類別樣本間的區(qū)分度，提高核函數(shù)的學(xué)習(xí)能力和泛化能力。實(shí)驗(yàn)結(jié)果表明，該算法對(duì)于多樣本數(shù)據(jù)具有比單核更好的聚類效果。

關(guān)鍵詞：聚類；核函數(shù)；多核函數(shù)

中圖分類號(hào)：TP181 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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

聚類分析在數(shù)據(jù)挖掘研究中占有重要地位，它將具有相似性的對(duì)象劃分為同一簇中，不同的對(duì)象劃分為不同的簇中 [1]。和經(jīng)典的聚類算法相比，引入模糊理論的模糊聚類算法[2]能夠?qū)颖緦傩赃M(jìn)行不確定性描述，具有更好的聚類效果。其中，模糊C均值聚類算法[3-4]對(duì)噪聲點(diǎn)和野值點(diǎn)較敏感，具有計(jì)算簡單，聚類效果較好的特點(diǎn)，但聚類效果主要根據(jù)樣本點(diǎn)的分布情況進(jìn)行聚類。當(dāng)各類樣本的邊界值受噪聲干擾較大且邊界點(diǎn)差異較大時(shí)，模糊聚類算法的聚類效果較差。故在模糊聚類中引用核方法[5]，核方法通過選取合適的核函數(shù)將輸入空間的特征數(shù)據(jù)非線性映射到高維特征空間，增大數(shù)據(jù)間的差異性，同時(shí)提高數(shù)據(jù)點(diǎn)可線性分類的比例。目前的核模糊聚類雖然能夠處理噪聲干擾點(diǎn)對(duì)聚類的影響問題，但是該算法研究主要集中在單核的構(gòu)造。

針對(duì)目前提出的多數(shù)據(jù)樣本數(shù)據(jù)集的聚類問題，文獻(xiàn)[6]提出了把多個(gè)核組合一起的多核學(xué)習(xí)概念。多核模型是一種基于不同核學(xué)習(xí)的模型。對(duì)于多特征數(shù)據(jù)來說，它具有比單核模型更優(yōu)的性能和精確度。文獻(xiàn)[7]把多核模型主要應(yīng)用于醫(yī)學(xué)的生物序列數(shù)據(jù)分類的領(lǐng)域，解決了醫(yī)學(xué)的基因序列問題。本文借鑒多核函數(shù)進(jìn)行多種數(shù)據(jù)源分類的模型，將多核學(xué)習(xí)引入到模糊C均值聚類中，解決模糊聚類中的多種數(shù)據(jù)源的問題，同時(shí)引入非歐式距離，將離中心近的點(diǎn)對(duì)聚類貢獻(xiàn)大，而稍遠(yuǎn)的點(diǎn)貢獻(xiàn)小的問題降低到最低，這樣能更好地解決受噪聲和離群點(diǎn)的數(shù)據(jù)的問題，讓算法更有效。

1相關(guān)研究

1.1核函數(shù)

假設(shè)將輸入空間數(shù)據(jù)樣本[xk∈RN，K=1，2，…，l]，，非線性映射到高維特征H得到[H（x1），H（x2），…，H（xl）]，那么輸入特征空間的數(shù)據(jù)用Mercer核點(diǎn)積形式來描述為：

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

由所有樣本組成核函數(shù)矩陣[Ki，j=K（xi，xj）]。它將原始樣本數(shù)據(jù)從低維特征空間映射到高維特征空間，由于經(jīng)過核函數(shù)的映射能使數(shù)據(jù)隱藏特征顯示出來，進(jìn)行更好的聚類。

定理[8]1 如果[K（x，y）]是一個(gè)連續(xù)的對(duì)稱核，則[x，y∈X]核[K（x，y）]可以展開為：

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

式（2）絕對(duì)一致收斂的充要條件是[babaK（x，y）g（x）g（y）dxdy≥0]對(duì)于所有滿足條件的[g（x）g（y）dx<∞，g（x）≠0]成立。相應(yīng)核函數(shù)K的特征函數(shù)和特征值為[（φi（x），λi）]。任意函數(shù)只要具備Mercer特性，就能當(dāng)作Mercer核，下面給出常用Mercer核函數(shù)：

多項(xiàng)式核[K（x，y）=（x?y+1）d]，其中d是整數(shù)，為自定義參數(shù)；

高斯核函數(shù)[K（x，y）=exp（-β||x-y||2/2δ2）]，其中[δ]為高斯函數(shù)的寬度；

神經(jīng)網(wǎng)絡(luò) sigmoidal核函數(shù)[K（x，y）=tanh（-b（x?y）-c]，其中b，c是自定義的常數(shù)。

在選用合適的核函數(shù)時(shí)，可以利用先驗(yàn)知識(shí)選取符合數(shù)據(jù)分布的核函數(shù)；也可采用交叉驗(yàn)證的方法來選擇合適的核函數(shù)，誤差小的為最好的核函數(shù)。

1.2多核函數(shù)

SVM能用于分類和回歸分析，它將向量映射到更高維空間進(jìn)行分類，常用的SVM分類函數(shù)為：

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

式中：[xi]是N個(gè)有標(biāo)志的訓(xùn)練樣本；[yi∈{+1，-1}]，[k（xi，x）]是核函數(shù)，它描述了樣本[xi]和x的相似性，其中的權(quán)重[α]可以通過二次優(yōu)化問題來求解。

而多核函數(shù)通過某種形式將多個(gè)子核函數(shù)組合在一起如下所示：

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

其中[Kk]是滿足Mercer條件的核函數(shù)。由Mercer條件可知，如果子核函數(shù)[Kk（xi，xj）]滿足條件為核函數(shù)，那么多核[K（xi，xj）]在一定條件下仍滿足核函數(shù)的條件。

每個(gè)子核[Kk]可以根據(jù)對(duì)樣本的貢獻(xiàn)度來選擇合適的子核[Kk]和權(quán)重系數(shù)[βk]，這種組合的多核函數(shù)[K（x，y）]具有更強(qiáng)劃分性能。且多核函數(shù)能有效地拉大各個(gè)樣本在特征空間的距離，從而加大各個(gè)樣本的差異性，進(jìn)而克服其他算法忽略微弱差別的樣本，最終能更好地進(jìn)行聚類。

和單核函數(shù)一樣，多核聚類算法經(jīng)過非線性映射，將輸入空間Rm中的N個(gè)樣本[x1，x2，…，xN]映射到高維特征空間得到[Φ（x1），Φ（x2），…，Φ（xN）]，最后在該特征空間中對(duì)特征矢量[Φ（xi），（i=1，…，N）]進(jìn)行聚類，得到聚類結(jié)果。多核函數(shù)在高維特征空間歐式距離表示為：

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

2 基于多核的改進(jìn)模糊聚類算法

2.1模糊核函數(shù)

設(shè)[U=（uij）C×N]為聚類算法中的模糊矩陣（其中，N為樣本個(gè)數(shù)，C為類別數(shù)，[uij]是第i個(gè)類中第j個(gè)樣本的模糊度），模糊聚類中心為[vi（i=1，2，…，C）]，又設(shè)[X={x1，x2，…，xn}]為輸入樣本數(shù)據(jù)集合，其中每個(gè)數(shù)據(jù)[xi]均有m個(gè)特性指標(biāo)，即[xi=（xi1，xi2，…，xim）]。則該算法的目標(biāo)函數(shù)為：

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

式中：[Φ（xj）]和[Φ（vi）]分別為原始樣本數(shù)據(jù)和聚類中心在高維特征空間H中映射的像。

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

（7）

2.1.1 一種新的非歐式聚類

上述模糊核聚類算法目標(biāo)函數(shù)通過歐式距離來度量，算法的非線性處理能力不夠，不能很好地處理強(qiáng)噪聲點(diǎn)和離群點(diǎn)的情況。為了解決噪聲點(diǎn)和離群點(diǎn)，使用非歐式距離[9-10]，該距離函數(shù)如下：

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

式中：x，y為向量；參數(shù)[β]為常數(shù)，且

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

[x=j=1Nxj/N]

函數(shù)[d2（x，y）]是關(guān)于范數(shù)[||x-y||]的單調(diào)遞減函數(shù)。該非歐式距離函數(shù)在[0，1]范圍內(nèi)取值，這樣在一定程度上減少了計(jì)算量且易于進(jìn)行分類。容易看出，當(dāng)存在離群點(diǎn)（即[||x-y||]很大）時(shí)，[d2（x，y）]的函數(shù)值很大，使用該距離的目標(biāo)函數(shù)值也很大。而模糊聚類方法是通過極小化目標(biāo)函數(shù)來求解的，故離群點(diǎn)對(duì)該新距離構(gòu)造的模糊聚類算法基本無影響，特別是對(duì)分布散亂的樣本數(shù)據(jù)具有較好的聚類效果。

因此將非歐式距離和多核函數(shù)同時(shí)應(yīng)用于模糊聚類算法，得到改進(jìn)的模糊核聚類算法，其目標(biāo)函數(shù)如下：

[][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

由于把多核函數(shù)作用于改進(jìn)的模糊聚類算法，根據(jù)式（4）的多核函數(shù)可得到以下：

[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）

根據(jù)拉格朗日優(yōu)化算法導(dǎo)出基于多核的改進(jìn)模糊聚類算法的模糊值[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）

根據(jù)上述優(yōu)化標(biāo)準(zhǔn)和方法，基于多核的改進(jìn)模糊聚類算法描述如下：

步驟1：初始化參數(shù)。設(shè)定聚類分類數(shù)C、模糊指數(shù)m，尺度參數(shù)[δ]、迭代停止條件[ε]和迭代次數(shù)T；

步驟2：按照數(shù)據(jù)集特性選擇較好的子核和權(quán)值來構(gòu)造多核函數(shù)。

步驟3：構(gòu)造多核函數(shù)映射，將輸入空間的多特征數(shù)據(jù)樣本[x1，x2，…，xN]映射到高維特征空間得

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

步驟4：初始化類中心[vi]

步驟5：初始化各個(gè)樣本在特征空間的隸屬度[uij]

步驟6：計(jì)算目標(biāo)函數(shù)值并按照式（14）更新隸屬度[uij]

步驟7：若[max||uji-uji||<ε]算法停止，否則轉(zhuǎn)到步驟5。

3 仿真實(shí)驗(yàn)與分析

實(shí)驗(yàn)采用UCI真實(shí)數(shù)據(jù)集，為了防止數(shù)據(jù)計(jì)算誤差大，需要對(duì)數(shù)據(jù)集進(jìn)行歸一化處理，將各個(gè)特征集都規(guī)劃在區(qū)間[0，1]之間。

3.1數(shù)據(jù)介紹

實(shí)驗(yàn)數(shù)據(jù)采用Iris（鳶尾花）數(shù)據(jù)，該數(shù)據(jù)分別屬于三個(gè)不同類別的鳶尾花。該數(shù)據(jù)集是多特征數(shù)據(jù)集。它有150個(gè)樣本組成，每類樣本50，分別在3個(gè)類中分布，其中一類別樣本和另外兩類樣本線性劃分，另外兩類樣本數(shù)據(jù)有部分重疊。此數(shù)據(jù)集在數(shù)據(jù)挖掘、數(shù)據(jù)分類中常常用到的測試集、訓(xùn)練集，也是目前模式識(shí)別中最好的測試數(shù)據(jù)集。

對(duì)于本文的算法來說，選擇不同的子函數(shù)來構(gòu)造多核函數(shù)。目前聚類算法中的核函數(shù)一般用高斯函數(shù)，本文在算法中利用高斯核構(gòu)造多核函數(shù)，其中權(quán)重系數(shù)為[β1=0.6]，[β2=0.3]，模糊聚類參數(shù)為m=2，[ε=10-5]，迭代次數(shù)T=50，實(shí)驗(yàn)結(jié)果如下：

表1是單核模糊聚類和基于多核的改進(jìn)模糊聚類在鳶尾花（Iris）數(shù)據(jù)集中的實(shí)驗(yàn)結(jié)果，從實(shí)驗(yàn)中可以看出多核聚類算法的平均分錯(cuò)個(gè)數(shù)有明顯的降低，說明多核算法在處理多特征數(shù)據(jù)集時(shí)，聚類效果更好。表2表明核參數(shù)對(duì)聚類算法的影響，通過實(shí)驗(yàn)數(shù)據(jù)可以看出，整體上多核聚類算法在不同的參數(shù)下分錯(cuò)個(gè)數(shù)明顯降低，且不同的參數(shù)會(huì)影響多核聚類算法的分錯(cuò)個(gè)數(shù)。

4總結(jié)

本文將多核函數(shù)引入到改進(jìn)的模糊聚類算法中，該算法利用改進(jìn)的模糊聚類算法對(duì)噪聲離群點(diǎn)和不平衡數(shù)據(jù)有較好的的區(qū)分，得到較好的聚類效果。

參考文獻(xiàn)：

[1] 邱保志， 賀艷芳， 申向東. 熵加權(quán)多視角核K-means法[J]. 計(jì)算機(jī)應(yīng)用， 2016， 36（6）：1619-1623.

[2] 陳海鵬， 申鉉京， 龍建武，等. 自動(dòng)確定聚類個(gè)數(shù)的模糊聚類算法[J]. 電子學(xué)報(bào)， 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] 張莉， 周偉達(dá)， 焦李成. 核聚類算法[J]. 計(jì)算機(jī)學(xué)報(bào)，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.