聚類分析及其在圖像處理上的應(yīng)用

1、聚類分析及其在圖像處理上的應(yīng)用1緒論1.1基于聚類的圖像處理的研究現(xiàn)狀聚類分析在圖像處理中應(yīng)用廣 泛，其中一項重要的應(yīng)用就是圖像分 割。圖像分割多年來一直受到人們的 高度重視，各種類型的分割算法相繼 被提出。雖然人們在圖像分割方面做 了許多工作，但是至今仍沒有通用的 分割算法，也不存在一個客觀的評價 準(zhǔn)則。大多數(shù)分割算法都是針對一種 具體類型的圖像提出的很難適用于所 有圖像。實際上由于各個領(lǐng)域的圖像 千差萬別，也很難提出萬能的分割算 法?；诰垲惖膱D像分割方法是圖像 分割領(lǐng)域中一類非常重要且應(yīng)用廣泛 的算法。2聚類分析概述2.1聚類的定義聚類的目的是將有限個無標(biāo)注數(shù) 據(jù)劃分到有限個離散的組或類

2、中，發(fā)現(xiàn)數(shù)據(jù)隱藏的部結(jié)構(gòu)。Backer和Jain 1指出 數(shù)據(jù)的劃分是依賴于所選擇的相似性 度量的，通過主觀地選擇相似性度量 來達(dá)到有的的劃分。至今，人們并沒有 對聚類給出一個統(tǒng)一的定義。多數(shù)研 究者都是從部同質(zhì)性和外部可分性對 聚類簇進(jìn)行描述，即同類數(shù)據(jù)對象問 應(yīng)該彼此相似，不同類間的數(shù)據(jù)對象 應(yīng)該不相似3。在給出聚類的數(shù)學(xué)描述 之前，首先介紹與聚類有關(guān)的一辟術(shù) 語和數(shù)學(xué)表達(dá)方法。樣本：指要進(jìn)行聚類的數(shù)據(jù)集中的單個數(shù)據(jù)。樣本一般是一個多維向量，向量的每個分量可以是數(shù)值型或者名詞型的數(shù)據(jù)，一般稱為特征或者屬性。樣本集：或稱數(shù)據(jù)集，是由單個樣本所 組成的集合，即是需要聚類操作的數(shù) 據(jù)整體，通常表

3、示為一個矩陣。相異度矩陣：該矩陣中的每個元素表$樣本集中的每對樣本之間的相異程 度，一般是非負(fù)值。相似度矩陣：該矩陣中的每個元素表 ??？樣本集中的每對樣本之間的相似 程度，一般是非負(fù)值。類：或稱簇，指通過聚類而形成的一組 同一類中的樣本具有相似的特征。通 常用C或K表示類的個數(shù)。類原型：能夠代表某個類性質(zhì)的數(shù)據(jù)兀，可以是某類樣本中的一個樣本，或者是某類樣本的一個加權(quán)值,也可以是能描述一個類特征的向量。劃分矩陣U n*K：矩陣中的每個元素表示每個樣本屬于各個類的模糊隸屬度K0 < utk < 1 口 以法二 LM ,且止之】，在此K表?樣本標(biāo)號,k表類標(biāo)標(biāo)號。通常獲得的數(shù)據(jù)類型有兩種

4、：一是數(shù) 據(jù)矩陣，二是相異度矩陣（相似度矩 陣）。假定數(shù)據(jù)集中有 n個樣本：Xi ,i=1,2,.,n,每個樣本有 p個變量（特征屬性），則這n個樣本可表 示成n*p（n個樣本xp個變量）的數(shù)據(jù) 矩陣。Ml為2工1必區(qū)2【422X2p * * *,*入門1處12-*（2-1）其中每個對象對應(yīng)為一個p維向量：r修二卜” t * .戶ip）（2-2）1.2聚類的數(shù)據(jù)類型相異度矩陣存儲的是n個樣本兩兩之 問的相界度，表現(xiàn)形式足一個n*n維的 矩陣。I 0妣1)0J(3,1) dt 2) 0* *魯fl4-I-din.)虹 2) 0(2-3)在這里d(i,j)是樣本i和樣本j之間 相異性的量化表示，通

