基于樣本特征加權的可能性模糊核聚類算法＊－

黃衛春，劉建林，熊李艷

（華東交通大學信息工程學院，江西 南昌330013）

1 引言

聚類分析是多元統計分析的一種，也是非監督模式識別的一個重要分支。聚類的目的是使得相似的樣本之間的距離盡可能地小，而不相似的樣本之間的距離盡可能地大。隨著模糊集理論的提出和不斷發展，模糊聚類分析已成為聚類分析研究的主流，其中以基于目標函數的模糊C－均值FCM（Fuzzy C－Means）算法理論最為完善，應用最為廣泛。模糊C－均值聚類算法是一種基于劃分的聚類方法，根據最小二乘原理，采用迭代方法優化目標函數，最終得到每個樣本點的歸屬。如今FCM算法已被廣泛地應用于模式識別、數據挖掘、圖像處理等領域［1～4］。

經典的FCM算法對初始聚類中心較為敏感，易出現局部最優的情況，且算法不考慮各個特征重要度及不同樣本對分類的影響。在實際應用中，聚類中心的選取會在一定程度上影響輸出結果，且一些數據集的樣本分布是非均勻的或非對稱的，也就是說樣本的特征對分類的結果是不均勻的，這些都會影響聚類效果。針對以上問題，許多學者提出了FCM的改進算法，如KPrishnapuranm K和Keller通過放松隸屬度約束的限制提出了可能性C－均值算法PCM（Possibilistic C－Means）。Pal N R 等［5］把FCM算法中的隸屬度和PCM算法中的可能性典型值相結合提出了可能性模糊C－均值算法PFCM（Possibilistic Fuzzy C－Means）。也有學者通過將遺傳算法和模糊聚類算法相結合，提出了許多混合算法，如于水英等［6］提出了將遺傳算法和模糊聚類相結合并應用到文本分類以提高分類效果；許松榮等［7］提出基于遺傳算法的模糊聚類算法等。還有學者提出了一些基于權重的混合算法，如王麗娟等［8］提出的基于屬性權重的FCM 算法；Shen Hong－bin等［9］提出的基于 mercer核的屬性加權FCM方法；賀楊成等［10］提出的特征空間屬性加權混合C－均值模糊核聚類算法；蔡靜穎等［11］提出的基于馬氏距離特征加權的模糊聚類新算法；劉兵等［12］提出的基于樣本加權的可能性模糊聚類算法等。這些改進算法都在一定程度上解決了經典FCM的噪聲敏感及局部最優的問題，但面對樣本離群點或噪聲數據較多時，算法性能可能會受到較大的影響。本文提出了一種基于樣本－特征加權的可能性模糊核聚類算法，利用可能性聚類的思想解決了噪聲敏感和一致性聚類的問題；同時，在聚類過程中動態計算樣本屬性特征間的不平衡性和樣本對聚類的重要性的權重，減少噪聲數據和例外點對聚類的影響，優化選取核參數并不斷修正核函數把原始空間中非線性可分的數據集轉化為高維特征空間中的可分數據集。實驗結果表明，該算法能減少噪聲數據和例外點的影響，比傳統的聚類算法具有更好的聚類精度。

2 模糊C－均值聚類算法

設定一個具有N個樣本的數據集X＝｛x1，x2，…，xN｝，xi＝ ｛xi1，xi2，…，xiL｝，i＝1，2，…，N ，每個樣本點xi有L個屬性，把其劃分到c個不相交的數據集中，每個數據集的聚類中心分別為v1，v2，…，vc。FCM算法使用模糊劃分，每個樣本點xj被賦予一個屬于第c個類別的隸屬度值，隸屬度值的取值范圍為0～1。其目標函數如下：

其中，dij為數據點xj與聚類中心vi的距離，在經典的FCM算法中總使用歐氏距離來計算；m為模糊指數，表示隸屬度矩陣的模糊程度，在實際應用中m的最佳取值范圍為 （1.5，2.5）。通過拉格朗日乘法來求解式（1）可得隸屬度uij、聚類中心vi的迭代式：

