AI筆記18 - K-Nearest Neighbors

沒有build model的ML

這是一個不建立model的ML方法。
他假設training samples如果有相似的特質的話，應該要歸類成同一個label。

特質就是一個feature vector，例如身高 體重 收入等等組成的d維向量，這些feature vectors在d維空間中看成點的話，彼此的euclidean distance就是相似度的依據：

當然也可以用其他的distance measurement！

Classification Algorithm

因為沒有training, 也沒有建立model，所以classification基本上只是把data point加入某個set的過程而已，加入的過程中，自然依據了distance做了分類了。

假設有一個未知需要分類的data xq，如果把他加入KNN dataset D，我們可以得到xq的KNN:

這k個最近的鄰居其實就能告訴xq他自己是屬於哪一群體？所謂近朱者赤：

當然如果這k個鄰居跨屬兩個不同的分類的話，那就是民主機制，數人頭了：

Decision Boundary

不過雖然KNN不建立function/model，但是它可能會形成non-linear decision boundary，這是其分類機制使然。假設把一個平面劃分成等距的小點，再根據平面上已經有的data points來做3-NN的話，可以看出nonlinear decision boundary:

優缺點

優點：
1. 超簡單，沒有複雜運算
2. 容易extend，每次加入新的data point就能延伸classification能力
3. 實務上用了很久了，重點會是在怎麼找出optimal K。包括以下applications:

缺點：
1. 需要儲存所有的data points，才能進行classification，佔據大量空間
2. run time慢！因為一個query需要O(nd) time，假設data set D有n個data，而且feature vector是d-dimensional
3. 如果feature vector dimension 太大，則distance變成沒有意義（ML課程會說明）。