文章目錄

• 1. 原型聚類
• • 1.1 KMeans
  • • 1.1.1 最小化成本函數(shù)
    • 1.1.2 實(shí)例
  • 1.2 KMeans++
  • • 1.2.1 KMeans++ 初始化實(shí)例
• 2. 在線可視化 KMeans
• 參考資料

相關(guān)文章：

機(jī)器學(xué)習(xí) | 目錄

機(jī)器學(xué)習(xí) | 聚類評估指標(biāo)

機(jī)器學(xué)習(xí) | 距離計(jì)算

無監(jiān)督學(xué)習(xí) | KMeans之Sklearn實(shí)現(xiàn)：電影評分聚類

無監(jiān)督學(xué)習(xí) | 層次聚類 之凝聚聚類原理及Sklearn實(shí)現(xiàn)

無監(jiān)督學(xué)習(xí) | DBSCAN 原理及Sklearn實(shí)現(xiàn)

無監(jiān)督學(xué)習(xí) | GMM 高斯混合聚類原理及Sklearn實(shí)現(xiàn)

1. 原型聚類

原型聚類亦稱“基于原型的聚類”（prototypr-based clustering）。此類算法假設(shè)聚類結(jié)構(gòu)能通過一組原型刻畫，在現(xiàn)實(shí)聚類任務(wù)重及其常用。通常情形下，算法先對原型進(jìn)行初始化，然后對原型進(jìn)行迭代更新求解。采用不同的原型表示、不同的求解方式，將產(chǎn)生不同的算法，如 KMeans、LVQ、高斯混合。下面介紹 KMeans 算法，我們將在下一篇文章中介紹高斯混合算法。

“原型”是指樣本空間具有代表性的點(diǎn)

1.1 KMeans

給定樣本集 $D=x_1,x_2,?,x_m$，“$k$ 均值”（k-means）算法針對聚類所得簇劃分 $C=C_1,C_2,?,C_k$ 最小化平方誤差（殘差平方和 $S_E$）：

$$E=\sum _{i=1}^k\sum _{x\in C_i}\Vert x?{\mu }_i{\Vert }_2^2\text{\hspace{1em}(1)}$$

其中 ${\mu }_i=\frac{1}{|C_i|}{\sum }_{x\in C_i}x$ 是簇 $C_i$ 的均值向量。直觀來看，式 (1) 在一定程度上刻畫了簇內(nèi)樣本圍繞簇均值向量的緊密程度，$E$ 值越小則簇內(nèi)樣本相似度越高。

1.1.1 最小化成本函數(shù)

最小化式 (1) 并不容易，找到它的最優(yōu)解需考察樣本集 $D$ 所有可能的簇劃分，這是一個 NP 難問題。因此，k均值算法采用了貪心策略，通過迭代優(yōu)化來近似求解式 (2) 。算法流程如下圖所示：

圖1 k 均值算法

其中第 1 行對均值向量進(jìn)行初始化，在第 4-8 行對當(dāng)前簇劃分迭代更新，第 9-16 行對均值向量迭代更新，若迭代更新后均值結(jié)果保持不變，則在第 18 行對當(dāng)前簇劃分結(jié)果返回。

為避免運(yùn)行時間過長，通常設(shè)置一個最大運(yùn)行輪數(shù)（max_iter）或最小調(diào)整幅度閾值（tol），若達(dá)到最大輪數(shù)或調(diào)整幅度小于閾值，則停止運(yùn)行。

1.1.2 實(shí)例

下面對西瓜數(shù)據(jù)集為例演示 k 均值算法的學(xué)習(xí)過程。為方便敘述，我們將變好為 $i$ 的樣本稱為 $x_i$，這是一個包含“密度”與“含糖率”兩個屬性值的二維向量。

表1 西瓜數(shù)據(jù)集

假定聚類簇數(shù)（n_clusters）$k=3$ ，算法開始時隨機(jī)選取三個樣本 $x_6,x_{12},x_{27}$ 作為初始均值向量，即：

$${\mu }_1=(0.403;0.237),{\mu }_2=(0.343;0.0999),{\mu }_3=(0.532;0.472)$$

考察樣本 $x_1=(0.697;0.460)$ ，它與當(dāng)前均值向量 ${\mu }_1,{\mu }_2,{\mu }_3$ 的距離分別為 0.369，0.506，0.166，因此 $x_1$ 將劃入簇 $C_3$ 中。類似的，對數(shù)據(jù)集中的所有樣本考慮一遍后，可得當(dāng)前簇劃分為：

$$\begin{array}{rl}{C}_1& =\{x_5,x_6,x_7,x_8,x_9,x_{10},x_{13},x_{14},x_{15},x_{17},x_{18},x_{19},x_{20},x_{23}\};\\ C_2& =\{x_{11},x_{12},x_{16}\};\\ C_3& =\{x_1,x_2,x_3,x_4,x_{21},x_{22},x_{24},x_{25},x_{26},x_{27},x_{28},x_{29},x_{30};\}\end{array}$$

