一、什么是K近邻?

K近邻是一种基本的分类和回归方法。
在分类时,对新的实例,根据其K个最近邻的训练实例的类别,通过多数表决权等方式预测其类别。
通俗的讲,找K个和其关系最近的邻居,哪个类别的邻居多,就把它划分到哪一类 特性:
(1)多分类
(2)判别模型
(3)三个基本要素:K值选择、距离度量、分类决策规则
(4)K=1时,称为最近邻算法

二、K近邻模型

1、模型:K近邻法的模型对应特征空间的一个划分,每一个划分对应一个类别

2、距离度量:
(1)通常使用欧氏距离
(2)更一般的Lp距离 3、K值选择:
(1)K值过小:整体模型复杂,容易过拟合 —— 只有最近的几个点起到作用,可能是噪声
(2)K值过大:整体模型简单 —— 距离过远(不相似)的点也会起到预测作用
(3)选择方法:在实际应用中,通常选择一个比较小的数值。通常采用交叉验证的方式选择最优的K值
(4)具体怎么选呢???—— 待补充 4、分类决策规则:多数表决权
损失函数:0-1函数
误分类率:1-正确分类率
误分类率最小(经验风险最小)——> 正确分类率最大
什么样的正确分类率最大? —— 分到多数堆里....

三、K近邻法的实现:kd树

K近邻法实现考虑的一个重要问题:如何对训练数据进行快速K近邻搜索?

简单实现:线性扫描,计算输入实例与每个训练实例的距离。

kd树:
(1)二叉树
(2)每个结点对应于K维空间划分中的一个超矩形区域
(3)快速搜索,省去对大部分数据点的搜索减少搜索的工作量
05-11 20:26