简述k近邻算法,k最近邻分类算法特点
K-邻域算法是基于案例学习的最基本的方法。首先，介绍了基于案例学习的相关概念。
一、基于实例的学习。
1.给定一系列训练样本，许多学习方法建立目标函数的明确和概括的描述；但与此不同的是，基于案例的学习只存储训练样本。
当需要对新的例子进行分类时，从这些例子中得出的结论就被推迟了。每当学习器遇到新的查询实例时，它将分析新实例与先前保存的实例之间的关系，并相应地将目标函数值分配给新实例。
2.基于案例的方法可以为不同的待分类查询案例建立不同的目标函数近似。事实上，许多技术仅创建目标函数的局部近似并将其应用于与新查询实例相邻的实例，而不能在整个实例空间中创建良好的近似。当目标函数复杂时，这具有明显的优势，但它可以通过不太复杂的局部近似来描述。
3.示例方法是不够的：
(1)对新实例进行分类的成本可能很高。这不是我第一次遇到训练样本，而是因为大部分计算都发生在分类的时候。因此，如何有效地索引训练样本并减少查询所需的计算量是一个重要的实际问题。
2)从内存中检索相似训练样本时，一般会考虑实例的所有属性。如果目标的概念依赖于许多属性中的一些，那么真正“相似”的实例很可能彼此远离。
其次，基于k近邻算法的最基本的学习方法是k近邻算法。该算法假设所有实例对应于N维欧几里得空间N中的点。在一个例子中，最近邻由标准欧几里得距离定义。更准确地说，任何实例x被表示为以下特征向量：
a1(x)，a1(x)，a1(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-最近邻算法将此空间中的示例分配给训练样本所属的分类。
简单地修改前面的k-最近邻算法就可以用来逼近连续值的目标函数。为了实现这一点，该算法不计算最常见的值，而是计算最接近采样平均值的k值。更准确地说，为了逼近真实值的目标函数，只需要用下面的表达式替换算法表达式
3.与k-最近邻算法相比，距离加权最近邻算法明显提高了贡献权重
例如，近似上表中的离散目标函数的算法可以基于邻居和每平方xq之间的距离的倒数来加权邻居的“投票权”。
这种方法是通过用下面的表达式代替上面的表算法的表达式来实现的：
在…之中
为了处理查询点xq与训练样本xi完全匹配且分母为0的情况，请使f’(xq)等于f(Xi)。如果有多个这样的训练样本，我们将
使用其中最常见的分类。
我们也可以以类似的方式对实值目标函数的距离进行加权，只要上表中的公式被替换为以下公式：
wi的定义与前面公式中的定义相同。
注意，这个公式中的分母是一个常数，它归一化了不同权重的贡献(例如，它保证如果f(xi)=c对于所有训练样本xi，那么(xq)-c)。
注意，上述k-最近邻算法的所有变体仅考虑K个邻居来分类查询点。如果使用按距离加权，那么允许所有训练样本影响xq的分类实际上没有坏处，因为非常远的样本对(xq)的影响很小。考虑所有样本的唯一缺点是它会使分类运行得更慢。如果在对新的查询实例进行分类时考虑了所有的训练样本，我们称之为全局方法。如果只考虑最近的训练例子，我们称之为局部法。
四、对k-近邻算法的说明
距离加权的K-最近邻算法是一种非常有效的归纳推理方法。它对训练数据中的噪声具有鲁棒性，并且在给定足够大的训练集时也非常有效。注意，通过对k个邻居进行加权平均，可以消除孤立噪声样本的影响。
1.问题1:邻居之间的距离会被大量不相关的属性所支配。
应用k-最近邻算法的一个实际问题是根据实例的所有属性(即包含实例的欧氏空间的所有坐标轴)计算实例之间的距离。这不同于那些只选择所有实例属性的子集的方法，比如决策树学习系统。
例如，有一个问题：每个实例由20个属性描述，但这些属性中只有2个与其分类相关。在这种情况下，两个相关属性具有相同值的实例在这个20维实例空间中可能相距很远。因此，依赖于这20个属性的相似性度量会误导k-最近邻算法的分类。邻居之间的距离会被大量不相关的属性所支配。这种由许多不相关的属性引起的问题有时被称为维数灾难。最近邻法对这个问题特别敏感。
2.解决方案：在计算两个实例之间的距离时，对每个属性进行加权。
这相当于在欧氏空间中缩放坐标轴，缩短对应于不太相关的属性的坐标轴，加长对应于更相关的属性的坐标轴。每个坐标轴的延伸量可以通过交叉验证自动确定。
3.问题2:应用k-最近邻算法的另一个实际问题是如何建立高效的索引。因为该算法会延迟所有处理，直到收到新的查询，所以处理每个新的查询可能需要大量的计算。
4.解决方案：目前已经开发了很多方法对存储的训练样本进行索引，以一定的存储开销更高效地确定最近邻。一种索引方法是KD树(Bentley 1975Friedman et al. 1977)，它将实例存储在树的叶节点中，并将相邻实例存储在相同或附近的节点中。通过测试新查询xq的选定属性，树的内部节点将查询xq排列到相关的叶节点。
Python和java版本代码讲解和下载
