圖像處理—聚類算法原理

1、聚類分析（Clusteranalysis）Clustering（聚類）和Classfcation（分類）Clustering中文翻譯作“聚類”，簡(jiǎn)單地說(shuō)就是把相似的東西分到一組，同Classification分類）不同，對(duì)于一個(gè)classifier,通常需要你告訴它“這個(gè)東西被分為某某類”這樣一些例子，理想情況下，一個(gè)classifier會(huì)從它得到的訓(xùn)練集中進(jìn)行“學(xué)習(xí)”，從而具備對(duì)未知數(shù)據(jù)進(jìn)行分類的能力，這種提供訓(xùn)練數(shù)據(jù)的過(guò)程通常叫做supervisedlearning（監(jiān)督學(xué)習(xí)），而在聚類的時(shí)候，我們并不關(guān)心某一類是什么，我們需要實(shí)現(xiàn)的目標(biāo)只是把相似的東西聚到一起，因此，一個(gè)聚類算法通常只需

2、要知道如何計(jì)算相似度就可以開(kāi)始工作了，因此clustering通常并不需要使用訓(xùn)練數(shù)據(jù)進(jìn)行學(xué)習(xí)，這在MachineLearning中被稱作unsupervisedlearning（無(wú)監(jiān)督學(xué)習(xí)）。舉一個(gè)簡(jiǎn)單的例子：現(xiàn)在有一群小學(xué)生，你要把他們分成幾組，讓組內(nèi)的成員之間盡量相似一些，而組之間則差別大一些。最后分出怎樣的結(jié)果，就取決于你對(duì)于“相似”的定義了咽此，在分類前，一定要知道，每一類的特征到底是什么），比如，你決定男生和男生是相似的，女生和女生也是相似的，而男生和女生之間則差別很大，這樣，你實(shí)際上是用一個(gè)可能取兩個(gè)值“男”和“女”的離散變量來(lái)代表了原來(lái)的一個(gè)小學(xué)生，我們通常把這樣的變量叫做特征

3、”。實(shí)際上，在這種情況下，所有的小學(xué)生都被映射到了兩個(gè)點(diǎn)的其中一個(gè)上，已經(jīng)很自然地形成了兩個(gè)組，不需要專門再做聚類了。另一種可能是使用“身高”這個(gè)特征。我在讀小學(xué)候，每周五在操場(chǎng)開(kāi)會(huì)訓(xùn)話的時(shí)候會(huì)按照大家住的地方的地域和距離遠(yuǎn)近來(lái)列隊(duì)，這樣結(jié)束之后就可以結(jié)隊(duì)回家了。除了讓事物映射到一個(gè)單獨(dú)的特征之外，一種常見(jiàn)的做法是同時(shí)提取N種特征，將它們放在一起組成一個(gè)N維向量（特征向量），從而得到一個(gè)從原始數(shù)據(jù)集合到N維向量空間的映射你總是需要顯式地或者隱式地完成這樣一個(gè)過(guò)程，因?yàn)樵S多機(jī)器學(xué)習(xí)的算法都需要工作在一個(gè)向量空間中。聚類分析聚類分析指將物理或抽象對(duì)象的集合分組成為由類似的對(duì)象組成的多個(gè)類的分析過(guò)程

4、。聚類分析的目標(biāo)就是在相似的基礎(chǔ)上收集數(shù)據(jù)來(lái)分類。在不同的應(yīng)用領(lǐng)域，很多聚類技術(shù)都得到了發(fā)展，這些技術(shù)方法被用作描述數(shù)據(jù)，衡量不同數(shù)據(jù)源間的相似性，以及把數(shù)據(jù)源分類到不同的簇中。Clusteranalysisorclusteringisthetaskofassigningasetofobjectsintogroups（calledclusters）sothattheobjectsinthesameclusteraremoresimilar（insomesenseoranother）toeachotherthantothoseinotherclusters.1Clusteranalysisits

5、elfisnotonespecificalgorithm,butthegeneraltasktobesolved.Itcanbeachievedbyvariousalgorithmsthatdiffersignificantlyintheirnotionofwhatconstitutesaclusterandhowtoefficientlyfindthem.Popularnotionsofclustersincludegroupswithlowdistancesamongtheclustermembers,denseareasofthedataspace,intervalsorparticul

6、arstatisticaldistributions.Clusteringcanthereforebeformulatedasamulti-objectiveoptimizationproblem.Theappropriateclusteringalgorithmandparametersettings（includingvaluessuchasthedistancefunctiontouse,adensitythresholdorthenumberofexpectedclusters）dependontheindividualdatasetandintendeduseoftheresults

7、.Clusteranalysisassuchisnotanautomatictask,butaniterativeprocessofknowledgediscoveryorinteractivemulti-objectiveoptimizationthatinvolvestrialandfailure.Itwilloftenbenecessarytomodifypreprocessingandparametersuntiltheresultachievesthedesiredproperties.K-means（K-均值聚類法）K-均值算法表示以空間中k個(gè)點(diǎn)為中心進(jìn)行聚類，對(duì)最靠近他們的對(duì)象歸

