簡介

K均值聚類，也叫做K-Means Clustering，是一種著名的用于分類問題的無監(jiān)督機器學(xué)習(xí)聚類算法。聚類是針對給定的樣本，依靠它們特征的相似度或者距離，將其歸到若干個‘類’或者’簇‘的數(shù)據(jù)分析問題。一個類就是給定樣本集合的一個子集。所謂”人以類聚，物以群分“，常理來看，越相似的人更容易聚集在一起，在這里也是一樣，相似的樣本聚集在相同的類里面，不相似的樣本分布在不同的類里。聚類屬于無監(jiān)督學(xué)習(xí)，因為只是根據(jù)樣本特征之間的相似度或者距離來進(jìn)行分類，而類或者簇事先并不知道，即這些類或者簇的個數(shù)以及對應(yīng)的概念語義需要使用者來把握和命名。下圖是對K-Means聚類算法執(zhí)行過程的一個動圖展示，圖片來自維基百科。

K-Means算法流程

聚類的基本概念

1. 相似度或距離度量方法

聚類的對象是觀測數(shù)據(jù)或者樣本集合。上面我們講到相似的樣本更大可能會聚集在相同的類或者簇里，但是如何來定義相似性呢？如果是判斷兩個人是否相似的話，我們一般會觀察這2個人的身高，長相，性格，習(xí)慣等特征，以此來判斷是否相似。同理，如果我們有 $n$ 個樣本，每個樣本具有 $m$ 個屬性，假設(shè)我們能夠計算出任意兩個樣本的每個屬性之間的相似度(similariity)或者距離(distance)，那么我們就可以根據(jù)這個值來判斷這兩個樣本是否相似。因此，聚類的核心概念是相似度和距離，有很多相似度和距離的計算方式。因為相似度和距離直接影響到聚類的結(jié)果，所以選擇適當(dāng)?shù)南嗨贫群途嚯x度量方法，是聚類的根本問題。
如果我們將樣本集合看成是空間中的點的集合，以該空間的距離表示樣本之間的相似度，那么常用的距離有閔可夫斯基距離，閔可夫斯基距離越大表示相似度越小，距離越小則相似度越大。

我們常用的歐氏距離，其實就是閔可夫斯基距離的一種。

給定樣本集合 $X$ , $X$ 是 $m$ 維實數(shù)向量空間 $R^m$ 中點的集合，其中 $x_i, x_j \in X, x_i = (x_{1i}, x_{2i},...,x_{mi})^T, x_j = (x_{1j}, x_{2j},...,x_{mj})^T, 那么樣本x_i和樣本x_j之間的閔可夫斯基距離定義為:$
$d_{ij} = (\sum_{k=1}^m |x_{ki} - x_{kj} |^p)^{ \frac {1}{p} }, 其中 p \ge 1$
當(dāng) $p = 2$ 時，稱為歐氏距離，即：
$d_{ij} = (\sum_{k=1}^m |x_{ki} - x_{kj} |^2 ) ^ { \frac {1}{2} }$
當(dāng) $p = 1$ 時，稱為曼哈頓距離，即：
$d_{ij} = \sum_{k=1}^m |x_{ki} - x_{kj}|$
當(dāng) $p = \inf$ 時，稱為切比雪夫距離，即取各個坐標(biāo)數(shù)值差的絕對值的最大值：
$d_{ij} = max_k(|x_{ki} - x_{kj}|)$

最常用也是大家最熟悉的，莫過于歐氏距離。除了上述距離度量方式以外，還有馬哈拉諾比斯距離、相關(guān)系數(shù)、夾角余弦等等。感興趣的讀者可以自行查閱資料。

2. 類或者簇的定義

通過上節(jié)講的相似度或者距離的度量方式，我們現(xiàn)在可以計算兩個樣本之間的距離了，然后通過聚類可以得到類或者簇，本質(zhì)都是樣本的子集。如果一個聚類方法假定一個樣本只能屬于一個類，或者類的交集為空集，那么該方法稱為硬聚類方法。否則，如果一個樣本屬于多個類，或者類的交集不為空集，那么該方法稱為軟聚類方法。用 $G$ 表示類或者簇，用 $x_i, x_j$ 表示類中的樣本，用 $n_G$ 表示 $G$ 中樣本的個數(shù)，用 $d_{ij}$ 表示樣本 $x_i, x_j$ 之間的距離。
設(shè) $T$ 為給定的正數(shù)，若集合 $G$ 中任意兩個樣本 $x_i, x_j$ , 若 $d_{ij}$ 滿足：
$d_{i,j} \leq T$
那么稱 $G$ 為一個類或者簇。
得到了一個類或者簇，也就是得到了一個子集，那么如何來描述這個類呢，主要有以下幾種方式:

