文章目录
  1. 1. kNN分类算法
  2. 2. 西瓜数据集3.0$\alpha$:
  3. 3. kNN分类器
  4. 4. 测试结果

kNN分类算法

一种常用的监督学习算法,k-Nearest Neighbor,k-近邻算法。算法思想如下:

选定参数k,对于样本X,选取距离X最近的k个样本,取这k个样本出现最多的类别作为预测的此类类别。

它没有显式的训练过程,有数据就可以开始进行测试或者预测了,是一种“懒惰学习”算法。
距离计算采用欧式距离,计算两个二维向量的距离:
$$d=\sqrt{(xA_0-xB_0)^2+(xA_1-xB_1)^2}$$

西瓜数据集3.0$\alpha$:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
密度 含糖率 好瓜
0.697 0.460 1
0.774 0.376 1
0.634 0.264 1
0.608 0.318 1
0.556 0.215 1
0.403 0.237 1
0.481 0.149 1
0.437 0.211 1
0.666 0.091 0
0.243 0.267 0
0.245 0.057 0
0.343 0.099 0
0.639 0.161 0
0.657 0.198 0
0.360 0.370 0
0.593 0.042 0
0.719 0.103 0

kNN分类器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
from numpy import *
from operator import itemgetter
import matplotlib.pyplot as plt

def file2matrix(filename): #数据从文本导入矩阵
file = open(filename)
arraylines = file.readlines()
numberoflines = len(arraylines) - 1
returnMat = zeros((numberoflines,2)) #创建行数为numberoflines,列数为2的矩阵
classLabel = []
index = 0
for line in arraylines[1:]:
line = line.strip()
lis = line.split(' ')
returnMat[index,:] = lis[0:2]
classLabel.append(int(lis[-1])+1) #是为2类,否为1类
index += 1
return returnMat,classLabel

def createDataSet(): #数据生成测试,忽略
group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
labels = [1,1,2,2]
return group,labels

def classify0(inX, dataSet, labels, k): # kNN分类器
dataSetSize = dataSet.shape[0] # shape[0]表行数,如果是二维数组,则shape[1]表列数
diffMat = tile(inX, (dataSetSize,1)) - dataSet # tile(A,(a,b)): 将数组A垂直重复a次,水平重复b次
sqdiffMat = diffMat ** 2 #距离平方
sqDistance = sqdiffMat.sum(axis=1) #距离相加,axis=0表按列求和,axis=1表按行求和
dis = sqDistance ** 0.5
sortedDisIndex = dis.argsort() #排序,argsort():排序后的数据原来的位置
classCount = {}
for i in range(k):
voteLabel = labels[sortedDisIndex[i]] # 根据i处的数据原来的位置找到其类别
classCount[voteLabel] = classCount.get(voteLabel,0)+1
sortedclassCount = sorted(classCount.items(),key=itemgetter(1), reverse=True)
return sortedclassCount[0][0] # 出现次数最多的类为预测类

def ClassTest(): #测试
testratio = 0.15 #测试数据比例
DataMat,Labels = file2matrix('D:\\MLinAction\\Data\\xiguaalpha.txt')
m = DataMat.shape[0] #数据组数
numTest = int(m*testratio) #测试数据组数
errorCount = 0.0
for i in range(numTest):
classifierRes = classify0(DataMat[i,:],DataMat[numTest:m,:],Labels[numTest:m],3)
print("分类器分类为: %d, 真实分类为 %d" %(classifierRes,Labels[i]))
if classifierRes != Labels[i]:
errorCount += 1.0
print("错误率: %.5f" %(errorCount/float(numTest)))

ClassTest()
group,labels = file2matrix('D:\\MLinAction\\Data\\xiguaalpha.txt')
plt.scatter(group[:,0],group[:,1],35.0*array(labels),35.0*array(labels))
plt.show()

测试结果

1
2
3
分类器分类为: 2, 真实分类为 2
分类器分类为: 2, 真实分类为 2
错误率: 0.00000

图1


参考文献:
《机器学习》
《机器学习实战》

机器学习 | Mac.Learning