Verwenden Sie Python-Codebeispiele, um die praktische Anwendung des kNN-Algorithmus zu demonstrieren_Grundkenntnisse

Der Nachbaralgorithmus oder K-Nearest-Neighbor-Klassifizierungsalgorithmus (kNN, k-NearestNeighbor) ist eine der einfachsten Methoden in der Data-Mining-Klassifizierungstechnologie. Der sogenannte K nächste Nachbar bedeutet k nächste Nachbarn. Dies bedeutet, dass jede Stichprobe durch ihre k nächsten Nachbarn dargestellt werden kann.
Die Kernidee des kNN-Algorithmus besteht darin, dass, wenn die meisten der k nächsten benachbarten Stichproben einer Stichprobe im Merkmalsraum zu einer bestimmten Kategorie gehören, die Stichprobe auch zu dieser Kategorie gehört und die Eigenschaften von Stichproben in dieser Kategorie aufweist. Diese Methode bestimmt nur die Kategorie der zu klassifizierenden Probe auf der Grundlage der Kategorie der nächstgelegenen oder mehrerer Proben bei der Bestimmung der Klassifizierungsentscheidung. Die kNN-Methode ist bei Kategorieentscheidungen nur für eine sehr kleine Anzahl benachbarter Stichproben relevant. Da die kNN-Methode zur Bestimmung der Kategorie hauptsächlich auf den begrenzten umgebenden Stichproben und nicht auf der Methode zur Unterscheidung des Klassenbereichs beruht, ist die kNN-Methode für die Aufteilung von Stichprobensätzen mit einer großen Anzahl von Schnittpunkten oder Überlappungen effizienter als andere Methoden die Klassendomäne für fit.

Welcher Klasse soll im Bild oben der grüne Kreis zugeordnet werden? Ist es ein rotes Dreieck oder ein blaues Quadrat? Wenn K=3, da der Anteil des roten Dreiecks 2/3 beträgt, wird dem grünen Kreis die Klasse des roten Dreiecks zugewiesen. Wenn K=5, da der Anteil des blauen Quadrats 3/5 beträgt, wird dem grünen Kreis die Klasse zugewiesen wird der Klasse des blauen Quadrattyps zugewiesen.
Der Klassifizierungsalgorithmus K-Nearest Neighbor (KNN) ist eine theoretisch ausgereifte Methode und einer der einfachsten Algorithmen für maschinelles Lernen. Die Idee dieser Methode ist: Wenn eine Stichprobe zu einer bestimmten Kategorie unter den k ähnlichsten (dh im Merkmalsraum am nächsten liegenden) Stichproben im Merkmalsraum gehört, gehört die Stichprobe auch zu dieser Kategorie. Im KNN-Algorithmus sind die ausgewählten Nachbarn alle korrekt klassifizierte Objekte. Diese Methode bestimmt nur die Kategorie der zu klassifizierenden Probe auf der Grundlage der Kategorie der nächsten oder mehrerer Proben bei der Klassifizierungsentscheidung. Obwohl die KNN-Methode im Prinzip auch auf dem Grenzwertsatz basiert, bezieht sie sich bei der Kategorieentscheidung nur auf eine sehr kleine Anzahl benachbarter Stichproben. Da die KNN-Methode zur Bestimmung der Kategorie hauptsächlich auf den begrenzten umgebenden Stichproben und nicht auf der Methode zur Unterscheidung des Klassenbereichs beruht, ist die KNN-Methode effizienter als andere Methoden für die Aufteilung des Stichprobensatzes mit einer großen Anzahl von Schnittpunkten oder Überlappungen die Klassendomäne für fit.
Der KNN-Algorithmus kann nicht nur zur Klassifizierung, sondern auch zur Regression verwendet werden. Durch Finden der k nächsten Nachbarn einer Stichprobe und Zuweisen des Durchschnitts der Attribute dieser Nachbarn zur Stichprobe können die Attribute der Stichprobe ermittelt werden. Eine nützlichere Methode besteht darin, dem Einfluss von Nachbarn in unterschiedlichen Entfernungen auf die Stichprobe unterschiedliche Gewichte zuzuweisen. Beispielsweise ist die Gewichtung umgekehrt proportional zur Entfernung.

Verwenden Sie den kNN-Algorithmus, um das Geschlecht der Douban-Filmbenutzer vorherzusagen
Zusammenfassung

Dieser Artikel geht davon aus, dass die Arten von Filmen, die Menschen unterschiedlichen Geschlechts bevorzugen, unterschiedlich sein werden, daher wurde dieses Experiment durchgeführt. Die 100 Filme, die kürzlich von 274 aktiven Douban-Benutzern angesehen wurden, wurden verwendet, um Statistiken über ihre Typen zu erstellen. Die erhaltenen 37 Filmtypen wurden als Attributmerkmale verwendet und das Geschlecht des Benutzers wurde als Bezeichnung für die Erstellung eines Beispielsatzes verwendet. Verwenden Sie den kNN-Algorithmus, um einen Geschlechtsklassifikator für Douban-Filmbenutzer zu erstellen. Dabei werden 90 % der Stichproben als Trainingsstichproben und 10 % als Teststichproben verwendet. Die Genauigkeit kann 81,48 % erreichen.

Experimentelle Daten

Bei den in diesem Experiment verwendeten Daten handelt es sich um die von Douban-Benutzern markierten Filme, und es wurden die 100 Filme ausgewählt, die kürzlich von 274 Douban-Benutzern angesehen wurden. Statistiken der Filmtypen für jeden Benutzer. In den in diesem Experiment verwendeten Daten gibt es insgesamt 37 Filmtypen. Daher werden diese 37 Typen als Attributmerkmale des Benutzers verwendet, und der Wert jedes Merkmals ist die Anzahl der Filme dieses Typs unter den 100 Filmen des Benutzers. Benutzer werden nach ihrem Geschlecht gekennzeichnet. Da Douban keine Informationen zum Benutzergeschlecht hat, wird alles manuell gekennzeichnet.

Das Datenformat ist wie folgt:

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

Beispiel:

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

像这样的数据一共有274行，表示274个样本。每一个的前37个数据是该样本的37个特征值，最后一个数据为标签，即性别：0表示男性，1表示女性。

在此次试验中取样本的前10%作为测试样本，其余作为训练样本。

首先对所有数据归一化。对矩阵中的每一列求取最大值（max_j）、最小值（min_j)，对矩阵中的数据X_j，
X_j=(X_j-min_j)/(max_j-min_j) 。

然后对于每一条测试样本，计算其与所有训练样本的欧氏距离。测试样本i与训练样本j之间的距离为：
distance_i_j=sqrt((Xi,1-Xj,1)^2+(Xi,2-Xj,2)^2+……+(Xi,37-Xj,37)^2) ，
对样本i的所有距离从小到大排序，在前k个中选择出现次数最多的标签，即为样本i的预测值。

实验结果

首先选择一个合适的k值。 对于k=1,3,5,7，均使用同一个测试样本和训练样本，测试其正确率，结果如下表所示。

选取不同k值的正确率表

由上述结果可知，在k=3时，测试的平均正确率最高，为74.07%，最高可以达到81.48%。

上述不同的测试集均来自同一样本集中，为随机选取所得。

Python代码

这段代码并非原创，来自《机器学习实战》（Peter Harrington，2013），并有所改动。

#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))