模糊聚類算法的研究與實現

摘要：聚類就是按照事物間的相似性進行區分和分類的過程，傳統的聚類分析是一種硬劃分，它把每個待辨識的對象嚴格地劃分到某個類中，具有非此即彼的性質，因此這種分類的類別界限是分明的。而實際上大多數對象并沒有嚴格的屬性，它們在形態和類屬方面存在著中介性，適合進行軟劃分。1965年，模糊理論的創始人Zadeh提出的模糊集理論為這種軟劃分提供了有力的分析工具，人們開始用模糊的方法來處理聚類問題，并稱之為模糊聚類。該文主要內容是研究和實現基于等價關系的模糊聚類算法，該算法以隸屬度作為聚類的出發點，以模糊等價矩陣作為啟發規則。首先根據給出的樣本，通過數據標準化求得數據矩陣；其次根據數量積法對數據矩陣進行標定即建立模糊相似矩陣；再次通過傳遞閉包法把模糊相似矩陣轉換成模糊等價矩陣，在模糊等價矩陣中取不同的元素作為閾值λ，再根據λ截矩陣的定義把模糊等價矩陣轉換成只有0和1的矩陣；最后，把該矩陣中元素相同的列聚為同一類。通過實例分析運用基于等價關系的模糊聚類算法進行聚類結果是正確的。

關鍵詞：模糊集；模糊聚類；模糊等價矩陣；傳遞閉包

中圖分類號：TP301文獻標識碼：A文章編號：1009-3044(2008)27-1987-04

The Research and Realization of Fuzzy Clustering Algorithm

LU Qiu-gen

(Department of Computer， Jiangxi Institute of Commerce， Nanchang 330100， China)

Abstract: Clustering is a process that assorts things by their similarity，traditional clustering analysis assorts things strictly， therefore the border of the classification is very clearly. But in fact most of things have no obvious border. The border is vague， so soft classification is a good way to process them. In 1965 Professor Zadeh proposed the theory of fuzzy sets， which offers a powerful tool to solve the problem. People begin to use fuzzy way to deal with clustering problem.This text has analyzed the fuzzy cluster's algorithm based on equivalent relation in fuzzy clustering. This algorithm begins with membership degree and uses fuzzy equivalent matrix as heuristic rules. The clustering algorithm is detailed as follows. Firstly， getting samples and normalizing. Secondly， building fuzzy similar matrix by dot product. Thirdly transferring fuzzy similar matrix into fuzzy equivalent matrix by transitive closure， and choosing different λ， then building 0-1 matrix according to λ. Lastly， doing clustering by same columns.Then， the realized fuzzy clustering algorithm based on equivalent relation is applied into an instance， the result is correct.

Key words: fuzzy set; fuzzy clustering; fuzzy equivalent matrix; transitive closure

1 引言

聚類是人類最基本的一項認識活動，人類要認識世界就必須區別不同的事物并認識事物間的區別與聯系，并且是伴隨著人類的產生和發展而不斷深化的一個問題。所謂聚類，它是一種研究分類的多元分析方法，就是按照事物的某些屬性，將事物分成多個類或簇，所以又稱為簇分析、群分析，它的做法是使得在同一類中的事物相似性盡可能的大，不同類別間的事物相似性盡可能的小。

經典分類學往往是從單因素或有限的幾個因素出發，憑經驗和專業知識對事物分類。這種分類具有非此即彼的特性，同一事物歸屬且僅歸屬所劃定類別中的一類，因此這種分類的類別界限是分明的，所以這種分類又被稱為硬分類。隨著人們認識的深入，發現這種分類越來越不適用于對具有含義模糊的事物進行分類。如把人按身高分為“個子高的人” ，“個子矮的人” ，“身材中等的人” 。如何判別特定的一個人的類別便產生了經典分類學解決不了的難題。而這類問題適合進行軟分類，模糊數學的產生就為軟分類提供了數學基礎，由此產生了模糊聚類分析。把應用普通數學方法進行分類的聚類方法稱為普通聚類分析，而把應用模糊數學方法進行分析的聚類分析稱為模糊聚類分析。由于模糊聚類得到了樣本屬于各個類別的不確定性程度，表達了樣本類屬的中介性，即建立起了樣本對于類別的不確定性的描述，能更客觀地反映現實世界，從而成為聚類分析研究的主流。