使用類中所有樣本的均值 $\overline x_G$ ，即類的中心
$\overline x_G = \frac {1}{n_G} \sum_{i=1}^{n_G} x_i$
使用類中任意兩個樣本之間的最大距離 $D_G$ ，即
$D_G = max d_{ij}$
使用類的樣本散布矩陣 $A_G$ 和樣本協(xié)方差矩陣 $S_G$
$A_G = \sum_{i=1}^{n_G} (x_i - \overline x_G)(x_i - \overline x_G)^T \\ S_G = \frac {1}{m-1} \sum_{i=1}^{n_G} (x_i - \overline x_G)(x_i - \overline x_G)^T \\$
其中 $m$ 為樣本的維度（樣本屬性的個數(shù)）。

3. 類間距離的度量

如果我們現(xiàn)在已經(jīng)有兩個類 $G_p、G_q$ ，分別包含 $n_p、n_q$ 個樣本，分別用 $\overline x_p、 \overline x_q$ 來代表它們的均值，即類中心。那么我們?nèi)绾魏饬窟@兩個類之間的距離呢？這里面也包含好幾種定義，如下。

最短距離或單連接
定義類 $G_p$ 的樣本與類 $G_q$ 的樣本之間的最短距離為兩類之間的距離
$D_{pq} = min(d_{ij} | x_i \in G_p, x_j \in G_q)$
最大距離或完全連接
定義類 $G_p$ 的樣本與類 $G_q$ 的樣本之間的最長距離為兩類之間的距離
$D_{pq} = max(d_{ij} | x_i \in G_p, x_j \in G_q)$
中心距離
定義類 $G_p$ 的類中心與類 $G_q$ 的類中心之間的距離
$D_{pq} = d_{\overline x_p \overline x_q}$

中心距離是我們比較常用的。

K-Means算法流程

在了解了聚類算法的相關(guān)基本概念之后，現(xiàn)在我們就可以正式介紹K-Means算法了。K-Means Clustering算法譯為K均值聚類算法，它是基于樣本集合劃分的聚類算法。k均值聚類將樣本集合劃分為k個子集，構(gòu)成k個類，將n個樣本劃分到k個類中，每個樣本到其所屬的類中心距離最短。并且每個樣本只能屬于一個類，故k均值聚類是硬聚類算法。K-均值算法歸結(jié)為對樣本集合X的劃分，或者說從樣本到類的函數(shù)的選擇問題。K-均值聚類的策略是通過損失函數(shù)的最小化選取最優(yōu)的劃分或者函數(shù)。

1. 策略

我們首先統(tǒng)一一下相似度或距離的度量方式，在下文中統(tǒng)一采用歐氏距離作為樣本之間的距離度量 $d(x_i, x_j)$ 。
$d(x_i, x_j) = \sum_{k=1}^m (x_{ki} - x_{kj})^2 = ||x_i - x_j ||^ 2$
接著，定義樣本與其所屬的類中心之間的距離的總和為損失函數(shù)，即：
$W(C) = \sum_{l=1}^k \sum_{C(i)=l} || x_i - \overline x_l||^2$
其中 $\overline x_l$ 是第 $l$ 個類的均值或者聚類中心， $C(i)=l$ 是指示函數(shù)，判斷第 $i$ 個樣本是否屬于第 $l$ 個類或簇。因此K均值算法就變成了一個最優(yōu)化問題：
$C^* = argmin \sum_{l=1}^k \sum_{C(i)=l} || x_i - \overline x_l||^2$
相似的樣本總是被聚到同類中，此時的損失函數(shù)值最小，這個目標(biāo)函數(shù)的最優(yōu)化能達(dá)到聚類的目的。但是這是個組合問題，所有可能的分法是指數(shù)級別的，實際操作時，我們一般采用迭代的方法逐漸逼近問題的解。

算法流程

k-均值聚類算法是一個迭代的過程，每次迭代包括兩個步驟。

首先選擇k個類的中心，將樣本逐漸指派到與其最相近的中心的類中，得到一個聚類結(jié)果。
接著計算每個類中的樣本均值，將其作為新的聚類中心。

不斷重復(fù)以上兩個步驟，直到聚類中心不再發(fā)生改變。
下面給出算法具體步驟：
輸入為 $n$ 個樣本集合 $X$ ，輸出為樣本的聚類 $C$ 。
（1）初始化時，令 $t=0$ ，從樣本集合中隨機選擇k個樣本作為初始聚類中心 $m^{(0)} = (m_1^{(0)},m_2^{(0)},...,m_k^{(0)} )$ 。
（2）對樣本進(jìn)行聚類。對固定的類中心 $m^{(t)} = (m_1^{(t)},m_2^{(t)},...,m_k^{(t)} )$ ，其中 $m_l^{(t)}$ 是 $G_l$ 的中心，計算每個樣本到所有類中心的距離，將每個樣本指派到與其最近的類中心去，構(gòu)成聚類結(jié)果 $C^{(t)}$ 。
（3）計算新的類中心。對每一輪的聚類結(jié)果 $C^{(t)}$ ，計算當(dāng)前各個類中的樣本的均值，作為新的類中心 $m^{(t)} = (m_1^{(t+1)},m_2^{(t+1)},...,m_k^{(t+1)} )$ 。
（4）如果步驟（3）中計算出來的聚類中心結(jié)果與步驟（2）一樣，即聚類中心不再發(fā)生改變，那么算法停止，輸出結(jié)果。否則 $t=t+1$ ，返回步驟（2）繼續(xù)執(zhí)行。

k-均值聚類算法的復(fù)雜度為O(mnk)，其中m是樣本的維度，n是樣本的個數(shù)，k是類或者簇的個數(shù)。

實例演示

假如我們有以下5個樣本點(為了可視化，這里選擇的是二維平面上的坐標(biāo)點)的集合，我們需要通過K-均值聚類算法將其聚集到2個類中。原始數(shù)據(jù)點如下。

import matplotlib.pyplot as plt

x_point = [0,0,1,5,5]
y_point = [2,0,0,0,2]
label_y = ['k','k','k','k','k']

plt.scatter(x_point, y_point, c=label_y)
# 設(shè)置坐標(biāo)軸范圍
plt.xlim(-2,6)
plt.ylim(-2,6)

plt.grid()
plt.show()

原始數(shù)據(jù)點

接著，我們從樣本點中隨機選擇兩個點作為初始的聚類中心點

m_1,m_2

，這里假設(shè)我們選擇的是

x_1

(0,2)和

x_2

(0,0)點，我們在圖中將其標(biāo)注出來，如下：

初始2個聚類中心

然后以

m_1, m_2

為聚類中心，形成兩個類

G_1, G_2

。計算每個點到聚類中心的距離，有：
對于

x_3而言，有d(x_3, m_1) = 2.23, d(x_3, m_2) = 1

,故

x_3

被分到

G_2

。
對于

x_4而言，有d(x_4, m_1) = 5.38, d(x_4, m_2) = 5

,故

x_3

被分到

G_2

。
對于

x_5而言，有d(x_5, m_1) = 5, d(x_5, m_2) = 5.38

,故

x_3

被分到

G_1

。
經(jīng)過這一輪劃分之后，得到了新的類

G_1 = \{ x_1, x_5 \}

G_2 = \{ x_2, x_3, x_4 \} \

。此時需要重新計算新的聚類中心

m_1, m_2

，有：

m_1 = (2.5, 2.0), m_2=(2, 0)

下面是新的樣本分布圖:

一次迭代之后

上圖中畫圈的是新的聚類中心，注意新計算的聚類中心不一定就在樣本上了。
重復(fù)上述步驟，直到聚類中心不再改變，具體就不再贅述了。

sklearn庫算法包

sklearn庫中已經(jīng)有包裝好的K-Means聚類算法，下面來展示一下其用法。我們使用sklearn的聚類數(shù)據(jù)集生成器，生成一些聚類數(shù)據(jù)，然后對其使用K-Means算法。如下：

import matplotlib.pyplot as plt
import seaborn as sns; sns.set()  # for plot styling
import numpy as np

from sklearn.datasets.samples_generator import make_blobs
X, y_true = make_blobs(n_samples=100, centers=4,
                       cluster_std=0.60, random_state=0)