但是，經典的FCM算法本質屬于局部搜索的爬山法，對初始聚類中心較為敏感，易出現局部最優的情況，且該算法不考慮各個屬性特征及樣本總體對分類重要性的影響。

3 基于樣本－特征加權的可能性模糊核聚類算法

3.1 樣本－特征加權

樣本加權是為了克服離群點對聚類分析的影響，加快聚類的收斂速度。通過給每個樣本整體添加一個權值，表示其對聚類的貢獻程度。對噪聲數據或例外點賦予一個較小的權值，使其參與聚類的程度被降低，也就減少甚至消除了它們對聚類結果的影響。假設樣本集X＝ ｛x1，x2，…，xN｝，為每個樣本xi賦予一個權重αj，αj的表達式如下：

其中，?為正的常數，j＝1，2，…，N ，‖xj－xk‖表示兩個樣本xj與xk之間的歐氏距離。

顯然樣本權值的大小與樣本點到其它所有樣本點之間的距離有關，離群點離樣本的距離相對較遠，那么其被賦予的權值就較小，也就減少了離群點的影響。同時，為了體現樣本屬性特征對類別的重要程度，定義一個權重系數wik，表示第k個屬性對i類的重要性，且：

假定 為一非線性隱射函數，：RL→H，x→（x），其中x∈RL是原始空間的一個樣本點，H為映射后的高維特征空間。把歐氏距離計算換成核函數計算，則基于樣本－特征加權的可能性模糊核聚類算法的目標函數（簡單表示為SFPFKM）為：

其中，1≤i≤c，1≤j≤N，c為類別數，vik是第i類的聚類中心，uij表示第j個樣本屬于第i類的隸屬度，tij為第j個樣本屬于第i類的可能性，σ2是協方差矩陣，其計算方法［13］如下：

定義核映射函數為：

任何一個函數只要滿足 Mercer定理［14］條件就可以作為Mercer核。用一個非線性函數 （x）把所有樣本映射到高維空間，可以得到新的樣本集。核的引入在原始空間中誘導出了依賴于核的新的距離度量。由式（9）可得：

其中核函數為高斯核函數：

由式（10）可得 K（x，x）＝1，則式（7）經過轉化可得：由式（12）的極值約束條件，根據拉格朗日乘法可得：

其中λ為拉格朗日系數，其最優化的一階必要條件為：

由式（14）可得隸屬度uij的迭代式為：

同理，由式（12）和式（13）可得權重系數wik、典型值tij和聚類中心vik的計算式分別為：

3.2 修正核函數及核參數優化

根據權重系數wik取值的不同，聚類中心vik的取值也不同，可得：

為了使目標函數獲得最優解，需要合理選取核函數的核參數φ，比較典型的方法是通過下降梯度法和交叉驗證法來確定φ的取值［15］。本文選用下降梯度法來確定φ的取值，φ的迭代式為：

其中δ為迭代步長。

對于一個正標量函數D（x），定義：

把式（12）稱為核函數通過因子D（x）的保形變換。ˉK（x，x′）為支持向量機的修正核函數［16］。

可以通過修正核函數來提高分類的精度，整個修正過程分為兩步：第一步是利用原始核函數進行聚類以產生支持向量，第二步利用支持向量信息修正核函數。令：

其中，θ為任意常數，v為聚類中心。由式（22）所得的修正核函數仍滿足Mercer條件［17］。

φ的初始值［18］設為：

其中，c為聚類數，N為樣本總數。

通過以上可得基于修正核函數的特征加權模糊核聚類算法，其描述如下：

步驟1 設定聚類數c，模糊權重指數m，核參數的迭代步長δ，?＞0，a＞0，b＞0，β＞1，η＞1，最大迭代次數max＿t，算法停止時最小閾值ε＞0。

步驟2 運行FCM算法，并以其結果作為初始聚類中心矩陣v（0）、初始隸屬度矩陣u（0）。

步驟3 隨機初始化典型值t（0）、權重w（0），令t＝1。

步驟4 使用式（23）初始化核參數φ＝φ（0）。

