kNN一句话概述

kNN算法：测量不同特征值之间的距离进行分类

举个栗子：电影类型分类

一、问题

• 问题描述：已知 6 部电影的打斗镜头、接吻镜头和电影类型，以及新电影的打斗镜头、接吻镜头，预测新电影类型。

• 数学表达：已知 6 个样本的特征向量 ( x⁽¹⁾, x⁽²⁾ ) 和类型（标记），以及新样本的特征向量，预测新样本类型。

• 数学符号：
  m 部电影 —— m 个样本

  n 个特征向量 ( X⁽¹⁾, X⁽²⁾, ... , X⁽ⁿ⁾) —— ( 打斗镜头、接吻镜头、... )

  第 i 个样本的特征向量为 ( x _i⁽¹⁾, x _i⁽²⁾, ... , x _i⁽ⁿ⁾ )

  m 个样本的特征向量为
  ( x ₁⁽¹⁾, x ₁⁽²⁾, ... , x ₁⁽ⁿ⁾
  x ₂⁽¹⁾, x ₂⁽²⁾, ... , x ₂⁽ⁿ⁾
  ... , ... , ... , ...
  x _m⁽¹⁾, x _m⁽²⁾, ... , x _m⁽ⁿ⁾ )

  预测值 ( 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