作者：張江 | 來源：ATYUN

在本文中，我們將討論K-Means算法，它是一種基於聚類的無監督機器學習算法。此外，我們還將討論如何使用K-Means來壓縮圖像。

在深入研究K-Means算法的細節之前，讓我們先了解一下無監督的機器學習是什麼，以及它的實際應用是什麼。

與有標記數據的監督機器學習不同，，無監督機器學習處理未標記數據的問題。如果你熟悉經典的有監督機器學習，你可能會問，如何從未標記的數據集中學習任何有用的東西？成本函數是否不需要輸出標籤來計算算法的執行方式？

無監督機器學習（更具體地說是K-Means），是通過將相似的數據點聚集在高維空間中來實現的。

在左側，數據點最初是分散的。假設我們不知道每個數據點是如何相關的，但它們不失普遍性。換句話說，僅僅通過查看圖表，我們無法確定某某點是否相似，只是因爲它們彼此靠近（同樣，想象數據點是高維的，即大於3維）。

聚類的作用是，它將彼此更接近的數據點分組到一個聚類中，而不管維度的數量，從而表明屬於單個聚類的數據點屬於特定類。

這個簡單的想法有可能解決我們社會面臨的許多問題：

• 市場細分：根據不同的特徵將潛在客戶的市場劃分或細分的過程。創建的細分市場由消費者組成，消費者將對營銷策略做出類似響應，並且共享諸如類似興趣，需求或位置等特徵。
• 社交網絡分析：分析具有相似品味的社交媒體平臺的用戶的過程。在識別具有相似品味的用戶之後，運行有針對性的廣告變得更容易。
• 天文數據分析：分析未標記的天文數據以找出隱藏模式的過程。

注意：你可能會驚訝地聽到這個事實，但是當今世界中標記數據的數量只是可用數據量的一小部分。因此，這一事實進一步增強了無監督機器學習的優勢。

K-Means算法

1. 選擇K，這是聚類的數量。雖然我們討論的是無監督的機器學習，但算法並不會神奇地將輸入數據集聚集到一定數量的聚類中。我們需要指定我們想要的聚類。基於領域知識，可以輕鬆指定所需的聚類。儘管如此，即使您不熟悉存在多少個聚類，也有一種技術可以確定如何選擇“K”。

2. 從所有可用數據點的集合中，隨機選擇K個數據點並將其稱爲“聚類質心”。

3. 聚類分配。遍歷整個數據集，對於每個數據點x（i），將其分配給它更接近的一個聚類質心。我們如何確定“近距離”？通過計算所述點之間的歐氏距離來做到這一點。現在，我們將形成聚類。我們將c（i）表示爲最接近x（i）的聚類質心的索引。

4. 移動質心。將聚類質心移動到另一個位置，該位置由它們所屬的聚類中的點的平均值（即聚類內所有點的位置的平均值）確定。

5. 連續重複步驟3和4，直到移動質心步驟沒有任何顯著變化。

實施K-Means

我們將使用以下關於汽車的數據集來執行聚類（從Kaggle下載）：

爲了全面瞭解數據集，讓我們查看seaborn配對圖：

運行K-Means的整個代碼庫（以及上面的數據集）在Github存儲庫中，可以作爲IPython筆記本使用：

github.com/adityachandupatla/ml_algorithms/blob/master/k_means/k-means.ipynb

我們在K-Means中用來確定聚類有多好的成本函數稱爲失真成本函數。本質上，它是數據點與分配給它的聚類質心的平均距離。

爲了可視化聚類，請從cars.csv文件的可用列中取出兩列。下面的可視化通過使用“hp”和“mpg”列完成的（但是，你可以自由選擇任意數量的列）：

1. K = 2

2. K = 4

3. K = 8

4. K = 16

在上述圖中，第一個圖顯示了數據集，以及聚類質心的最終位置（表示爲三角形）。下一個圖顯示了結果聚類。我們可以看到，數據集似乎有大約2-4個聚類。爲什麼只有2-4個聚類，爲什麼不是8個或16個聚類？通過查看圖，我們可以很容易看出K=8和K=16是冗餘的，試圖將足夠接近的數據聚在一起。

這種說法似乎很直觀。但是，如果我們的數據集是高維的呢？如果我們無法將其繪製在2D平面上，並想象K-Means中“K”的選擇是對還是錯，該怎麼辦？下一節將討論這一問題。

選擇K-Means中的K

在不依賴於領域知識或可視化的情況下，選擇K的方法是採用elbow method。

我們用不同的 K 值運行K-Means幾次（即首先只有一個聚類質心，然後是兩個，以此類推）。對於每次運行，收集成本函數的輸出並將其繪製在針對K的圖形上。隨着K增加，我們觀察到成本函數J（）也減小了。但過了一段時間後，在K = 3或4以後，K開始慢慢減少。你會得到一個看起來像肘部的圖表：

根據經驗，肘點對應於K的最佳值。

使用K-Means進行圖像壓縮

是時候測試我們對K-Means的知識並將其應用於解決現實生活中的問題了。我們將使用K-Means來執行圖像壓縮。

最左邊的圖像描繪了實際圖像。中間圖像描繪了一個壓縮圖像，但剩下一點點分辨率。最右邊的圖像描繪了高度壓縮和低分辨率的圖像。壓縮已經使用K-Means完成。

考慮你有一個大小爲128 X 128 X 3的圖像。如果你矢量化圖像，你將有一個大小爲16384 X 3的numpy數組。我們可以將這個圖像視爲數字數據的數據點，即我們必須忽略這個事實這個數據代表一個圖像。

更具體地說，你可以將其視爲任何其他大小爲16384 X 3的numpy數組，其中示例的總數爲m = 16384，並且要素的總數爲n = 3。如果我們將K-Means應用於此數據集，通過選擇讓我們說K = 16，我們將選擇16個最重要的數據點（這些數據點只是集羣質心）。

如果我們現在將數組視爲一個圖像，唯一的區別是，我們現在只使用4位（因爲2⁴= 16 = K）來表示圖像顏色。新圖像的總大小爲：128 X 128 X 4 = 65536位。但是，我們仍然需要一些存儲開銷。我們僅使用4位來表示16種顏色。

但是，每種顏色（如果我們假設RGB格式）每個通道需要8位。換句話說，R + G + B = 8 + 8 + 8 = 24位以表示一種顏色。由於我們選擇K = 16，對應16種顏色，我們額外需要24 X 16 = 384位。因此，表示新圖像的總位數：65536 + 384 = 65920位。將其與原始圖像進行比較，原始圖像具有128 X 128像素，每個像素爲24位顏色，結果是128 X 128 X 24 = 393216位。

顯然，我們將圖像壓縮了6倍！結果驚人！

請記住，較高的K值意味着你不會大幅壓縮圖像，也就是說你將保留很多分辨率。但是，如果要選擇較小的K值，則圖像將被高度壓縮，因此分辨率較低。

——————————————