圖像處理—聚類算法原理

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

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

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

4、。聚類分析的目標就是在相似的基礎上收集數據來分類。在不同的應用領域，很多聚類技術都得到了發(fā)展，這些技術方法被用作描述數據，衡量不同數據源間的相似性，以及把數據源分類到不同的簇中。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個點為中心進行聚類，對最靠近他們的對象歸

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

9、到該中心點的距離小于到其他cluster的中心的距離。雖然實際情況中得到的數據并不能保證總是滿足這樣的約束，但這通常已經是我們所能達到的最好的結果，而那些誤差通常是固有存在的或者問題本身的不可分性造成的。例如下圖所示的兩個高斯分布，從兩個分布中隨機地抽取一些數據點出來，混雜到一起，現在要讓你將這些混雜在一起的數據點按照它們被生成的那個分布分開來：0.沁由于這兩個分布本身有很大一部分重疊在一起了，例如，對于數據點2.5來說，它由兩個分布產生的概率都是相等的，你所做的只能是一個猜測；稍微好一點的情況是2，通常我們會將它歸類為左邊的那個分布，因為概率大一些，然而此時它由右邊的分布生成的概率仍然是比較

10、大的，我們仍然有不小的幾率會猜錯。而整個陰影部分是我們所能達到的最小的猜錯的概率，這來自于問題本身的不可分性，無法避免。因此，我們將:-means所依賴的這個假設看作是合理的。基于這樣一個假設，我們再來導出k-means所要優(yōu)化的目標函數：設我們一共有N個數據點需要分為K個cluster，k-means要做的就是最小化YKJ=工工-陽F,-i=Lk=I這個函數，其中，在數據點n被歸類到clusterk的時候為1，否則為0。直接尋找和:來最小化、并不容易，不過我們可以采取迭代的辦法：先固定，選擇最優(yōu)的，很容易看出，只要將數據點歸類到離他最近的那個中心就能保證最小。下一步則固定，再求最優(yōu)的:將對:

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