## 一、knn簡介
k臨近算法采用測量不同特征值之間的距離來分類,在樣本數(shù)據(jù)及中找出k個待分類數(shù)據(jù)最相似的樣本，這k個樣本中出現(xiàn)最多的類別作為待分類樣本的類別
### 算法流程
```
遍歷所有樣本
對輸入數(shù)據(jù)計算和每一個樣本數(shù)據(jù)的誤差
找出k個誤差最小的樣本
統(tǒng)計k個最相似的樣本中出現(xiàn)最多的類別作為待分類樣本類別
```
## 二、代碼實(shí)現(xiàn)
### 樣本數(shù)據(jù)
這是一份約會網(wǎng)站數(shù)據(jù),
**數(shù)據(jù)有三種分類：**
1. largeDoses 極具魅力的人
2. smallDoses 魅力一般的人
3. didntlike????? 不喜歡的人
**每條數(shù)據(jù)共有三種特征:**
1. 每年乘飛機(jī)飛行里程數(shù)
2. 玩游戲時間百分比
3. 每周消耗冰欺凌公升數(shù)
```
40920??? 8.326976??? 0.953952??? largeDoses
14488??? 7.153469??? 1.673904??? smallDoses
26052??? 1.441871??? 0.805124??? didntLike
75136??? 13.147394??? 0.428964??? didntLike
38344??? 1.669788??? 0.134296??? didntLike
72993??? 10.141740??? 1.032955??? didntLike
35948??? 6.830792??? 1.213192??? largeDoses
42666??? 13.276369??? 0.543880??? largeDoses
67497??? 8.631577??? 0.749278??? didntLike
35483??? 12.273169??? 1.508053??? largeDoses
... ...
```
這些數(shù)據(jù)保存在datingTestData.txt中。
### 讀取數(shù)據(jù)
將數(shù)據(jù)文件中特征值讀取為numpy 3*n數(shù)組ret_mat
標(biāo)簽去讀取為1*n數(shù)組labels
```
for line in lines:
line = line.strip()
l = line.split('\t')
ret_mat[index] = l[0:3]
labels.append(l[-1])
index += 1
```
----------
### 數(shù)據(jù)歸一化
不同評價指標(biāo)往往具有不同的量綱和量綱單位，這樣的情況會影響到數(shù)據(jù)分析的結(jié)果，為了消除指標(biāo)之間的量綱影響，需要進(jìn)行數(shù)據(jù)標(biāo)準(zhǔn)化處理，以解決數(shù)據(jù)指標(biāo)之間的可比性。原始數(shù)據(jù)經(jīng)過數(shù)據(jù)標(biāo)準(zhǔn)化處理后，各指標(biāo)處于同一數(shù)量級，適合進(jìn)行綜合對比評價.
#### 常用的歸一化方法有:
* min-max標(biāo)準(zhǔn)化法
* Z-score標(biāo)準(zhǔn)化方法
這里我們使用min-max標(biāo)準(zhǔn)化法。
$\frac{x-minval}{maxval-minval}$
### 分類
knn與其他機(jī)器學(xué)習(xí)方法不同的是，沒有訓(xùn)練過程，直接對數(shù)據(jù)集上所有數(shù)據(jù)計算。分類時需要計算待分類樣本與每一個樣本數(shù)據(jù)的相似度，這里相似度我們用L2距離(就是我們常見的歐氏距離)表示
$L_2 = \sqrt{\sum_{k=1}^n x_{ik} - x_{jk}}$
簡單的說就是向量每個元素平方和再開根，距離越小誤差越小，即相似度越大
```
def classify0(in_x,dataset,labels,k):
dataset_size = dataset.shape[0]
diff_mat = in_x - dataset # numpy Broadcasting
sq_mat = diff_mat**2
sq_distance = sq_mat.sum(axis=1)
distances = sq_distance**0.5
sort_distance_index = distances.argsort()
class_count = {}
for i in range(k):
cur_label = labels[sort_distance_index[i]]
class_count[cur_label] = class_count.get(cur_label,0) + 1
sort_class_cout = sorted(class_count.iteritems(),key = operator.itemgetter(1),reverse=True)
return sort_class_cout[0][0]
```
###測試我們的分類器
文本中有1000條數(shù)據(jù)，我們將其中一部分用來做測試數(shù)據(jù)，一部分用來做樣本庫，每隔1/10 取一條數(shù)據(jù)作為測試數(shù)據(jù)
```
test_data = dataset[0:data_size/10:1,0:]
test_labels = labels[0:data_size/10:1]
```
剩下的作為樣本庫
```
dataset = dataset[data_size/10:data_size:1,0:]
labels = labels[data_size/10:data_size:1]
```
[完整代碼][1]
[1]: https://github.com/SolemnJoker/ml-learn/tree/master/01_knn
