半監督聚類算法

聚類是人類一項最基本的、最重要的認識活動, 在許多領域中被廣泛地應用。 半監督學習是近幾年來 在機器學習領域新發展的一種學習方法,國外半監督 聚類的研究開始得比較早,已經取得了一定的成果。Janne Sinkkonen 和Samul Kaski 等人在2000 年及以後提出了相關的算法研究, 並初步應用在基因分析、文本內容挖掘等領域,取得了很大的進步。國內也有部分學者正在研究半監督聚類算法及其應用,相對來説研究工作還比較少。

目前半監督聚類中常見的先驗知識表現為反映樣本間相似關係的約束條件文獻[3] ^[1]  對約束條件的定義,即兩個樣本屬於同一類為 Must-Link ,不屬於同一類的則為 Cannot-Link。約束條件用於半監督聚類主要有兩大類方法:基於約束的方法和基於距離的方法。前者將約束作為聚類目標的一部分直接作用於聚類算法,並且依靠用户提供的標號或約束來指導 算法,產生更合適的數據劃分;後者是使用一種自適 應距離度量,該度量已經被訓練,以滿足監督數據中的標號或根據約束構造某種距離度量並以此為基礎 運行各種聚類算法,文獻[4] ^[2]  提出一種對現有約束進行擴展的方法,即基於密度的約束擴展方法(DCE),擴展後的約束集可用於各種半監督聚類算法。另外,半監督聚類挖掘方面的研究領域還表現在異常入侵檢測算法、數據集空間結構的半監督聚類方法、基於半監督聚類的 Web 流量分類、隱馬爾可夫樹(HMT) 模型、隱馬爾可夫隨機場(HMRF)模型、SAR 圖像小波係數隱狀態的迭代算法。

半監督聚類分析來源於綜合研究領域,包括數據 挖掘、統計學、生物學、數據安全以及機器學習、地理、 Web 文檔分類、仿真等。其應用也是相當廣泛,例如市 場或客户分割、模式識別、生物學研究、空間數據分 析、Web 文檔分類、異常檢測、數據流挖掘。 它可以成為一種單獨的數據挖掘工具。

沒有一種算法是十全十美的,根據實際情況使用綜合性的半監督聚類算法。 半監督聚類是近幾年機器學習領域的一個 新的研究方向,隨着應用的日益廣泛,需處理的數據量越來越大、越來越複雜,維數越來越高,可以利用有效處理二維和小的數據集的半監督聚類方法進行強化和修改,以使其能處理大的和高維的數據集。

將物理或抽象對象的集合分成相似的對象類的 過程稱為聚類(Clustering)。 簇是數據對象的集合,這 些對象與同一個簇中的對象彼此相似,而與其他簇中 的對象相異。 聚類分析是一種重要的人類活動,已經 成為數據挖掘研究領域中一個非常活躍的研究課題, 現有的數據挖掘以及聚類的主要算法如圖 1。

近幾年機器學習領域的一個新的研究方向是半 監督聚類(Semi-Supervised Clustering)。 本文對數據挖掘半監督聚類算法的研究現狀及發展趨勢進行了 分析與概括,並比較分析了七種典型半監督聚類算法 (圖 2)的優點與侷限性,以便於對半監督聚類算法作 進一步的研究。

基於模型方法就是為每個聚類假設一個模型,然後再去發現符合相應模型的數據對象。一個基於模型 的算法可以通過構造一個描述數據點空間分佈的密度函數來確定具體聚類。它根據標準統計方法並考慮到噪聲或異常數據,可以自動確定聚類個數。

