
Bi這里是的意思就是Binary,二進制的意思,所以有時候叫這個算法為二進Kmeans算法。為什么我們需要用BiKmeans呢,就是為了解決初始化k個隨機的質(zhì)心點時其中一個或者多個點由于位置太極端而導(dǎo)致迭代的過程中消失的問題。BiKmeans只是Kmeans其中一個優(yōu)化方案,其實還是有很多優(yōu)化的方案,這里BiKmeans容易講解和理解,并且容易用numpy, pandas實現(xiàn)。
那為什么二進Kmeans算法可以有效的解決這個問題呢。我們需要從二進Kmeans的基礎(chǔ)看是講起。其實BiKmeans的迭代過程類似于一個決策樹。首先我們看一下K-means聚類等算法的步驟。
利用之前寫好的Kmeans算法包,設(shè)置k為2。所以每次傳入一個數(shù)據(jù)集的時候,都是進行2分類。
假設(shè)我們預(yù)先想分出K個簇。
那這個算法其實就是非常的類似決策樹的算法。在決策樹節(jié)點由父節(jié)點劃分成子節(jié)點的過程中,用的是gini不純度來判斷是否需要劃分,我們選擇不純度差值最大的那個特征來做劃分。這里也類似,我們最后的目標是最小化SSE,所以對每一個簇來說,都可以得出該簇在劃分出成2個簇之后總體上SSE降低了多少,我們需要做的就是保持其他的簇不變,選取的就是那個能夠最大程度的降低SSE的那個簇進行Kmeans二分類。
那個算法里面還是有個缺陷,就是在算法的過程中,會對每個簇重復(fù)計算劃分后SSE的差值,所以這里我在對每個簇做劃分后,記錄下它的SSE差值,后期就可以直接使用SSE,不用重新再計算一遍了。
我們首先用決策樹的概念來看下BiKmeans,我們目標是分成4個簇,首先有我們有我們的根節(jié)點,也就是我們的整體的數(shù)據(jù)集,假設(shè)這個數(shù)據(jù)集的SSE為100.
首先先讀取數(shù)據(jù),讀取的是上次我們在Kmeans中間過程最后展示原始Kmeans理論缺陷的那組數(shù)據(jù)。
from Kmeans_pack import *
r = 4 k = 3 x , y = make_blobs(n_samples = 400, cluster_std = [0.2, 0.4, 0.4, 0.4], centers = [[0.3,-1],[1,1],[-1,1], [-1,-1]], random_state = r ) np.random.seed(r) sim_data = pd.DataFrame(x, columns = ['x', 'y']) sim_data['label'] = y dataset = sim_data.copy()
現(xiàn)在我們嘗試的將數(shù)據(jù)只做一次二分Kmeans的迭代,查看結(jié)果,這個時候會有兩種結(jié)果
在這兩個情況下,我們看到2分Kmeans可以將當前數(shù)據(jù)集分成2個簇,緊接著我們就需要嘗試分別對藍色和黃色的簇進行2分Kmeans查看每個簇劃分后SSE下降了少。我們會首先寫一個Split函數(shù),對每個傳進去的數(shù)據(jù)集進行2分Kmeans。但是這里需要注意是否是第一次做劃分,就比如上面的情況。
這里我們首先有個split函數(shù),專門用來對傳入的數(shù)據(jù)做2分Kmeans,算出聚類前和聚類后的SSE,比如說假如這個時候我們有x和y,\bar{x}xˉ和\bar{y}yˉ為x和y的平均值
\left[ \begin{matrix} (x_{1}-\bar{x})^2 + (y_{1}-\bar{y})^2 \\ (x_{2}-\bar{x})^2 + (y_{2}-\bar{y})^2 \\ (x_{3}-\bar{x})^2 + (y_{3}-\bar{y})^2 \end{matrix} \right]??(x1?xˉ)2+(y1?yˉ)2(x2?xˉ)2+(y2?yˉ)2(x3?xˉ)2+(y3?yˉ)2??
def Split(dataset): #假設(shè)當前數(shù)據(jù)不是第一次二分Kmeans,就是說傳進來的是整體的數(shù)據(jù)集,當前的質(zhì)心點就是每個特征的平均值 temp_data = dataset.loc[:, dataset.columns != 'label'].copy() #計算當前數(shù)據(jù)集的SSE current_error = np.power(temp_data - temp_data.mean(), 2).sum().sum() #對數(shù)據(jù)集做二分Kmeans curr_group, SSE_list, centers = Kmeans_regular(temp_data, k = 2) #記錄二分后的SSE after_split_error = SSE_list[-1] #已經(jīng)有了curr_group將二分類后的數(shù)據(jù)集先拿出來 clusters = list(dataset.groupby(curr_group)) #這里有非常非常少的情況會出現(xiàn)二分Kmeans中初始的質(zhì)心點其中一個由于離所有的都太遠,導(dǎo)致丟失的情況 #所以這里多加了一個判斷,假如其中一個質(zhì)心掉了,那上面給的clusters只有一個而不是兩個 #在這個情況下,dataset沒有被成功二分類,我們需要將dataset自身給return,進行下一次迭代,肯定有一次迭代能成功分出2個簇 #所以在這個情況下entropy就是current_error, cluster1就是dataset自己,cluster2為空 if len(clusters) == 1: entropy = current_error return [entropy, dataset, None, current_error] #分別取出2個簇 cluster1, cluster2 = [i[1] for i in clusters] #計算這個簇做了二分Kmeans后SSE下降的多少 entropy = current_error - after_split_error #最后返回結(jié)果,返回當前這個簇二分后的SSE差值,分出的簇1和簇2,還有當前這個簇的SSE return [entropy, cluster1, cluster2, current_error]
這個函數(shù)寫好之后我們來測試一下,當前我們將所有的數(shù)據(jù)全部傳進去后,給出的結(jié)果
entropy, cluster1, cluster2, current_error = Split(dataset) entropy, cluster1.shape[0], cluster2.shape[0], current_error
(432.9176440191153, 200, 200, 813.3842612925762)
當前數(shù)據(jù)集做完二分后整體SSE由原來的813,下降了432.92。
接下來就是需要完成2分Kmeans的迭代過程
def bi_iterate(dataset, k = 4): #首先準備一個空的cluster_info_list,這個list是用來存二分后的結(jié)果,里面每一個元素都是一個簇 #對于每個元素來說,它代表的是個簇,里面記錄的這個簇的[entropy, cluster1, cluster2, current_error] #也就是每個簇的[SSE差值,第一個二分后的簇,第二個二分后的簇,當前簇的SSE] cluster_info_list = [] #使用while做循環(huán)直到cluster_info_list里面一共達到k個簇的時候停止 while len(cluster_info_list) < k: #假如當前我們是第一次迭代的話也就是cluster_info_list是空list的話做以下操作 if len(cluster_info_list) == 0: #直接用Split函數(shù),將整體數(shù)據(jù)集放入cluster_info_list里,然后下面的操作都不用,continue進入下一個循環(huán) cluster_info_list.append(Split(dataset)) continue #首先將cluster_info_list最后一個元素取出來,cluster_info_list里面是所有簇的信息 #我們后面會對cluster_info_list做sort,由于cluster_info_list里面每個元素的第一位是SSE差值 #所以我們做完sort后,最后一個元素肯定是SSE差值(entropy)最大的那一個,也就是我們需要下一步做二分的簇 #將最后一個元素里的2個clusters取出來后,將這個當前在cluster_info_list里SSE最大的一個簇刪除掉(pop方法) #取而代之的是Split(cluster1)和Split(cluster2),也是就嘗試著對新的兩個cluster嘗試去算SSE差值 cluster1, cluster2 = cluster_info_list[-1][1:-1] cluster_info_list.pop(-1) #將Split(cluster1)和Split(cluster2)的結(jié)果追加到cluster_info_list #注意假如只有cluster2給出的是None,則碰到二分類不成功的情況,cluster1還為原來上一次dataset,cluster2為空 #不將cluster2追加到cluster_info_list當中 cluster_info_list.append(Split(cluster1)) if cluster2 is not None: cluster_info_list.append(Split(cluster2)) #整體的cluster_info_list進行一次sort,找出當前所有的簇中,哪一個簇的SSE差值最大 #這里我們是需要對整體cluster_info_list做sort,因為新追加進去的2個心cluster的SSE差值可能沒有cluster_info_list里已經(jīng)記錄的簇的SSE大。 cluster_info_list.sort() #進入下一個循環(huán) return cluster_info_list
將總共的代碼都放在一起,內(nèi)容不多,和網(wǎng)上的代碼相比的話,簡單易懂量少,也避免了效率較低的for循環(huán)。
from Kmeans_pack import * def Split(dataset): temp_data = dataset.loc[:, dataset.columns != 'label'].copy() current_error = np.power(temp_data - temp_data.mean(), 2).sum().sum() curr_group, SSE_list, centers = Kmeans_regular(temp_data, k = 2) after_split_error = SSE_list[-1] clusters = list(dataset.groupby(curr_group)) if len(clusters) == 1: entropy = current_error return [entropy, dataset, None, None, current_error] cluster1, cluster2 = [i[1] for i in clusters] entropy = current_error - after_split_error return [entropy, cluster1, cluster2, centers, curr_group, current_error, dataset] def bi_Kmeans(dataset, k = 4): cluster_info_list = [] while len(cluster_info_list) < k: if len(cluster_info_list) == 0: cluster_info_list.append(Split(dataset)) continue cluster1, cluster2 = cluster_info_list[-1][1:3] cluster_info_list.pop(-1) cluster_info_list.append(Split(cluster1)) if cluster2 is not None: cluster_info_list.append(Split(cluster2)) cluster_info_list.sort() return cluster_info_list
我們測試一下代碼,返回的cluster_info_list里面所有的元素都是簇的信息,每個元素的最后一位都是這個簇的簇內(nèi)SSE,所以我們可以用列表解析的方法將每個元素的最后一位取出來,進行相加就能得到BiKmeans最后的結(jié)果給出的整體的SSE,我們可以看出在數(shù)據(jù)集要4個簇的前提下,我們SSE最后為95.64
np.random.seed(1) cluster_info_list = bi_Kmeans(dataset, k = 4)
我們也可以將這個結(jié)果和原始寫好的Kmeans_regular做比較
regular_SSE = [] bi_SSE = [] for i in range(50): curr_group, SSE_list, centers = Kmeans_regular(dataset, k = 4) cluster_info_list = bi_Kmeans(dataset, k = 4) bi_sse = sum([i[-1] for i in cluster_info_list]) regular_SSE.append(SSE_list[-1]) bi_SSE.append(bi_sse)
data_compare = pd.DataFrame({'ReKmeans':regular_SSE,'BiKmeans':bi_SSE}) data = [go.Scatter(x = data_compare.index + 1, y = data_compare[i], mode = 'lines+markers', name = i ) for i in data_compare.columns] layout = go.Layout(title = '原始Kmeans與二分Kmeans的SSE穩(wěn)定性比較', xaxis = {'title' : '次數(shù)'}, yaxis = {'title' : 'SSE值'}, template = 'plotly_white' ) fig = go.Figure(data = data, layout = layout) #fig.show()
我們這里隨機的跑30次,來比較最后2個算法所得到的SSE,我們這里主要查看穩(wěn)定性??梢詮膱D中看出對于原始的(RegularKmeans)的SSE非常不穩(wěn)定,而對于BiKmeans來說的話,SSE非常穩(wěn)定,一直保持在大約95左右。這里就體現(xiàn)出的BiKmeans的優(yōu)點,可以很大概率的(不是絕無可能)保證每次隨機生成的2個質(zhì)心點不會因為太極端而導(dǎo)致其中一個丟失的問題,從而導(dǎo)致最后SSE很高,結(jié)果陷入局部最優(yōu)的這樣一個問題。
這里我們不會像Kmeans中間過程那樣給出詳細的從隨機選取的質(zhì)心點到收斂的過程。我們這個給出一個大致的BiKmeans中間過程,有助于同學(xué)們理解。
數(shù)據(jù)分析咨詢請掃描二維碼
若不方便掃碼,搜微信號:CDAshujufenxi
LSTM 模型輸入長度選擇技巧:提升序列建模效能的關(guān)鍵? 在循環(huán)神經(jīng)網(wǎng)絡(luò)(RNN)家族中,長短期記憶網(wǎng)絡(luò)(LSTM)憑借其解決長序列 ...
2025-07-11CDA 數(shù)據(jù)分析師報考條件詳解與準備指南? ? 在數(shù)據(jù)驅(qū)動決策的時代浪潮下,CDA 數(shù)據(jù)分析師認證愈發(fā)受到矚目,成為眾多有志投身數(shù) ...
2025-07-11數(shù)據(jù)透視表中兩列相乘合計的實用指南? 在數(shù)據(jù)分析的日常工作中,數(shù)據(jù)透視表憑借其強大的數(shù)據(jù)匯總和分析功能,成為了 Excel 用戶 ...
2025-07-11尊敬的考生: 您好! 我們誠摯通知您,CDA Level I和 Level II考試大綱將于 2025年7月25日 實施重大更新。 此次更新旨在確保認 ...
2025-07-10BI 大數(shù)據(jù)分析師:連接數(shù)據(jù)與業(yè)務(wù)的價值轉(zhuǎn)化者? ? 在大數(shù)據(jù)與商業(yè)智能(Business Intelligence,簡稱 BI)深度融合的時代,BI ...
2025-07-10SQL 在預(yù)測分析中的應(yīng)用:從數(shù)據(jù)查詢到趨勢預(yù)判? ? 在數(shù)據(jù)驅(qū)動決策的時代,預(yù)測分析作為挖掘數(shù)據(jù)潛在價值的核心手段,正被廣泛 ...
2025-07-10數(shù)據(jù)查詢結(jié)束后:分析師的收尾工作與價值深化? ? 在數(shù)據(jù)分析的全流程中,“query end”(查詢結(jié)束)并非工作的終點,而是將數(shù) ...
2025-07-10CDA 數(shù)據(jù)分析師考試:從報考到取證的全攻略? 在數(shù)字經(jīng)濟蓬勃發(fā)展的今天,數(shù)據(jù)分析師已成為各行業(yè)爭搶的核心人才,而 CDA(Certi ...
2025-07-09【CDA干貨】單樣本趨勢性檢驗:捕捉數(shù)據(jù)背后的時間軌跡? 在數(shù)據(jù)分析的版圖中,單樣本趨勢性檢驗如同一位耐心的偵探,專注于從單 ...
2025-07-09year_month數(shù)據(jù)類型:時間維度的精準切片? ? 在數(shù)據(jù)的世界里,時間是最不可或缺的維度之一,而year_month數(shù)據(jù)類型就像一把精準 ...
2025-07-09CDA 備考干貨:Python 在數(shù)據(jù)分析中的核心應(yīng)用與實戰(zhàn)技巧? ? 在 CDA 數(shù)據(jù)分析師認證考試中,Python 作為數(shù)據(jù)處理與分析的核心 ...
2025-07-08SPSS 中的 Mann-Kendall 檢驗:數(shù)據(jù)趨勢與突變分析的有力工具? ? ? 在數(shù)據(jù)分析的廣袤領(lǐng)域中,準確捕捉數(shù)據(jù)的趨勢變化以及識別 ...
2025-07-08備戰(zhàn) CDA 數(shù)據(jù)分析師考試:需要多久?如何規(guī)劃? CDA(Certified Data Analyst)數(shù)據(jù)分析師認證作為國內(nèi)權(quán)威的數(shù)據(jù)分析能力認證 ...
2025-07-08LSTM 輸出不確定的成因、影響與應(yīng)對策略? 長短期記憶網(wǎng)絡(luò)(LSTM)作為循環(huán)神經(jīng)網(wǎng)絡(luò)(RNN)的一種變體,憑借獨特的門控機制,在 ...
2025-07-07統(tǒng)計學(xué)方法在市場調(diào)研數(shù)據(jù)中的深度應(yīng)用? 市場調(diào)研是企業(yè)洞察市場動態(tài)、了解消費者需求的重要途徑,而統(tǒng)計學(xué)方法則是市場調(diào)研數(shù) ...
2025-07-07CDA數(shù)據(jù)分析師證書考試全攻略? 在數(shù)字化浪潮席卷全球的當下,數(shù)據(jù)已成為企業(yè)決策、行業(yè)發(fā)展的核心驅(qū)動力,數(shù)據(jù)分析師也因此成為 ...
2025-07-07剖析 CDA 數(shù)據(jù)分析師考試題型:解鎖高效備考與答題策略? CDA(Certified Data Analyst)數(shù)據(jù)分析師考試作為衡量數(shù)據(jù)專業(yè)能力的 ...
2025-07-04SQL Server 字符串截取轉(zhuǎn)日期:解鎖數(shù)據(jù)處理的關(guān)鍵技能? 在數(shù)據(jù)處理與分析工作中,數(shù)據(jù)格式的規(guī)范性是保證后續(xù)分析準確性的基礎(chǔ) ...
2025-07-04CDA 數(shù)據(jù)分析師視角:從數(shù)據(jù)迷霧中探尋商業(yè)真相? 在數(shù)字化浪潮席卷全球的今天,數(shù)據(jù)已成為企業(yè)決策的核心驅(qū)動力,CDA(Certifie ...
2025-07-04CDA 數(shù)據(jù)分析師:開啟數(shù)據(jù)職業(yè)發(fā)展新征程? ? 在數(shù)據(jù)成為核心生產(chǎn)要素的今天,數(shù)據(jù)分析師的職業(yè)價值愈發(fā)凸顯。CDA(Certified D ...
2025-07-03