摘   要： 提出了一種高效的增量式模糊聚類算法。該算法僅對新增數(shù)據(jù)計算相似系數(shù)而直接聚類，其結(jié)果和廣泛運用的傳遞閉包法、最大支撐樹法等算法相同。
關(guān)鍵詞： 模糊聚類  增量式算法  數(shù)據(jù)挖掘

　　聚類分析是數(shù)據(jù)挖掘和知識發(fā)現(xiàn)的重要手段。在聚類分析中，經(jīng)常存在大量的模糊信息，因此，模糊聚類得到了廣泛的研究和應(yīng)用。經(jīng)典的模糊聚類算法在獲得模糊相似矩陣后，需要進(jìn)一步的計算才能進(jìn)行聚類分析。面對新增數(shù)據(jù)只能將全部數(shù)據(jù)重新聚類。重新聚類不僅計算量大，而且浪費了前期的計算成果?，F(xiàn)代數(shù)據(jù)庫系統(tǒng)一般規(guī)模龐大，而且數(shù)據(jù)增長相當(dāng)迅速。如果能在前期聚類的基礎(chǔ)上，僅對新增數(shù)據(jù)增量式聚類，則是非常有意義的。為此，本文提出了一種增量式模糊聚類算法。該算法在大大提高聚類分析效率的同時，得到的結(jié)果與傳遞閉包法、最大支撐樹法等經(jīng)典算法相同。
1  模糊聚類算法
　　經(jīng)典的模糊聚類算法有傳遞閉包算法、最大支撐樹算法、動態(tài)直接聚類算法、基于攝動的模糊聚類算法等，它們都是在模糊相似關(guān)系的基礎(chǔ)上進(jìn)行聚類的。建立模糊相似關(guān)系的關(guān)鍵是標(biāo)定各個數(shù)據(jù)對象之間的相似系數(shù)，相似系數(shù)反映了數(shù)據(jù)對象相對于某些屬性的相似程度。常用的相似系數(shù)計算方法有：數(shù)量積法、夾角余弦法、距離法、指數(shù)相似系數(shù)法、絕對值指數(shù)法和絕對值倒數(shù)法等。
　　通過標(biāo)定相似系數(shù)可以得到模糊相似矩陣。模糊相似矩陣一般不滿足傳遞性，只滿足自反性和對稱性。因此，模糊相似矩陣不是等價關(guān)系矩陣，不能直接用于聚類分析。傳遞閉包法通過求模糊相似矩陣的傳遞閉包得到數(shù)據(jù)對象的模糊等價關(guān)系，而后對數(shù)據(jù)對象進(jìn)行聚類分析。
　　模糊相似矩陣的收斂性是指：對于n階模糊相似矩陣R，存在一個最小自然數(shù)k(k<n)，使得其傳遞閉包tr(R)=R^k，且對一切大于k的自然數(shù)l，恒有R^l=R^k。這表明通過模糊相似矩陣的平方自乘，可以快速求得模糊相似矩陣的傳遞閉包。在得到傳遞閉包和給定閾值λ（0≤λ≤1）后，求該閉包的截矩陣就可以得到數(shù)據(jù)對象的聚類。
　　最大支撐樹法利用了圖論中的有關(guān)理論，即在求得模糊相似矩陣后，用圖來表示模糊相似關(guān)系，然后求該圖的最大支撐樹。在給定閾值?姿后，截斷最大支撐樹中權(quán)值小于λ的邊，得到的若干連通子圖就構(gòu)成了λ上的聚類。著名的最大支撐樹求解算法有Prim算法和Kruskal算法，它們得到的最大支撐樹可能不同，但聚類的結(jié)果是一樣的。
　　圖1給出的是15個數(shù)據(jù)的相似系數(shù)矩陣。圖2表示用Prim算法對前10個數(shù)據(jù)求得的最大支撐樹。給定閾值λ=0.8，截斷連接權(quán)值小于?姿的邊(虛線所示)，連通子樹形成的聚類用數(shù)據(jù)的序號表示為：{1，4}，{2，3，5，9}，{6，7，8，10}。