5、常是一個非負(fù) 的數(shù)值，當(dāng)樣本i和樣本j越相似， d(i,j)的值就越接近0;反之，兩個樣 本越不相似，的值就越大。d(i,j)= d(j, i),且 d(i,j)=0,因此得到形如(2-3)的矩陣。圖像數(shù)據(jù)的表示日常應(yīng)用中得到的圖像一般分為兩類：灰度圖像和彩色圖像?；叶葓D像的數(shù)值表示為一個二維矩陣I m*n圖像 一共包含m*n個像素。在此，m和n分 別代表圖像的高和寬，(ij)表示位于 第i行和第j列的像素，Iij表小其灰 度俏。彩色圖像的數(shù)值表示為一個三維矩陣I m*n*3,像素的個數(shù)仍為m>n,3表示三個顏色通道，每一層的二維矩 陣表示該圖像在某一個顏色通道的數(shù) 值。位于位置(i,j

6、)的像素對應(yīng)的 顏 色特征向量表示為 I(i,j,1),I(i,j,2),I(i,j,3)。在許多t#況下，色彩是描述一幅圖像 最簡單有效的特征，而且人眼對色彩 的分辨率大大高于對灰度圖像的分辨 率，因此彩色圖像所攜帶的信息遠(yuǎn)遠(yuǎn) 大于灰度圖像。一般的圖像處理技術(shù) 最先應(yīng)用于灰度圖像，然后發(fā)展到彩 色圖像，圖像分割也不列外。顏色特征 可以來自于不同的顏色空間，不同的 顏色空間以不同的方式對圖像顏色進(jìn) 行描述。一共有四種不同的顏色空間： RG射色空間、XYZ顏色空間、HIS顏 色空間、Lab顏色空間。RGB®色空間 是基本的顏色空間，RGB對應(yīng)于紅(R)、 I(G)、藍(lán)(B)三種基色，其

7、余所有顏色 空間都可由RGB顏色空間經(jīng)過線性或 非線性變換得出的。給定一幅待分割的圖像，我們可以直接獲得像素的位置信息，灰度值 （灰度圖像）或者RG的色特征值（彩色 圖像），這些特征也是圖像分割中最常 用的特征屬性。但是對于一些復(fù)雜圖 像,單純依賴這些底層特征不能得到 滿意的分割結(jié)果?；谶@些底層特征， 人們提取了更多有效的特征 ，其中常 用的有描述物體表面灰度變化的紋理 特征和根據(jù)特定對象的先驗信息加入 的形狀特征。最近，人們開始借助一辟 先進(jìn)的電子產(chǎn)品提取深度信息，通過 加入這辟高層特征來改善對特定類圖 像的分割結(jié)果。在提取特征之后，就可以得到每 個像素點的一個向量表小 ，也就可以 看成是

8、高維空間中的一個數(shù)據(jù)點。但 是，像素點又和傳統(tǒng)的數(shù)據(jù)不同，每個 像素點在閣像中的位置是固定的，每 個像素點的鄰域像素點都可以直接通 過位置信息獲得，這一特性也在圖像 數(shù)據(jù)的相似度計算上得以體現(xiàn)。2.3聚類算法近些年來，聚類分析一直是研究 熱點問題?；谙嗨贫染仃嚨木垲愃?法指的足給定相似度矩陣的情況下即 可進(jìn)行聚類處理的算法。只要給定相 似度計算模型，則基于相似度矩陣的 聚類算法也可以處理數(shù)據(jù)矩陣，即首 先根據(jù)數(shù)據(jù)矩陣計算出相似度矩陣，然后利用基于相似度矩陣的聚類算法 進(jìn)行聚類。2.3.1 基于數(shù)據(jù)矩陣的聚類算法基于數(shù)據(jù)矩陣的聚類算法只能處理數(shù)據(jù)矩陣對象，其中很多經(jīng)典的類原型聚類算法都可以劃分

9、到這一類聚一個簇可以由類原型表示，達(dá)到對原類算法中,如K均值型聚類算法，模糊C 均值型聚類算法（FCM）, EM®聚類算法 等。這辟算法之所以稱為類原型聚類 算法，是因為每個類可以由類原型來 代表，在對數(shù)據(jù)進(jìn)行劃分的同時也給 每個類找到具有代表作用的類原型。有的數(shù)據(jù)集的壓縮編碼，這也可以說(2-5)是聚類的另外一個功能。給定一數(shù)據(jù) 矩陣兇n*p表示n個p維樣本。K均值算法K均值算法將n個樣本劃分到K個 簇C = C1,C2,。9，使得簇樣本具 有較高相似度，簇間樣本具有較低相 似度。設(shè)V= VI, V2,Vk為K個類 對應(yīng)的類中心(類原型)，其中Vk是第 Ck個簇中樣本的平均值，每個