深基坑施工是基礎施工的基礎，開工前根據建筑工程實際對基坑施工標準進行全面的優化，要確保基坑自身的強度及安全穩定性，增強地基的稱在惡劣，并且施工人員也要嚴格的按照施工工序進行施工，確保深基坑施工的安全性。

步驟5 使用式（21）和式（22）不斷修正K（xj，vi），并使用如下迭代公式進行循環，逼近最優解：

（1）使用式（18）更新聚類中心v（t）；

（2）使用式（17）更新典型值t（t）；

（3）使用式（16）更新權重值w（t）；

（4）使用式（20）計算新的核參數φ（t）；

（5）使用式（15）更新隸屬度u（t）；

（6）t＝t＋1；

4 實驗結果與分析

為了驗證本文算法的魯棒性和有效性，利用從UCI中選取的四個數據集和含噪聲數據集兩組實驗對算法進行驗證。在實驗中將本文算法的聚類性能分別與FCM算法、PCM算法、PFCM算法的性能進行對比。在UCI中的四個數據集上比較各算法的聚類精度，也就是正確聚類樣本數與樣本總數所得的比值，值越大也就是聚類的精度越大，正確聚類的樣本越多；在含噪聲數據集上比較算法發現含噪聲數據的聚類中心的能力。算法在PC機上利用 Microsoft Visual C＋＋6.0進行仿真實驗。

4.1 UCI數據集實驗

從UCI中選取的四個數據集分別為Iris、Wine、Pima和 Breast－cancer，這四個數據集是比較無監督聚類效果好壞的典型數據，其基本特征如表1所示，將這四個數據集應用不同算法的聚類結果如表2所示。

Table 1 Basic information of data set表1 數據集的基本信息

實驗中各參數的配置為：ε＝0.000 01，最大迭代次數max＿t＝150，m＝2.0。PFCM 算法在四個數據集上的其它參數設置為a＝1.0，b＝1.0，β＝2.0；本文算法在四個數據集上的其它參數分別設為a＝1.0，b＝1.0，β＝2.0，η＝2.0；a＝1.0，b＝50，β＝1.5，η＝2.0；a＝0.1，b＝100，β＝1.5，η＝2.0；a＝0.1，b＝90，β＝1.0，η＝2.0（這些參數的選擇是根據多次實驗而來的，為方便比較，我們選取具有最優的聚類效果的參數作為本文算法的實驗參數）。

Table 2 Comparision of the algorithms’clustering results表2 各算法的聚類結果比較

從表2中可得，基于樣本特征加權可能性模糊聚類算法的聚類精度均優于經典的FCM、PCM、PFCM算法的聚類精度，且對于不同的數據集，本文算法的聚類精度的改善程度是不一樣的。與FCM、PCM、PFCM三種算法相比，本文算法在I－ris數據集上的聚類精度比其他三種算法分別提高了近0.14、0.27、0.02；在Pima數據集上的聚類精度分別提高了近0.21、0.44、0.04；在 Wine數據集上的聚類精度分別提高了0.03、0.30、0.01；在Breast＿cancer數據集的聚類精度分別提高了近0.01、0.64、0.01。由此可見，基于樣本－特征加權的可能性模糊聚類算法優于經典聚類算法的聚類性能，相比其它算法能獲得更好的數據集劃分。

4.2 含噪聲數據集實驗

為了測試本文算法在含噪聲數據集上的運行效果，本文對含噪聲的數據集X12［19］進 行 實 驗 ，X12是由12個數據點構成的二維數據集，其坐標值如表3［19］所示。X12中有10個數據共分為兩類，另外兩個數據點x6和x12是到兩類中心相等的噪聲點。實驗條件為ε＝0.000 01，最大迭代次數max＿t＝150，m ＝ 2.0，a＝1.0，b＝1.0，β＝2.0，η＝2.0，通過各算法運行后的隸屬度值和（或）典型值如表3所示，各算法運行后的聚類中心如表4所示。

Table 4 Cluster centers of the algorithms表4 各算法的聚類中心

