內(nèi)容參考：
Kmeans算法與KNN算法的區(qū)別
kNN與kMeans聚類算法的區(qū)別
| 對(duì)比項(xiàng) | KNN | K-Means |
|---|---|---|
| 目的 | 為了確定一個(gè)點(diǎn)的分類 | 為了將一系列點(diǎn)集分成K類 |
| 分類算法 | 聚類算法 | |
| 監(jiān)督學(xué)習(xí)（有學(xué)習(xí)語(yǔ)料） | 無監(jiān)督學(xué)習(xí)（沒有學(xué)習(xí)語(yǔ)料） | |
| 沒有明顯的前期訓(xùn)練過程，屬于memory-based learning | 有明顯的前期訓(xùn)練過程 | |
| K的含義 | “k”是用來計(jì)算的相鄰數(shù)據(jù)數(shù)。來了一個(gè)樣本x，要給它分類，即求出它的y，就從數(shù)據(jù)集中，在x附近找離它最近的K個(gè)數(shù)據(jù)點(diǎn)，這K個(gè)數(shù)據(jù)點(diǎn)，類別c占的個(gè)數(shù)最多，就把x的label設(shè)為c | “k”是類的數(shù)目。K是人工固定好的數(shù)字，假設(shè)數(shù)據(jù)集合可以分為K個(gè)簇，由于是依靠人工定好，需要一點(diǎn)先驗(yàn)知識(shí) |
| K值確定后每次結(jié)果固定 | K值確定后每次結(jié)果可能不同，從 n個(gè)數(shù)據(jù)對(duì)象任意選擇 k 個(gè)對(duì)象作為初始聚類中心，隨機(jī)性對(duì)結(jié)果影響較大 | |
| 時(shí)間復(fù)雜度 | O(n) | O(nkt)，t為迭代次數(shù) |
| 常用距離 | 曼哈頓距離、歐式距離和閔可夫斯基距離 | 歐幾里得距離 |
| 相似點(diǎn) | 都包含這樣的過程：給定一個(gè)點(diǎn)，在數(shù)據(jù)集中找離它最近的點(diǎn)。即二者都用到了NN(Nears Neighbor)算法，一般用KD樹來實(shí)現(xiàn)NN。 |
KNN-近鄰算法-分類算法
思想：在訓(xùn)練集中數(shù)據(jù)和標(biāo)簽已知的情況下，輸入測(cè)試數(shù)據(jù)，將測(cè)試數(shù)據(jù)的特征與訓(xùn)練集中對(duì)應(yīng)的特征進(jìn)行相互比較，找到訓(xùn)練集中與之最為相似的前K個(gè)數(shù)據(jù)，則該測(cè)試數(shù)據(jù)對(duì)應(yīng)的類別就是K個(gè)數(shù)據(jù)中出現(xiàn)次數(shù)最多的那個(gè)分類。
算法的描述為：
1）計(jì)算測(cè)試數(shù)據(jù)與各個(gè)訓(xùn)練數(shù)據(jù)之間的距離（一般使用歐氏距離或曼哈頓距離）；
image
2）按照距離的遞增關(guān)系進(jìn)行排序；
3）選取距離最小的K個(gè)點(diǎn)；
4）確定前K個(gè)點(diǎn)所在類別的出現(xiàn)頻率；
5）返回前K個(gè)點(diǎn)中出現(xiàn)頻率最高的類別作為測(cè)試數(shù)據(jù)的預(yù)測(cè)分類。
K-Means聚類算法
把n個(gè)對(duì)象根據(jù)他們的屬性分為k個(gè)聚類以便使得所獲得的聚類滿足：同一聚類中的對(duì)象相似度較高；而不同聚類中的對(duì)象相似度較小
Kmeans算法的缺陷：
- 聚類中心的個(gè)數(shù)K 需要事先給定，但在實(shí)際中這個(gè) K 值的選定是非常難以估計(jì)的，很多時(shí)候，事先并不知道給定的數(shù)據(jù)集應(yīng)該分成多少個(gè)類別才最合適
- Kmeans需要人為地確定初始聚類中心，不同的初始聚類中心可能導(dǎo)致完全不同的聚類結(jié)果。（可以使用Kmeans++算法來解決）
針對(duì)上述第2個(gè)缺陷，可以使用Kmeans++算法來解決
