作者：堅新

研究方向：自然語言處理

https://github.com/yangjianxin1/PAMAE

---

編者按：AINLP技術群的堅新同學發(fā)布了一個新項目：PAMAE (PAMAE: Parallel k-Medoids Clustering with High Accuracy and Efficiency論文復現(xiàn)?)，以下是來自該項目的詳細介紹，歡迎Star。

---

項目介紹

PAMAE: Parallel k-Medoids Clustering with High Accuracy and Efficiency 是SIGKDD2017一篇關于k-medoids并行聚類的論文，論文中作者使用Spark與Hadoop實現(xiàn)算法的并行化，而本項目使用python并行編程模擬MapReduce的并行，對該論文算法的思想進行復現(xiàn)。

使用本項目復現(xiàn)的代碼對中心數(shù)量分別為5、10、15、20的數(shù)據(jù)集進行聚類的效果圖如下(數(shù)據(jù)集大小為1萬)

使用方法

直接運行如下命令即可，程序會使用默認參數(shù)，生成一個數(shù)據(jù)集，并對該數(shù)據(jù)集執(zhí)行聚類算法

python pamae.py

也可以指定如下參數(shù)：

• n_points：生成的數(shù)據(jù)的個數(shù)，默認為10000

• subset_size：phase 1中采樣后子集的大小，默認為100

• subset_num：phase 1中采樣的子集的數(shù)量 ，默認為5

• centroid_num：簇中心的數(shù)量 ，默認為10

python pamae.py --n_points 10000 --subset_size 100 --subset_num 5 --centroid_num 10

程序產(chǎn)生的Phase 1與Phase 2的聚類結果圖，會保存在根目錄的results文件夾下，命名方式為"phase[1|2]_數(shù)據(jù)集大小_采樣子集大小_采樣子集數(shù)量_中心數(shù)量"，并且在控制臺輸出每個階段的的中心集合、耗時、聚類誤差等數(shù)據(jù)

背景介紹

聚類就是將數(shù)據(jù)集劃分為多個簇(cluster)，每個簇由若干相似對象組成，使得同一個簇中對象間的相似度最大化，不同簇中對象間的相似度最小化。其中k-means與k-medoids是最基礎的兩種聚類算法

k-means算法選擇簇中所有對象的均值作為簇的中心，因此k-means算法實現(xiàn)簡單、時間復雜度低，但其對噪聲和離群點很敏感

k-medoids算法則是選擇離簇均值最近的對象作為簇中心。所以k-medoids算法對噪聲和離群點更具魯棒性，但其時間復雜度卻很高。

k-meansk-medoids

優(yōu)點	實現(xiàn)簡單、時間復雜度低	對噪聲和離群點更具魯棒性
缺點	對噪聲和離群點很敏感	時間復雜度高

k-means算法

算法簡介：k-means算法采用簇中所有對象的均值作為簇中心。給定劃分的簇的數(shù)量k。隨機選擇k個對象作為k個簇中心，將剩余對象指派到距離最近的簇，然后重新計算每個簇的新均值，得到更新后的簇中心。不斷重復上述步驟，直到簇中心不再發(fā)生變化。

k-means算法偽代碼如下：

輸入：數(shù)據(jù)集D，劃分簇的個數(shù)k
輸出：k個簇的集合
從數(shù)據(jù)集D中任意選擇k個對象作為初始簇中心
repeat
for 數(shù)據(jù)集D中每個對象P do
計算對象P到k個簇中心的距離
將對象P指派到與其最近(距離最短)的簇
end for
計算每個簇中對象的均值，以該均值點作為新的簇的中心
until k個簇的簇中心不再發(fā)生變化

k-means算法示意圖如下：

PAM算法

算法簡介：PAM算法是k-medoids算法的變種，PAM算法并不是采用簇的均值作為簇中心，而是選擇簇中距平均值最近的對象作為簇中心

聚類誤差S：所以對象到其簇中心的距離之和

PAM算法偽代碼如下：

輸入：數(shù)據(jù)集D，劃分簇的個數(shù)k
輸出：k個簇的集合
從數(shù)據(jù)集D中任意選擇k個對象作為初始簇中心
repeat
把剩余對象分配到距離最近的簇中心
對于所有(中心點C，非中心點P)的二元組。嘗試將中心點與非中心點交換，并計算聚類誤差
若交換之后聚類誤差降低了，則使用該非中心點替換中心點
until k個簇的簇中心不再發(fā)生變化

PAM算法示意圖如下：

研究現(xiàn)狀

盡管k-medoids具有更好的魯棒性，但是由于其計算復雜度過高，所以人們用的主要還是k-means算法。有許多研究者嘗試解決k-medoids算法的效率問題， 但基本都是以算法準確率作為代價，也就是說現(xiàn)有研究都沒能很好地解決k-medoids算法的效率與準確率之間的矛盾。

解決k-medoids算法效率問題的各種舉措可以按照以下三個維度進行劃分

