2.2 聚類

2.2.1 簡介

聚類（Cluster Analysis）是將數據集中的所有樣本根據相似度的大小進行劃分，形成兩個或多個類（簇）的過程。作為一種無監督機器學習方法，聚類經常用于數據挖掘和模式識別。簇是數據集中相似的樣本集合。聚類沒有訓練過程，是一種無監督學習。它同分類的根本區別在于：分類需要有標號的樣本進行訓練。常用的聚類算法可分為基于劃分方法的、基于層次方法的、基于密度方法的、基于網格方法的和基于模型方法的聚類。目前常用的聚類算法是基于層次的聚類和基于劃分的聚類?；趯哟蔚木垲愔饕校浩胶獾鳒p聚類法、基于密度的聚類方法和使用代表點的聚類方法等；基于劃分的聚類方法主要有：K均值聚類算法、K中心點聚類算法和隨機搜索聚類算法等。

2.2.2 基本原理

聚類是按照相似性大小，將無標號的數據集劃分為若干類或簇的過程。聚類的結果是類內樣本的相似度高，類間樣本的相似度低。相似性的度量通常采用樣本間的距離來表示，距離函數值的大小反映相似的程度。相似度越大，兩個樣本間的距離函數的值越??；相似度越小，兩個樣本間的距離函數值越大。

常用的距離計算方法如下。

1.歐氏距離

歐氏距離（Euclidean Distance）是最常見的距離表示法。

假設x={x1,x2,",xn}，y={y1,y2,",yn}，則它們之間的距離為：

即兩項間的差是每個變量值差的平方和再取平方根，目的是計算其間的整體距離，即不相似性。歐氏距離的優點是計算公式比較簡單，缺點是不能將樣本的不同屬性（即各指標或各變量）之間的差別等同看待，在某些特定的應用背景中不能滿足要求。一般的聚類大都采用歐氏距離。

2.曼哈頓距離

曼哈頓距離（Manhattan Distance）也稱為城市街區距離（CityBlock Distance），是在歐氏空間的固定直角坐標系上兩點所形成的線段對軸產生的投影的距離總和。

二維平面兩點a(x1,x2)與b(y1,y2)間的曼哈頓距離定義為：

兩個n維向量a(x11,x12,",x1n)與b(x21,x22,",x2n)間的曼哈頓距離：

需要注意的是，曼哈頓距離依賴坐標系統的轉度，而非系統在坐標軸上的平移或映射。

3.明氏距離

明氏距離（Minkowski Distance）也被稱作閔氏距離，可以理解為N維空間的距離，是歐氏距離的擴展，兩個n維變量a(x11,x12,",x1n)與b(x21,x22,",x2n)間的明氏距離定義為：

其中p是一個變參數。

根據變參數的不同，明氏距離可以表示以下的距離。

（1）當p=1時，明氏距離即為曼哈頓距離。

（2）當p=2時，明氏距離即為歐氏距離。

（3）當p→∞時，明氏距離即為切比雪夫距離。

4.余弦距離

余弦距離（Cosine Similarity）也稱為余弦相似度，是用向量空間中兩個向量夾角的余弦值作為衡量兩個個體間差異的大小的度量。

對于二維空間，其定義為：

假設向量a、b的坐標分別為(x1,y1)、(x2,y2)，則：

設向量A=(A1,A2,",An)，B=(B1,B2,",Bn)，推廣到多維：

余弦距離通過測量兩個向量內積空間夾角的余弦值來度量它們的相似性。余弦值的范圍在[-1，1]之間，值越趨近于1，代表兩個向量的方向越接近，越相似；越趨近于-1，它們的方向越相反，越不相似；越趨近于0，表示兩個向量趨近于正交。余弦距離可以用在任何維度的向量比較中，在高維正空間中采用較多。

2.2.3 常用聚類算法

下面介紹幾種常用的聚類算法。

1．K近鄰算法（KNN）

K近鄰算法是一種常見的有監督的聚類算法，也是非參數分類的重要方法之一。K近鄰算法的優點在于算法原理比較簡單，容易理解和實現，不需要先驗知識等；缺點在于計算量較大，在處理孤立點或噪聲方面精度較低。

（1）K近鄰算法基本思想

K近鄰算法的基本思想是針對測試集中的一個樣本點，在已經學習并且完成分類的樣本空間中找到K個距離最近的樣本點，距離的計算通常采用歐氏距離或明氏距離。如果找到的K個樣本點大多屬于某一個類別，則可以判定該樣本也屬于這個類別。

K近鄰算法的實現主要有以下3個要素。

① 數據特征的量化。如果數據特征中存在非數值類型，則需要運用一定的手段量化成數值。若樣本中存在顏色這一特征屬性，可將顏色轉化成灰度值來計算距離；或為了保證參數取值較大時的影響力覆蓋參數取值較小時的影響力，通常需要對樣本的特征數值進行歸一化處理。

② 樣本間距離計算公式的選擇。常見的距離計算公式有歐氏距離、曼哈頓距離、明氏距離、余弦距離等。不同情況下對公式的選擇不同，例如：樣本變量為連續型時，通常采用歐氏距離；樣本變量為非連續型時，通常采用明氏距離。

