聚類是一種無監(jiān)督的學(xué)習(xí)徘六，它將相似的對象歸為同一個(gè)簇中。之所以成為k均值是因?yàn)樗梢园l(fā)現(xiàn)k個(gè)不同的簇钱雷，且每個(gè)簇的中心采用簇中所含值的均值計(jì)算而成。
聚類分析視圖將相似對象歸入同一簇棠耕，將不相似對象歸到不同簇。相似這一概念取決于所選擇的相似度計(jì)算方法柠新。前面介紹的各種相似度計(jì)算方法后面還會出現(xiàn)窍荧，而到底用那種相似度方法取決于具體應(yīng)用。
下面我們會構(gòu)建k均值方法并觀察期實(shí)際效果恨憎，然后討論簡單k均值算法中的缺陷蕊退。為了解決其中的一些缺陷，可以通過后處理來產(chǎn)生更好的簇憔恳。接著會給出一個(gè)更有效的稱為二分k均值的聚類算法瓤荔。最后給出一個(gè)實(shí)例應(yīng)用。
10.1? k均值聚類算法
k均值是發(fā)現(xiàn)給定數(shù)據(jù)集的k個(gè)簇的算法钥组。簇的個(gè)數(shù)k是用戶給定的输硝，每個(gè)簇通過其質(zhì)心，即簇中所有點(diǎn)的質(zhì)心來描述程梦。
k均值算法的工作流程：首先点把，隨機(jī)確定k個(gè)初始點(diǎn)為質(zhì)心。然后將數(shù)據(jù)集的每個(gè)點(diǎn)分配到一個(gè)簇屿附，具體來講郎逃，為每個(gè)點(diǎn)找距其最近的質(zhì)心，并將其分配給該質(zhì)心所對應(yīng)的簇挺份，這一步完成之后褒翰，每個(gè)簇的質(zhì)心更新為該簇所有點(diǎn)的均值。
求與某數(shù)據(jù)點(diǎn)最近的質(zhì)心意味著要進(jìn)行某種距離計(jì)算匀泊，這里使用的是歐氏距離影暴。此外，初始的k個(gè)隨機(jī)質(zhì)心需要在整個(gè)數(shù)據(jù)集邊界范圍之內(nèi)探赫。對數(shù)據(jù)集進(jìn)行畫圖如下：
PS：畫個(gè)圖也費(fèi)我老半天時(shí)間額~郁悶~
算法主要就是計(jì)算質(zhì)心-分配-重新計(jì)算，不斷迭代伦吠，直到所有數(shù)據(jù)點(diǎn)的簇分配結(jié)果不再改變?yōu)橹棺倍摇Ｗ詈笏惴ǚ祷貎蓚€(gè)矩陣：centroids有k行n列，用來裝質(zhì)心數(shù)據(jù)毛仪，k行表示k個(gè)質(zhì)心搁嗓，n行表示質(zhì)心數(shù)據(jù)維度。clusterAssment有m行2列箱靴，m行對應(yīng)數(shù)據(jù)集中m個(gè)數(shù)據(jù)點(diǎn)腺逛，第一列記錄該數(shù)據(jù)點(diǎn)所在簇索引值，第二列記錄該數(shù)據(jù)點(diǎn)與所在簇質(zhì)心的距離衡怀，即存儲誤差棍矛。
PS：python神操作：數(shù)組b賦值給矩陣a安疗，則a成了數(shù)組類型并得到相應(yīng)的值。而數(shù)組b賦給矩陣a的某一列后够委，數(shù)據(jù)a還是矩陣荐类，并得到了b的對應(yīng)值。此外茁帽，數(shù)組可以與某一個(gè)數(shù)加減乘除玉罐，結(jié)果是數(shù)組的對應(yīng)元素與這個(gè)值加減乘除。最后潘拨，random.rang(m,n)生成m行n列數(shù)組吊输，數(shù)組元素是0到1之間的隨機(jī)數(shù)。
10.2 使用后處理來提高聚類性能
在k均值聚類中簇的數(shù)目k是一個(gè)用戶預(yù)先定義好的參數(shù)铁追，而用戶并不知道該設(shè)置成多少為最好璧亚。在包含簇結(jié)果的矩陣中保存著每個(gè)點(diǎn)的誤差，即該點(diǎn)到簇質(zhì)心的距離平方值脂信。下面我們可以用該誤差來評價(jià)聚類質(zhì)量的方法癣蟋。
k均值算法收斂但聚類效果較差的原因：k均值算法收斂到局部最小值，而不是全局最小值狰闪。
一種用于度量聚類效果的指標(biāo)是SSE（誤差平方和）疯搅，即clusterAssment矩陣的第一列之和，SSE值越小表示數(shù)據(jù)越接近它們的質(zhì)心埋泵，聚類效果也越好幔欧。一種肯定可以降低SSE值的方法是增加簇的個(gè)數(shù)，但是這違背了聚類的目標(biāo)丽声，聚類的目標(biāo)是在保持簇不變的情況下提高簇的質(zhì)量礁蔗。
所以，我們應(yīng)該對簇進(jìn)行后處理雁社，一種方法是將具有最大SSE的簇劃分成兩個(gè)簇浴井，具體實(shí)現(xiàn)就是將最大簇包含的點(diǎn)過濾出來，然后再這些點(diǎn)上運(yùn)行k均值算法霉撵，k設(shè)為2磺浙。而為了保持簇的總數(shù)不變，可以將某兩個(gè)簇合并徒坡，那么又該按照什么依據(jù)合并呢撕氧？
有兩種量化辦法：第一種，合并最近的質(zhì)心喇完，即計(jì)算所有質(zhì)心之間的距離伦泥，然后合并最近的兩個(gè)質(zhì)心。第二種，合并兩個(gè)使得SSE增幅最小的質(zhì)心不脯，即合并兩個(gè)簇然后算總SSE值府怯，這需要在所有可能的兩個(gè)簇上重復(fù)上述操作，知道找到合并最佳的簇為止跨新。
10.3? 二分k均值算法
為了克服k均值算法收斂于局部最小值的問題，有人提出了二分k均值算法坏逢，該算法首先將所有點(diǎn)作為一個(gè)簇域帐，然后將該簇一分為二，之后選擇其中一個(gè)簇繼續(xù)一分為二是整，選擇哪個(gè)簇取決于對其劃分是否可以最大程度降低SSE的值肖揣。上述劃分過程不斷重復(fù)，直到得到用戶指定的簇?cái)?shù)為止浮入。
另一種做法是選擇SSE最大的簇進(jìn)行劃分龙优，直到簇的數(shù)目達(dá)到用戶指定的數(shù)目為止。
下面的操作是對第一種方法的實(shí)現(xiàn)事秀，即劃分依據(jù)是降低劃分后總的SSE值彤断。代碼思路很簡單，就是對所有的簇都進(jìn)行k均值劃分易迹，然后計(jì)算總SSE值宰衙，找到能使SSE值最小的劃分簇，將其劃分睹欲，將被劃分簇的質(zhì)心矩陣和誤差矩陣加入總數(shù)據(jù)集的質(zhì)心矩陣和誤差矩陣供炼，直到簇的個(gè)數(shù)滿足用戶指定的參數(shù)。
下面給出用二分k均值算法進(jìn)行劃分后的結(jié)果圖：
此次劃分用的數(shù)據(jù)與上一張圖一樣袋哼，只是方法不同：前面用的是k均值聚類算法，初始質(zhì)心是隨機(jī)選取的闸衫，劃分后得到的效果并不好涛贯，這從圖上就能看出來。而這里用的是二分k均值算法蔚出，是從一個(gè)簇不斷劃分而來疫蔓，劃分結(jié)果明顯比上一張好些。
下面我又用二分k均值聚類算法在另一個(gè)數(shù)據(jù)集做了劃分身冬，結(jié)果如下：
劃分結(jié)果~外瑞固的~
10.4? 本章小結(jié)
聚類是一種無監(jiān)督學(xué)習(xí)方法。所謂無監(jiān)督學(xué)習(xí)方法酥筝，就是事先不知道要尋找的內(nèi)容滚躯，即沒有目標(biāo)向量。聚類將數(shù)據(jù)點(diǎn)歸到多個(gè)簇中，其中相似的點(diǎn)處于同一個(gè)簇掸掏，而不相似的點(diǎn)處于不同的簇中茁影。聚類可以使用多種不同的方法來計(jì)算相似度。
一種廣泛使用的聚類方法是k均值算法丧凤，其中k是用戶指定的要?jiǎng)?chuàng)建的簇的數(shù)目募闲。k均值聚類算法以k個(gè)隨機(jī)質(zhì)心開始。算法會計(jì)算每個(gè)點(diǎn)到質(zhì)心的距離愿待。每個(gè)點(diǎn)會分配到距其最近的簇質(zhì)心浩螺，然后緊接著基于新分配到簇的點(diǎn)更新簇質(zhì)心。以上過程重復(fù)數(shù)次仍侥，直到簇質(zhì)心不再改變要出。
這個(gè)方法簡單有效，但容易受到初始簇質(zhì)心的影響农渊。為了更好的聚類效果患蹂，可以使用一種稱為二分k均值的聚類算法。
二分k均值聚類算法首先將所有點(diǎn)作為一個(gè)簇砸紊，然后使用k均值算法（k=2）對其劃分传于。下一迭代時(shí)，選擇有最大誤差的簇進(jìn)行劃分醉顽。該過程重復(fù)直到k個(gè)簇創(chuàng)建成功為止格了。
二分k均值的聚類效果要好于k均值算法。
over~? ^_^
