官术网_书友最值得收藏!

2.2 k-均值算法

將觀測值進行聚類分析時,我們需要進行距離衡量。首先假設有兩個特征取值x和y,將兩個特征的散點分布圖顯示在二維坐標圖上。假設其中有兩個觀測值A和B,如圖2-1所示,則兩點之間的距離計算為歐氏距離(Euclidean distance),即圖中直線AB的長度。假設對于觀測值A,x=xA且y=yA,同樣對于觀測值B,x=xB且y=yB,則A與B兩點間的歐式距離為(利用畢達哥拉斯定理,即勾股定理):

該距離的計算方法可以被延伸到更多的維度上。假設我們的一組觀測值中有m個特征,對于第i個觀測值的第j列特征,我們稱之為vij,則第p個觀測值與第q個觀測值之間的距離為:

圖2-1 A與B之間的距離,通過(xA,yA)和(xB,yB)兩點坐標,計算出直線AB的長度

將兩個特征擴展到三個很容易理解,即通過衡量三個而不是兩個維度去計算距離;如果假設需要衡量的距離超過三個(m>3)就變得不那么容易了,但公式依然是由一個、兩個、三個維度延展而來的。

另外一個在k-均值算法中需要了解的定義是一個聚類的中心(center),又被稱為聚類的矩心(centroid)。假設一部分觀測值被歸為同個聚類,則中心為這個聚類中每個特征的所有觀測值的平均數;如表2-1所示,假設某個聚類中有4個特征和5個觀測值,則這個聚類的中心0.914、0.990、0.316和0.330依次為特征1、2、3、4的中心(例如,0.914為1.00、0.80、0.82、1.10和0.85的平均數)。所以,每個觀測值與聚類中心之間的距離(表2-1的最后一列)的計算方式與A和B點的距離(見圖2-1)的計算方式一致。第一個觀測值與聚類中心的距離計算如下:

計算結果等于0.145。

表2-1 5個觀測值和4個特征的聚類中心計算

圖2-2闡述了k-均值算法是如何運行的。第一步是要選擇k,即聚類的個數(后續將更詳細地講解)。作為第一步,我們通常隨機選擇k個點作為每個子聚類的中心。每個觀測值與每個子聚類中心的距離由上面介紹的方法計算而得,然后觀測值被分配到最近的一個聚類中。這樣就產生了由所有樣本第一次分割而成的k個聚類。然后,我們為每個聚類計算新的子聚類中心,如圖2-2所示。每個觀測值與這個新的中心的距離可以被計算出來,然后按照距離大小重新將每個觀測值分配到最鄰近的聚類中心。依此類推,我們不停地迭代產生新的中心,直到子聚類的分配不再產生變化為止。

一種衡量上述算法效果的指標為聚類內的平方和,也就是“慣性矩”(inertia),設di為第i個觀測值與其子聚類中心的距離:

圖2-2 k-均值算法

式中,n為觀測值的數量,在已設置k值的條件下,聚類算法的目的是使慣性矩最小化。在k-均值算法中,最終的結果可能會受初始設置子聚類個數的影響(k值),所以我們必須嘗試設置不同的個數,以確保慣性矩最小化,即聚類的最優結果。

在通常情況下,慣性矩隨著k值上升而下降,當k值數量達到極限,即k值等于觀測值的數量時,每個觀測值都有一個聚類,此時慣性矩為零。

主站蜘蛛池模板: 应用必备| 迁安市| 辉县市| 西乌珠穆沁旗| 浏阳市| 东宁县| 伊宁县| 磐石市| 辽阳县| 确山县| 澎湖县| 庐江县| 宁波市| 建宁县| 南丰县| 西乌珠穆沁旗| 祥云县| 台安县| 大田县| 荔波县| 米泉市| 偏关县| 蓬安县| 峨山| 安远县| 钦州市| 五寨县| 大丰市| 孟津县| 甘德县| 永年县| 宜阳县| 屏边| 太仆寺旗| 南木林县| 仁化县| 民丰县| 同江市| 东乌| 休宁县| 凌源市|