Python 코드 예제를 사용하여 kNN 알고리즘의 실제 적용 시연_기본 지식

이웃 알고리즘 또는 K-최근접 이웃(kNN, k-NearestNeighbor) 분류 알고리즘은 데이터 마이닝 분류 기술에서 가장 간단한 방법 중 하나입니다. 소위 K 최근접 이웃은 k 최근접 이웃을 의미합니다. 이는 각 샘플이 k 최근접 이웃으로 표현될 수 있음을 의미합니다.
kNN 알고리즘의 핵심 아이디어는 특징 공간에서 샘플의 가장 가까운 인접 샘플 k개 대부분이 특정 카테고리에 속하면 샘플도 이 카테고리에 속하며 이 카테고리에 있는 샘플의 특성을 갖는다는 것입니다. 이 방법은 분류 결정에 있어서 가장 가까운 하나 또는 여러 개의 샘플의 범주를 기준으로 분류할 샘플의 범주만 결정합니다. kNN 방법은 카테고리 결정을 내릴 때 매우 적은 수의 인접 샘플에만 관련됩니다. kNN 방법은 카테고리를 결정하기 위해 클래스 도메인을 구별하는 방법보다는 제한된 주변 샘플에 주로 의존하기 때문에, 교차점이나 중복되는 부분이 많은 샘플 세트를 분할하는 데에는 kNN 방법이 다른 방법보다 효율적입니다. 적합성을 위한 클래스 도메인.

위 사진에서 녹색 원은 어느 반에 배정되어야 할까요? 빨간색 삼각형인가요, 아니면 파란색 사각형인가요? K=3이면 빨간색 삼각형의 비율이 2/3이므로 녹색 원에 빨간색 삼각형의 클래스가 할당됩니다. K=5이면 파란색 사각형의 비율이 3/5이므로 녹색 원에 할당됩니다. 파란색 사각형 유형의 클래스가 지정됩니다.
KNN(K-Nearest Neighbor) 분류 알고리즘은 이론적으로 성숙한 방법이며 가장 간단한 기계 학습 알고리즘 중 하나입니다. 이 방법의 아이디어는: 샘플이 특징 공간에서 가장 유사한(즉, 특징 공간에서 가장 가까운) k개의 샘플 중 특정 범주에 속하면 샘플도 이 범주에 속한다는 것입니다. KNN 알고리즘에서 선택된 이웃은 모두 올바르게 분류된 객체입니다. 이 방법은 분류 의사결정에서 가장 가까운 하나 또는 여러 개의 샘플의 범주를 기반으로 분류할 샘플의 범주만 결정합니다. KNN 방법도 원칙적으로 극한 정리에 의존하지만 카테고리 결정을 내릴 때 매우 적은 수의 인접 샘플에만 관련됩니다. KNN 방법은 카테고리를 결정하기 위해 클래스 도메인을 판별하는 방법보다는 제한된 주변 샘플에 주로 의존하기 때문에 샘플 세트를 많은 수의 교차 또는 중첩으로 분할하는 데에는 KNN 방법이 다른 방법보다 효율적입니다. 적합성을 위한 클래스 도메인.
KNN 알고리즘은 분류뿐만 아니라 회귀에도 사용할 수 있습니다. 샘플의 가장 가까운 이웃 k개를 찾아 이들 이웃의 속성 평균을 샘플에 할당함으로써 샘플의 속성을 얻을 수 있습니다. 더 유용한 방법은 샘플에서 서로 다른 거리에 있는 이웃의 영향에 서로 다른 가중치를 부여하는 것입니다. 예를 들어 가중치는 거리에 반비례합니다.

kNN 알고리즘을 사용하여 Douban 영화 사용자의 성별 예측
요약

본 글에서는 성별에 따라 선호하는 영화의 종류가 다를 것이라고 판단하여 이 실험을 진행하게 되었습니다. 활성 Douban 사용자 274명이 최근 관람한 100편의 영화를 이용하여 유형에 대한 통계를 작성하였고, 획득된 37개의 영화 유형을 속성 특징으로 사용하였고, 사용자의 성별을 라벨로 사용하여 샘플 세트를 구성하였다. kNN 알고리즘을 사용하여 샘플의 90%를 훈련 샘플로 사용하고 10%를 테스트 샘플로 사용하여 Douban 영화 사용자 성별 분류기를 구성하며 정확도는 81.48%에 도달할 수 있습니다.

실험 데이터

본 실험에 사용된 데이터는 Douban 사용자가 표시한 영화로, Douban 사용자 274명이 최근 시청한 영화 100편을 선정했습니다. 각 사용자에 대한 영화 유형 통계입니다. 본 실험에 사용된 데이터에는 총 37개의 영화 유형이 있으므로 이 37가지 유형을 사용자의 속성특징으로 사용하고, 각 특징의 값은 사용자의 영화 100개 중 해당 유형의 영화 개수이다. 사용자는 성별에 따라 라벨이 지정됩니다. Douban에는 사용자 성별 정보가 없으므로 모두 수동으로 라벨이 지정됩니다.

데이터 형식은 다음과 같습니다.

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

像这样的数据一共有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))