1. K-近鄰算法####
k-近鄰算法（k Nearest Neighbor），是最基本的分類算法，其基本思想是采用測量不同特征值之間的距離方法進行分類。
2. 算法原理####
存在一個樣本數(shù)據(jù)集合（訓練集），并且樣本集中每個數(shù)據(jù)都存在標簽（即每一數(shù)據(jù)與所屬分類的關(guān)系已知）。輸入沒有標簽的新數(shù)據(jù)后，將新數(shù)據(jù)的每個特征與樣本集中數(shù)據(jù)對應(yīng)的特征進行比較（計算距離），然后提取樣本集中特征最相似數(shù)據(jù)（最近鄰）的分類標簽。一般會取前k個最相似的數(shù)據(jù)，然后取k個最相似數(shù)據(jù)中出現(xiàn)次數(shù)最多的標簽（分類）最后新數(shù)據(jù)的分類。
因此，這是一個很“懶惰”的算法，所謂的訓練數(shù)據(jù)并沒有形成一個“模型”，而是一個新的數(shù)據(jù)需要分類了，去和所有訓練數(shù)據(jù)逐一比較，最終給出分類。這個特征導致在數(shù)據(jù)量較大時，性能很差勁。
3. 算法過程####
對未知類別屬性的數(shù)據(jù)集中的每個點依次執(zhí)行以下操作：
1）計算已知類別數(shù)據(jù)集中的點與當前點之間的距離（歐式距離、曼哈頓距離或者余弦夾角等各種距離算法，具體情況具體分析用哪種）；
2）按照距離遞增次序排序；
3）選取與當前點距離最小的k個點；
4）確定前k個點所在類別的出現(xiàn)頻率；
5）返回前k個點出現(xiàn)頻率最高的類別作為當前點的預測分類。
歐氏距離計算：
- 二維平面上兩點A(x1,y1)與B(x2,y2)間的歐氏距離：
- 三維空間兩點A(x1,y1,z1)與B(x2,y2,z2)間的歐氏距離：
- n維空間兩點的歐式距離以此類推
4. 計算案例####
我還是瞎編一個案例，下表有11個同學的小學成績和12年后讀的大學的情況，現(xiàn)在已知“衛(wèi)”同學的小學成績了，可以根據(jù)kNN來預測未來讀啥大學。
逐一計算各位同學與衛(wèi)同學的距離，然后我們選定3位（即這里的k=3）最為接近的同學，推測衛(wèi)同學最終的大學
3位同學中2個清華，1個北郵，所以衛(wèi)同學很有可能在12年后上清華。
5. 算法要點####
1） K的選擇，一般不超過訓練集數(shù)量的平方根
2）距離更近的近鄰也許更應(yīng)該決定最終的分類，所以可以對于K個近鄰根據(jù)距離的大小設(shè)置權(quán)重，結(jié)果會更有說服力
3）如果采用歐氏距離計算，不同變量間的值域差距較大時，需要進行標準化，否則值域較大的變量將成為最終分類的唯一決定因素