plt.scatter(X[:, 0], X[:, 1], s=50);

聚類數(shù)據(jù)

肉眼觀察可以看到這實際上可以聚為4類，接下來我們使用K-Means算法來自動進(jìn)行分類。

from sklearn.cluster import KMeans
kmeans = KMeans(n_clusters=4)
kmeans.fit(X)
y_kmeans = kmeans.predict(X)
y_kmeans

可視化一下：

plt.scatter(X[:, 0], X[:, 1], c=y_kmeans, s=50, cmap='viridis')
# 取出K-Means算法得到的聚類中心
centers = kmeans.cluster_centers_
print(centers)
plt.scatter(centers[:, 0], centers[:, 1], c='r', marker='*', s=200);

K-Means算法結(jié)果

可以看到K-Means算法得到的結(jié)果跟我們直觀看上去的很接近，很完美的完成了聚類任務(wù)。

手寫K-Means算法

鑒于K-Means算法比較經(jīng)典，同時也比較簡單，因此在很多大廠面試的時候，都要求能夠手寫K-Means算法，本文這里也給出一個簡單實現(xiàn)，如下：

import numpy as np

def euclidean(X, Y):
    return sum([(a - b)**2 for (a,b) in zip(X,Y)])**0.5

def dispatch_samples(x, centers):
    # 將樣本x指派到距離最近的聚類中心
    res = []
    for i in range(x.shape[0]):
        idx, dis = 0, float('inf')
        for j in range(centers.shape[0]):
            d = euclidean(x[i], centers[j])
            if d < dis:
                idx, dis = j, d
        res.append(idx) # 將當(dāng)前樣本指派的類別放入數(shù)組中
    return np.array(res)

def Simple_KMeans(X, n_clusters, rseed=2):
    # 1. 首先隨機選擇n_clusters個樣本作為原始聚類中心
    # 生成一個偽隨機數(shù)生成器，每次都通過它來生成隨機數(shù)，可以保證每次運行生成的隨機數(shù)是一樣
    rng = np.random.RandomState(rseed)
    # 取一個排列，然后取前n_clusters個作為聚類中心
    i = rng.permutation(X.shape[0])[:n_clusters]
    centers = X[i]
    while True:
        # 1. 對每個樣本都計算其到所有聚類中心的距離，將樣本指派到距離其最近的聚類中心
        labels = dispatch_samples(X, centers)
        # 2. 重新計算當(dāng)前聚類的聚類中心
        new_centers = np.array([X[labels == i].mean(0) for i in range(n_clusters)])
        
        # 如果新的聚類中心與之前一致，則退出算法
        if np.all(centers == new_centers): break
        # 使用新的聚類中心
        centers = new_centers
    # 返回聚類中心和標(biāo)簽
    return centers, labels

centers, labels = Simple_KMeans(X, 4)
plt.scatter(X[:, 0], X[:, 1], c=labels, s=50, cmap='viridis');
plt.scatter(centers[:, 0], centers[:, 1], c='r', marker='*', s=200);

生成的結(jié)果與調(diào)用sklearn庫是一樣的，如下：

手寫K-Means算法執(zhí)行結(jié)果

K-Means優(yōu)缺點

K-Means算法是一個經(jīng)典的，實用的聚類算法，值得我們?nèi)フ莆账哂幸韵聝?yōu)點：

算法原理簡單，實現(xiàn)容易，收斂較快
聚類效果較優(yōu)
算法可解釋性較強
參數(shù)較少，僅僅需要類別數(shù)K

當(dāng)然K-Means算法也有很多缺點，下面逐一說明。

K-Means算法得到的結(jié)果是局部最優(yōu)，并不總能得到全局最優(yōu)解。還是以上面的例子，如果我們使用另外一個隨機種子，那么得到的結(jié)果可能是這樣的。

centers, labels = find_clusters(X, 4, rseed=80)
plt.scatter(X[:, 0], X[:, 1], c=labels,
            s=50, cmap='viridis');

錯誤的聚類結(jié)果

可以看到，修改了隨機種子之后，說明初始聚類中心也改變了，那么得到的聚類結(jié)果就可能發(fā)生很大的改變，甚至不是我們想要的結(jié)果。

