算法学习——K近邻算法

一、K近邻算法

二、K近邻模型

k近邻法使用的模型实际上对应于对特征空间的划分。模型由三个基本要素——距离度量、k值的选择和分类决策规则决定。

2.1 模型

2.2 距离度量

例题&＃xff1a;距离度量使用Lp距离进行计算。

下面给出上述计算的做法&＃xff0c;便于理解
L1&＃xff08;X1,X3&＃xff09;&＃61; 6 &＃61; 3&＃43;3
L2&＃xff08;X1,X3&＃xff09;&＃61; 4.24 &＃61; &＃xff08;3的平方&＃43;3的平方&＃xff09;开根号
L3&＃xff08;X1,X3&＃xff09;&＃61; 3.78 &＃61; &＃xff08;3的3次方&＃43;3的3次方&＃xff09;开根号3
L4&＃xff08;X1,X3&＃xff09;&＃61; 3.57 &＃61; &＃xff08;3的4次方&＃43;3的4次方&＃xff09;开根号4

2.3 K值的选择

通常采用交叉验证法选取最优的K值

2.4 分类决策规则

三、kd树

3.1 构造kd树

例题&＃xff1a;kd树构造


下面给出上述计算的做法&＃xff0c;便于理解

1. 构建根结点&＃xff0c;此时切分维度为x轴(即数据的第一维度)&＃xff0c;上述集合在x轴从小到大排序为(2,3),(4,7),(5,4),(7,2),(8,1),(9,6)&＃xff1b;中值为(7,2)&＃xff1b;(2,3),(4,7),(5,4)挂在(7,2)结点的左子树&＃xff1b;(8,1),(9,6)挂在(7,2)结点的右子树。
2. 构建(7,2)结点的左子树&＃xff0c;点集合(2,3),(4,7),(5,4)&＃xff0c;此时切分维度为y轴(即数据的第二维度)&＃xff0c;中值为(5,4)。接着按x轴切分&＃xff0c;(2,3)挂在(5,4结点)的左子树&＃xff0c;(4,7)挂在(5,4)结点的右子树。
3. 构建(7,2)结点的右子树&＃xff0c;点集合(8,1),(9,6)&＃xff0c;此时切分维度为y轴&＃xff0c;中值为(9,6)。接着按x轴切分&＃xff0c;(8,1)挂在(9,6)结点的左子树。至此k-d tree构建完成。

3.2 搜索kd树

例题&＃xff1a;搜索kd树


下面给出上述计算的做法&＃xff0c;便于理解
1.找到包含S的叶结点D&＃xff0c;因为最近邻点肯定在以S为圆心的圆内。
2.上退回D的父结点B和B的父结点F搜索最近邻。由图可知&＃xff0c;结点B中只有结点D与S最近&＃xff0c;而F与圆不相交&＃xff0c;所以不存在最近邻点。
3.上退回根结点A&＃xff0c;由图可知&＃xff0c;A与圆不相交&＃xff0c;所以不存在最近邻点。
4.向下搜索根节点A的另一个结点G。由图可知&＃xff0c;而G与圆不相交&＃xff0c;所以不存在最近邻点。
5.向下搜索结点C&＃xff0c;发现C和圆相交&＃xff0c;且相交点在圆内为实例点E。由图可知&＃xff0c;E比D距离S更近&＃xff0c;最后&＃xff0c;得到E是点S的最近邻点。

四 、K近邻的概要