10、族可以 由對應(yīng)的類原型來表示。K均值算法通 過最小化類誤差平方和準(zhǔn)則函數(shù)來對 數(shù)據(jù)進(jìn)行劃分，其目標(biāo)函數(shù)定義如下：榮尤0 = 2 -躁儼七二1君EC*(2-4)在此Ck包含所有到第k個類中心 Vk距離最小的樣本點，可描述如下。C - I片 w 川k = arg min |x(- - 廣 網(wǎng)IN-用£為a為Vjk =IQI(2-6)K均值算法是一個貪心算法，通過 迭代地更新類中心和各個簇成員來得 到公式(2-4)的局部最優(yōu)解。K均值 聚類算法主要包括以下幾個步驟：1 .初始化：隨機(jī)選取個樣本作為 初始的類中心；2 .樣本指派：計算樣本到各個類 中心的歐氏距離，將樣本劃分到距離 其最近的類

11、；3 .更新：重新計算每個新簇的類 中心；4 .重復(fù)步驟2和3直到簇樣本不 再發(fā)生變化后停止。K均值算法的主要優(yōu)點有收斂速 度快，儲存空間小，時間復(fù)雜度低等。 一般的K均值型聚類算法的時間復(fù)雜 度為O (nKt),其中n是數(shù)據(jù)集中樣 本的個數(shù)，K是期望聚類的個數(shù)，t是迭代次數(shù)。要根據(jù)相似度模型計算出相似度矩模本C均值算法Dunn在1973年提出模糊C均值聚類思想，之后Bezdek把這一工作進(jìn)一 步推廣到一個模糊目標(biāo)函數(shù)聚類的優(yōu) 化算法，并證明了該算法的收斂性。模糊C均值聚類算法給出每個樣本屬 于各個類的程度，即隸屬度(menibershipvalue)。相比K均值聚類的硬化分,模糊劃分更豐富地

12、反映了樣本與各個類原型的相關(guān)度，從而可以更好的推測數(shù)據(jù)集的部結(jié)構(gòu)。2.3.2基于相似度矩陣的聚類算法基于相似度矩陣的聚類算法是以相似度(相異度)矩陣為基礎(chǔ)。如果數(shù)據(jù)是用數(shù)據(jù)矩陣的形式表現(xiàn)的，在使用基于相似度矩陣的聚類算法之前 陣。與基于數(shù)據(jù)矩陣的聚類算法相比， 這類算法使用起來更靈活，無論輸入 是數(shù)據(jù)矩陣還是相似度矩陣都能夠進(jìn) 行聚類操作，相反基于數(shù)據(jù)的聚類算 法則不能處理只給出相似度矩陣的聚 類問題。然而，一些應(yīng)用領(lǐng)域往往無法 給出明確的數(shù)據(jù)矩陣，而是給出一辟 數(shù)據(jù)點白關(guān)系(如相似度)，社團(tuán)分析 中常碰到這類情況。直接使用相似度 矩陣進(jìn)行聚類的典型聚類算法有基于圖的聚類算法、基于類原型的 K

13、中心算法(K-medoids)和AP聚類算法、層次聚類算法以及基于密度的聚類算法等?；趫D的聚類算法基于圖的聚類算法是一類基于無向圖的聚類算法。假定將侮個樣本看 作圖中白頂點V,根據(jù)樣本間的相似度 為頂點間的邊E賦于權(quán)重W這樣得到 一個基于樣本相似度的無向加權(quán)圖G=(V,E)。將樣本映射到圖之后，可以 使用圖論中很多成熟的理論來進(jìn)行聚類，一類非常流行的基于圖的聚類算 法是譜聚類算法，這類算法也是本文 的基礎(chǔ)算法，很多相關(guān)實驗也是基于 這類算法完成的。因此，下面會比較詳 細(xì)的介紹幾種常用的譜聚類算法。譜 聚類算法的思想源于譜圖劃分理論，其本質(zhì)是將聚類問題轉(zhuǎn)化為圖的 最優(yōu)化分問題。與傳統(tǒng)聚類算法假

14、設(shè) 一樣，基于圖論的最優(yōu)劃分準(zhǔn)則也是 使劃分的子圖部相似度最大，子圖之 問的相似度最小。不同的劃分準(zhǔn)則會得到不同的聚類結(jié)架。表 2.1給出了 一辟常見的劃分準(zhǔn)則。由于圖劃分問題的本質(zhì)，求圖劃 分準(zhǔn)則的最優(yōu)解是一個NP難問題。求 解圖劃分問題一個主要的工具是圖的 拉普拉斯矩陣法（Laplacian matrices）。這類矩陣的學(xué)習(xí)已經(jīng)形成 了一個完整的體系，稱為譜圖論早在 1973年,Donath 和 HoffmanfN 就提出 利用圖的鄰接矩陣的特征向量來求解圖劃分問題。同年,Fiedlerl發(fā)現(xiàn)了圖的2-way劃分與該圖的拉普拉斯矩陣對應(yīng)的第二小特 征信對應(yīng)的特征向量有密切關(guān)系，并提出使用

15、這一向量對圖進(jìn)行劃分。這 一特征向量代表了最佳圖劃分的一個 解（即勢函數(shù)），后來將這一特征向量 命名為Fiedlerl 向量?；谧V圖理論，原來的圖劃分問題 就可以轉(zhuǎn)換成求解相似度矩陣或 Laplacian矩陣的譜分解問題，因此將 這類方法統(tǒng)稱為譜聚類，可以認(rèn)為譜 聚類是對圖劃分準(zhǔn)則的逼近。AuthH.lef.McAodObrcwt Rhcbuii附Minim岫 cut幽A,用= £ %ShiiVlik1*廂Mi同EL跟隊用=墮力言自強(qiáng)曖Rark加加財尚二湍蜂四明版刖3Mm（兒盼瑞1工 *I F-fr', >'D譜聚類中常用的相似性度量為空間相似性計算模型中的高

16、斯型相似性計算方法。相似度矩陣通常用W或A表示，有時也稱為親和矩陣（AffinityMatrix), Wij = Wji=Sij 。在得到相似度矩陣后即可求解拉普拉斯矩陣，不同的文獻(xiàn)可能使用不同類型的拉普拉斯矩陣，不同的拉普拉斯矩陣即得 到不同的譜映射方法。在給出不同類型的拉普拉斯矩陣之前，先引入矩陣 D。D為對角矩陣，.二小啊即可 以看作是每個頂點的度，所以也稱為 度矩陣。圖的拉普拉斯矩陣分為兩類：非規(guī)拉普拉斯矩陣和規(guī)拉普拉斯矩陣。非規(guī)拉普拉斯矩陣定義為：L= D-W(2-7)規(guī)的拉普拉斯矩P$有兩種形式，分別為：= D'l/2LD-lf2 =/一 DWif2(2-8)Lrw = /

