摘 要： 提出了一種高效的增量式模糊聚類算法。該算法僅對新增數據計算相似系數而直接聚類，其結果和廣泛運用的傳遞閉包法、最大支撐樹法等算法相同。
關鍵詞： 模糊聚類 增量式算法 數據挖掘
聚類分析是數據挖掘和知識發(fā)現的重要手段。在聚類分析中，經常存在大量的模糊信息，因此，模糊聚類得到了廣泛的研究和應用。經典的模糊聚類算法在獲得模糊相似矩陣后，需要進一步的計算才能進行聚類分析。面對新增數據只能將全部數據重新聚類。重新聚類不僅計算量大，而且浪費了前期的計算成果?，F代數據庫系統一般規(guī)模龐大，而且數據增長相當迅速。如果能在前期聚類的基礎上，僅對新增數據增量式聚類，則是非常有意義的。為此，本文提出了一種增量式模糊聚類算法。該算法在大大提高聚類分析效率的同時，得到的結果與傳遞閉包法、最大支撐樹法等經典算法相同。
1 模糊聚類算法
經典的模糊聚類算法有傳遞閉包算法、最大支撐樹算法、動態(tài)直接聚類算法、基于攝動的模糊聚類算法等，它們都是在模糊相似關系的基礎上進行聚類的。建立模糊相似關系的關鍵是標定各個數據對象之間的相似系數，相似系數反映了數據對象相對于某些屬性的相似程度。常用的相似系數計算方法有：數量積法、夾角余弦法、距離法、指數相似系數法、絕對值指數法和絕對值倒數法等。
通過標定相似系數可以得到模糊相似矩陣。模糊相似矩陣一般不滿足傳遞性，只滿足自反性和對稱性。因此，模糊相似矩陣不是等價關系矩陣，不能直接用于聚類分析。傳遞閉包法通過求模糊相似矩陣的傳遞閉包得到數據對象的模糊等價關系，而后對數據對象進行聚類分析。
模糊相似矩陣的收斂性是指：對于n階模糊相似矩陣R，存在一個最小自然數k(k<n)，使得其傳遞閉包tr(R)=Rk，且對一切大于k的自然數l，恒有Rl=Rk。這表明通過模糊相似矩陣的平方自乘，可以快速求得模糊相似矩陣的傳遞閉包。在得到傳遞閉包和給定閾值λ（0≤λ≤1）后，求該閉包的截矩陣就可以得到數據對象的聚類。
最大支撐樹法利用了圖論中的有關理論，即在求得模糊相似矩陣后，用圖來表示模糊相似關系，然后求該圖的最大支撐樹。在給定閾值?姿后，截斷最大支撐樹中權值小于λ的邊，得到的若干連通子圖就構成了λ上的聚類。著名的最大支撐樹求解算法有Prim算法和Kruskal算法，它們得到的最大支撐樹可能不同，但聚類的結果是一樣的。
圖1給出的是15個數據的相似系數矩陣。圖2表示用Prim算法對前10個數據求得的最大支撐樹。給定閾值λ=0.8，截斷連接權值小于?姿的邊(虛線所示)，連通子樹形成的聚類用數據的序號表示為：{1，4}，{2，3，5，9}，{6，7，8，10}。
同樣，用最大支撐樹法對全部15個數據進行聚類，得到的聚類結果為：{1，4，6，7，8，10，14，15}，{2，3，5，9，12}，{11，13}。
參考文獻[7]證明了傳遞閉包法、最大支撐樹法、動態(tài)直接聚類法的聚類結果是相同的，它們是互為等價的聚類算法。其他聚類算法的應用也比較廣泛，這里不再贅述。
2 增量式模糊聚類算法
在考察新增數據對已有聚類的影響時，如果某聚類中存在同新增數據的相似系數不小于給定的閾值，則稱這個聚類為新增數據的貼近類。新增數據對已有聚類的影響至多分三種情況：新增數據不貼近于任何已有的聚類；新增數據貼近已有的某一聚類；新增數據同時貼近多個已有的聚類。確定新增數據屬于上述何種情況并對其進行相應的聚類處理，是實現增量式聚類算法的關鍵。
2.1 算法描述
增量式模糊聚類算法的主要思想是：逐個考察新增數據和已有聚類的貼近程度，如果新增數據和某個已有聚類貼近，則新增數據的貼近類計數器s增1；在已有聚類全部考察完畢后，根據s的值對新增數據歸類，或對已有聚類進行調整。下面對增量式模糊聚類算法進行描述。
輸入：已有聚類，新增數據。
輸出：全部數據的聚類?！ ?/p>
算法步驟：
(1)輸入閾值?姿和所有新增數據。
(2)對每一個新增數據，令s=0，執(zhí)行(3)～(5)步。
(3)計算新增數據對已有聚類中數據的相似系數。如果新增數據和這個聚類貼近，則標記這個類貼近，并使貼近類計數器s增1。當前聚類考察結束，考察下一個聚類。
(4)如果對所有聚類都已考察，則轉步驟(5)，否則轉步驟(3)。
(5)聚類。根據s的值，做如下處理：如果s=0，新增數據形成新的聚類；如果s=1，新增數據歸入惟一貼近的類，清除類的貼近標記；如果s>1，合并所有貼近的類，將新增數據歸入此類，并清除各貼近標記。
在用傳遞閉包法、最大支撐樹法或動態(tài)直接聚類法對部分數據進行聚類的基礎上，可以使用增量式聚類算法對新增數據進行聚類。為了保證增量式聚類算法和前述算法重新聚類全部數據的結果相同，這些算法中關于相似系數的求法和閾值λ的設定必須保持一致。下面結合最大支撐樹的生成過程來說明增量式模糊聚類算法和最大支撐樹算法的等價性。
2.2 算法說明
如圖3所示，算法中s的三種取值對應初始最大支撐樹的調整情況。其中加粗的結點和連線表示初始聚類的最大支撐樹，細線表示新增數據貼近最大支撐樹結點的可能情形，有“×”標記的邊將在樹的調整過程中被剪斷，實線標記的邊權值（相似系數）不小于λ虛線標記的邊權值小于λ。
(1)s＝0，新增數據同已有聚類都不貼近。調整后的最大支撐樹有二種可能的形狀：新增結點（圖3(a)中的Y）直接連接到某個結點上，或者新增結點（圖3(a)中的Y′）連接到多個結點上。由于在基于最大支撐樹聚類時，權值小于λ的邊都將被截斷，所以，已有聚類結果保持不變，而新增數據形成新的聚類。
(2)s=1，新增數據僅貼近一個已有聚類。如果已有聚類只存在一個相似數據，則新增結點(圖3(b)中的Y)直接連接到該數據結點；如果已有聚類存在多個相似數據，則剪斷初始連通子樹中權值較小的邊，新增結點（圖3(b)中的Y′）后的子樹仍是最大支撐子樹。無論出現哪種情況，同一子樹中的結點調整后仍在同一個子樹中。因此，調整只將新增數據歸入貼近聚類，而不影響其他的聚類。
(3)s>1，新增數據至少貼近二個已有聚類。當調整產生新的最大支撐樹時，新增結點與多個聚類的結點連接。若同一子樹內產生了回路，其處理方法和圖3(b)中的Y′一樣；而子樹之間必然產生回路，消除回路時剪斷的邊的權值必小于?姿，從而使這些子樹由權值大于?姿的邊連接，合并成了一個如圖3(c)所示的新的子樹。
綜上所述，增量式算法對每個新增數據的歸類及對已有聚類的調整，都和重新生成最大支撐樹的對應調整情況相同，因此，增量式聚類和最大支撐樹法重新聚類的結果是相同的。由于傳遞閉包法、最大支撐樹法、動態(tài)直接聚類法是等價的，故增量式聚類算法也和這些算法之間互為等價。
3 實驗與分析
在采用最大支撐樹法對前10個數據聚類的基礎上，采用增量式聚類算法對后面5個數據進行聚類。對第11個新增數據，已有各類中的數據和它相似的系數都小于?姿，故算法中s＝0，新增數據單獨形成新的聚類，結果如下：
{1，4}，{2，3，5，9}，{6，7，8，10}，{11}
對第12個新增數據，僅第二個聚類存在相似系數不小于?姿的數據，故s=1。新增數據歸入第二個聚類中，結果如下：
{1，4}，{2，3，5，9，12}，{6，7，8，10}，{11}
第13個數據和第12個數據的情況相同，也歸入已有的聚類：
{1，4}，{2，3，5，9，12}，{6，7，8，10}，{11，13}
對第14個數據，第一個和第三個聚類都存在和它相似的、系數不小于?姿的數據，故s=2，這使得上一步的第一個和第三個聚類合并：
{1，4，6，7，8，10，14}，{2，3，5，9，12}，{11，13}
第15個數據和第12、13個類似，歸入已有的聚類：
{1，4，6，7，8，10，14，15}，{2，3，5，9，12}，{11，13}
圖1中已給出了用最大支撐樹法聚類全部15個數據的結果，這一結果和增量式聚類的結果完全相同。在原始聚類結果為空的基礎上，用增量式聚類算法對15個數據聚類，所得到的結果也和上面的結果相同。
增量式聚類算法在效率上比最大支撐樹算法和傳遞閉包法有很大提高。假定全部數據量為n，其中已聚類的數據量為m，增量式聚類算法主要耗時在算法的步驟（3）上，最壞情況下每個新增數據都要針對全部已聚類數據計算相似系數，計算量是：m+(m+1)+……+(m+(n-m-1))=(n2-n+m-m2)/2。在無前期聚類結果的情況下（m=0），其計算量是(n2-n)/2，小于最大支撐樹算法中Prim算法的3n3/2及Kruskal算法的n3～n3log2n，也小于傳遞閉包法的n3～n3log2n，與動態(tài)直接聚類法的計算量3n2/2處在同一數量級。
4 結 論
本文提出的增量式模糊聚類算法和傳遞閉包法、最大支撐樹法、動態(tài)直接聚類法等價，相關實驗結果也證實了這個結論。增量式算法只需對已聚類數據計算相似系數，不用計算已聚類數據之間的相似系數，相對其他算法而言，其計算量已大為減小。
在發(fā)現海量數據庫的知識時，尤其是在數據快速增長的情況下，利用本文所提出的增量式聚類技術，不僅有利于提高聚類分析效率，而且有助于維護和擴充聚類結果，降低知識庫維護的開銷。
參考文獻
1 Zadeh L A.Fuzzy sets.Inf Cont，1965；8（3）
2 Ruspini E H.Numerical methods for fuzzy clustering. Information Sciences，1970；2（3）
3 Dunn J C.A fuzzy relative of the ISODATA process and its use in detecting compact well separated clusters. Cybernetics，1974；3（3）
4 Bezdek J C.Cluster validity with fuzzy sets.Cybernetics， 1974；3（3）
5 韓立巖，汪培莊.應用模糊數學.北京：首都經濟貿易大學出 版社，1989
6 史忠植.知識發(fā)現.北京：清華大學出版社，2002
7 羅承忠.模糊集引論(上冊).北京：北京師范大學出版社，1985