K-近邻算法---分类
使用 k 近邻算法改进网站的配对效果
# 导入程序所需要的模块
import numpy as np
import operator
定义数据集导入函数
file2matrix函数实现的功能是读取文件数据,函数返回的returnMat和classLabelVector分别是数据集的特征矩阵和输出标签向量。
def file2matrix(filename):
love_dictionary = {'largeDoses':3, 'smallDoses':2, 'didntLike':1} # 三个类别
fr = open(filename) # 打开文件
arrayOLines = fr.readlines() # 逐行打开
numberOfLines = len(arrayOLines) #得到文件的行数
returnMat = np.zeros((numberOfLines, 3)) #初始化特征矩阵
classLabelVector = [] #初始化输出标签向量
index = 0
for line in arrayOLines:
line = line.strip() # 删去字符串首部尾部空字符
listFromLine = line.split('\t') # 按'\t'对字符串进行分割,listFromLine 是列表
returnMat[index, :] = listFromLine[0:3] # listFromLine的0,1,2元素是特征,赋值给returnMat的当前行
if(listFromLine[-1].isdigit()): # 如果listFromLine最后一个元素是数字
classLabelVector.append(int(listFromLine[-1])) # 直接赋值给classLabelVector
else: # 如果listFromLine最后一个元素不是数字,而是字符串
classLabelVector.append(love_dictionary.get(listFromLine[-1])) # 根据字典love_dictionary转化为数字
index += 1
return returnMat, classLabelVector # 返回的类别标签classLabelVector是1,2,3
定义特征归一化函数
这里为什么要对特征进行归一化?
因为在处理这种不同取值范围的特征值时,数值归一化能够将不同特征的取值范围限定在同一区间例如[0,1]之间,让不同特征对距离的计算影响相同。具体可看《机器学习实战》第2.2.3节内容。
def autoNorm(dataSet):
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals
normDataSet = np.zeros(np.shape(dataSet))
m = dataSet.shape[0]
normDataSet = dataSet - np.tile(minVals, (m, 1))
normDataSet = normDataSet/np.tile(ranges, (m, 1)) # normDataSet值被限定在[0,1]之间
return normDataSet, ranges, minVals
定义 k 近邻算法
def classify0(inX, dataSet, labels, k): # inX是测试集,dataSet是训练集,lebels是训练样本标签,k是取的最近邻个数
dataSetSize = dataSet.shape[0] # 训练样本个数
diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet # np.tile: 重复n次
sqDiffMat = diffMat**2
sqDistances = sqDiffMat.sum(axis=1)
distances = sqDistances**0.5 # distance是inX与dataSet的欧氏距离
sortedDistIndicies = distances.argsort() # 返回排序从小到达的索引位置
classCount = {} # 字典存储k近邻不同label出现的次数
for i in range(k):
voteIlabel = labels[sortedDistIndicies[i]]
classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1 # 对应label加1,classCount中若无此key,则默认为0
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True) # operator.itemgetter 获取对象的哪个维度的数据
return sortedClassCount[0][0] # 返回k近邻中所属类别最多的哪一类
测试算法:作为完整程序验证分类器
def datingClassTest():
hoRatio = 0.10 #整个数据集的10%用来测试
datingDataMat, datingLabels = file2matrix('datingTestSet2.txt') #导入数据集
normMat, ranges, minVals = autoNorm(datingDataMat) # 所有特征归一化
m = normMat.shape[0] # 样本个数
numTestVecs = int(m*hoRatio) # 测试样本个数
errorCount = 0.0
for i in range(numTestVecs):
classifierResult = classify0(normMat[i, :], normMat[numTestVecs:m, :], datingLabels[numTestVecs:m], 3)
print("the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i]))
if (classifierResult != datingLabels[i]): errorCount += 1.0
print("the total error rate is: %f" % (errorCount / float(numTestVecs))) # 打印错误率
print(errorCount) # 打印错误个数
datingClassTest()
运行结果;
使用算法:构建完整可用系统
根据用户输入,在线判断类别。
def classifyPerson():
resultList = ['not at all', 'in small doses', 'in large doses']
percentTats = float(input(\
"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('datingTestSet2.txt')
normMat, ranges, minVals = autoNorm(datingDataMat)
inArr = np.array([ffMiles, percentTats, iceCream, ])
classifierResult = classify0((inArr - \
minVals)/ranges, normMat, datingLabels, 3)
print("You will probably like this person: %s" % resultList[classifierResult - 1])
classifyPerson()
运行结果: