聚類算法
Author：Miracle8070
From：AI蝸牛車
1. 寫在前面
如果想從事數據挖掘或者機器學習的工作，掌握常用的機器學習算法是非常有必要的，常見的機器學習算法：
監督學習算法：邏輯回歸，線性回歸，決策樹，樸素貝葉斯，K近鄰，支持向量機，集成算法Adaboost等無監督算法：聚類，降維，關聯規則, PageRank等為了詳細的理解這些原理，曾經看過西瓜書，統計學習方法，機器學習實戰等書，也聽過一些機器學習的課程，但總感覺話語裡比較深奧，讀起來沒有耐心，並且理論到處有，而實戰最重要， 所以在這裡想用最淺顯易懂的語言寫一個白話機器學習算法理論+實戰系列。
個人認為，理解算法背後的idea和使用，要比看懂它的數學推導更加重要。idea會讓你有一個直觀的感受，從而明白算法的合理性，數學推導只是將這種合理性用更加嚴謹的語言表達出來而已，打個比方，一個梨很甜，用數學的語言可以表述為糖分含量90%，但只有親自咬一口，你才能真正感覺到這個梨有多甜，也才能真正理解數學上的90%的糖分究竟是怎麼樣的。如果算法是個梨，本文的首要目的就是先帶領大家咬一口。另外還有下面幾個目的：
能開心的學習這些算法的核心思想， 找到學習這些算法的興趣，為深入的學習這些算法打一個基礎。每一節課的理論都會放一個實戰案例，能夠真正的做到學以致用，既可以鍛鍊編程能力，又可以加深算法理論的把握程度。也想把之前所有的筆記和參考放在一塊，方便以後查看時的方便。學習算法的過程，獲得的不應該只有算法理論，還應該有樂趣和解決實際問題的能力！
今天是白話機器學習算法理論+實戰的第八篇 之KMeans聚類算法， 聽到這個名字，你可別和第七篇K近鄰算法搞混了，K-Means 是一種非監督學習，解決的是聚類問題，這裡的K表示的是聚成K類。而之前的K近鄰算法是監督學習算法，解決的是分類問題，這裡的K表示的是K個鄰居。相差十萬八千裡吧， 一條取經路呢。一定要區分開。這個算法也不是很難，前面說道，K近鄰算法的原理可以用八個大字叫做「近朱者赤，近墨者黑」來總結，這裡我依然放出八個大字：「人以類聚，物以群分」，形容KMeans最好不過了。
通過今天的學習，掌握KMeans算法的工作原理，然後會使用sklearn實現KMeans聚類，最後我們來做一個實戰項目：如何使用KMeans對圖像進行分割？ 下面我們開始吧。
大綱如下：
KMeans聚類的工作原理（結合足球隊等級劃分談一談）20支亞洲足球隊，你能劃分出等級嗎？（KMeans聚類應用）OK， let's go!
2. K-Means的工作原理上面我們說過，K-Means 是一種非監督學習，解決的是聚類問題。K 代表的是 K 類，Means 代表的是中心，你可以理解這個算法的本質是確定 K 類的中心點，當你找到了這些中心點，也就完成了聚類。
那麼這裡有兩個問題：如何確定K類的中心點？如何把其他類劃分到K個類中去？
先別慌， 先和我考慮一個場景，假設我有 20 支亞洲足球隊，想要將它們按照成績劃分成 3 個等級，可以怎樣劃分？
元芳， 你怎麼看？
★對亞洲足球隊的水平，你可能也有自己的判斷。比如一流的亞洲球隊有誰？你可能會說伊朗或韓國。二流的亞洲球隊呢？你可能說是中國。三流的亞洲球隊呢？你可能會說越南。
」其實這些都是靠我們的經驗來劃分的，那麼伊朗、中國、越南可以說是三個等級的典型代表，也就是我們每個類的中心點。
所以回過頭來，如何確定 K 類的中心點？一開始我們是可以隨機指派的，當你確認了中心點後，就可以按照距離將其他足球隊劃分到不同的類別中。
這也就是 K-Means 的中心思想，就是這麼簡單直接。
你可能會問：如果一開始，選擇一流球隊是中國，二流球隊是伊朗，三流球隊是韓國，中心點選擇錯了怎麼辦？其實不用擔心，K-Means 有自我糾正機制，在不斷的迭代過程中，會糾正中心點。中心點在整個迭代過程中，並不是唯一的，只是你需要一個初始值，一般算法會隨機設置初始的中心點。
那下面就給出K-Means的工作原理，兩步就搞定，就是那兩個問題的解決：
選取 K 個點作為初始的類中心點，這些點一般都是從數據集中隨機抽取的；將每個點分配到最近的類中心點，這樣就形成了 K 個類，然後重新計算每個類的中心點；（這個怎麼算最近，一般是歐幾裡得距離公式， 那麼怎麼重新計算每個類的中心點， 每個維度的平均值就可以的）重複第二步，直到類不發生變化，或者你也可以設置最大迭代次數，這樣即使類中心點發生變化，但是只要達到最大迭代次數就會結束。什麼？還不明白？ 好吧，那直接看看亞洲球隊聚類的例子吧
3. 如何給亞洲球隊做聚類對於機器來說需要數據才能判斷類中心點，所以下面整理了 2015-2019 年亞洲球隊的排名，如下表所示。
我來說明一下數據概況。
其中 2019 年國際足聯的世界排名，2015 年亞洲杯排名均為實際排名。2018 年世界盃中，很多球隊沒有進入到決賽圈，所以只有進入到決賽圈的球隊才有實際的排名。如果是亞洲區預選賽 12 強的球隊，排名會設置為 40。如果沒有進入亞洲區預選賽 12 強，球隊排名會設置為 50。我們怎麼做聚類呢？可以跟著我的思路走了：
首先，針對上面的排名，我們需要做的就是數據規範化，你可以把這些值劃分到[0,1]或者按照均值為 0，方差為 1 的正態分布進行規範化。我先把數值規範化到了[0,1]空間中，得到了下面的數值表：如果我們隨機選取中國、日本、韓國為三個類的中心點，我們就需要看下這些球隊到中心點的距離。
下面就是把其其他樣本根據距離中心點的遠近劃分到這三個類中去，有關距離可以參考KNN那一篇博客。 常用的有歐氏距離，曼哈頓距離等。這裡採用歐式距離。
歐氏距離是最常用的距離計算方式，這裡選擇歐氏距離作為距離的標準，計算每個隊伍分別到中國、日本、韓國的距離，然後根據距離遠近來劃分。我們看到大部分的隊，會和中國隊聚類到一起。這裡我整理了距離的計算過程，比如中國和中國的歐氏距離為 0，中國和日本的歐式距離為 0.732003。如果按照中國、日本、韓國為 3 個分類的中心點，歐氏距離的計算結果如下表所示：然後我們再重新計算這三個類的中心點，如何計算呢？最簡單的方式就是取平均值，然後根據新的中心點按照距離遠近重新分配球隊的分類，再根據球隊的分類更新中心點的位置。計算過程這裡不展開，最後一直迭代（重複上述的計算過程：計算中心點和劃分分類）到分類不再發生變化，可以得到以下的分類結果：所以我們能看出來第一梯隊有日本、韓國、伊朗、沙特、澳洲；第二梯隊有中國、伊拉克、阿聯、烏茲別克斯坦；第三梯隊有卡達、泰國、越南、阿曼、巴林、朝鮮、印尼、敘利亞、約旦、科威特和巴勒斯坦。
這個就是KMeans進行聚類的過程了。簡單點，就是反覆兩個過程：
上面這個也可以使用sklearn中的K-Means進行實戰一下子，作為圖像分割圖像的準備期。
4. KMeans聚類實戰：如何使用KMeans對圖像進行分割？還是老規矩，我們在實戰之前，先看一下如何調用sklearn實現KMeans。
4.1 如何使用sklearn中的KMeans算法sklearn 是 Python 的機器學習工具庫，如果從功能上來劃分，sklearn 可以實現分類、聚類、回歸、降維、模型選擇和預處理等功能。這裡我們使用的是 sklearn 的聚類函數庫，因此需要引用工具包，具體代碼如下：
from sklearn.cluster import KMeans當然 K-Means 只是 sklearn.cluster 中的一個聚類庫，實際上包括 K-Means 在內，sklearn.cluster 一共提供了 9 種聚類方法，比如 Mean-shift，DBSCAN，Spectral clustering（譜聚類）等。這些聚類方法的原理和 K-Means 不同，這裡不做介紹。
我們看下 K-Means 如何創建：
KMeans(n_clusters=8, init='k-means++', n_init=10, max_iter=300, tol=0.0001, precompute_distances='auto', verbose=0, random_state=None, copy_x=True, n_jobs=1, algorithm='auto')這些參數解釋一下：
n_clusters: 即 K 值，一般需要多試一些 K 值來保證更好的聚類效果。你可以隨機設置一些 K 值，然後選擇聚類效果最好的作為最終的 K 值；max_iter：最大迭代次數，如果聚類很難收斂的話，設置最大迭代次數可以讓我們及時得到反饋結果，否則程序運行時間會非常長；n_init：初始化中心點的運算次數，默認是 10。程序是否能快速收斂和中心點的選擇關係非常大，所以在中心點選擇上多花一些時間，來爭取整體時間上的快速收斂還是非常值得的。由於每一次中心點都是隨機生成的，這樣得到的結果就有好有壞，非常不確定，所以要運行 n_init 次, 取其中最好的作為初始的中心點。如果 K 值比較大的時候，你可以適當增大 n_init 這個值；init：即初始值選擇的方式，默認是採用優化過的 k-means++ 方式，你也可以自己指定中心點，或者採用 random 完全隨機的方式。自己設置中心點一般是對於個性化的數據進行設置，很少採用。random 的方式則是完全隨機的方式，一般推薦採用優化過的 k-means++ 方式；algorithm：k-means 的實現算法，有「auto」 「full」「elkan」三種。一般來說建議直接用默認的"auto"。簡單說下這三個取值的區別，如果你選擇"full"採用的是傳統的 K-Means 算法，「auto」會根據數據的特點自動選擇是選擇「full」還是「elkan」。我們一般選擇默認的取值，即「auto」 。在創建好 K-Means 類之後，就可以使用它的方法，最常用的是 fit 和 predict 這個兩個函數。你可以單獨使用 fit 函數和 predict 函數，也可以合併使用 fit_predict 函數。其中 fit(data) 可以對 data 數據進行 k-Means 聚類。predict(data) 可以針對 data 中的每個樣本，計算最近的類。
下面我們先跑一遍20支亞洲球隊的聚類問題：數據集在這下載
# coding: utf-8
from sklearn.cluster import KMeans
from sklearn import preprocessing
import pandas as pd
import numpy as np
# 輸入數據
data = pd.read_csv('data.csv', encoding='gbk')
train_x = data[["2019年國際排名","2018世界盃","2015亞洲杯"]]
df = pd.DataFrame(train_x)
kmeans = KMeans(n_clusters=3)
# 規範化到[0,1]空間
min_max_scaler=preprocessing.MinMaxScaler()
train_x=min_max_scaler.fit_transform(train_x)
# kmeans算法
kmeans.fit(train_x)
predict_y = kmeans.predict(train_x)
# 合併聚類結果，插入到原數據中
result = pd.concat((data,pd.DataFrame(predict_y)),axis=1)
result.rename({0:u'聚類'},axis=1,inplace=True)
print(result)運行結果如下：
國家 2019年國際排名 2018世界盃 2015亞洲杯 聚類
0 中國 73 40 7 2
1 日本 60 15 5 0
2 韓國 61 19 2 0
3 伊朗 34 18 6 0
4 沙特 67 26 10 0
5 伊拉克 91 40 4 2
6 卡達 101 40 13 1
7 阿聯 81 40 6 2
8 烏茲別克斯坦 88 40 8 2
9 泰國 122 40 17 1
10 越南 102 50 17 1
11 阿曼 87 50 12 1
12 巴林 116 50 11 1
13 朝鮮 110 50 14 1
14 印尼 164 50 17 1
15 澳洲 40 30 1 0
16 敘利亞 76 40 17 1
17 約旦 118 50 9 1
18 科威特 160 50 15 1
19 巴勒斯坦 96 50 16 1
4.2 如何用KMeans對圖像進行分割？圖像分割就是利用圖像自身的信息，比如顏色、紋理、形狀等特徵進行劃分，將圖像分割成不同的區域，劃分出來的每個區域就相當於是對圖像中的像素進行了聚類。單個區域內的像素之間的相似度大，不同區域間的像素差異性大。這個特性正好符合聚類的特性，所以你可以把圖像分割看成是將圖像中的信息進行聚類。當然聚類只是分割圖像的一種方式，除了聚類，我們還可以基於圖像顏色的閾值進行分割，或者基於圖像邊緣的信息進行分割等。
將微信開屏封面進行分割。
我們現在用 K-Means 算法對微信頁面進行分割。微信開屏圖如下所示：我們先設定下聚類的流程，聚類的流程和分類差不多，如圖所示：在準備階段裡，我們需要對數據進行加載。因為處理的是圖像信息，我們除了要獲取圖像數據以外，還需要獲取圖像的尺寸和通道數，然後基於圖像中每個通道的數值進行數據規範化。這裡我們需要定義個函數 load_data，來幫我們進行圖像加載和數據規範化。代碼如下：
# 加載圖像，並對數據進行規範化
def load_data(filePath):
# 讀文件
f = open(filePath,'rb')
data = []
# 得到圖像的像素值
img = image.open(f)
# 得到圖像尺寸
width, height = img.size
for x in range(width):
for y in range(height):
# 得到點(x,y)的三個通道值
c1, c2, c3 = img.getpixel((x, y))
data.append([c1, c2, c3])
f.close()
# 採用Min-Max規範化
mm = preprocessing.MinMaxScaler()
data = mm.fit_transform(data)
return np.mat(data), width, height因為 jpg 格式的圖像是三個通道 (R,G,B)，也就是一個像素點具有 3 個特徵值。這裡我們用 c1、c2、c3 來獲取平面坐標點 (x,y) 的三個特徵值，特徵值是在 0-255 之間。
為了加快聚類的收斂，我們需要採用 Min-Max 規範化對數據進行規範化。我們定義的 load_data 函數返回的結果包括了針對 (R,G,B) 三個通道規範化的數據，以及圖像的尺寸信息。在定義好 load_data 函數後，我們直接調用就可以得到相關信息，代碼如下：
# 加載圖像，得到規範化的結果img，以及圖像尺寸
img, width, height = load_data('./weixin.jpg')假設我們想要對圖像分割成 2 部分，在聚類階段，我們可以將聚類數設置為 2，這樣圖像就自動聚成 2 類。代碼如下：
# 用K-Means對圖像進行2聚類
kmeans =KMeans(n_clusters=2)
kmeans.fit(img)
label = kmeans.predict(img)
# 將圖像聚類結果，轉化成圖像尺寸的矩陣
label = label.reshape([width, height])
# 創建個新圖像pic_mark，用來保存圖像聚類的結果，並設置不同的灰度值
pic_mark = image.new("L", (width, height))
for x in range(width):
for y in range(height):
# 根據類別設置圖像灰度, 類別0 灰度值為255， 類別1 灰度值為127
pic_mark.putpixel((x, y), int(256/(label[x][y]+1))-1)
pic_mark.save("weixin_mark.jpg", "JPEG")代碼中有一些參數，下面說一下這些參數的作用和設置方法：
★我們使用了 fit 和 predict 這兩個函數來做數據的訓練擬合和預測，因為傳入的參數是一樣的，我們可以同時進行 fit 和 predict 操作，這樣我們可以直接使用 fit_predict(data) 得到聚類的結果。得到聚類的結果 label 後，實際上是一個一維的向量，我們需要把它轉化成圖像尺寸的矩陣。label 的聚類結果是從 0 開始統計的，當聚類數為 2 的時候，聚類的標識 label=0 或者 1。
」
如果你想對圖像聚類的結果進行可視化，直接看 0 和 1 是看不出來的，還需要將 0 和 1 轉化為灰度值。灰度值一般是在 0-255 的範圍內，我們可以將 label=0 設定為灰度值 255，label=1 設定為灰度值 127。具體方法是用 int(256/(label[x][y]+1))-1。可視化的時候，主要是通過設置圖像的灰度值進行顯示。所以我們把聚類 label=0 的像素點都統一設置灰度值為 255，把聚類 label=1 的像素點都統一設置灰度值為 127。原來圖像的灰度值是在 0-255 之間，現在就只有 2 種顏色（也就是灰度為 255，和灰度 127）。有了這些灰度信息，我們就可以用 image.new 創建一個新的圖像，用 putpixel 函數對新圖像的點進行灰度值的設置，最後用 save 函數保存聚類的灰度圖像。這樣你就可以看到聚類的可視化結果了，如下圖所示：如果我們想要分割成 16 個部分，該如何對不同分類設置不同的顏色值呢？這裡需要用到 skimage 工具包，它是圖像處理工具包。你需要使用 pip install scikit-image 來進行安裝。這段代碼可以將聚類標識矩陣轉化為不同顏色的矩陣：
from skimage import color
# 將聚類標識矩陣轉化為不同顏色的矩陣
label_color = (color.label2rgb(label)*255).astype(np.uint8)
label_color = label_color.transpose(1,0,2)
images = image.fromarray(label_color)
images.save('weixin_mark_color.jpg')代碼中，我使用 skimage 中的 label2rgb 函數來將 label 分類標識轉化為顏色數值，因為我們的顏色值範圍是[0,255]，所以還需要乘以 255 進行轉化，最後再轉化為 np.uint8 類型。unit8 類型代表無符號整數，範圍是 0-255 之間。
得到顏色矩陣後，你可以把它輸出出來，這時你發現輸出的圖像是顛倒的，原因可能是圖像源拍攝的時候本身是倒置的。我們需要設置三維矩陣的轉置，讓第一維和第二維顛倒過來，也就是使用 transpose(1,0,2)，將原來的 (0,1,2）順序轉化為 (1,0,2) 順序，即第一維和第二維互換。
最後我們使用 fromarray 函數，它可以通過矩陣來生成圖片，並使用 save 進行保存。最後得到的分類標識顏色化圖像是這樣的：剛才我們做的是聚類的可視化。如果我們想要看到對應的原圖，可以將每個簇（即每個類別）的點的 RGB 值設置為該簇質心點的 RGB 值，也就是簇內的點的特徵均為質心點的特徵。
我給出了完整的代碼，代碼中，我可以把範圍為 0-255 的數值投射到 1-256 數值之間，方法是對每個數值進行加 1，你可以自己來運行下：
# -*- coding: utf-8 -*-
# 使用K-means對圖像進行聚類，並顯示聚類壓縮後的圖像
import numpy as np
import PIL.Image as image
from sklearn.cluster import KMeans
from sklearn import preprocessing
import matplotlib.image as mpimg
# 加載圖像，並對數據進行規範化
def load_data(filePath):
# 讀文件
f = open(filePath,'rb')
data = []
# 得到圖像的像素值
img = image.open(f)
# 得到圖像尺寸
width, height = img.size
for x in range(width):
for y in range(height):
# 得到點(x,y)的三個通道值
c1, c2, c3 = img.getpixel((x, y))
data.append([(c1+1)/256.0, (c2+1)/256.0, (c3+1)/256.0])
f.close()
return np.mat(data), width, height
# 加載圖像，得到規範化的結果imgData，以及圖像尺寸
img, width, height = load_data('./weixin.jpg')
# 用K-Means對圖像進行16聚類
kmeans =KMeans(n_clusters=16)
label = kmeans.fit_predict(img)
# 將圖像聚類結果，轉化成圖像尺寸的矩陣
label = label.reshape([width, height])
# 創建個新圖像img，用來保存圖像聚類壓縮後的結果
img=image.new('RGB', (width, height))
for x in range(width):
for y in range(height):
c1 = kmeans.cluster_centers_[label[x, y], 0]
c2 = kmeans.cluster_centers_[label[x, y], 1]
c3 = kmeans.cluster_centers_[label[x, y], 2]
img.putpixel((x, y), (int(c1*256)-1, int(c2*256)-1, int(c3*256)-1))
img.save('weixin_new.jpg')結果如下：你可以看到我沒有用到 sklearn 自帶的 MinMaxScaler，而是自己寫了 Min-Max 規範化的公式。這樣做的原因是我們知道 RGB 每個通道的數值在[0,255]之間，所以我們可以用每個通道的數值 +1/256，這樣數值就會在[0,1]之間。
對圖像做了 Min-Max 空間變換之後，還可以對其進行反變換，還原出對應原圖的通道值。對於點 (x,y)，我們找到它們所屬的簇 label[x,y]，然後得到這個簇的質心特徵，用 c1,c2,c3 表示：
c1 = kmeans.cluster_centers_[label[x, y], 0]
c2 = kmeans.cluster_centers_[label[x, y], 1]
c3 = kmeans.cluster_centers_[label[x, y], 2]因為 c1, c2, c3 對應的是數據規範化的數值，因此我們還需要進行反變換，即：
c1=int(c1*256)-1
c2=int(c2*256)-1
c3=int(c3*256)-1然後用 img.putpixel 設置點 (x,y) 反變換後得到的特徵值。最後用 img.save 保存圖像。
5. 總結好了，寫到這關於KMeans，就要結束了。下面快速的回顧一下：
首先，通過足球隊聚類的例子引出了KMeans聚類的工作原理，簡單來說兩步，你可以回憶回憶。
然後，通過KMeans實現了對圖像分割的實戰，另外我們還學習了如何在 Python 中如何對圖像進行讀寫，具體的代碼如下，上文中也有相應代碼，你也可以自己對應下：
import PIL.Image as image
# 得到圖像的像素值
img = image.open(f)
# 得到圖像尺寸
width, height = img.size這裡會使用 PIL 這個工具包，它的英文全稱叫 Python Imaging Library，顧名思義，它是 Python 圖像處理標準庫。同時我們也使用到了 skimage 工具包（scikit-image），它也是圖像處理工具包。用過 Matlab 的同學知道，Matlab 處理起圖像來非常方便。skimage 可以和它相媲美，集成了很多圖像處理函數，其中對不同分類標識顯示不同的顏色。在 Python 中圖像處理工具包，我們用的是 skimage 工具包。
好了，KMeans的故事就到這裡吧。