機器學習之K-means聚類（一）

資料加載

我們首先加載資料并繪制散點圖。

#plot the data
data = loadmat('ex7data2.mat')['X']
plt.scatter(data[:,0],data[:,1])
plt.show()
           

觀察資料我們可以發現，這個資料集我們大緻可以分為三類，即 k = 3 , k=3, k=3,但存在一個問題就是我們實際應用中我們所面對的資料可能是超高維的，我們無法畫圖去觀察，那時候我們該怎麼辦呢？

其實我也不知道啦，或許我們可以去降維，或是一個個試？

還是留作後續思考吧！

我們接着往下講。

選取初始聚類中心點

采用随機的方法從所有資料點中随機選取K個點作為初始的中心點。

#中心
centroids=np.zeros((n,shape[1]))
for i in range(n):
    centroids[i]=data[np.random.randint(shape[0]),:]
           

這個是我們選擇的初始的三個中心點，注意初始點的選擇是随機的每次可能不同。

根據初始點對資料分類

對于我們的資料集中的每個點，我們選取離這個點最近的中心點作為我們的分類結果。那麼接下來的問題就是我們應該使用什麼距離來判定？

這裡我們選用通常采用的歐氏距離，就是我們通常所了解的距離。

d ( x i , x j ) = ∑ k = 1 n ( x i k − x j k ) 2 d(x_i,x_j)=\sqrt{\sum_{k=1}^{n}(x_{ik}-x_{jk})^2} d(xi​,xj​)=k=1∑n​(xik​−xjk​)2

​

我們假設第 i i i類的中心點位 V i V_i Vi​.

def find_Closest_Centroids(data,centroids,n):
    '''

    :param data: input data
    :param centroids:  the k center
    :return: idx  the classification result
    '''
    shape = np.shape(data)
    idx = np.zeros((n,shape[0]))


    for i in range(shape[0]):
        dis_list = []
        for j in range(np.shape(centroids)[0]):
            distance = np.sqrt(np.sum((data[i]-centroids[j])**2))
            dis_list.append(distance)
        idx[np.argmin(dis_list),i]=1



    return idx
           

更新中心點

初始分類之後我們開始更新中心點的位置。

我們假設第 i i i類共有 m i m_i mi​個資料點即有 m i m_i mi​個資料點屬于第 i i i類。 x i j x_{ij} xij​表示第 i i i類中的第 j j j個樣本。中心點更新公式如下：

V i = ∑ j = 1 m i x i j m i V_i=\frac{\sum_{j=1}^{m_i}x_{ij}}{m_i} Vi​=mi​∑j=1mi​​xij​​

#計算新的中心點
def computeMeans(data,idx,n):
    shape = np.shape(data)
    centroids = np.zeros((n,shape[1]))
    for i in range(n):
        centroids[i]=[0,0]
        i_total = 0
        for j in range(shape[0]):
            if idx[j]==i:
                i_total+=1

        for j in range(shape[0]):
            if idx[j]==i:
                centroids[i]=centroids[i]+data[j]/i_total
    return centroids
           

停止條件（誤差範圍）

我們将分類結果用一個矩陣 U U U來表示， U U U的大小為 k ∗ n k*n k∗n, k k k表示我們要分的類别數目， n n n表示資料總數。若第 i i i組 ( i = 1 , 2 , . . . , n ) (i=1,2,...,n) (i=1,2,...,n)資料屬于第 j j j類 ( j = 1 , 2 , . . . , k ) (j=1,2,...,k) (j=1,2,...,k),則 U j i = 1 U_{ji}=1 Uji​=1否則等于 0 0 0.

第 r r r次疊代的結果為 U r U_r Ur​,第 r + 1 r+1 r+1此的結果為 U r + 1 U_{r+1} Ur+1​,随着疊代次數增加， ∣ ∣ U r − U r + 1 ∣ ∣ 逐 漸 收 斂 于 0 ||U_r-U_{r+1}||逐漸收斂于0 ∣∣Ur​−Ur+1​∣∣逐漸收斂于0，我們設定誤差限度為 ε \varepsilon ε.

當

∣ ∣ U r − U r + 1 ∣ ∣ < ε ||U_r-U_{r+1}||<\varepsilon ∣∣Ur​−Ur+1​∣∣<ε

時，我們推出疊代。

對于這裡的收斂性你可能存在疑問，我們後續會進行推導。

歡迎先關注我呦。

結果

可以發現我們疊代了三次就收斂到0了，是以說效果還是很不錯的。當然這僅僅是對這裡這種成簇的資料，實際應用中需要你對資料做一些處理才能有不錯的效果。

如果你對算法有興趣，或者你想做一些有趣的小程式。那麼歡迎關注我的微信公衆号：