數(shù)字圖像聚類技術研究

數(shù)字圖像聚類技術研究多媒體是一種極其重要的信息資源，現(xiàn)代技術已能運用各種手段大量地采集和產(chǎn)生各種類型的多媒體信息數(shù)據(jù)，而多媒體信息中占有舉足輕重作用的一種就是圖像信息。近年來隨著需求的增加、工藝技術的進步，以各種方式獲取的圖像信息的數(shù)量得到了飛速的增長，進入新世紀后，有人估計世界每年產(chǎn)生的新圖像已達800億幅，信息膨脹已給人類帶來過多的信息量以致超出了人的接受能力，有鑒于此，如何快速、準確、高效的從浩如煙海的圖像信息源（比如網(wǎng)絡）中獲取有用的信息就變得極為重要，近年來國際上廣泛開展了基于內(nèi)容的圖像檢索研究，而其中圖像聚類與檢索技術已取得相當進展，在各個領域已得到了廣泛的應用。所謂圖像聚類就是在給出的圖像集合中，根據(jù)圖像的內(nèi)容，在無先驗知識的條件下，將圖像分成有意義的簇。對于圖像聚類，最引人注目的特征屬性是顏色、紋理和形狀等。目前有很多有效的聚類技術，如層次聚類算法、基于分割的算法、劃分算法、層次方法、基于密度的算法、基于模型的方法以及基于網(wǎng)格的方法。1引言在圖像檢索的過程中我們同樣面臨著分類的任務，具體地講就是圖像的聚類。所謂圖像聚類就是將未知類別的一組圖像分成若干類的過程，也稱無監(jiān)督學習或無教師學習。聚類分析的思路比較直觀，根據(jù)各個待分類圖像特征的相似程度來進行分類，將在特征空間中聚集在一起的樣本點劃分為一類。選擇合適的聚類算法對圖像庫中的圖像進行聚類，是我們的核心任務之一。因此根據(jù)實際科研情況,選擇一個好的聚類算法對后續(xù)的研究工作是非常關鍵的。聚類的定義:聚類是將數(shù)據(jù)劃分成群組的過程。通過確定數(shù)據(jù)之間在預先制定的屬性上的相似性來完成聚類任務,這樣最相似的數(shù)據(jù)就聚集成簇。聚類與分類的不同點:聚類的類別取決于數(shù)據(jù)本身;而分類的類別是由數(shù)據(jù)分析人員預先定義好的。聚類算法的分類:一般可分為基于層次的,基于劃分的,基于密度的,基于網(wǎng)格的和基于模型的五種.2聚類的定義

聚類分析僅根據(jù)在數(shù)據(jù)中發(fā)現(xiàn)的描述對象及其關系的信息，將數(shù)據(jù)對象分組。其目標是，組內(nèi)的對象相互之間是相關的，而不同組的對象是不相關的，組內(nèi)相似度越大，組間差別度越大，聚內(nèi)效果就越好。聚類分析技術作為強大的輔助工具在科學研究、社會服務、市場營銷等多個領域發(fā)揮了巨大的作用。因此聚類分析技術研究也成為一個熱點課題。3聚類方法

