学习笔记：K-近邻算法

一、K-近邻算法概述

适用于：数值型和标量型

（1）收集数据

（2）准备数据：向量点距离

（3）按照距离递增次序排序

（4）选取与当前距离最小的k个点

（5）确定选择k个点所在类别的频率

（6）判断当前点的的类别

二、K-近邻算法实现（Python语言实现)

（1）数据来源：采用datingTestSet.txt文件，数据来源于《Machine Learning in Action》源代码

共有数据1000行，含有三个数据特征：

每年获得的飞行里程数

玩视频游戏消耗的时间百分比

每周消费的冰淇淋公升数

（2）准备数据：从文本文件datingTestSet.txt中解析数据

def getMatrixFrmFile(filename):
#打开文件
file = open(filename)
#从文件中读取所有的行数
arrayAllLines = file.readlines()
#总行数
numberOfLines = len(arrayAllLines)
#保存结果的矩阵初始化(1000×3)
resultMat = np.zeros((numberOfLines,3))
#结果标签
resultLabelVector = []
index = 0
for line in arrayAllLines:
line = line.strip()
#分成三列数据
listFrmLine = line.split(“\t”)
resultMat[index,:] = listFrmLine[0:3]
#获得最后一列的标签数据
resultLabelVector.append(int(listFrmLine[-1]))
#处理下一行
index+=1
return resultMat,resultLabelVector

（3）解析数据

将numpy的矩阵数据分解成三组3中特征的数组

#处理数据
def handleData(resultMat,resultLabelVector):
labelX1,labelY1,labelZ1,labelX2,labelY2,labelZ2,labelX3,labelY3,labelZ3 = [],[],[],[],[],[],[],[],[]
resultArr = np.array(resultMat)

index=0
for label in resultLabelVector:
if index>1000:
break
if label==1:
labelX1.append(resultArr[index][0])
labelY1.append(resultArr[index][1])
labelZ1.append(resultArr[index][2])
elif label==2:
labelX2.append(resultArr[index][0])
labelY2.append(resultArr[index][1])
labelZ2.append(resultArr[index][2])
elif label==3:
labelX3.append(resultArr[index][0])
labelY3.append(resultArr[index][1])
labelZ3.append(resultArr[index][2])
index+=1
return labelX1,labelY1,labelZ1,labelX2,labelY2,labelZ2,labelX3,labelY3,labelZ3

（4）分析数据:使用Matplotlib创建散点图，分析结果

#绘制散点图,title1和title2表示点的名称
def drawDots(title1,title2,labelX1,labelY1,labelX2,labelY2,labelX3,labelY3):
plt.figure(figsize=(8, 5), dpi=80)
axes = plt.subplot(111)

label1 = axes.scatter(labelX1, labelY1, s=20, c=”red”)
label2 = axes.scatter(labelX2, labelY2, s=20, c=”green”)
label3 = axes.scatter(labelX3, labelY3, s=20, c=”blue”)

plt.xlabel(title1)
plt.ylabel(title2)
axes.legend((label1, label2, label3), (“don’t like”, “attraction common”, “attraction perfect”), loc=2)

plt.show()

（5）KNN算法

#使用K-近邻算法对输入的数据进行分类
def kNN_classify(inX,dataMat,labels,k):
”’
inX:输入的向量
dataMat:训练样本数据集
labels:训练样本的分类标签
k:选择近邻的个数
”’
#计算矩阵的行数
dataSize = dataMat.shape[0]
#计算距离
diffMat = np.tile(inX,(dataSize,1)) – dataMat
sqDiffMat = diffMat**2
sqDistance = sqDiffMat.sum(axis=1)
distance = sqDistance**0.5
#对距离进行排序,然后提取其索引赋值给sortedDistance
sortedDistance = distance.argsort()

classCount={}
for i in range(k):
voteLabel = labels[sortedDistance[i]]
classCount[voteLabel] = classCount.get(voteLabel,0)+1

sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
return sortedClassCount[0][0]

（6）特征向量归一化

#归一化特征值
def normalize(dataMat):
#求最小距离的向量
minVal = dataMat.min(0)
#求最大距离的向量
maxVal = dataMat.max(0)
#最值向量的差距
ranges = maxVal – minVal
#特征向量初始化
normDataMat = np.zeros(np.shape(dataMat))
#向量数
matSize = dataMat.shape[0]
#求特征值向量
normDataMat = dataMat – np.tile(minVal,(matSize,1))
normDataMat = normDataMat / np.tile(ranges,(matSize,1))
return normDataMat,ranges,minValresultMat,resultLabel = getMatrixFrmFile(“datingTestSet2.txt”)

（7）测试分类器

#测试分类器
def testDatingClassifier():
#测试数据的占总数据集的百分比
rate = 0.15
#从文件读取数据集和标签
datingDataMat,datingLabels = getMatrixFrmFile(“datingTestSet2.txt”)
labelX1,labelY1,labelZ1,labelX2,labelY2,labelZ2,labelX3,labelY3,labelZ3=handleData(datingDataMat,datingLabels)

drawDots(“Flying distance”,”Time for playing Video Game per Week”,labelX1,labelZ1,labelX2,labelZ2,labelX3,labelZ3)
drawDots(“Number of comsuming icecream per week”,”Time for playing Video Game per Week”,labelY1,labelZ1,labelY2,labelZ2,labelY3,labelZ3)
drawDots(“Flying distance”,”Number of comsuming icecream per week”,labelX1,labelY1,labelX2,labelY2,labelX3,labelY3)

#数据集归一化
normMat,ranges,minVals = normalize(datingDataMat)
#计算测试数据的个数
m = datingDataMat.shape[0]
numOfTest = int(rate*m)
#初始化出错数
errorNumber=0
#测试numOfTest个数据
for i in range(numOfTest):
classifiedResult = kNN_classify(normMat[i,:],normMat[numOfTest:m,:],datingLabels[numOfTest:m],3)
#print(“分类%d,结论是：%d” % (classifiedResult,datingLabels[i]))
if classifiedResult != datingLabels[i]:
errorNumber+=1.0
print(“总的正确率是%f” %(1-errorNumber/float(numOfTest)))

（8）测试运行结果

#main入口函数
if __name__ == ‘__main__’:
testDatingClassifier()
#判断下列数据的类别
inputX = [42666 ,13.276369, 0.543880]
datingDataMat,datingLabels = getMatrixFrmFile(“datingTestSet2.txt”)
normDataMat,ranges,minVal = normalize(datingDataMat)
inputX2 = (inputX-minVal)/ranges
className = classfiedName(kNN_classify(inputX2,normDataMat,datingLabels,3))
print(“对飞行里程：%f,每周冰淇淋消费数量：%f,每周玩视频游戏的比率：%f的人的感觉是%s” %(inputX[0],inputX[1],inputX[2],className))

运行结果如下：