簡(jiǎn)介
K-means算法是聚類(lèi)算法中最簡(jiǎn)單的一種聋庵，但是里面包含的思想?yún)s不一般炊邦。K-means屬于無(wú)監(jiān)督學(xué)習(xí)，以往的回歸狼渊、樸素貝葉斯箱熬、SVM等都是有類(lèi)別標(biāo)簽y的，也就是說(shuō)樣例中已經(jīng)給出了樣例的分類(lèi)狈邑。而聚類(lèi)的樣本中卻沒(méi)有給定y城须，只有特征x，假設(shè)宇宙星空中的點(diǎn)集可以表現(xiàn)成（X米苹，Y糕伐，Z），聚類(lèi)的目的就是為X找到潛在的Y蘸嘶，并將同類(lèi)別的Y放在一起
算法描述
- 隨機(jī)選取K個(gè)點(diǎn)作為質(zhì)點(diǎn)
- 對(duì)于每一個(gè)樣本點(diǎn)X良瞧，將其歸類(lèi)為距離質(zhì)心點(diǎn)最近的類(lèi)別
- 更新每個(gè)類(lèi)別的質(zhì)心點(diǎn)為隸屬于該類(lèi)別所有點(diǎn)的平均值
- 重復(fù)步驟二三，直至質(zhì)心不變或變化很小
問(wèn)題
1.K-means算法的第一個(gè)問(wèn)題就是如何保證收斂训唱，因?yàn)榍懊嫠惴ǖ慕Y(jié)束條件就是收斂褥蚯，下面我們來(lái)描述一下：
定義畸變函數(shù)J（c，u） ,表示每個(gè)樣本點(diǎn)到其質(zhì)心的距離平方和
此時(shí)我們的重點(diǎn)是研究如何研究是J函數(shù)最小况增，假設(shè)J函數(shù)沒(méi)有函數(shù)達(dá)到最小值赞庶，那樣我們就可以先固定每個(gè)類(lèi)的質(zhì)心，調(diào)整每個(gè)樣例所屬的類(lèi)別來(lái)讓J函數(shù)減小，或者固定類(lèi)別尘执，調(diào)整質(zhì)心也可以使J減小舍哄。這兩個(gè)過(guò)程就是內(nèi)循環(huán)中使J函數(shù)減小的過(guò)程，當(dāng)J函數(shù)最小時(shí)誊锭，u表悬，c也同時(shí)收斂。
由于畸變函數(shù)J是非凸函數(shù)丧靡，意味著我們不能保證取得的最小值是全局最小值蟆沫，也就是說(shuō)k-means對(duì)質(zhì)心初始位置的選取比較感冒，但一般情況下k-means達(dá)到的局部最優(yōu)已經(jīng)滿足需求温治。但如果你怕陷入局部最優(yōu)饭庞，那么可以選取不同的初始值跑多遍k-means，然后取其中最小的J對(duì)應(yīng)的u
凸優(yōu)化有個(gè)非常重要的定理熬荆，即任何局部最優(yōu)解即為全局最優(yōu)解舟山。
EM思想：這里只是指出EM的思想，E步就是估計(jì)隱含類(lèi)別y的期望值卤恳，M步調(diào)整其他參數(shù)使得在給定類(lèi)別y的情況下累盗，極大似然估計(jì)P(x,y)能夠達(dá)到極大值。然后在其他參數(shù)確定的情況下突琳，重新估計(jì)y若债，周而復(fù)始，直至收斂拆融。其實(shí)總體還是一個(gè)迭代優(yōu)化的過(guò)程蠢琳。
缺點(diǎn)：K-means算法有兩個(gè)缺點(diǎn)，第一镜豹、該方法對(duì)K個(gè)質(zhì)心初始位置的選擇比較感冒傲须，一般而言k-means算法只能達(dá)到局部最優(yōu)，因此K個(gè)質(zhì)心初始位置不同逛艰，則達(dá)到的局部最優(yōu)解也會(huì)不一樣躏碳；第二、K值一般要根據(jù)先驗(yàn)知識(shí)散怖，事先給定。