2 基于等價關系的模糊聚類算法的設計與實現

2.1 算法的設計

模糊聚類包含下面三個步驟：

1) 數據標準化

① 數據標準化的作用得到數據矩陣；

② 數據標準化的方法。

在實際問題中，不同的數據一般會有不同的量綱，為了使不同量綱的數據也能進行比較，通常需要對數據進行適當的變換。但是，即使這樣，得到的數據也不一定在區間[0，1]上，因此，要對數據進行標準化，就是根據模糊矩陣的要求，將數據壓縮到區間[0，1]上。數據標準化要作下面兩種變換。

經過標準差變換后，每個變量的均值都為0，標準差為1，并且消除了量綱的影響。但是，這樣得到的x'ik還不一定在[0，1]上，所以還要作下一個變換，即平移極差變換。

②平移極差變換。

經過平移極差變換后，顯然有0≤x'ik≤1，量綱的影響。

2) 模糊相似矩陣的建立

建立模糊相似矩陣又稱為標定，即標出衡量被分類的對象之間相似程度的統計量rij (i=1，2，…n，j=1，2，…n)。設論域U={xl， x2，x3，…，xn}，xi={xil，xi2，xi3，…，xim}依據傳統聚類方法確定相似系數，建立模糊相似矩陣，xi與xj的相似程度rij=R(xi，xj)。確定rij=R(xi，xj)的方法主要是借用傳統聚類分析的相似系數法、距離法以及其他方法。可以計算rij的方法很多，要根據問題的性質來決定具體使用什么方法。本文采用的是數量積法。

3) 模糊聚類

模糊等價矩陣能對論域進行等價的劃分，能夠滿足聚類分析的需要。然而，在通常的情況下，由標定過程構造出的模糊關系僅僅能滿足自反性和對稱性，而不滿足傳遞性，所以生成的只是一個模糊相似矩陣R，而不是模糊等價矩陣，所以為了進行分類，還要在這個模糊相似矩陣的基礎之上去生成一個模糊等價矩陣，最自然的方法就是去求該模糊相似矩陣R的傳遞閉包t(R)，這樣便可以得到一個模糊等價矩陣。當生成模糊等價矩陣后，求出閾值λ(λ∈[0，1])，然后根據λ-截矩陣的定義把模糊等價矩陣轉換成只有0和1的矩陣；再根據聚類的原則，把上述矩陣中列中元素相同的列作為同一類，把不同的列聚到不同的類。如果依次將λ閾值從1變小至0時，便可以得到X的一個逐漸由細變粗的動態聚類。在這個方法中，由于模糊等價矩陣是采用傳遞閉包的方法得到的，故稱此方法為傳遞閉包法。

可見，采用傳遞閉包法進行聚類的過程，可以歸納為以下的兩個步驟：

①生成模糊等價矩陣：由一個模糊相似矩陣通過求閉包生成一個模糊等價矩陣；

②劃分：由大到小，依次取實數λ∈[0，1]，計算Rλ，再根據Rλ對X進行劃分。最后便得到在不同的水平下對事物的劃分。

2.2 模糊聚類實例

為了能夠更好地理解模糊聚類的步驟，接下來通過一個環境單元分類來解釋。

每個環境單元包括四個要素：空氣、水分、土壤和作物，而環境單元的污染情況可以由污染物在四個要素中含量的超限度來進行描述。表1是對五個環境單元的污染狀所做的記錄。

這個等價布爾矩陣把X劃分一類：{a， b， c， d， e}。

由聚類結果可以看出，當閾值λ從1到0的變化過程中，當λ取值越大，矩陣包含的元素就越少，聚類就越多；反之，當λ取值越小，矩陣包含的元素就越多，聚類就越少。

2.3 算法的實現

用VC++實現算法的源代碼如下：

void SimilarArray(float array[][4]，int row，int col，float r[][10]，int rrow，int rcol)

//數量積法求出模糊相似矩陣

