摘要

Kmeans算法中，K值所決定的是在該聚類算法中，所要分配聚類的簇的多少。Kmeans算法對(duì)初始值是?較敏感的，對(duì)于同樣的k值，選取的點(diǎn)不同，會(huì)影響算法的聚類效果和迭代的次數(shù)。本文通過計(jì)算原始數(shù)據(jù)中的：手肘法、輪廓系數(shù)、CH值和DB值，四種指標(biāo)來(lái)衡量K-means的最佳聚類數(shù)目，并使用K-means進(jìn)行聚類，最后可視化聚類的結(jié)果。
一篇文章教會(huì)你如何使用matlab進(jìn)行K-means聚類，以及如何確定最優(yōu)k值，不要再去看那些付費(fèi)文章了。

1. K-means算法

1.1 聚類算法簡(jiǎn)介

對(duì)于"監(jiān)督學(xué)習(xí)"(supervised learning)，其訓(xùn)練樣本是帶有標(biāo)記信息的，并且監(jiān)督學(xué)習(xí)的目的是：對(duì)帶有標(biāo)記的數(shù)據(jù)集進(jìn)行模型學(xué)習(xí)，從而便于對(duì)新的樣本進(jìn)行分類。而在“無(wú)監(jiān)督學(xué)習(xí)”(unsupervised learning)中，訓(xùn)練樣本的標(biāo)記信息是未知的，目標(biāo)是通過對(duì)無(wú)標(biāo)記訓(xùn)練樣本的學(xué)習(xí)來(lái)揭示數(shù)據(jù)的內(nèi)在性質(zhì)及規(guī)律，為進(jìn)一步的數(shù)據(jù)分析提供基礎(chǔ)。對(duì)于無(wú)監(jiān)督學(xué)習(xí)，應(yīng)用最廣的便是"聚類"(clustering)。

"聚類算法"試圖將數(shù)據(jù)集中的樣本劃分為若干個(gè)通常是不相交的子集，每個(gè)子集稱為一個(gè)“簇”(cluster)，通過這樣的劃分，每個(gè)簇可能對(duì)應(yīng)于一些潛在的概念或類別。

1.2 K-means聚類算法

kmeans算法又名k均值算法,K-means算法中的k表示的是聚類為k個(gè)簇，means代表取每一個(gè)聚類中數(shù)據(jù)值的均值作為該簇的中心，或者稱為質(zhì)心，即用每一個(gè)的類的質(zhì)心對(duì)該簇進(jìn)行描述。

其算法思想大致為：先從樣本集中隨機(jī)選取 k個(gè)樣本作為簇中心，并計(jì)算所有樣本與這 k個(gè)“簇中心”的距離，對(duì)于每一個(gè)樣本，將其劃分到與其距離最近的“簇中心”所在的簇中，對(duì)于新的簇計(jì)算各個(gè)簇的新的“簇中心”。

根據(jù)以上描述，我們大致可以猜測(cè)到實(shí)現(xiàn)kmeans算法的主要四點(diǎn)：
?? （1）簇個(gè)數(shù) k 的選擇
?? （2）各個(gè)樣本點(diǎn)到“簇中心”的距離
?? （3）根據(jù)新劃分的簇，更新“簇中心”
?? （4）重復(fù)上述2、3過程，直至"簇中心"沒有移動(dòng)。

1.3 代碼實(shí)現(xiàn)

注意：需要先通過下文2部分確定k值

import random
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt

# 計(jì)算歐式距離
def calcDis(dataSet, centroids, k):
    clalist=[]
    for data in dataSet:
        diff = np.tile(data, (k, 1)) - centroids  #相減   (np.tile(a,(2,1))就是把a(bǔ)先沿x軸復(fù)制1倍，即沒有復(fù)制，仍然是 [0,1,2]。 再把結(jié)果沿y方向復(fù)制2倍得到array([[0,1,2],[0,1,2]]))
        squaredDiff = diff ** 2     #平方
        squaredDist = np.sum(squaredDiff, axis=1)   #和  (axis=1表示行)
        distance = squaredDist ** 0.5  #開根號(hào)
        clalist.append(distance) 
    clalist = np.array(clalist)  #返回一個(gè)每個(gè)點(diǎn)到質(zhì)點(diǎn)的距離len(dateSet)*k的數(shù)組
    return clalist

