邻近算法(k-NearestNeighbor) 是机器学习中的一种分类(classification)算法,也是机器学习中最简单的算法之一了。虽然很简单,但在解决特定问题时却能发挥很好的效果。因此,学习kNN算法是机器学习入门的一个很好的途径。
kNN算法的思想非常的朴素,它选取k个离测试点最近的样本点,输出在这k个样本点中数量最多的标签(label)。我们假设每一个样本有m个特征值(property),则一个样本的可以用一个m维向量表示: X =( x1,x2,... , xm ), 同样地,测试点的特征值也可表示成:Y =( y1,y2,... , ym )。那我们怎么定义这两者之间的“距离”呢?
在二维空间中,有:d2 = ( x1 - y1 )2 + ( x2 - y2 )2 , 在三维空间中,两点的距离被定义为:d2 = ( x1 - y1 )2 + ( x2 - y2 )2 + ( x3 - y3 )2 。我们可以据此推广到m维空间中,定义m维空间的距离:d2 = ( x1 - y1 )2 + ( x2 - y2 )2 + ...... + ( xm - ym )2 。要实现kNN算法,我们只需要计算出每一个样本点与测试点的距离,选取距离最近的k个样本,获取他们的标签(label) ,然后找出k个样本中数量最多的标签,返回该标签。
在开始实现算法之前,我们要考虑一个问题,不同特征的特征值范围可能有很大的差别,例如,我们要分辨一个人的性别,一个女生的身高是1.70m,体重是60kg,一个男生的身高是1.80m,体重是70kg,而一个未知性别的人的身高是1.81m, 体重是64kg,这个人与女生数据点的“距离”的平方 d2 = ( 1.70 - 1.81 )2 + ( 60 - 64 )2 = 0.0121 + 16.0 = 16.0121,而与男生数据点的“距离”的平方d2 = ( 1.80 - 1.81 )2 + ( 70 - 64 )2 = 0.0001 + 36.0 = 36.0001 。可见,在这种情况下,身高差的平方相对于体重差的平方基本可以忽略不计,但是身高对于辨别性别来说是十分重要的。为了解决这个问题,就需要将数据标准化(normalize),把每一个特征值除以该特征的范围,保证标准化后每一个特征值都在0~1之间。我们写一个normData函数来执行标准化数据集的工作:
def normData(dataSet): maxVals = dataSet.max(axis=0) minVals = dataSet.min(axis=0) ranges = maxVals - minVals retData = (dataSet - minVals) / ranges return retData, ranges, minVals
然后开始实现kNN算法:
def kNN(dataSet, labels, testData, k): distSquareMat = (dataSet - testData) ** 2 # 计算差值的平方 distSquareSums = distSquareMat.sum(axis=1) # 求每一行的差值平方和 distances = distSquareSums ** 0.5 # 开根号,得出每个样本到测试点的距离 sortedIndices = distances.argsort() # 排序,得到排序后的下标 indices = sortedIndices[:k] # 取最小的k个 labelCount = {} # 存储每个label的出现次数 for i in indices: label = labels[i] labelCount[label] = labelCount.get(label, 0) + 1 # 次数加一 sortedCount = sorted(labelCount.items(), key=opt.itemgetter(1), reverse=True) # 对label出现的次数从大到小进行排序 return sortedCount[0][0] # 返回出现次数最大的label
注意,在testData作为参数传入kNN函数之前,需要经过标准化。
我们用几个小数据验证一下kNN函数是否能正常工作:
if __name__ == "__main__": dataSet = np.array([[2, 3], [6, 8]]) normDataSet, ranges, minVals = normData(dataSet) labels = ['a', 'b'] testData = np.array([3.9, 5.5]) normTestData = (testData - minVals) / ranges result = kNN(normDataSet, labels, normTestData, 1) print(result)
结果输出 a ,与预期结果一致。
完整代码:
import numpy as np from math import sqrt import operator as opt def normData(dataSet): maxVals = dataSet.max(axis=0) minVals = dataSet.min(axis=0) ranges = maxVals - minVals retData = (dataSet - minVals) / ranges return retData, ranges, minVals def kNN(dataSet, labels, testData, k): distSquareMat = (dataSet - testData) ** 2 # 计算差值的平方 distSquareSums = distSquareMat.sum(axis=1) # 求每一行的差值平方和 distances = distSquareSums ** 0.5 # 开根号,得出每个样本到测试点的距离 sortedIndices = distances.argsort() # 排序,得到排序后的下标 indices = sortedIndices[:k] # 取最小的k个 labelCount = {} # 存储每个label的出现次数 for i in indices: label = labels[i] labelCount[label] = labelCount.get(label, 0) + 1 # 次数加一 sortedCount = sorted(labelCount.items(), key=opt.itemgetter(1), reverse=True) # 对label出现的次数从大到小进行排序 return sortedCount[0][0] # 返回出现次数最大的label if __name__ == "__main__": dataSet = np.array([[2, 3], [6, 8]]) normDataSet, ranges, minVals = normData(dataSet) labels = ['a', 'b'] testData = np.array([3.9, 5.5]) normTestData = (testData - minVals) / ranges result = kNN(normDataSet, labels, normTestData, 1) print(result)
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
Python实现kNN算法
更新日志
- 群星《前途海量 电影原声专辑》[FLAC/分轨][227.78MB]
- 张信哲.1992-知道新曲与精丫巨石】【WAV+CUE】
- 王翠玲.1995-ANGEL【新艺宝】【WAV+CUE】
- 景冈山.1996-我的眼里只有你【大地唱片】【WAV+CUE】
- 群星《八戒 电影原声带》[320K/MP3][188.97MB]
- 群星《我的阿勒泰 影视原声带》[320K/MP3][139.47MB]
- 纪钧瀚《胎教古典音乐 钢琴与大提琴的沉浸时光》[320K/MP3][148.91MB]
- 刘雅丽.2001-丽花皇后·EMI精选王【EMI百代】【FLAC分轨】
- 齐秦.1994-黄金十年1981-1990CHINA.TOUR.LIVE精丫上华】【WAV+CUE】
- 群星.2008-本色·百代音乐人创作专辑【EMI百代】【WAV+CUE】
- 群星.2001-同步过冬AVCD【环球】【WAV+CUE】
- 群星.2020-同步过冬2020冀待晴空【环球】【WAV+CUE】
- 沈雁.1986-四季(2012梦田复刻版)【白云唱片】【WAV+CUE】
- 纪钧瀚《胎教古典音乐 钢琴与大提琴的沉浸时光》[FLAC/分轨][257.88MB]
- 《国语老歌 怀旧篇 3CD》[WAV/分轨][1.6GB]