改進的粗糙模糊和模糊粗糙K-均值聚類算法

田大增，吳靜

1.河北大學物理科學與技術學院，河北保定 071002

2.河北大學數學與計算機學院，河北保定 071002

改進的粗糙模糊和模糊粗糙K-均值聚類算法

田大增1，吳靜2

1.河北大學物理科學與技術學院，河北保定 071002

2.河北大學數學與計算機學院，河北保定 071002

在分析歸納原有聚類方法不足的基礎上，結合粗糙理論和模糊理論，給出了改進的粗糙模糊K-均值聚類算法；設計了新的模糊粗糙K-均值聚類算法，并驗證了該聚類算法的有效性；進而將這兩種聚類算法應用到支持向量機中，對訓練樣本做預處理，以減少樣本數目，提高了其訓練速度和分類精度。

粗糙模糊K-均值聚類；模糊粗糙K-均值聚類；支持向量機

1 引言

隨著信息技術的迅猛發展和人們搜集數據能力的日益增強，大量的數據庫被用于商業管理、政府辦公、科學研究和工程開發等領域。因此數據挖掘（Data mining）和知識發現技術應運而生，并得以蓬勃發展，越來越顯示出其強大的生命力。數據挖掘已經引起了人們的廣泛關注，成為國內外數據庫和信息決策領域的最前沿研究方向[1-3]。

聚類[4]是數據挖掘領域最為常用的技術之一。隨著計算機的發展和實際問題的需要，基于目標函數的聚類方法已成為聚類分析的主流。一方面是由于可以將聚類問題表述成優化問題，易與非線性規劃領域聯系起來，可用現代數學方法來求解；另一方面是由于計算機可以比較容易地實現算法的求解過程。各種聚類算法已經在許多領域得到了廣泛的應用，在圖像處理中被應用于圖像分割[5]、圖像增強、圖像壓縮等；在模式識別[6]中，被用于語音識別、雷達目標識別；此外還可以用于模糊推理規則的建立、醫學診斷[7]等。目前，對聚類算法的研究也不斷深入，利用其已有算法的優勢，改進其不足，提出了改進的粗糙模糊K-均值聚類算法和粗糙模糊K-均值聚類算法，使聚類算法更能反映客觀世界。

支持向量機（Support Vector Machine，SVM）[8-9]是數據挖掘中的一項技術，是借助于最優化方法解決機器學習問題的工具。它是Vapnik在統計學習理論基礎上提出的一類機器學習算法。正因為支持向量機的提出，才促進了統計學習理論的應用得到了發展。支持向量機與傳統機器學習方法相比，在解決小樣本、高維度以及非線性問題上具有明顯的優勢。但是，支持向量機作為一種技術，目前仍存在許多局限。SVM的研究主要有兩類問題亟待解決[10]，一方面由于訓練樣本多導致訓練時間可能很長，從而影響到其應用；另一方面，盡管支持向量機方法具有較好的推廣能力，但是由于在構造最優分類面時所有訓練樣本被認為對最優超平面具有相同的作用，所以當訓練樣本中含有噪聲與野值樣本時，由于這些含有異常信息的樣本在特征空間中常常位于分類面附近，因此導致獲得的分類面不是真正的最優超平面。

針對以上問題，如果能夠使用某種方法對支持向量機樣本進行預處理，既減少訓練樣本個數，又可以保留樣本的屬性特征，使得在提高支持向量機的訓練速度的同時又能保證支持向量機的分類精度。本文提出的聚類算法，對支持向量機的訓練樣本進行預處理，能夠減少樣本數目，提高訓練速度；與此同時，又通過定義的一種基于樣本緊密度的新的模糊隸屬函數，能夠減少樣本中噪聲點、孤立點對分類的影響，從而提高分類精度。

2 粗糙模糊K-均值（RFKM）聚類算法的改進算法

RFKM算法是基于粗糙集的上、下近似的概念改進了FKM的目標函數，從而改變了隸屬度函數的分布，使得隸屬度函數的分布更加合理，同時RFKM的時間復雜性比FKM更低。

其中Ai稱為上近似限，上近似限刻畫了所有可能屬于第i類的對象的邊界，若某個對象不屬于上近似限所界定的范圍，則它屬于這個類的負域，即完全不屬于這個類。

定義2[11]粗糙模糊K-均值算法的目標函數為：

同樣可以得到粗糙模糊K-均值算法的迭代公式：

質心計算公式不變：

從RFKM算法很容易得到以下兩個性質：

下面具體給出RFKM算法的步驟[11]：

