k-means聚類與高斯混合模型

1、 K-means算法，也被稱為K-均值，是一種得到最廣泛使 用的聚類算法。它是將各個(gè)聚類內(nèi)的所有數(shù)據(jù)樣本的均值作為該聚類的代表點(diǎn)，算法的主要思想是通過迭代過程把數(shù)據(jù)劃分為不同的類別，使得評(píng)價(jià)聚類性能的準(zhǔn)則函數(shù)能達(dá)到最優(yōu)，從而使生成的每個(gè)聚類內(nèi)緊湊，類間獨(dú)立。K-MEANS算法流程算法流程u從樣本選從樣本選K K個(gè)對(duì)象作為初始聚類的中心個(gè)對(duì)象作為初始聚類的中心u根據(jù)樣本與聚類中心的相異度判斷每個(gè)樣根據(jù)樣本與聚類中心的相異度判斷每個(gè)樣本屬于哪個(gè)簇本屬于哪個(gè)簇u每個(gè)簇中重新計(jì)算聚類中心每個(gè)簇中重新計(jì)算聚類中心1. 1.重復(fù)重復(fù)2 2、3 3步驟直到聚類不再變化步驟直到聚類不再變化 標(biāo)量：標(biāo)量： 閔可

2、夫斯基距離：閔可夫斯基距離： 曼哈頓距離曼哈頓距離: : 歐幾里得距離歐幾里得距離: : 對(duì)于每個(gè)樣本，計(jì)算出它與每個(gè)樣本中心的距離，距離最小的樣本中心則視為相異度最低，則該樣本屬于該樣本中心對(duì)應(yīng)的簇，從而可以計(jì)算出每個(gè)樣本都屬于哪個(gè)簇。根據(jù)樣本與聚類中心的根據(jù)樣本與聚類中心的相異度相異度判斷每個(gè)判斷每個(gè) 樣本屬于樣本屬于哪個(gè)簇哪個(gè)簇 二元變量二元變量： 取值不同的同位屬性數(shù)取值不同的同位屬性數(shù)/單個(gè)元素的屬性位數(shù)單個(gè)元素的屬性位數(shù)二元變量是只能取0和1兩種值變量，例如X=1,0,0,0,1,0,1,1，Y=0,0,0,1,1,1,1,1，可以看到，兩個(gè)元素第2、3、5、7和8個(gè)屬性取值相同，

3、而第1、4和6個(gè)取值不同，那么相異度可以標(biāo)識(shí)為3/8=0.375向量向量： （相似度） 在每個(gè)簇中重新計(jì)算聚類中心：在每個(gè)簇中重新計(jì)算聚類中心： 將同一個(gè)簇的樣本的每個(gè)屬性求平均值，從而計(jì)算出每個(gè)簇的聚類中心。此處可以生成新的K個(gè)聚類中心，用于下次計(jì)算樣本屬于的類別。例如：簇中有點(diǎn)(1,2,3) (4,5,6)。聚類中心就為（2.5,3.5,4.5） 每個(gè)簇中重新計(jì)算聚類中心每個(gè)簇中重新計(jì)算聚類中心要點(diǎn)：要點(diǎn)：1、初始聚類中心的選取、初始聚類中心的選取這個(gè)過程大多數(shù)情況下采用隨機(jī)選取的辦法。因?yàn)閗-means 并不能保證全局最優(yōu)，是否能收斂到全局最優(yōu)解其實(shí)和初值的選取有很大的關(guān)系，所以有時(shí)候我

4、們會(huì)多次選取初值跑 k-means ，并取其中最好的一次結(jié)果K-means-test演示采用基于距離和的孤立點(diǎn)定義來進(jìn)行孤立點(diǎn)的預(yù)先篩選不可預(yù)知孤立點(diǎn)就進(jìn)行最遠(yuǎn)距離法首先整理移除孤立點(diǎn)后的數(shù)據(jù)集U,記錄數(shù)據(jù)個(gè)數(shù)y,令m=1。比較數(shù)據(jù)集中所有數(shù)據(jù)對(duì)象兩兩之間的距離。找出距離最近的2個(gè)數(shù)據(jù)對(duì)象形成集合Am;比較Am中每一個(gè)數(shù)據(jù)對(duì)象與數(shù)據(jù)對(duì)象集合U中每一個(gè)對(duì)象的距離,在U中找出與Am 中最近的數(shù)據(jù)對(duì)象,優(yōu)先吸收到Am 中,直到Am 中的數(shù)據(jù)對(duì)象個(gè)數(shù)到達(dá)一定數(shù)值,然后令m=m+1。再從U中找到對(duì)象兩兩間距離最近的2個(gè)數(shù)據(jù)對(duì)象構(gòu)成Am,重復(fù)上面的過程,直到形成k個(gè)對(duì)象集合。這些集合內(nèi)部的數(shù)據(jù)是相似的,而