從表3可知，數據點x6和x12在運行FCM算法后的隸屬值均為0.5，而實際上x6的隸屬值應該要大于x12，因為x6更靠近類的中心，可知FCM算法對噪聲比較敏感。PCM算法運行后的典型值分別為0.62和0.08，因為x12比x6更加非典型，其值比x6的典型值要小，故PCM算法減少了噪聲數據的影響。PFCM算法運行后的典型值分別為0.49和0.07，而本文算法運行后的典型值分別為0.21和0.02，相比PCM算法，這兩種算法的典型值要小些，這就減少了噪聲的影響，相比沒有典型值的FCM算法，這兩種算法都適合處理含噪聲的數據，且本文算法更適合處理含噪聲的數據集。一般可用算法運行后的聚類中心與真實聚類中心之間的歐氏距離來衡量算法所得聚類中心的偏差。對于PFCM算法和本文算法，可以不斷調整a、b的值來計算類中心，選擇合適的a、b值可得到最佳的聚類中心。從表4可知，本文算法所得聚類中心離真實類中心最近，其次是PFCM算法，最后是PCM算法，這就說明對含有噪聲的數據，本文算法所得的聚類中心比上述算法更接近真實類中心。

Table 3 Coordinate values of data set X12，memberships and typical values of the algorithms表3 X12數據集的坐標值及各算法運行后的隸屬值和（或）典型值

5 結束語

針對經典FCM算法的缺陷，本文提出了基于樣本－特征加權的可能性模糊核聚類算法，將可能性聚類應用到模糊聚類中并與FCM算法相結合，在聚類過程中，動態計算各屬性特征對聚類類別的權重系數及樣本對聚類的重要性權值，并優化選取核參數，不斷修正核函數，把原始空間中非線性可分的數據集轉化為高維空間中的可分數據集。通過實驗將該算法與FCM算法、PCM算法、PFCM算法的聚類性能進行對比，結果表明，基于樣本－特征加權的可能性模糊核聚類算法能有效反映屬性間的不平衡性，減少噪聲數據和例外點的影響，具有更高的聚類精度，比傳統的聚類算法具有更好的聚類性能。同時，在聚類算法中如何選取合適的參數值，這需要不斷通過實驗進行驗證。在本文中是將算法運行多次并取不同的參數值，將具有最優聚類效果的參數作為最終的實驗參數，因此算法中實驗參數的選取、修正核函數的選擇以及核參數的優化等，都是本文算法有待繼續研究的地方。

［1］ Sun J G，Liu J，Zhao L Y.Clustering algorithms research［J］.Journal of Software，2008，19（1）：48－61.（in Chinese）

［2］ Kirindis S，Chatzis V.A robust fuzzy local information C－means clustering algorithm［J］.IEEE Transactions on Image Process，2010，19（5）：1328－1337.

［3］ Cai W，Chen S，Zhang D.Fast and robust fuzzy C－means clustering algorithms incorporating local information for image segmentation［J］.Pattern Recognition，2007，40（3）：825－838.

［4］ Tian Jun－wei，Huang Yong－xuan，Yu Ya－lin.A fast FCM cluster multi－threshold image segmentation algorithm based on entropy constraint［J］.Pattern Recognition and Artificial Intelligence，2008，21（2）：221－226.（in Chinese）

［5］ Pal N R，Pal K，Keller J，et al.A possibilistic fuzzy C－means clustering algorithm［J］.IEEE Transactions on Fuzzy System，2005，13（4）：517－530.

［6］ Yu Shui－ying，Ding Hua－fu，Fu Zhi－chao.Study on text cat－egorization based on genetic algorithm and fuzzy clustering［J］.Computer Technology and Development，2009，19（4）：131－142.（in Chinese）

［7］ Xu Song－rong.The fuzzy clustering method based on genetic arithmetic［J］.Journal of Huazhong University of Science and Technology（Nature Science Edition），2004，32（10）：217－219.（in Chinese）

［8］ Wang L J，Guan S Y，Wang X L，et al.Fuzzy C mean algorithm based on feature weights［J］.Chinese Journal of Computers，2006，29（10）：1797－1803.（in Chinese）

