數據挖掘十大算法--K-均值聚類算法

一、相異度計算 

在正式討論聚類前，我們要先弄清楚一個問題：如何定量計算兩個可比較元素間的相異度。用通俗的話說，相異度就是兩個東西差別有多大，例如人類與章魚的相異度明顯大于人類與黑猩猩的相異度，這是能我們直觀感受到的。但是，計算機沒有這種直觀感受能力，我們必須對相異度在數學上進行定量定義。
      設 ，其中X，Y是兩個元素項，各自具有n個可度量特征屬性，那么X和Y的相異度定義為：

 ，其中R為實數域。也就是說相異度是兩個元素對實數域的一個映射，所映射的實數定量表示兩個元素的相異度。
      下面介紹不同類型變量相異度計算方法。

1、標量

（1）標量也就是無方向意義的數字，也叫標度變量。現在先考慮元素的所有特征屬性都是標量的情況。例如，計算X={2,1,102}和Y={1,3,2}的相異度。一種很自然的想法是用兩者的歐幾里得距離來作為相異度，歐幾里得距離的定義如下：

其意義就是兩個元素在歐氏空間中的集合距離，因為其直觀易懂且可解釋性強，被廣泛用于標識兩個標量元素的相異度。將上面兩個示例數據代入公式，可得兩者的歐氏距離為：

（2）除歐氏距離外，常用作度量標量相異度的還有曼哈頓距離和閔可夫斯基距離，兩者定義如下：

      曼哈頓距離 ：

（3） 閔可夫斯基距離：

（4）皮爾遜系數(Pearson Correlation Coefficient)

兩個變量之間的皮爾遜相關系數定義為兩個變量之間的協方差和標準差的商.

