K-Means||算法

K-Means||算法是為了解決K-Means++算法缺點(diǎn)而產(chǎn)生的一種算法；

主要思路是改變每次遍歷時(shí)候的取樣規(guī)則，并非按照K-Means++算法每次遍歷只獲取一個(gè)樣本，而是每次獲取K個(gè)樣本，重復(fù)該取樣操作O(logn)次(n是樣本的個(gè)數(shù))，然后再將這些抽樣出來(lái)的樣本聚類(lèi)出K個(gè)點(diǎn)，最后使用這K個(gè)點(diǎn)作為K-Means算法的初始聚簇中心點(diǎn)。實(shí)踐證明：一般5次重復(fù)采用就可以保證一個(gè)比較好的聚簇中心點(diǎn)。

整體步驟

在N個(gè)樣本中抽K個(gè)樣本，一共抽log(n)次，形成一個(gè)新的樣本集，一共有K*log(n)個(gè)數(shù)據(jù)。

在新數(shù)據(jù)集中使用K-Means算法，找到K個(gè)聚簇中心。

把這K個(gè)聚簇中心放到最初的樣本集中，作為初始聚簇中心。

原數(shù)據(jù)集根據(jù)上述初始聚簇中心，再用K-Means算法計(jì)算出最終的聚簇。

偽代碼

采用了一個(gè)采樣因子l，第1步隨機(jī)初始化一個(gè)中心點(diǎn)，第2-6步計(jì)算出滿(mǎn)足概率條件的多個(gè)候選中心點(diǎn)C，候選中心點(diǎn)的個(gè)數(shù)可能大于k個(gè)，所以通過(guò)第7-8步來(lái)處理。第7步給C中所有點(diǎn)賦予一個(gè)權(quán)重值

，這個(gè)權(quán)重值表示距離x點(diǎn)最近的點(diǎn)的個(gè)數(shù)。第8步使用k-means算法聚類(lèi)出這些候選點(diǎn)的k個(gè)聚類(lèi)中心。

Canopy算法

Canopy算法屬于一種“粗”聚類(lèi)算法，速度較快，但精度較低。 與傳統(tǒng)的聚類(lèi)算法(如K-Means)不同，Canopy聚類(lèi)最大的特點(diǎn)是不需要事先指定k值(即聚類(lèi)的個(gè)數(shù))，因此具有很大的實(shí)際應(yīng)用價(jià)值。

步驟如下：

給定樣本列表 以及初始距離閾值為 (T1、T2可自己定義)；

從列表L中任取一點(diǎn)P，計(jì)算P到所有聚簇中心點(diǎn)的距離(如果不存在聚簇中心，那么就把點(diǎn)P作為一個(gè)新的聚簇)，并選出與聚類(lèi)中心最近的距離 ；

如果距離D小于T1，表示該節(jié)點(diǎn)屬于該聚簇，添加到該聚簇列表中。

如果距離D小于T2，表示該節(jié)點(diǎn)不僅僅屬于該聚簇，還表示和當(dāng)前聚簇中心點(diǎn)非常近，所以將P從列表L中刪除。

如果距離D大于T1，那么節(jié)點(diǎn)P形成一個(gè)新的聚簇。

重復(fù)步驟2-5，直到列表L為空時(shí)結(jié)束循環(huán)。

Canopy算法得到的最終結(jié)果的值，聚簇之間是可能存在重疊的，但是不會(huì)存在某個(gè)對(duì)象不屬于任何聚簇的情況。

Canopy算法過(guò)程圖形說(shuō)明

Canopy+ K-Means聚類(lèi)算法

由于K-Means算法存在初始聚簇中心點(diǎn)敏感的問(wèn)題，常用使用Canopy+K-Means算法進(jìn)行模型構(gòu)建，這種形式聚類(lèi)算法聚類(lèi)效果良好。

步驟

先使用 Canopy算法進(jìn)行“粗”聚類(lèi)得到K個(gè)聚類(lèi)中心點(diǎn)。

