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