> Photo by Peter Neumann on Unsplash

Python從頭開始的完整K均值聚類演算法：分步指南

另外，如何使用K均值聚類演算法進行影象降維

K聚類是什麼意思？

K均值聚類是最流行和廣泛使用的無監督學習模型。它也稱為群集，因為它透過群集資料來工作。與監督學習模型不同，非監督模型不使用標記資料。

該演算法的目的不是預測任何標籤。而是更好地瞭解資料集並對其進行標記。

在k均值聚類中，我們將資料集聚類為不同的組。

這是k均值聚類演算法的工作原理

1.第一步是隨機初始化一些點。這些點稱為簇質心。

在上圖中，紅色和藍色點是群集質心。

您可以選擇任意數量的群集質心。但是簇質心的數量必須少於資料點的總數。

2.第二步是群集分配步驟。在此步驟中，我們需要遍歷每個綠點。根據點是否更靠近紅色或藍色點，我們需要將其分配給其中一個點。

換句話說，根據綠色點是紅色還是藍色來著色，具體取決於它是靠近藍色簇質心還是紅色簇質心。

3.下一步是移動群集質心。現在，我們必須對分配給紅色聚類質心的所有紅點取平均值，然後將紅色聚類質心移至該平均值。我們需要對藍色簇質心執行相同的操作。

現在，我們有了新的簇質心。我們必須回到編號2（叢集分配步驟）。我們需要將點重新排列到新的群集質心。在那之後重複第三。

數字2和3需要重複幾次，直到兩個聚類質心都位於合適的位置，如下圖所示。

看，我們只是按照分配給它們的簇質心對所有綠色點進行了著色。藍色簇質心位於藍色簇的中心，紅色簇質心位於紅色簇的中心。

開發演算法

我將用於此演算法的資料集是從安德魯·伍（Andrew Ng）在Coursera的機器學習課程中獲得的。這是開發k均值演算法的分步指南：

1.匯入必要的包和資料集

import pandas as pdimport numpy as npdf1 = pd.read_excel('dataset.xlsx', sheet_name='ex7data2_X', header=None)df1.head()

資料集只有兩列。我採用了兩個特色資料集，因為它很容易視覺化。當您看到視覺效果時，該演算法將對您更容易理解。但是，相同的演算法也將適用於多維資料集。

我將DataFrame df1轉換為Numpy陣列，因為我們將在此過程中處理其他陣列：

2.第一步是隨機初始化質心。

我將從資料集中隨機初始化三個點。首先，我將在0和資料集長度之間選擇三個數字。

import randominit_centroids = random.sample(range(0, len(df1)), 3)init_centroids

輸出：

[95, 30, 17]

使用這三個數字作為索引，並獲取這些索引的資料點。

centroids = []for i in init_centroids:    centroids.append(df1.loc[i])centroids

輸出：

[0 3.907793 1 5.094647 Name: 95, dtype: float64, 0 2.660466 1 5.196238 Name: 30, dtype: float64, 0 3.007089 1 4.678978 Name: 17, dtype: float64]

這三點是我們最初的質心。

我將它們轉換為二維陣列。因為這是我比較熟悉的格式。

centroids = np.array(centroids)

輸出：

array([[3.90779317, 5.09464676], [2.66046572, 5.19623848], [3.00708934, 4.67897758]])

3.實施群集分配步驟。

在這一步中，我們將遍歷資料集中的所有資料點。

一個數據點表示一行資料

讓我們看一行資料，瞭解如何將這些資料分配給叢集。

我們將計算所有三個質心的資料距離。然後將該資料點分配給距離最短的質心。

如我們所見，我們必須計算兩個點之間的許多距離。讓我們開發一個計算距離的函式。

def calc_distance(X1, X2):    return(sum((X1 - X2)**2))**0.5

開發一個函式，將每個資料點分配給一個質心。我們的"質心"陣列只有三個值。因此，我們有三個索引：0、1、2。我們將為每個資料點分配這些索引之一。

