K最近邻算法在分类和预测中的应用
5星 · 超过95%的资源 需积分: 12 29 浏览量
2012-06-01
09:53:38
上传
评论 1
收藏 130KB PDF 举报 
第一讲
k-最近邻算法在分类和预测中的应用
1 k-最近邻分类
在 k-最近邻算法背后的思想是建立一种对函数形式没有假设的分类方法， 方程
，把因变量（或回应） 和自变量 联系起来。我们所做的唯
一的假设是，认为它是一个光滑的函数。这是一个非参数的方法，因为它不涉及在一个假设
了函数形式的方程中进行参数估计，这和我们在线性回归中碰到的线性假设和系数求解完全
不同。
),...,,(
21 p
xxxfy =
y
p
xxx ,...,
21
我们的训练数据中，每个观测点（observation）都含有 y 值，这个值刚好是该观测点的
类别。例如，如果我们有两个类，那么 是一个二元的变量。k-最近相邻的方法是在训练数
据集中动态的确定和一个新的观测点相近的 k 个观测点，比如，对于点 ，我
们希望用 k 个观测点去把一个特定的观测点分到某一类 中。如果我们知道函数 ，那就简
单地计算 。如果我们所有的假设是： 是一个光滑函数，那么一个合理
的想法就是在观测点集中寻找和它（根据自变量）相近的观测点，并从 值计算出 。这是
一个类似于插值的思想，如同我们常用的正态分布表。当我们谈到邻居时，通常隐含着我们
能够计算观测点间的距离或相异的度量，这些度量能够根据自变量得出。目前，我们局限于
最常见的距离度量方法中：欧几里德距离。点 和 之间的欧式距离
为：
y
),...,,(
21 p
uuu
^
v
f
),...,,(
21
^
p
uuufv =
f
y
^
v
),...,(
21 p
xxx ),...,(
21 p
uuu
22
22
2
11
)(...)()(
pp
uxuxux −++−+−
当讨论聚类方法的时候，我们会考虑在预测变量空间中点的距离的其它定义。
最简单的情况是当 k=1 的情况，这时我们发现观测点就是最近的（最近邻），并且 ，
这里 是最近邻的观测点的类别。一个显著的事实是：这是简单的、直观的、有力的分类想
法，尤其当我们的训练集中观测点的数目很大的时候。可以证明 1-NN 的误分的概率不劣于
我们知道每个类的精确的概率密度函数时误分概率的 2 倍。换句话说，如果有大量的数据及
充分复杂的分类规则，我们最多能减少划分错误到用简单的 1-NN 规则时的一半。
yv =
^
y
下面我们延伸 1-NN 的想法为 k-NN。首先，发现最近 k 邻居然后用大量的决策规则去
分类一个新的观测点。由于在训练数据中存在噪声，高一点的 k 值的优点是提供平滑的分类，
以便减少过拟和的风险。在典型的应用中，k 是几个或十几个单元，而不是成百上千。注意
到如果 k=n，在整个观测数据训练集中的数据数目，我们仅仅预测在训练数据集中大多数训
练数据的所属类别，而不管 的值如何。这显然是一个过平滑的例子，除非根本
就没有关于因变量的自变量的信息。
),...,(
21 p
uuu
1
angelaxiaohan
- 粉丝: 1
- 资源: 4
- 1
- 2
前往页