書名: 商用機器學習:數據科學實踐作者名: (加)約翰·赫爾本章字數: 1124字更新時間: 2020-10-16 17:15:27
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值等于觀測值的數量時,每個觀測值都有一個聚類,此時慣性矩為零。
- Clojure Programming Cookbook
- Visual C++串口通信開發入門與編程實踐
- Python機器學習:數據分析與評分卡建模(微課版)
- 網店設計看這本就夠了
- Visual C++數字圖像處理技術詳解
- 網絡爬蟲原理與實踐:基于C#語言
- jQuery開發基礎教程
- Mastering Android Game Development
- 零基礎學Java第2版
- Offer來了:Java面試核心知識點精講(框架篇)
- Getting Started with hapi.js
- 從零開始學UI設計·基礎篇
- ASP.NET Core 2 High Performance(Second Edition)
- Java EE互聯網輕量級框架整合開發:SSM+Redis+Spring微服務(上下冊)
- 秒懂算法:用常識解讀數據結構與算法