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í) |