5、集合間是相異的。 可以看出,這種聚類方法同時(shí)滿足以下2個(gè)條件:每個(gè)組至少包含一個(gè)數(shù)據(jù)對(duì)象; 每個(gè)數(shù)據(jù)對(duì)象必須屬于且僅屬于一個(gè)組。即數(shù)據(jù)對(duì)象Xi Ai ,且U=A1 A2 Ak A0 ,且Ai Aj =。最后對(duì)k個(gè)對(duì)象集合分別進(jìn)行算術(shù)平均,形成k個(gè)初始聚類中心。KNN算法等等摘自wiki百科 迭代終止條件迭代終止條件 1、 重復(fù)迭代直到聚類中心不再變化或者變化很小 準(zhǔn)則函數(shù)： 每一個(gè)樣本點(diǎn)到其聚類中心點(diǎn)的平方和，K-MEANS要將J函數(shù)調(diào)整到最小。當(dāng)J函數(shù)前后相差小于一個(gè)閾值的時(shí)候即可以終止迭代。若單一定義讓聚類中心不再變化則停止迭代，可能會(huì)存在問題。因?yàn)槟骋稽c(diǎn)不一定百分之百屬于某個(gè)聚類。演示K

6、-MEANS-TEST22、達(dá)到迭代最大步數(shù)Opencv的函數(shù)cvKMeans2中變量CvTermCriteria可設(shè)置兩個(gè)迭代終止條件 高斯混合模型高斯混合模型GMM（Gaussian Mixture Model） 可以看出K-MEANS是簡單的，因?yàn)樗诩僭O(shè)即一個(gè)點(diǎn)僅以1或者0的概率屬于某一聚類，這兩者中間的取值沒有考慮，將一個(gè)可以無窮取值的模型進(jìn)化到了兩個(gè)值，顯然變得不那么復(fù)雜了，那么如果想要考慮到中間的值呢？即一個(gè)點(diǎn)僅以某一個(gè)概率屬于某一類呢？ 既然考慮到概率，那么與K-MEANS的數(shù)學(xué)基礎(chǔ)便是完全不同的，即并沒有直接考慮歐氏距離的問題。此處就可以用高斯混合模型和E-M算法進(jìn)行解決。

7、 高斯混合模型高斯混合模型GMM（Gaussian Mixture Model）高斯分布（正態(tài)分布）：高斯分布（正態(tài)分布）： x是d維列向量，u是期望，是方差 高斯混合模型：高斯混合模型：高斯混合模型由K個(gè)單高斯生成，每個(gè)高斯模型為一個(gè)Component。首先隨機(jī)地在這個(gè) Component 之中選一個(gè)，每個(gè) Component 被選中的概率為 選中了Component后，再考慮從這個(gè)Component中選取某一個(gè)點(diǎn)。 GMM與聚類的關(guān)系與聚類的關(guān)系K是事先確定好的值，每個(gè)component就是一個(gè)聚類中心，即在只有樣本點(diǎn)，不知道樣本分類（含有隱含變量）的情況下，計(jì)算出模型參數(shù)（，u和）我們就

8、需要確定 、u 和 這些參數(shù)。 找到這樣一組參數(shù)，它所確定的概率分布生成這些給定的數(shù)據(jù)點(diǎn)的概率最大它所確定的概率分布生成這些給定的數(shù)據(jù)點(diǎn)的概率最大假設(shè)我們有一個(gè)訓(xùn)練集x(1),x(m)，數(shù)據(jù)服從 Mixture Gaussian Distribution ，即把數(shù)據(jù)看作是從許多個(gè) Gaussian Distribution 中生成出來的。具體就是建立聯(lián)合分布： z(i) 滿足多項(xiàng)分布 , z(i) 即為上式中的 ，即每個(gè) Component 被選中的概率 ?j即p(z(i)=j)。 ，k為開始就確定好的k個(gè)Component1、首先選取一個(gè)Component，概率 2、在這個(gè)Component

9、中的x(i)屬于高斯分布 注意：此處的z(i)都是未知的 現(xiàn)在，我們要確定，使生成x(i)這些數(shù)據(jù)點(diǎn)的概率最大，這里用到了最大似然估計(jì)法。似然函數(shù)： (可看做未知數(shù)，的集合，N即 文中的m)取對(duì)數(shù)此處則轉(zhuǎn)化為模型：求，使的 l (，)的值最大。無法直接求導(dǎo)取0，然后求最大值。所以此處用到E-M算法。 E步：步：估計(jì)數(shù)據(jù)由每個(gè) Component 生成的概率（并不是每個(gè) Component 被選中的概率）：對(duì)于每個(gè)x(i)數(shù)據(jù)來說，它由第j個(gè) Component 生成的概率為(貝葉斯公式)：由于式子里的 和 也是需要我們估計(jì)的值，我們采用迭代法，在計(jì)算 的時(shí)候我們假定 和 均已知，我們將取上一次迭代所得的值（或者初始值）。問題：初始值怎么定的？ M步：步：估計(jì)每個(gè) Component 的