③ K值的選擇。K為自定義的常數，K值的選擇對聚類的結果有很大的影響。通常采用交叉驗證法確定K的取值，且K的取值一般小于訓練樣本數的平方根。

（2）K近鄰算法過程

K近鄰算法過程具體描述如下。

① 構建訓練集和測試集，使訓練集按照已有的標準分成離散型數值類或連續型數值類。

② 根據樣本集為離散型或連續型選擇適當的距離計算公式，計算測試集中的數據與各個訓練集數據之間的距離，并排序。

③ 利用交叉驗證法確定K的取值，并選擇距離最小的K個點。

④ 確定K個點所在類別的出現頻率，選擇出現頻率最高的類別作為測試集的預測類。

2．K均值聚類（K-means）

K均值聚類是劃分方法中經典的聚類算法之一。其優點是算法簡單，聚類效果較好，效率較高，對于處理大數據集有較好的可伸縮性；缺點是 K 值需要事先指定，受孤立點或噪聲的影響較大，而且由于算法本身是迭代的，最終得到的結果有可能是局部最優而不是全局最優。

（1）K均值算法基本思想

K均值算法的基本思想是將n個樣本點劃分或聚類成K個簇，使簇內具有較高的相似度，而簇間的相似度較低。首先確定所要聚類的最終數目 K，并從樣本中隨機選擇 K 個樣本作為中心；其次將集合中每個數據點被劃分到與其距離最近的簇中心所在的類簇之中，形成 K 個聚類的初始分布；然后對分配完的每一個類簇內對象計算平均值，重新確定新的簇中心，繼續進行數據分配過程；迭代執行若干次，若簇中心不再發生變化，且聚類準則函數收斂，則將數據對象完全分配至所屬的類簇中；否則繼續執行迭代過程，直至聚類準則函數收斂。

（2）K均值算法過程

K均值算法具體描述如下。

假設給定的n個樣本是，每個x(i)∈Rn，其中樣本間的距離選擇歐氏距離。

輸入：n個樣本和簇的數目K。

輸出：K個簇，且平方誤差準則最小。

具體步驟如下。

① 確定所要聚類的最終數目K，并從樣本中隨機選擇K個樣本作為中心，即μ1,μ2,",μk∈Rn。

② 重復以下過程，直至誤差平方和準則函數E收斂至某個固定值。

{

對每個樣本i，計算并確定其應屬類別：

對于每一個類j，重新計算類的簇中心：

計算E，并判斷其是否收斂于某個固定的值。

}

其中K為確定的值，C(i)代表樣本i與K個類中距離最近的類，取值為[1,K]，簇中心μj代表對屬于同一個類的樣本中心點的預測。

聚類準則函數用于判斷聚類質量的高低，一般采用誤差平方和準則函數 E 的值變化情況判斷是否繼續進行迭代過程，E的值在每次迭代過程中逐漸減小，最終收斂至一個固定的值，則迭代過程結束，否則繼續執行迭代過程，直至E收斂。

誤差平方和準則函數E定義如下：

其中，E是所有樣本點的平方誤差的總和，p是某一樣本點，mi是簇Ci的平均值。

3．K中心點聚類（K-mediods）

K中心點聚類算法是對K均值聚類的改進，屬于基于劃分方法的聚類。與K均值聚類算法相比，優點是減輕了對孤立點的敏感性，提高了聚類結果的準確率；缺點是算法的復雜性比 K 均值聚類算法高。K 中心聚類算法與 K 均值聚類算法最大的區別在于選擇將簇內離平均值最近的對象作為該簇的中心，而不是將簇內各對象的平均值作為簇的中心。

（1）K中心點算法基本思想

K中心點算法的基本思想如下。

① 確定所要聚類的最終數目K，并從樣本中隨機選擇K個樣本作為中心。

② 將集合中每個數據點被劃分到與其距離最近的簇中心所在的類簇之中，形成K個聚類的初始分布。

③ 反復地利用各簇中的非中心點樣本來替代中心點樣本，并計算各簇中各中心點樣本與非中心點樣本的距離之和。

④ 迭代執行若干次，尋找最小距離之和，通過不斷更新各距離值來不斷調整聚類的結果。

（2）K中心點算法過程

K中心點算法具體描述如下。

假設給定的n個樣本是，每個x(i)∈Rn，其中樣本間的距離選擇歐氏距離。

輸入：n個樣本和簇的數目K。

輸出：K個簇。

具體步驟如下。

① 確定所要聚類的最終數目K，并從樣本中隨機選擇K個樣本作為中心，即o1,o2,",ok(ok∈D)。

② 對每個樣本p，計算并確定其應屬類別，使得其歐氏距離M最小。

③ 調整聚類中心，隨機選取一個非簇中心樣本orandom代替om (1≤m≤k)，重新分配所有剩余樣本p，使得

④ 若M′?M <0，則orandom=om，否則本次迭代中om不發生變化。

⑤ 重復執行以上步驟，直到步驟③中M′?M <0不再成立，否則繼續迭代執行②。