（1）確定類數k(2≤k≤n)、參數m、初始矩陣、類的上近似邊界Ai和一個適當小數ε＞0，s=0。

（3）若xj?wi，則uij=0，否則按式（11）更新。

（4）若||U(s)-U(s+1)||＜ε，則停止，否則，s=s+1，轉步驟（2）。

RFKM算法的主要思想是把屬于某個類的對象分成了肯定的、可能的和否定的三個集合，以所有可能的對象的最小類內平方誤差和為聚類準則進行聚類。RFKM算法和FKM算法最大的不同在于，它認為xj屬于wi的隸屬度uij的計算只與上近似中包含xj的類有關，若某個類wk的上近似中不包含xj，則這個類對xj的隸屬度是沒有任何貢獻的。

對于上述粗糙模糊K-均值聚類的算法，由于引進了歸一化條件，則在樣本不理想的情況下會導致不好的效果。比如，如果某個樣本遠離歐氏距離的類中心，本來它隸屬各類的隸屬度都很小，但由于歸一化的要求，將會使它對各類都有較大的隸屬度，最終將影響迭代的結果。本文對聚類中隸屬函數進行了改進，從而有效地改進了這些問題。

考慮放松對隸屬度歸一化的要求，改變隸屬度函數的約束條件，將會對噪聲數據有較好的處理能力。則要求算法中各個數據點的隸屬度只需滿足大于零的條件，并且更新了目標函數。通過這種方法產生的各個聚類中心之間相互獨立，即某一點中心的改變不會影響到其他的類中心，因此，改進后的隸屬度可以解釋為數據點屬于某一類的絕對程度。

改進算法的目標函數為：

其中uij∈[0，1]，ηi(i=1，2，…，k)是一個合適的正整數。

利用Lagrange乘數法，可以得到使目標函數取得最小值的條件如下：

一般L取值為1，ηi值控制各個聚類原型之間的距離，其中xj∈wi。

下面具體給出改進后的RFKM算法的步驟：

（1）確定類數k(2≤k≤n)、參數m、初始矩陣、類的上近似邊界Ai和一個適當小數ε＞0，s=0。

（3）若xj?wi，則uij=0，否則按式（4）更新。

（4）如果‖Us-Us+1‖≤ε，迭代終止，否則令s=s+1，返回步驟（2）。

但是在應用中應該注意到，當上近似限取得足夠大時，RFKM算法退化為FKM算法或改進的FKM算法，不同數據集的分布不同，得到Ai理論上的計算公式是困難的一件事情，只能采取一些經驗的方法來確定其上近似限。上近似限取值宜大不宜過小，上近似限取得過小，會使得聚類錯誤率過高。同時不同類之間的上近似限應該盡量地有差別，上近似限不同才能使得不同的類分開的可能性增大。這樣做可以減小對初始隸屬度矩陣的依賴。

3 模糊粗糙K-均值（FRKM）聚類算法及聚類有效性

3.1 模糊粗糙K-均值聚類算法

該算法是對粗糙K-均值聚類算法的一個改進，為每一個樣本點定義一個模糊隸屬函數，使每個樣本點對聚類中心的調節作用因隸屬度的不同而有差別，提高聚類精度。

設數據集合X={x1，x2，…，xn}，聚類中心M={m1，m2，…，mk}（本文中用(mi)，(mi)表示mi對應聚類簇的上，下近似集），用d(xi，mj)表示第i個對象到第j個聚類中心的距離。令表示對象xi到最近的簇中心ml的距離。相應的聚類中心作如下修改，公式如下：

其中wl，wp分別表示第k個簇的下近似集和邊界集在求簇中心時的權重，且wl+wp=1，且由于下近似集對簇中心的影響大，要盡量減少邊界集中的對象對聚類中心的影響，一般wl＞wp，則在基于粗糙K-均值聚類的基礎上，基于粗糙模糊K-均值聚類的聚類算法可描述為：

（1）初始化指數因子m，權重wl，wp，閾值ε(ε∈[0，1])，停止誤差δ(δ∈[0，1])，聚類數k，整數s=0。

（2）令數據集合X={x1，x2，…，xn}，隨機選取k個初始聚類中心M(s)。

（3）設xi為待聚類的向量，如果對于任意的d(xi，mj)，0≤j≤k，有d(xi，mj)-dil≤ε，則xi屬于(ml)，xi屬于(mj)；否則d(xi，mj)-dil＞ε，有xi屬于(ml)。其中l≠j，0≤l，j≤k。

（5）按照公式（5）調節聚類中心，得到新的聚類中心M(s+1)。

