An Algorithm Summary of Programming Collective Intelligence (3)

k-Nearest Neighbors kNN(不要問我叫什么)
PCI里面用kNN做了一個價格預測模型，還有一個簡單的電影喜好預測。簡單來說就是要對一個東西做數值預測，就要先有一堆已經有數值的東西，從里面找出和要預測的東西相似的，再通過計算這些相似東西的均值來作出預測。

kNN里面首先遇到的問題是如何定義“相似”。

把物品的各種屬性量化，這樣就構成了一個若干維度的向量空間。于是我們說相似就是離得近。這個量化的時候學問很大，畢竟各種不同的屬性用不同的量化方法算出來的數值千差百異。所以還要根據各自的重要性進行伸縮調整，不重要的干脆就乘以一個零直接去掉省心。這是一個非常費心的活兒。不同的問題伸縮系數肯定各異，如何來確定這些系數就要加上主觀判斷、反復調整、結果比較、cross validation。這個時候優化算法是個不錯的選擇。這個我們后面還會提到。

怎么計算離得近呢？方法很多，PCI給了幾個：歐式距離，Pearson相關度和Tanimoto分數。具體如何計算就不重復了，讓我重復也重復不出來。

當然只選擇一個最相似的來進行預測是不夠準確的，所以有了k——選k個最相似的來平均——這就是kNN的來歷。

如何計算平均也是一個很有意思的事情。直接把k個數值加起來一除可以，就是有點簡單粗暴，不像讀書人做的事情，雖然暴力美有時候也是很誘人的。更合理一點的方法是給不同的數值分配權值，離得近的權重大一點，遠的就小一點。突然想起來原來的萬有引力公式，牛老大也喜歡近的，不知道能不能改叭改叭拿過來用。

優點
即使在復雜數值預測問題中依然理解，對系數調整的經驗在處理類似問題時依然很有幫助。
伸縮系數的調整不僅可以改善預測的結果，也說明了對應屬性的重要性。
隨時可以增大數據集

缺點
計算量大
調整系數很煩人

Clustering 聚類

層次聚類和K-means聚類都不做預測，所以也就不需要訓練。PCI里面舉了一個給blog分類的例子。

層次聚類很簡單，第一步的工作也是先量化，構建向量空間，然后不斷尋找最接近的兩個向量并合并他們作為一個新的聚類向量，直到最后只剩下一個聚類為止。

K-means聚類（又是k?!）有所不同。它先任意在向量空間中挑出k個點，然后把所有向量按照和這k個點的遠近劃分成組，每個向量加入距離最近的點所代表的組。然后計算每組的重心，把代表小組的點的位置調整到這個重心上，再重復上面的計算，知道所有的向量分組不再變化為止。

K-means需要你來確定這個K和點的初始位置，這里面沒有什么好辦法。