　　同樣，用最大支撐樹法對全部15個數(shù)據(jù)進(jìn)行聚類，得到的聚類結(jié)果為：{1，4，6，7，8，10，14，15}，{2，3，5，9，12}，{11，13}。
　　參考文獻(xiàn)[7]證明了傳遞閉包法、最大支撐樹法、動態(tài)直接聚類法的聚類結(jié)果是相同的，它們是互為等價的聚類算法。其他聚類算法的應(yīng)用也比較廣泛，這里不再贅述。
2  增量式模糊聚類算法
　　在考察新增數(shù)據(jù)對已有聚類的影響時，如果某聚類中存在同新增數(shù)據(jù)的相似系數(shù)不小于給定的閾值，則稱這個聚類為新增數(shù)據(jù)的貼近類。新增數(shù)據(jù)對已有聚類的影響至多分三種情況：新增數(shù)據(jù)不貼近于任何已有的聚類；新增數(shù)據(jù)貼近已有的某一聚類；新增數(shù)據(jù)同時貼近多個已有的聚類。確定新增數(shù)據(jù)屬于上述何種情況并對其進(jìn)行相應(yīng)的聚類處理，是實現(xiàn)增量式聚類算法的關(guān)鍵。
2.1 算法描述
　　增量式模糊聚類算法的主要思想是：逐個考察新增數(shù)據(jù)和已有聚類的貼近程度，如果新增數(shù)據(jù)和某個已有聚類貼近，則新增數(shù)據(jù)的貼近類計數(shù)器s增1；在已有聚類全部考察完畢后，根據(jù)s的值對新增數(shù)據(jù)歸類，或?qū)σ延芯垲愡M(jìn)行調(diào)整。下面對增量式模糊聚類算法進(jìn)行描述。
　　輸入：已有聚類，新增數(shù)據(jù)。
　　輸出：全部數(shù)據(jù)的聚類?！　?/p>

　　算法步驟：
　　(1)輸入閾值?姿和所有新增數(shù)據(jù)。
　　(2)對每一個新增數(shù)據(jù)，令s=0，執(zhí)行(3)～(5)步。
　　(3)計算新增數(shù)據(jù)對已有聚類中數(shù)據(jù)的相似系數(shù)。如果新增數(shù)據(jù)和這個聚類貼近，則標(biāo)記這個類貼近，并使貼近類計數(shù)器s增1。當(dāng)前聚類考察結(jié)束，考察下一個聚類。
　　(4)如果對所有聚類都已考察，則轉(zhuǎn)步驟(5)，否則轉(zhuǎn)步驟(3)。
　　(5)聚類。根據(jù)s的值，做如下處理：如果s=0，新增數(shù)據(jù)形成新的聚類；如果s=1，新增數(shù)據(jù)歸入惟一貼近的類，清除類的貼近標(biāo)記；如果s>1，合并所有貼近的類，將新增數(shù)據(jù)歸入此類，并清除各貼近標(biāo)記。
在用傳遞閉包法、最大支撐樹法或動態(tài)直接聚類法對部分?jǐn)?shù)據(jù)進(jìn)行聚類的基礎(chǔ)上，可以使用增量式聚類算法對新增數(shù)據(jù)進(jìn)行聚類。為了保證增量式聚類算法和前述算法重新聚類全部數(shù)據(jù)的結(jié)果相同，這些算法中關(guān)于相似系數(shù)的求法和閾值λ的設(shè)定必須保持一致。下面結(jié)合最大支撐樹的生成過程來說明增量式模糊聚類算法和最大支撐樹算法的等價性。
2.2 算法說明
　　如圖3所示，算法中s的三種取值對應(yīng)初始最大支撐樹的調(diào)整情況。其中加粗的結(jié)點和連線表示初始聚類的最大支撐樹，細(xì)線表示新增數(shù)據(jù)貼近最大支撐樹結(jié)點的可能情形，有“×”標(biāo)記的邊將在樹的調(diào)整過程中被剪斷，實線標(biāo)記的邊權(quán)值（相似系數(shù)）不小于λ虛線標(biāo)記的邊權(quán)值小于λ。

