kNN一句话概述
kNN算法:测量不同特征值之间的距离进行分类
举个栗子:电影类型分类
一、问题
问题描述:已知 6 部电影的打斗镜头、接吻镜头和电影类型,以及新电影的打斗镜头、接吻镜头,预测新电影类型。
数学表达:已知 6 个样本的特征向量 ( x(1), x(2) ) 和类型(标记),以及新样本的特征向量,预测新样本类型。
-
数学符号:
m 部电影 —— m 个样本n 个特征向量 ( X(1), X(2), ... , X(n)) —— ( 打斗镜头、接吻镜头、... )
第 i 个样本的特征向量为 ( x i(1), x i(2), ... , x i(n) )
m 个样本的特征向量为
( x 1(1), x 1(2), ... , x 1(n)
x 2(1), x 2(2), ... , x 2(n)
... , ... , ... , ...
x m(1), x m(2), ... , x m(n) )预测值 ( Y ) —— ( 电影类型 )
如下图所示:
编号/电影名称 (m) 打斗镜头 (X(1)) 接吻镜头 (X(2)) 电影类型 (Y) 1 California Man 3 104 爱情片 2 omitted 2 100 爱情片 3 omitted 1 81 爱情片 4 omitted 101 10 动作片 5 omitted 99 5 动作片 6 omitted 88 2 动作片 7 omitted 18 90 ?
二、kNN算法步骤
1. 计算未知点与已知类别点的距离
- 欧氏距离
d= \sqrt [] { \sum_{k = 1}^{n} {(x_1^k - x_2^k)^2}}- 曼哈顿距离
d= \sqrt [] { \sum_{k = 1}^{n} {|x_1^k- x_2^k|}}- 切比雪夫距离
d= max(|x_1^1-x_2^1|,|x_1^2-x_2^2|,...,|x_1^n-x_2^n|)- 闵可夫斯基距离
d= \sqrt [p] { \sum_{k = 1}^{n} {|x_1^k - x_2^k|^p}}
p为 1 时,闵可夫斯基距离即曼哈顿距离
p为 2 时,闵可夫斯基距离即欧氏距离
p为 ∞ 时,闵可夫斯基距离即切比雪夫距离
按照欧式距离计算,样本 1 与 新电影欧式距离计算:
d = \sqrt [] { (3 - 18)^2 + (104 - 90)^2}=20.5
如图:
编号/电影名称 (m) 与新电影的距离 1 California Man 20.5 2 omitted 18.7 3 omitted 19.2 4 omitted 115.3 5 omitted 117.4 6 omitted 118.9
2. 按照距离递增次序排序
如图:
编号/电影名称 (m) 与新电影的距离 2 omitted 18.7 1 omitted 20.5 3 omitted 19.2 4 omitted 115.3 5 omitted 117.4 6 omitted 118.9
3. 选取与新电影距离最小的 k 个点
这里令 k 为 4,与新电影距离最近的 2 个点依次为第 2 个样本、第 1 个样本、第 3 个样本和第 4 个样本,其中爱情片的数量为 3,动作片的数量为 1,则爱情片出现的频率为:
p(love) = 3 / 4
动作片出现的频率为:
p(action) = 1 / 4
注:例子的样本数很小,为更好地说明问题,k值取得较大
4. 确定前k个点所在类别的出现频率
p(love) > p(action),因此爱情片出现的频率更高
5. 返回前k个点出现最高频率的类别,即预测类别
新电影的类别为爱情片
- 待更新
参考:《机器学习实战》【美】Peter Harrington