基本思想

通常的学习算法都是从训练样本中学到目标函数，然后把目标函数用到新样例中。K-近邻算法不同，它并没学到这样的普遍函数，只是把训练样例存起来，当来了新样例的时候，根据新样例和训练样例的关系，赋给新样例一个函数值。

它的基本思想是这样的：在和新样例最相似的k个训练样例中，最多样例属于哪个类别，新样例就属于哪个类别。

可通过下面这个图说明。图中的图形分两类，蓝色正方形和红色三角形，而那个绿色圆点的类别未知，它该属哪一类呢？如果采用3-近邻算法，绿色圆被划分到红色三角一类，因为距离它最近的三个图形中，有两个属于三角形，一个属于正方形，三角形更多。而5-近邻算法则把绿色圆归到蓝正方形一类，因为离它最近的五个图形中，蓝正方形有3个，红三角只有两个。

基本算法

    一个样例包含n个属性，它对应于n维空间Rⁿ的点。目标函数值可以是离散值，也可以是连续值。

先考虑离散值，目标函数f为：Rⁿ→V，其中V是有限集合{v1,v2,……，vs}。新新样例为x_q，从训练样例中找出距离x_q最近的k个点（点间距离可用欧式距离定义）。按K-近邻算法：

加权算法

距离不同的点赋予不同的权值，较近的点比较重要，权值大，远的点权值小。类似引力定律，权值与距离平方成反比：

维度灾难

样例间的距离是根据样例的所有属性计算的，但实际上可能有的属性与分类无关。举个例子，每个样例由20个属性描述，但这些属性中只有两个与分类有关。这两个属性值一致的样例在20维空间中可能距离会很远，用这样的距离进行分类会导致错误结果。这种情况称之为维度灾难。

解决维度灾难的一个方法是，采用近邻算法时先对每个属性乘一个加权因子，然后再对测试样例分类，根据分类误差反复调整加权因子，从而对属性的重要性得到一个合理的估算。

K-近邻算法的另一个不足是，计算主要发生在新样例进来的时候。它处理每个新样例都需要大量的计算，资源开销比较大。