K-means聚類演算法，K-means又叫-k均值或者k-平均聚類演算法。演算法思想就是首先會隨機確定k個中心點作為聚類中心，然後把各個數據點分配給最鄰近的中心點，分配完成後將中心點移動到所表示的聚類的平均中心位置處，然後重複迭代上述步驟直到分配過程不再產生變化位置。

K-means演算法步驟：

假設輸入樣本為T= X_{1} , X_{2} ,..., X_{m} ;則演算法步驟為（使用歐幾里得距離公式）：

  • 選擇初始化的k個類別中心 a_{1} , a_{2} ,... a_{k} ;
  • 對於每個樣本 X_{i} ，將其標記位距離類別中心 a_{j} 最近的類別j；
  • 更新每個類別的中心點 a_{j} 為隸屬該類別的所有樣本的均值；
  • 重複上面兩步操作，直到達到某個中止條件。

中止條件：

迭代次數、最小平方誤差MSE、簇中心點變化率

K-means演算法流程：

  1. 對於k值的選擇，一般會根據先驗經驗選擇，如果沒有什麼先驗經驗，可以通過交叉驗證選擇合適的K。k個初始化的質心的位置選擇對最後的聚類結果和運行時間都有很大的影響，因此需要選擇合適的k個質心，最好這些質心不能太近。記K個簇中心分別為a_{1} , a_{2} ,... a_{k} ;每個簇的樣本數量為 N_{1} , N_{2} ,..., N_{k} ;
  2. 使用平方誤差作為目標函數（使用歐幾里得距離），公式為：

3.當目標函數取最小值時取得最優解，對J函數求偏導數，可以得到簇中心點a更新的公式為：

4.如果K個質心不再發生變化，輸出簇劃分。

傳統K-means實現：

import random
from sklearn import datasets
import numpy as np

# 正規化數據集 X
def normalize(X, axis=-1, p=2):
lp_norm = np.atleast_1d(np.linalg.norm(X, p, axis))
lp_norm[lp_norm == 0] = 1
return X / np.expand_dims(lp_norm, axis)

# 計算一個樣本與數據集中所有樣本的歐氏距離的平方
def euclidean_distance(one_sample, X):
one_sample = one_sample.reshape(1, -1)
X = X.reshape(X.shape[0], -1)
distances = np.power(np.tile(one_sample, (X.shape[0], 1)) - X, 2).sum(axis=1)
return distances

class Kmeans():
def __init__(self, k=2, max_iterations=500, varepsilon=0.0001):
self.k = k
self.max_iterations = max_iterations
self.varepsilon = varepsilon

# 從所有樣本中隨機選取self.k樣本作為初始的聚類中心
def init_random_centroids(self, X):
n_samples, n_features = np.shape(X)
centroids = np.zeros((self.k, n_features))
for i in range(self.k):
centroid = X[np.random.choice(range(n_samples))]
centroids[i] = centroid
return centroids

# 返回距離該樣本最近的一個中心索引[0, self.k)
def _closest_centroid(self, sample, centroids):
distances = euclidean_distance(sample, centroids)
closest_i = np.argmin(distances)
return closest_i

# 將所有樣本進行歸類，歸類規則就是將該樣本歸類到與其最近的中心
def create_clusters(self, centroids, X):
n_samples = np.shape(X)[0]
clusters = [[] for _ in range(self.k)]
for sample_i, sample in enumerate(X):
centroid_i = self._closest_centroid(sample, centroids)
clusters[centroid_i].append(sample_i)
return clusters

# 對中心進行更新
def update_centroids(self, clusters, X):
n_features = np.shape(X)[1]
centroids = np.zeros((self.k, n_features))
for i, cluster in enumerate(clusters):
centroid = np.mean(X[cluster], axis=0)
centroids[i] = centroid
return centroids

# 將所有樣本進行歸類，其所在的類別的索引就是其類別標籤
def get_cluster_labels(self, clusters, X):
y_pred = np.zeros(np.shape(X)[0])
for cluster_i, cluster in enumerate(clusters):
for sample_i in cluster:
y_pred[sample_i] = cluster_i
return y_pred

# 對整個數據集X進行Kmeans聚類，返回其聚類的標籤
def predict(self, X):
# 從所有樣本中隨機選取self.k樣本作為初始的聚類中心
centroids = self.init_random_centroids(X)

# 迭代，直到演算法收斂(上一次的聚類中心和這一次的聚類中心幾乎重合)或者達到最大迭代次數
for _ in range(self.max_iterations):
# 將所有進行歸類，歸類規則就是將該樣本歸類到與其最近的中心
clusters = self.create_clusters(centroids, X)
former_centroids = centroids

# 計算新的聚類中心
centroids = self.update_centroids(clusters, X)

# 如果聚類中心幾乎沒有變化，說明演算法已經收斂，退出迭代
diff = centroids - former_centroids
if diff.any() < self.varepsilon:
break

return self.get_cluster_labels(clusters, X)

def main():
# Load the dataset
X, y = datasets.make_blobs(n_samples=10000,
n_features=3,
centers=[[3,3, 3], [0,0,0], [1,1,1], [2,2,2]],
cluster_std=[0.2, 0.1, 0.2, 0.2],
random_state =9)

# 用Kmeans演算法進行聚類
clf = Kmeans(k=4)
y_pred = clf.predict(X)

