一、算法公式講解

對(duì)于
n代表了x有n維，x上標(biāo)j表示第j維的特征，下標(biāo)i表示該向量是第i個(gè)樣本

簇中心坐標(biāo)為：（當(dāng)然，這也是重新計(jì)算簇中心坐標(biāo)的方法！?。?br> 向量$u_i=(u_i^{(1)},u_i^{(2)},???,u_i^{(j)},???,u_i^{(n)})$，然后標(biāo)量

其中一個(gè)維度,這里比如說(shuō)是第2個(gè)樣本的第1維特征$u_2^1$,我就到這個(gè)第二個(gè)簇里面把這個(gè)簇所有點(diǎn)第一特征求和得到sum，然后把總和sum除以這個(gè)簇的大小|$C_2$|(這個(gè)簇里面點(diǎn)的個(gè)數(shù))，然后就得到第2簇的簇中心的第1維的特征（坐標(biāo)）
比如第一簇的簇中心坐標(biāo)：

則

二、算法流程

K-means算法首先隨機(jī)分布簇中心，然后計(jì)算簇中心并重新分簇為一個(gè)周期進(jìn)行迭代，直到簇穩(wěn)定為止，

三、算法實(shí)現(xiàn)代碼

有Kmeans.py和kmeansSamples.txt兩個(gè)文件，kmeansSamples.txt記錄的是所有點(diǎn)的坐標(biāo)，Kmeans.py描述算法實(shí)現(xiàn)
Kmeans.py文件如下

# -*- coding: utf-8 -*-


import numpy as np
import matplotlib.pyplot as plt

def L2(vecXi, vecXj):
    '''
    計(jì)算歐氏距離
    para vecXi：點(diǎn)坐標(biāo)，向量
    para vecXj：點(diǎn)坐標(biāo)，向量
    retrurn: 兩點(diǎn)之間的歐氏距離
    '''
    return np.sqrt(np.sum(np.power(vecXi - vecXj, 2)))

def kMeans(S, k, distMeas=L2):
    '''
    K均值聚類
    para S：樣本集，多維數(shù)組
    para k：簇個(gè)數(shù)
    para distMeas：距離度量函數(shù)，默認(rèn)為歐氏距離計(jì)算函數(shù)
    return sampleTag：一維數(shù)組，存儲(chǔ)樣本對(duì)應(yīng)的簇標(biāo)記
    return clusterCents：一維數(shù)組，各簇中心
    retrun SSE:誤差平方和
    '''
    print('k = ' , k)
    m = np.shape(S)[0] # 樣本總數(shù)
    sampleTag = np.zeros(m)
    print('sampleTag.shape=',sampleTag)
    # 隨機(jī)產(chǎn)生k個(gè)初始簇中心
    n = np.shape(S)[1] # 樣本向量的特征數(shù)
    print('n = ' , n)
    clusterCents = np.mat([[-1.93964824,2.33260803],[7.79822795,6.72621783],[10.64183154,0.20088133]])
    #clusterCents = np.mat(np.zeros((k,n)))
    #for j in range(n):
    #    minJ = min(S[:,j]) 
    #    rangeJ = float(max(S[:,j]) - minJ)
    #    clusterCents[:,j] = np.mat(minJ + rangeJ * np.random.rand(k,1))
        
    sampleTagChanged = True
    SSE = 0.0
    while sampleTagChanged: # 如果沒有點(diǎn)發(fā)生分配結(jié)果改變，則結(jié)束
        sampleTagChanged = False
        SSE = 0.0
        
        # 計(jì)算每個(gè)樣本點(diǎn)到各簇中心的距離
        # m是樣本總數(shù)
        for i in range(m):
            minD = np.inf
            minIndex = -1
            # k是簇中心個(gè)數(shù)
            for j in range(k):
                # S樣本集，clusterCents樣本中心點(diǎn)
                d = distMeas(clusterCents[j,:],S[i,:])
                if d < minD:
                    minD = d
                    minIndex = j
            if sampleTag[i] != minIndex: 
                sampleTagChanged = True
            sampleTag[i] = minIndex
            SSE += minD**2
        print(clusterCents)
        plt.scatter(clusterCents[:,0].tolist(),clusterCents[:,1].tolist(),c='r',marker='^',linewidths=7)
        plt.scatter(S[:,0],S[:,1],c=sampleTag,linewidths=np.power(sampleTag+0.5, 2))
        plt.show()
        print(SSE)
        
        # 重新計(jì)算簇中心
        for i in range(k):
            ClustI = S[np.nonzero(sampleTag[:]==i)[0]]
            clusterCents[i,:] = np.mean(ClustI, axis=0)
    return clusterCents, sampleTag, SSE

if __name__=='__main__':
    samples = np.loadtxt("kmeansSamples.txt")
    clusterCents, sampleTag, SSE = kMeans(samples, 3)
    #plt.scatter(clusterCents[:,0].tolist(),clusterCents[:,1].tolist(),c='r',marker='^')
    #plt.scatter(samples[:,0],samples[:,1],c=sampleTag,linewidths=np.power(sampleTag+0.5, 2))
    plt.show()
    print(clusterCents)
    print(SSE)

kmeansSamples.txt文件如下

