KNN 原理
-
假设有一个带有标签的样本数据集（训练样本集），其中包含每条数据与所属分类的对应关系。
-
输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较。
-
计算新数据与样本数据集中每条数据的距离。
-
对求得的所有距离进行排序（从小到大，越小表示越相似）。
-
取前 k （k 一般小于等于 20 ）个样本数据对应的分类标签。
-
-
求 k 个数据中出现次数最多的分类标签作为新数据的分类。
KNN 开发流程
-
收集数据：任何方法
-
准备数据：距离计算所需要的数值，最好是结构化的数据格式
-
分析数据：任何方法
-
训练算法：此步骤不适用于 k-近邻算法
-
测试算法：计算错误率
-
使用算法：输入样本数据和结构化的输出结果，然后运行 k-近邻算法判断输入数据分类属于哪个分类，最后对计算出的分类执行后续处理
KNN 算法特点
-
优点：精度高、对异常值不敏感、无数据输入假定
-
缺点：计算复杂度高、空间复杂度高
-
适用数据范围：数值型和标称型
KNN 项目案例
约会网站的配对效果
数据说明：
-
每年的飞行里程数
-
视频和游戏所耗时间百分比
-
每周消费的冰淇淋公升数
-
喜欢程度
1. txt 转换为 arry
原代码注释已经非常详细，但毕竟是一个项目类，而且有些代码是基于python2.x版本的，所以非常基础的点就没有再提。作为新手的阅读笔记，逐行分析了代码，包括函数用法，参数原理等。
import numpy as np
import operator
def convert_text_into_arry(filename):
"""
Desc:
导入训练数据
parameters:
filename: 数据文件路径
return:
数据矩阵 returnMat 和对应的类别 classLabelVector
"""
fr = open(filename)
# readlines() 用于读取所有行(直到结束符 EOF)并返回列表，
# 该列表可以由 Python 的 for... in ... 结构进行处理。
number_of_lines = len(fr.readlines())
# 生成等行的矩阵，值全为0
return_mat = np.zeros((number_of_lines, 3), dtype = float)
# 生成标签列
class_labels = []
"""
read() 运行结束后，将指针移动到了数据末尾
a.重新open()
b.用seek(0)将指针重新复位到开头
"""
fr.seek(0)
index = 0
for line in fr.readlines():
# 删除开头或是结尾的字符
line = line.strip()
list_from_line = line.split('\t')
# 每一行由index 和 原列表的前三列构成
return_mat[index, :] = list_from_line[0:3]
# 将每行的最后一个数字添加到标签列中
class_labels.append(int(list_from_line[-1]))
index += 1
# 结果返回为return_mat和class_labels待其他function调用。
return return_mat, class_labels
# 关闭打开的文件
fr.close()
2. R语言可视化
file = file.choose()
data <- read.table(file = file, header = FALSE)
data <- rename(data, Flyier_miles = V1,
Time_plaing_video_games = V2,
Icecream = V3,
levels = V4)
data$levels <- factor(data$levels,
levels = c(1,2,3))
ggplot(data = data) + geom_point(aes(x = Flyier_miles,
y = Time_plaing_video_games,
color = levels)) +
scale_color_discrete(labels = c("don't like",
"like in small doses",
"like in large doses"))
K-NN.png
3. 归一化特征值
def autoNorm(dataSet):
"""
Desc:
归一化特征值，消除特征之间量级不同导致的影响
parameter:
dataSet: 数据集
return:
归一化后的数据集 normDataSet. ranges和minVals即最小值与范围，并没有用到
归一化公式：
Y = (X - Xmin)/(Xmax - Xmin)
其中的 min 和 max 分别是数据集中的最小特征值和最大特征值。
该函数可以自动将数字特征值转化为0到1的区间。
"""
# 计算每列的最大值、最小值、极差
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals
m = dataSet.shape[0]
# 根据数据集的样子，新建值一个全为0的矩阵
normDataSet = np.zeros(np.shape(dataSet))
# 生成数据集与最小值之差组成的新矩阵
## tile(minVals, (m, 1)) 重复minVals m次，生成m行、列数不变的新数据集
normDataSet = dataSet - np.tile(minVals, (m, 1))
# 将最小值之差除以范围组成矩阵
normDataSet = normDataSet / np.tile(ranges, (m, 1))
return normDataSet, ranges, minVals
4.距离计算
特征空间中两个实例点的距离就是是两个实例点相似程度的反映。一般采用欧氏距离，但也可以是cosine距离，曼哈顿距离等。
欧氏距离(Euclidean Distance)
欧几里得度量（euclidean metric）（也称欧氏距离）是一个通常采用的距离定义，指在m维空间中两个点之间的真实距离，或者向量的自然长度（即该点到原点的距离），在二维和三维空间中的欧氏距离就是两点之间的实际距离。
二维平面：
三维空间：
n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x}2n)间的欧氏距离:
算法实现
def classify0(inX, dataSet, labels, k):
# 按照输入的dataSet的样式生成一个数值为0的矩阵。
dataSetSize = dataSet.shape[0]
#距离度量 度量公式为欧氏距离
diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
sqDiffMat = diffMat**2
sqDistances = sqDiffMat.sum(axis = 1)
distances = sqDistances**0.5
#将距离排序：从小到大
sortedDistIndicies = distances.argsort()
#选取前K个最短距离， 选取这K个中最多的分类类别
classCount={}
for i in range(k):
voteIlabel = labels[sortedDistIndicies[i]]
classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
此时，KNN算法的核心代码就写完了，将上面的三个function放在一起，输入数据即可完成对数据的分类。
测试代码
利用约会网站的数据，测试代码的准确性。如果预测分类与实际类别不同，则标记为一个错误。
def datingClassTest(file):
"""
Desc:
对约会网站的测试方法
parameters:
none
return:
错误数
"""
# 设置测试数据的的一个比例（训练数据集比例=1-hoRatio）
hoRatio = 0.1 # 测试范围,一部分测试一部分作为样本
# 从文件中加载数据
datingDataMat, datingLabels = convert_text_into_arry(file) # load data setfrom file
# 归一化数据
normMat, ranges, minVals = autoNorm(datingDataMat)
# m 表示数据的行数，即矩阵的第一维
m = normMat.shape[0]
# 设置测试的样本数量， numTestVecs:m表示训练样本的数量
numTestVecs = int(m * hoRatio)
print('numTestVecs=', numTestVecs)
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("C:\\Users\\Administrator\\Desktop\\KNN\\datingTestSet2.txt")
KNN分类
使用算法：通过可以输入一些特征数据，逐项调用上面的function，以判断对方是否为自己喜欢的类型。
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 filer miles earned per year?"))
iceCream = float(input("liters of ice cream consumed per year?"))
return_mat, class_labels = convert_text_into_arry("C:\\Users\\Administrator\\Desktop\\KNN\\datingTestSet2.txt")
normDataSet, ranges, minVals = autoNorm(return_mat)
inArr = np.array([ffMiles, percentTats, iceCream])
classifierResult = classify0((inArr-minVals)/ranges, normDataSet, class_labels, 3)
print("You will probably like this person: ", resultList[classifierResult - 1])
classifyPerson()
网友评论