
機(jī)器學(xué)習(xí)經(jīng)典算法詳解及Python實(shí)現(xiàn)
聚類是一種無監(jiān)督的學(xué)習(xí)(無監(jiān)督學(xué)習(xí)不依賴預(yù)先定義的類或帶類標(biāo)記的訓(xùn)練實(shí)例),它將相似的對(duì)象歸到同一個(gè)簇中,它是觀察式學(xué)習(xí),而非示例式的學(xué)習(xí),有點(diǎn)像全自動(dòng)分類。
說白了,聚類 (clustering)是完全可以按字面意思來理解的——將相同、相似、相近、相關(guān)的對(duì)象實(shí)例聚成一類的過程。機(jī)器學(xué)習(xí)中常見的聚類算法包括 k-Means算法、期望最大化算法(Expectation Maximization,EM,參考“EM算法原理”)、譜聚類算法(參考機(jī)器學(xué)習(xí)算法復(fù)習(xí)-譜聚類)以及人工神經(jīng)網(wǎng)絡(luò)算法,本文闡述的是K-均值聚類算法,本文介紹K-均值(K-means)和二分K-均值聚類算法。
機(jī)器學(xué)習(xí)經(jīng)典算法詳解及Python實(shí)現(xiàn)–K近鄰(KNN)算法
機(jī)器學(xué)習(xí)經(jīng)典算法詳解及Python實(shí)現(xiàn)–線性回歸(Linear Regression)算法
機(jī)器學(xué)習(xí)經(jīng)典算法詳解及Python實(shí)現(xiàn)–決策樹(Decision Tree)
機(jī)器學(xué)習(xí)經(jīng)典算法詳解及Python實(shí)現(xiàn)–CART分類決策樹、回歸樹和模型樹
(一)何謂聚類
還是那句“物以類聚、人以群分”,如果預(yù)先知道人群的標(biāo)簽(如文藝、普通、2B),那么根據(jù)監(jiān)督學(xué)習(xí)的分類算法可將一個(gè)人明確的劃分到某一類;如果預(yù)先不知道人群的標(biāo)簽,那就只有根據(jù)人的特征(如愛好、學(xué)歷、職業(yè)等)劃堆了,這就是聚類算法。
聚類是一種無監(jiān)督的學(xué)習(xí)(無監(jiān)督學(xué)習(xí)不 依賴預(yù)先定義的類或帶類標(biāo)記的訓(xùn)練實(shí)例),它將相似的對(duì)象歸到同一個(gè)簇中,它是觀察式學(xué)習(xí),而非示例式的學(xué)習(xí),有點(diǎn)像全自動(dòng)分類。
所謂簇就是該集合中的對(duì) 象有很大的相似性,而不同集合間的對(duì)象有很大的相異性。簇識(shí)別(cluster identification)給出了聚類結(jié)果的含義,告訴我們這些簇到底都是些什么。通常情況下,簇質(zhì)心可以代表整個(gè)簇的數(shù)據(jù)來做出決策。聚類方法幾乎 可以應(yīng)用于所有對(duì)象,簇內(nèi)的對(duì)象越相似,聚類的效果越好。
從機(jī)器學(xué)習(xí)的角度講,簇相當(dāng)于隱藏模式,聚類與分類的最大不同在于,分類學(xué)習(xí)的實(shí)例或數(shù)據(jù)對(duì)象有類別標(biāo)記,而聚類則不一樣,需要由聚類學(xué)習(xí)算法自動(dòng) 確定標(biāo)記。因?yàn)槠洚a(chǎn)生的結(jié)果與分類相同,而只是類別沒有預(yù)先定義,所以聚類也被稱為無監(jiān)督分類(unsupervised classification )。
聚類分析是一種探索性的分析,在分類的過程中,人們不必事先給出一個(gè)分類的標(biāo)準(zhǔn),聚類分析能夠從樣本數(shù)據(jù)出發(fā),自動(dòng)進(jìn)行 分類。聚類分析所使用方法的不同,常常會(huì)得到不同的結(jié)論。不同研究者對(duì)于同一組數(shù)據(jù)進(jìn)行聚類分析,所得到的聚類數(shù)未必一致。
從實(shí)際應(yīng)用的角度看,聚類分析 是數(shù)據(jù)挖掘的主要任務(wù)之一。而且聚類能夠作為一個(gè)獨(dú)立的工具獲得數(shù)據(jù)的分布狀況,觀察每一簇?cái)?shù)據(jù)的特征,集中對(duì)特定的聚簇集合作進(jìn)一步地分析。聚類分析還 可以作為其他算法(如分類和定性歸納算法)的預(yù)處理步驟。
聚類分析試圖將相似對(duì)象歸入同一簇,將不相似對(duì)象歸到不同簇,那么是否“相似”就要有所選擇的相似度計(jì)算方法?,F(xiàn)在,存在多種不同的相似度計(jì)算方 法,到底使用哪種相似度計(jì)算方法取決于具體應(yīng)用,選擇合適的相似度計(jì)算方法才會(huì)提高聚類算法的性能。機(jī)器學(xué)習(xí)中常用的相似性度量方法參考博文“機(jī)器學(xué)習(xí)中的相似性度量”。
聚類算法通常按照中心點(diǎn)或者分層的方式對(duì)輸入數(shù)據(jù)進(jìn)行歸并,所以的聚類算法都試圖找到數(shù)據(jù)的內(nèi)在結(jié)構(gòu),以便按照最大的共同點(diǎn)將數(shù)據(jù)進(jìn)行歸類,其目標(biāo) 是使同一類對(duì)象的相似度盡可能地大;不同類對(duì)象之間的相似度盡可能地小。
目前聚類的方法很多,根據(jù)基本思想的不同,大致可以將聚類算法分為五大類:層次聚 類算法、分割聚類算法、基于約束的聚類算法、機(jī)器學(xué)習(xí)中的聚類算法和用于高維度的聚類算法,參考“各種聚類算法的比較”。聚類算法的基本過程包含特征選擇、相似性度量、聚類準(zhǔn)則、聚類算法和結(jié)果驗(yàn)證等,具體參考“聚類算法學(xué)習(xí)筆記(一)——基礎(chǔ)”。
說白了,聚類(clustering)是完全可以按字面意思來理解的——將相同、相似、相近、相關(guān)的對(duì)象實(shí)例聚成一類的過程。簡(jiǎn)單理解,如果一個(gè)數(shù) 據(jù)集合包含N個(gè)實(shí)例,根據(jù)某種準(zhǔn)則可以將這N個(gè)實(shí)例劃分為m個(gè)類別,每個(gè)類別中的實(shí)例都是相關(guān)的,而不同類別之間是區(qū)別的也就是不相關(guān)的,這就得到了一個(gè) 聚類模型了。判別新樣本點(diǎn)的所屬類時(shí),就通過計(jì)算該點(diǎn)與這m個(gè)類別的相似度,選擇最相似的那個(gè)類作為該點(diǎn)的歸類。
既然聚類可以看做是一種無監(jiān)督分類,那么其應(yīng)用場(chǎng)景就是廣泛的,包括用戶群劃分、文本分類、圖像識(shí)別等等。當(dāng)幾乎沒有有關(guān)數(shù)據(jù)的先驗(yàn)信息(如統(tǒng)計(jì)模 型)可用,而用戶又要求盡可能地對(duì)數(shù)據(jù)的可能性少進(jìn)行假設(shè)等限制條件下,聚類方法都適合用來查看數(shù)據(jù)點(diǎn)中的內(nèi)在關(guān)系以對(duì)它們的結(jié)構(gòu)進(jìn)行評(píng)估、決策。
機(jī)器學(xué)習(xí)中常見的聚類算法包括 k-Means算法、期望最大化算法(Expectation Maximization,EM,參考“EM算法原理”)、譜聚類算法(參考機(jī)器學(xué)習(xí)算法復(fù)習(xí)-譜聚類)以及人工神經(jīng)網(wǎng)絡(luò)算法,本文介紹K-均值(K-means)聚類算法。
(二)K-均值(K-means)聚類算法
1. 認(rèn)識(shí)K-均值聚類算法
K-均值算法是最簡(jiǎn)單的一種聚類算法,屬于分割式聚類算法,目的是使各個(gè)簇(共k個(gè))中的數(shù)據(jù)點(diǎn)與所在簇質(zhì)心的誤差平方和SSE(Sum of Squared Error)達(dá)到最小,這也是評(píng)價(jià)K-means算法最后聚類效果的評(píng)價(jià)標(biāo)準(zhǔn)。
k-means算法的基礎(chǔ)是最小誤差平方和準(zhǔn)則。其代價(jià)函數(shù)是:
式中,μc(i)表示第i個(gè)簇的質(zhì)心,我們希望得到的聚類模型代價(jià)函數(shù)最小,直觀的來說,各簇內(nèi)的樣本越相似,其與該簇質(zhì)心 的誤差平方越小。計(jì)算所有簇的誤差平方之和,即可驗(yàn)證分為k個(gè)簇時(shí)時(shí)的聚類是否是最優(yōu)的。SSE值越小表示數(shù)據(jù)點(diǎn)越接近于它們的質(zhì)心,聚類效果也越好。因 為對(duì)誤差取了平方,因此更加重視那些遠(yuǎn)離中心的點(diǎn)。
一種肯定可以降低SSE值的方法是增加簇的個(gè)數(shù),但這違背了聚類的目標(biāo),聚類的目標(biāo)是在保持族數(shù)目不變 的情況下提高簇的質(zhì)量。
k-均值(k-means)聚類算法之所以稱之為k-均值是因?yàn)樗梢园l(fā)現(xiàn)k個(gè)不同的簇,且每個(gè)簇的中心采用簇中所含子數(shù)據(jù)集樣本特征的均值計(jì)算而 成。k-均值是發(fā)現(xiàn)給定數(shù)據(jù)集的k個(gè)簇的算法,簇個(gè)數(shù)k由用戶給定,每一個(gè)簇通過其質(zhì)心( centroid) — 即簇中所有點(diǎn)的中心來描述。K-均值聚類算法需要數(shù)值型數(shù)據(jù)來進(jìn)行相似性度量,也可以將標(biāo)稱型數(shù)據(jù)映射為二值型數(shù)據(jù)再用于度量相似性,其優(yōu)點(diǎn)是容易實(shí)現(xiàn), 缺點(diǎn)是可能收斂到局部最小值,在大規(guī)模數(shù)據(jù)集上收斂較慢。
假設(shè)訓(xùn)練樣本數(shù)據(jù)集X為(m, n)維矩陣,m表示樣本數(shù)、n表示每個(gè)樣本點(diǎn)的特征數(shù),那么k-均值聚類算法的結(jié)果就是得到一個(gè)kxn維矩陣,k表示用戶指定的簇個(gè)數(shù),每一行都是一個(gè)長(zhǎng) 度為n的行向量–第i個(gè)元素就是該簇中所有樣本第j(j=0,1,…,n-1)個(gè)特征的均值。下圖是K-均值聚類算法聚類的過程:
2. 算法過程
K-均值算法的工作流程是這樣的。首先,隨機(jī)確定k個(gè)初始點(diǎn)作為質(zhì)心;然后將數(shù)據(jù)集中的每個(gè)點(diǎn)分配到一個(gè)簇中–就是為每個(gè)點(diǎn)找距其最近的質(zhì)心,并將 其分配給該質(zhì)心所對(duì)應(yīng)的簇;該步完成之后更新每個(gè)簇的質(zhì)心(該簇所有數(shù)據(jù)樣本特征的平均值);
上述過程迭代多次直至所有數(shù)據(jù)點(diǎn)的簇歸屬不再改變或者達(dá)到了 最大迭代次數(shù)Maxiteration。k-均值算法的性能會(huì)受到所選相似性度量方法的影響,常用的相似性度量方法就是計(jì)算歐氏距離。上述過程的偽代碼表 示如下:
***************************************************************
創(chuàng)建k個(gè)點(diǎn)作為起始質(zhì)心
任意點(diǎn)的簇分配結(jié)果發(fā)生改變時(shí)(循環(huán)內(nèi)設(shè)置、維護(hù)標(biāo)志位changed,也可同時(shí)設(shè)定最大迭代次數(shù)max)
對(duì)數(shù)據(jù)集中的每個(gè)數(shù)據(jù)點(diǎn)
對(duì)每個(gè)質(zhì)心
計(jì)算質(zhì)心與數(shù)據(jù)點(diǎn)之間的距離
將數(shù)據(jù)點(diǎn)分配到距其最近的簇(若有點(diǎn)的簇發(fā)生改變則置標(biāo)志位為changed = True)
更新簇中心: 對(duì)每一個(gè)簇,計(jì)算簇中所有點(diǎn)的均值并將均值作為質(zhì)心
***************************************************************
上述循環(huán)的終止條件是每個(gè)點(diǎn)的簇分配結(jié)果沒有發(fā)生改變或者達(dá)到了最大循環(huán)次數(shù)。
初始化時(shí)k個(gè)質(zhì)心的選擇可以是隨機(jī)的,但為了提高性能常用的方式是
(1)盡量選擇距離比較遠(yuǎn)的點(diǎn)(方法:依次計(jì)算出與已確定的點(diǎn)(第一個(gè)點(diǎn)可以隨機(jī)選擇)的距離,并選擇距離最大的點(diǎn))。當(dāng)k比較大時(shí),這種方法計(jì)算量比較復(fù)雜,適合二分K-均值聚類算法的k值初始化。
(2)采取層次聚類的方式找出k個(gè)簇。 TBD
3. 特征值處理
K-均值聚類算法需要數(shù)值型數(shù)據(jù)來進(jìn)行相似性度量,也可以將標(biāo)稱型數(shù)據(jù)映射為二值型數(shù)據(jù)再用于度量相似性。
另外,樣本會(huì)有多個(gè)特征,每一個(gè)特征都有自己的定義域和取值范圍,他們對(duì)distance計(jì)算的影響也就不一樣,如取值較大的影響力會(huì)蓋過取值較小 的參數(shù)。為了公平,樣本特征取值必須做一些scale處理,最簡(jiǎn)單的方式就是所有特征的數(shù)值都采取歸一化處置,把每一維的數(shù)據(jù)都轉(zhuǎn)化到0,1區(qū)間內(nèi),從而 減少迭代次數(shù),提高算法的收斂速度。
4. k值的選取
前面提到,在k-均值聚類中簇的數(shù)目k是一個(gè)用戶預(yù)先定義的參數(shù),那么用戶如何才能知道k的選擇是否正確?如何才能知道生成的簇比較好呢?與K-近鄰分類算法的k值確定方法一樣,k-均值算法也可采用交叉驗(yàn)證法確定誤差率最低的k值,參考“機(jī)器學(xué)習(xí)經(jīng)典算法詳解及Python實(shí)現(xiàn)–K近鄰(KNN)算法”的2.3節(jié)-k值的確定。
當(dāng)k的數(shù)目低于真實(shí)的簇的數(shù)目時(shí),SSE(或者平均直徑等其他分散度指標(biāo))會(huì)快速上升。所以可以采用多次聚類,然后比較的方式確定最佳k值。多次聚 類,一般是采用 k=1, 2, 4, 8… 這種二分?jǐn)?shù)列的方式,通過交叉驗(yàn)證找到一個(gè)k在 v/2, v 時(shí)獲取較好聚類效果的v值,然后繼續(xù)使用二分法,在 [v/2, v] 之間找到最佳的k值。
5. K-均值算法的Python實(shí)現(xiàn)
下載地址:TBD
K-均值算法收斂但聚類效果較差的原因是,K-均值算法收斂到了局部最小值,而非全局最小值(局部最小值指結(jié)果還可以但并非最好結(jié)果,全局最小值是 可能的最好結(jié)果)。為克服k-均值算法收斂于局部最小值的問題,有人提出了另一個(gè)稱為二分k- 均值(bisecting K-means)的算法。
(三)二分K-均值(bisecting k-means)聚類算法
顧名思義,二分K-均值聚類算法就是每次對(duì)數(shù)據(jù)集(子數(shù)據(jù)集)采取k=2的k-均值聚類劃分,子數(shù)據(jù)集的選取則有一定的準(zhǔn)則。二分K-均值聚類算法 首先將所有點(diǎn)作為一個(gè)簇,第一步是然后將該簇一分為二,之后的迭代是:在所有簇中根據(jù)SSE選擇一個(gè)簇繼續(xù)進(jìn)行二分K-均值劃分,直到得到用戶指定的簇?cái)?shù) 目為止。根據(jù)SSE選取繼續(xù)劃分簇的準(zhǔn)則有如下兩種:
(1)選擇哪一個(gè)簇進(jìn)行劃分取決于對(duì)”其劃分是否可以最大程度降低SSE的值。這需要將每個(gè)簇都進(jìn)行二分劃分,然后計(jì)算該簇二分后的簇SSE之和并計(jì)算其與二分前簇SSE之差(當(dāng)然SSE必須下降),最后選取差值最大的那個(gè)簇進(jìn)行二分。
該方案下的二分k-均值算法的偽代碼形式如下:
***************************************************************
將所有數(shù)據(jù)點(diǎn)看成一個(gè)簇
當(dāng)簇?cái)?shù)目小于k時(shí)
對(duì)每一個(gè)簇
計(jì)算總誤差
在給定的簇上面進(jìn)行k-均值聚類(k=2)
計(jì)算將該簇一分為二后的總誤差
選擇使得誤差最小的那個(gè)簇進(jìn)行劃分操作
***************************************************************
(2)另一種做法是所有簇中選擇SSE最大的簇進(jìn)行劃分,直到簇?cái)?shù)目達(dá)到用戶指定的數(shù)目為止,算法過程與(1)相似,區(qū)別僅在于每次選取簇中SSE最大的簇。
二分K-均值聚類算法的Python實(shí)現(xiàn)
數(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ù)分析師:開啟數(shù)據(jù)職業(yè)發(fā)展新征程? ? 在數(shù)據(jù)成為核心生產(chǎn)要素的今天,數(shù)據(jù)分析師的職業(yè)價(jià)值愈發(fā)凸顯。CDA(Certified D ...
2025-07-03