再使用K-Means算法，并用Canopy算法得到的K個(gè)聚類(lèi)中心點(diǎn)作為初始中心點(diǎn)，進(jìn)行“細(xì)”聚類(lèi)。

優(yōu)點(diǎn)

執(zhí)行速度快(先進(jìn)行了一次聚簇中心點(diǎn)選擇的預(yù)處理)；

不需要給定K值，應(yīng)用場(chǎng)景多；

能夠緩解K-Means算法對(duì)于初始聚類(lèi)中心點(diǎn)敏感的問(wèn)題。

Mini Batch K-Means算法

Mini Batch K-Means算法是K-Means算法的一種優(yōu)化變種，采用小規(guī)模的數(shù)據(jù)子集(每次訓(xùn)練使用的數(shù)據(jù)集是在訓(xùn)練算法的時(shí)候隨機(jī)抽取的數(shù)據(jù)子集)減少計(jì)算時(shí)間，同時(shí)試圖優(yōu)化目標(biāo)函數(shù)；Mini Batch K-Means算法可以減少K-Means算法的收斂時(shí)間，而且產(chǎn)生的結(jié)果效果只是略差于標(biāo)準(zhǔn)K-Means算法。

算法步驟如下

首先抽取部分?jǐn)?shù)據(jù)集，使用K-Means算法構(gòu)建出K個(gè)聚簇點(diǎn)的模型;

繼續(xù)抽取訓(xùn)練數(shù)據(jù)集中的部分?jǐn)?shù)據(jù)集樣本數(shù)據(jù)，并將其添加到模型中，分配給距離最近的聚簇中心點(diǎn);

更新聚簇的中心點(diǎn)值;

重復(fù)2-3步，直到中心點(diǎn)穩(wěn)定或者達(dá)到迭代次數(shù)為止。

Python實(shí)現(xiàn)

import time import matplotlib.pyplot as plt import matplotlib from sklearn.cluster import MiniBatchKMeans from sklearn.datasets import make_blobs # 導(dǎo)入產(chǎn)生模擬數(shù)據(jù)的方法 matplotlib.rcParams['font.sans-serif'] = [u'SimHei'] matplotlib.rcParams['axes.unicode_minus'] = False# 生成模擬數(shù)據(jù) k = 5 # 給定聚類(lèi)數(shù)量 X, Y = make_blobs(n_samples=1000, n_features=2, centers=k, random_state=1) s = time.time() km = MiniBatchKMeans(n_clusters = k, batch_size = 100) km.fit(X) print("用sklearn內(nèi)置的Mini Batch K-Means算法聚類(lèi)耗時(shí)：", time.time() - s)label_pred = km.labels_ # 獲取聚類(lèi)后的樣本所屬簇對(duì)應(yīng)值 centroids = km.cluster_centers_ # 獲取簇心# 繪制Mini Batch K-Means結(jié)果 # 未聚類(lèi)前的數(shù)據(jù)分布 plt.subplot(121) plt.scatter(X[:, 0], X[:, 1], s=50) plt.title("未聚類(lèi)前的數(shù)據(jù)分布") plt.subplots_adjust(wspace=0.5)plt.subplot(122) plt.scatter(X[:, 0], X[:, 1], c=label_pred, s=50, cmap='viridis') plt.scatter(centroids[:, 0], centroids[:, 1], c='red', marker='o', s=100) plt.title("Mini Batch K-Means算法聚類(lèi)結(jié)果") plt.show()

運(yùn)行結(jié)果

總結(jié)： Mini Batch K-Means 算法比 K-Means 算法運(yùn)行的時(shí)間大大減少，并且效果也差不多。

相關(guān)鏈接

K-Means算法python代碼

聚類(lèi)算法總結(jié)

Canopy聚類(lèi)算法

K-Means||算法

與50位技術(shù)專(zhuān)家面對(duì)面20年技術(shù)見(jiàn)證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的k中心点聚类算法伪代码_聚类算法之——K-Means、Canopy、Mini Batch K-Means的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。