8、類。該算法的最大優(yōu)勢(shì)在于簡(jiǎn)潔和快速。劣勢(shì)在于對(duì)于一些結(jié)果并不能夠滿足需要，因?yàn)榻Y(jié)果往往需要隨機(jī)點(diǎn)的選擇非常巧合。算法歸納為（J.MacQueen,1967）:（1）初始化：選擇（或人為指定）某些記錄作為凝聚點(diǎn)循環(huán)：2.1按就近原則將其余記錄向凝聚點(diǎn)凝集2.2計(jì)算出各個(gè)初始分類的中心位置（均值）2.3用計(jì)算出的中心位置重新進(jìn)行聚類如此反復(fù)循環(huán)，直到凝聚點(diǎn)位置收斂為止方法特點(diǎn)通常要求已知類別數(shù)節(jié)省運(yùn)算時(shí)間樣本量大于100時(shí)有必要考慮只能使用連續(xù)性變量k-means對(duì)于需要進(jìn)行聚類的數(shù)據(jù)有一個(gè)基本假設(shè)：對(duì)于每一個(gè)cluster，我們可以選出一個(gè)中心點(diǎn)(center)，使得該cluster中的所有的點(diǎn)

9、到該中心點(diǎn)的距離小于到其他cluster的中心的距離。雖然實(shí)際情況中得到的數(shù)據(jù)并不能保證總是滿足這樣的約束，但這通常已經(jīng)是我們所能達(dá)到的最好的結(jié)果，而那些誤差通常是固有存在的或者問(wèn)題本身的不可分性造成的。例如下圖所示的兩個(gè)高斯分布，從兩個(gè)分布中隨機(jī)地抽取一些數(shù)據(jù)點(diǎn)出來(lái)，混雜到一起，現(xiàn)在要讓你將這些混雜在一起的數(shù)據(jù)點(diǎn)按照它們被生成的那個(gè)分布分開(kāi)來(lái)：0.沁由于這兩個(gè)分布本身有很大一部分重疊在一起了，例如，對(duì)于數(shù)據(jù)點(diǎn)2.5來(lái)說(shuō)，它由兩個(gè)分布產(chǎn)生的概率都是相等的，你所做的只能是一個(gè)猜測(cè)；稍微好一點(diǎn)的情況是2，通常我們會(huì)將它歸類為左邊的那個(gè)分布，因?yàn)楦怕蚀笠恍?，然而此時(shí)它由右邊的分布生成的概率仍然是比較

10、大的，我們?nèi)匀挥胁恍〉膸茁蕰?huì)猜錯(cuò)。而整個(gè)陰影部分是我們所能達(dá)到的最小的猜錯(cuò)的概率，這來(lái)自于問(wèn)題本身的不可分性，無(wú)法避免。因此，我們將:-means所依賴的這個(gè)假設(shè)看作是合理的?；谶@樣一個(gè)假設(shè)，我們?cè)賮?lái)導(dǎo)出k-means所要優(yōu)化的目標(biāo)函數(shù)：設(shè)我們一共有N個(gè)數(shù)據(jù)點(diǎn)需要分為K個(gè)cluster，k-means要做的就是最小化YKJ=工工-陽(yáng)F,-i=Lk=I這個(gè)函數(shù)，其中，在數(shù)據(jù)點(diǎn)n被歸類到clusterk的時(shí)候?yàn)?，否則為0。直接尋找和:來(lái)最小化、并不容易，不過(guò)我們可以采取迭代的辦法：先固定，選擇最優(yōu)的，很容易看出，只要將數(shù)據(jù)點(diǎn)歸類到離他最近的那個(gè)中心就能保證最小。下一步則固定，再求最優(yōu)的:將對(duì):

11、求導(dǎo)并令導(dǎo)數(shù)等于零，很容易得到、最小的時(shí)候：應(yīng)該滿足：=mean(xn),其中xn為屬于clusterk的點(diǎn)的坐標(biāo)亦即丿從的值應(yīng)當(dāng)是所有clusterk中的數(shù)據(jù)點(diǎn)的平均值。由于每一次迭代都是取到的最小值，因此只會(huì)不斷地減小(或者不變)，而不會(huì)增加，這保證了k-means最終會(huì)到達(dá)一個(gè)極小值。雖然k-means并不能保證總是能得到全局最優(yōu)解，但是對(duì)于這樣的問(wèn)題，像k-means這種復(fù)雜度的算法，這樣的結(jié)果已經(jīng)是很不錯(cuò)的了。下面我們來(lái)總結(jié)一下k-means算法的具體步驟：選定K個(gè)中心丿的初值。這個(gè)過(guò)程通常是針對(duì)具體的問(wèn)題有一些啟發(fā)式的選取方法，或者大多數(shù)情況下采用隨機(jī)選取的辦法。因?yàn)榍懊嬲f(shuō)過(guò)k-means并不能保證全局最優(yōu)，而是否能收斂到全局最優(yōu)解其實(shí)和初值的選取有很大的關(guān)系，所以有時(shí)候我們會(huì)多次選取初值跑k-means，并取其中最好的一