1、精選優(yōu)質(zhì)文檔-傾情為你奉上有關(guān)k-均值聚類算法的理解1.K-均值聚類算法的歷史：聚類分析作為一種非監(jiān)督學(xué)習(xí)方法，是機器學(xué)習(xí)領(lǐng)域中的一個重要的研究方向，同時，聚類技術(shù)也是數(shù)據(jù)挖掘中進行數(shù)據(jù)處理的重要分析工具和方法。1967 年MacQueen 首次提出了K 均值聚類算法（K-means算法）。到目前為止用于科學(xué)和工業(yè)應(yīng)用的諸多聚類算法中一種極有影響的技術(shù)。它是聚類方法中一個基本的劃分方法，常常采用誤差平方和準(zhǔn)則函數(shù)作為聚類準(zhǔn)則函數(shù)迄今為止，很多聚類任務(wù)都選擇該經(jīng)典算法，K-means算法雖然有能對大型數(shù)據(jù)集進行高效分類的優(yōu)點，但K-means算法必須事先確定類的數(shù)目k，而實際應(yīng)用過程中，k 值是

2、很難確定的，并且初始聚類中心選擇得不恰當(dāng)會使算法迭代次數(shù)增加，并在獲得一個局部最優(yōu)值時終止，因此在實際應(yīng)用中有一定的局限性。半監(jiān)督學(xué)習(xí)是近年來機器學(xué)習(xí)領(lǐng)域的一個研究熱點，已經(jīng)出現(xiàn)了很多半監(jiān)督學(xué)習(xí)算法，在很多實際應(yīng)用中，獲取大量的無標(biāo)號樣本非常容易，而獲取有標(biāo)簽的樣本通常需要出較大的代價。因而，相對大量的無標(biāo)簽樣本，有標(biāo)簽的樣本通常會很少。傳統(tǒng)的監(jiān)督學(xué)習(xí)只能利用少量的有標(biāo)簽樣本學(xué)習(xí)，而無監(jiān)督學(xué)習(xí)只利用無標(biāo)簽樣本學(xué)習(xí)。半監(jiān)督學(xué)習(xí)的優(yōu)越性則體現(xiàn)在能同時利用有標(biāo)簽樣本和無標(biāo)簽樣本學(xué)習(xí)。針對這種情況，引入半監(jiān)督學(xué)習(xí)的思想，對部分已知分類樣本運用圖論知識迭代確定K-means 算法的K值和初始聚類中心，然

3、后在全體樣本集上進行K-均值聚類算法。2. K-算法在遙感多光譜分類中的應(yīng)用基于K-均值聚類的多光譜分類算法近年來對高光譜與多光譜進行分類去混的研究方法很多，K-均值聚類算法與光譜相似度計算算法都屬于成熟的分類算法.這類算法的聚類原則是以數(shù)據(jù)的均值作為對象集的聚類中心。均值體現(xiàn)的是數(shù)據(jù)集的整體特征，而掩蓋了數(shù)據(jù)本身的特性。無論是對高光譜還是對多光譜進行分類的方法很多，K-均值算法屬于聚類方法中一種成熟的方法。使用ENVI將多光譜圖像合成一幅偽彩色圖像見圖1，圖中可以看出它由標(biāo)有數(shù)字1 的背景與標(biāo)有數(shù)字2 和3的兩種不同的氣泡及標(biāo)有數(shù)字4的兩個氣泡重疊處構(gòu)成。圖1 原始圖像用ENVI進行K-me

4、ans分類，分類結(jié)果如圖2，背景被分成標(biāo)有數(shù)字1的紅色與標(biāo)有數(shù)字2的綠色兩類；一種氣泡被分為兩類，一類歸為標(biāo)有數(shù)字2的綠色的背景類，一類為標(biāo)有數(shù)字4的藍色的氣泡類；另外一種氣泡被分為標(biāo)有數(shù)字3的黃色與標(biāo)有數(shù)字5的淺藍色兩類。通過ENVI用K-均值（K-means）進行分類，K-means算法對于兩種氣泡的分類效果都很好。圖2 K-均值分類后的圖像3. K-算法的步驟：第一步：選K個初始聚類中心，其中括號內(nèi)的序號為尋找聚類中心的迭代運算的次序號。聚類中心的向量值可任意設(shè)定，例如可選開始的K個模式樣本的向量值作為初始聚類中心。第二步：逐個將需分類的模式樣本x按最小距離準(zhǔn)則分配給K個聚類中心中的某一

