99999久久久久久亚洲,欧美人与禽猛交狂配,高清日韩av在线影院,一个人在线高清免费观看,啦啦啦在线视频免费观看www

熱線電話:13121318867

登錄
首頁(yè)大數(shù)據(jù)時(shí)代Kmeans優(yōu)化算法:二分K-means聚類算法
Kmeans優(yōu)化算法:二分K-means聚類算法
2020-05-29
收藏

算法的理解

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è)簇。

  1. 使用Kmeans(k=2)將數(shù)據(jù)集分成2個(gè)簇,記錄SSE
  2. 對(duì)于每一個(gè)簇來(lái)說(shuō),都有自己當(dāng)前的SSE,取名為父節(jié)點(diǎn)SSEa. 對(duì)這些簇都進(jìn)行Kmeans二分類,并且記錄分出的2個(gè)簇的SSE只和,稱之為子節(jié)點(diǎn)總SSEb. 記錄這個(gè)簇被2分類之后SSE的差值,SSE差值 = 父節(jié)點(diǎn)SSE - 子節(jié)點(diǎn)SSE
  3. 選擇SSE差值最大的那個(gè)簇進(jìn)行劃分,而其他的簇不進(jìn)行劃分。
  4. 重復(fù)第二的步驟,直到簇的總個(gè)數(shù)達(dá)到K

決策樹(shù)的方法理解BiKmeans

那這個(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.

  1. 使用Kmeans對(duì)根節(jié)點(diǎn)做2分類。得出2個(gè)簇,簇內(nèi)SSE分別為40和30,也就是說(shuō)如果我們對(duì)整體數(shù)據(jù)集做一次Kmeans二分類的話,我們的整體SSE會(huì)下降100-(30+40)=30
  1. 在此時(shí)可以對(duì)每個(gè)葉節(jié)點(diǎn)的數(shù)據(jù)集進(jìn)行二分類,查看這個(gè)簇做二分Kmeans后,SSE下降多少。從這里可以看出,對(duì)簇1來(lái)說(shuō),SSE的變化為40-(20+15)=5,對(duì)簇2來(lái)說(shuō),SSE的變化為30-(10+10)=10。所以說(shuō)對(duì)這2個(gè)簇來(lái)說(shuō)的話,應(yīng)該保留簇1,對(duì)簇2進(jìn)行二分Kmeans。這樣的話可以最大程度的減少總體SSE,因?yàn)榇?二分Kmeans后SSE下降的最快。結(jié)果就是以下的情況,當(dāng)前葉節(jié)點(diǎn)有3個(gè),也就是說(shuō)當(dāng)前我們有3個(gè)簇,還沒(méi)有達(dá)到我們的目標(biāo),4個(gè)簇,繼續(xù)對(duì)每個(gè)葉節(jié)點(diǎn)進(jìn)行劃分。注,這里原來(lái)的簇2就不復(fù)存在了,變成了小一點(diǎn)的簇2和簇3。
  1. 從上面的圖看出,現(xiàn)在有3個(gè)簇,對(duì)每個(gè)簇都做二分Kmeans,之前簇1的SSE差值已經(jīng)算過(guò)了,是40-(20+15)=5,對(duì)于簇2來(lái)說(shuō),SSE變化為10-(8+1)=1, 對(duì)于簇3來(lái)說(shuō),SSE的變化為10-(7+1)=2。這里簇1的SSE變化值最大,優(yōu)先對(duì)簇1做二分Kmeans,得出以下結(jié)果。
  1. 當(dāng)前決策樹(shù)一共有4個(gè)葉節(jié)點(diǎn),每個(gè)葉節(jié)點(diǎn)都代表一個(gè)簇,簇的個(gè)數(shù)已經(jīng)達(dá)到我們的目標(biāo)。算法結(jié)束。

代碼實(shí)現(xiàn)

首先先讀取數(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??

  1. 用的方法就是使用np.power(data - mean, 2).sum(axis = 1)得出的就是這個(gè)簇一開(kāi)始的SSE。
  2. 將數(shù)據(jù)集帶入之前寫的Kmeans_regular后設(shè)置k=2,會(huì)給出SSE_list, SSE_list[-1]會(huì)給出Kmeans聚類好數(shù)據(jù)集之后2個(gè)簇加起來(lái)SSE的綜合,并且也會(huì)給出curr_group, 用來(lái)劃分我們的簇,方便選取其中的簇帶入下一次迭代
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)