# 計(jì)算質(zhì)心
def classify(dataSet, centroids, k):
    # 計(jì)算樣本到質(zhì)心的距離
    clalist = calcDis(dataSet, centroids, k)
    # 分組并計(jì)算新的質(zhì)心
    minDistIndices = np.argmin(clalist, axis=1)    #axis=1 表示求出每行的最小值的下標(biāo)
    newCentroids = pd.DataFrame(dataSet).groupby(minDistIndices).mean() #DataFramte(dataSet)對(duì)DataSet分組，groupby(min)按照min進(jìn)行統(tǒng)計(jì)分類，mean()對(duì)分類結(jié)果求均值
    newCentroids = newCentroids.values
 
    # 計(jì)算變化量
    changed = newCentroids - centroids
 
    return changed, newCentroids

# 使用k-means分類
def kmeans(dataSet, k):
    # 隨機(jī)取質(zhì)心
    centroids = random.sample(dataSet, k)
    
    # 更新質(zhì)心 直到變化量全為0
    changed, newCentroids = classify(dataSet, centroids, k)
    while np.any(changed != 0):
        changed, newCentroids = classify(dataSet, newCentroids, k)
 
    centroids = sorted(newCentroids.tolist())   #tolist()將矩陣轉(zhuǎn)換成列表 sorted()排序
 
    # 根據(jù)質(zhì)心計(jì)算每個(gè)集群
    cluster = []
    clalist = calcDis(dataSet, centroids, k) #調(diào)用歐拉距離
    minDistIndices = np.argmin(clalist, axis=1)  
    for i in range(k):
        cluster.append([])
    for i, j in enumerate(minDistIndices):   #enymerate()可同時(shí)遍歷索引和遍歷元素
        cluster[j].append(dataSet[i])
        
    return centroids, cluster
 
# 創(chuàng)建數(shù)據(jù)集
def createDataSet():
    return [[1, 1], [1, 2], [2, 1], [6, 4], [6, 3], [5, 4]]

if __name__=='__main__': 
    dataset = createDataSet()
    centroids, cluster = kmeans(dataset, 2)
    print('質(zhì)心為：%s' % centroids)
    print('集群為：%s' % cluster)
    for i in range(len(dataset)):
      plt.scatter(dataset[i][0],dataset[i][1], marker = 'o',color = 'green', s = 40 ,label = '原始點(diǎn)')
                                                    #  記號(hào)形狀       顏色      點(diǎn)的大小      設(shè)置標(biāo)簽
      for j in range(len(centroids)):
        plt.scatter(centroids[j][0],centroids[j][1],marker='x',color='red',s=50,label='質(zhì)心')
        plt.show()

2. 最優(yōu)聚類數(shù)目K的確定

2.1 手肘法–Elbow（經(jīng)驗(yàn)方法）

我們知道k-means是以最小化樣本與質(zhì)點(diǎn)平方誤差作為目標(biāo)函數(shù)，將每個(gè)簇的質(zhì)點(diǎn)與簇內(nèi)樣本點(diǎn)的平方距離誤差和稱為畸變程度(distortions)，那么，對(duì)于一個(gè)簇，它的畸變程度越低，代表簇內(nèi)成員越緊密，畸變程度越高，代表簇內(nèi)結(jié)構(gòu)越松散。 畸變程度會(huì)隨著類別的增加而降低，但對(duì)于有一定區(qū)分度的數(shù)據(jù)，在達(dá)到某個(gè)臨界點(diǎn)時(shí)畸變程度會(huì)得到極大改善，之后緩慢下降，這個(gè)臨界點(diǎn)就可以考慮為聚類性能較好的點(diǎn)。

# 導(dǎo)包
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from scipy.spatial.distance import cdist
from sklearn.cluster import KMeans