8.764743691132109049e+00 1.497536962729086341e+01
4.545778445909218313e+00 7.394332431706460262e+00
5.661841772908352333e+00 1.045327224311696668e+01
6.020055532521467967e+00 1.860759073162559929e+01
1.256729723000295529e+01 5.506569916803323750e+00
4.186942275051188211e+00 1.402615035721461290e+01
5.726706075832996845e+00 8.375613974148174989e+00
4.099899279500291094e+00 1.444273323355928795e+01
2.257178930021525254e+00 1.977895587652345855e+00
4.669135451288612515e+00 7.717803834787531070e-01
8.121947597697801058e+00 7.976212807755792555e-01
7.972277764807800260e-02 -1.938666197338206221e+00
8.370047062442882435e+00 1.077781799178707622e+01
6.680973199869320922e+00 1.553118858170866545e+01
5.991946943553537963e+00 1.657732863976965021e+01
5.641990155271871643e+00 1.554671013661827672e+01
-2.925147643580102041e+00 1.108844569740028163e+01
4.996949605297930752e+00 1.986732057663068707e+00
3.866584099986317025e+00 -1.752825909916766900e+00
2.626427441224858939e+00 2.208897582166075324e+01
5.656225833870900388e+00 1.477736974879376675e+01
-3.388227926726261607e-01 5.569311423852095544e+00
1.093574481611491223e+01 1.124487205516641275e+01
4.650235760178413003e+00 1.278869502885029341e+01
8.498485127403823114e+00 9.787697108749913610e+00
7.530467091751554598e+00 8.502325665434069535e+00
6.171183705302398792e+00 2.174394049079376856e+01
-9.333949569013078040e-01 1.594142490265068712e+00
-6.377004909329702542e+00 3.463894089865578341e+00
7.135980906743346175e+00 1.417794597480970609e+01

四、代碼結(jié)果分析

第一次迭代，簇中心分布不太合理（紅色三角形代表簇中心）

第二次迭代，簇中心重新計(jì)算，因此簇中心分布比第一次更合理

第3次迭代

第四次迭代

五、K-Means庫(kù)函數(shù)

KMeans(n_clusters=8, *, init=‘k-means++’, n_init=‘k-means++’, n_init=10,max_iter=300, tol=0.0001, verbose=0, random_state=None, copy_x=True, algorithm=‘a(chǎn)uto’)
鏈接??：??Sklearn關(guān)于K-Means的API介紹
相關(guān)輸人參數(shù)和返回值，在網(wǎng)站上有詳細(xì)介紹，建議 直接看原版文檔，這里僅介紹幾個(gè)重要參數(shù)，其他內(nèi)容不再贅述。

• init 參數(shù)提供了三種產(chǎn)生筷中心的方法：“K-means++”指定產(chǎn)生較大間距的筷中心(2.1.4節(jié))；“random”指定隨機(jī)產(chǎn)生簇中心；由用戶通過(guò)一個(gè)ndarrav 數(shù)組指定初始筷中心。
• n_init 參數(shù)指定了算法運(yùn)行次數(shù)，它在不指定初始筷中心時(shí)，通過(guò)多次運(yùn)行算法，最終選擇最好的結(jié)果作為輸出。
• max iter 參數(shù)指定了一次運(yùn)行中的最大迭代次數(shù)。在大規(guī)模數(shù)據(jù)集中，算法往往要耗費(fèi)大量的時(shí)間，可通過(guò)指定迭代次數(shù)來(lái)折中耗時(shí)和效果。
• tol 參數(shù)指定了算法收斂的國(guó)值。在大規(guī)模數(shù)據(jù)集中，算法往往難以完全收斂，即達(dá)到連續(xù)兩次相同的分筷需要耗費(fèi)很長(zhǎng)時(shí)間,可通過(guò)指定國(guó)值來(lái)折中耗時(shí)和最優(yōu)目標(biāo)。
• algorithm 參數(shù)指定了是否采用elkan k-means 算法來(lái)簡(jiǎn)化距離計(jì)算。該算法比經(jīng)典的k-means 算法在迭代速度方面有很大的提高。但該算法不適用于稀疏的樣本數(shù)據(jù)。值“full”指定采用經(jīng)典k-means 算法。值“ellkan”指定采用 elkan k-means 算法。值“auto”自動(dòng)選擇，在稠密數(shù)據(jù)時(shí)采用 elkan k-means 算法，在稀疏數(shù)據(jù)時(shí)采用經(jīng)典k-means 算法。

六、K-Means算法時(shí)間復(fù)雜度

設(shè)樣本總數(shù)為 m，分簇?cái)?shù)為k。一次迭代過(guò)程中，以樣本與簇中心的距離計(jì)算為基本運(yùn)算,需要$m\times k$。如果迭代次數(shù)為t（，則算法的時(shí)間復(fù)雜度是 O($m\times k\times t$)。
算法運(yùn)行不需要增長(zhǎng)額外輔助空問(wèn)，以樣本和簇中心存儲(chǔ)空間為基本空間,空間復(fù)雜度是0（$m+k$）。
由于m,k,t可認(rèn)為是常量,因此算法的時(shí)間復(fù)雜度和空間復(fù)雜度都可認(rèn)為是線性的$O(N)$ .文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-719139.html

到了這里，關(guān)于K-Means聚類算法及其python實(shí)現(xiàn)（已附上代碼至本博客）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！