K-means演算法在迭代的過程中使用所有點的均值作為新的質點(中心點)，如果簇中存在異常點，將導致均值偏差比較嚴重。比如一個簇中有2、4、6、8、100五個數據，那麼新的質點為24，顯然這個質點離絕大多數點都比較遠；在當前情況下，使用中位數6可能比使用均值的想法更好，使用中位數的聚類方式叫做K-Mediods聚類(K中值聚類)。對於極端數據，還可以先做異常點檢測，剔除異常點後再聚類。常用的異常點檢測方法比如 oneClassSVM。

K-means演算法是初值敏感的，選擇不同的初始值可能導致不同的簇劃分規則。為了避免這種敏感性導致的最終結果異常性，可以採用初始化多套初始節點構造不同的分類規則，然後選擇最優的構造規則。

為了解決K-means初值敏感、運行耗時問題，有了以下優化演算法：

1、二分K-Means

解決K-Means演算法對初始簇心比較敏感、收斂於局部最小值的問題，二分K-Means演算法是一種弱化初始質心的一種演算法。具體思路步驟如下：

  • 將所有樣本數據作為一個簇放到一個隊列中
  • 當簇小於數目k時，對於每一個簇計算總誤差，在給定的簇上進行K-均值聚類,k值為2，計算將該簇劃分成兩個簇後總誤差SSE，選擇是的誤差最小的那個簇進行劃分（還有一種辦法是對樣本數據量最多的簇進行劃分）
  • 循環迭代第二步操作，直到中止條件達到(聚簇數量、最小平方誤差、迭代次數等)
  • 隊列中的簇就是最終的分類簇集合

2、K-Means++

K-Means++演算法和K-Means演算法的區別主要在於初始的K個中心點的選擇方面，K-Means演算法使用隨機給定的方式，K-Means++演算法採用下列步驟給定K個初始質點：

  • 從數據集中任選一個節點作為第一個聚類中心
  • 對數據集中的每個點x，計算x到所有已有聚類中心點的距離和D(X)，基於D(X)採用線性概率選擇出下一個聚類中心點(距離較遠的一個點成為新增的一個聚類中心點)
  • 重複步驟2知道找到k個聚類中心點

由於聚類中心點選擇過程中的內在有序性，在擴展方面存在著性能方面的問題(第k個聚類中心點的選擇依賴前k-1個聚類中心點的值)。

3、K-Means||

為了解決K-Means++演算法缺點而產生的一種演算法。主要規則是改變每次遍歷時候的取樣規則，並非按照K-Means++演算法每次遍歷只獲取一個樣本而是每次獲取K個樣本，，重複該取樣操作O(logn)次，然後再將這些抽樣出來的樣本聚類出K個點，最後使用這K個點作為K-Means演算法的初始聚簇中心點。實踐證明：一般5次重複採樣就可以保證一個比較好的聚簇中心點。

4、elkan K-Means

在傳統的K-Means演算法中，我們每輪迭代時，計算所有的樣本點到所有的質心的距離，這樣比較耗時。elkan K-Means對於距離計算優化，減少不必要的距離的計算。elkan K-Means利用了兩邊之和大於等於第三邊,以及兩邊之差小於第三邊的三角形性質，來減少距離的計算。

第一種規律是對於一個樣本點x和兩個質心A、B。如果我們預先計算出了這兩個質心之間的距離D( j_{1} ， j_{2} )D( j_{1} , j_{2} )，則如果計算髮現2D(x, j_{1} )≤D( j_{1} ， j_{2} )，我們立即就可以知道D(x， j_{1} )≤D(x， j_{2} )。此時我們不需要再計算D(x， j_{2} )，也就是說省了一步距離計算。

第二種規律是對於一個樣本點xx和兩個質心A、B。我們可以得到D(x， j_{2} )≥max{0,D(x， j_{1} )?D( j_{1} ， j_{2} )}。這個從三角形的性質也很容易得到。

利用上邊的兩個規律，迭代速度有很大的提高。但是如果特徵是稀疏的，有缺失值的話，這個方法就不適用了，此時某些距離無法計算，則不能使用該演算法。

6、Mini Batch K-Means

Mini Batch K-Means演算法是K-Means演算法的一種優化變種，採用小規模的數據子集(每次訓練使用的數據集是在訓練演算法的時候隨機抽取的數據子集)減少計算時間，同時試圖優化目標函數；Mini Batch K-Means演算法可以減少K-Means演算法的收斂時間，而且產生的結果效果只是略差於標準K-Means演算法。

演算法步驟如下：

  • 抽取部分數據集，使用K-Means構建出K個聚簇點的模型
  • 繼續抽取訓練數據集中的部分數據集樣本數據，並將其添加到模型中，分配給最近的聚簇中心點
  • 更新局促的中心點值
  • 循環迭代第二步和第三步，直到中心點穩定或者達到迭代次數，停止計算操作

最後對對K-Means的優缺點做一個總結。

K-Means的主要優點有：

1、原理簡單，易實現，可解釋性強；

2、聚類效果較優，尤其當簇近似高斯分布；

3、主要需要調參的參數只有簇數K；

4、處理大數據集的時候，該演算法可以保證較好的伸縮性和高效率。

K-Means的主要缺點有：

1、不適合發現非凸形狀的簇或者大小差別較大的簇；

2、對雜訊和異常點比較敏感；

3、K值是用戶給定的，在進行數據處理前，K值是未知的，不同的K值得到的結果也不一 樣；

4、對初始簇的中心點敏感。


推薦閱讀：
相关文章