{int i，j，k;

float r1[10][10];

float m=55.25;

for(i=0;i

for(j=0;j

{if(i==j) r[i][j]=1;

else {r1[i][j]=0;

for(k=0;k

r1[i][j]=array[i][k]*array[j][k]+r1[i][j]; //數量積法

r[i][j]=r1[i][j]/m; }}

cout<<\"輸出的模糊相似矩陣：\"<

for(i=0;i

{for(j=0;j

printf(\"\\");}

cout<

void ArrayUnion(float r0[][10]，int r0row，int r0col，float r1[][10]，int r1row，int r1col)

//矩陣合成為一個新定義的矩陣

{floattemp[10];

for(int i=0;i<10;i++)

{for(int j=0;j<10;j++){

for(int k=0;k<10;k++)

{temp[k]=r0[i][k]<=r0[k][j]?r0[i][k]：r0[k][j]; //條件選擇語句且選小數}

for(int var1=0;var1<9;var1++)

{if(temp[var1]>=temp[var1+1]) //進行比較，選擇大的

temp[var1+1]=temp[var1];}

r1[i][j]=temp[9]; }}}

int FuzzyEqualArray(float r[][10]，int rrow，int rcol，float r1[][10]，int r1row，int r1col)

{int pos=0;//標記一個位子號碼

for(int i=0;i

{for(int j=0;j

{break;}

else pos++; }}

cout<

if(pos<(rrow*rcol))

{ArrayUnion(r1，r1row，r1col，r，rrow，rcol);}

return pos;}

void ProcessFuzzy(float r[][10]，int rrow，int rcol，float r1[][10]，int r1row，int r1col)

{int pos=FuzzyEqualArray(r，10，10，r1，10，10);

while(pos<100) {

pos=FuzzyEqualArray(r1，10，10，r，10，10);

if(pos>=100)

break;

pos=FuzzyEqualArray(r，10，10，r1，10，10);//滿足傳遞閉包法，用新合成的矩陣代替舊矩陣

}

cout<<\"輸出的模糊等價矩陣：\"<

for(int i=0;i<10;i++)

{for(int j=0;j<10;j++)

{printf(\"%.3f\"， r[i][j]);}

printf(\"\\");}

cout<

void GetNUm(float r[][10]，int rrow，int rcol，float Num[])

{ int i=0;

float temp[100];

for(int var1=0;var1

{for(int var2=0;var2

{temp[i++]=r[var1][var2]; //降維處理，變成一元矩陣}}

i=0;

Num[i++]=temp[0];

for(var1=1;var1<100;var1++)

{int var2=i-1;

while(var2>=0){if(temp[var1]!=Num[var2]) //進行比較，得出閾值

var2--;

else

break;}

if(var2<0)

Num[i++]=temp[var1];}

for(i;i<50;i++)

Num[i++]=-1;}

void JuLei(float r[][10]，int rrow，int rcol，float num)

{for(int i=0;i

for(int j=0;j

{if(r[i][j]>=num)//模糊聚類

r[i][j]=1;

else

r[i][j]=0;}}

3 結束語

本文介紹了模糊聚類理論的相關知識，本文主要研究的是基于等價關系的模糊聚類算法，該算法使用隸屬度作為聚類的出發點，將模糊等價矩陣作為啟發規則。通過對基于模糊等價關系的模糊聚類算法的研究得出了以下結論：對同一個傳遞閉包（等價矩陣）來說，它可能是由不同的相似矩陣得到的，而且這些相似矩陣很可能差別很大，卻都用同一個等價矩陣來聚類，自然聚類結果可能不正確，這就是傳遞閉包法的缺陷，。改進的措施是用最優等價矩陣這個概念，具體做法就是先通過相似矩陣求出它的傳遞閉包，即等價矩陣，在利用等價矩陣的一些性質和定理對這個矩陣進行一系列的變換，同時在變換過程中計算它到相似矩陣的歐氏距離，直到求得距離最小為止。

參考文獻：

[1] PAWLAK Z. Fuzzy set[J]. International journal of computer and information science，1982:321-396.

[2] CHAN C C.A Fuzzy set approach to attribute generalization in datamining[J]. Journal of information science，2000:119-176.

[3] 史忠植．知識發現[M]．北京：清華大學出版社，2005.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文?！?/p>