ReKmeans和BiKmeans的結(jié)果對(duì)比

我們也可以將這個(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)題。

BiKmeans大致中間過(guò)程

這里我們不會(huì)像Kmeans中間過(guò)程那樣給出詳細(xì)的從隨機(jī)選取的質(zhì)心點(diǎn)到收斂的過(guò)程。我們這個(gè)給出一個(gè)大致的BiKmeans中間過(guò)程,有助于同學(xué)們理解。

數(shù)據(jù)分析咨詢請(qǐng)掃描二維碼

若不方便掃碼,搜微信號(hào):CDAshujufenxi

數(shù)據(jù)分析師資訊
更多

OK
客服在線
立即咨詢
客服在線
立即咨詢
') } function initGt() { var handler = function (captchaObj) { captchaObj.appendTo('#captcha'); captchaObj.onReady(function () { $("#wait").hide(); }).onSuccess(function(){ $('.getcheckcode').removeClass('dis'); $('.getcheckcode').trigger('click'); }); window.captchaObj = captchaObj; }; $('#captcha').show(); $.ajax({ url: "/login/gtstart?t=" + (new Date()).getTime(), // 加隨機(jī)數(shù)防止緩存 type: "get", dataType: "json", success: function (data) { $('#text').hide(); $('#wait').show(); // 調(diào)用 initGeetest 進(jìn)行初始化 // 參數(shù)1:配置參數(shù) // 參數(shù)2:回調(diào),回調(diào)的第一個(gè)參數(shù)驗(yàn)證碼對(duì)象,之后可以使用它調(diào)用相應(yīng)的接口 initGeetest({ // 以下 4 個(gè)配置參數(shù)為必須,不能缺少 gt: data.gt, challenge: data.challenge, offline: !data.success, // 表示用戶后臺(tái)檢測(cè)極驗(yàn)服務(wù)器是否宕機(jī) new_captcha: data.new_captcha, // 用于宕機(jī)時(shí)表示是新驗(yàn)證碼的宕機(jī) product: "float", // 產(chǎn)品形式,包括:float,popup width: "280px", https: true // 更多配置參數(shù)說(shuō)明請(qǐng)參見(jiàn):http://docs.geetest.com/install/client/web-front/ }, handler); } }); } function codeCutdown() { if(_wait == 0){ //倒計(jì)時(shí)完成 $(".getcheckcode").removeClass('dis').html("重新獲取"); }else{ $(".getcheckcode").addClass('dis').html("重新獲取("+_wait+"s)"); _wait--; setTimeout(function () { codeCutdown(); },1000); } } function inputValidate(ele,telInput) { var oInput = ele; var inputVal = oInput.val(); var oType = ele.attr('data-type'); var oEtag = $('#etag').val(); var oErr = oInput.closest('.form_box').next('.err_txt'); var empTxt = '請(qǐng)輸入'+oInput.attr('placeholder')+'!'; var errTxt = '請(qǐng)輸入正確的'+oInput.attr('placeholder')+'!'; var pattern; if(inputVal==""){ if(!telInput){ errFun(oErr,empTxt); } return false; }else { switch (oType){ case 'login_mobile': pattern = /^1[3456789]\d{9}$/; if(inputVal.length==11) { $.ajax({ url: '/login/checkmobile', type: "post", dataType: "json", data: { mobile: inputVal, etag: oEtag, page_ur: window.location.href, page_referer: document.referrer }, success: function (data) { } }); } break; case 'login_yzm': pattern = /^\d{6}$/; break; } if(oType=='login_mobile'){ } if(!!validateFun(pattern,inputVal)){ errFun(oErr,'') if(telInput){ $('.getcheckcode').removeClass('dis'); } }else { if(!telInput) { errFun(oErr, errTxt); }else { $('.getcheckcode').addClass('dis'); } return false; } } return true; } function errFun(obj,msg) { obj.html(msg); if(msg==''){ $('.login_submit').removeClass('dis'); }else { $('.login_submit').addClass('dis'); } } function validateFun(pat,val) { return pat.test(val); }