本來(lái)這篇文章是5月份寫的，今天修改了一下內(nèi)容，就成今天發(fā)表的了，CSDN這是出BUG了還是什么改規(guī)則了。。。

引文：決策樹和基于規(guī)則的分類器都是積極學(xué)習(xí)方法（eager learner）的例子，因?yàn)橐坏┯?xùn)練數(shù)據(jù)可用，他們就開始學(xué)習(xí)從輸入屬性到類標(biāo)號(hào)的映射模型。一個(gè)相反的策略是推遲對(duì)訓(xùn)練數(shù)據(jù)的建模，直到需要分類測(cè)試樣例時(shí)再進(jìn)行。采用這種策略的技術(shù)被稱為消極學(xué)習(xí)法（lazy learner）。最近鄰分類器就是這樣的一種方法。

注：KNN既可以用于分類，也可以用于回歸。

1.K最近鄰分類器原理

首先給出一張圖，根據(jù)這張圖來(lái)理解最近鄰分類器，如下：

根據(jù)上圖所示，有兩類不同的樣本數(shù)據(jù)，分別用藍(lán)色的小正方形和紅色的小三角形表示，而圖正中間的那個(gè)綠色的圓所標(biāo)示的數(shù)據(jù)則是待分類的數(shù)據(jù)。也就是說(shuō)，現(xiàn)在， 我們不知道中間那個(gè)綠色的數(shù)據(jù)是從屬于哪一類（藍(lán)色小正方形or紅色小三角形），下面，我們就要解決這個(gè)問題：給這個(gè)綠色的圓分類。

我們常說(shuō)，物以類聚，人以群分，判別一個(gè)人是一個(gè)什么樣品質(zhì)特征的人，常常可以從他or她身邊的朋友入手，所謂觀其友，而識(shí)其人。我們不是要判別上圖中那個(gè)綠色的圓是屬于哪一類數(shù)據(jù)么，好說(shuō)，從它的鄰居下手。但一次性看多少個(gè)鄰居呢？從上圖中，你還能看到：

• 如果K=3，綠色圓點(diǎn)的最近的3個(gè)鄰居是2個(gè)紅色小三角形和1個(gè)藍(lán)色小正方形，少數(shù)從屬于多數(shù)，基于統(tǒng)計(jì)的方法，判定綠色的這個(gè)待分類點(diǎn)屬于紅色的三角形一類。
• 如果K=5，綠色圓點(diǎn)的最近的5個(gè)鄰居是2個(gè)紅色三角形和3個(gè)藍(lán)色的正方形，還是少數(shù)從屬于多數(shù)，基于統(tǒng)計(jì)的方法，判定綠色的這個(gè)待分類點(diǎn)屬于藍(lán)色的正方形一類。

于此我們看到，當(dāng)無(wú)法判定當(dāng)前待分類點(diǎn)是從屬于已知分類中的哪一類時(shí)，我們可以依據(jù)統(tǒng)計(jì)學(xué)的理論看它所處的位置特征，衡量它周圍鄰居的權(quán)重，而把它歸為(或分配)到權(quán)重更大的那一類。這就是K近鄰算法的核心思想。其關(guān)鍵還在于K值的選取，所以應(yīng)當(dāng)謹(jǐn)慎。

KNN算法中，所選擇的鄰居都是已經(jīng)正確分類的對(duì)象。該方法在定類決策上只依據(jù)最鄰近的一個(gè)或者幾個(gè)樣本的類別來(lái)決定待分樣本所屬的類別。

KNN 算法本身簡(jiǎn)單有效，它是一種 lazy-learning 算法，分類器不需要使用訓(xùn)練集進(jìn)行訓(xùn)練，訓(xùn)練時(shí)間復(fù)雜度為0。KNN 分類的計(jì)算復(fù)雜度和訓(xùn)練集中的文檔數(shù)目成正比，也就是說(shuō)，如果訓(xùn)練集中文檔總數(shù)為 n，那么 KNN 的分類時(shí)間復(fù)雜度為O(n)。

前面的例子中強(qiáng)調(diào)了選擇合適的K值的重要性。如果太小，則最近鄰分類器容易受到訓(xùn)練數(shù)據(jù)的噪聲而產(chǎn)生的過分?jǐn)M合的影響；相反，如果K太大，最近分類器可能會(huì)誤會(huì)分類測(cè)試樣例，因?yàn)樽罱徚斜碇锌赡馨h(yuǎn)離其近鄰的數(shù)據(jù)點(diǎn)。（如下圖所示）

K較大時(shí)的最近鄰分類

可見，K值的選取還是非常關(guān)鍵。

2.算法算法描述

