文档介绍：数据挖掘十大算法
数据挖掘十大算法— K 近邻算法
k -近邻算法是基于实例的学****方法中最基本的，先介绍基于实例学****的相关概念。
一、基于实例的学****1 、已知一系列的训练样例，很多学****方法为目标函数建立起明确的一般化描述；但数据挖掘十大算法
数据挖掘十大算法— K 近邻算法
k -近邻算法是基于实例的学****方法中最基本的，先介绍基于实例学****的相关概念。
一、基于实例的学****1 、已知一系列的训练样例，很多学****方法为目标函数建立起明确的一般化描述；但与此不同，基于实例的学****方法只是简单地把训练样例存储起来。
从这些实例中泛化的工作被推迟到必须分类新的实例时。每当学****器遇到一个新的查询实例，它分析这个新实例与以前存储的实例的关系，并据此把一个目标函数值赋给新实例。 2 、基于实例的方法可以为不同的待分类查询实例建立不同的目标函数逼近。事实上，很多技术只建立目标函数的局部逼近，将其应用于与新查询实例邻近的实例，而从不建立在整个实例空间上都表现良好的逼近。当目标函数很复杂，但它可用不太复杂的局部逼近描述时，这样做有显著的优势。
3、基于实例方法的不足：
(1)分类新实例的开销可能很大。这是因为几乎所有的计算都发生在分类时，而不是在第一次遇到训练样例时。所以，如何有效地索引训练样例，以减少查询时所需计算是一个重要的实践问题。 (2 )当从存储器中检索相似的训练样例时，它们一般考虑实例的所有属性。如果目标概念仅依赖于很多属性中的几个时，那么真正最“相似”的实例之间很可能相距甚远。
二、k-近邻法基于实例的学****方法中最基本的是k -近邻算法。这个算法假定所有的实例对应于 n 维欧氏空间 ?n 中的点。一个实例的最近邻是根据标准欧氏距离定义的。更精确地讲，把任意的实例 x 表示为下面的特征向量：其中 a r
(x )表示实例x的第r个属性值。那么两个实例x i和x j间的距离定义为d (x i ,
x j ) ，其中：
说明：
1、在最近邻学****中，目标函数值可以为离散值也可以为实值。
2、我们先考虑学****以下形式的离散目标函数。其中 V 是有限集合
{v 1，... v s }。下表给出了逼近离散目标函数的 k- 近邻算法。 3、正如下表中所指出的，这个算法的返回值f' (x q )为对f (x q )的估计，它就是距离x q最近的k个训练样例中最普遍的f值。4、如果我们选择k =1，那么“1 -近邻算法”就把f (x i )赋给
(x q )，其中x i是最靠近x q的训练实例。对于较大的k值，这个算法返回前k个最靠近的训练实例中最普遍的 f 值。
逼近离散值函数f : ?n_V k的-近邻算法
下图图解了一种简单情况下的 k - 近邻算法，在这里实例是二维空间中的点，目标函数具有布尔值。正反训练样例用“ -”+分”别和表“示。图中也画出
了一
个查询点 x q 。注意在这幅图中， 1- 近邻算法把 x q 分类为正例，然而 5- 近邻算法把 x q 分类为反例。
图解说明：左图画出了一系列的正反训练样例和一个要分类的查询实例 x q 。 1-近邻算法把 x q 分类为正例，然而 5-近邻算法把 x q 分类为反例。
右图是对于一个典型的训练样例