17、7附(2-9)在此將第一個矩陣標(biāo)記為 Lsym, 因為該矩陣為對稱矩陣；第二個矩陣 標(biāo)記為Lrw,因為該矩陣與隨機(jī)游走有密切關(guān)系。根據(jù)不同的準(zhǔn)則函數(shù)及譜映射方 法，文獻(xiàn)中已提出很多種不同的譜聚 類算法。眾多的譜聚類算法中應(yīng)用最 廣的要數(shù)Shi和Malik提出的Ncut譜 聚類算法_,Ng等。人提出的NJW算法。 Ncut算法最初是用于求解兩類問題， 可以迭代地對之前步驟得到的子圖進(jìn) 行劃分來得到期望的聚類個數(shù)，所以 也屬于迭代譜聚類算法中的一種。NJW 算法是針對多類問題提出，使用更多 的特征向量并且直接計算 k路分割對 數(shù)據(jù)進(jìn)行聚類。譜聚類算法的主要優(yōu)勢在于該類 算法對簇的形狀沒有很強(qiáng)的假設(shè)

18、，可 以處理更一般化的聚類問題。K均值聚 類算法建立在球形的樣本空間上，適 合發(fā)現(xiàn)千犬簇，對于含有任意形狀簇 的數(shù)據(jù)集往往得不到期望的聚類結(jié) 果。處理更多類型的數(shù)據(jù)集是近幾年 譜聚類流行起來的主要原因。但是也 正是由于譜聚類是直接基于相似度矩陣的聚類算法，不同的相似度矩陣得 到的聚類結(jié)果可能會有很大差界。K中心點方法K中心點方法也可以看作是K均值 算法的一個變形算法，之所以將其歸 類為基于相似度（相異度）矩陣的聚類 算法是因為K中心點算法選用族中位 置最中心的對象作為類代表點 （類中 心），而不是簇中對象的平均值（質(zhì) 心）。K中心點方法仍是基于最小化所 有對象到類中心之間的相異度之和的 原則來