類的個數(shù)K必須手動提前設(shè)置
我們必須提前告訴算法要聚成多少類，這個數(shù)據(jù)算法無法自己從數(shù)據(jù)中學(xué)到。但是有時候我們也無法確定應(yīng)該設(shè)置成多少。算法只會乖乖地將數(shù)據(jù)聚合成我們設(shè)置給它的K類。在上面的例子中，如果我們將k設(shè)置成6，那么可能會得到以下的結(jié)果。

centers, labels = find_clusters(X, 6)
plt.scatter(X[:, 0], X[:, 1], c=labels,
            s=50, cmap='viridis');

聚成6類

算法確實收斂了，將樣本聚成了6類，但是這個結(jié)果對我們來說有意義嘛？這個不太好回答。因為實際應(yīng)用中的最優(yōu)K值往往是不知道的。解決這個問題的一個思路是，嘗試多個不同的K值，然后檢查不同K值下的聚類結(jié)果的質(zhì)量。衡量聚類結(jié)果的質(zhì)量的方式可以是計算算是函數(shù)值，也可以是使用類的平均直徑，即所有類的直徑取平均。一般來說，類別數(shù)k變小時，平均直徑會變大；類別說變大是，平均直徑會逐漸減小，直到某個閾值之后就不再減小。而這個值一般是最優(yōu)的k值。

K-Means聚類受限于線性聚類邊界
K-Means模型假設(shè)一個樣本點應(yīng)該是比其他點更加靠近自己的聚類中心，但是對于一些有復(fù)雜邊界的樣本集合，這個假設(shè)就不成立了，比如如下這種情況。

from sklearn.datasets import make_moons
X, y = make_moons(200, noise=.05, random_state=0)

labels = KMeans(2, random_state=0).fit_predict(X)
plt.scatter(X[:, 0], X[:, 1], c=labels,
            s=50, cmap='viridis');

復(fù)雜邊界樣本的聚類

實際上K-Means類之間的邊界應(yīng)該總是線性的，當(dāng)面對這種具有復(fù)雜邊界的情況是，K-Means算法并不能取得好的結(jié)果。

計算量巨大
同KNN算法一樣，K-Means算法在每次迭代的時候，每一個點都需要跟所有的聚類中心進(jìn)行距離計算，當(dāng)樣本的維度較高時，這個計算量是非常大的。

K-Means++算法

K-Means算法自1967年由MacQueen提出后，歷經(jīng)很多次改進(jìn)，比較有名的有K-Means++算法。K-Means++算法主要是解決前面提及的K-Means算法的初始化聚類中心隨機選擇導(dǎo)致的問題。K-Means++不再采用K-Means算法隨機確定初始聚類中心的做法，而是令最初選擇的聚類中心盡可能的遠(yuǎn)。這也符合我們的直覺，因為每個類之間就應(yīng)該盡可能的遠(yuǎn)。K-Means++算法的流程如下：
（1）隨機選取一個樣本作為第一個聚類中心 $c_1$ ；
（2）計算每個樣本與當(dāng)前已有類聚中心最短距離（即與最近一個聚類中心的距離），用 $D(x)$ 表示；這個值越大，表示被選取作為聚類中心的概率較大；最后，用輪盤法選出下一個聚類中心；
（3）：重復(fù)（2），直到選出 k 個聚類中心。

選出初始點后，其余步驟就與標(biāo)準(zhǔn)K-means 算法一致了。

參考

《統(tǒng)計學(xué)習(xí)方法》 -- 李航
《機器學(xué)習(xí)》-- 周志華
https://matplotlib.org/stable/api/_as_gen/matplotlib.pyplot.scatter.html
https://jakevdp.github.io/PythonDataScienceHandbook/05.11-k-means.html
https://zhuanlan.zhihu.com/p/32375430

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

K-Means聚類算法理論與代碼實踐

K-Means聚類算法理論與代碼實踐

簡介

聚類的基本概念

1. 相似度或距離度量方法

2. 類或者簇的定義

3. 類間距離的度量

K-Means算法流程

1. 策略

算法流程

實例演示

sklearn庫算法包

手寫K-Means算法

K-Means優(yōu)缺點

K-Means++算法

參考

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

K-Means聚類算法理論與代碼實踐

簡介

聚類的基本概念

1. 相似度或距離度量方法

2. 類或者簇的定義

3. 類間距離的度量

K-Means算法流程

1. 策略

算法流程

實例演示

sklearn庫算法包

手寫K-Means算法

K-Means優(yōu)缺點

K-Means++算法

參考

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av