于是，可從 $C_1、C_2、C_3$ 分別求出新的均值向量：

$${\mathbf{\mu }}_1^{\prime }=(0.473;0.214),{\mathbf{\mu }}_2^{\prime }=(0.394;0.066),{\mathbf{\mu }}_3^{\prime }=(0.623;0.388)$$

更新當(dāng)前均值向量后，不斷重復(fù)上述過程，如下圖所示，第五輪迭代產(chǎn)生的結(jié)果與第四輪迭代相同，于是算法停止，得到最終的簇劃分：^[1]

圖2 k 均值算法 4 輪迭代后的簇劃分

標(biāo)準(zhǔn) KMeans 的聚類結(jié)果受初始均值向量的影響，初始點(diǎn)不同，則聚類結(jié)果就有可能不同，因此可以通過多次隨機(jī)初始化（n_init）聚類中心最終選取最優(yōu)結(jié)果。

1.2 KMeans++

由于 KMeans 算法的分類結(jié)果會收到初始點(diǎn)的選取而有所區(qū)別，因此提出了標(biāo)準(zhǔn) KMeans 的改進(jìn) KMeans++。

其改進(jìn)在于對初始均值向量的選擇，其他步驟同標(biāo)準(zhǔn) KMeans 相同。初始均值向量選取的基本思路是：初始的聚類中心之間的相互距離要盡量遠(yuǎn)。

初始均值向量選取如下：

步驟一：隨機(jī)選取一個樣本作為第一個聚類中心 c1；

步驟二：

• 計(jì)算每個樣本與當(dāng)前已有類聚中心最短距離（即與最近一個聚類中心的距離），用 D(x)表示；

• 接著計(jì)算每個樣本被選為下一個聚類中心的概率:

$$\frac{D(x{)}^2}{{\sum }_{x\in X}D(x{)}^2}\text{\hspace{1em}(2)}$$

這個值越大，表示被選取作為聚類中心的概率較大；

• 最后，用輪盤法選出下一個聚類中心；

步驟三：重復(fù)步驟二，直到選出 k 個聚類中心。^[2]

1.2.1 KMeans++ 初始化實(shí)例

假設(shè)經(jīng)過步驟一后 6 號點(diǎn)被選擇為第一個初始聚類中心，那在進(jìn)行步驟二時每個樣本的 $D(x)$ 和被選擇為第二個聚類中心的概率 $P(x)$ 如下表所示：

表2 第二個聚類中心的選擇

其中的 $P(x)$ 就是每個樣本被選擇為下一個聚類中心的概率。因此 $P(x)$ 可以看作 PDF，Sum 可以看作 CDF，是 $P(x)$ 的累加和，用于輪盤法選擇出第二個聚類中心。

輪盤法方法就是隨機(jī)產(chǎn)生一個 0～1 之間的隨機(jī)數(shù)，判斷隨機(jī)數(shù)屬于 Sum 行的哪個區(qū)間，那么該區(qū)間對應(yīng)的序號就是被選擇出來的第二個聚類中心了。例如 1 號點(diǎn)的區(qū)間為 $[0,0.2)$ ，2 號點(diǎn)的區(qū)間為 $[0.2,0.525)$。

從表中可以直觀的看到第二個初始聚類中心有 90% 的概率落在 1～4 號點(diǎn)。而這 4 個點(diǎn)正好是離第一個聚類中心 6 號點(diǎn)較遠(yuǎn)的四個點(diǎn)。這也驗(yàn)證了 KMeans++ 的思想：即離當(dāng)前已有聚類中心較遠(yuǎn)的點(diǎn)有更大的概率被選為下一個聚類中心。

當(dāng) k 值大于 2 時，每個樣本會有多個距離，需要取最小的那個距離作為 $D(x)$。

重復(fù)步驟 2 直到選出 k 個聚類中心，并利用這 k 個初始聚類中心來運(yùn)行標(biāo)準(zhǔn) KMeans 算法。^[3]

2. 在線可視化 KMeans

這個網(wǎng)站可以通過自己設(shè)定初始值方式以及數(shù)據(jù)分布，來進(jìn)行迭代過程的可視化，有興趣的也可以試試看。

參考資料

[1] 周志華. 機(jī)器學(xué)習(xí)[M]. 北京: 清華大學(xué)出版社, 2016: 202-205.

[2] 寒杰士.[ML] K-means與K-means++[EB/OL].https://www.cnblogs.com/wang2825/articles/8696830.html, 2018-04-02.

[3] 0過把火0.[ML] K-means++[EB/OL].https://www.jianshu.com/p/680dbffad345, 2018-10-19.

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的无监督学习 | KMeans与KMeans++原理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。