19、執(zhí)行，在已知對象與對象間的 相異度時，該方法就能對對象進(jìn)行聚 類。K中心點方法采用中心點來代替質(zhì) 心，減少了對噪聲和孤立點數(shù)據(jù)的敏 感程度。K中心點聚類算法的基本策略是： 首先為每個族隨機(jī)選擇一個代表點；剩余的數(shù)據(jù)點根據(jù)其與代表點的距離 分配給最近的一個簇。然后反復(fù)用非 代表點來替換代表點，以改進(jìn)聚類的 質(zhì)量，降低聚類質(zhì)量的代價函數(shù)，即數(shù) 據(jù)點到其類代表點的平方誤差和。每 次代表點替換發(fā)生時，檢查代價函數(shù) 是否降低，如果降低則保留替換，否則 放棄該替換，重復(fù)上述過程直到代價 函數(shù)不再發(fā)生變化為止。給定聚類數(shù) K,典型的K中心點聚類算法的主要步 驟概括如下：1 .初始化：隨機(jī)選取足個樣本作 為初

20、始的中心點；2 .樣本指派：計算樣本到各個類 中心的距離，將樣本劃分到距離其最 近的中心點所代表的簇；3 .類中心替換：隨機(jī)地選擇一個 非類中心點，計算用選中的樣本代替 原來的類中心的代價函數(shù)，如果代價 函數(shù)降低，則替換原有的中心點形成 新的K個中心點集合；4 .重復(fù)步驟2和3直到類中心點 不評發(fā)生變化后停止。PAM （Partitioning AroundMedoids )是最早提出的K中心點算 法之一。雖然K中心算法比K均值算 法在處理噪聲點時表現(xiàn)的要健壯，但是K中心點算法的執(zhí)行代價比 K均值 方法高，其時間復(fù)雜度為如果數(shù)據(jù)集 規(guī)模和類的個數(shù)較大，PAM算法的效率 會很低為了用K中心點方法

21、處理大規(guī) 模數(shù)據(jù)集，Kaufman和Rousseeuw將抽 樣方法和PAMT法結(jié)合提出了 一個新 的尺中心點方法，稱為 CLARA(Clustering LARge Applications)算法 CLARAB法 + 再考 慮整個數(shù)據(jù)集，而是從整個數(shù)據(jù)集中 進(jìn)行抽樣，選取數(shù)據(jù)中的一小部分作 為數(shù)據(jù)的樣本，然后用PAMT法從這些 選中的樣本中選擇中心點。為了減少 抽樣樣本對最終聚類的影響，CLARA算 法采取多次抽樣，對每次抽樣樣本應(yīng) 用PAMT法，返回這幾次抽樣最好的聚類結(jié)果作為最終 結(jié)果。通過抽樣處理，CLARA算法一次 抽樣的時間復(fù)雜度為對),其中s是抽樣樣本的大小。CLARA?法的一大缺

22、點是 不能保證最佳的個類中心點被選中為 最終的類中心點，如果在抽樣的時候 這辟數(shù)據(jù)點沒有被抽中，那么CLARAT法將永遠(yuǎn)找不到最佳聚類。為了改進(jìn)CLARAJ法的聚類質(zhì)量，Ng和Han提出 了 CLARAN潴法(Clustering LargeApplications based upon RANdomizedSearch),該算法也采用了抽樣技術(shù)，但是在搜索的每個階段不訴使用一個固定的抽樣集合，而在搜索的每一步都會隨機(jī)的抽取樣本，其時間復(fù)雜度為5島)。CLARANS法的聚類質(zhì)量也依 賴于所用的抽樣方法。3實驗與分析針對相似度計算模型和數(shù)據(jù)特征兩方 面的工作，實驗分為兩部分：基于不同高斯型相似度的實驗結(jié)果和基于不同 特征的實驗結(jié)果。每部分都使用模擬(a)(b)數(shù)據(jù)及實際數(shù)據(jù)對相應(yīng)方法進(jìn)行測試 聚類算法選用NJW倍聚類算法。3.21基于不同高斯型相似度的聚類結(jié) 果下面給山基于六種高斯型相似性度量 的聚類結(jié)果。六種相似性度量分別為： 標(biāo)準(zhǔn)高斯核相似度(SC)自適應(yīng)高斯 核相似度I(STI)、自適應(yīng)高斯核相似 度n (STH)局部密度的自適應(yīng)相似度 (CNN)加權(quán)自適應(yīng)相似度I (WSTI)以 及加權(quán)自適應(yīng)相似度n (wsTn)。3.3模擬數(shù)據(jù)首先對模擬數(shù)據(jù)進(jìn)行實驗，部分?jǐn)?shù)據(jù) 集來自文獻(xiàn)。對于各種相似