knn k臨近算法

## 一、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

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末蝉绷,一起剝皮案震驚了整個(gè)濱河市鸭廷,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌熔吗,老刑警劉巖辆床,帶你破解...
    沈念sama閱讀 211,376評(píng)論 6 491
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異桅狠,居然都是意外死亡讼载,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,126評(píng)論 2 385
  • 文/潘曉璐 我一進(jìn)店門(mén)中跌,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)咨堤,“玉大人,你說(shuō)我怎么就攤上這事漩符∫淮” “怎么了?”我有些...
    開(kāi)封第一講書(shū)人閱讀 156,966評(píng)論 0 347
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)凸克。 經(jīng)常有香客問(wèn)我议蟆,道長(zhǎng),這世上最難降的妖魔是什么萎战? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 56,432評(píng)論 1 283
  • 正文 為了忘掉前任咐容,我火速辦了婚禮,結(jié)果婚禮上蚂维,老公的妹妹穿的比我還像新娘戳粒。我一直安慰自己,他們只是感情好虫啥,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,519評(píng)論 6 385
  • 文/花漫 我一把揭開(kāi)白布蔚约。 她就那樣靜靜地躺著,像睡著了一般孝鹊。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上展蒂,一...
    開(kāi)封第一講書(shū)人閱讀 49,792評(píng)論 1 290
  • 那天又活,我揣著相機(jī)與錄音,去河邊找鬼锰悼。 笑死柳骄,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的箕般。 我是一名探鬼主播耐薯,決...
    沈念sama閱讀 38,933評(píng)論 3 406
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼丝里!你這毒婦竟也來(lái)了曲初?” 一聲冷哼從身側(cè)響起,我...
    開(kāi)封第一講書(shū)人閱讀 37,701評(píng)論 0 266
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤杯聚,失蹤者是張志新(化名)和其女友劉穎臼婆,沒(méi)想到半個(gè)月后,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體幌绍,經(jīng)...
    沈念sama閱讀 44,143評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡颁褂,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,488評(píng)論 2 327
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了傀广。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片颁独。...
    茶點(diǎn)故事閱讀 38,626評(píng)論 1 340
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖伪冰,靈堂內(nèi)的尸體忽然破棺而出誓酒,到底是詐尸還是另有隱情,我是刑警寧澤贮聂,帶...
    沈念sama閱讀 34,292評(píng)論 4 329
  • 正文 年R本政府宣布丰捷,位于F島的核電站坯墨,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏病往。R本人自食惡果不足惜捣染,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,896評(píng)論 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望停巷。 院中可真熱鬧耍攘,春花似錦、人聲如沸畔勤。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 30,742評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)庆揪。三九已至式曲,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間缸榛,已是汗流浹背吝羞。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 31,977評(píng)論 1 265
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留内颗,地道東北人钧排。 一個(gè)月前我還...
    沈念sama閱讀 46,324評(píng)論 2 360
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像均澳,于是被迫代替她去往敵國(guó)和親恨溜。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,494評(píng)論 2 348

推薦閱讀更多精彩內(nèi)容