本文的代碼與數(shù)據(jù)地址已上傳至github：https://github.com/helloWorldchn/MachineLearning
一、K-means算法基本思想
1、基于劃分的聚類
劃分算法的思想是，將給定待挖掘數(shù)據(jù)集中的數(shù)據(jù)對象劃分成K組（k≤N，N代表數(shù)據(jù)集中對象數(shù)目），每一組表示一個(gè)聚類的簇。并且要滿足任何一個(gè)數(shù)據(jù)對象僅可以屬于一個(gè)聚類，每個(gè)聚類中至少具有一個(gè)數(shù)據(jù)對象。
此算法通常要求算法開始之前，給定參數(shù)K以決定聚類后的聚類的個(gè)數(shù)。算法根據(jù)參數(shù)k建立一個(gè)初始的分組，以后算法反復(fù)運(yùn)用迭代重定位技術(shù)將數(shù)據(jù)對象在各個(gè)簇中重新分配，進(jìn)而得到最終的相對滿意的聚類結(jié)果。簇內(nèi)部數(shù)據(jù)對象之間差距盡量小，簇之間數(shù)據(jù)對象差距盡量大才稱得上是一個(gè)好的聚類分析算法。K-medoids和K-means算法是劃分算法中兩個(gè)比較經(jīng)典的算法。其他很多劃分算法都是從這兩個(gè)算法演變改進(jìn)而來的。
2、K-means簡介
1957 年 Lloyd首次在文獻(xiàn)中提出 k-均值算法，1967 年 MacQueen 在文獻(xiàn)中給出了經(jīng)典的 k-均值算法，描述 k-均值算法的完整理論并進(jìn)行了詳細(xì)的研究。 作為最經(jīng)典的劃分聚類算法，k-均值算法的實(shí)現(xiàn)并不復(fù)雜，具有較高的可伸縮性，同時(shí) k-均值算法具有良好的可靠性和高效性，是一種廣泛應(yīng)用的聚類算法。
3、K-means算法流程
K-means（K均值）算法接受一個(gè)參數(shù)K用以決定結(jié)果中簇的數(shù)目。算法開始時(shí)，要在數(shù)據(jù)集中隨機(jī)選擇K個(gè)數(shù)據(jù)對象用來當(dāng)做k個(gè)簇的初始中心，而將剩下的各個(gè)數(shù)據(jù)對象就根據(jù)他們和每個(gè)聚類簇心的距離選擇簇心最近的簇分配到其中。然后重新計(jì)算各個(gè)聚類簇中的所有數(shù)據(jù)對象的平均值，并將得到的結(jié)果作為新的簇心；逐步重復(fù)上述的過程直至目標(biāo)函數(shù)收斂為止。
下面介紹該算法的具體步驟：
- 對于給定的一組數(shù)據(jù)，隨機(jī)初始化K個(gè)聚類中心（簇中心）
- 計(jì)算每個(gè)數(shù)據(jù)到簇中心的距離（一般采用歐氏距離），并把該數(shù)據(jù)歸為離它最近的簇。
- 根據(jù)得到的簇，重新計(jì)算簇中心。
- 對步驟2、步驟3進(jìn)行迭代直至簇中心不再改變或者小于指定閾值。
K-means算法的流程圖
4、K-means偽代碼
輸入 n 個(gè)數(shù)據(jù)對象集合Xi ;輸出 k 個(gè)聚類中心 Zj 及K 個(gè)聚類數(shù)據(jù)對象集合 Cj .
Procedure K -means(s , k)
S ={x 1 ,x 2 , …,x n };
m =1;for j =1 to k 初始化聚類中心 Zj ;
do {for i =1 to n
for j=1 to k
{D(Xi ,Zj)= Xi -Zj ;if D(Xi ,Zj)=Min{D(Xi ,Zj)}then Xi ∈Cj ;}//歸類
if m=1 then Jc(m)=∑kj=1∑ Xi -Zj
2
m =m+1;for j =1 to k
Zj =(∑
n
i=1 (Xi)
j )/n;//重置聚類中心
}while J c (m)-J c (m -1) >ξ
二、K-means代碼實(shí)現(xiàn)
本文使用的數(shù)據(jù)集為UCI數(shù)據(jù)集，分別使用鳶尾花數(shù)據(jù)集Iris、葡萄酒數(shù)據(jù)集Wine、小麥種子數(shù)據(jù)集seeds進(jìn)行測試，本文從UCI官網(wǎng)上將這三個(gè)數(shù)據(jù)集下載下來，并放入和python文件同一個(gè)文件夾內(nèi)即可。同時(shí)由于程序需要，將數(shù)據(jù)集的列的位置做出了略微改動(dòng)。數(shù)據(jù)集具體信息如下表：
| 數(shù)據(jù)集 | 樣本數(shù) | 屬性維度 | 類別個(gè)數(shù) |
|---|---|---|---|
| Iris | 150 | 4 | 3 |
| Wine | 178 | 3 | 3 |
| Seeds | 210 | 7 | 3 |
數(shù)據(jù)集在我主頁資源里有，免積分下載，如果無法下載，可以私信我。
1、Python3代碼實(shí)現(xiàn)
import time
import pandas as pd
import matplotlib.pyplot as plt
import numpy as np
from numpy import nonzero, array
from sklearn.cluster import KMeans
from sklearn.metrics import f1_score, accuracy_score, normalized_mutual_info_score, rand_score, adjusted_rand_score
from sklearn.preprocessing import LabelEncoder
from sklearn.decomposition import PCA
# 數(shù)據(jù)保存在.csv文件中
iris = pd.read_csv("dataset/Iris.csv", header=0) # 鳶尾花數(shù)據(jù)集 Iris class=3
wine = pd.read_csv("dataset/wine.csv") # 葡萄酒數(shù)據(jù)集 Wine class=3
seeds = pd.read_csv("dataset/seeds.csv") # 小麥種子數(shù)據(jù)集 seeds class=3
wdbc = pd.read_csv("dataset/wdbc.csv") # 威斯康星州乳腺癌數(shù)據(jù)集 Breast Cancer Wisconsin (Diagnostic) class=2
glass = pd.read_csv("dataset/glass.csv") # 玻璃辨識(shí)數(shù)據(jù)集 Glass Identification class=6
df = iris # 設(shè)置要讀取的數(shù)據(jù)集
# print(df)
columns = list(df.columns) # 獲取數(shù)據(jù)集的第一行，第一行通常為特征名，所以先取出
features = columns[:len(columns) - 1] # 數(shù)據(jù)集的特征名（去除了最后一列，因?yàn)樽詈笠涣写娣诺氖菢?biāo)簽，不是數(shù)據(jù)）
dataset = df[features] # 預(yù)處理之后的數(shù)據(jù)，去除掉了第一行的數(shù)據(jù)（因?yàn)槠錇樘卣髅?，如果?shù)據(jù)第一行不是特征名，可跳過這一步）
attributes = len(df.columns) - 1 # 屬性數(shù)量（數(shù)據(jù)集維度）
original_labels = list(df[columns[-1]]) # 原始標(biāo)簽
def initialize_centroids(data, k):
# 從數(shù)據(jù)集中隨機(jī)選擇k個(gè)點(diǎn)作為初始質(zhì)心
centers = data[np.random.choice(data.shape[0], k, replace=False)]
return centers
def get_clusters(data, centroids):
# 計(jì)算數(shù)據(jù)點(diǎn)與質(zhì)心之間的距離，并將數(shù)據(jù)點(diǎn)分配給最近的質(zhì)心
distances = np.linalg.norm(data[:, np.newaxis] - centroids, axis=2)
cluster_labels = np.argmin(distances, axis=1)
return cluster_labels
def update_centroids(data, cluster_labels, k):
# 計(jì)算每個(gè)簇的新質(zhì)心，即簇內(nèi)數(shù)據(jù)點(diǎn)的均值
new_centroids = np.array([data[cluster_labels == i].mean(axis=0) for i in range(k)])
return new_centroids
def k_means(data, k, T, epsilon):
start = time.time() # 開始時(shí)間，計(jì)時(shí)
# 初始化質(zhì)心
centroids = initialize_centroids(data, k)
t = 0
while t <= T:
# 分配簇
cluster_labels = get_clusters(data, centroids)
# 更新質(zhì)心
new_centroids = update_centroids(data, cluster_labels, k)
# 檢查收斂條件
if np.linalg.norm(new_centroids - centroids) < epsilon:
break
centroids = new_centroids
print("第", t, "次迭代")
t += 1
print("用時(shí)：{0}".format(time.time() - start))
return cluster_labels, centroids
# 計(jì)算聚類指標(biāo)
def clustering_indicators(labels_true, labels_pred):
if type(labels_true[0]) != int:
labels_true = LabelEncoder().fit_transform(df[columns[len(columns) - 1]]) # 如果數(shù)據(jù)集的標(biāo)簽為文本類型，把文本標(biāo)簽轉(zhuǎn)換為數(shù)字標(biāo)簽
f_measure = f1_score(labels_true, labels_pred, average='macro') # F值
accuracy = accuracy_score(labels_true, labels_pred) # ACC
normalized_mutual_information = normalized_mutual_info_score(labels_true, labels_pred) # NMI
rand_index = rand_score(labels_true, labels_pred) # RI
ARI = adjusted_rand_score(labels_true, labels_pred)
return f_measure, accuracy, normalized_mutual_information, rand_index, ARI
# 繪制聚類結(jié)果散點(diǎn)圖
def draw_cluster(dataset, centers, labels):
center_array = array(centers)
if attributes > 2:
dataset = PCA(n_components=2).fit_transform(dataset) # 如果屬性數(shù)量大于2，降維
center_array = PCA(n_components=2).fit_transform(center_array) # 如果屬性數(shù)量大于2，降維
else:
dataset = array(dataset)
# 做散點(diǎn)圖
label = array(labels)
plt.scatter(dataset[:, 0], dataset[:, 1], marker='o', c='black', s=7) # 原圖
# plt.show()
colors = np.array(
["#FF0000", "#0000FF", "#00FF00", "#FFFF00", "#00FFFF", "#FF00FF", "#800000", "#008000", "#000080", "#808000",
"#800080", "#008080", "#444444", "#FFD700", "#008080"])
# 循換打印k個(gè)簇，每個(gè)簇使用不同的顏色
for i in range(k):
plt.scatter(dataset[nonzero(label == i), 0], dataset[nonzero(label == i), 1], c=colors[i], s=7, marker='o')
# plt.scatter(center_array[:, 0], center_array[:, 1], marker='x', color='m', s=30) # 聚類中心
plt.show()
if __name__ == "__main__":
k = 3 # 聚類簇?cái)?shù)
T = 100 # 最大迭代數(shù)
n = len(dataset) # 樣本數(shù)
epsilon = 1e-5
# 預(yù)測全部數(shù)據(jù)
labels, centers = k_means(np.array(dataset), k, T, epsilon)
# print(labels)
F_measure, ACC, NMI, RI, ARI = clustering_indicators(original_labels, labels) # 計(jì)算聚類指標(biāo)
print("F_measure:", F_measure, "ACC:", ACC, "NMI", NMI, "RI", RI, "ARI", ARI)
# print(membership)
# print(centers)
# print(dataset)
draw_cluster(dataset, centers, labels=labels)
2、聚類結(jié)果分析
本文選擇了F值（F-measure，F(xiàn)M）、準(zhǔn)確率（Accuracy，ACC）、標(biāo)準(zhǔn)互信息（Normalized Mutual Information，NMI）和蘭德指數(shù)（Rand Index，RI）作為評估指標(biāo)，其值域?yàn)閇0,1]，取值越大說明聚類結(jié)果越符合預(yù)期。
F值結(jié)合了精度（Precision）與召回率（Recall）兩種指標(biāo)，它的值為精度與召回率的調(diào)和平均，其計(jì)算公式見公式：
P r e c i s i o n = T P T P + F P Precision=\frac{TP}{TP+FP} Precision=TP+FPTP?
R e c a l l = T P T P + F N Recall=\frac{TP}{TP+FN} Recall=TP+FNTP?
F ? m e a s u r e = 2 R e c a l l × P r e c i s i o n R e c a l l + P r e c i s i o n F-measure=\frac{2Recall \times Precision}{Recall+Precision} F?measure=Recall+Precision2Recall×Precision?
ACC是被正確分類的樣本數(shù)與數(shù)據(jù)集總樣本數(shù)的比值，計(jì)算公式如下：
A C C = T P + T N T P + T N + F P + F N ACC=\frac{TP+TN}{TP+TN+FP+FN} ACC=TP+TN+FP+FNTP+TN?
其中，TP（True Positive）表示將正類預(yù)測為正類數(shù)的樣本個(gè)數(shù)，TN （True Negative）表示將負(fù)類預(yù)測為負(fù)類數(shù)的樣本個(gè)數(shù)，F(xiàn)P（False Positive）表示將負(fù)類預(yù)測為正類數(shù)誤報(bào)的樣本個(gè)數(shù)，F(xiàn)N（False Negative）表示將正類預(yù)測為負(fù)類數(shù)的樣本個(gè)數(shù)。
NMI用于量化聚類結(jié)果和已知類別標(biāo)簽的匹配程度，相比于ACC，NMI的值不會(huì)受到族類標(biāo)簽排列的影響。計(jì)算公式如下：
N M I = I ( U , V ) H ( U ) H ( V ) NMI=\frac{I\left(U,V\right)}{\sqrt{H\left(U\right)H\left(V\right)}} NMI=H(U)H(V)?I(U,V)?
其中H(U)代表正確分類的熵，H(V)分別代表通過算法得到的結(jié)果的熵。
其具體實(shí)現(xiàn)代嗎如下：
由于數(shù)據(jù)集中給定的正確標(biāo)簽可能為文本類型而不是數(shù)字標(biāo)簽，所以在計(jì)算前先判斷數(shù)據(jù)集的標(biāo)簽是否為數(shù)字類型，如果不是，則轉(zhuǎn)化為數(shù)字類型
def clustering_indicators(labels_true, labels_pred):
if type(labels_true[0]) != int:
labels_true = LabelEncoder().fit_transform(df[columns[len(columns) - 1]]) # 如果數(shù)據(jù)集的標(biāo)簽為文本類型，把文本標(biāo)簽轉(zhuǎn)換為數(shù)字標(biāo)簽
f_measure = f1_score(labels_true, labels_pred, average='macro') # F值
accuracy = accuracy_score(labels_true, labels_pred) # ACC
normalized_mutual_information = normalized_mutual_info_score(labels_true, labels_pred) # NMI
rand_index = rand_score(labels_true, labels_pred) # RI
return f_measure, accuracy, normalized_mutual_information, rand_index
F_measure, ACC, NMI, RI = clustering_indicators(class_labels, label)
print("F_measure:", F_measure, "ACC:", ACC, "NMI", NMI, "RI", RI)
如果需要計(jì)算出聚類分析指標(biāo)，只要將以上代碼插入K-means實(shí)現(xiàn)代碼中即可。
3、聚類結(jié)果
-
鳶尾花數(shù)據(jù)集Iris
Iris鳶尾花數(shù)據(jù)集原圖 
Iris鳶尾花數(shù)據(jù)集K-means聚類效果圖 -
葡萄酒數(shù)據(jù)集Wine
Wine葡萄酒數(shù)據(jù)集原圖 
Wine葡萄酒數(shù)據(jù)集K-means聚類效果圖 -
小麥種子數(shù)據(jù)集Seeds
文章來源：http://www.zghlxwxcb.cn/news/detail-471595.htmlSeeds小麥種子數(shù)據(jù)集原圖 
Seeds小麥種子數(shù)據(jù)集K-means聚類效果圖
4、K-means算法的不足
K-means算法的核心步驟就是通過不斷地迭代，更新聚類簇中心，達(dá)到簇內(nèi)距離最小。算法的時(shí)間復(fù)雜度很低，因此該算法得到了廣泛應(yīng)用，但是該算法存在著許多不足，主要不足如下：文章來源地址http://www.zghlxwxcb.cn/news/detail-471595.html
- K-means聚類的簇?cái)?shù)目需要用戶指定。K-means算法首先需要用戶指定簇的數(shù)目K值，K值的確定直接影響聚類的結(jié)果，通常情況下，K值需要用戶依據(jù)自己的經(jīng)驗(yàn)和對數(shù)據(jù)集的理解指定，因此指定的數(shù)值未必理想，聚類的結(jié)果也就無從保證。
- K-means算法的初始中心點(diǎn)選取上采用的是隨機(jī)的方法。K-means算法極為依賴初始中心點(diǎn)的選?。阂坏╁e(cuò)誤地選取了初始中心點(diǎn)，對于后續(xù)的聚類過程影響極大，很可能得不到最理想的聚類結(jié)果，同時(shí)聚類迭代的次數(shù)也可能會(huì)增加。而隨機(jī)選取的初始中心點(diǎn)具有很大的不確定性，也直接影響著聚類的效果。
- K-means采用歐氏距離進(jìn)行相似性度量，在非凸形數(shù)據(jù)集中難以達(dá)到良好的聚類效果。
到了這里，關(guān)于K-means聚類算法（附Python實(shí)現(xiàn)代碼）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
