## 一、knn簡(jiǎn)介
k臨近算法采用測(cè)量不同特征值之間的距離來(lái)分類(lèi),在樣本數(shù)據(jù)及中找出k個(gè)待分類(lèi)數(shù)據(jù)最相似的樣本状共,這k個(gè)樣本中出現(xiàn)最多的類(lèi)別作為待分類(lèi)樣本的類(lèi)別
### 算法流程
```
遍歷所有樣本
對(duì)輸入數(shù)據(jù)計(jì)算和每一個(gè)樣本數(shù)據(jù)的誤差
找出k個(gè)誤差最小的樣本
統(tǒng)計(jì)k個(gè)最相似的樣本中出現(xiàn)最多的類(lèi)別作為待分類(lèi)樣本類(lèi)別
```
## 二、代碼實(shí)現(xiàn)
### 樣本數(shù)據(jù)
這是一份約會(huì)網(wǎng)站數(shù)據(jù),
**數(shù)據(jù)有三種分類(lèi):**
1. largeDoses 極具魅力的人
2. smallDoses 魅力一般的人
3. didntlike????? 不喜歡的人
**每條數(shù)據(jù)共有三種特征:**
1. 每年乘飛機(jī)飛行里程數(shù)
2. 玩游戲時(shí)間百分比
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ù)歸一化
不同評(píng)價(jià)指標(biāo)往往具有不同的量綱和量綱單位挠唆,這樣的情況會(huì)影響到數(shù)據(jù)分析的結(jié)果,為了消除指標(biāo)之間的量綱影響雹仿,需要進(jìn)行數(shù)據(jù)標(biāo)準(zhǔn)化處理增热,以解決數(shù)據(jù)指標(biāo)之間的可比性。原始數(shù)據(jù)經(jīng)過(guò)數(shù)據(jù)標(biāo)準(zhǔn)化處理后胧辽,各指標(biāo)處于同一數(shù)量級(jí)峻仇,適合進(jìn)行綜合對(duì)比評(píng)價(jià).
#### 常用的歸一化方法有:
* min-max標(biāo)準(zhǔn)化法
* Z-score標(biāo)準(zhǔn)化方法
這里我們使用min-max標(biāo)準(zhǔn)化法。
$\frac{x-minval}{maxval-minval}$
### 分類(lèi)
knn與其他機(jī)器學(xué)習(xí)方法不同的是邑商,沒(méi)有訓(xùn)練過(guò)程摄咆,直接對(duì)數(shù)據(jù)集上所有數(shù)據(jù)計(jì)算。分類(lèi)時(shí)需要計(jì)算待分類(lèi)樣本與每一個(gè)樣本數(shù)據(jù)的相似度人断,這里相似度我們用L2距離(就是我們常見(jiàn)的歐氏距離)表示
$L_2 = \sqrt{\sum_{k=1}^n x_{ik} - x_{jk}}$
簡(jiǎn)單的說(shuō)就是向量每個(gè)元素平方和再開(kāi)根吭从,距離越小誤差越小,即相似度越大
```
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]
```
###測(cè)試我們的分類(lèi)器
文本中有1000條數(shù)據(jù)恶迈,我們將其中一部分用來(lái)做測(cè)試數(shù)據(jù)影锈,一部分用來(lái)做樣本庫(kù),每隔1/10 取一條數(shù)據(jù)作為測(cè)試數(shù)據(jù)
```
test_data = dataset[0:data_size/10:1,0:]
test_labels = labels[0:data_size/10:1]
```
剩下的作為樣本庫(kù)
```
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