來源：http://blog.csdn.net/u011067360/article/details/24383051
一、相異度計算
在正式讨論聚類前，我們要先弄清楚一個問題：如何定量計算兩個可比較元素間的相異度。用通俗的話說，相異度就是兩個東西差别有多大，例如人類與章魚的相異度明顯大于人類與黑猩猩的相異度，這是能我們直覺感受到的。但是，計算機沒有這種直覺感受能力，我們必須對相異度在數學上進行定量定義。
設
，其中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
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算法對于孤立點是敏感的。為了解決這個問題，不采用簇中的平均值作為參照點，可以選用簇中位置最中心的對象，即中心點作為參照點。這樣劃分方法仍然是基于最小化所有對象與其參照點之間的相異度之和的原則來執行的。