1. K-means
作用
把n個(gè)對(duì)象根據(jù)他們的屬性分為K個(gè)聚類(lèi),使得
- 同一個(gè)聚類(lèi)中的對(duì)象相似度較高
- 不同聚類(lèi)中的對(duì)象相似度較小
算法過(guò)程
一開(kāi)始是原始數(shù)據(jù)兔毒,雜亂無(wú)章,看起來(lái)都一樣馋袜,沒(méi)有l(wèi)abel旨巷。
- 人為指定聚類(lèi)個(gè)數(shù),令K=2尿赚;
- 人為指定初始聚類(lèi)中心(需要一定的先驗(yàn)知識(shí)):隨機(jī)在坐標(biāo)上選K(此處K=2)個(gè)點(diǎn)散庶,作為聚類(lèi)中心;
- 把每個(gè)數(shù)據(jù)樣本劃分到最近的中心點(diǎn)那一簇凌净;
- 劃分完后更新每個(gè)簇的中心(即把該簇的所有數(shù)據(jù)點(diǎn)的坐標(biāo)加起來(lái)取平均值)悲龟,得到新的簇中心后,再次進(jìn)行操作3冰寻,就這樣不斷“劃分——更新——?jiǎng)澐帧隆毙虢蹋烂總€(gè)簇的中心不再移動(dòng)為止。
注意
求簇中心的算法:
1. 使用每個(gè)點(diǎn)的坐標(biāo)平均值
2.
3.
4.
算法特點(diǎn)
- 聚類(lèi)中心的個(gè)數(shù)K要事先給定,但在實(shí)際中這個(gè)K是非常難以估計(jì)的轻腺,很多時(shí)候事先并不知道該分幾個(gè)類(lèi)才合適乐疆。
- 需要人為地指定初始聚類(lèi)中心,不同的初始聚類(lèi)中心可能導(dǎo)致完全不同的聚類(lèi)結(jié)果贬养。(這個(gè)缺陷可以使用K-means++改進(jìn))挤土。
2. K-means++
算法過(guò)程
- 從輸入的數(shù)據(jù)點(diǎn)集合中隨機(jī)選擇一個(gè)點(diǎn)作為第一個(gè)聚類(lèi)中心
- 對(duì)于數(shù)據(jù)集中的每一個(gè)點(diǎn)x,計(jì)算它與最近聚類(lèi)中心(指已選擇的聚類(lèi)中心)的距離D(x)
- 選擇一個(gè)新的數(shù)據(jù)點(diǎn)作為新的聚類(lèi)中心误算,選擇的原則是:D(x)較大的點(diǎn)仰美,被選取作為聚類(lèi)中心的概率較大
- 重復(fù)2和3直到K個(gè)聚類(lèi)中心被選出來(lái)
- 利用這K個(gè)初始的聚類(lèi)中心來(lái)運(yùn)行標(biāo)準(zhǔn)的K-means算法。
注意
如何使D(x)較大的點(diǎn)儿礼,被選取作為聚類(lèi)中心的概率較大
A:
1. 先從數(shù)據(jù)庫(kù)中隨機(jī)挑個(gè)隨機(jī)點(diǎn)當(dāng)“種子點(diǎn)”
2. 對(duì)每個(gè)未被選中的點(diǎn):計(jì)算其和最近的“種子點(diǎn)”的距離D(x)保存在一個(gè)數(shù)組里咖杂,然后把這些距離加起來(lái)得到Sum(D(x))
3. 再取一個(gè)隨機(jī)值,用權(quán)重的方式來(lái)取下一個(gè)“種子點(diǎn)”:
1)先取一個(gè)能落在Sum(D(x))中的隨機(jī)值Random
2)對(duì)于未被選中的數(shù)據(jù)點(diǎn)蜘犁,如果Random-=D(x)后翰苫,Random<=0止邮,則將該數(shù)據(jù)點(diǎn)選做種子點(diǎn)
4. 重復(fù)2和3这橙,直到K個(gè)聚類(lèi)中心被選出來(lái)
5. 利用這K個(gè)聚類(lèi)中心運(yùn)行標(biāo)準(zhǔn)的K-means算法
算法特點(diǎn)
- 聚類(lèi)中心的個(gè)數(shù)K要事先給定,但在實(shí)際中這個(gè)K是非常難以估計(jì)的导披,很多時(shí)候事先并不知道該分幾個(gè)類(lèi)才合適屈扎。
- 不需人為地指定初始聚類(lèi)中心(是對(duì)K-means的改進(jìn))。
3. KNN
4. KNN和K-means比較
KNN | K-means |
---|---|
分類(lèi)算法 | 聚類(lèi)算法 |
監(jiān)督學(xué)習(xí) | 無(wú)監(jiān)督學(xué)習(xí) |
喂給它的數(shù)據(jù)集是帶label的數(shù)據(jù) | 喂給它的數(shù)據(jù)集是無(wú)label的 |
沒(méi)有明顯的前期訓(xùn)練過(guò)程撩匕,屬于memory-based learning | 有明顯的前期訓(xùn)練過(guò)程 |
K的含義:…… | K是人工固定好的數(shù)字鹰晨,假設(shè)數(shù)據(jù)集可以分為K個(gè)簇,由于是依靠人工定好止毕,需要一點(diǎn)先驗(yàn)知識(shí) |