［9］ Shen Hong－bin，Yang Jie，Wang Shi－tong.Attribute weighted mercer kernel based fuzzy clustering algorithm for general non－shpherical datasets［J］.Soft Computing，2006，10（11）：1061－1073.

［10］ He Yang－cheng，Wang Shi－tong，Jiang Nan.Mercer－kernel based mixed C－means fuzzy clustering algorithm with attributes weights in feature space［J］.Computer Engineering and Applications，2011，47（23）：159－163.（in Chinese）

［11］ Cai Jing－ying，Xie Fu－ding，Zhang Yong.New fuzzy clustering algorithm based on feature weighted Mahalanobis distances［J］.Computer Engineering and Applications，2012，48（5）：198－200.（in Chinese）

［12］ Liu Bing，Xia Shi－xiong，Zhou Yong，et al.A sample－weighted possibilistic fuzzy clustering algorithm［J］.Acta Electronica Sinica，2012，2（2）：371－375.（in Chinese）

［13］ Yang M S，Wu K L.Unsupervised possibilistic clustering［J］.Pattern Recognition，2006，39（1）：5－21.

［14］ Pan Qing－feng，Chen Shui－li，Chen Guo－long.Study on fuzzy C－means clustering algorithm based on kernel function［J］.Journal of Jimei University：Natural Science，2006，11（4）：369－373.（in Chinese）

［15］ Zhang Xiang，Xiao Xiao－ling，Xu Guang－you.A new method for determining the parameter of Gaussian kernel［J］.Computer Engineering，2007，6（12）：52－56.（in Chinese）

［16］ Amari S，Wu S.Improving support vector machine classifiers by modifying kernel functions［J］.Neural Networks，1999，12（6）：783－789.

［17］ Li Hong－ying，Zhong Bo.Modifying kernel function for support vector machines classifier［J］.Computer Engineering and Applications，2009，45（24）：53－55.（in Chinese）

［18］ Tushir M，Srivastava S.A new kernelized hybrid C－mean clustering model with optimized parameters［J］.Applied Soft Computing，2010，10（2）：381－389.

［19］ Pal N R，Pal K，Bezdek J C.A new hybrid C－means clustering model［C］∥Proc of the IEEE International Conference on Fuzzy Systems，2004：179－184.

附中文參考文獻：

［1］ 孫吉貴，劉杰，趙連宇.聚類算法研究［J］.軟件學報，2008，19（1）：48－61.

［4］ 田軍委，黃永宣，于亞琳.基于熵約束的快速FCM聚類多閾值圖像分割算法［J］.模式識別與人工智能，2008，21（2）：221－226.

［6］ 于水英，丁華福，付志超.基于遺傳算法和模糊聚類的文本分類研究［J］.計算機技術與發展，2009，19（4）：131－142.

［7］ 許松榮.基于遺傳算法的模糊聚類算法［J］.華中科技大學學報（自然科學版），2004，32（10）：217－219.

［8］ 王麗娟，關守義，王小龍，等.基于屬性權重的 Fuzzy CMeans算法［J］.計算機學報，2006，29（10）：1797－1803.

［10］ 賀楊成，王士同，江南.特征空間屬性加權混合C均值模糊核聚類算法［J］.計算機工程與應用，2011，47（23）：159－163.

［11］ 蔡靜穎，謝福鼎，張永.基于馬氏距離特征加權的模糊聚類新算法［J］.計算機工程與應用，2012，48（5）：198－200.

［12］ 劉兵，夏士雄，周勇，等.基于樣本加權的可能性模糊聚類算法［J］.電子學報，2012，2（2）：371－375.

［14］ 潘慶豐，陳水利，陳國龍.基于核函數的模糊C均值聚類算法［J］.集美大學學報，2006，11（4）：369－373.

［15］ 張翔，肖小玲，徐光佑.一種確定高斯核函數模型參數的新方法［J］.計算機工程，2007，6（12）：52－56.

［17］ 李紅英，鐘波.支持向量分類機的修正核函數［J］.計算機工程與應用，2009，45（24）：53－55.