5、個。對所有的ij，j=1,2,K ，如果則 ，X其中k為迭代運算的次序號，第一次迭代k=1，表示第j個聚類，其聚類中心為。第三步：計算各個聚類中心的新的向量值，j=1,2,K,求各聚類域中所包含樣本的均值向量： 其中為第j個聚類域中所包含的樣本個數(shù)。以均值向量作為新的聚類中心，可使如下聚類準(zhǔn)則函數(shù)J最小：在這一步中要分別計算K個聚類中的樣本均值向量，所以稱之為K-均值算法。第四步：若 ，j=1,2,K，則返回第二步，將模式樣本逐個重新分類，重復(fù)迭代運算；若 ，j=1,2,K，則算法收斂，計算結(jié)束。4.K-均值聚類算法的優(yōu)缺點：優(yōu)點：算法的特點是：第一，能根據(jù)較少的已知聚類樣本的類別對樹進行剪枝

6、確定部分樣本的分類；第二，為克服少量樣本聚類的不準(zhǔn)確性，該算法本身具有優(yōu)化迭代功能，在已經(jīng)求得的聚類上再次進行迭代修正剪枝確定部分樣本的聚類，優(yōu)化了初始監(jiān)督學(xué)習(xí)樣本分類不合理的地方；第三，由于只是針對部分小樣本可以降低總的聚類時間復(fù)雜度。缺點： 在 K-means 算法中 K 是事先給定的，這個 K 值的選定是非常難以估計的。很多時候，事先并不知道給定的數(shù)據(jù)集應(yīng)該分成多少個類別才最合適。這也是 K-means 算法的一個不足。有的算法是通過類的自動合并和分裂，得到較為合理的類型數(shù)目 K，例如 ISODATA 算法。關(guān)于 K-means 算法中聚類數(shù)目K 值的確定在文獻中，是根據(jù)方差分析理論，應(yīng)

7、用混合 F 統(tǒng)計量來確定最佳分類數(shù)，并應(yīng)用了模糊劃分熵來驗證最佳分類數(shù)的正確性。在文獻中，使用了一種結(jié)合全協(xié)方差矩陣的 RPCL 算法，并逐步刪除那些只包含少量訓(xùn)練數(shù)據(jù)的類。而文獻中使用的是一種稱為次勝者受罰的競爭學(xué)習(xí)規(guī)則，來自動決定類的適當(dāng)數(shù)目。它的思想是：對每個輸入而言，不僅競爭獲勝單元的權(quán)值被修正以適應(yīng)輸入值，而且對次勝單元采用懲罰的方法使之遠離輸入值。 在 K-means 算法中，首先需要根據(jù)初始聚類中心來確定一個初始劃分，然后對初始劃分進行優(yōu)化。這個初始聚類中心的選擇對聚類結(jié)果有較大的影響，一旦初始值選擇的不好，可能無法得到有效的聚類結(jié)果，這也成為 K-means算法的一個主要問題。

8、對于該問題的解決，許多算法采用遺傳算法（GA），例如文獻 中采用遺傳算法（GA）進行初始化，以內(nèi)部聚類準(zhǔn)則作為評價指標(biāo)。 從 K-means 算法可以看出，該算法需要不斷地進行樣本分類調(diào)整，不斷地計算調(diào)整后的新的聚類中心，因此當(dāng)數(shù)據(jù)量非常大時，算法的時間開銷是非常大的。所以需要對算法的時間復(fù)雜度進行分析、改進，提高算法應(yīng)用范圍。在文獻中從該算法的時間復(fù)雜度進行分析考慮，通過一定的相似性準(zhǔn)則來去掉聚類中心的侯選集。而在文獻中，使用的 K-means 算法是對樣本數(shù)據(jù)進行聚類，無論是初始點的選擇還是一次迭代完成時對數(shù)據(jù)的調(diào)整，都是建立在隨機選取的樣本數(shù)據(jù)的基礎(chǔ)之上，這樣可以提高算法的收斂速度。5.K-均值算法的總結(jié)： K-means是最常用的聚類算法之一，能有效地處理規(guī)模較大和高維的數(shù)據(jù)集合，能對大型數(shù)據(jù)集進行高效分類，把數(shù)據(jù)分成幾組，按照定義的測量標(biāo)準(zhǔn)，同組內(nèi)數(shù)據(jù)與其他組數(shù)據(jù)相比具有較強的相似性，這就叫聚簇。K-means算法的效率比較高；缺點是只能處理數(shù)值型數(shù)據(jù)，不能處理分類數(shù)據(jù)，對例外數(shù)據(jù)非常敏感，不能