Python Monte Carlo K-Means聚類實戰(zhàn)研究
原文鏈接：http://tecdat.cn/?p=6689?
?
在本文中，188個國家基于這19個社會經(jīng)濟指標聚集在一起，使用Python實現(xiàn)的蒙特卡羅K-Means聚類算法。通過將類似國家分組在一起并對其進行概括，聚類可以幫助減少識別有吸引力的投資機會所需的工作量。
在討論聚類國家和得出結論的結果之前，本文詳細介紹了距離度量，聚類質量測量，聚類算法，K-Means聚類算法。?
?
?
聚類理論 - 相似與距離的度量
聚類是將一組異構（不同）對象劃分為同類（相似）對象的子集的過程。聚類分析的核心是假設給定任何兩個對象，您可以量化這些對象之間的相似性或不相似性。在連續(xù)搜索空間中距離測量相似性。
下面我寫了關于連續(xù)搜索空間的相似性度量。對于每個我都包含公式（給定兩個向量，??和q）和Python代碼。用于編寫本文的所有Python代碼都可用。?
?
class Similarity:def __init__(self, minimum):self.e = minimumself.vector_operators = VectorOperations()def manhattan_distance(self, p_vec, q_vec):"""This method implements the manhattan distance metric:param p_vec: vector one:param q_vec: vector two:return: the manhattan distance between vector one and two"""return max(np.sum(np.fabs(p_vec - q_vec)), self.e)def square_euclidean_distance(self, p_vec, q_vec):"""This method implements the squared euclidean distance metric:param p_vec: vector one:param q_vec: vector two:return: the squared euclidean distance between vector one and two"""diff = p_vec - q_vecreturn max(np.sum(diff ** 2), self.e)
聚類理論 - 聚類算法類
聚類算法的兩個主要類別是分層聚類和分區(qū)聚類。分層聚類通過將小聚類合并為較大的聚類或將較大的聚類分成較小的聚類來形成聚類。分區(qū)聚類通過將輸入數(shù)據(jù)集劃分為互斥的子集來形成聚類。
分層和分區(qū)聚類之間的差異主要與所需的輸入有關。分層聚類僅需要相似性度量，而分區(qū)聚類可能需要許多額外的輸入，最常見的是簇的數(shù)量。一般而言，分層聚類算法也更適合于分類數(shù)據(jù)。??
分層聚類
有兩種類型的層次聚類，即凝聚聚類和分裂聚類。凝聚聚類是一種自下而上的方法，涉及將較小的聚類（每個輸入模式本身）合并為更大的聚類。分裂聚類是一種自上而下的方法，從一個大型集群（所有輸入模式）開始，并將它們分成越來越小的集群，直到每個輸入模式本身都在集群中。
分區(qū)聚類
在本文中，我們將重點介紹分區(qū)聚類算法。分區(qū)聚類算法的兩個主要類別是??基于質心的聚類??和??基于密度的聚類。本文重點介紹基于質心的聚類;?特別是流行的K-means聚類算法。
?
?
?
聚類理論 - K-Means聚類算法
K-Means聚類算法是一種基于質心的分區(qū)聚類算法，它使用均值漂移啟發(fā)式算法。K均值聚類算法包括三個步驟（初始化，分配和更新）。重復這些步驟，直到聚類已經(jīng)收斂或已經(jīng)超過迭代次數(shù)，即計算預算已用盡。
初始化
?在搜索空間中隨機初始化一組質心。這些質心必須與聚類的數(shù)據(jù)模式處于同一數(shù)量級。換句話說，如果數(shù)據(jù)模式中的值介于0到100之間，則初始化值介于0和1之間的隨機向量是沒有意義的。?
?
注意：確?？缑總€屬性規(guī)范化數(shù)據(jù)，而不是每個模式
分配
一旦質心在空間中被隨機初始化，我們迭代數(shù)據(jù)集中的每個模式并將其分配給最近的質心。嘗試并行執(zhí)行此步驟，尤其是在數(shù)據(jù)集中有大量模式的情況下。
更新
一旦將模式分配給它們的質心，就應用均值漂移啟發(fā)式。此啟發(fā)式替換每個質心中的每個值，并將該值的平均值替換為已分配給該質心的模式。這將質心移向屬于它的圖案的高維平均值。均值漂移啟發(fā)式問題在于它對異常值敏感。為了克服這個問題，可以使用K-medoids聚類算法??，也可以使用??標準化數(shù)據(jù)來抑制異常值的影響，
?
迭代
重復這三個步驟進行多次迭代，直到聚類已經(jīng)收斂于解決方案。一個非常好的GIF顯示如下所示，
PYTHON代碼 - 聚類類的補充
下面的Python方法是Clustering類的擴展，它允許它執(zhí)行K-means聚類算法。這涉及使用均值漂移啟發(fā)式更新質心。
??
聚類理論 - 聚類質量的度量
假設您有一定的相似度和數(shù)據(jù)聚類，您仍然需要一個目標函數(shù)來衡量該聚類的質量。大多數(shù)群集質量指標都嘗試根據(jù)群集間和群集內(nèi)距離來優(yōu)化群集。簡單地說，這些指標試圖確保同一集群中的模式緊密相連，不同集群中的模式相距甚遠。
量化誤差
量化誤差測量由量化引入的舍入誤差，即將一組輸入值映射到有限的較小集合。這基本上是我們通過將模式聚類到k個集群中所做的事情。?
注意：圖像還假設我們使用曼哈頓距離。?
在量化誤差的上述說明中，我們計算每個模式與其分配的質心之間的平方絕對距離之和。
戴維斯 - 布爾丁指數(shù)
?戴維斯-爾丁標準是基于一個特定的聚類的簇內(nèi)和簇間的距離比。?
注意：圖像假設我們使用曼哈頓距離。?
在Davies-Bouldin指數(shù)的上圖中，我們有三個由三個模式組成的集群。
剪影指數(shù)
該??剪影指數(shù)是衡量一個特定的聚類質量的最流行的方式之一。它衡量每個模式與其自身集群中的模式的相似程度，與其他集群中的模式進行比較。
?
def silhouette_index(self, index):# store the total distance to each clustersilhouette_totals = []# store the number of patterns in each clustersilhouette_counts = []# initialize the variablesfor i in range(self.solution.num_clusters):silhouette_totals.append(0.0)silhouette_counts.append(0.0)s = Similarity(self.e)for i in range(len(self.solution.patterns)):# for every pattern other than the one we are calculating nowif i != index:# get the distance between pattern[index] and that patterndistance = s.fractional_distance(self.solution.patterns[i], self.solution.patterns[index])# add that distance to the silhouette totals for the correct clustersilhouette_totals[self.solution.solution[i]] += distance# update the number of patterns in that clustersilhouette_counts[self.solution.solution[i]] += 1# setup variable to find the cluster (not equal to the pattern[index]'s cluster) with the smallest distancesmallest_silhouette = silhouette_totals[0] / max(1.0, silhouette_counts[0])for i in range(len(silhouette_totals)):# calculate the average distance of each pattern in that cluster from pattern[index]silhouette = silhouette_totals[i] / max(1.0, silhouette_counts[i])# if the average distance is lower and it isn't pattern[index] cluster update the valueif silhouette < smallest_silhouette and i != self.solution.solution[index]:smallest_silhouette = silhouette# calculate the internal cluster distances for pattern[index]index_cluster = self.solution.solution[index]index_silhouette = self.e + silhouette_totals[index_cluster] / max(1.0, silhouette_counts[index_cluster])# return the ratio between the smallest distance from pattern[index] to another cluster's patterns and# the patterns belong to the same cluster as pattern[index]return (smallest_silhouette - index_silhouette) / max(smallest_silhouette, index_silhouette)
高輪廓值表示????與其自己的簇很好地匹配，并且與相鄰簇很不匹配。人們應該致力于為數(shù)據(jù)集中的每個模式最大化小號一世小號一世。
注意：圖像還假設我們使用曼哈頓距離。?
?
在使用這些指標過去幾個月后，我得出的結論是，它們都不是完美的，
量化誤差?- 該度量的計算復雜度最小，但是度量偏向大量群集，因為當您添加更多質心時，群集會變得更?。ǜo湊），并且在極端情況下，您可能會為每個群集分配一個模式質心。在這種情況下，量化誤差被最小化。使用這個指標The Good，結果是最可信??的。
戴維斯 - 布爾丁?- 隨著你增加的值，??每個質心之間的距離平均會自然減少。因為這個術語在分母中，所以對于較大的值，最終除以較小的數(shù)字??。其結果是度量偏向于具有較少數(shù)量的簇的解決方案。
Silhouette Index?- 這個指標的計算復雜性是瘋狂的。假設您計算從每個模式?一世?一世到每個其他模式的距離，以計算哪個簇最接近，并且您為每個模式執(zhí)行此操作，則需要計算|?Z?|?*?|?Z?-1?||?|*|?-?1|距離。在這個例子中，相當于35,156次計算。如果你完美地記憶，每次傳球的計算次數(shù)減半。
以下對不同指標的分析很好地證明了這些偏差;?盡管事實上他們應該測量相同的東西，但他們幾乎完全是負相關的。
?
XQED BSIQE1.0-0.965-0.894SB-0.9651.00.949SI-0.8940.9491.0?
?
PYTHON代碼 - 聚類
在評估給定聚類的適應性之前，您需要實際聚類模式。Clustering類包含將模式分配給最近的質心的方法。
?
PYTHON代碼 - 目標函數(shù)
ClusteringQuality類測量給定輸入模式的聚類的質量。
??
聚類理論 - 聚類中的蒙特卡羅方法
K-Means聚類算法的兩個最大問題是：
它對質心的隨機初始化很敏感
初始化的質心數(shù)，??
由于這些原因，K-means聚類算法經(jīng)常重啟多次。因為初始化（通常）是隨機的，所以我們基本上對質心的隨機高維起始位置進行采樣，這也稱為蒙特卡羅模擬。為了比較獨立模擬的解決方案，我們需要衡量集群質量，例如前面討論過的那些。
確定性初始化
我說初始化通常是隨機的，因為K-Means聚類算法有確定性初始化技術。
隨機初始化
不同之處在于偽隨機序列中的下一個隨機數(shù)與先前的隨機數(shù)無關，而在準隨機數(shù)序列中，下一個隨機數(shù)取決于先前的隨機數(shù)。相關隨機數(shù)覆蓋搜索空間的更大表面。
比較二維空間中的偽隨機序列（左）和準隨機序列（右）
選擇正確的K
除了測試不同的初始化之外，我們還可以在蒙特卡羅框架中測試不同的值??。目前，沒有動態(tài)確定正確數(shù)量的聚類的最佳方式，盡管總是正在研究用于確定正確??值的技術。我更愿意只是憑經(jīng)驗嘗試不同的k值并比較結果，盡管這很費時，特別是在大型數(shù)據(jù)集上。?
?
聚類結果 - 可視化和質心分析
下面提出的最終結果表示發(fā)現(xiàn)在范圍最好聚類??=?{?6?，7?，8?}?={6，7，8}超過1000獨立每的每一個值的模擬??。歐幾里德距離和量化誤差是蒙特卡羅K均值聚類中使用的距離和質量度量。用于產(chǎn)生結果的數(shù)據(jù)集是2014年的標準化時間點數(shù)據(jù)集，其中包括19個被確定為與實際GDP增長正相關的社會經(jīng)濟指標。?
?
群集細分和質心分析
下面的每個標簽都將集群分解為屬于它的國家，并將質心與我們聚集的19個社會經(jīng)濟指標中的每一個的中心質心進行比較。
?
?
2014年該群組中的國家/地區(qū)
?
?
?
?
?
聚類結果 - 結論和進一步研究
量化不是風險管理，衍生品定價或算法交易;?它是關于挑戰(zhàn)事情的方式，并通常使用統(tǒng)計和計算方法找到更好的方法。
2004年，美國是一個異常值，并且自己占據(jù)了一個集群。該集群的特點是PPP的匯率低，進口高，出口高，家庭支出高，工業(yè)生產(chǎn)高，政府收入相對較高，特別是在健康方面。在這個時間點，最大的差異仍然是中國發(fā)生的投資數(shù)量要大得多，而且人口（人口在15到64歲之間）人口更多（顯然）更大。在工業(yè)生產(chǎn)方面，中國也超過了美國。這些在下面的并排比較中顯示，
?
?
?
諸如東歐與西歐國家之類的俗語出現(xiàn)在地圖上，并且（因為缺乏一個更好的詞）正確。然而，諸如金磚四國（巴西，俄羅斯，印度，中國和南非）之類的口語顯然更多地受到政治經(jīng)濟的驅動，而不是實際經(jīng)濟。以下是我對一些常見口語的看法，
東歐與西歐?- 第一組中的國家與第五組和第二組中的國家之間似乎有明顯的區(qū)別。過去十年來，西班牙，愛爾蘭，捷克共和國和其他附近國家發(fā)生了變化。這可能是主權債務危機的結果。
東西方國家?- 這是一種過度簡化。大多數(shù)亞洲國家占據(jù)不同的集群，而美國和英國等傳統(tǒng)的西方國家實際上并不占據(jù)同一集群。
金磚四國?- 巴西，俄羅斯，印度，中國和南非屬于不同的集群。雖然他們可能已達成貿(mào)易協(xié)議，但這并不意味著這些國家具有相同的社會，人口和經(jīng)濟構成或未來實際GDP增長的相同潛力。
非洲增長故事?- 雖然資本市場在過去十年中表現(xiàn)良好，但這似乎并沒有反映出非洲大陸的社會，人口和經(jīng)濟構成的重大變化。有趣的是，印度和巴基斯坦不再與中非和南非國家聚集在一起。
北非與南部非洲?- 北非國家（摩洛哥，阿爾及利亞，埃及，利比亞等）與非洲其他國家之間存在明顯區(qū)別。令人驚訝的是，南非現(xiàn)在與這些國家聚集在一起。
新興國家與發(fā)達國家?- 這似乎過于簡化了。似乎有一些發(fā)展階段將在下一節(jié)討論。
還有更多的俗語，我為不評論所有這些而道歉，這六個只是我日常生活中經(jīng)常遇到的那些。如果您發(fā)現(xiàn)其他有趣的關系，請評論。由于我們不知道每個社會經(jīng)濟指標的相對重要性，因此無法量化在一個集群與另一個集群中的有多好。在某些情況下，我們甚至無法確定大或小的價值是好還是壞。例如，如果政府效率低下，政府的大筆支出是否仍然有效？盡管如此，我還是試圖構建一個粗略的度量標準來對每個集群進行排名：
排名=出口+家庭支出+進口+改善衛(wèi)生+改善水+人口+ 15歲至64歲人口增長+總投資+城市百分比+手機訂閱+政府收入+政府支出+醫(yī)療支出+工業(yè)生產(chǎn)+互聯(lián)網(wǎng)用戶 - PPP的匯率 - 失業(yè)率 - 年齡依賴率
根據(jù)此指標，每個群集的相對排名如下所示，
?
簇排名值秩計數(shù)
6
10.23812
8
5.191222
1
5.146320
5
3.827420
2
3.825545
4
3.111632
3
3.07874
7
1.799843
?
?
這個排名并不完美，但它再次證實了我們的觀點，即世界是一個不平等的地方。
那對投資者意味著什么呢？我認為這意味著應該在處于不同發(fā)展階段的國家之間作出區(qū)分。這是因為雖然大多數(shù)欠發(fā)達國家代表的是具有最大回報潛力的投資，但它們的風險也更大，可能需要更長的時間才能獲得回報。理想情況下，這些因素應相互權衡，并與投資者的風險回報偏好進行比較。
?
非常感謝您閱讀本文，有任何問題請在下面留言！
? ?請選中你要保存的內(nèi)容，粘貼到此文本框
