鄰近算法，或者說(shuō)K最近鄰(kNN，k-NearestNeighbor)分類(lèi)算法是數(shù)據(jù)挖掘分類(lèi)技術(shù)中最簡(jiǎn)單的方法之一。所謂K最近鄰，就是k個(gè)最近的鄰居的意思，說(shuō)的是每個(gè)樣本都可以用它最接近的k個(gè)鄰居來(lái)代表。
kNN算法的核心思想是如果一個(gè)樣本在特征空間中的k個(gè)最相鄰的樣本中的大多數(shù)屬于某一個(gè)類(lèi)別，則該樣本也屬于這個(gè)類(lèi)別，并具有這個(gè)類(lèi)別上樣本的特性。該方法在確定分類(lèi)決策上只依據(jù)最鄰近的一個(gè)或者幾個(gè)樣本的類(lèi)別來(lái)決定待分樣本所屬的類(lèi)別。 kNN方法在類(lèi)別決策時(shí)，只與極少量的相鄰樣本有關(guān)。由于kNN方法主要靠周?chē)邢薜泥徑臉颖?，而不是靠判別類(lèi)域的方法來(lái)確定所屬類(lèi)別的，因此對(duì)于類(lèi)域的交叉或重疊較多的待分樣本集來(lái)說(shuō)，kNN方法較其他方法更為適合。

上圖中，綠色圓要被決定賦予哪個(gè)類(lèi)，是紅色三角形還是藍(lán)色四方形？如果K=3，由于紅色三角形所占比例為2/3，綠色圓將被賦予紅色三角形那個(gè)類(lèi)，如果K=5，由于藍(lán)色四方形比例為3/5，因此綠色圓被賦予藍(lán)色四方形類(lèi)。
K最近鄰(k-Nearest Neighbor，KNN)分類(lèi)算法，是一個(gè)理論上比較成熟的方法，也是最簡(jiǎn)單的機(jī)器學(xué)習(xí)算法之一。該方法的思路是：如果一個(gè)樣本在特征空間中的k個(gè)最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個(gè)類(lèi)別，則該樣本也屬于這個(gè)類(lèi)別。KNN算法中，所選擇的鄰居都是已經(jīng)正確分類(lèi)的對(duì)象。該方法在定類(lèi)決策上只依據(jù)最鄰近的一個(gè)或者幾個(gè)樣本的類(lèi)別來(lái)決定待分樣本所屬的類(lèi)別。 KNN方法雖然從原理上也依賴于極限定理，但在類(lèi)別決策時(shí)，只與極少量的相鄰樣本有關(guān)。由于KNN方法主要靠周?chē)邢薜泥徑臉颖?，而不是靠判別類(lèi)域的方法來(lái)確定所屬類(lèi)別的，因此對(duì)于類(lèi)域的交叉或重疊較多的待分樣本集來(lái)說(shuō)，KNN方法較其他方法更為適合。
KNN算法不僅可以用于分類(lèi)，還可以用于回歸。通過(guò)找出一個(gè)樣本的k個(gè)最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對(duì)該樣本產(chǎn)生的影響給予不同的權(quán)值(weight)，如權(quán)值與距離成反比。

用 kNN 算法預(yù)測(cè)豆瓣電影用戶的性別
摘要

本文認(rèn)為不同性別的人偏好的電影類(lèi)型會(huì)有所不同，因此進(jìn)行了此實(shí)驗(yàn)。利用較為活躍的274位豆瓣用戶最近觀看的100部電影，對(duì)其類(lèi)型進(jìn)行統(tǒng)計(jì)，以得到的37種電影類(lèi)型作為屬性特征，以用戶性別作為標(biāo)簽構(gòu)建樣本集。使用kNN算法構(gòu)建豆瓣電影用戶性別分類(lèi)器，使用樣本中的90%作為訓(xùn)練樣本，10%作為測(cè)試樣本，準(zhǔn)確率可以達(dá)到81.48%。

實(shí)驗(yàn)數(shù)據(jù)

本次實(shí)驗(yàn)所用數(shù)據(jù)為豆瓣用戶標(biāo)記的看過(guò)的電影，選取了274位豆瓣用戶最近看過(guò)的100部電影。對(duì)每個(gè)用戶的電影類(lèi)型進(jìn)行統(tǒng)計(jì)。本次實(shí)驗(yàn)所用數(shù)據(jù)中共有37個(gè)電影類(lèi)型，因此將這37個(gè)類(lèi)型作為用戶的屬性特征，各特征的值即為用戶100部電影中該類(lèi)型電影的數(shù)量。用戶的標(biāo)簽為其性別，由于豆瓣沒(méi)有用戶性別信息，因此均為人工標(biāo)注。

數(shù)據(jù)格式如下所示：

X1,1，X1,2，X1,3，X1,4……X1,36，X1,37，Y1
X2,1，X2,2，X2,3，X2,4……X2,36，X2,37，Y2
…………
X274,1，X274,2，X274,3，X274,4……X274,36，X274,37，Y274

