python中k-means和k-means++原理及實(shí)現(xiàn)
前言
k-means算法是無監(jiān)督的聚類算法,實(shí)現(xiàn)起來較為簡(jiǎn)單,k-means++可以理解為k-means的增強(qiáng)版,在初始化中心點(diǎn)的方式上比k-means更友好。
k-means原理
k-means的實(shí)現(xiàn)步驟如下:
- 從樣本中隨機(jī)選取k個(gè)點(diǎn)作為聚類中心點(diǎn)
- 對(duì)于任意一個(gè)樣本點(diǎn),求其到k個(gè)聚類中心的距離,然后,將樣本點(diǎn)歸類到距離最小的聚類中心,直到歸類完所有的樣本點(diǎn)(聚成k類)
- 對(duì)每個(gè)聚類求平均值,然后將k個(gè)均值分別作為各自聚類新的中心點(diǎn)
- 重復(fù)2、3步,直到中心點(diǎn)位置不在變化或者中心點(diǎn)的位置變化小于閾值
優(yōu)點(diǎn):
- 原理簡(jiǎn)單,實(shí)現(xiàn)起來比較容易
- 收斂速度較快,聚類效果較優(yōu)
缺點(diǎn):
- 初始中心點(diǎn)的選取具有隨機(jī)性,可能會(huì)選取到不好的初始值。
k-means++原理
k-means++是k-means的增強(qiáng)版,它初始選取的聚類中心點(diǎn)盡可能的分散開來,這樣可以有效減少迭代次數(shù),加快運(yùn)算速度,實(shí)現(xiàn)步驟如下:
- 從樣本中隨機(jī)選取一個(gè)點(diǎn)作為聚類中心
- 計(jì)算每一個(gè)樣本點(diǎn)到已選擇的聚類中心的距離,用D(X)表示:D(X)越大,其被選取下一個(gè)聚類中心的概率就越大
- 利用輪盤法的方式選出下一個(gè)聚類中心(D(X)越大,被選取聚類中心的概率就越大)
- 重復(fù)步驟2,直到選出k個(gè)聚類中心
- 選出k個(gè)聚類中心后,使用標(biāo)準(zhǔn)的k-means算法聚類
這里不得不說明一點(diǎn),有的文獻(xiàn)中把與已選擇的聚類中心最大距離的點(diǎn)選作下一個(gè)中心點(diǎn),這個(gè)說法是不太準(zhǔn)確的,準(zhǔn)的說是與已選擇的聚類中心最大距離的點(diǎn)被選作下一個(gè)中心點(diǎn)的概率最大,但不一定就是改點(diǎn),因?yàn)榭偸侨∽畲笠膊惶茫ㄓ龅教厥鈹?shù)據(jù),比如有一個(gè)點(diǎn)離某個(gè)聚類所有點(diǎn)都很遠(yuǎn))。
一般初始化部分,始終要給些隨機(jī)。因?yàn)閿?shù)據(jù)是隨機(jī)的。
盡管計(jì)算初始點(diǎn)時(shí)花費(fèi)了額外的時(shí)間,但是在迭代過程中,k-mean 本身能快速收斂,因此算法實(shí)際上降低了計(jì)算時(shí)間。
現(xiàn)在重點(diǎn)是利用輪盤法的方式選出下一個(gè)聚類中心,我們以一個(gè)例子說明K-means++是如何選取初始聚類中心的。
假如數(shù)據(jù)集中有8個(gè)樣本,分布分布以及對(duì)應(yīng)序號(hào)如下圖所示:
我們先用 k-means++的步驟1選擇6號(hào)點(diǎn)作為第一個(gè)聚類中心,然后進(jìn)行第二步,計(jì)算每個(gè)樣本點(diǎn)到已選擇的聚類中心的距離D(X),如下所示:
- D(X)是每個(gè)樣本點(diǎn)與所選取的聚類中心的距離(即第一個(gè)聚類中心)
- P(X)每個(gè)樣本被選為下一個(gè)聚類中心的概率
- Sum是概率P(x)的累加和,用于輪盤法選擇出第二個(gè)聚類中心。
然后執(zhí)行 k-means++的第三步:利用輪盤法的方式選出下一個(gè)聚類中心,方法是隨機(jī)產(chǎn)生出一個(gè)0~1之間的隨機(jī)數(shù),判斷它屬于哪個(gè)區(qū)間,那么該區(qū)間對(duì)應(yīng)的序號(hào)就是被選擇出來的第二個(gè)聚類中心了。
在上圖1號(hào)點(diǎn)區(qū)間為[0,0.2),2號(hào)點(diǎn)的區(qū)間為[0.2, 0.525),4號(hào)點(diǎn)的區(qū)間為[0.65,0.9)
從上表可以直觀的看到,1號(hào),2號(hào),3號(hào),4號(hào)總的概率之和為0.9,這4個(gè)點(diǎn)正好是離第一個(gè)初始聚類中心(即6號(hào)點(diǎn))較遠(yuǎn)的四個(gè)點(diǎn),因此選取的第二個(gè)聚類中心大概率會(huì)落在這4個(gè)點(diǎn)中的一個(gè),其中2號(hào)點(diǎn)被選作為下一個(gè)聚類中心的概率最大。
k-means及k-means++代碼實(shí)現(xiàn)
這里選擇的中心點(diǎn)是樣本的特征(不是索引),這樣做是為了方便計(jì)算,選擇的聚類點(diǎn)(中心點(diǎn)周圍的點(diǎn))是樣本的索引。
k-means實(shí)現(xiàn)
# 定義歐式距離 import numpy as np def get_distance(x1, x2): return np.sqrt(np.sum(np.square(x1-x2)))
import random # 定義中心初始化函數(shù),中心點(diǎn)選擇的是樣本特征 def center_init(k, X): n_samples, n_features = X.shape centers = np.zeros((k, n_features)) selected_centers_index = [] for i in range(k): # 每一次循環(huán)隨機(jī)選擇一個(gè)類別中心,判斷不讓centers重復(fù) sel_index = random.choice(list(set(range(n_samples))-set(selected_centers_index))) centers[i] = X[sel_index] selected_centers_index.append(sel_index) return centers
# 判斷一個(gè)樣本點(diǎn)離哪個(gè)中心點(diǎn)近, 返回的是該中心點(diǎn)的索引 ## 比如有三個(gè)中心點(diǎn),返回的是0,1,2 def closest_center(sample, centers): closest_i = 0 closest_dist = float('inf') for i, c in enumerate(centers): # 根據(jù)歐式距離判斷,選擇最小距離的中心點(diǎn)所屬類別 distance = get_distance(sample, c) if distance < closest_dist: closest_i = i closest_dist = distance return closest_i
# 定義構(gòu)建聚類的過程 # 每一個(gè)聚類存的內(nèi)容是樣本的索引,即對(duì)樣本索引進(jìn)行聚類,方便操作 def create_clusters(centers, k, X): clusters = [[] for _ in range(k)] for sample_i, sample in enumerate(X): # 將樣本劃分到最近的類別區(qū)域 center_i = closest_center(sample, centers) # 存放樣本的索引 clusters[center_i].append(sample_i) return clusters
# 根據(jù)上一步聚類結(jié)果計(jì)算新的中心點(diǎn) def calculate_new_centers(clusters, k, X): n_samples, n_features = X.shape centers = np.zeros((k, n_features)) # 以當(dāng)前每個(gè)類樣本的均值為新的中心點(diǎn) for i, cluster in enumerate(clusters): # cluster為分類后每一類的索引 new_center = np.mean(X[cluster], axis=0) # 按列求平均值 centers[i] = new_center return centers
# 獲取每個(gè)樣本所屬的聚類類別 def get_cluster_labels(clusters, X): y_pred = np.zeros(np.shape(X)[0]) for cluster_i, cluster in enumerate(clusters): for sample_i in cluster: y_pred[sample_i] = cluster_i #print('把樣本{}歸到{}類'.format(sample_i,cluster_i)) return y_pred
# 根據(jù)上述各流程定義kmeans算法流程 def Mykmeans(X, k, max_iterations,init): # 1.初始化中心點(diǎn) if init == 'kmeans': centers = center_init(k, X) else: centers = get_kmeansplus_centers(k, X) # 遍歷迭代求解 for _ in range(max_iterations): # 2.根據(jù)當(dāng)前中心點(diǎn)進(jìn)行聚類 clusters = create_clusters(centers, k, X) # 保存當(dāng)前中心點(diǎn) pre_centers = centers # 3.根據(jù)聚類結(jié)果計(jì)算新的中心點(diǎn) new_centers = calculate_new_centers(clusters, k, X) # 4.設(shè)定收斂條件為中心點(diǎn)是否發(fā)生變化 diff = new_centers - pre_centers # 說明中心點(diǎn)沒有變化,停止更新 if diff.sum() == 0: break # 返回最終的聚類標(biāo)簽 return get_cluster_labels(clusters, X)
# 測(cè)試執(zhí)行 X = np.array([[0,2],[0,0],[1,0],[5,0],[5,2]]) # 設(shè)定聚類類別為2個(gè),最大迭代次數(shù)為10次 labels = Mykmeans(X, k = 2, max_iterations = 10,init = 'kmeans') # 打印每個(gè)樣本所屬的類別標(biāo)簽 print("最后分類結(jié)果",labels) ## 輸出為 [1. 1. 1. 0. 0.]
# 使用sklearn驗(yàn)證 from sklearn.cluster import KMeans X = np.array([[0,2],[0,0],[1,0],[5,0],[5,2]]) kmeans = KMeans(n_clusters=2,init = 'random').fit(X) # 由于center的隨機(jī)性,結(jié)果可能不一樣 print(kmeans.labels_)
k-means++實(shí)現(xiàn)
## 得到kmean++中心點(diǎn) def get_kmeansplus_centers(k, X): n_samples, n_features = X.shape init_one_center_i = np.random.choice(range(n_samples)) centers = [] centers.append(X[init_one_center_i]) dists = [ 0 for _ in range(n_samples)] # 執(zhí)行 for _ in range(k-1): total = 0 for sample_i,sample in enumerate(X): # 得到最短距離 closet_i = closest_center(sample,centers) d = get_distance(X[closet_i],sample) dists[sample_i] = d total += d total = total * np.random.random() for sample_i,d in enumerate(dists): # 輪盤法選出下一個(gè)聚類中心 total -= d if total > 0: continue # 選取新的中心點(diǎn) centers.append(X[sample_i]) break return centers
X = np.array([[0,2],[0,0],[1,0],[5,0],[5,2]]) # 設(shè)定聚類類別為2個(gè),最大迭代次數(shù)為10次 labels = Mykmeans(X, k = 2, max_iterations = 10,init = 'kmeans++') print("最后分類結(jié)果",labels) ## 輸出為 [1. 1. 1. 0. 0.]
# 使用sklearn驗(yàn)證 X = np.array([[0,2],[0,0],[1,0],[5,0],[5,2]]) kmeans = KMeans(n_clusters=2,init='k-means++').fit(X) print(kmeans.labels_)
參考文檔
K-means與K-means++
K-means原理、優(yōu)化及應(yīng)用
到此這篇關(guān)于python中k-means和k-means++原理及實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)python k-means和k-means++ 內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
對(duì)python For 循環(huán)的三種遍歷方式解析
今天小編就為大家分享一篇對(duì)python For 循環(huán)的三種遍歷方式解析,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2019-02-02Linux 發(fā)郵件磁盤空間監(jiān)控(python)
這篇文章主要介紹了Linux發(fā)郵件磁盤空間監(jiān)控功能,python實(shí)現(xiàn),需要的朋友可以參考下2016-04-04python實(shí)現(xiàn)自主查詢實(shí)時(shí)天氣
這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)自主查詢實(shí)時(shí)天氣,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2018-06-06淺談python中頻繁的print到底能浪費(fèi)多長(zhǎng)時(shí)間
今天小編就為大家分享一篇淺談python中頻繁的print到底能浪費(fèi)多長(zhǎng)時(shí)間,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-02-02python文件轉(zhuǎn)為exe文件的方法及用法詳解
py2exe是一個(gè)將python腳本轉(zhuǎn)換成windows上的可獨(dú)立執(zhí)行的可執(zhí)行程序(*.exe)的工具,這樣,你就可以不用裝python而在windows系統(tǒng)上運(yùn)行這個(gè)可執(zhí)行程序。本文重點(diǎn)給大家介紹python文件轉(zhuǎn)為exe文件的方法,感興趣的朋友跟隨小編一起看看吧2019-07-07python實(shí)現(xiàn)簡(jiǎn)易淘寶購(gòu)物
這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)簡(jiǎn)易淘寶購(gòu)物,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2019-11-11報(bào)錯(cuò)No?module?named?numpy問題的解決辦法
之前安裝了Python,后來因?yàn)榫毩?xí)使用Python寫科學(xué)計(jì)算的東西,又安裝了Anaconda,但是安裝Anaconda之后又出現(xiàn)了一個(gè)問題,下面這篇文章主要給大家介紹了關(guān)于報(bào)錯(cuò)No?module?named?numpy問題的解決辦法,需要的朋友可以參考下2022-08-08