python Kmeans算法原理深入解析
一. 概述
首先需要先介紹一下無(wú)監(jiān)督學(xué)習(xí)，所謂無(wú)監(jiān)督學(xué)習(xí)，就是訓(xùn)練樣本中的標(biāo)記信息是位置的，目標(biāo)是通過(guò)對(duì)無(wú)標(biāo)記訓(xùn)練樣本的學(xué)習(xí)來(lái)揭示數(shù)據(jù)的內(nèi)在性質(zhì)以及規(guī)律。通俗得說(shuō)，就是根據(jù)數(shù)據(jù)的一些內(nèi)在性質(zhì)，找出其內(nèi)在的規(guī)律。而這一類算法，應(yīng)用最為廣泛的就是“聚類”。
聚類算法可以對(duì)數(shù)據(jù)進(jìn)行數(shù)據(jù)歸約，即在盡可能保證數(shù)據(jù)完整的前提下，減少數(shù)據(jù)的量級(jí)，以便后續(xù)處理。也可以對(duì)聚類數(shù)據(jù)結(jié)果直接應(yīng)用或分析。
而Kmeans 算法可以說(shuō)是聚類算法里面較為基礎(chǔ)的一種算法。
二. 從樣例開(kāi)始
我們現(xiàn)在在二維平面上有這樣一些點(diǎn)
x y 1.658985 4.285136 -3.453687 3.424321 4.838138 -1.151539 -5.379713 -3.362104 0.972564 2.924086 -3.567919 1.531611 0.450614 -3.302219 -3.487105 -1.724432 2.668759 1.594842 -3.156485 3.191137 3.165506 -3.999838 -2.786837 -3.099354 4.208187 2.984927 -2.123337 2.943366 0.704199 -0.479481 -0.392370 -3.963704 2.831667 1.574018 -0.790153 3.343144 2.943496 -3.357075 ...
它在二維平面上的分布大概是這樣的：
好，這些點(diǎn)看起來(lái)隱約分成4個(gè)“簇”，那么我們可以假定它就是要分成4個(gè)“簇”。（雖然我們可以“看”出來(lái)是要分成4個(gè)“簇”，但實(shí)際上也可以分成其他個(gè)，比如說(shuō)5個(gè)。）這里分成“4個(gè)簇“是我們看出來(lái)的。而在實(shí)際應(yīng)用中其實(shí)應(yīng)該由機(jī)器算得，下面也會(huì)有介紹的。
找出4個(gè)”簇”之后，就要找出每個(gè)“簇”的中心了，我們可以“看出”大概的中心點(diǎn)，但機(jī)器不知道啊。那么機(jī)器是如何知道的呢？答案是通過(guò)向量距離，也叫向量相似性。這個(gè)相似性計(jì)算有多種方法，比如歐式距離，曼哈頓距離，切比雪夫距離等等。
我們這里使用的是歐式距離，歐式距離其實(shí)就是反應(yīng)空間中兩點(diǎn)的直線距離。
知道這些后，我們就可以開(kāi)始讓機(jī)器計(jì)算出4個(gè)“簇”了。
主要做法是這樣，先隨機(jī)生成4個(gè)點(diǎn)，假設(shè)這4個(gè)點(diǎn)就是4個(gè)“簇”的中心。計(jì)算平面中每個(gè)點(diǎn)到4個(gè)中心點(diǎn)的距離，平面中每個(gè)點(diǎn)選取距離最近的那個(gè)中心作為自己的中心。
此時(shí)我們就完成第一步，將平面中所有點(diǎn)分成4個(gè)”簇“。但是剛剛那幾個(gè)中心都是隨機(jī)的，這樣分成的4個(gè)簇明顯不是我們想要的結(jié)果。怎么辦呢？做法如下：
現(xiàn)在有4個(gè)簇，根據(jù)每個(gè)簇中所有點(diǎn)計(jì)算出每個(gè)簇的新中心點(diǎn)。這個(gè)新中心點(diǎn)就會(huì)比上一個(gè)舊的中心點(diǎn)更優(yōu)，因?yàn)樗又行摹Ｈ缓笫褂眯轮行狞c(diǎn)重復(fù)第一步的步驟。即再對(duì)平面中所有點(diǎn)算距離，然后分發(fā)到4個(gè)新簇中。不斷迭代，直到誤差較小。
這就是 Kmeans 算法的過(guò)程了。
三. 知識(shí)點(diǎn)淺析
3.1 確定“簇”的個(gè)數(shù)
上面所說(shuō)的分成 4 個(gè)簇，這個(gè) 4 其實(shí)就是 Kmeans 中的K。要使用 Kmeans 首先就是要選取一個(gè) K 作為聚類個(gè)數(shù)。而上面的例子其實(shí)是我們主觀”看“出來(lái)的，但多數(shù)情況下我們是無(wú)法直觀”看“出分多少個(gè) K 比較好。那怎么辦呢？
我們可以從較低的 K 值開(kāi)始。使用較簡(jiǎn)單的 Kmeans 算法的結(jié)果（即較少的迭代次數(shù)，不求最佳結(jié)果，但求最快）。計(jì)算每個(gè)點(diǎn)到其歸屬的“簇”的中心點(diǎn)的距離，然后求和，求和結(jié)果就是誤差值。
然后再增加 K 值，再計(jì)算誤差值。比如上面的例子，我們可以從 K=2 開(kāi)始，計(jì)算 K 值從 2 到 7 的 Kmeans 算法的誤差值。
這樣會(huì)得到類似這樣一張圖：
里面的 Error 可以理解未 Kmeans 的誤差，而當(dāng)分成越多“簇”的適合，誤差肯定是越來(lái)越小。
但是不是“簇”越多越好呢？答案是否定的，有時(shí)候“簇”過(guò)多的話是不利于我們得到想要的結(jié)果或是做下一步操作的。
所以我們通常會(huì)選擇誤差減小速度比較平緩的那個(gè)臨界點(diǎn)，比如上圖中的 4。
可以發(fā)現(xiàn)，在分成 4 個(gè)簇之后，再增加簇的數(shù)量，誤差也不會(huì)有很大的減少。而取 4 個(gè)簇也和我們所看到的相符。
3.2 歐式距離
歐氏距離是一個(gè)通常采用的距離定義，指在m維空間中兩個(gè)點(diǎn)之間的真實(shí)距離，計(jì)算公式如下：
而本例種的是在二維空間種，故而本例的計(jì)算公式如下：
四. 代碼和結(jié)果
加載數(shù)據(jù)的代碼，使用了 numpy ，先是將代碼加載成 matrix 類型。
import numpy as np
def loadDataSet(fileName):
'''
加載數(shù)據(jù)集
:param fileName:
:return:
'''
# 初始化一個(gè)空列表
dataSet = []
# 讀取文件
fr = open(fileName)
# 循環(huán)遍歷文件所有行
for line in fr.readlines():
# 切割每一行的數(shù)據(jù)
curLine = line.strip().split('\t')
# 將數(shù)據(jù)轉(zhuǎn)換為浮點(diǎn)類型,便于后面的計(jì)算
# fltLine = [float(x) for x in curLine]
# 將數(shù)據(jù)追加到dataMat
fltLine = list(map(float,curLine)) # 映射所有的元素為 float（浮點(diǎn)數(shù)）類型
dataSet.append(fltLine)
# 返回dataMat
return np.matrix(dataSet)
接下來(lái)需要生成 K 個(gè)初始的質(zhì)點(diǎn)，即中心點(diǎn)。這里采用隨機(jī)生成的方法生成 k 個(gè)“簇”。
def randCent(dataMat, k):
'''
為給定數(shù)據(jù)集構(gòu)建一個(gè)包含K個(gè)隨機(jī)質(zhì)心的集合,
隨機(jī)質(zhì)心必須要在整個(gè)數(shù)據(jù)集的邊界之內(nèi),這可以通過(guò)找到數(shù)據(jù)集每一維的最小和最大值來(lái)完成
然后生成0到1.0之間的隨機(jī)數(shù)并通過(guò)取值范圍和最小值,以便確保隨機(jī)點(diǎn)在數(shù)據(jù)的邊界之內(nèi)
:param dataMat:
:param k:
:return:
'''
# 獲取樣本數(shù)與特征值
m, n = np.shape(dataMat)
# 初始化質(zhì)心,創(chuàng)建(k,n)個(gè)以零填充的矩陣
centroids = np.mat(np.zeros((k, n)))
# 循環(huán)遍歷特征值
for j in range(n):
# 計(jì)算每一列的最小值
minJ = min(dataMat[:, j])
# 計(jì)算每一列的范圍值
rangeJ = float(max(dataMat[:, j]) - minJ)
# 計(jì)算每一列的質(zhì)心,并將值賦給centroids
centroids[:, j] = np.mat(minJ + rangeJ * np.random.rand(k, 1))
# 返回質(zhì)心
return centroids
歐式距離計(jì)算
def distEclud(vecA, vecB): ''' 歐氏距離計(jì)算函數(shù) :param vecA: :param vecB: :return: ''' return np.sqrt(sum(np.power(vecA - vecB, 2)))
cost 方法將執(zhí)行一個(gè)簡(jiǎn)化的 kMeans ，即較少次數(shù)的迭代，計(jì)算出其中的誤差（即當(dāng)前點(diǎn)到簇質(zhì)心的距離,后面會(huì)使用該誤差來(lái)評(píng)價(jià)聚類的效果）
def cost(dataMat, k, distMeas=distEclud, createCent=randCent,iterNum=300):
'''
計(jì)算誤差的多少，通過(guò)這個(gè)方法來(lái)確定 k 為多少比較合適，這個(gè)其實(shí)就是一個(gè)簡(jiǎn)化版的 kMeans
:param dataMat: 數(shù)據(jù)集
:param k: 簇的數(shù)目
:param distMeans: 計(jì)算距離
:param createCent: 創(chuàng)建初始質(zhì)心
:param iterNum：默認(rèn)迭代次數(shù)
:return:
'''
# 獲取樣本數(shù)和特征數(shù)
m, n = np.shape(dataMat)
# 初始化一個(gè)矩陣來(lái)存儲(chǔ)每個(gè)點(diǎn)的簇分配結(jié)果
# clusterAssment包含兩個(gè)列:一列記錄簇索引值,第二列存儲(chǔ)誤差(誤差是指當(dāng)前點(diǎn)到簇質(zhì)心的距離,后面會(huì)使用該誤差來(lái)評(píng)價(jià)聚類的效果)
clusterAssment = np.mat(np.zeros((m, 2)))
# 創(chuàng)建質(zhì)心,隨機(jī)K個(gè)質(zhì)心
centroids = createCent(dataMat, k)
clusterChanged = True
while iterNum > 0:
clusterChanged = False
# 遍歷所有數(shù)據(jù)找到距離每個(gè)點(diǎn)最近的質(zhì)心,
# 可以通過(guò)對(duì)每個(gè)點(diǎn)遍歷所有質(zhì)心并計(jì)算點(diǎn)到每個(gè)質(zhì)心的距離來(lái)完成
for i in range(m):
minDist = np.inf
minIndex = -1
for j in range(k):
# 計(jì)算數(shù)據(jù)點(diǎn)到質(zhì)心的距離
# 計(jì)算距離是使用distMeas參數(shù)給出的距離公式,默認(rèn)距離函數(shù)是distEclud
distJI = distMeas(centroids[j, :], dataMat[i, :])
# print(distJI)
# 如果距離比minDist(最小距離)還小,更新minDist(最小距離)和最小質(zhì)心的index(索引)
if distJI < minDist:
minDist = distJI
minIndex = j
# 更新簇分配結(jié)果為最小質(zhì)心的index(索引),minDist(最小距離)的平方
clusterAssment[i, :] = minIndex, minDist ** 2
iterNum -= 1;
# print(centroids)
# 遍歷所有質(zhì)心并更新它們的取值
for cent in range(k):
# 通過(guò)數(shù)據(jù)過(guò)濾來(lái)獲得給定簇的所有點(diǎn)
ptsInClust = dataMat[np.nonzero(clusterAssment[:, 0].A == cent)[0]]
# 計(jì)算所有點(diǎn)的均值,axis=0表示沿矩陣的列方向進(jìn)行均值計(jì)算
centroids[cent, :] = np.mean(ptsInClust, axis=0)
# 返回給定迭代次數(shù)后誤差的值
return np.mat(clusterAssment[:,1].sum(0))[0,0]
最后可以調(diào)用 Kmeans 算法來(lái)進(jìn)行計(jì)算。
def kMeans(dataMat, k, distMeas=distEclud, createCent=randCent):
'''
創(chuàng)建K個(gè)質(zhì)心,然后將每個(gè)店分配到最近的質(zhì)心,再重新計(jì)算質(zhì)心。
這個(gè)過(guò)程重復(fù)數(shù)次,直到數(shù)據(jù)點(diǎn)的簇分配結(jié)果不再改變?yōu)橹?
:param dataMat: 數(shù)據(jù)集
:param k: 簇的數(shù)目
:param distMeans: 計(jì)算距離
:param createCent: 創(chuàng)建初始質(zhì)心
:return:
'''
# 獲取樣本數(shù)和特征數(shù)
m, n = np.shape(dataMat)
# 初始化一個(gè)矩陣來(lái)存儲(chǔ)每個(gè)點(diǎn)的簇分配結(jié)果
# clusterAssment包含兩個(gè)列:一列記錄簇索引值,第二列存儲(chǔ)誤差(誤差是指當(dāng)前點(diǎn)到簇質(zhì)心的距離,后面會(huì)使用該誤差來(lái)評(píng)價(jià)聚類的效果)
clusterAssment = np.mat(np.zeros((m, 2)))
# 創(chuàng)建質(zhì)心,隨機(jī)K個(gè)質(zhì)心
centroids = createCent(dataMat, k)
# 初始化標(biāo)志變量,用于判斷迭代是否繼續(xù),如果True,則繼續(xù)迭代
clusterChanged = True
while clusterChanged:
clusterChanged = False
# 遍歷所有數(shù)據(jù)找到距離每個(gè)點(diǎn)最近的質(zhì)心,
# 可以通過(guò)對(duì)每個(gè)點(diǎn)遍歷所有質(zhì)心并計(jì)算點(diǎn)到每個(gè)質(zhì)心的距離來(lái)完成
for i in range(m):
minDist = np.inf
minIndex = -1
for j in range(k):
# 計(jì)算數(shù)據(jù)點(diǎn)到質(zhì)心的距離
# 計(jì)算距離是使用distMeas參數(shù)給出的距離公式,默認(rèn)距離函數(shù)是distEclud
distJI = distMeas(centroids[j, :], dataMat[i, :])
# 如果距離比minDist(最小距離)還小,更新minDist(最小距離)和最小質(zhì)心的index(索引)
if distJI < minDist:
minDist = distJI
minIndex = j
# 如果任一點(diǎn)的簇分配結(jié)果發(fā)生改變,則更新clusterChanged標(biāo)志
if clusterAssment[i, 0] != minIndex: clusterChanged = True
# 更新簇分配結(jié)果為最小質(zhì)心的index(索引),minDist(最小距離)的平方
clusterAssment[i, :] = minIndex, minDist ** 2
# print(centroids)
# 遍歷所有質(zhì)心并更新它們的取值
for cent in range(k):
# 通過(guò)數(shù)據(jù)過(guò)濾來(lái)獲得給定簇的所有點(diǎn)
ptsInClust = dataMat[np.nonzero(clusterAssment[:, 0].A == cent)[0]]
# 計(jì)算所有點(diǎn)的均值,axis=0表示沿矩陣的列方向進(jìn)行均值計(jì)算
centroids[cent, :] = np.mean(ptsInClust, axis=0)
# 返回所有的類質(zhì)心與點(diǎn)分配結(jié)果
return centroids, clusterAssment
選取不同的 k 值對(duì)結(jié)果影響有多大呢？我們來(lái)看看就知道了，下面給出的是 k 值為 2 到 6 的效果。
圖中紅色方塊即為“簇”的中心點(diǎn)，每個(gè)“簇”所屬的點(diǎn)用不同的顏色表示。
K = 2
K = 3
K = 4
K = 5
K = 6
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)梯度下降算法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-08-08
python自動(dòng)化辦公現(xiàn)在可不是一個(gè)陌生的詞，也隨著人們對(duì)自己隱私越來(lái)越看重，本文主要介紹了python 實(shí)現(xiàn)批量文件加密功能，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-07-07
Python使用Nocalhost并開(kāi)啟debug調(diào)試的方法
Nocalhost是一種開(kāi)發(fā)者工具，支持針對(duì)Kubernetes應(yīng)用程序進(jìn)行調(diào)試和部署，這篇文章主要介紹了Python怎么使用Nocalhost并開(kāi)啟debug,需要的朋友可以參考下2023-04-04
在Django model中設(shè)置多個(gè)字段聯(lián)合唯一約束的實(shí)例
今天小編就為大家分享一篇在Django model中設(shè)置多個(gè)字段聯(lián)合唯一約束的實(shí)例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2019-07-07
學(xué)習(xí)Python能用來(lái)做什么的問(wèn)題
這篇文章主要介紹了關(guān)于Python能用來(lái)做什么的問(wèn)題,如果你想學(xué)Python，或者你剛開(kāi)始學(xué)習(xí)Python，那么你可能會(huì)問(wèn)：我能用Python做什么？下面就讓我們一起來(lái)看看吧2023-04-04
這篇文章主要介紹了用Python登錄好友QQ空間點(diǎn)贊的示例代碼，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-11-11
Python利用yield?form實(shí)現(xiàn)異步協(xié)程爬蟲(chóng)
這篇文章主要為大家詳細(xì)介紹了Python如何利用yield?form實(shí)現(xiàn)異步協(xié)程爬蟲(chóng)。其實(shí)這是很古老的用法了，現(xiàn)在大多用的aiohttp庫(kù)實(shí)現(xiàn)，這篇記錄僅僅用做個(gè)人的協(xié)程底層實(shí)現(xiàn)的學(xué)習(xí)，希望對(duì)大家有所幫助2022-11-11
這篇文章主要介紹了pyspark操作MongoDB的方法步驟，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2019-01-01
Python語(yǔ)言描述機(jī)器學(xué)習(xí)之Logistic回歸算法
這篇文章主要介紹了Python語(yǔ)言描述機(jī)器學(xué)習(xí)之Logistic回歸算法，涉及Sigmoid函數(shù)，梯度上升法等相關(guān)內(nèi)容，具有一定借鑒價(jià)值，需要的朋友可以參考下。2017-12-12
Python作用域(局部?全局)及global關(guān)鍵字使用詳解
這篇文章主要為大家介紹了Python作用域(局部?全局)及global關(guān)鍵字使用詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-10-10