k近鄰算法簡(jiǎn)單、直觀：給定一個(gè)訓(xùn)練數(shù)據(jù)集（包括類別標(biāo)簽），對(duì)新的輸入實(shí)例，在訓(xùn)練數(shù)據(jù)集中找到與該實(shí)例最鄰近的k個(gè)實(shí)例，這k個(gè)實(shí)例的多數(shù)屬于某個(gè)類，就把該輸入實(shí)例分為這個(gè)類。下面是knn的算法步驟。

算法步驟如下所示：

對(duì)每個(gè)測(cè)試樣例z=(x′,y′)，算法計(jì)算它和所有訓(xùn)練樣例（x,y）屬于D之間的距離（如歐氏距離，或相似度），以確定其最近鄰列表Dz。如果訓(xùn)練樣例的數(shù)目很大，那么這種計(jì)算的開銷就會(huì)很大。不過，可以使索引技術(shù)降低為測(cè)試樣例找最近鄰是的計(jì)算量。

特征空間中兩個(gè)實(shí)例點(diǎn)的距離是兩個(gè)實(shí)例相似程度的反映。

一旦得到最近鄰列表，測(cè)試樣例就可以根據(jù)最近鄰的多數(shù)類進(jìn)行分類，使用多數(shù)表決方法。

K值選擇

k值對(duì)模型的預(yù)測(cè)有著直接的影響，如果k值過小，預(yù)測(cè)結(jié)果對(duì)鄰近的實(shí)例點(diǎn)非常敏感。如果鄰近的實(shí)例恰巧是噪聲數(shù)據(jù)，預(yù)測(cè)就會(huì)出錯(cuò)。也就是說(shuō)，k值越小就意味著整個(gè)模型就變得越復(fù)雜，越容易發(fā)生過擬合。

相反，如果k值越大，有點(diǎn)是可以減少模型的預(yù)測(cè)誤差，缺點(diǎn)是學(xué)習(xí)的近似誤差會(huì)增大。會(huì)使得距離實(shí)例點(diǎn)較遠(yuǎn)的點(diǎn)也起作用，致使預(yù)測(cè)發(fā)生錯(cuò)誤。同時(shí)，k值的增大意味著模型變得越來(lái)越簡(jiǎn)單。如果k=N，那么無(wú)論輸入實(shí)例是什么，都將簡(jiǎn)單的把它預(yù)測(cè)為樣本中最多的一類。這顯然實(shí)不可取的。

在實(shí)際建模應(yīng)用中，k值一般取一個(gè)較小的數(shù)值，通常采用cross-validation的方法來(lái)選擇最優(yōu)的k值。

3.K最鄰近算法實(shí)現(xiàn)（Python）

KNN.py（代碼來(lái)源《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》一書）

from numpy import *
import operator

class KNN:
  def createDataset(self):
    group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
    labels = ['A','A','B','B']
    return group,labels

  def KnnClassify(self,testX,trainX,labels,K):
    [N,M]=trainX.shape

  #calculate the distance between testX and other training samples
    difference = tile(testX,(N,1)) - trainX # tile for array and repeat for matrix in Python, == repmat in Matlab
    difference = difference ** 2 # take pow(difference,2)
    distance = difference.sum(1) # take the sum of difference from all dimensions
    distance = distance ** 0.5
    sortdiffidx = distance.argsort()

  # find the k nearest neighbours
    vote = {} #create the dictionary
    for i in range(K):
      ith_label = labels[sortdiffidx[i]];
      vote[ith_label] = vote.get(ith_label,0)+1 #get(ith_label,0) : if dictionary 'vote' exist key 'ith_label', return vote[ith_label]; else return 0
    sortedvote = sorted(vote.iteritems(),key = lambda x:x[1], reverse = True)
    # 'key = lambda x: x[1]' can be substituted by operator.itemgetter(1)
    return sortedvote[0][0]

k = KNN() #create KNN object
group,labels = k.createDataset()
cls = k.KnnClassify([0,0],group,labels,3)
print cls

運(yùn)行：
1. 在Python Shell 中可以運(yùn)行KNN.py

>>>import os
>>>os.chdir("/home/liudiwei/code/data_miningKNN/")
>>>execfile("KNN.py")

輸出:B
（B表示類別）

2.或者terminal中直接運(yùn)行

$ python KNN.py

3.也可以不在KNN.py中寫輸出，而選擇在Shell中獲得結(jié)果，i.e.,

>>>import KNN
>>> KNN.k.KnnClassify([0,0],KNN.group,KNN.labels,3)

附件（兩張自己的計(jì)算過程圖）：

 圖

1 KNN算法核心部分

圖2 KNN計(jì)算過程

說(shuō)明：上述圖片僅供參考，看不懂就自己測(cè)試一組數(shù)據(jù)如[0,1]慢慢推導(dǎo)一下吧

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評(píng)論