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