目前，在聚類的算法主要可分為以下幾種：劃分算法、層次方法、基于密度的算法、基于模型的方法以及基于網(wǎng)格的方法。下面主要介紹劃分方法和層次方法：圖1CURE中的做法。（b）綜合層次凝聚和迭代的重定位方法。首先用自底向上的層次算法，然后用迭代的重定位來改進結(jié)果。分裂的層次聚類是將像這樣的自頂向下的策略與凝聚的層次聚類有些不一樣，它首先將所有對象放在一個簇中，然后慢慢地細分為越來越小的簇，直到每個對象自行形成一簇，或者直達滿足其他的一個終結(jié)條件，例如滿足了某個期望的簇數(shù)目，又或者兩個最近的簇之間的距離達到了某一個閾值。3.1.2基于距離度量的方法在凝聚和分裂的層次聚類之間，我們又依據(jù)計算簇間的距離的不同，分為下面的幾類方法：單連鎖（singlelinkage）,又稱最近鄰（nearestneighbor）方法。指兩個不一樣的簇之間任意兩點之間的最近距離。這里的距離是表示兩點之間的相異度，所以距離越近，兩個簇相似度越大。這種方法最善于處理非橢圓結(jié)構(gòu)。卻對于噪聲和孤立點特別的敏感，取出距離很遠的兩個類之中出現(xiàn)一個孤立點時，這個點就很有可能把兩類合并在一起。距離公式如公式1所示。（1）（1）全連鎖（comlpetelinkage），又稱最遠鄰（furthestneighbor）方法。指兩個不一樣的簇中任意的兩點之間的最遠的距離。它面對噪聲和孤立點很不敏感，趨向于尋求某一些緊湊的分類，但是，有可能使比較大的簇破裂。距離公式如公式2所示。（2）(2)組平均方法(grouPaveragelinkage)，定義距離為數(shù)據(jù)兩兩距離的平均值。這個方法傾向于合并差異小的兩個類，產(chǎn)生的聚類具有相對的魯棒性。距離公式如公式3所示。（3）（3）平均值方法(centroidlinkage),現(xiàn)計算各個類的平均值，然后定義平均值之差為兩類的距離。距離公式如公式3.4所示。（4）（4）其中,是兩個類，|為對象p和之間的距離，，分別為,的對象個數(shù)，，分別為類,的平均值。3.2基于劃分的聚類方法給定一個數(shù)據(jù)庫包含個數(shù)據(jù)對象以及數(shù)目K的即將生成的簇,一個劃分類的算法將對象分為K個劃分，其中，這里的每個劃分分別代表一個簇，并且K<=。其中的K需要人為指定。它一般從一個初始劃分開始，然后通過重復的控制策略，使某個準則函數(shù)最優(yōu)化。因此，它可以被看作是一個優(yōu)化問題，而優(yōu)化問題往往是NP-難問題。基于劃分的聚類方法的優(yōu)缺點跟層次的聚類方法的優(yōu)缺點剛剛好反，層次聚類算法的優(yōu)點恰恰是劃分聚類方法的缺點，反之亦然。根據(jù)它們之間的優(yōu)缺點，人們往往會更趨向于使用劃分的聚類方法，所以，本文著重于講解基于劃分的聚類方法?；趧澐值木垲愃惴ㄓ性S多，下面介紹幾中常見的基于劃分的聚類算法。3.2.1K-meansk-means算法是最為經(jīng)典的基于劃分的聚類方法，是十大經(jīng)典數(shù)據(jù)挖掘算法之一。k-means算法的基本思想是：以空間中k個點為中心進行聚類，對最靠近他們的對象歸類。通過迭代的方法，逐次更新各聚類中心的值，直至得到最好的聚類結(jié)果。該算法的迭代的終止條件是直至中心點收斂。因此，K-means算法需要優(yōu)化的目標函數(shù)是：（5）其中E為數(shù)據(jù)庫中所有對象的均方差之和，p為代表對象的空間中的一個點，mi為聚類Ci的均值(p和mi均是多維的)。公式(1)所示的聚類標準，旨在使所獲得的k個聚類具有以下特點：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。而K-medoids算法跟k-means算法的不同之處在于K-medoids用接近聚類中心的一個對象來表示每個簇而K-means用簇中對象的平均值來表示每個簇。輸入:簇的數(shù)目k和包含n個對象的數(shù)據(jù)集。輸出:k個簇。方法：（1）對于數(shù)據(jù)對象集,任意選取k個對象作為初始的簇中心;（2）根據(jù)簇中對象的平均值,將每個對象重新賦給最相似的簇;（3）更新簇的平均值,即計算每個簇中對象的平均值;（4）重復(2)(3);（5）直到不再發(fā)生變化。（a）(b)(c)3.2.2模糊C均值算法C-均值聚類算法：1．條件及約定設待分類的模式特征矢量集為，類的數(shù)目是事先確定的。2．基本思路設方法取定類和選取個初始聚類中心，按最小距離原則將各模式分配到類中的某一類，之后不斷地計算類心和調(diào)整個模式的類別，最終使各模式到其判屬類別中心的距離平方之和最小。3．算法步驟（1）任選個模式特征矢量作為初始聚類中心：，令。（2）將待分類的模式特征矢量集中的模式逐個按最小距離原則分劃給類中的某一類，即如果，，存在一個。則判定。式中表示和的中心的距離，上角標表示迭代次數(shù)。于是產(chǎn)生新的聚類。（3）計算重新分類后的各類中心式中為類中所含模式的個數(shù)。因為這一步采取平均的方法計算調(diào)整后各類的中心，且定為類，故稱為-均值法。（4）如果，則結(jié)束；否則，，轉(zhuǎn)至（2）。應用C-均值聚類算法實現(xiàn)圖像聚類：這里假設圖像分割成個區(qū)域，其圖像大小為的灰度圖像，任意位置處的灰度值為。因此，灰度圖像可采用集合方式描述為。假設灰度圖像中最小灰度值為，最大灰度值為，其中任意灰度級出現(xiàn)的總個數(shù)記為且滿足，這里表示給定灰度圖像中所有灰度總個數(shù)。采用C-均值聚類圖像的算法過程如下：步驟1：從0至255中任意選取個不同大小的值作為圖像聚成類的中心值，即采用0至255的整數(shù)初始化的值，令。步驟2：將圖像中所有不同位置像素的灰度值逐個按最小距離原則分劃給類中的某一類，即如果，，存在一個，則判定。式中表示和的中心的距離，上角標表示迭代次數(shù)。于是產(chǎn)生新的聚類。步驟3：計算重新分類后的各類中心式中為類中所含模式的個數(shù)。因為這一步采取平均的方法計算調(diào)整后各類的中心，且定為類，故稱為-均值法。如果，則結(jié)束；否則，，轉(zhuǎn)至步驟2.(a)(b)（c）3.2.3KHM算法譜聚類算法首先根據(jù)給定的樣本數(shù)據(jù)集定義一個描述成對數(shù)據(jù)點相似度的親合矩陣,并且計算矩陣的特征值和特征向量

