机器学习实战-k近邻算法
2.1 kNN 算法
引入：电影识别问题
现在我有一些电影，其打斗镜头、接吻镜头、电影类型成一个表格，并且存在着一定的关系。现在我有一部新的电影，已知打斗镜头数量和接吻镜头数量，请问这最有可能是一部什么电影。
我们想象一个坐标轴，x 轴是打斗镜头；y 轴是接吻镜头。然后将源电影的点放在这个轴上。然后我们就可以得到一个很自然的思路：我的目标电影离哪些源电影更近，我的目标电影就更有可能是什么电影。
那么我们如何衡量最近呢？我们知道有三种距离：曼哈顿距离（绝对值差之和），切比雪夫距离（绝对值差最大值），欧几里得距离（方差）。然后我们要考虑到我们要利用一个强大的工具：矩阵。而事实上，这几个距离当中最原教旨的距离就是欧氏距离了。所以最后的方案就是采用欧氏距离。
算法步骤
- Step 1：目标矩阵和源矩阵每行求逐差
- Step 2：逐差各自平方
- Step 3：按行求和
- Step 4：按行根号
- Step 5：排序求最前 k 个点
- Step 6：统计前 k 个点所在的类
- Step 7：返回最多的类别
def classify0(inX, dataSet, labels, k):
dataSetSize = dataSet.shape[0]
diffMat = tile(inX, (dataSetSize,1))-dataSet # Step 1
sqDiffMat = diffMat**2 # Step 2
sqDistances = sqDiffMat.sum(axis=1) # Step 3
distances = sqDistances**0.5 # Step 4
sortedDistIndicies = distances.argsort() # Step 5.1 排序
classCount={}
for i in range(k): # Step 5.2 求前k个点
voteLabel = labels[sortedDistIndicies[i]]
classCount[voteLabel]=classCount.get(voteLabel,0)+1 # Step 6 统计
sortedClassCount = sorted(classCount.items(),
key=operator.itemgetter[1],reverse=True)
return sortedClassCount[0][0] # Step 7 返回最多的类2.2 使用 kNN 算法改进约会网站配对效果
海伦的样本有三个特征：飞行里程数，视频游戏所耗时间，消费冰淇淋公升数。她想要凭借这些数据，将约会网站推荐的对象划分入不喜欢的人，魅力一般的人，极具魅力的人三个分类。请你解析出这些数据。
2.2.1 准备数据：
数据集的格式如下：
|飞行里程|视频游戏所耗时间|消费冰淇淋公升数|魅力分类|
这样的数据显然没法直接被我们的程序所使用，所以我们要先处理数据生成数据集。
一个数据集分为两个部分：训练样本矩阵＋类标签向量；向量中每一个元素和一条训练样本是一一对应的。
算法流程
Step 1：读入文件内容，并且按照文本大小创建空矩阵
Step 2：将文件每行利用分片操作进行分割，得到每行的训练样本矩阵和类标签向量。
def file2matrix(filename):
fr = open(filename)
lines = fr.readlines()
mat = zeros((len(lines),3))
label=[]
for i in range(0,len(lines)):
line=lines[i]
line=line.strip()
datas=line.split('\t')
mat[i]=datas[:3]
label.append(int(datas[-1]))
return mat,label2.2.2 创建散点图
我们用样本分类标签展示其中两个维度的散点图：
mat,label=file2matrix("/home/andyshen/ml-learning/Chapter2/datingTestSet.txt")
fig=plt.figure()
ax = fig.add_subplot(111)
ax.scatter(mat[:,1],mat[:,2],15*array(label),15*array(label))2.2.3 归一化矩阵
显然原始数据本身数值大小会导致不同参数其作用不同，为了消除这种影响，我们可以将求出来的值进行归一化：将在
def autoNorm(dataSet: ndarray):
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals-minVals
result = zeros(shape(dataSet))
m=dataSet.shape[0]
result=dataSet-tile(minVals,(m,1))
result = result/tile(ranges,(m,1))
return result,ranges,minVals2.2.4 测试算法
结合前面的 classify0，我们就可以将这几个部件组装在一起了。
我们先做一个自我检测，原理很简单：用源数据检验得到的矩阵是否正确。
算法流程
- Step 1：读取数据，转化为矩阵和名称向量
- Step 2：将矩阵归一化
- Step 3：取出一部分源数据集中数据作为测试数据，使用余下数据进行检测。
经测试，该算法正确率高达 95%！
2.3 手写识别系统
呼之欲出的，我们可以类似的将手写数据进行转换，然后利用手写数据集去识别其文字。
我们要做如下操作：将手写图片转换成 32x32 的矩阵，再将其转为长度为 1024 的向量，将数据集的向量组装起来形成源数据。第一步别人已经做好了，我就做后几步。转换为数据集之后，跑 kNN 出结果就行。
import os
from numpy import *
import operator
dir_pre="/home/andyshen/ml-learning/Chapter2/"
def file2vec(filename:str) -> list[int]:
fr=open(filename)
lines = fr.readlines()
line=""
for l in lines:
line+=l.strip()
vec=[]
for c in line:
vec.append(int(c))
return vec
def readTrainingDigits(dir:str) -> ndarray[tuple[int,int]]:
files=os.listdir(dir_pre+dir)
length=len(files)
labels=[]
mat=zeros((length,1024))
for i in range(length):
filename=files[i]
label=int(filename.split('_')[0])
labels.append(label)
vec = file2vec(dir_pre+dir+filename)
mat[i,:]=vec
return mat,labels
def classify(xIn:list[int],dataSet:ndarray[tuple[int,int]],labels:list[int],k:int) -> int:
dataSetSize = len(dataSet)
diffMatrix = dataSet - tile(xIn,(dataSetSize,1))
sqrtMatrix = diffMatrix**2
sqrtVec:ndarray[int] = sqrtMatrix.sum(axis=1)
vec:ndarray[int] = sqrtVec**0.5
sortedVecIdx = vec.argsort()
classCount={}
for i in range(k):
label=labels[sortedVecIdx[i]]
classCount[label]=classCount.get(label,0)+1
sortedClassCount = sorted(classCount.items(),
key=operator.itemgetter(1),reverse=True)
return sortedClassCount[0][0]
# print(file2vec(dir_pre+"trainingDigits/0_0.txt"))
# print(os.listdir("trainingDigits"))
mat,labels=readTrainingDigits("trainingDigits/")
testdir="testDigits/"
testfiles = os.listdir(dir_pre+testdir)
corr=0
for testfile in testfiles:
src=int(testfile.strip().split('_')[0])
vec=file2vec(dir_pre+testdir+testfile)
res=classify(vec,mat,labels,3)
print(f"src: {src}; res: {res}")
corr+=src==res
total=len(testfiles)
print(f"correct:{corr},total{total},rate:{corr/total}")