在本系列的前面幾期中，我們介紹了包含決策樹及其相關算法在內的一系列有監督學習算法。本期不妨換換口味，學習一種比較簡單的無監督學習算法：k-means.
k-means 算法理論講解你可能已經聽說過這個算法，沒有也不要緊，它的原理並不複雜，讓我們來看看~
給你一批樣本的數據，就像這樣：
其中不同的id代表不同樣本，共10個樣本。x和y是兩個特徵，每一個樣本都有且只有這兩個特徵。
現在希望你能夠對這些樣本進行分類。
我們知道，在屬於有監督學習的分類問題中，訓練數據往往會包含類別標籤。而上面這份數據本身是不含標籤的，所以這並不是一個分類問題。
既然不知道類別標籤，你又讓我對這些樣本進行分類，那如何聚類？又要聚成幾類呢？
其實，在k-means中，最終聚成幾類是由我們自己決定的；這裡的類別標籤通常用數字表示，如0,1,2等；當我們指定好類別總數後，每一個樣本被歸到哪一類，就需要聚類算法自己去學習了。
k-means算法學習將相似的樣本聚在一起，稱為一個類別(也稱為一個"簇")，而將不相似的樣本劃分到不同的類別("簇")中。
這裡的相似程度，通常是用樣本之間的距離來度量的，比如最常用的歐氏距離。
囉嗦了這麼多，k-means算法的執行步驟可以總結如下：
(1) 對於給定的一批樣本，初始化聚類中心（這裡需要手動指定聚成幾類），初始化每個樣本所屬簇；
(2) 對於每一個樣本，分別計算該樣本與所有聚類中心之間的距離，選擇距離該樣本最近的聚類中心作為該樣本所屬簇；
(3) 經過(2)之後，每個樣本所屬簇就被更新了，現在來更新聚類中心：計算每一個簇內所有樣本在所有特徵維度上的平均值，將其作為該簇新的聚類中心。
(4) 重複(2)、(3)若干次，便完成了聚類。
接下來，我們將根據以上四步，用Python實現k-means算法。
k-means 算法的Python實現我們需要手動指定要聚成幾類，這裡用參數k來表示，比如k=3就代表我們希望聚成3類。
data是訓練數據，毫無疑問也是需要手動傳入的。
另外，我們還設置了一個是否隨機打亂樣本順序的開關：do_shuffle，默認保持樣本原序。
class MyKmeans:
def __init__(self,k,data,do_shuffle=False):
self.k=k#自己指定聚成幾類
self.data=data#訓練數據
self.do_shuffle=do_shuffle#是否隨機打亂樣本順序現在實現(1)，即：初始化聚類中心，初始化每個樣本所屬簇。
這裡，我直接以前k個樣本的坐標分別作為k個初始聚類中心，並將每個樣本的類別標籤(所屬簇)初始化為0。
def initialize(self):
if self.do_shuffle:
np.random.shuffle(self.data)
#初始化聚類中心
self.centers=self.data[:self.k]
#初始化每個樣本所屬簇
self.targets=np.zeros(self.data.shape[0])再看(2)，其中涉及到了求距離，所以先來實現兩個樣本點之間的距離計算方法，這裡採用歐氏距離：
def cal_dist(self,p1,p2):
return np.sqrt(np.sum((p1-p2)**2))然後來實現(2)，即：更新樣本所屬簇
for i,item in enumerate(self.data):#對於每一個樣本點
c=[]#分別計算該樣本點到k個聚類中心的距離，並存入c
for j in range(len(self.centers)):
c.append(self.cal_dist(item,self.centers[j]))
#print(c)
self.targets[i]=np.argmin(c)#更新targets現在來實現(3)，即：更新聚類中心
#更新聚類中心
new_centers=[]
for i in range(self.k):#對於每一個類中的全部樣本點
#此時target的取值集合是0到k-1
#挑選出屬於簇i的全部樣本
i_data=[]
for index,item in enumerate(self.data):
if self.targets[index]==i:
i_data.append(item)
if len(i_data)!=0:
cent=[]#存儲新的聚類中心的每一個維度
for p in range(len(self.data[0])):#對於點的每一個維度
sums=0
#計算第i個簇中，每個維度的新值
for x in i_data:
sums+=x[p]
res=sums/len(i_data)
cent.append(res)
new_centers.append(cent)
else:
new_centers.append(self.centers[i])#若某一個簇中所含樣本數為0，則不更新該簇的中心點
self.centers=new_centers注意這裡需要判斷某個簇中所含樣本個數是否為0，因為當樣本數為0時，上述代碼中求解均值所做的除法會報錯。
為了避免這個錯誤，當出現這種情況時，我們選擇本次不更新該簇的聚類中心。
以上便完成了(2)和(3)，注意到(4)中需要重複(2)和(3)這兩個步驟，因此，我們可以將(2)和(3)封裝到一個方法裡面，就像這樣：
def one_step(self):
for i,item in enumerate(self.data):#對於每一個樣本點
c=[]#分別計算該樣本點到k個聚類中心的距離，並存入c
for j in range(len(self.centers)):
c.append(self.cal_dist(item,self.centers[j]))
#print(c)
self.targets[i]=np.argmin(c)#更新targets
#更新聚類中心
new_centers=[]
for i in range(self.k):#對於每一個類中的全部樣本點
#此時target的取值集合是0到k-1
#挑選出屬於簇i的全部樣本
i_data=[]
for index,item in enumerate(self.data):
if self.targets[index]==i:
i_data.append(item)
if len(i_data)!=0:
cent=[]#存儲新的聚類中心的每一個維度
for p in range(len(self.data[0])):#對於點的每一個維度
sums=0
#計算第i個簇中，每個維度的新值
for x in i_data:
sums+=x[p]
res=sums/len(i_data)
cent.append(res)
new_centers.append(cent)
else:
new_centers.append(self.centers[i])#若某一個簇中所含樣本數為0，則不更新該簇的中心點
self.centers=new_centers有了上面實現的這些方法，第(4)步的實現就很簡單啦，直接來個for循環即可
def run(self,iterations):
self.initialize()#初始化聚類中心和各樣本所屬類別
#經過iterations次迭代，基本就完成了聚類
for it in range(iterations):
#print('iterations',it)
self.one_step()
return self.centers,self.targets到這裡，我們就完成了整個k-means算法，是時候測試一下效果了。
我們的訓練數據是隨機生成的，共100個樣本，每個樣本含2個特徵。
import matplotlib.pyplot as plt
import numpy as np
if __name__ == '__main__':
datasets=np.random.randint(0,100,size=(100,2))
k=4#聚類數
iterations=100#總迭代次數
mykmeans=MyKmeans(k,datasets,True)#實例化
centers,targets=mykmeans.run(iterations)#迭代求解
#可視化聚類結果
plt.scatter(datasets[:,0],datasets[:,1],c=targets)
for center in centers:
plt.scatter(center[0],center[1],marker='*',s=300)
plt.text(center[0], center[1], (round(center[0],2),round(center[1],2)), fontsize=10, color = "r")
plt.show()聚類結果如下圖所示
現將完整的k-means實現代碼匯總如下：
import numpy as np
class MyKmeans:
def __init__(self,k,data,do_shuffle=False):
self.k=k
self.data=data
self.do_shuffle=do_shuffle
#計算歐氏距離
def cal_dist(self,p1,p2):
return np.sqrt(np.sum((p1-p2)**2))
#初始化聚類中心和每個樣本所屬類別
def initialize(self):
if self.do_shuffle:
np.random.shuffle(self.data)
#初始化聚類中心
self.centers=self.data[:self.k]
#初始化每個樣本所屬簇
self.targets=np.zeros(self.data.shape[0])
def one_step(self):
for i,item in enumerate(self.data):#對於每一個樣本點
c=[]#分別計算該樣本點到k個聚類中心的距離，並存入c
for j in range(len(self.centers)):
c.append(self.cal_dist(item,self.centers[j]))
#print(c)
self.targets[i]=np.argmin(c)#更新targets
#更新聚類中心
new_centers=[]
for i in range(self.k):#對於每一個類中的全部樣本點
#此時target的取值集合是0到k-1
#挑選出屬於簇i的全部樣本
i_data=[]
for index,item in enumerate(self.data):
if self.targets[index]==i:
i_data.append(item)
if len(i_data)!=0:
cent=[]#存儲新的聚類中心的每一個維度
for p in range(len(self.data[0])):#對於點的每一個維度
sums=0
#計算第i個簇中，每個維度的新值
for x in i_data:
sums+=x[p]
res=sums/len(i_data)
cent.append(res)
new_centers.append(cent)
else:
new_centers.append(self.centers[i])#若某一個簇中所含樣本數為0，則不更新該簇的中心點
self.centers=new_centers
def run(self,iterations):
self.initialize()#初始化聚類中心和各樣本所屬類別
#經過iterations次迭代，基本就完成了聚類
for it in range(iterations):
#print('iterations',it)
self.one_step()
return self.centers,self.targets
長按即可關注我們
原創不易，感謝你的每一次點讚與分享！