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

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

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

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

當(dāng)然只選擇一個最相似的來進行預(yù)測是不夠準(zhǔn)確的，所以有了k——選k個最相似的來平均——這就是kNN的來歷。

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

優(yōu)點
即使在復(fù)雜數(shù)值預(yù)測問題中依然理解，對系數(shù)調(diào)整的經(jīng)驗在處理類似問題時依然很有幫助。
伸縮系數(shù)的調(diào)整不僅可以改善預(yù)測的結(jié)果，也說明了對應(yīng)屬性的重要性。
隨時可以增大數(shù)據(jù)集

缺點
計算量大
調(diào)整系數(shù)很煩人

Clustering 聚類

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

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

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

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

?

Neural Networks 神經(jīng)網(wǎng)絡(luò)（是這么說吧）

nn可以用來做分類和數(shù)值型預(yù)測。nn有很多類型，PCI里面介紹的是一種多層認知網(wǎng)絡(luò)，有一層輸入神經(jīng)元和若干層（這里是一層）隱藏神經(jīng)元。每個神經(jīng)元有自己的輸出值，連接神經(jīng)元的突觸有各自的權(quán)重。

使用nn計算的方法叫feed forward，是通過對所有連接到這個節(jié)點上一層神經(jīng)元的輸出值與相應(yīng)的突觸權(quán)重的乘積求和再用tanh（PCI里面）計算得到的。最后一層的所有輸出值可以用來幫助挑選結(jié)果。這個過程中對神經(jīng)元輸出的改變保留在nn中。

PCI里面用了一個通過記錄搜索引擎用戶點擊結(jié)果的日志來訓(xùn)練的nn實例。搜索關(guān)鍵詞或者關(guān)鍵詞的組合作為樣本中的輸入數(shù)據(jù)，而用戶最終的點擊的搜索結(jié)果集中的鏈接作為樣本中的輸出數(shù)據(jù)。隱藏層的節(jié)點表示不同輸入之間的組合。

nn可以使用隨機值作為突觸的權(quán)重，而且單個輸入值和輸出沒有直接概率聯(lián)系（因為網(wǎng)絡(luò)是通過輸入值的組合的集合來計算的，這和貝葉斯的概率矩陣不一樣。當(dāng)然如果所有的輸入都是單個值的話那就和貝葉斯一樣了），所以不能像貝葉斯那樣直接把輸入扔進去來修正網(wǎng)絡(luò)中突觸的權(quán)重。nn的一種訓(xùn)練方法是back propagate（叫反向傳播？）。

bp的方法是先用現(xiàn)有網(wǎng)絡(luò)計算輸出，然后和給定的樣本輸出比較，計算得到誤差，用誤差來修正隱藏層突觸的權(quán)重，再計算隱藏層的誤差，來修正輸入層。

優(yōu)點：
支持增量訓(xùn)練
適應(yīng)任何類型輸入
缺點：
這是一個黑盒過程，中間的隱藏層很難解釋出具體含義
對于訓(xùn)練頻率和網(wǎng)絡(luò)大小沒有固定固定規(guī)律可循，多是通過實驗得到

對于nn的黑盒特性倒是想說兩句，nn本來就是仿生的方式解決問題，我們自己的神經(jīng)系統(tǒng)也就這樣。感應(yīng)電流從神經(jīng)末梢沿著神經(jīng)線傳入大腦以后誰知道是按照哪條固定線路走的啊，用科學(xué)家的話，那是刺激了大腦中的某個區(qū)域。但是具體是這個區(qū)域中的那個或者那幾個細胞在起決定作用就說不清楚了。

其實對于面向某些領(lǐng)域的nn來說，生物的神經(jīng)系統(tǒng)倒是可以更多的借鑒，可以對輸入和輸出做劃分，畢竟手上傳來的感覺對管腳丫子的大腦皮層區(qū)域影響微乎其微。

Support-Vector Machines 支持向量機 （感謝好同學(xué)的解釋）

