Intro
k近邻法(k-nearest neighbor, k-NN)是1967年由Cover T和Hart P提出的一种基本分类与回归方法。它的工作原理是：存在一个样本数据集合，也称作为训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一个数据与所属分类的对应关系。输入没有标签的新数据后，将新的数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本最相似数据(最近邻)的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。
比较Metric
使用欧氏距离度量样本之间特征的相似度。
算法步骤
- 计算训练数据集中的点与当前点之间的距离；
- 按照距离递增次序排序；
- 选取与当前点距离最小的k个点；
- 确定前k个点所在类别的出现频率；
- 返回前k个点所出现频率最高的类别作为当前点的预测分类。
小问题
一位女士对男士的印象可以分为：不喜欢的人、魅力一般的人、极具魅力的人；主要根据三个特征来决定印象：每年获得的飞行常客里程数、玩视频游戏所消耗时间百分比、每周消费的冰淇淋公升数；
代码
数据预处理，符号化
# 读取数据，并符号化
def file2matrix(filepath):
with open(filepath, mode="r") as fr:
arrayOLines = fr.readlines()
# 得到文件行数
numberOfLines = len(arrayOLines)
# 返回的NumPy矩阵,解析完成的数据:numberOfLines行,3列
returnMat = np.zeros((numberOfLines, 3))
# 返回的分类标签向量
classLabelVector = []
# 行的索引值
index = 0
for line in arrayOLines:
line = line.strip()
# 使用s.split(str="",num=string,cout(str))将字符串根据'\t'分隔符进行切片。
listFromLine = line.split("\t")
# 将数据前三列提取出来,存放到returnMat的NumPy矩阵中,也就是特征矩阵
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
数据标准化，为了提出样本的不同特征之间值范围的影响；
# 标准化是机器学习和深度学习中的常见操作
def auto_norm(dataSet):
# 获得数据的最小值
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
# 最大值和最小值的范围
ranges = maxVals - minVals
# shape(dataSet)返回dataSet的矩阵行列数
normDataSet = np.zeros(np.shape(dataSet))
# 返回dataSet的行数
m = dataSet.shape[0]
# np.tile 铺瓷砖函数
normDataSet = dataSet - np.tile(minVals, (m, 1))
normDataSet = normDataSet / np.tile(ranges, (m, 1))
return normDataSet, ranges, minVals
测试
# 返回一个测试样本的分类结果
def classify0(test_set, train_set, labels, k):
# numpy函数shape[0]返回dataSet的行数
dataSetSize = train_set.shape[0]
# 在列向量方向上重复inX共1次(横向),行向量方向上重复inX共dataSetSize次(纵向)
# 这里如果test_set不是一条数据，就是一种粗粒度的比较
diffMat = np.tile(test_set, (dataSetSize, 1)) - train_set
# 二维特征相减后平方
sqDiffMat = diffMat**2
# sum()所有元素相加,sum(0)列相加,sum(1)行相加
sqDistances = sqDiffMat.sum(axis=1)
# 开方,计算出距离
distances = sqDistances**0.5
# 返回distances中元素从小到大排序后的索引值
sortedDistIndices = distances.argsort()
# 定一个记录类别次数的字典
classCount = {}
for i in range(k):
# 取出前k个元素的类别
voteIlabel = labels[sortedDistIndices[i]]
# dict.get(key,default=None),字典的get()方法,返回指定键的值,如果值不在字典中返回默认值。
# 计算类别次数
classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
# reverse降序排序字典
sortedClassCount = sorted(
classCount.items(), key=lambda item: item[1], reverse=True
)
# 返回次数最多的类别,即所要分类的类别
return sortedClassCount[0][0]
# 给定一个男人的三个特征，判断其所属类别
def classifyPerson():
# 输出结果
resultList = ["讨厌", "有些喜欢", "非常喜欢"]
# 三维特征用户输入
precentTats = float(input("玩视频游戏所耗时间百分比:"))
ffMiles = float(input("每年获得的飞行常客里程数:"))
iceCream = float(input("每周消费的冰激淋公升数:"))
# 打开的文件名
filename = "../dataset/datingTestSet.txt"
# 打开并处理数据
datingDataMat, datingLabels = file2matrix(filename)
# 训练集归一化
normMat, ranges, minVals = auto_norm(datingDataMat)
# 生成NumPy数组,测试集
inArr = np.array([ffMiles, precentTats, iceCream])
# 测试集归一化
norminArr = (inArr - minVals) / ranges
# 返回分类结果
classifierResult = classify0(norminArr, normMat, datingLabels, 3)
# 打印结果
print("你可能%s这个人" % (resultList[classifierResult - 1]))
if __name__ == "__main__":
classifyPerson()
参考
参考 内涵数据集下载地址。