通過上表，我們可以清楚看到

• global search與entire data的使用可以提高算法的準確率，但會降低算法的效率

• sampled data與local search的使用可以提高算法效率，但會降低準確率

論文貢獻

本文嘗試在k-medoids的準確率與效率之間找到一個平衡點，于是作者提出了一個基于k-medoids的并行聚類算法(PAMAE)，算法分為兩個階段，每個階段都使用Spark和Hadoop實現(xiàn)并行處理，提高算法的效率：

• 在第一階段采用sampled data與global search策略

• 在第二階段采用entire data與local search策略

進行以上組合的原因：global search與entire data策略的使用可以提高算法的準確率，但同時使用，必定會降低算法的效率。而entire data與local search策略可以提高算法的效率，但同時使用，也必定會降低算法的準確率。因此作者在四者的組合中找到了一個平衡點，即sampled data+global search與entire data+local search。

第一階段的sampled data可以提高算法效率，global search可以提高算法準確率，這是一個高效率+高準確率的組合。

第二階段的entire data可以提高算法準確率，local search可以提高效率，也是一個高效率+高準確率的組合。

可以發(fā)現(xiàn)每個階段都是高效率+高準確率的組合，PAMAE算法就是通過這種“一快一準”的策略組合，再加上MapReduce的并行處理，以達到高效率和高準確率之間的平衡

PAMAE算法描述

PAMAE算法分為如下兩個階段

Phase 1

算法思想：對整個數(shù)據(jù)集進行隨機采樣(sampled data )，生成m個規(guī)模為n的子集。然后對m個子集并行執(zhí)行PAM算法(global search)，計算整個數(shù)據(jù)集的聚類誤差，選擇聚類誤差最小的中心集合

算法流程：

對整個數(shù)據(jù)集進行隨機采樣，生成m個規(guī)模為n的子集substes
for subset in subsets:
使用global search策略(這里使用PAM算法)找到子集subset的k個簇中心
將整個數(shù)據(jù)集Entire data的每個數(shù)據(jù)劃分到距離最近的簇中心
計算聚類誤差(每個數(shù)據(jù)點到其簇中心的距離之和)
選擇聚類誤差最小的一組中心集合輸入到Phase2

注：對于for循環(huán)里每個子集的聚類與計算聚類誤差的操作，是并行的

第一階段的算法示意圖如下：

Phase 2

經(jīng)過Phase 1的步驟，已經(jīng)得到了一個近似的聚類中心集合，但是Phase 1中的中心集合是從sampled data中得到的，因此可能與真實的中心還存在一定的偏差，第二階段就是為了對第一階段生成的中心集合進行微調

算法思想：對于Phase 1獲得的中心集合，將整個數(shù)據(jù)集的數(shù)據(jù)劃分到距離最近的簇中心，然后并行更新每個簇的中心，以達到對簇中心進行微調的目的。得到的就是最終的k個簇中心

第二階段的算法示意圖如下：

實驗結果

數(shù)據(jù)集大小為1萬，不同中心數(shù)量的數(shù)據(jù)集，第一階段和第二階段聚類結果如下所示。可以看到，經(jīng)過Phase 1得到的聚類效果已經(jīng)很不錯，再經(jīng)過Phase 2微調之后，聚類效果也確實有所提高。

簇中心數(shù)量為5：

簇中心數(shù)量為10：

簇中心數(shù)量為15：

簇中心數(shù)量為20：

不足

本項目使用python的并行編程模擬Spark與Hadoop的MapReduce并行計算，運算速度不如MapReduce。由于Phase 1采用的是Global search的策略，運算復雜度較高，當采樣子集規(guī)模較大時，Phase 1的耗時會增大。

---

推薦閱讀

AINLP年度閱讀收藏清單

用于中文閑聊的GPT2模型：GPT2-chitchat

中文歌詞生成，缺不缺語料？這里有一個開源項目值得推薦

Nvidia League Player：來呀比到天荒地老

我們建了一個免費的知識星球：AINLP芝麻街，歡迎來玩，期待一個高質量的NLP問答社區(qū)

征稿啟示| 讓更多的NLPer看到你的文章

AINLP-DBC GPU 云服務器租用平臺建立，價格足夠便宜

關于AINLP

AINLP 是一個有趣有AI的自然語言處理社區(qū)，專注于 AI、NLP、機器學習、深度學習、推薦算法等相關技術的分享，主題包括文本摘要、智能問答、聊天機器人、機器翻譯、自動生成、知識圖譜、預訓練模型、推薦系統(tǒng)、計算廣告、招聘信息、求職經(jīng)驗分享等，歡迎關注！加技術交流群請?zhí)砑覣INLP君微信(id：AINLP2)，備注工作/研究方向+加群目的。

總結

以上是生活随笔為你收集整理的python生成簇_使用Python复现SIGKDD2017的PAMAE算法(并行kmedoids算法)的全部內容，希望文章能夠幫你解決所遇到的問題。

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