(一）算法基本思想
K
N
N
KNN
KNN是一种常用的监督学习方法。给定测试样本，基于某种距离度量找出训练集中与其最靠近的
k
k
k个训练样本，然后基于这
k
k
k个邻居的信息来进行预测。使用投票法，选择
k
k
k个样本中出现最多的类别标记作为预测结果，这
k
k
k个实例的多数属于某类，就把该输入实例分为哪类。也可以基于距离远近进行加权平均，距离越近样本权重越大。
k
k
k值的选择、距离的度量、以及分类决策规则是
k
k
k邻近算法三个基本要素。
（二）算法实现
输入：训练数据集
T
=
[
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
.
.
.
,
(
x
n
,
y
n
)
]
T={[(x_1,y_1),(x_2,y_2),...,(x_n,y_n)]}
T=[(x1,y1),(x2,y2),...,(xn,yn)],
x
i
x_i
xi为特征向量，
y
i
y_i
yi为实例类别。 输出：实例
x
x
x所属的类别
y
y
y。
(1)
根据给定的距离度量，在训练集
T
T
T中找出与
x
x
x最邻近的
k
k
k个点；
(2)
在
k
k
k个点中进行分类表决，少数服从多数原则，决定
x
x
x的类别
y
y
y。
y
=
a
r
g
m
a
x
∑
x
I
(
y
i
=
c
j
)
y=argmax\sum_xI(y_i=c_j)
y=argmax∑xI(yi=cj),选择相应数目最多的类别。当
k
=
1
k=1
k=1时，称为最邻近算法。
k
k
k邻近模型
（1）模型
当训练集、距离度量、
k
k
k值以及分类决策规则确定后，对于任何一个新的输入实例，它所属的类唯一的确定。
（2）距离度量
使用的距离一般是欧式距离。
L
p
=
(
∑
l
=
1
n
∣
x
i
（
l
）
−
x
j
（
l
）
∣
p
)
1
p
L_p={(\sum_{l=1}^n|x_i^{（l）}-x_j^{（l）}|^p)^{\frac{1}{p}}}
Lp=(∑l=1n∣xi（l）−xj（l）∣p)p1;当
p
=
2
p=2
p=2时，为欧式距离。当
p
=
1
p=1
p=1时，为曼哈顿距离。
（3）
k
k
k值的选择
k
k
k值较小，学习的近似误差会减小，估计误差会增大，意味着整体模型变得更复杂，容易发生过拟合；若
k
k
k值较大，可以减少学习的估计误差，但近似误差会变大，但意味着整体的模型变得简单。在实际中，
k
k
k值一般选择一个比较小的数值。
(4) 分类决策规则
分类误差率为：
1
k
∑
x
I
(
y
i
<
>
c
j
)
=
1
−
1
k
∑
x
I
(
y
i
=
c
j
)
\frac{1}{k}\sum_x{I(y_i<>c_j)=1-\frac{1}{k}}\sum_x{I(y_i=c_j)}
k1∑xI(yi<>cj)=1−k1∑xI(yi=cj) 要使分类误差率最小，即经验风险最小，就要使
∑
x
I
(
y
i
=
c
j
)
\sum_xI(y_i=c_j)
∑xI(yi=cj)最大，所以多数表决规则等价于经验风险最小化。
k
k
k邻近代码实现
# -*- coding: UTF-8 -*-
import numpy as np
import operator
from os import listdir
global nums
def classify0(inX, dataSet, labels, k):
#numpy函数shape[0]返回dataSet的行数
dataSetSize = dataSet.shape[0]
#在列向量方向上重复inX共1次(横向),行向量方向上重复inX共dataSetSize次(纵向)
diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
#二维特征相减后平方
sqDiffMat = diffMat**2
#sum()所有元素相加,sum(0)列相加,sum(1)行相加
sqDistances = sqDiffMat.sum(axis=1)
#开方,计算出距离
distances = sqDistances**0.5
#返回distances中元素从小到大排序后的索引值
sortedDistIndices = distances.argsort()
#定一个记录类别次数的字典
classCount = {}
for i in range(k):
#取出前k个元素的类别
voteIlabel = labels[sortedDistIndices[i]]
#dict.get(key,default=None),字典的get()方法,返回指定键的值,如果值不在字典中返回默认值。
#计算类别次数
classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
#python3中用items()替换python2中的iteritems()
#key=operator.itemgetter(1)根据字典的值进行排序
#key=operator.itemgetter(0)根据字典的键进行排序
#reverse降序排序字典
sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
#返回次数最多的类别,即所要分类的类别
return sortedClassCount[0][0]
def file2vector(filename):
fr = open(filename)
arrayOLines=fr.readlines()
numberOfLines=len(arrayOLines)
nums=numberOfLines
returnMat=np.zeros((numberOfLines,16))
classLabelVector=[]
index=0
for line in arrayOLines:
line=line.strip()
listFromLine=line.split(',')
returnMat[index,:]=listFromLine[1:17]
classLabelVector.append(listFromLine[0])
index+=1
return returnMat,classLabelVector
def alphabetClassTest():
trainingMat,alLabels=file2vector("trainingData.txt")
errorCount = 0.0
with open("testingData.txt",'r',encoding='utf-8') as f:
arrays=f.readline()
while arrays:
testMat=np.zeros((1,16))
teLabels=[]
inde=0
l=arrays.strip()
llist=l.split(',')
for i in range(1,17):
testMat[0,inde]=llist[i]
inde+=1
teLabels.append(llist[0])
classifierResult = classify0(testMat, trainingMat, alLabels, 5)
print("分类返回结果为%s\t真实结果为%s" % (classifierResult, teLabels[0]))
if(classifierResult != teLabels[0]):
errorCount += 1.0
arrays=f.readline()
print("总共4000，错了%d个数据\n正确率为%f%%" % (errorCount, (1-(errorCount)/4000)*100))
if __name__ == '__main__':
alphabetClassTest()