，然后選擇合適的特征向量聚類不同的數(shù)據(jù)點。譜聚類算法最初用于計算機視覺

、VLSI設計等領域，最近才開始用于機器學習中，并迅速成為國際上機器學習領域的研究熱點。譜聚類算法建立在譜圖理論基礎上，其本質(zhì)是將聚類問題轉(zhuǎn)化為圖的最優(yōu)劃分問題，是一種點對聚類算法，與傳統(tǒng)的聚類算法相比，它具有能在任意形狀的樣本空間上聚類且收斂于全局最優(yōu)解的優(yōu)點。KHM算法的權(quán)重是個變量，它把距離中心點遠的數(shù)據(jù)點賦以高的權(quán)重，這樣可以讓質(zhì)心能夠很好的覆蓋整個數(shù)據(jù)集。KHM算法對初始值不敏感，適合處理大數(shù)據(jù)集，然而KHM算法容易陷入局部最優(yōu)及簇個數(shù)需要預先指定的問題。綜合上來說它勝過K-means、FCM和EM算法。3.3基于密度的算法絕大多數(shù)劃分方法基于對象之間的距離進行聚類，這樣的方法只能發(fā)現(xiàn)球狀的類。因此，出現(xiàn)了基于密度的聚類方法，其主要思想是：只要鄰近區(qū)域的密度(對象或數(shù)據(jù)點的數(shù)目)超過某個閾值，就繼續(xù)聚類，這樣的方法可以過濾“噪聲”數(shù)據(jù)，發(fā)現(xiàn)任意形狀的類。從而克服基于距離的方法只能發(fā)現(xiàn)類圓形聚類的缺點。代表性算法有：DBSCAN算法、OPTICS算法、DENCLUE算法等。DBSCAN(densitybasedspatialclusteringofapplicationswithnoise)算法可以有效地發(fā)現(xiàn)具有任意形狀的類，并正確地處理噪聲數(shù)據(jù)。除此之外，該算法還具有實現(xiàn)簡單、聚類效果較好等優(yōu)點。該算法對于一個類中的每個對象，在其給定半徑的領域中包含的對象不能少于某一給定的最小數(shù)目，即DBSCAN算法將聚類定義為基于密度可達性最大的密度相連對象的集合。另外不進行任何的預處理而直接對整個數(shù)據(jù)集進行聚類操作。DBSCAN對用戶定義的參數(shù)很敏感，細微的不同都可能導致差別很大的結(jié)果，而參數(shù)的選擇無規(guī)律可循，只能靠經(jīng)驗確定。OPTICS算法是一種基于類排序方法。該算法并不明確產(chǎn)生一個聚類，而是為自動交互的聚類分析計算出一個增強聚類順序。這個順序代表了數(shù)據(jù)的基于密度的聚類結(jié)構(gòu)。核心距離：對象p的核心距離是指是p成為核心對象的最小E’。如果p不是核心對象，那么p的核心距離沒有任何意義。可達距離：對象q到對象p的可達距離是指p的核心距離和p與q之間歐幾里得距離之間的較大值。如果p不是核心對象，p和q之間的可達距離沒有意義。例如：假設鄰域半徑E=2,minPts=3，存在點：A(2,3),B(2,4),C(1,4),D(1,3),E(2,2),F(3,2)點A為核心對象，在A的E領域中有點{A,B,C,D,E,F}，其中A的核心距離為E’=1，因為在點A的E’鄰域中有點{A,B,D,E}>3;DENCLUE算法是一個基于一組密度分布函數(shù)的聚類算法。該算法主要基于下面的想法：(1)每個數(shù)據(jù)點的影響可以用一個數(shù)學函數(shù)來形式化地模擬，它描述了一個數(shù)據(jù)點在領域內(nèi)的影響，被稱為影響函數(shù)；(2)數(shù)據(jù)空間的整體密度可以被模型化為所有數(shù)據(jù)點的影響函數(shù)的總和；(3)聚類可以通過確定密度吸引點來得到，這里的密度吸引點是全局密度函數(shù)的局部最大。3.4基于網(wǎng)格法主要思想是將空間區(qū)域劃分若干個具有層次結(jié)構(gòu)的矩形單元，不同層次的單元對應于不同的分辨率網(wǎng)格，把數(shù)據(jù)集中的所有數(shù)據(jù)都映射到不同的單元網(wǎng)格中，算法所有的處理都是以單個單元網(wǎng)格為對象，其處理速度要遠比以元組為處理對象的效率要高的多。代表性算法有：STING算法、CLIQUE算法、WAVE-CLUSTER算法等。STING(statisticalinformationgrid)算法首先將空間區(qū)域劃分為若干矩形單元，這些單元形成一個層次結(jié)構(gòu)，每個高層單元被劃分為多個低一層的單元。單元中預先計算并存儲屬性的統(tǒng)計信息，高層單元的統(tǒng)計信息可以通過底層單元計算獲得。這種算法的優(yōu)點是效率很高，而且層次結(jié)構(gòu)有利于并行處理和增量更新；其缺點是聚類的邊界全部是垂直或是水平的，與實際情況可能有比較大的差別，影響聚類的質(zhì)量。CLIQUE(clusteringinquest)算法綜合了基于密度和基于網(wǎng)格的聚類方法。其主要思想是將多維數(shù)據(jù)空間劃分為多個矩形單元，通過計算每一個單元中數(shù)據(jù)點中全部數(shù)據(jù)點的比例的方法確定聚類。其優(yōu)點是能夠有效處理高維度的數(shù)據(jù)集，缺點是聚類的精度有可能會降低。WaveCluster(clusteringusingwavelettransformation)算法是一種采用小波變換的聚類方法。其首先使用多維數(shù)據(jù)網(wǎng)格結(jié)構(gòu)匯總區(qū)域空間數(shù)據(jù)，用多維向量空間表示多維空間中的數(shù)據(jù)對象，然后使用小波變換方法對特征空間進行處理，發(fā)現(xiàn)特征空間中的稠密區(qū)域。最終通過多次小波變換，獲得多分辨率的聚類。3.5基于模型法給每一個聚類假定一個模型，然后去尋找能夠很好地滿足這個模型的數(shù)據(jù)集。常用的模型主要有兩種：一種是統(tǒng)計學的方法，代表性算法是COBWEB算法；另一種是神經(jīng)網(wǎng)絡的方法，代表性的算法是競爭學習算法。COBWEB算法是一種增量概念聚類算法。這種算法不同于傳統(tǒng)的聚類方法，它的聚類過程分為兩步：首先進行聚類，然后給出特征描述。因此，分類質(zhì)量不再是單個對象的函數(shù)，而且也加入了對聚類結(jié)果的特征性描述。競爭學習算法屬于神經(jīng)網(wǎng)絡聚類。它采用若干個單元的層次結(jié)構(gòu)，以一種“勝者全取”的方式對系統(tǒng)當前所處理的對象進行競爭。COBWEB是一種流行的簡單增量概念聚類算法。它的輸入對象用分類屬性-值對來描述。它以一個分類樹的形式創(chuàng)建層次聚類。分類樹的每個節(jié)點對應一個概念，包含該概念的一個概率描述，概述被分在該節(jié)點下的對象。在分類樹某個層次上的兄弟節(jié)點形成了一個劃分。為了用分類樹對一個對象進行分類，采用了一個部分匹配函數(shù)沿著“最佳”匹配節(jié)點的路徑在樹中向下移動。尋找可以分類該對象的最好節(jié)點。這個判定基于將對象臨時置于每個節(jié)點，并計算結(jié)果劃分的分類效用。產(chǎn)生最高分類效用的位置應當是對象節(jié)點一個好的選擇。但如果對象不屬于樹中現(xiàn)有的任何概念，則為該對象創(chuàng)建一個新類。CORWEB的優(yōu)點在于：他不需要用戶輸入?yún)?shù)來確定分類的個數(shù)，它可以自動修正劃分中類的數(shù)目。缺點是：首先，它基于這樣一個假設：在每個屬性上的概率分布是彼此獨立的。由于屬性間經(jīng)常是相關的，這個假設并不總是成立。此外，聚類的概率分布表示使得更新和存儲類相當昂貴。因為時間和空間復雜度不只依賴于屬性的數(shù)目，而且取決于每個屬性的值的數(shù)目，所以當屬性有大量的取值時情況尤其嚴重。而且，分類樹對于偏斜的輸入數(shù)據(jù)不是高度平衡的，它可能導致時間和空間復雜性的劇烈變化。3.6各類算法比較基于上述的分析，下面對常用聚類算法的性能從可伸縮性、發(fā)現(xiàn)聚類的形狀、對“噪聲”的敏感性、對數(shù)據(jù)輸入順序的敏感性、高維性和是否是硬聚類六個方面進行比較，如表1所示。算法可伸縮性發(fā)現(xiàn)聚類的形狀對“噪聲”的敏感性對數(shù)據(jù)輸入順序的敏感性高維性K-means不好凸形敏感敏感不好FCM好任意形狀敏感不敏感好EM不好任意形狀敏感不敏感不好KHM好任意形狀敏感不敏感不好SNN好任意形狀敏感不敏感好CLARANS好球形及凸形不敏感很敏感一般CURE差任意形狀不敏感敏感好BIRCH差球形或凸形一般不太敏感好STING好任意形狀不敏感不敏感好DBSCAN較好任意形狀不敏感敏感一般COBWEB較好任意形狀一般敏感好FCM好任意形狀敏感不敏感好k-means好球形或凸形敏感不敏感好表1：各類算法比較4、總結(jié)聚類分析是圖像處理中一種非常有用的技術，它可作為特征和分類算法的預處理步驟，這些算法再在生成的簇上進行處理，也可將聚類結(jié)果用于進一步關聯(lián)分析還可以作為一個獨立的工具來獲得數(shù)據(jù)分布的情況，觀察每個簇的特點，集中對特定的某些簇做進一步分析其應用范圍涉及商務，生物，地理，web文檔分類，仿真等諸多領域。聚類能更好地應用到現(xiàn)實生活中是很必要的。這些新算法正努力把靜態(tài)的聚類推向動態(tài)的、適應性強的、帶約束條件的及與生活聯(lián)系緊密的聚類。同時，對目前可有效處理二維和小的數(shù)據(jù)集的聚類方法進行強化和修改，以使其能處理大的和高維的數(shù)據(jù)，這也是努力的一個方向。參考文獻[1]G.H.Omran,P.Engelbrechtandsalman.IntelligentDataAnalysis:Anoverviewofclusteringmethods.2007,583-605.[2]宋余慶，謝從華，朱玉全等．基于近似密度函數(shù)的醫(yī)學圖像聚類分析研究[J]．計算機研究與發(fā)展，2006，43(11)：1947·1952．[3]宋余慶，王春紅，陳健美等．基于高斯混合密度模型的醫(yī)學圖像聚類方法[J]．江蘇大學學報(自然科學版)，2009，30(3)：293·296．[4]段明秀.層次聚類算法的研究及應用[D]:[碩士學位論文].長沙：中南大學,2009.[5]G.HamerlyandC.Elkan,CIKM-2002:AlternativestotheK-meansAlgorithmthatFindBetterClusterings.2002,600-607.[6]B.zhang,GeneralizedK-HarmonicMeans-BoostinginUnsupervisedLearning.TechnicalReportHPL-2000-137.Hewlett-PackardLabs,2000.[7]J.MacQueen,SomeMethodsforClassi?cationandAnalysisofMultivariateObservations.InProceedingsFifthBerkeleySymposiumonMathematics,StatisticsandProbability,vol.1,1967,281–297.[8]喬小妮，張明新，史變霞.一種基于密度的K-means算法.電腦開發(fā)與應用.2008.21(10).9-11[9]傅德勝，周辰.基于密度的改進K均值算法及實現(xiàn).計算機應用.