# 1.利用pandas讀入數(shù)據(jù)
data = pd.read_csv(data_path, header=None) # data_path換成你的需要聚類的數(shù)據(jù)所在路徑，我的數(shù)據(jù)沒有表頭，所以設(shè)置header=None
x = data[0: 150] # 設(shè)置需要聚類的數(shù)據(jù)列數(shù)，我的是150維

# 2.繪制手肘圖
dispersions = []
for k in range(1, 20): # k:需要聚幾類，按需修改，推薦至少10類
    kmeans = KMeans(n_clusters=k, random_state=9)
    y_pred = kmeans.fit_predict(x)
    dispersions.append(sum(np.min(cdist(x, kmeans.cluster_centers_, 'euclidean'), axis=1))/x.shape[0])
print(dispersions)

plt.plot(range(1, 20), dispersions, 'bx-')
plt.xlabel('Number of Clusters (k)')
plt.ylabel('Average Dispersion')
plt.title('the Elbow Method')
plt.show()

我的數(shù)據(jù)比較差，暫且認(rèn)為在聚5類之前走勢(shì)變換程度較大，聚5類以后走勢(shì)變得平緩，所以如果按照手肘法，我的k值確定為5。
注意：手肘法通過人眼觀察肘部圖的走向來(lái)確定肘部位置進(jìn)而來(lái)確定k值，主觀因素很大，不推薦在寫論文時(shí)使用，解釋不清，以免審稿人刁難。

2.2 Silhouette Coefficient（輪廓系數(shù)，理論方法）

對(duì)于一個(gè)聚類任務(wù)，我們希望得到的類別簇中，簇內(nèi)盡量緊密，簇間盡量遠(yuǎn)離，輪廓系數(shù)便是類的密集與分散程度的評(píng)價(jià)指標(biāo)，公式表達(dá)為s=(b?a)/max(a,b)，其中a簇樣本到彼此間距離的均值，b代表樣本到除自身所在簇外的最近簇的樣本的均值，s取值在[-1, 1]之間，越接近1表示聚類效果越好

import pandas as pd
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score


data = pd.read_csv(data_path, header=None)
x = data[0: 150]

silhouette_scores = []
for k in range(2, 10):
    y_pred = KMeans(n_clusters=k, random_state=9).fit_predict(x)
    silhouette_scores.append(silhouette_score(x, y_pred))
print(silhouette_scores)

plt.plot(range(2, 10), silhouette_scores, 'bx-')
plt.xlabel('Number of Clusters (k)')
plt.ylabel('silhouette')
plt.title('the Silhouette Method')
plt.show()

2.3 Calinski-Harabasz Criterion（卡林斯基-哈拉巴斯指標(biāo)，CH值，理論方法）

定義就不多說了，直接上代碼文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-446186.html

import pandas as pd
import matplotlib.pyplot as plt
from sklearn import metrics
from sklearn.cluster import KMeans


data = pd.read_csv(data_path, header=None)
x = data[0: 520]

scores = []
for k in range(2, 20):
    y_pred = KMeans(n_clusters=k, random_state=9).fit_predict(x)
    score = metrics.calinski_harabasz_score(x, y_pred)
    scores.append(score)

print(scores)
plt.plot(range(2, 20), scores, 'bx-')
plt.xlabel('k')
plt.ylabel('the Calinski Carabasz Score')
plt.title('the CH Method')
plt.show()

2.4 Davies-Bouldin Criterion（戴維斯-博爾丁指標(biāo)，DB值，理論方法）

import pandas as pd
import matplotlib.pyplot as plt
from sklearn import metrics
from sklearn.cluster import KMeans


data = pd.read_csv(data_path, header=None)
x = data[0: 520]

scores = []
for k in range(2, 20):
    y_pred = KMeans(n_clusters=k, random_state=9).fit_predict(x)
    score = metrics.davies_bouldin_score(x, y_pred)
    scores.append(score)

print(scores)
plt.plot(range(2, 20), scores, 'bx-')
plt.xlabel('k')
plt.ylabel('the Davies Bouldin Score')
plt.title('the DB Method')
plt.show()

到了這里，關(guān)于（python實(shí)現(xiàn)）一篇文章教會(huì)你k-means聚類算法（包括最優(yōu)聚類數(shù)目k的確定）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！