人生苦短,我用 Python
K - 近邻算法:简单来说,K - 近邻算法就是采用测量不同特征值之间的距离方法进行分类
优点:精度高,对异常值不敏感,无数据输入假定
缺点:计算复杂度高,空间复杂度高
适用范围:数值型,标称型
工作原理:
存在一个样本数据集合,也称作训练样本集,并且样本集中每个数据都存在标签,即我们知道样本集中每一个数据与所属分类的对应关系.输入没有标签的新数据后,将新数据的每个特征与样本集中数据对应的特征进行比较,然后算法提取样本集中特征最相似的数据(最近邻)的分类标签.一般来说,我们只选择样本集中前 K 个最相似的数据,这就是 K - 近邻算法中 K 的出处,通常 K 是不大于 20 的整数.最后,选择 K 个最相似数据中出现次数最多的分类,作为新数据的分类.
K - 近邻算法的一般流程:
收集数据:可以使用任何方法.
准备数据:距离计算所需要的数值,最好是结构化的数据格式.
分析数据:可以使用任何方法.
训练算法:此步骤不适用于 K - 近邻算法.
测试算法:计算错误率.
使用算法:首先需要输入样本数据和结构化的输出结果,然后运行 K - 近邻算法判定输入数据分别属于哪个分类,最后应用对计算出的分类执行后续的处理.
实施 KNN 分类算法 -- 伪代码
对未知类别属性的数据集中的每个点依次执行以下操作:
计算已知类别数据集中的点与当前点之间的距离;
按照距离递增次序排序;
选取与当前点距离最小的 K 个点;
确定前 K 个点所在类别的出现频率;
返回前 K 个点出现频率最高的类别作为当前点的预测分类;
计算两个向量点之间的距离公式 -- 欧式距离公式:
例如:点(0,0)与(1,2)之间的距离计算为:
sqrt((1-0)**2+(2-0)**2)
代码实现:
测试结果:
import numpy as np
import operator
"""
def CreateDataSet():
group=np.array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
labels=['A','A','B','B']
return group,labels
print(CreateDataSet())
"""
"""
inX--用于分类的输入向量
dataSet--输入的训练样本集
labels--标签向量
k--用于选择最近邻居的数目
其中标签向量的元素数目和矩阵dataSet的行数相同
"""
def classify(inX,dataSet,labels,k):
dataSetSize=dataSet.shape[0] #获得训练样本集的行数
#将输入向量在列方向重复一次,在行方向上dataSize次,并与训练样本集dataSet相减
diffMat=np.tile(inX,(dataSetSize,1))-dataSet
print("diffMat:")
print(diffMat)
#将相减后的集合进行平方运算
sqDiffMat=diffMat**2
print("sqDiffMat:")
print(sqDiffMat)
#对平方后的集合进行相加运算--按行相加
sqDistances=sqDiffMat.sum(axis=1)
print("sqDistances:")
print(sqDistances)
#对相加后的数据开平方,得到输入向量与每个训练样本集之间的距离值
distances=np.sqrt(sqDistances)
print("distances")
print(distances)
#返回数组从小到大的索引值--排序
sortedDistIndicies=np.argsort(distances)
print("sortedDistIndicies")
print(sortedDistIndicies)
classCount={}
for i in range(k):
voteIlabel=labels[sortedDistIndicies[i]]
print("voteIlabel"+str(i))
print(voteIlabel)
classCount[voteIlabel]=classCount.get(voteIlabel,0)+1
print("classCount"+str(i))
print(classCount)
sortedClassCount=sorted(classCount.items(),
key=operator.itemgetter(1),reverse=True)
print("sortedClassCount:")
print(sortedClassCount)
return sortedClassCount[0][0]
if __name__=='__main__':
#训练样本集
group = np.array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
#标签向量
labels = ['A', 'A', 'B', 'B']
#输入向量
inX=[0,0]
#用于选择最近邻居的数目
k=3
result=classify(inX,group,labels,k)
print(result)
"""
输出值:
diffMat:
[[-1. -1.1]
[-1. -1. ]
[ 0. 0. ]
[ 0. -0.1]]
sqDiffMat:
[[ 1. 1.21]
[ 1. 1. ]
[ 0. 0. ]
[ 0. 0.01]]
sqDistances:
[ 2.21 2. 0. 0.01]
distances
[ 1.48660687 1.41421356 0. 0.1 ]
sortedDistIndicies
[2 3 1 0]
voteIlabel0
B
classCount0
{'B': 1}
voteIlabel1
B
classCount1
{'B': 2}
voteIlabel2
A
classCount2
{'B': 2, 'A': 1}
sortedClassCount:
[('B', 2), ('A', 1)]
B
Process finished with exit code 0
"""
输入 [0,0], 经过测试后,返回的结果是 B,也就是说[0,0] 这个输入向量通过 K - 近邻算法分类后归为 B 类
示例:使用 K - 近邻算法改进约会网站的配对效果
收集数据:提供文本文件
准备数据:使用 Python 解析文本文件
分析数据:使用 Matplotlib 画二维扩散图
训练算法:此步骤不适用与 K - 近邻算法
测试算法:使用海伦提供的部分数据作为测试样本
测试样本和非测试的区别在于:测试样本是已经完成分类的数据,如果预测分类与实际类别不同,则标记为一个错误.
使用算法:产生简单的命令行程序,然后可以输入一些特征数据以判断对方是否是自己喜欢的类型
准备数据:从文本文件中解析数据
文本样本数据特征:
每年获得的飞行常客里程数
玩视频游戏所耗时间的百分比
每周消费的冰淇淋公升数
将文本记录转换为 numpy 数据的解析程序:
特别说明:代码中的资源文件可以在此处下载: LiuGuoJiang/machinelearninginaction
def file2matrix(filename):
# 打开文件
fr = open(filename, 'r', encoding='utf-8')
# 按行读取数据
arrayOLines = fr.readlines()
# 获取数据的行数
numberOfLines = len(arrayOLines)
# 创建以0填充的矩阵
returnMat = np.zeros((numberOfLines, 3))
print(returnMat)
classLabelVector = []
index = 0
for line in arrayOLines:
print(line)
# 截取掉所有回车字符
line = line.strip()
print(line)
# 以'\t'将line分割成一个元素列表
listFromLine = line.split('\t')
# 选取前三个元素,存储到特征矩阵中
returnMat[index, :] = listFromLine[0:3]
# 选取最后一个元素存储到标签向量中
classLabelVector.append(int(listFromLine[-1]))
index += 1
return returnMat, classLabelVector
datingDataMat,datingLabels=file2matrix('D:\liuguojiang_Python\city_58\city_58\datingTestSet2.txt')
fig=plt.figure()
plt.title('K-')
plt.xlabel('fly')
plt.ylabel('consume')
ax=fig.add_subplot(111)
ax.scatter(datingDataMat[:,0],datingDataMat[:,1],
15.0*np.array(datingLabels),15.0*np.array(datingLabels))
plt.show()
解析文本数据并用散点图展示:
准备数据:归一化数值
任选样本数据中一行数据,计算距离时,因为飞行常客里程数比较大,所以对最后计算结果影响过大,所以需要对数据做归一化处理.如将取值范围处理为 0~1 或者 - 1~1 之间.下面的公式可以将任意取值范围的特征值转化为 0~1 区间内的值:
newValue=(oldValue-min)/(max-min)
其中 min 和 max 分别是数据集中的最小特征值和最大特征值.
归一化特征值函数:
测试算法:机器学习算法一个很重要的工作就是评估算法的正确率,通常我们只提供已有数据的 90% 作为训练样本来训练分类器,而使用其余的 10% 数据去测试分类器,检测分类器的正确率.10% 数据应该是随机选择的.分类器的测试代码:
def autoNorm(dataSet):
#选取列的最小值
minVals=dataSet.min(0)
#选取列的最大值
maxVals=dataSet.max(0)
#列的最大值与最小值做减法
ranges=maxVals-minVals
#
normDataSet=np.zeros([dataSet.shape[0],dataSet.shape[1]])
print(normDataSet)
#取出dataSet的行数
m=dataSet.shape[0]
#np.tile(minVals,(m,1))将minVals在 列上重复一次,在行上重复m次
normDataSet=dataSet-np.tile(minVals,(m,1)) #(oldValue-min)
normDataSet=normDataSet/np.tile(ranges,(m,1)) #(oldValue-min)/(max-min)
return normDataSet,ranges,minVals
normDataSet,ranges,minVals=autoNorm(datingDataMat)
print(normDataSet)
分类器处理数据集的错误率是 5%,即代表此分类器可以帮助对象判定分类.
def datingClassUnitTest():
hoRatio=0.10
datingDataMat, datingLabels = file2matrix('D:\liuguojiang_Python\city_58\city_58\datingTestSet2.txt')
print(datingDataMat)
normDataSet, ranges, minVals = autoNorm(datingDataMat)
print(normDataSet)
m=normDataSet.shape[0]
numTestVecs=int(m*hoRatio)
print("numTestVecs")
print(numTestVecs)
errorCount=0.0
for i in range(numTestVecs):
classifierResult=classify(normDataSet[i,:],normDataSet[numTestVecs:m,:],datingLabels[numTestVecs:m],3)
print("the classfier came back with:{},the real answer is:{}".format(classifierResult,datingLabels[i]))
if (classifierResult!=datingLabels[i]):errorCount+=1.0
print("the total error rate is:{}".format(errorCount/float(numTestVecs)))
the classfier came back with:3,the real answer is:3
the classfier came back with:2,the real answer is:2
the classfier came back with:1,the real answer is:1
.........
the classfier came back with:1,the real answer is:1
the classfier came back with:3,the real answer is:3
the classfier came back with:3,the real answer is:3
the classfier came back with:2,the real answer is:2
the classfier came back with:1,the real answer is:1
the classfier came back with:3,the real answer is:1
the total error rate is:0.05
编写可以让用户输入自己需要判断的输入向量,通过该分类器帮助用户判断属于哪一分类:
percentTats = float(input( \
def classifyPerson():
resultList = ['not at all', 'in small doses', 'in large doses']
classifierResult = classify((inArr - \
"percentage of time spent playing video games?"))
ffMiles = float(input("frequent flier miles earned per year?"))
iceCream = float(input("liters of ice cream consumed per year?"))
datingDataMat, datingLabels = file2matrix('D:\liuguojiang_Python\city_58\city_58\datingTestSet2.txt')
normDataSet, ranges, minVals = autoNorm(datingDataMat)
inArr = np.array([ffMiles, percentTats, iceCream, ])
总结:
minVals) / ranges, normDataSet, datingLabels, 3)
print("You will probably like this person: {}".format(resultList[classifierResult - 1]))
if __name__=='__main__':
classifyPerson()
"""
return:
percentage of time spent playing video games?10
frequent flier miles earned per year?10000
liters of ice cream consumed per year?0.5
You will probably like this person: in small doses
"""
定义 K - 近邻算法程序.
定义将文本数据集处理成二维数组的函数,便于处理.
为消除某一特征数值过大对结果判定的影响,定义归一化数值函数,公式:(oldValue-min)/(max-min)
定义测试算法函数,用于测试分类器的错误率是否满足使用要求.
定义可以让用户输入的代码,输入输入向量,用于判定分类
来源: https://juejin.im/post/5a5608b6518825732d7f7eb5