[發明專利]基于熵排序的半監督譜聚類確定聚類數的方法

無效

• 申請號: 201010278767.2
• 申請日: 2010-09-09
• 公開（公告）號: CN101968852A
• 公開（公告）日: 2011-02-09
• 發明（設計）人: 張向榮;焦李成;楊杰;侯彪;王爽;公茂果;劉若辰;李陽陽
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 王品華;朱紅星

技術領域

本發明屬于圖像處理技術領域，涉及圖像聚類方法，可應用于圖像聚類領域，以自適應地確定聚類數。

背景技術

圖像聚類是圖像處理過程中的一個重要步驟。圖像聚類的目的是將圖像上不同的區域根據圖像像素點之間的關系聚成不同的類。譜聚類是近年來新興的一個聚類方法，該算法的思想起先源于譜圖劃分理論，被看作是一個無向圖的多路劃分問題。譜聚類優于傳統的聚類算法原因在于其不受樣本空間形狀限制且收斂于全局最優解，因此，譜聚類算法在圖像聚類領域得到了廣泛應用。

近年來提出的半監督譜聚類算法是在譜聚類算法的基礎上加入人工標記的類標簽來改良聚類結果的一種方法。這種類標簽以先驗信息的形式出現，一般地，通過修正親和度矩陣來加入先驗信息。類標簽的個數很有講究，太少不足以達到理想的聚類結果，太多又會給計算和存儲帶來過大負擔，因此，加入多少類標簽需要讀者在實際中權衡。

譜聚類中有兩個共同關注的問題，即尺度參數和聚類數的自適應確定。尺度參數確定的方法近年來已經發展得相當完善。本發明主要探討聚類數的確定問題。聚類數的事先確定會使得聚類過程更加的自適應，降低了手工工作量。目前現有的方法大都通過分析由親和度矩陣構造而得的拉普拉斯矩陣的特征值和特征向量入手的。

2001年，A.NG等人指出特征向量等于1的個數即為該組數據的類別數，參見A.Y.Ng，M.I.Jordan，and?Y.Weiss，《On?spectral?clustering：Analysis?and?an?algorithm》，Advances?in?Neural?Information?Processing?Systems(NIPS)。這種方法容易受到噪聲影響而導致聚類結果出現誤差。

2005年，Zelnik-Manor和Perona等人提出的自調節譜聚類(self-tuning?spectral?clustering)算法通過將部分特征向量進行旋轉以構造一個與聚類數相關的目標函數，認為使之達到最小的即為最佳聚類數，參見Zelnik-Manor，L.，and?Perona，P.，《Self-tuning?spectral?clustering》，Advances?in?Neural?Information?Processing?Systems。這種方法能出色地處理一些復雜性問題，但是由于其反復重組旋轉向量大大增加了計算代價，而且，由于要人工設定閾值，所以針對不同數據集，不同實踐者，就產生了誤差，同時帶來了較大工作量。

Zhong等人于2008年提出一種新的自適應譜聚類(adaptive?spectral?clustering，ASC)算法，參見Qingliu，Z.，and?Zixing，C.，《Adaptive?spectral?clustering?algorithm?for?color?image?Segmentation?Application》，Research?of?Computers?25(12)，(2008)。它采用全局平均N近鄰距離的比例參數代替局部N近鄰距離的比例參數，利用相鄰特征向量前k個相鄰列間的平均差異與第一列的比值來確定最佳分類數，直到該比值小于某個給定閾值時對應的k認為是最佳分類數。該算法由于要人工設定閾值，使得它的自調節性大打折扣。

Wang等人于2005年提出的ACNA算法通過特征向量與相應坐標軸的距離將數據點劃分至不同的類，經過若干次的循環迭代最后穩定到的那個k值就認為是最佳的聚類數，參見Chongjun，W.，Wujun，L.，Lin，D.，Juan，T.，and?Shifu，C.，《Image?segmentation?using?spectral?clustering》，Proceedings?of?the?17th?IEEE?In?ternational?Conference?on?Tools?with?Artificial?Intelligence，IEEE?Computer?Society，677-678(2005)。該算法在一定程度上取得了較好的結果，但是對于復雜數據結果就欠理想。

以上自動確定聚類數方法由于均選取前k個最大特征值對應的特征向量，因此存在以下不足：1.易受噪聲影響而導致聚類誤差；2.對大數據結果欠佳或者失效；3.需人工設定閾值。

發明內容