利用Python如何實(shí)現(xiàn)K-means聚類算法
K-Means 是一種非常簡(jiǎn)單的聚類算法(聚類算法都屬于無監(jiān)督學(xué)習(xí))。給定固定數(shù)量的聚類和輸入數(shù)據(jù)集，該算法試圖將數(shù)據(jù)劃分為聚類，使得聚類內(nèi)部具有較高的相似性，聚類與聚類之間具有較低的相似性。
算法原理
1. 初始化聚類中心，或者在輸入數(shù)據(jù)范圍內(nèi)隨機(jī)選擇，或者使用一些現(xiàn)有的訓(xùn)練樣本(推薦)
2. 直到收斂
- 將每個(gè)數(shù)據(jù)點(diǎn)分配到最近的聚類。點(diǎn)與聚類中心之間的距離是通過歐幾里德距離測(cè)量得到的。
- 通過將聚類中心的當(dāng)前估計(jì)值設(shè)置為屬于該聚類的所有實(shí)例的平均值，來更新它們的當(dāng)前估計(jì)值。
目標(biāo)函數(shù)
聚類算法的目標(biāo)函數(shù)試圖找到聚類中心，以便數(shù)據(jù)將劃分到相應(yīng)的聚類中，并使得數(shù)據(jù)與其最接近的聚類中心之間的距離盡可能小。
給定一組數(shù)據(jù)X1，...，Xn和一個(gè)正數(shù)k，找到k個(gè)聚類中心C1，...，Ck并最小化目標(biāo)函數(shù)：
其中
是質(zhì)心，計(jì)算表達(dá)式為
上圖a表達(dá)了初始的數(shù)據(jù)集，假設(shè)k=2。在圖b中，我們隨機(jī)選擇了兩個(gè)k類所對(duì)應(yīng)的類別質(zhì)心，即圖中的紅色質(zhì)心和藍(lán)色質(zhì)心，然后分別求樣本中所有點(diǎn)到這兩個(gè)質(zhì)心的距離，并標(biāo)記每個(gè)樣本的類別為和該樣本距離最小的質(zhì)心的類別，如圖c所示，經(jīng)過計(jì)算樣本和紅色質(zhì)心和藍(lán)色質(zhì)心的距離，我們得到了所有樣本點(diǎn)的第一輪迭代后的類別。此時(shí)我們對(duì)我們當(dāng)前標(biāo)記為紅色和藍(lán)色的點(diǎn)分別求其新的質(zhì)心，如圖4所示，新的紅色質(zhì)心和藍(lán)色質(zhì)心的位置已經(jīng)發(fā)生了變動(dòng)。圖e和圖f重復(fù)了我們?cè)趫Dc和圖d的過程，即將所有點(diǎn)的類別標(biāo)記為距離最近的質(zhì)心的類別并求新的質(zhì)心。最終我們得到的兩個(gè)類別如圖f。當(dāng)然在實(shí)際K-Mean算法中，我們一般會(huì)多次運(yùn)行圖c和圖d，才能達(dá)到最終的比較優(yōu)的類別。
算法流程
注意點(diǎn)：
- 對(duì)于K-Means算法，首先要注意的是k值的選擇，一般來說，我們會(huì)根據(jù)對(duì)數(shù)據(jù)的先驗(yàn)經(jīng)驗(yàn)選擇一個(gè)合適的k值，如果沒有什么先驗(yàn)知識(shí)，則可以通過交叉驗(yàn)證選擇一個(gè)合適的k值
- 在確定了k的個(gè)數(shù)后，我們需要選擇k個(gè)初始化的質(zhì)心，就像上圖b中的隨機(jī)質(zhì)心。由于我們是啟發(fā)式方法，k個(gè)初始化的質(zhì)心的位置選擇對(duì)最后的聚類結(jié)果和運(yùn)行時(shí)間都有很大的影響，因此需要選擇合適的k個(gè)質(zhì)心，最好這些質(zhì)心不能太近。
流程：
輸入是樣本集D={x1,x2,...xm},聚類的簇樹k,最大迭代次數(shù)N
輸出是簇劃分C={C1,C2,...Ck}
1) 從數(shù)據(jù)集D中隨機(jī)選擇k個(gè)樣本作為初始的k個(gè)質(zhì)心向量： {μ1,μ2,...,μk}
2）對(duì)于n=1,2,...,N
a) 將簇劃分C初始化為Ct=∅ t=1,2...k
b) 對(duì)于i=1,2...m,計(jì)算樣本xi和各個(gè)質(zhì)心向量μj(j=1,2,...k)的距離：
，將xixi標(biāo)記最小的為
所對(duì)應(yīng)的類別
。此時(shí)更新
c) 對(duì)于j=1,2,...,k,對(duì)Cj中所有的樣本點(diǎn)重新計(jì)算新的質(zhì)心
e) 如果所有的k個(gè)質(zhì)心向量都沒有發(fā)生變化，則轉(zhuǎn)到步驟3）
3） 輸出簇劃分C={C1,C2,...Ck}
Python實(shí)現(xiàn)
import numpy as np
import matplotlib.pyplot as plt
import random
from sklearn.datasets import make_blobs
np.random.seed(123)
from sklearn.cluster import KMeans
class Kmeans:
def __init__(self,data,k):
self.data=data
self.k = k
def cluster_data_Bysklearn(self):
kmeans_model = KMeans(self.k,random_state=1)
labels = kmeans_model.fit(self.data).labels_
print(labels)
return labels
def kmeans(self):
# 獲取4個(gè)隨機(jī)數(shù)
rarray = np.random.random(size=self.k)
# 乘以數(shù)據(jù)集大小——>數(shù)據(jù)集中隨機(jī)的4個(gè)點(diǎn)
rarray = np.floor(rarray * len(self.data))
# 轉(zhuǎn)為int
rarray = rarray.astype(int)
print('數(shù)據(jù)集中隨機(jī)索引', rarray)
# 隨機(jī)取數(shù)據(jù)集中的4個(gè)點(diǎn)作為初始中心點(diǎn)
center = data[rarray]
# 測(cè)試比較偏、比較集中的點(diǎn)，效果依然完美，測(cè)試需要?jiǎng)h除以上代碼
# center = np.array([[4.6,-2.5],[4.4,-1.7],[4.3,-0.7],[4.8,-1.1]])
# 1行80列的0數(shù)組，標(biāo)記每個(gè)樣本所屬的類(k[i])
cls = np.zeros([len(self.data)], np.int)
print('初始center=\n', center)
run = True
time = 0
n = len(self.data)
while run:
time = time + 1
for i in range(n):
# 求差
tmp = data[i] - center
# 求平方
tmp = np.square(tmp)
# axis=1表示按行求和
tmp = np.sum(tmp, axis=1)
# 取最?。ㄗ罱┑慕o該點(diǎn)“染色”（標(biāo)記每個(gè)樣本所屬的類(k[i])）
cls[i] = np.argmin(tmp)
# 如果沒有修改各分類中心點(diǎn)，就結(jié)束循環(huán)
run = False
# 計(jì)算更新每個(gè)類的中心點(diǎn)
for i in range(self.k):
# 找到屬于該類的所有樣本
club = data[cls == i]
# axis=0表示按列求平均值，計(jì)算出新的中心點(diǎn)
newcenter = np.mean(club, axis=0)
# 如果新舊center的差距很小，看做他們相等，否則更新之。run置true，再來一次循環(huán)
ss = np.abs(center[i] - newcenter)
if np.sum(ss, axis=0) > 1e-4:
center[i] = newcenter
run = True
print('new center=\n', center)
print('程序結(jié)束，迭代次數(shù)：', time)
# 按類打印圖表，因?yàn)槊看蛴∫淮?，顏色都不一樣，所以可區(qū)分出來
# for i in range(self.k):
# club = data[cls == i]
# self.showtable(club)
# 打印最后的中心點(diǎn)
self.showtable(center)
#打印聚類標(biāo)簽
print(cls)
def showtable(self,data):
x = data.T[0]
y = data.T[1]
plt.scatter(x, y)
plt.show()
if __name__ == '__main__':
data = np.random.rand(10,2)
K = 4
model = Kmeans(data,K)
model.kmeans()
model.cluster_data_Bysklearn()
結(jié)果：
自寫得出的 [0 2 0 0 0 2 3 2 1 2]
調(diào)用模型的出的[0 2 0 1 0 2 3 2 3 0]
jupyter notebook實(shí)現(xiàn)
import numpy as np import matplotlib.pyplot as plt import random from sklearn.datasets import make_blobs %matplotlib inline
X, y = make_blobs(centers=6, n_samples=1000)
print(f'Shape of dataset: {X.shape}')
fig = plt.figure(figsize=(8,6))
plt.scatter(X[:,0], X[:,1], c=y)
plt.title("Dataset with 6 clusters")
plt.xlabel("First feature")
plt.ylabel("Second feature")
plt.show()
class KMeans():
def __init__(self, n_clusters=6):
self.k = n_clusters
def fit(self, data):
"""
Fits the k-means model to the given dataset
"""
n_samples, _ = data.shape
# initialize cluster centers
self.centers = np.array(random.sample(list(data), self.k))
self.initial_centers = np.copy(self.centers)
# We will keep track of whether the assignment of data points
# to the clusters has changed. If it stops changing, we are
# done fitting the model
old_assigns = None
n_iters = 0
while True:
new_assigns = [self.classify(datapoint) for datapoint in data]
if new_assigns == old_assigns:
print(f"Training finished after {n_iters} iterations!")
return
old_assigns = new_assigns
n_iters += 1
# recalculate centers
for id_ in range(self.k):
points_idx = np.where(np.array(new_assigns) == id_)
datapoints = data[points_idx]
self.centers[id_] = datapoints.mean(axis=0)
def l2_distance(self, datapoint):
dists = np.sqrt(np.sum((self.centers - datapoint)**2, axis=1))
return dists
def classify(self, datapoint):
"""
Given a datapoint, compute the cluster closest to the
datapoint. Return the cluster ID of that cluster.
"""
dists = self.l2_distance(datapoint)
return np.argmin(dists)
def plot_clusters(self, data):
plt.figure(figsize=(12,10))
plt.title("Initial centers in black, final centers in red")
plt.scatter(data[:, 0], data[:, 1], marker='.', c='y')
plt.scatter(self.centers[:, 0], self.centers[:,1], c='r')
plt.scatter(self.initial_centers[:, 0], self.initial_centers[:,1], c='k')
plt.show()
X = np.random.randn(10,100) kmeans = KMeans(n_clusters=6) kmeans.fit(X) for data in X: print(kmeans.classify(data))
總結(jié)
K-Means的主要優(yōu)點(diǎn)：
1）原理簡(jiǎn)單，容易實(shí)現(xiàn)
2）可解釋度較強(qiáng)
K-Means的主要缺點(diǎn)：
1）K值很難確定
2）局部最優(yōu)
3）對(duì)噪音和異常點(diǎn)敏感
4）需樣本存在均值（限定數(shù)據(jù)種類）
5）聚類效果依賴于聚類中心的初始化
6）對(duì)于非凸數(shù)據(jù)集或類別規(guī)模差異太大的數(shù)據(jù)效果不好
到此這篇關(guān)于利用Python如何實(shí)現(xiàn)K-means聚類算法的文章就介紹到這了,更多相關(guān)Python實(shí)現(xiàn)K-means聚類算法內(nèi)容請(qǐng)搜索本站以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持本站！
版權(quán)聲明：本站文章來源標(biāo)注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請(qǐng)保持原文完整并注明來源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站，禁止在非www.sddonglingsh.com所屬的服務(wù)器上建立鏡像，否則將依法追究法律責(zé)任。本站部分內(nèi)容來源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來，僅供學(xué)習(xí)參考，不代表本站立場(chǎng)，如有內(nèi)容涉嫌侵權(quán)，請(qǐng)聯(lián)系alex-e#qq.com處理。
關(guān)注官方微信