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 官网

上一篇:微服务前端开发框架React-Admin


下一篇:SqlServer数据库端口默认是1433吗?