改進(jìn)的粗糙模糊和模糊粗糙K-均值聚類算法

田大增，吳靜

1.河北大學(xué)物理科學(xué)與技術(shù)學(xué)院，河北保定 071002

2.河北大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院，河北保定 071002

改進(jìn)的粗糙模糊和模糊粗糙K-均值聚類算法

田大增1，吳靜2

1.河北大學(xué)物理科學(xué)與技術(shù)學(xué)院，河北保定 071002

2.河北大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院，河北保定 071002

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

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

1 引言

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

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

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

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

2 粗糙模糊K-均值（RFKM）聚類算法的改進(jìn)算法

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

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

定義2[11]粗糙模糊K-均值算法的目標(biāo)函數(shù)為：

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

質(zhì)心計(jì)算公式不變：

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

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

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

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

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

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

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

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

改進(jìn)算法的目標(biāo)函數(shù)為：

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

利用Lagrange乘數(shù)法，可以得到使目標(biāo)函數(shù)取得最小值的條件如下：

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

下面具體給出改進(jìn)后的RFKM算法的步驟：

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

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

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

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

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

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

該算法是對粗糙K-均值聚類算法的一個改進(jìn)，為每一個樣本點(diǎn)定義一個模糊隸屬函數(shù)，使每個樣本點(diǎn)對聚類中心的調(diào)節(jié)作用因隸屬度的不同而有差別，提高聚類精度。

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

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

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

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

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

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

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

3.2 聚類的有效性

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

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

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

4 兩種聚類算法的比較

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

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

（2）RFKM聚類算法中引入了上近似界這個參數(shù)。而在該算法中，這個參數(shù)的選取與調(diào)節(jié)至關(guān)重要。而在現(xiàn)有研究基礎(chǔ)上，只能用經(jīng)驗(yàn)來確定。這一點(diǎn)需要在將來進(jìn)一步研究，來完善該算法的性能。而FRKM聚類算法中把模糊隸屬度作為了聚類中心調(diào)節(jié)的權(quán)重，意在使用模糊隸屬度來表示數(shù)據(jù)對于中心的調(diào)節(jié)各自的貢獻(xiàn)不同，從而提高聚類的有效性，但聚類中心的調(diào)節(jié)公式還有待于進(jìn)一步完善。

兩種算法在一些數(shù)據(jù)處理方面各有利弊，則要求在以后的學(xué)習(xí)、研究中繼承其優(yōu)勢，改進(jìn)其缺陷，進(jìn)一步完善聚類算法。

5 實(shí)驗(yàn)結(jié)果與分析

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

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

選定數(shù)據(jù)集spambase是從經(jīng)典數(shù)據(jù)集的Spambase數(shù)據(jù)集中隨機(jī)選取的，此數(shù)據(jù)集共有訓(xùn)練樣本個數(shù)1 187個，測試樣本個數(shù)40個，維數(shù)均為24維。其中訓(xùn)練樣本中-1類數(shù)據(jù)568個，1類數(shù)據(jù)619個。分別對1類和-1類數(shù)據(jù)進(jìn)行聚類，得到聚類中心。經(jīng)聚類有效性判斷知：當(dāng)l類數(shù)據(jù)參數(shù)分別為c=100，m=2，ε=0.1，-1類參數(shù)分別為c=100，m=2，ε=0.1時，為最優(yōu)聚類。實(shí)驗(yàn)結(jié)果見表1。

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

6 結(jié)論

通過分析聚類算法和SVM算法的優(yōu)缺點(diǎn)，本文在模糊K-均值聚類和粗糙K-均值聚類的基礎(chǔ)上提出了粗

表1 RFKM+SVM算法、FRKM+SVM算法與SVM算法計(jì)算結(jié)果

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

[1]劉小華，胡學(xué)鋼.數(shù)據(jù)挖掘的應(yīng)用綜述[J].信息技術(shù)，2009，21（9）：149-152.

[2]化柏林.數(shù)據(jù)挖掘與知識發(fā)現(xiàn)關(guān)系探析[J].情報理論與實(shí)踐，2008，31（4）：507-510.

[3]黃艷玲.數(shù)據(jù)挖掘在醫(yī)學(xué)領(lǐng)域中的文獻(xiàn)發(fā)展評價[J].現(xiàn)代醫(yī)院，2007，7（1）：145-147.

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

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

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

[7]劉木清，周德成，徐新元.聚類算法用于中藥材的近紅外光譜分析[J].光譜學(xué)與光譜分析，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]黃嘯.支持向量機(jī)核函數(shù)的研究[D].江蘇蘇州：蘇州大學(xué)，2008.

[11]王丹，吳孟達(dá).粗糙模糊C-均值算法及其在圖像聚類中的應(yīng)用[J].國防科技大學(xué)學(xué)報，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

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

田大增（1965—），男，博士，教授，碩士生導(dǎo)師，主要從事不確定統(tǒng)計(jì)學(xué)習(xí)理論和支持向量機(jī)等方面的研究；吳靜（1984—），女，碩士，主要從事支持向量機(jī)等方面的研究。E-mail：tdz19651204@hbu.cn

2012-10-19

2012-11-26

1002-8331（2014）17-0142-04

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-01-11,http://www.cnki.net/kcm s/detail/11.2127.TP.20130111.0953.019.htm l