data mining-基于实例的学习

在基于实例的学习中，训练样本被完全保存起来，并且使用距离函数带来判定训练集中的哪个实例与一个未知的测试实例最近。

距离函数

选择欧几里得距离，因为更高的指数距离增加了大差异的影响力而削弱了小差异的影响力，欧几里得距离是一个折中的方法。
注意：通常要使用min-max方法对属性进行归一化处理。

高效的寻找最近邻

基于实例的学习方法很简单而且有效，但速度慢，传统的只需要计算测试点与实例点的各个距离，筛选出最近的即可，但遍历大量数据需要花费大量时间。
一种更加有效的方法是使用树结构kD树。它用一个超平面将输入实例空间分隔开，再将每一个部分递归的进行分裂。在二维空间里，所有的分裂都与轴平行或垂直，具体的原理类似分支限界法的剪枝原理。

基于实例的学习方法的讨论

首先原理简单、效果好，但由于数据库很容易受干扰样本的破坏，可以使用k最近邻法，让k个最近邻根据少数服从多数的原则投票测试样例属于哪个类别。
当样本数量非常少时，最近邻法效果很差。当样本数量无穷大和投票实例k无穷大时，最近邻法理论上误差概率达到最小。
注意：kD树对于实例空间的纬度很大时，其效率变得非常低，当属性很小（最高为10），才有应用价值。球树是最近研究的通用结构