《Python網絡爬蟲與數據挖掘小課堂》——part3

2019 年 11 月 24 日
筆記

基於Python的K-Means聚類數據分析

摘要：在數據挖掘中，K-Means算法是一種 cluster analysis 的算法，其主要是來計算數據聚集的算法，主要通過不斷地取離種子點最近均值的算法。

來源於維基百科，自由的百科全書的解釋：

k-平均算法源於信號處理中的一種向量量化方法，現在則更多地作為一種聚類分析方法流行於數據挖掘領域。k-平均聚類的目的是：把n個點（可以是樣本的一次觀察或一個實例）劃分到k個聚類中，使得每個點都屬於離他最近的均值（此即聚類中心）對應的聚類，以之作為聚類的標準。這個問題將歸結為一個把數據空間劃分為Voronoi cells的問題。

在數據挖掘中，K-Means算法是一種cluster analysis的算法，其主要是來計算數據聚集的算法，主要通過不斷地取離種子點最近均值的算法。

問題

K-Means算法主要解決的問題如下圖所示。我們可以看到，在圖的左邊有一些點，我們用肉眼可以看出來有四個點群，但是我們怎麼通過計算機程序找出這幾個點群來呢？於是就出現了我們的K-Means算法。

算法概要

這個算法其實很簡單，如下圖所示：

從上圖中，我們可以看到，A，B，C，D，E是五個在圖中點。而灰色的點是我們的種子點，也就是我們用來找點群的點。有兩個種子點，所以K=2。

然後，K-Means的算法如下：

隨機在圖中取K（這裡K=2）個種子點。
然後對圖中的所有點求到這K個種子點的距離，假如點Pi離種子點Si最近，那麼Pi屬於Si點群。（上圖中，我們可以看到A，B屬於上面的種子點，C，D，E屬於下面中部的種子點）
接下來，我們要移動種子點到屬於他的「點群」的中心。（見圖上的第三步）
然後重複第2）和第3）步，直到，種子點沒有移動（我們可以看到圖中的第四步上面的種子點聚合了A，B，C，下面的種子點聚合了D，E）。

這個算法很簡單，但是有些細節我要提一下，求距離的公式我不說了，大家有初中畢業水平的人都應該知道怎麼算的。我重點想說一下"求點群中心的算法"。

求點群中心的算法

一般來說，求點群中心點的算法你可以很簡的使用各個點的X/Y坐標的平均值。不過，我這裡想告訴大家另三個求中心點的的公式：

1）Minkowski Distance公式——λ可以隨意取值，可以是負數，也可以是正數，或是無窮大。

2）Euclidean Distance公式——也就是第一個公式λ=2的情況

3）CityBlock Distance公式——也就是第一個公式λ=1的情況

這三個公式的求中心點有一些不一樣的地方，我們看下圖（對於第一個λ在0-1之間）。

上面這幾個圖的大意是他們是怎麼個逼近中心的，第一個圖以星形的方式，第二個圖以同心圓的方式，第三個圖以菱形的方式。