def findClosestCentroids(ic, X):    assigned_centroid = []    for i in X:        distance=[]        for j in ic:            distance.append(calc_distance(i, j))        assigned_centroid.append(np.argmin(distance))    return assigned_centroid

此功能是將資料點分配給群集的功能。讓我們使用此函式來計算每個資料點的質心：

get_centroids = findClosestCentroids(centroids, X)get_centroids

部分輸出：

[2, 0, 0, 2, 1, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 0,

總輸出很長。因此，我在這裡顯示部分輸出。輸出中的第一個質心為2，這意味著將其分配給質心列表的索引2。

4.最後一步是根據資料點的平均值移動質心

在這一步中，我們將取每個質心的所有資料點的平均值，然後將質心移動到該平均值。

例如，我們將在索引2處找到分配給質心的所有點的平均值，然後將質心2移至平均值。對索引0和1的質心也執行相同的操作。

讓我們定義一個函式來做到這一點：

def calc_centroids(clusters, X):    new_centroids = []    new_df = pd.concat([pd.DataFrame(X), pd.DataFrame(clusters, columns=['cluster'])],                      axis=1)    for c in set(new_df['cluster']):        current_cluster = new_df[new_df['cluster'] == c][new_df.columns[:-1]]        cluster_mean = current_cluster.mean(axis=0)        new_centroids.append(cluster_mean)    return new_centroids

這些都是我們需要開發的所有功能。

對於此問題，我選擇重複此過程10次。我將在每次迭代後繼續繪製質心和資料，以直觀地向您展示其工作方式。

for i in range(10):    get_centroids = findClosestCentroids(centroids, X)    centroids = calc_centroids(get_centroids, X)    #print(centroids)    plt.figure()    plt.scatter(np.array(centroids)[:, 0], np.array(centroids)[:, 1], color='black')    plt.scatter(X[:, 0], X[:, 1], alpha=0.1)    plt.show()

經過五次迭代，將質心設定為其最佳位置。因此，他們此後不再更改職位。

我建議，在嘗試降維之前，請執行上面的所有程式碼以使其學習好。

否則，您可能會感到不知所措！另外，由於我們已經詳細解釋了該演算法，因此我現在將加快執行速度。

降維

我想解釋一下這種演算法的至少一個用例。一種非常有用的用例是降維。

想一想影象。影象中可能有太多不同的畫素。在任何計算機視覺問題中，如果我們可以縮小圖片的尺寸，則裝置讀取該圖片的速度將大大提高！是不是

我們可以使用剛剛開發的演算法來縮小圖片的尺寸。

我將使用青蛙的圖片來說明這一點：

> Image By Author

我將這張照片上傳到了與筆記本相同的資料夾中。讓我們匯入這個：

import cv2im = cv2.imread('frog.png')im

輸出：

array([[[  2,  57,  20],        [  2,  57,  20],        [  2,  57,  21],        ...,        [  0,   5,   3],        [  8,  12,  11],        [ 91,  94,  93]],       [[  2,  56,  20],        [  1,  54,  20],        [  1,  56,  19],        ...,        [  0,   2,   1],        [  7,   9,   8],        [ 91,  92,  91]],       [[  2,  55,  20],        [  2,  53,  19],        [  1,  54,  18],        ...,        [  2,   4,   2],        [  8,  11,   9],        [ 91,  93,  91]],       ...,       [[  6,  76,  27],        [  6,  77,  26],        [  6,  78,  28],        ...,        [  6,  55,  18],        [ 13,  61,  25],        [ 94, 125, 102]],       [[  9,  79,  31],        [ 11,  81,  33],        [ 12,  82,  32],        ...,        [  6,  56,  19],        [ 14,  61,  27],        [ 96, 126, 103]],       [[ 43, 103,  63],        [ 44, 107,  66],        [ 46, 106,  66],        ...,        [ 37,  81,  50],        [ 47,  88,  59],        [118, 145, 126]]], dtype=uint8)

檢查陣列的形狀，

im.sgape

輸出：

(155, 201, 3)

我將整個陣列除以255，以使所有值從0到1。

然後將其重塑為155 * 201 x 3，使其成為二維陣列。因為我們之前開發了二維陣列的所有函式。

im = (im/255).reshape(155*201, 3)

如您在上方所見，有許多不同的畫素值。我們要減少它並僅保留10畫素值。

讓我們初始化10個隨機索引，

random_index = random.sample(range(0, len(im)), 10)

現在，像上一個示例一樣找到質心：

centroids = []for i in random_index:    centroids.append(im[i])centroids = np.array(centroids)

輸出：

array([[0.00392157, 0.21176471, 0.06666667], [0.03529412, 0.2627451 , 0.09803922], [0.29411765, 0.3254902 , 0.26666667], [0.00784314, 0.18431373, 0.05882353], [0.29019608, 0.49411765, 0.28235294], [0.5254902 , 0.61176471, 0.48627451], [0.04313725, 0.23921569, 0.09803922], [0.00392157, 0.23529412, 0.0745098 ], [0.00392157, 0.20392157, 0.04705882], [0.22352941, 0.48235294, 0.40784314]])

現在，我也將" im"轉換為陣列，

im = np.array(im)

資料準備就緒。現在，我們可以繼續進行叢集過程。但是這次，我將不進行視覺化。因為資料不再是二維的。因此，視覺化並不容易。

for i in range(20):    get_centroids = findClosestCentroids(centroids, im)    centroids = calc_centroids(get_centroids, im)

我們現在得到了更新的質心。

centroids

輸出：

[0 0.017726 1 0.227360 2 0.084389 dtype: float64, 0 0.119791 1 0.385882 2 0.247633 dtype: float64, 0 0.155117 1 0.492051 2 0.331497 dtype: float64, 0 0.006217 1 0.048596 2 0.019410 dtype: float64, 0 0.258289 1 0.553290 2 0.406759 dtype: float64, 0 0.728167 1 0.764610 2 0.689944 dtype: float64, 0 0.073519 1 0.318513 2 0.170943 dtype: float64, 0 0.035116 1 0.273665 2 0.114766 dtype: float64, 0 0.010810 1 0.144621 2 0.053192 dtype: float64, 0 0.444197 1 0.617780 2 0.513234 dtype: float64]

這是最後一步。我們只會保留這10點。

如果還列印get_centroids，您將看到叢集分配。

現在，我們要遍歷整個陣列" im"，並將資料更改為其相應的簇質心值。這樣，我們將僅具有這些質心值。

我不想更改原始陣列，而是要製作一個副本並在那裡進行更改。

im_recovered = im.copy()for i in range(len(im)):    im_recovered[i] = centroids[get_centroids[i]]

您還記得，我們在一開始就更改了影象的尺寸，使其成為二維陣列。我們現在需要將其更改為原始形狀。

im_recovered = im_recovered.reshape(155, 201, 3)

在這裡，我將並排繪製原始影象和縮小後的影象，以顯示差異：

im1 = cv2.imread('frog.png')import matplotlib.image as mpimgfig,ax = plt.subplots(1,2)ax[0].imshow(im1)ax[1].imshow(im_recovered)

> Image by Author

看，我們如此大地減小了影象的尺寸。不過，它看起來像只青蛙！但是計算機閱讀起來會快得多！

結論

在本文中，我解釋了k均值聚類的工作原理以及如何從頭開始開發k均值聚類演算法。我還解釋瞭如何使用此演算法來縮小影象尺寸。請嘗試使用其他影象。

這是我在本文中使用的資料集的連結。https://github.com/rashida048/Machine-Learning-With-Python/blob/master/kmean.xlsx

這個是程式碼：https://github.com/rashida048/Machine-Learning-With-Python/blob/master/k_mean_clustering_final.ipynb