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