k-近邻算法
一、k-近邻算法概述
k-近邻算法是一种常用的监督学习算法，用于分类和回归任务。其思想为：如果一个样本在特征空间中的k个最近邻居中的大多数属于某个类别，那么该样本也属于这个类别（对于分类任务）或者可以通过这些最近邻居的标签来估计其目标值（对于回归任务）。
1.1 使用python导入数据
def createDataSet():
'''
构造数据
Parameters:
None
Returns:
group - 数据
labels - 标签
'''
group = array([[100,98],[100,100],[0,0],[0,10]]) #[测试1的得分,测试2的得分]
labels = ['A','A','B','B'] #整体评级情况
return group, labels
1.2 从文本文件中解析数据
通过计算两点之间的距离来进一步选择相近的k个点：
d = ( x A 0 − x B 0 ) 2 − ( x A 1 − x B 1 ) 2 d=\sqrt{(x_{A_0}-x_{B_0})^2-(x_{A_1}-x_{B_1})^2} d=(xA0−xB0)2−(xA1−xB1)2
def classify_KNN(inX, dataSet, labels, k):
'''
使用kNN算法进行分类
Parameters:
inX - 用于分类的数据(测试集)
dataSet - 用于训练的数据(训练集)
labels - 训练集标签
k - kNN算法参数,选择距离最小的k个点
Returns:
sortedClassCount - 分类结果
'''
dataSetSize = dataSet.shape[0] #dataSet的行数
diffMat = inX - 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 #类别数量+1
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
至此，就可以通过给定数据进行分类预测，分类预测的效果与数据集的标准
二、使用k-近邻算法改进约会网站的配对效果
2.1 准备数据
海伦将自己交往过的人可以进行如下分类：不喜欢的人、魅力一般的人、极具魅力的人。
海伦收集约会数据已经有了一段时间，她把这些数据存放在文本文件datingTestSet.txt中，每个样本数据占据一行，总共有1000行。海伦收集的样本数据主要包含以下3种特征：每年获得的飞行常客里程数、玩视频游戏所消耗时间百分比、每周消费的冰淇淋公升数。
def file2matrix(filename):
'''
读取数据，并将其转化为矩阵
Parameters:
filename - 文件路径
Returns:
returnMat - 数据矩阵
classLabelVector - 数据标签
'''
with open(filename, "r") as file:
lines = file.readlines() #读取文本信息
numberOfLines = len(lines) #计算行数
returnMat = zeros((numberOfLines,3)) #初始化矩阵
classLabelVector = [] #创建分类标签向量
index = 0
for line in lines:
line = line.strip()
listFromLine = line.split('\t')
returnMat[index,:] = listFromLine[0:3]
#根据文本中标记的喜欢的程度进行分类,1代表不喜欢,2代表魅力一般,3代表极具魅力
if listFromLine[-1] == 'didntLike':
classLabelVector.append(1)
elif listFromLine[-1] == 'smallDoses':
classLabelVector.append(2)
elif listFromLine[-1] == 'largeDoses':
classLabelVector.append(3)
index += 1
return returnMat, classLabelVector #(1000, 3),(1000,)
2.2 数据预处理
对于不同的类别的数据分布差异可能比较大，例如游戏时长百分比的差异在0-1之间，而飞行里程往往差异成败上千不等，差异大的属性值会严重影响欧式距离。因此需要对数据进行标准化，计算公式如下：
d a t a n o r m = d a t a − d a t a m i n d a t a m a x − d a t a m i n data_{norm} = \frac{data-data_{min}}{data_{max}-data_{min}} datanorm=datamax−datamindata−datamin
def autoNorm(dataSet):
'''
归一化dataset中的值，函数返回归一化后的数据
Parameters:
dataSet - 原始数据
Returns:
normDataSet - 归一化后的数据
ranges - 最大最小值的差值
minVals - 数据中的最小值
'''
minVals = dataSet.min(0) #获得数据的最小值
maxVals = dataSet.max(0) #获得数据的最大值
ranges = maxVals - minVals#最大值和最小值的范围
normDataSet = zeros(shape(dataSet)) #初始化归一矩阵
m = dataSet.shape[0] #dataSet的行数
normDataSet = dataSet - tile(minVals, (m, 1)) #原始值减去最小值，tile是扩充函数
normDataSet = normDataSet / tile(ranges, (m, 1)) #除以最大和最小值的差,得到归一化数据
return normDataSet, ranges, minVals
2.3 分析数据
def showdatas(datingDataMat, datingLabels):
'''
将数据以散点图形式展示出来。
Parameters:
datingDataMat - 数据矩阵
datingLabels - 数据标签
Returns:
None
'''
color_map = {1: 'r', 2: 'g', 3: 'b'} # 创建颜色映射，将每个标签映射到不同的颜色
label_name = ['didntLike','smallDoses','largeDoses']
# 根据标签分组数据点
grouped_data = {}
for label in np.unique(datingLabels):
grouped_data[label] = datingDataMat[datingLabels == label]
plt.figure(figsize=(18, 6))
plt.subplot(131) # 创建X-Y平面上的散点图
for label, color in color_map.items():
points = grouped_data[label]
plt.scatter(points[:, 0], points[:, 1], c=color, label=f'{label_name[label-1]}')
plt.xlabel('每年获得的飞行常客里程数',fontproperties=font)
plt.ylabel('玩视频游戏所消耗时间占',fontproperties=font)
plt.legend()
# 创建X-Z平面上的散点图
plt.subplot(132)
for label, color in color_map.items():
points = grouped_data[label]
plt.scatter(points[:, 0], points[:, 2], c=color, label=f'{label_name[label-1]}')
plt.xlabel('每年获得的飞行常客里程数',fontproperties=font)
plt.ylabel('每周消费的冰激淋公升数',fontproperties=font)
plt.legend()
# 创建Y-Z平面上的散点图
plt.subplot(133)
for label, color in color_map.items():
points = grouped_data[label]
plt.scatter(points[:, 1], points[:, 2], c=color, label=f'{label_name[label-1]}')
plt.xlabel('玩视频游戏所消耗时间占',fontproperties=font)
plt.ylabel('每周消费的冰激淋公升数',fontproperties=font)
plt.legend()
# 显示图形
plt.tight_layout()
plt.show()
2.4 测试算法
将数据按照指定比例划分训练集与测试集，训练集用于构建模型，测试集用于评估算法与数据的可靠性。
def datingClassTest():
"""
测试算法的准确度，打印出算法的错误率
Parameters:
None
Returns:
None
"""
filename = r"./datingTestSet.txt" #文件路径
datingDataMat, datingLabels = file2matrix(filename)
hoRatio = 0.10 #测试集比例
normMat, ranges, minVals = autoNorm(datingDataMat) #数据归一化
m = normMat.shape[0] #数据量
numTestVecs = int(m * hoRatio) #测试集个数
errorCount = 0.0 #分类错误量
for i in range(numTestVecs): #遍历测试集，评估正确率
classifierResult = classify_KNN(normMat[i,:], normMat[numTestVecs:m,:],datingLabels[numTestVecs:m], 4)
#输出错误的情况
if classifierResult != datingLabels[i]:
errorCount += 1.0
print("分类结果:%d\t真实类别:%d" % (classifierResult, datingLabels[i]))
print("错误率:%f%%" %(errorCount/float(numTestVecs)*100))
2.5使用算法
调用模型就可以进行数据的预估，不同的k值也可能会有不同的结果。需要根据实际应用场景决定
def classifyPerson():
"""
根据输入内容进行判断
Parameters:
None
Returns:
None
"""
resultList = ['讨厌','有些喜欢','非常喜欢'] #输出结果
precentTats = float(input("玩视频游戏所耗时间百分比:"))
ffMiles = float(input("每年获得的飞行常客里程数:"))
iceCream = float(input("每周消费的冰激淋公升数:"))
filename = "./datingTestSet.txt"
datingDataMat, datingLabels = file2matrix(filename)
normMat, ranges, minVals = autoNorm(datingDataMat)
inArr = array([precentTats, ffMiles, iceCream])
norminArr = (inArr - minVals) / ranges
#返回分类结果
classifierResult = classify_KNN(norminArr, normMat, datingLabels, 3)
#打印结果
print("你可能%s这个人" % (resultList[classifierResult-1]))
三、手写体识别系统
对于手写识别系统而言整体流程是一致的，主要差距在于数据的输入以及预处理上。
def img2vector(file_path):
"""
将32x32的二进制图像转换为1x1024向量。
Parameters:
file_path - 文件名
Returns:
returnVect - 返回的二进制图像的1x1024向量
"""
returnVect = np.zeros((1, 1024)) #初始化
with open(file_path, 'r') as file:
for i in range(32):
lineStr = file.readline()
for j in range(32):
returnVect[0, 32*i+j] = int(lineStr[j])
return returnVect