KNN算法原理（python代码实现）

kNN(k-nearest neighbor algorithm)算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。简单地说，K-近邻算法采用测量不同特征值之间的距离方法进行分类。
- 优点：精度高、对异常值不敏感、无数据输入假定。
- 缺点：计算复杂度高、空间复杂度高。
- 适用数据范围：数值型和标称型。

举个简单的例子，一群男生和一群女生，我们知道他们的身高和性别。
如下表格：

身高	性别
165	女
166	女
169	女
175	男
178	男
180	男
190	男
179	未知

这里有8位同学，已知所有人的身高，其中7个人的性别，还有位同学只知道身高，那么这位同学可能是男生还是女生。

下面我们利用KNN算法来分类：
1. 求这位同学跟其他同学的身高差；
2. 设定一个K值，选择跟这位同学身高相差最小的K个同学；
3. 在这K个同学中，哪种性别的人多，就认为这位同学属于哪种性别。

举例：设K为5

计算这位同学与其他同学的身高差的绝对值：如下

身高差的绝对值	性别
14	女
13	女
10	女
4	男
1	男
1	男
11	男

与这位同学身高差最接近的5位同学中，有4位男生，1位女生，所以我们认为这位同学也是男生。

现实当中，肯定不止考虑身高，还要考虑体重、头发长度等等因素。算法的思想还是一样，这时候“距离”的计算公式为欧氏距离：

在多个特征，多个分类的情况下，KNN算法思想：
1. 计算预分类的与样本中的欧氏距离（当然还有其他距离）；
2. 选择距离最小的K的样本；
3. 把预分类归为：K个样本中，类别最多的那个类别。

下面是KNN的python代码实现:

 from numpy import *

 import operator

 from os import listdir

 filename_train='C:\\Users\\Administrator\\Desktop\\digits\\trainingDigits\\'

 filename_test='C:\\Users\\Administrator\\Desktop\\digits\\testDigits\\'

 #KNN算法函数

 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.items(), key=operator.itemgetter(1), reverse=True)

     return(sortedClassCount[0][0])

 #将图像转化为向量

 def img2vector(filename):

     returnVect = zeros((1, 1024))

     fr = open(filename)

     for i in range(32):

         lineStr = fr.readline()

         for j in range(32):

             returnVect[0, 32 * i + j] = int(lineStr[j])

     return(returnVect)

 #手写分类

 def handwritingClassTest():

     hwLabels = []

     trainingFileList = listdir(filename_train)  # 载入数据所在目录

     m = len(trainingFileList)

     trainingMat = zeros((m, 1024))

     for i in range(m):

         fileNameStr = trainingFileList[i]

         fileStr = fileNameStr.split('.')[0]

         classNumStr = int(fileStr.split('_')[0])

         hwLabels.append(classNumStr)

         trainingMat[i, :] = img2vector(filename_train+fileNameStr)

     testFileList = listdir(filename_test)

     errorCount = 0.0

     mTest = len(testFileList)

     for i in range(mTest):

         fileNameStr = testFileList[i]

         fileStr = fileNameStr.split('.')[0]

         classNumStr = int(fileStr.split('_')[0])

         vectorUnderTest = img2vector(filename_test+fileNameStr)

         classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)

         print("the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNumStr))

         if (classifierResult != classNumStr): errorCount += 1.0

     print("\nthe total number of errors is: %d" % errorCount)

     print("\nthe total error rate is: %f" % (errorCount / float(mTest)))

 if __name__=='__main__':

     handwritingClassTest()

结果如下，效果还不错。
the total number of errors is: 11
the total error rate is: 0.011628

参考：
1. 《Machine Learning in Action》
2. scikit-learn KNeighborsClassifier 官网

巴特西

KNN算法原理（python代码实现）

最新文章

热门文章