該算法利用粗糙K-均值算法的優勢，并在此基礎上引進模糊隸屬函數，使每個樣本在屬于每個粗糙集時具有不同的程度，提高了聚類的精度，并減小了孤立點對聚類的影響。

3.2 聚類的有效性

初始化閾值是對數據進行初始化聚類劃分的依據，K均值算法采用隨機法選取初始聚類中心，選取點的不同，聚類結果可能就不同，這樣的依賴性就導致聚類結果的不穩定性，且容易陷入局部最優而非全局最優聚類結果。而文中提出的改進FRKM聚類算法是在RKM基礎上改進的，引入了模糊的思想，通過引入聚類簇的隸屬度的概念，改進了劃分閾值的敏感性和對于數據比例變換缺乏魯棒性的缺陷，克服了硬劃分算法的缺陷。

從以上模糊粗糙K-均值聚類算法中可以看出，聚類的結果受分類數k和參數m及初始聚類中心的影響，使其在選擇不同參數時正確率存在差異。所以有必要判斷聚類的有效性。以保證聚類的正確率，從而保證將聚類中心作為訓練樣本的有效性。最有效的聚類應在類內緊湊度與類間分離度之間找到一個平衡點，以獲得最好的聚類。本文采用Xie和Beni提出的基于緊密度和分離度的有效性函數[12]作為判斷模糊粗糙K-均值聚類算法有效性的指標。有效性函數為：

其中U是隸屬度矩陣，V是聚類中心矩陣，k是聚類中心數，uic表示U中元素，vi表示V中第i行。分子表示聚類的緊密度，分母表示聚類的分離度。在類內緊湊度和類間分離度之間找一個平衡點，使其達到最小，從而獲得最好的聚類效果。而Vxie越小，表示所有聚類緊密且相互獨立，即為最優聚類。

4 兩種聚類算法的比較

文中引入了RFKM聚類和FRKM聚類這兩種算法，下面簡要說明和比較兩種算法：

（1）RFKM聚類算法在FKM基礎上利用粗糙集的上、下近似的概念，改進了模糊隸屬度矩陣的分布，使該分布更加合理，同時RFKM的時間復雜性比FKM更低。

（2）RFKM聚類算法中引入了上近似界這個參數。而在該算法中，這個參數的選取與調節至關重要。而在現有研究基礎上，只能用經驗來確定。這一點需要在將來進一步研究，來完善該算法的性能。而FRKM聚類算法中把模糊隸屬度作為了聚類中心調節的權重，意在使用模糊隸屬度來表示數據對于中心的調節各自的貢獻不同，從而提高聚類的有效性，但聚類中心的調節公式還有待于進一步完善。

兩種算法在一些數據處理方面各有利弊，則要求在以后的學習、研究中繼承其優勢，改進其缺陷，進一步完善聚類算法。

5 實驗結果與分析

為了更好地實現FRKM聚類算法，在Matlab環境下用frkm_classify，frkm_calcU，frkm_center這三個主要函數來體現這個聚類的過程。函數frkm_classify是實現了FRKM聚類過程中的歸類過程，從而構成了聚類中心數對應的上，下近似集。函數frkm_calcU是更新隸屬度矩陣的過程。在聚類算法中，把模糊隸屬度引進到聚類中心調整中，使各個樣本對聚類中心的作用各不相同。函數frkm_center在訓練階段，要對兩類樣本分別進行聚類的預處理，作用是計算，從而更新聚類中心。本文使用FRKM聚類算法。輸出每一類的聚類中心，然后用輸出的聚類中心做為SVM的新的訓練數據進行訓練。SVM訓練核函數選用線性核函數K(x，xi)= exp(-g‖x-xi‖2)，分類閾值ε=0.1，g=0.5。分別對以下兩組經典數據進行測試：

選定數據集cancer為從經典數據集的Cancer數據集中隨機選取的，取150個作為訓練樣本，50個作為檢驗樣本，其中訓練樣本中1類數據為84個，-1類數據為66個。分別對1類和-1類數據進行聚類，得到聚類中心。經聚類有效性判斷知：當l類數據參數分別為c=10，m=2，ε=0.1，-1類參數分別為c=10，m=2，ε=0.1時，為最優聚類。

選定數據集spambase是從經典數據集的Spambase數據集中隨機選取的，此數據集共有訓練樣本個數1 187個，測試樣本個數40個，維數均為24維。其中訓練樣本中-1類數據568個，1類數據619個。分別對1類和-1類數據進行聚類，得到聚類中心。經聚類有效性判斷知：當l類數據參數分別為c=100，m=2，ε=0.1，-1類參數分別為c=100，m=2，ε=0.1時，為最優聚類。實驗結果見表1。

