Python Monte Carlo K-Means聚類實戰(zhàn)研究|附代碼數(shù)據(jù)
原文鏈接：http://tecdat.cn/?p=6689?
最近我們被客戶要求撰寫關(guān)于聚類的研究報告，包括一些圖形和統(tǒng)計輸出。
在本文中，188個國家基于這19個社會經(jīng)濟指標(biāo)聚集在一起，使用Python實現(xiàn)的蒙特卡羅K-Means聚類算法。通過將類似國家分組在一起并對其進行概括，聚類可以減少發(fā)現(xiàn)有吸引力投資機會所需的工作量
在討論聚類國家和得出結(jié)論的結(jié)果之前，本文詳細(xì)介紹了距離度量，聚類質(zhì)量測量，聚類算法，K-Means聚類算法。
聚類理論 - 相似與距離的度量
聚類是將一組異構(gòu)（不同）對象劃分為同類（相似）對象的子集的過程。聚類分析的核心是假設(shè)給定任何兩個對象，您可以量化這些對象之間的相似性或不相似性。在連續(xù)搜索空間中距離測量相似性。
下面我寫了關(guān)于連續(xù)搜索空間的相似性度量。
class?Similarity:?????def?__init__(self,?minimum):????????self.e?=?minimum????????self.vector_operators?=?VectorOperations()????def?manhattan_distance(self,?p_vec,?q_vec):????????"""????????這個方法實現(xiàn)了曼哈頓距離的度量????????:param?p_vec:?矢量一????????:param?q_vec:?向量二????????:返回：向量一和二之間的曼哈頓距離????????"""????????return?max(np.sum(np.fabs(p_vec?-?q_vec)),?self.e)????def?square_euclidean_distance(self,?p_vec,?q_vec):????????"""????????這個方法實現(xiàn)了平方歐幾里得距離指標(biāo)????????:param?p_vec:?向量一????????:param?q_vec:?向量二????????:返回：向量一和向量二之間的平方歐幾里得距離????????"""????????diff?=?p_vec?-?q_vec????????return?max(np.sum(diff?**?2),?self.e)
聚類理論 - 聚類算法類
聚類算法的兩個主要類別是分層聚類和分區(qū)聚類。分層聚類通過將小聚類合并為較大的聚類或?qū)⑤^大的聚類分成較小的聚類來形成聚類。分區(qū)聚類通過將輸入數(shù)據(jù)集劃分為互斥的子集來形成聚類。
分層和分區(qū)聚類之間的差異主要與所需的輸入有關(guān)。分層聚類僅需要相似性度量，而分區(qū)聚類可能需要許多額外的輸入，最常見的是簇的數(shù)量。一般而言，分層聚類算法也更適合于分類數(shù)據(jù)。
分層聚類
有兩種類型的層次聚類，即凝聚聚類和分裂聚類。凝聚聚類是一種自下而上的方法，涉及將較小的聚類（每個輸入模式本身）合并為更大的聚類。分裂聚類是一種自上而下的方法，從一個大型集群（所有輸入模式）開始，并將它們分成越來越小的集群，直到每個輸入模式本身都在集群中。
分區(qū)聚類
在本文中，我們將重點介紹分區(qū)聚類算法。分區(qū)聚類算法的兩個主要類別是??基于質(zhì)心的聚類??和??基于密度的聚類。本文重點介紹基于質(zhì)心的聚類;?特別是流行的K-means聚類算法。
聚類理論 - K-Means聚類算法
K-Means聚類算法是一種基于質(zhì)心的分區(qū)聚類算法。K均值聚類算法包括三個步驟（初始化，分配和更新）。重復(fù)這些步驟，直到聚類已經(jīng)收斂或已經(jīng)超過迭代次數(shù)。
初始化
在搜索空間中隨機初始化一組質(zhì)心。這些質(zhì)心必須與聚類的數(shù)據(jù)模式處于同一數(shù)量級。換句話說，如果數(shù)據(jù)模式中的值介于0到100之間，則初始化值介于0和1之間的隨機向量是沒有意義的。?
分配
一旦質(zhì)心在空間中被隨機初始化，我們迭代數(shù)據(jù)集中的每個模式并將其分配給最近的質(zhì)心。嘗試并行執(zhí)行此步驟，尤其是在數(shù)據(jù)集中有大量模式的情況下。
更新
一旦將模式分配給它們的質(zhì)心，就應(yīng)用均值漂移啟發(fā)式。此啟發(fā)式替換每個質(zhì)心中的每個值，并將該值的平均值替換為已分配給該質(zhì)心的模式。這將質(zhì)心移向?qū)儆谒膱D案的高維平均值。均值漂移啟發(fā)式問題在于它對異常值敏感。為了克服這個問題，可以使用K-medoids聚類算法??，也可以使用??標(biāo)準(zhǔn)化數(shù)據(jù)來抑制異常值的影響，
迭代
重復(fù)這三個步驟進行多次迭代，直到聚類已經(jīng)收斂于解決方案。一個非常好的GIF顯示如下所示，
PYTHON代碼 - 聚類類的補充
下面的Python方法是Clustering類的擴展，它允許它執(zhí)行K-means聚類算法。這涉及使用均值漂移啟發(fā)式更新質(zhì)心。
聚類理論 - 聚類質(zhì)量的度量
假設(shè)您有一定的相似度和數(shù)據(jù)聚類，您仍然需要一個目標(biāo)函數(shù)來衡量該聚類的質(zhì)量。大多數(shù)群集質(zhì)量指標(biāo)都嘗試根據(jù)群集間和群集內(nèi)距離來優(yōu)化群集。簡單地說，這些指標(biāo)確保同一集群中的模式緊密相關(guān)，不同集群中的模式相差甚遠。
量化誤差
量化誤差測量由量化引入的舍入誤差，即將一組輸入值映射到有限的較小集合。這基本上是我們通過將模式聚類到_k個_集群中所做的事情。?
注意：圖像假設(shè)我們使用曼哈頓距離。
在量化誤差的上述說明中，我們計算每個模式與其分配的質(zhì)心之間的平方絕對距離之和。
Davies-Bouldin指數(shù)
戴維斯-爾丁標(biāo)準(zhǔn)是基于一個特定的聚類的簇內(nèi)和簇間的距離比。?
注意：圖像假設(shè)我們使用曼哈頓距離。
在Davies-Bouldin指數(shù)的上圖中，我們有三個由三個模式組成的集群。
剪影指數(shù)
該??剪影指數(shù))是衡量一個特定的聚類質(zhì)量的最流行的方式之一。它衡量每個模式與其自身集群中的模式的相似程度，與其他集群中的模式進行比較。
def?silhouette_index(self,?index):?????????????#?存儲到每個集群的總距離????????silhouette_totals?=?[]????????#?存儲每個簇中的數(shù)量????????silhouette_counts?=?[]????????#?初始化這些變量????????for?i?in?range(solution.num_clusters):????????????silhouette_totals.append(0.0)????????????silhouette_counts.append(0.0)????????for?i?in?range(len(self.solution.pattern)):????????????#?對于除我們現(xiàn)在計算的模式之外的每個模式????????????如果i != index。????????????????#?得到pattern[index]與該圖案之間的距離????????????????distance?=?s.fractional_distance(self.solution.patterns[i],?????????????????#?將該距離添加到正確群集的剪影總數(shù)中??????????????? silhouette_totals[self.solution.solution[i]]?+= distance。+=?距離????????????????#?更新該簇中的圖案數(shù)量????????????????silhouette_counts[self.solution.solution[i]]?+=?1?+=?1????????#?設(shè)置變量以找到距離最小的集群（不等于圖案[索引]的集群）。????????smallest_silhouette?=?silhouette_totals[0]?/?max(1.0,?silhouette_counts[0])????????for?i?in?range(len(silhouette_totals)):????????????#?從pattern[index]中計算出該簇中每個圖案的平均距離????????????silhouette?=?silhouette_totals[i]?/?max(1.0,?silhouette_counts[i])????????????#?如果平均距離較低，并且不是pattern[index]集群，則更新該值????????????如果?silhouette?<?smallest_silhouette?and?i?!=?self.solution.solution[index]:????????????????Smallest_silhouette?=?silhouette????????#?計算模式[index]的內(nèi)部集群距離????????index_silhouette?=?self.e?+?silhouette_totals[index_cluster]?/?max(1.0,?silhouette_counts[index_cluster]?)????????#?返回pattern[index]與另一個簇的圖案的最小距離之間的比率，并且????????#?該圖案與pattern[index]屬于同一集群
高輪廓值表示?? 與其自己的簇很好地匹配，并且與相鄰簇很不匹配。
注意：圖像還假設(shè)我們使用曼哈頓距離。
在使用這些指標(biāo)過去幾個月后，我得出的結(jié)論是，它們都不是完美的，
量化誤差?- 該度量的計算復(fù)雜度最小，但是度量偏向大量群集，因為當(dāng)您添加更多質(zhì)心時，群集會變得更小（更緊湊），并且在極端情況下，您可能會為每個群集分配一個模式質(zhì)心。在這種情況下，量化誤差被最小化。結(jié)果是最可信??的。
戴維斯 - 布爾丁?- 隨著你增加的值，每個質(zhì)心之間的距離平均會自然減少。因為這個術(shù)語在分母中，所以對于較大的值，最終除以較小的數(shù)字?。其結(jié)果是度量偏向于具有較少數(shù)量的簇的解決方案。
Silhouette Index?- 這個指標(biāo)的計算復(fù)雜性很大。假設(shè)您計算從每個模式到每個其他模式的距離，以計算哪個簇最接近，并且您為每個模式執(zhí)行此操作。在這個例子中，相當(dāng)于35,156次計算。
以下對不同指標(biāo)的分析很好地證明了這些偏差;?盡管事實上他們應(yīng)該測量相同的東西，但他們幾乎完全是負(fù)相關(guān)的。
XQED BSIQE1.0-0.965-0.894SB-0.9651.00.949SI-0.8940.9491.0
PYTHON代碼 - 聚類
在評估給定聚類的適應(yīng)性之前，您需要實際聚類模式。Clustering類包含將模式分配給最近的質(zhì)心的方法。
PYTHON代碼 - 目標(biāo)函數(shù)
ClusteringQuality類測量給定輸入模式的聚類的質(zhì)量。
聚類理論 - 聚類中的蒙特卡羅方法
K-Means聚類算法的兩個最大問題是：
它對質(zhì)心的隨機初始化很敏感
初始化的質(zhì)心數(shù)，k
由于這些原因，K-means聚類算法經(jīng)常重啟多次。因為初始化（通常）是隨機的，所以我們基本上對質(zhì)心的隨機高維起始位置進行采樣，這也稱為蒙特卡羅模擬。為了比較獨立模擬的解決方案，我們需要衡量集群質(zhì)量，例如前面討論過的那些。
確定性初始化
我說初始化通常是隨機的，因為K-Means聚類算法有確定性初始化技術(shù)。
隨機初始化
不同之處在于偽隨機序列中的下一個隨機數(shù)與先前的隨機數(shù)_無關(guān)_，而在準(zhǔn)隨機數(shù)序列中，下一個隨機數(shù)_取決于_先前的隨機數(shù)。相關(guān)隨機數(shù)覆蓋搜索空間的更大面積。
比較二維空間中的偽隨機序列（左）和準(zhǔn)隨機序列（右）
選擇正確的K
除了測試不同的初始化之外，我們還可以在蒙特卡羅框架中測試不同的值k。目前，沒有動態(tài)確定正確數(shù)量的聚類的最佳方式，盡管_總是_正在研究用于確定正確k值的技術(shù)。我更愿意只是憑經(jīng)驗嘗試不同的_k_值并比較結(jié)果，盡管這很費時，特別是在大型數(shù)據(jù)集上。
聚類結(jié)果 - 可視化和質(zhì)心分析
歐幾里德距離和量化誤差是蒙特卡羅K均值聚類中使用的距離和質(zhì)量度量。數(shù)據(jù)集是2014年的標(biāo)準(zhǔn)化時間點數(shù)據(jù)集，其中包括19個與實際GDP增長正相關(guān)的社會經(jīng)濟指標(biāo)。
群集細(xì)分和質(zhì)心分析
下面的每個標(biāo)簽都將集群分解為屬于它的國家，并將質(zhì)心與我們聚集的19個社會經(jīng)濟指標(biāo)中的每一個的中心質(zhì)心進行比較。
2014年該群組中的國家/地區(qū)
聚類結(jié)果 - 結(jié)論和進一步研究
量化不是風(fēng)險管理，衍生品定價或算法交易;?它是關(guān)于挑戰(zhàn)事情的方式，通常使用統(tǒng)計和計算方法找到更好的方法。
2004年，美國是一個異常值，并且自己占據(jù)了一個集群。該集群的特點是PPP的匯率低，進口高，出口高，家庭支出高，工業(yè)生產(chǎn)高，政府收入相對較高，特別是在健康方面。在這個時間點，最大的差異：中國發(fā)生的投資數(shù)量要大得多，而且人口（人口在15到64歲之間）更多。在工業(yè)生產(chǎn)方面，中國也超過了美國。這些在下面的比較中顯示，
金磚四國（巴西，俄羅斯，印度，中國和南非）顯然更多地受到政治經(jīng)濟的驅(qū)動，而不是實際經(jīng)濟。以下是我的看法，
東歐與西歐?- 第一組中的國家與第五組和第二組中的國家之間似乎有明顯的區(qū)別。過去十年來，西班牙，愛爾蘭，捷克共和國和其他附近國家發(fā)生了變化。這可能是主權(quán)債務(wù)危機的結(jié)果。
東西方國家?- 大多數(shù)亞洲國家占據(jù)不同的集群，而美國和英國等傳統(tǒng)的西方國家實際上并不占據(jù)同一集群。
金磚四國?- 巴西，俄羅斯，印度，中國和南非屬于不同的集群。雖然他們可能已達成貿(mào)易協(xié)議，但這并不意味著這些國家具有相同的社會，人口和經(jīng)濟構(gòu)成或未來實際GDP增長的相同潛力。
非洲增長故事?- 雖然資本市場在過去十年中表現(xiàn)良好，但這似乎并沒有反映出非洲大陸的社會，人口和經(jīng)濟構(gòu)成的重大變化。有趣的是，印度和巴基斯坦不再與中非和南非國家聚集在一起。
北非與南部非洲?- 北非國家（摩洛哥，阿爾及利亞，埃及，利比亞等）與非洲其他國家之間存在明顯區(qū)別。令人驚訝的是，南非現(xiàn)在與這些國家聚集在一起。
新興國家與發(fā)達國家?。
如果您發(fā)現(xiàn)其他有趣的關(guān)系，請評論。由于我們不知道每個社會經(jīng)濟指標(biāo)的相對重要性，因此無法量化在一個集群與另一個集群中的有多好。在某些情況下，我們無法確定價值是好還是壞。例如，如果政府效率低下，政府的大筆支出是否仍然有效？盡管如此，我還是構(gòu)建一個度量標(biāo)準(zhǔn)來對每個集群進行排名：
排名=出口+家庭支出+進口+改善衛(wèi)生+改善水+人口+ 15歲至64歲人口增長+總投資+城市百分比+手機訂閱+政府收入+政府支出+醫(yī)療支出+工業(yè)生產(chǎn)+互聯(lián)網(wǎng)用戶 - PPP的匯率 - 失業(yè)率 - 年齡依賴率
根據(jù)此指標(biāo)，每個群集的相對排名如下所示，
簇排名值秩計數(shù)610.2381285.19122215.14632053.82742023.82554543.11163233.0787471.799843
這個排名并不完美，但它再次證實了我們的觀點，即世界是不平等的。
那對投資者意味著什么呢？我認(rèn)為這意味著應(yīng)該在處于不同發(fā)展階段的國家之間作出區(qū)分。這是因為雖然大多數(shù)欠發(fā)達國家代表的是具有最大收益潛力的投資，但它們的風(fēng)險也更大，可能需要更長的時間才能獲得收益。理想情況下，這些因素應(yīng)相互權(quán)衡，與投資者的風(fēng)險收益偏好進行比較。
非常感謝您閱讀本文，有任何問題請在下面留言！
點擊文末?“閱讀原文”
獲取全文完整代碼數(shù)據(jù)資料。
本文選自《Python Monte Carlo K-Means聚類實戰(zhàn)研究》。
點擊標(biāo)題查閱往期內(nèi)容
R語言k-Shape時間序列聚類方法對股票價格時間序列聚類
R語言對用電負(fù)荷時間序列數(shù)據(jù)進行K-medoids聚類建模和GAM回歸
R語言譜聚類、K-MEANS聚類分析非線性環(huán)狀數(shù)據(jù)比較
R語言實現(xiàn)k-means聚類優(yōu)化的分層抽樣(Stratified Sampling)分析各市鎮(zhèn)的人口
R語言聚類有效性：確定最優(yōu)聚類數(shù)分析IRIS鳶尾花數(shù)據(jù)和可視化Python、R對小說進行文本挖掘和層次聚類可視化分析案例
R語言k-means聚類、層次聚類、主成分（PCA）降維及可視化分析鳶尾花iris數(shù)據(jù)集
R語言有限混合模型(FMM,finite mixture model)EM算法聚類分析間歇泉噴發(fā)時間
R語言用溫度對城市層次聚類、kmean聚類、主成分分析和Voronoi圖可視化
R語言k-Shape時間序列聚類方法對股票價格時間序列聚類
R語言中的SOM(自組織映射神經(jīng)網(wǎng)絡(luò))對NBA球員聚類分析
R語言復(fù)雜網(wǎng)絡(luò)分析：聚類（社區(qū)檢測）和可視化
R語言中的劃分聚類模型
基于模型的聚類和R語言中的高斯混合模型
r語言聚類分析：k-means和層次聚類
SAS用K-Means 聚類最優(yōu)k值的選取和分析
用R語言進行網(wǎng)站評論文本挖掘聚類
基于LDA主題模型聚類的商品評論文本挖掘
R語言鳶尾花iris數(shù)據(jù)集的層次聚類分析
R語言對用電負(fù)荷時間序列數(shù)據(jù)進行K-medoids聚類建模和GAM回歸
R語言聚類算法的應(yīng)用實例