示例：

0,0,0,3,1,34,5,0,0,0,11,31,0,0,38,40,0,0,15,8,3,9,14,2,3,0,4,1,1,15,0,0,1,13,0,0,1,1 0,1,0,2,2,24,8,0,0,0,10,37,0,0,44,34,0,0,3,0,4,10,15,5,3,0,0,7,2,13,0,0,2,12,0,0,0,0

像這樣的數(shù)據(jù)一共有274行，表示274個(gè)樣本。每一個(gè)的前37個(gè)數(shù)據(jù)是該樣本的37個(gè)特征值，最后一個(gè)數(shù)據(jù)為標(biāo)簽，即性別：0表示男性，1表示女性。

在此次試驗(yàn)中取樣本的前10%作為測(cè)試樣本，其余作為訓(xùn)練樣本。

首先對(duì)所有數(shù)據(jù)歸一化。對(duì)矩陣中的每一列求取最大值（max_j）、最小值（min_j)，對(duì)矩陣中的數(shù)據(jù)X_j，
X_j=(X_j-min_j)/(max_j-min_j) 。

然后對(duì)于每一條測(cè)試樣本，計(jì)算其與所有訓(xùn)練樣本的歐氏距離。測(cè)試樣本i與訓(xùn)練樣本j之間的距離為：
distance_i_j=sqrt((Xi,1-Xj,1)^2+(Xi,2-Xj,2)^2+……+(Xi,37-Xj,37)^2) ，
對(duì)樣本i的所有距離從小到大排序，在前k個(gè)中選擇出現(xiàn)次數(shù)最多的標(biāo)簽，即為樣本i的預(yù)測(cè)值。

實(shí)驗(yàn)結(jié)果

首先選擇一個(gè)合適的k值。 對(duì)于k=1,3,5,7，均使用同一個(gè)測(cè)試樣本和訓(xùn)練樣本，測(cè)試其正確率，結(jié)果如下表所示。

選取不同k值的正確率表

由上述結(jié)果可知，在k=3時(shí)，測(cè)試的平均正確率最高，為74.07%，最高可以達(dá)到81.48%。

上述不同的測(cè)試集均來(lái)自同一樣本集中，為隨機(jī)選取所得。

Python代碼

這段代碼并非原創(chuàng)，來(lái)自《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》（Peter Harrington，2013），并有所改動(dòng)。

#coding:utf-8

from numpy import *
import operator

def classify0(inX, dataSet, labels, k):
  dataSetSize = dataSet.shape[0]
  diffMat = tile(inX, (dataSetSize,1)) - dataSet
  sqDiffMat = diffMat**2
  sqDistances = sqDiffMat.sum(axis=1)
  distances = sqDistances**0.5
  sortedDistIndicies = distances.argsort()   
  classCount={}     
  for i in range(k):
    voteIlabel = labels[sortedDistIndicies[i]]
    classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
  sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
  return sortedClassCount[0][0]

def autoNorm(dataSet):
  minVals = dataSet.min(0)
  maxVals = dataSet.max(0)
  ranges = maxVals - minVals
  normDataSet = zeros(shape(dataSet))
  m = dataSet.shape[0]
  normDataSet = dataSet - tile(minVals, (m,1))
  normDataSet = normDataSet/tile(ranges, (m,1))  #element wise divide
  return normDataSet, ranges, minVals

def file2matrix(filename):
  fr = open(filename)
  numberOfLines = len(fr.readlines())     #get the number of lines in the file
  returnMat = zeros((numberOfLines,37))    #prepare matrix to return
  classLabelVector = []            #prepare labels return  
  fr = open(filename)
  index = 0
  for line in fr.readlines():
    line = line.strip()
    listFromLine = line.split(',')
    returnMat[index,:] = listFromLine[0:37]
    classLabelVector.append(int(listFromLine[-1]))
    index += 1
  fr.close()
  return returnMat,classLabelVector

def genderClassTest():
  hoRatio = 0.10   #hold out 10%
  datingDataMat,datingLabels = file2matrix('doubanMovieDataSet.txt')    #load data setfrom file
  normMat,ranges,minVals=autoNorm(datingDataMat)
  m = normMat.shape[0]
  numTestVecs = int(m*hoRatio)
  testMat=normMat[0:numTestVecs,:]
  trainMat=normMat[numTestVecs:m,:]
  trainLabels=datingLabels[numTestVecs:m]
  k=3
  errorCount = 0.0
  for i in range(numTestVecs):
    classifierResult = classify0(testMat[i,:],trainMat,trainLabels,k)
    print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i])
    if (classifierResult != datingLabels[i]):
      errorCount += 1.0
  print "Total errors:%d" %errorCount
  print "The total accuracy rate is %f" %(1.0-errorCount/float(numTestVecs))