在上世紀 70 年代末源於統計力學的馬爾可夫隨機場(Markov Random Field,MRF)理論開始應用於圖像處理領域。MRF通過描述圖像相鄰像素之間的相 互關係,有效地表達了圖像的上下文信息。自1984年以來 , 在 S. Geman 和 D. Geman 所做的奠基性工作之上,在圖像處理領域中許多研究者開始不斷地改進 或者提出新的基於 HMRF 模型。模型的圖像分割算法文獻[5] ^[3]  提出了一種隱馬爾可夫隨機場(HMRF),這 種模型是一種距離與約束條件相結合的半監督聚類分析方法,利用它可以解決圖像分割問題,對於每一階模型的圖像分割,該算法充分利用了相鄰模型之間 的相關信息,該算法克服了均值場算法對初始化條件要求非常苛刻的缺點。文獻[6] ^[4]  提出一種基於 HMRF 模型的無監督圖像分割算法,這種算法克服了均值場 算法對初始化條件要求非常苛刻的缺點,並且算法避免了對某些無意義的模型階次進行分析,減少了整個算法的計算量。

隱馬爾科夫樹模型(HMT)在圖像去噪方面應用較多的一種模型。由於HMT需要大量的迭代運算，隨着小波係數的增多，計算的複雜度也隨着增大。張偉等人提出多小波描述的通用隱馬爾可夫樹模型圖像去噪算法,小波域通用隱馬爾可夫樹(uHMT)模 型充分利用了實際圖像內部的自相似性,僅用極小參數與圖像的大小和小波的尺度數目無關就可以完全確定實際圖像的隱馬爾可夫樹模型 ,極大地簡化了隱 馬爾可夫樹模型 ,但這使得圖像去噪的精度降低。多小波描述在圖像去噪方面取得了較好的效果,但是沒 有更有效的解決算法的複雜性。基於模型的算法依賴 於可用數據的類型,又依賴於應用的特定目標。 ^[5] 

根據約束構造某種距離度量並以此為基礎運行各種聚類算法,已有的半監督聚類方法很少將數據 集的空間結構信息加以利用。基於距離的方法僅根據 約束信息調整樣本間的距離而大部分情況下可用的 約束條件數量較少,因而數據集的空間分佈信息無法 得到有效利用。 因此,可以將數據集結構信息以某種 形式引入基於約束的聚類方法中,以超越有限的約束 條件來得到更好的聚類效果。有幾種不同的自適應距離度量被使用,例如用期望值最大化(EM)方法訓練 得到的串編輯距離(String-Edit Distance)和由最短距離算法修訂過的歐幾里得距離。文獻[4] ^[2]  提出一種對現有約束進行擴展的方法,即基於密度的約束擴展方 法(DCE),這種方法的優點是將數據集結構信息引入 聚類,在約束條件較少;不足以反映數據集分佈特點 時,可以達到更好的聚類效果,擴展後的約束集可用 於各種半監督聚類算法。基於模型方法與基於距離的 方法都是從全局角度來考慮的方法,當數據集合密度 不均或者有多種分佈時效果不佳。 ^[5] 

基於約束的方法是一種結合用户指定或面向應 用的約束進行半監督聚類的方法。 文獻[3] ^[1]  對約束條件的定義, 即兩個樣本屬於同一類為 Must-Link ,不 屬於同一類的規則為 Cannot-Link。 基於約束的方法 是約束條件用於半監督聚類的另一主要方法。它以約束作為聚類目標的一部分直接作用於聚類算法, Re- nato Cordeiro de Amorim Birkbeck 等提出一種增強的K-means 聚類算法:基於約束條件少,有效提高效果, 雖然這一方法可以有效地提高輸出效果,但是,當增加約束條件或增加樣本集的情況下,該方法可能得不到較好的效果。 ^[5] 

文獻[7~8]密度敏感的距離測度在特定圖像聚類中的應用算法以及一種改進的密度敏感的半監 督聚類算法[7]。 在文獻[8]中提出一種新的基於圖的半監督學習算法, 稱為密度敏感的半監督聚類算法 (DS-SC),該算法引入一種密度敏感的距離測度,它能 較好地反映聚類假設,並且充分挖掘了數據集中複雜的內在結構信息,同時與基於圖的半監督學習方法相 結合,使得算法在聚類性能上有了顯著的提高。 文獻 [7] ^[6]  提出一種改進的密度敏感的半監督聚類算法,一種改進的密度敏感的距離測量,可有效地擴大數據點 之間的距離在不同的高密度地區和在同一高密度地 區縮短數據點之間的距離。此外,半監督學習算法改 進了密度敏感的半監督聚類 (入侵檢測系統-SC)的 算法。 ^[5] 