這是PCI里面最復(fù)雜的分類算法。svm可以計算數(shù)值數(shù)據(jù)集應(yīng)該屬于的分類。它在目標(biāo)平面（空間）里計算出分割線（面）來把數(shù)據(jù)集劃分成屬于不同類型的區(qū)域，以使表示數(shù)據(jù)的點到分割線（平面）的距離最大。有時候需要對數(shù)據(jù)集進行變換使同一類數(shù)據(jù)相對集中，不同類別相對分的清一點。這叫Kernel trick或者Kernel method。

問題的關(guān)鍵是找到分割線（面）。這就要靠那些可能靠近分割線（面）的數(shù)據(jù)點了。這些點我們稱為支持向量，這也是這個算法名稱的由來。但是至于如何找這些點和通過這些點來找分割線（面）PCI就沒有交代了，原因是太復(fù)雜（畢竟是應(yīng)用型的書啊），只是用了一個現(xiàn)成的libsvm :-(

svm的訓(xùn)練只要是通過cross validation來迭代改進，這需要有大量樣本數(shù)據(jù)才能得到很好的結(jié)果。所以svm也只適合于大數(shù)據(jù)量的分類。

優(yōu)點：
很好很強大
速度快
可以處理不同類型數(shù)據(jù)（要轉(zhuǎn)換成數(shù)值）
缺點：
好的核變換算法不好找，而且沒有通用的方法來找
cross validation需要有大量數(shù)據(jù)做基礎(chǔ)

就按照最后一章的順序來說吧。很多名字都不知道中文該怎么說，就直接用英文名稱了。

Naive Bayesian Classifier 樸素貝葉斯分類器
nb算法是通過學(xué)習(xí)樣本中已經(jīng)分類的條目，計算生成條目中的特性相對于類別的概率矩陣，然后根據(jù)待分類條目中特性在這個矩陣中的值來反向計算條目的類別概率。

P(Category|Item)=P(Item|Category)*P(Category)/P(Item)

在靜態(tài)樣本中，P(Item)是固定的，所以可以去掉簡化計算。但是如果樣本集是動態(tài)的，就需要考慮進來。

P(Item|Category)=P(Feature1|Category)*P(Feature2|Category)*...

優(yōu)點：
速度快
增量訓(xùn)練時可以不使用舊樣本
容易理解
分類效果往往比想象的好
缺點：
對于內(nèi)容龐雜的大分類來說效果不太好，特別是出現(xiàn)比較中性的特性組合時更是如此。

Decision Tree Classifier 決策樹
dt算法進行分類計算是很簡單直觀的，它的技巧在于決策樹的構(gòu)造過程。樣本是已知的條件結(jié)果數(shù)據(jù)矩陣，需要決定的是用來分類的條件順序。為了得到這個順序，就要針對每個條件計算單純應(yīng)用這個條件分類后結(jié)果的混合度，也就是看用哪個條件來分可以分得更清楚一些。確定了最好的分類條件，就把數(shù)據(jù)分開成若干子集，對每個子集再計算最佳分類條件，以此類推，直到子集只包含一個結(jié)果或者達到某些終止條件。

dt算法有兩個有意思的地方。一是如何計算應(yīng)用某個條件得到的分類結(jié)果的混合度。書里面給了一個簡單的計數(shù)算法和一個熵算法（好親切啊）。

p(i)=frequency(outcome)=count(outcome)/count(total rows)
Entropy=sum of p(i)*log(p(i) for all outcomes

進一步計算information gain:
weight1 = size of subset1 / size of original set
weight2 = size of subset2 / size of original set
gain = entropy(original) – weight1*entropy(set1) – weight2*entropy(set2)

另外一個有意思的地方是對不同類型的條件數(shù)據(jù)如何選擇分類點。對于是否問題這個比較容易解決，但是對于數(shù)值或者字符串或者更復(fù)雜的類型就要特殊情況特殊處理了。

優(yōu)點：
結(jié)果簡潔直觀
可以處理不同的條件數(shù)據(jù)類型
缺點：
不能通過增量訓(xùn)練來改進，生成決策樹必須使用整個已知樣本集。
大數(shù)據(jù)集可能存在的眾多條件會產(chǎn)生巨大繁雜的決策樹，分類計算會變得緩慢。

轉(zhuǎn)自：http://www.cnblogs.com/ysjxw/category/128788.html

總結(jié)

以上是生活随笔為你收集整理的An Algorithm Summary of Programming Collective Intelligence的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。