1.1 k近鄰學(xué)習(xí)
k近鄰學(xué)習(xí)（k-Nearest Neighbor,簡稱kNN）學(xué)習(xí)是一種常見的監(jiān)督學(xué)習(xí)方法，其工作機(jī)制非常簡單：給定測試樣本，基于某種距離度量找出訓(xùn)練集中與其最靠近的k個(gè)訓(xùn)練樣本，然后基于這k個(gè)“鄰居”的信息來進(jìn)行預(yù)測。通常，在分類任務(wù)中可使用“投票法”，即選擇這k個(gè)樣本中出現(xiàn)最多的類別標(biāo)記作為預(yù)測結(jié)果；在回歸任務(wù)中可使用“平均法”，即將這k個(gè)樣本的實(shí)值輸出標(biāo)記的平均值作為預(yù)測結(jié)果；還可基于距離遠(yuǎn)近進(jìn)行加權(quán)平均或加權(quán)投票，距離越近的樣本權(quán)重越大。
與前面介紹的學(xué)習(xí)相比，k近鄰學(xué)習(xí)有一個(gè)明顯的不同之處：它似乎沒有顯示的訓(xùn)練過程！事實(shí)上，它是“懶惰學(xué)習(xí)“（laze learning）的代表，此類學(xué)習(xí)技術(shù)在訓(xùn)練階段僅僅是把樣本保存起來，訓(xùn)練時(shí)間開銷為零，待收到測試樣本后在進(jìn)行處理；相應(yīng)的，那些在訓(xùn)練階段就對樣本進(jìn)行學(xué)習(xí)處理的方法，稱為“急切學(xué)習(xí)”（eager learning）.
下圖是k近鄰分類器的一個(gè)示意圖。顯然，k是一個(gè)重要參數(shù)，當(dāng)k取不同值時(shí)，分類結(jié)果會(huì)有顯著的不同。另一方面，若采用不同的距離計(jì)算方式，則找出“近鄰”可能有顯著差別，從而也會(huì)導(dǎo)致分類結(jié)果有顯著不同。
暫且假設(shè)距離計(jì)算是“恰當(dāng)”的，即能夠恰當(dāng)?shù)卣页鰇個(gè)近鄰，我們來對“最近鄰分類器”（1NN,即k=1）在二分類問題上的性能做一個(gè)簡單的討論。
給定測試樣本x，若其最近鄰樣本為z，則最近鄰分類器出錯(cuò)的概率就是x與z類別標(biāo)記不同的概率，即
假設(shè)樣本獨(dú)立同分布，且對任意x和任意小正數(shù)，在x附近
距離范圍內(nèi)總能找到一個(gè)訓(xùn)練樣本；換言之，對任意測試樣本，總能在任意范圍內(nèi)找到上式中的訓(xùn)練樣本z。令
表示貝葉斯最優(yōu)分類器的結(jié)構(gòu)，有
于是我們得到了有點(diǎn)令人吃驚的結(jié)論：最近鄰分類器雖簡單，但它的泛化能力錯(cuò)誤率不超過貝葉斯最優(yōu)分類器的錯(cuò)誤率的兩倍。
1.2 低維嵌入