Janne Sinkkonen 和Samul Kaski 等人提出一種基於空間條件分佈的半監督聚類方法(AMSC)。 這 種方法把主空間的信息投影到輔助空間,利用輔助空 間完成迭代優化過程。 AMSC 輔助空間的引入使聚類 效果進一步改善,但是主空間的變化對聚類過程的影 響被減弱,不能夠很好地迭代優化,在迭代過程中算法不穩定,往往收斂於局部最小,不能有效地處理局部極值問題。為了避免上述不足, 文獻 [9~10] ^[7-8]  提出 DMSC 聚類算法, 把主空間和輔助空間結合起來,共 同影響着聚類過程,引入兩個近鄰測度函數,一個近鄰測度是基於輔助空間的, 採取Kullback-Leibler 距離,第二個近鄰測度是基於主空間的。使用 DMSC 算法,不易陷入局部最優,受初始點影響小,提高了聚 類的有效性,但是必須尋找合適的 K 值和下降函數。 ^[5] 

這種算法首先將數據空間劃分成為有限個單元 的網格結構, 所有的處理都是以單個的單元為對象的。處理速度通常與目標數據庫中記錄的個數無關, 它只與單元的個數有關,故這種算法的一個突出優點就是處理速度很快。代表算法有DenClue算法和 CLIQUE算法 。 ^[5] 

從傳統的聚類方法中,適當地加入約束條件進行 判別分析,該方法更加有效,有利於提高算法的性能。比較著名的算法有 Bayes 判別法、Fisher 判別函數法、距離函數法和K-近鄰法、Jensen-Shannon 梯度下降法、歐式距離修改最短路徑法[9]等。

Bayes判別法利用以往對研究對象的認識, 以先驗概率來輔助判斷,希望得到更精確的分析結論。誤判概率最小、風險最小,但是 Bayes 判別法需要已知條件概率,而且其決策面往往是超曲面,形狀複雜,難 以計算和構造。

文獻[11] ^[9]  提出一種基於成對約束的判別型半監督聚類分析方法(Discriminative Semi-Supervised Clus- tering Analysis with Pairwise Constraints,DSCA)。這種方法第一步利用Must-Link 和Cannot-Link 成對約束產生投影矩陣,在投影空間中對數據聚類生成聚類標 號;第二步,利用線性判別分析(Linear Discriminant Analysis,LDA)選擇子空間;第三步,使用基於成對約 束的 K 均值算法對子空間中的數據聚類。 DSCA 有效 地利用了監督信息集成數據降維和聚類, 降低了基於 約束的半監督聚類算法的計算複雜度。 ^[5] 

半監督聚類算法在很多實際領域中已獲得廣泛應用.在生物信息處理方面,Huang&Pan綜合基因本體(GeneOntology, GO)信息提出一種 K-medoids 的擴展算法。Tari等人提出 GO模糊 C-means, 可自動確定聚類的個數 .Cecareli等人用度量學習(MetricLearning)方法對模糊聚類算法進行改進.在文本分類問題上, Huang&Lam提出一種主動學習方法用於半監督文本聚類.在網絡入侵檢測領域, Erman等人將半監督聚類用於網絡中 P2P數據 包的實時分類.在圖像處理方面, Chang和 Yeung 提出局部線性自適應度量 (LocalyLinerMetricAd-aptation, LLMA)方法用於半監督聚類和圖像檢索,Bensaid等人將半監 督聚類用於圖像分割.在其它方面如GPS數據中的道路檢測、邊緣檢測等領域的應用,均取得較好效果。 ^[10]