從實驗結果可以看到，采用原訓練數據的有效聚類中心作為新的訓練數據，從而大大減少了訓練樣本個數，加快了樣本的訓練速度。同時，RFKM和FRKM聚類算法的有效性和聚類中心的代表性避免了噪聲樣本成為訓練樣本的可能性，從而提高了訓練精度，而且FRKM+SVM要比RFKM+SVM精度更高一點。并且，隨著訓練數據的增加，FRKM+SVM算法的優勢愈加明顯。

6 結論

通過分析聚類算法和SVM算法的優缺點，本文在模糊K-均值聚類和粗糙K-均值聚類的基礎上提出了粗

表1 RFKM+SVM算法、FRKM+SVM算法與SVM算法計算結果

糙模糊K-均值聚類（RFKM）的改進和模糊粗糙K-均值聚類（FRKM）算法，用RFKM和FRKM聚類算法對數據進行預處理，從而減少了樣本個數，提高了支持向量機訓練精度和速度。

[1]劉小華，胡學鋼.數據挖掘的應用綜述[J].信息技術，2009，21（9）：149-152.

[2]化柏林.數據挖掘與知識發現關系探析[J].情報理論與實踐，2008，31（4）：507-510.

[3]黃艷玲.數據挖掘在醫學領域中的文獻發展評價[J].現代醫院，2007，7（1）：145-147.

[4]Andrew S T.Computer networks[M].Beijing：Tsinghua University Press，2003.

[5]朱嵬鵬，王世同.基于空間模式聚類的彩色圖像分割[J].計算機工程與應用，2009，45（34）：161-163.

[6]呂佳.核聚類算法及其在模式識別中的應用[J].重慶師范大學學報：自然科學版，2006，23（1）：22-24.

[7]劉木清，周德成，徐新元.聚類算法用于中藥材的近紅外光譜分析[J].光譜學與光譜分析，2007，27（10）：1985-1988.

[8]Vapnik V N.Statistical learning theory[M].New York：Wiley-Interscience Publication，1998.

[9]Vapnik V N，Chervonenkis A Y.The necessary and sufficient conditions for consistency of the method of empirical risk minimization[J].Yearbook of the Academ y of Sciences of the USSR on Recognition，Classification and Forecasting，Nauka，Moscow，1998，2：207-249.

[10]黃嘯.支持向量機核函數的研究[D].江蘇蘇州：蘇州大學，2008.

[11]王丹，吳孟達.粗糙模糊C-均值算法及其在圖像聚類中的應用[J].國防科技大學學報，2007，29（2）：76-80.

[12]Xie X L，Beni G.A validity measure for fuzzy clustering[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1991，13（8）：841-847.

TIAN Dazeng1,WU Jing2

1.Faculty of Physics Science and Technology,Hebei University,Baoding,Hebei 071002,China
2.Faculty of Mathematics and Computer Science,Hebei University,Baoding,Hebei 071002,China

The shortcomings of the original clustering methods are analyzed. Moreover, the rough theory and fuzzy theory are combined together. The improvement of rough fuzzy K-means clustering algorithm is given. A fuzzy rough K-means clustering algorithm is designed, and the validity of fuzzy rough K-means clustering algorithm is verified. The proposed clustering algorithms are applied to support vector machine. In the above applications, the training samples are pre-processed to reduce the number of samples and improve the training speed and the classification accuracy.

rough fuzzy K-mean clustering;fuzzy rough K-mean clustering;support vector machine

TIAN Dazeng, WU Jing. Improvement of rough fuzzy and fuzzy rough clustering algorithm. Computer Engineering and Applications, 2014, 50（17）：142-145.

A

TP311.13

10.3778/j.issn.1002-8331.1210-0203

國家自然科學基金（No.61073121）；河北省自然科學基金（No.A 2012201033，No.F2012402037）；河北省教育廳自然科學青年基金（No.Q2012046）。

田大增（1965—），男，博士，教授，碩士生導師，主要從事不確定統計學習理論和支持向量機等方面的研究；吳靜（1984—），女，碩士，主要從事支持向量機等方面的研究。E-mail：tdz19651204@hbu.cn

2012-10-19

2012-11-26

1002-8331（2014）17-0142-04

CNKI網絡優先出版：2013-01-11,http://www.cnki.net/kcm s/detail/11.2127.TP.20130111.0953.019.htm l