免规则采集器列表算法(基于实例的学习方法中最基本的是k-近邻算法)

　　免规则采集器列表算法(基于实例的学习方法中最基本的是k-近邻算法)

　　k-近邻算法是最基础的基于实例的学习方法，首先介绍基于实例的学习的相关概念。

　　一、基于实例的学习。

　　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：ÂnV 的 _k-最近邻算法

　　训练算法：

　　对于每个训练示例，将此示例添加到列表 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 个最接近示例的平均值，而不是计算最常见的值。更准确地说，为了逼近一个实值目标函数

　　，我们只需要将算法中的公式替换为：

　　三、距离加权最近邻算法

　　k-最近邻算法的一个明显改进是对k个最近邻的贡献进行加权，并根据最近邻与查询点xq的距离为其分配更大的权重。

　　例如，在上表中逼近离散目标函数的算法中，我们可以根据每个邻居与xq的距离平方的倒数对每个邻居的“投票权”进行加权。

　　该方法是通过将上表算法中的公式替换为以下公式来实现的：

　　在

　　为了处理查询点 xq 与某个训练样例 xi 完全匹配，导致分母为 0 的情况，我们在这种情况下设置 f'(xq) 等于 f(xi)。如果有多个这样的训练示例，我们使用占大多数的分类。

　　我们也可以用类似的方式对实值目标函数进行加权，只要我们将上表中的公式替换为以下公式即可：

　　wi 的定义与前面的公式相同。

　　注意，这个公式中的分母是一个常数，它对不同权重的贡献进行了归一化（例如，它保证如果对于所有训练样例 xi，f(xi)=c，则 (xq)c）。

　　请注意，上述 k-最近邻算法的所有变体仅考虑 k 个最近邻来对查询点进行分类。如果使用按距离加权，实际上允许所有训练样例影响 xq 的分类是没有坏处的，因为很远的样例对 (xq) 的影响很小。考虑所有示例的唯一缺点是分类运行速度会更慢。如果在对新查询实例进行分类时考虑所有训练示例，我们称其为全局方法。如果只考虑最接近的训练示例，我们称其为本地方法。

　　四、 k-近邻算法解释

　　距离加权的k-最近邻算法是一种非常有效的归纳推理方法。它对训练数据中的噪声非常鲁棒，在给定足够大的训练集时也非常有效。注意，通过取k个最近邻的加权平均，可以消除孤立噪声样本的影响。

　　1、问题1：邻居之间的距离会被大量不相关的属性支配。

　　应用k-最近邻算法的一个实际问题是，实例之间的距离是根据实例的所有属性（即收录该实例的欧几里得空间的所有坐标轴）计算的。这与仅选择所有实例属性的子集的方法不同，例如决策树学习系统。

　　例如，这样一个问题：每个实例由 20 个属性描述，但其中只有 2 个属性与其分类相关。在这种情况下，这两个相关属性值相同的实例在这个20维的实例空间中可能相距很远。因此，依赖这 20 个属性的相似性度量会误导 k-近邻算法的分类。邻居之间的距离会被大量不相关的属性所支配。由于存在许多不相关的属性而导致的这个问题有时被称为维度灾难（curse of Dimensionity）。最近邻法对这个问题特别敏感。

　　2、解决方案：计算两个实例之间的距离时对每个属性进行加权。

　　这相当于在欧几里德空间中缩放坐标轴，缩短相关性较低的属性对应的坐标轴，延长相关性较高的属性对应的坐标轴。每个坐标轴应该拉伸的量可以通过交叉验证的方法自动确定。

　　3、问题2：应用k-最近邻算法的另一个实际问题是如何建立一个高效的索引。由于此算法将所有处理推迟到接收到新查询之前，因此处理每个新查询可能需要进行大量计算。

　　4、 解决方案：目前已经开发了很多方法来索引存储的训练示例，以便在存储开销有一定增加的情况下更有效地确定最近邻。一种索引方法是kd-tree（Bentley 1975; Friedman et al. 1977），它将实例存储在树的叶节点中，相邻的实例存储在相同或附近的节点中。通过来测试所选的新查询 xq 的属性，树的内部节点将查询 xq 排列到相关的叶节点。

　　机器学习与数据挖掘-K最近邻（KNN）算法实现（java和python版）