(其中，E為數學期望或均值，D為方差，D開根號為標準差，E{ [X-ux] [Y-uy]}稱為隨機變量X與Y的協方差，記為Cov(X,Y)，即Cov(X,Y) = E{ [X-ux] [Y-ux}，而兩個變量之間的協方差和標準差的商則稱為隨機變量X與Y的相關系數，記為)

歐氏距離和曼哈頓距離可以看做是閔可夫斯基距離在p=2和p=1下的特例。另外這三種距離都可以加權，這個很容易理解。

     下面要說一下標量的規格化問題。上面這樣計算相異度的方式有一點問題，就是取值范圍大的屬性對距離的影響高于取值范圍小的屬性。例如上述例子中第三個屬性的取值跨度遠大于前兩個，這樣不利于真實反映真實的相異度，為了解決這個問題，一般要對屬性值進行規格化。

所謂規格化就是將各個屬性值按比例映射到相同的取值區間，這樣是為了平衡各個屬性對距離的影響。通常將各個屬性均映射到[0,1]區間，映射公式為：

其中max(ai)和min(ai)表示所有元素項中第i個屬性的最大值和最小值。例如，將示例中的元素規格化到[0,1]區間后，就變成了X’={1,0,1}，Y’={0,1,0}，重新計算歐氏距離約為1.732。

2、二元變量

所謂二元變量是只能取0和1兩種值變量，有點類似布爾值，通常用來標識是或不是這種二值屬性。對于二元變量，上一節提到的距離不能很好標識其相異度，我們需要一種更適合的標識。一種常用的方法是用元素相同序位同值屬性的比例來標識其相異度。

     設有X={1,0,0,0,1,0,1,1}，Y={0,0,0,1,1,1,1,1}，可以看到，兩個元素第2、3、5、7和8個屬性取值相同，而第1、4和6個取值不同，那么相異度可以標識為3/8=0.375。一般的，對于二元變量，相異度可用“取值不同的同位屬性數/單個元素的屬性位數”標識。

     上面所說的相異度應該叫做對稱二元相異度。現實中還有一種情況，就是我們只關心兩者都取1的情況，而認為兩者都取0的屬性并不意味著兩者更相似。例如在根據病情對病人聚類時，如果兩個人都患有肺癌，我們認為兩個人增強了相似度，但如果兩個人都沒患肺癌，并不覺得這加強了兩人的相似性，在這種情況下，改用“取值不同的同位屬性數/(單個元素的屬性位數-同取0的位數)”來標識相異度，這叫做非對稱二元相異度。如果用1減去非對稱二元相異度，則得到非對稱二元相似度，也叫Jaccard系數，是一個非常重要的概念。

3、分類變量

分類變量是二元變量的推廣，類似于程序中的枚舉變量，但各個值沒有數字或序數意義，如顏色、民族等等，對于分類變量，用“取值不同的同位屬性數/單個元素的全部屬性數”來標識其相異度。

4、序數變量

序數變量是具有序數意義的分類變量，通常可以按照一定順序意義排列，如冠軍、亞軍和季軍。對于序數變量，一般為每個值分配一個數，叫做這個值的秩，然后以秩代替原值當做標量屬性計算相異度。

5、向量

對于向量，由于它不僅有大小而且有方向，所以閔可夫斯基距離不是度量其相異度的好辦法，一種流行的做法是用兩個向量的余弦度量，其度量公式為：

     

     其中||X||表示X的歐幾里得范數。要注意，余弦度量度量的不是兩者的相異度，而是相似度！

二、聚類問題

 所謂聚類問題，就是給定一個元素集合D，其中每個元素具有n個可觀察屬性，使用某種算法將D劃分成k個子集，要求每個子集內部的元素之間相異度盡可能低，而不同子集的元素相異度盡可能高。其中每個子集叫做一個簇。
      與分類不同，分類是示例式學習，要求分類前明確各個類別，并斷言每個元素映射到一個類別，而聚類是觀察式學習，在聚類前可以不知道類別甚至不給定類別數量，是無監督學習的一種。目前聚類廣泛應用于統計學、生物學、數據庫技術和市場營銷等領域，相應的算法也非常的多。本文僅介紹一種最簡單的聚類算法——k均值（k-means）算法。

1、算法簡介

k-means算法，也被稱為k-平均或k-均值，是一種得到最廣泛使用的聚類算法。 它是將各個聚類子集內的所有數據樣本的均值作為該聚類的代表點，

算法的主要思想是通過迭代過程把數據集劃分為不同的類別，使得評價聚類性能的準則函數達到最優，從而使生成的每個聚類內緊湊，類間獨立。這一算法不適合處理離散型屬性，但是對于連續型具有較好的聚類效果。

2、算法描述
1、為中心向量c1, c2, …, ck初始化k個種子
2、分組:
（1）將樣本分配給距離其最近的中心向量
（2）由這些樣本構造不相交（ non-overlapping ）的聚類
3、確定中心:
用各個聚類的中心向量作為新的中心
4、重復分組和確定中心的步驟，直至算法收斂。

3、算法  k-means算法
輸入：簇的數目k和包含n個對象的數據庫。
輸出：k個簇，使平方誤差準則最小。
算法步驟： 
1.為每個聚類確定一個初始聚類中心，這樣就有K 個初始聚類中心。 
 2.將樣本集中的樣本按照最小距離原則分配到最鄰近聚類  
 3.使用每個聚類中的樣本均值作為新的聚類中心。
 4.重復步驟2.3直到聚類中心不再變化。
 5.結束，得到K個聚類

PS

1、將樣本分配給距離它們最近的中心向量，并使目標函數值減小

2、更新簇平均值

3、計算準則函數E

計算準則函數

E

4、劃分聚類方法對數據集進行聚類時包括如下
  三個要點：
  （1）選定某種距離作為數據樣本間的相似性度量              
     上面講到，k-means聚類算法不適合處理離散型屬性，對連續型屬性比較適合。因此在計算數據樣本之間的距離時，可以根據實際需要選擇歐式距離、曼哈頓距離或者明考斯距離中的一種來作為算法的相似性度量，其中最常用的是歐式距離。下面我再給大家具體介紹一下歐式距離。 平均值

假設給定的數據集，X中的樣本用d個描述屬性A1,A2…Ad來表示，并且d個描述屬性都是連續型屬性。數據樣本xi=(xi1,xi2,…xid),xj=(xj1,xj2,…xjd)其中，xi1,xi2,…xid和xj1,xj2,…xjd分別是樣本xi和xj對應d個描述屬性A1,A2,…Ad的具體取值。樣本xi和xj之間的相似度通常用它們之間的距離d(xi,xj)來表示，距離越小，樣本xi和xj越相似，差異度越小；距離越大，樣本xi和xj越不相似，差異度越大。

      歐式距離公式如下：

（2）選擇評價聚類性能的準則函數
      k-means聚類算法使用誤差平方和準則函數來 評價聚類性能。給定數據集X，其中只包含描述屬性，不包含類別屬性。假設X包含k個聚類子集X1,X2,…XK；各個聚類子集中的樣本數量分別為n1，n2,…,nk;各個聚類子集的均值代表點（也稱聚類中心）分別為m1，m2,…,mk。則誤差平方和準則函數公式為：

（3）相似度的計算根據一個簇中對象的平均值來進行。
1）將所有對象隨機分配到k個非空的簇中。
2）計算每個簇的平均值，并用該平均值代表相應的簇。
3）根據每個對象與各個簇中心的距離，分配給最近的簇。
4）然后轉2），重新計算每個簇的平均值。這個過程不斷重復直到滿足某個準則函數才停止

三、聚類例子

數據對象集合S見上表，作為一個聚類分析的二維樣本，要求的簇的數量k=2。
(1)選擇 ，為初始的簇中心，即 

   ，                  。
(2)對剩余的每個對象，根據其與各個簇中心的距離，將它賦給最近的簇

對O3 ：

     

     

顯然 O3，故將C2分配給

對于O4:

因為：所以將O4分配給C2

對于O5:

因為：所以講O5分配給C1

更新，得到新簇 和

計算平方誤差準則，單個方差為

總體平均方差是：

（3）計算新的簇的中心。 

重復（2）和（3），得到O1分配給C1；O2分配給C2，O3分配給C2 ，O4分配給C2，O5分配給C1。更新，得到新簇
 和。 中心為  ， 。

單個方差分別為

總體平均誤差是： 


由上可以看出，第一次迭代后，總體平均誤差值52.25~25.65，顯著減小。由于在兩次迭代中，簇中心不變，所以停止迭代過程，算法停止。

PS 

1、k-means算法的性能分析

主要優點：
是解決聚類問題的一種經典算法，簡單、快速。
對處理大數據集，該算法是相對可伸縮和高效率的。因為它的復雜度是0 (n k t ) , 其中, n 是所有對象的數目, k 是簇的數目, t 是迭代的次數。通常k < <n 且t < <n 。
當結果簇是密集的，而簇與簇之間區別明顯時, 它的效果較好。

主要缺點
在簇的平均值被定義的情況下才能使用，這對于處理符號屬性的數據不適用。
必須事先給出k（要生成的簇的數目），而且對初值敏感，對于不同的初始值，可能會導致不同結果。

    它對于“躁聲”和孤立點數據是敏感的，少量的該類數據能夠對平均值產生極大的影響。

K-Means算法對于不同的初始值，可能會導致不同結果。解決方法：
1.多設置一些不同的初值，對比最后的運算結果）一直到結果趨于穩定結束，比較耗時和浪費資源
2.很多時候，事先并不知道給定的數據集應該分成多少個類別才最合適。這也是 K-means 算法的一個不足。有的算法是通過類的自動合并和分裂，得到較為合理的類型數目 K.

2、k-means算法的改進方法——k-prototype算法
k-Prototype算法：可以對離散與數值屬性兩種混合的數據進行聚類，在k-prototype中定義了一個對數值與離散屬性都計算的相異性度量標準。

K-Prototype算法是結合K-Means與K-modes算法，針對混合屬性的，解決2個核心問題如下：
1.度量具有混合屬性的方法是，數值屬性采用K-means方法得到P1，分類屬性采用K-modes方法P2，那么D=P1+a*P2，a是權重，如果覺得分類屬性重要，則增加a，否則減少a，a=0時即只有數值屬性
2.更新一個簇的中心的方法，方法是結合K-Means與K-modes的更新方法。

3、k-means算法的改進方法——k-中心點算法
k-中心點算法：k -means算法對于孤立點是敏感的。為了解決這個問題，不采用簇中的平均值作為參照點，可以選用簇中位置最中心的對象，即中心點作為參照點。這樣劃分方法仍然是基于最小化所有對象與其參照點之間的相異度之和的原則來執行的。 

來自： http://blog.csdn.net//u011067360/article/details/24383051