　　(1)s＝0，新增數(shù)據(jù)同已有聚類都不貼近。調(diào)整后的最大支撐樹有二種可能的形狀：新增結(jié)點（圖3(a)中的Y）直接連接到某個結(jié)點上，或者新增結(jié)點（圖3(a)中的Y′）連接到多個結(jié)點上。由于在基于最大支撐樹聚類時，權(quán)值小于λ的邊都將被截斷，所以，已有聚類結(jié)果保持不變，而新增數(shù)據(jù)形成新的聚類。
　　(2)s=1，新增數(shù)據(jù)僅貼近一個已有聚類。如果已有聚類只存在一個相似數(shù)據(jù)，則新增結(jié)點(圖3(b)中的Y)直接連接到該數(shù)據(jù)結(jié)點；如果已有聚類存在多個相似數(shù)據(jù)，則剪斷初始連通子樹中權(quán)值較小的邊，新增結(jié)點（圖3(b)中的Y′）后的子樹仍是最大支撐子樹。無論出現(xiàn)哪種情況，同一子樹中的結(jié)點調(diào)整后仍在同一個子樹中。因此，調(diào)整只將新增數(shù)據(jù)歸入貼近聚類，而不影響其他的聚類。
　　(3)s>1，新增數(shù)據(jù)至少貼近二個已有聚類。當(dāng)調(diào)整產(chǎn)生新的最大支撐樹時，新增結(jié)點與多個聚類的結(jié)點連接。若同一子樹內(nèi)產(chǎn)生了回路，其處理方法和圖3(b)中的Y′一樣；而子樹之間必然產(chǎn)生回路，消除回路時剪斷的邊的權(quán)值必小于?姿，從而使這些子樹由權(quán)值大于?姿的邊連接，合并成了一個如圖3(c)所示的新的子樹。
　　綜上所述，增量式算法對每個新增數(shù)據(jù)的歸類及對已有聚類的調(diào)整，都和重新生成最大支撐樹的對應(yīng)調(diào)整情況相同，因此，增量式聚類和最大支撐樹法重新聚類的結(jié)果是相同的。由于傳遞閉包法、最大支撐樹法、動態(tài)直接聚類法是等價的，故增量式聚類算法也和這些算法之間互為等價。
3  實驗與分析
　　在采用最大支撐樹法對前10個數(shù)據(jù)聚類的基礎(chǔ)上，采用增量式聚類算法對后面5個數(shù)據(jù)進(jìn)行聚類。對第11個新增數(shù)據(jù)，已有各類中的數(shù)據(jù)和它相似的系數(shù)都小于?姿，故算法中s＝0，新增數(shù)據(jù)單獨形成新的聚類，結(jié)果如下：
　　{1，4}，{2，3，5，9}，{6，7，8，10}，{11}
　　對第12個新增數(shù)據(jù)，僅第二個聚類存在相似系數(shù)不小于?姿的數(shù)據(jù)，故s=1。新增數(shù)據(jù)歸入第二個聚類中，結(jié)果如下：
　　{1，4}，{2，3，5，9，12}，{6，7，8，10}，{11}
　　第13個數(shù)據(jù)和第12個數(shù)據(jù)的情況相同，也歸入已有的聚類：
　　{1，4}，{2，3，5，9，12}，{6，7，8，10}，{11，13}
　　對第14個數(shù)據(jù)，第一個和第三個聚類都存在和它相似的、系數(shù)不小于?姿的數(shù)據(jù)，故s=2，這使得上一步的第一個和第三個聚類合并：
　　{1，4，6，7，8，10，14}，{2，3，5，9，12}，{11，13}
　　第15個數(shù)據(jù)和第12、13個類似，歸入已有的聚類：
　　{1，4，6，7，8，10，14，15}，{2，3，5，9，12}，{11，13}
　　圖1中已給出了用最大支撐樹法聚類全部15個數(shù)據(jù)的結(jié)果，這一結(jié)果和增量式聚類的結(jié)果完全相同。在原始聚類結(jié)果為空的基礎(chǔ)上，用增量式聚類算法對15個數(shù)據(jù)聚類，所得到的結(jié)果也和上面的結(jié)果相同。
　　增量式聚類算法在效率上比最大支撐樹算法和傳遞閉包法有很大提高。假定全部數(shù)據(jù)量為n，其中已聚類的數(shù)據(jù)量為m，增量式聚類算法主要耗時在算法的步驟（3）上，最壞情況下每個新增數(shù)據(jù)都要針對全部已聚類數(shù)據(jù)計算相似系數(shù)，計算量是：m+(m+1)+……+(m+(n-m-1))=(n²-n+m-m²)/2。在無前期聚類結(jié)果的情況下（m=0），其計算量是(n²-n)/2，小于最大支撐樹算法中Prim算法的3n³/2及Kruskal算法的n³～n³log₂n，也小于傳遞閉包法的n³～n³log₂n，與動態(tài)直接聚類法的計算量3n²/2處在同一數(shù)量級。
4  結(jié)  論
　　本文提出的增量式模糊聚類算法和傳遞閉包法、最大支撐樹法、動態(tài)直接聚類法等價，相關(guān)實驗結(jié)果也證實了這個結(jié)論。增量式算法只需對已聚類數(shù)據(jù)計算相似系數(shù)，不用計算已聚類數(shù)據(jù)之間的相似系數(shù)，相對其他算法而言，其計算量已大為減小。
　　在發(fā)現(xiàn)海量數(shù)據(jù)庫的知識時，尤其是在數(shù)據(jù)快速增長的情況下，利用本文所提出的增量式聚類技術(shù)，不僅有利于提高聚類分析效率，而且有助于維護(hù)和擴(kuò)充聚類結(jié)果，降低知識庫維護(hù)的開銷。
參考文獻(xiàn)
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   韓立巖，汪培莊.應(yīng)用模糊數(shù)學(xué).北京：首都經(jīng)濟(jì)貿(mào)易大學(xué)出 版社，1989
6   史忠植.知識發(fā)現(xiàn).北京：清華大學(xué)出版社，2002
7   羅承忠.模糊集引論(上冊).北京：北京師范大學(xué)出版社，1985