Supervised Learning

給你一些數(shù)據(jù)集屡拨，用算法去訓練函數(shù)份招，訓練出來后，就可以投入新的數(shù)據(jù)進行預測哩罪。

Instance Based Learning

不包含訓練函數(shù)這個過程授霸，只需要把所有數(shù)據(jù)放在數(shù)據(jù)庫里巡验，投入新的數(shù)據(jù)時，只需要去數(shù)據(jù)庫里查找碘耳，

優(yōu)點是：

Remember：可信显设，不需要平滑什么的近似

Fast：不需要 learning

Simple：

缺點是：

Overfitting：太依賴已有數(shù)據(jù)了

看起來只能返回已有數(shù)據(jù)，無法返回新數(shù)據(jù)

應用舉例：

紅色很貴辛辨，藍色中等捕捂，綠色最便宜，要預測黑色點的顏色斗搞。

方法就是看 Nearest Neighbor指攒，如果只看一個neighbor，有些點比較容易看出來僻焚，有些點需要看很多 neighbor 才能看準允悦，不能單純只取一個最近的，所以是 K Nearest Neighbors溅呢。

相似度比較

K-近鄰算法（KNN）概述?

最簡單最初級的分類器是將全部的訓練數(shù)據(jù)所對應的類別都記錄下來澡屡，當測試對象的屬性和某個訓練對象的屬性完全匹配時，便可以對其進行分類咐旧。但是怎么可能所有測試對象都會找到與之完全匹配的訓練對象呢，其次就是存在一個測試對象同時與多個訓練對象匹配绩蜻，導致一個訓練對象被分到了多個類的問題铣墨，基于這些問題呢，就產(chǎn)生了KNN办绝。

? ? ?KNN是通過測量不同特征值之間的距離進行分類伊约。它的思路是：如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別孕蝉，其中K通常是不大于20的整數(shù)屡律。KNN算法中，所選擇的鄰居都是已經(jīng)正確分類的對象降淮。該方法在定類決策上只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別超埋。

? ? ?下面通過一個簡單的例子說明一下：如下圖，綠色圓要被決定賦予哪個類佳鳖，是紅色三角形還是藍色四方形霍殴？如果K=3，由于紅色三角形所占比例為2/3系吩，綠色圓將被賦予紅色三角形那個類来庭，如果K=5，由于藍色四方形比例為3/5穿挨，因此綠色圓被賦予藍色四方形類月弛。

由此也說明了KNN算法的結果很大程度取決于K的選擇肴盏。

? ? ?在KNN中，通過計算對象間距離來作為各個對象之間的非相似性指標帽衙，避免了對象之間的匹配問題叁鉴，在這里距離一般使用歐氏距離或曼哈頓距離：

同時，KNN通過依據(jù)k個對象中占優(yōu)的類別進行決策佛寿，而不是單一的對象類別決策幌墓。這兩點就是KNN算法的優(yōu)勢。

?? 接下來對KNN算法的思想總結一下：就是在訓練集中數(shù)據(jù)和標簽已知的情況下冀泻，輸入測試數(shù)據(jù)常侣，將測試數(shù)據(jù)的特征與訓練集中對應的特征進行相互比較，找到訓練集中與之最為相似的前K個數(shù)據(jù)弹渔，則該測試數(shù)據(jù)對應的類別就是K個數(shù)據(jù)中出現(xiàn)次數(shù)最多的那個分類胳施，其算法的描述為：

1）計算測試數(shù)據(jù)與各個訓練數(shù)據(jù)之間的距離；

2）按照距離的遞增關系進行排序肢专；

3）選取距離最小的K個點舞肆；

4）確定前K個點所在類別的出現(xiàn)頻率；

5）返回前K個點中出現(xiàn)頻率最高的類別作為測試數(shù)據(jù)的預測分類博杖。

K-近鄰的優(yōu)缺點

KNN算法的優(yōu)點：

1）簡單椿胯、有效。

2）重新訓練的代價較低（類別體系的變化和訓練集的變化剃根，在Web環(huán)境和電子商務應用中是很常見的）哩盲。

3）計算時間和空間線性于訓練集的規(guī)模（在一些場合不算太大）。

4）由于KNN方法主要靠周圍有限的鄰近的樣本狈醉，而不是靠判別類域的方法來確定所屬類別的廉油，因此對于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合苗傅。

5）該算法比較適用于樣本容量比較大的類域的自動分類抒线，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。

KNN算法缺點：

1）KNN算法是懶散學習方法（lazy learning,基本上不學習）渣慕，一些積極學習的算法要快很多嘶炭。

2）類別評分不是規(guī)格化的（不像概率評分）。

3）輸出的可解釋性不強摇庙，例如決策樹的可解釋性較強旱物。

4）該算法在分類時有個主要的不足是，當樣本不平衡時卫袒，如一個類的樣本容量很大宵呛，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時夕凝，該樣本的K個鄰居中大容量類的樣本占多數(shù)宝穗。該算法只計算“最近的”鄰居樣本户秤，某一類的樣本數(shù)量很大，那么或者這類樣本并不接近目標樣本逮矛，或者這類樣本很靠近目標樣本鸡号。無論怎樣，數(shù)量并不能影響運行結果须鼎【ò椋可以采用權值的方法（和該樣本距離小的鄰居權值大）來改進。

5）計算量較大晋控。目前常用的解決方法是事先對已知樣本點進行剪輯汞窗，事先去除對分類作用不大的樣本。

再講一下KNN是如何匹配class的

1看每個class的出現(xiàn)頻率

2通過計算每個class離中心得距離來weight

舉例

如果各class頻率和weighted distance都一樣怎么辦赡译？

隨機一個class

選一個有最高可能性的class（不太明白這里怎么選）

k+1

那K應該取多少呢仲吏？

取小了會導致有noise（過擬合）使得classifier性能變差

取大了會導致性能傾向于0-r（也差）

Overfitting

在統(tǒng)計學和機器學習中，overfitting一般在描述統(tǒng)計學模型隨機誤差或噪音時用到蝌焚。它通常發(fā)生在模型過于復雜的情況下裹唆，如參數(shù)過多等。overfitting會使得模型的預測性能變弱只洒，并且增加數(shù)據(jù)的波動性许帐。

發(fā)生overfitting是因為評判訓練模型的標準不適用于作為評判該模型好壞的標準，模型通常會增強模型在訓練模型的預測性能红碑。但是模型的性能并不是由模型在訓練集的表現(xiàn)好壞而決定舞吭，它是由模型在未知數(shù)據(jù)集上的表現(xiàn)確定的。當模型開始“memorize”訓練數(shù)據(jù)而不是從訓練數(shù)據(jù)中“l(fā)earning”時析珊，overfitting就出現(xiàn)了。比如蔑穴，如果模型的parameters大于或等于觀測值的個數(shù)忠寻，這種模型會顯得過于簡單，雖然模型在訓練時的效果可以表現(xiàn)的很完美存和，基本上記住了數(shù)據(jù)的全部特點奕剃，但這種模型在未知數(shù)據(jù)的表現(xiàn)能力會大減折扣，因為簡單的模型泛化能力通常都是很弱的捐腿。

Nearest Prototype Classification

取每個class的instance的平均點纵朋，然后計算中心店離每個class的距離，選最短的那個