|
k-邻近算法是基于实例的学习方法中最基本的，先介绍基于实例的相关概念。 一、基于实例的学习 基于实例的算法常常用来对决策问题建立模型，这样的模型常常先选取一批样本，然后根据某些近似性把新数据与样本数据进行比较。通过这种方式来寻找最佳的匹配。因此，基于实例的算法常常也被称为“赢家通吃”学习或者“基于记忆的学习”。常见的算法包括k-Nearest Neighbor（KNN），学习矢量量化（Learning VectorQuantization，LVQ），以及自组织映射算法（Self – Organizing Map，SOM）。 1.已知一系列的训练样本，很多学习方法为目标函数建立起明确的一般化描述；但与此不同，基于实例的学习方法只是简单地把训练样本存储起来。这些实例中泛化的工作被推迟到必须分类新的实例时。每当分类器遇到一个新的查询实例，它分析这个新实例与以前存储的实例的关系，并据此把一个目标函数值赋给新实例。 2.基于实例的方法可以为不同的待分类查询实例建立不同的目标函数逼近。事实上，很多技术只建立目标函数的局部逼近，将其应用于与新查询实例邻近的实例，而从不建立在整个实例空间上表现良好的逼近。当目标函数很复杂，但它可用不太复杂的局部逼近描述时，这样做有显著的优势。 3.基于实例方法的不足： （1）分类新实例的开销可能很大。这是因为几乎所有的计算都发生在分类时，而不是第一次遇到训练样本时。所以，如何有效地索引训练样本，以减少查询时所需计算是一个重要的实践问题。 （2）当从存储器中检索相似的训练样本时，它们一般考虑实例的所有属性。如果目标概念仅依赖于很多属性中的几个时，那么真正最“相似”的实例之间很可能相距甚远。 二、k-邻近算法 k-邻近算法概述 k-邻近算法采用测量不同特征之间的距离方法进行分类。 优点：精度高、对异常值不敏感、无数据输入假定。 缺点：计算复杂度高、空间复杂度高。 适用数据范围：数值型和标称型。 k-邻近算法的工作原理是：存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一个数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最邻近）的分类标签。一般来说，我们只选择样本集中前k个最相似的数据，这就是k-邻近算法中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。 如上图所示，有两类不同的样本数据，分别用蓝色的小正方形和红色小三角形表示，而图正中间的哪个绿色的圆所标示的数据是待分类的数据。 如果k=3，绿色圆点的最近的3个邻居是2个红色三角形和1个蓝色小正方形，少数服从多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。 如果k=5，绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色小正方形，少数服从多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。 于此我们看到，当无法判定当前待分类点是从属于已知分类中的哪一类时，我们可以依据统计学的理论看它所处的位置特征，衡量它周围邻居的权重，而把它归为（或分配）到权重更大的哪一类。这就是k-邻近算法的核心思想。 除了定义距离的问题外，还有一个选择多少个邻居，即k值定义为多大的问题。不要小看这个k值选择问题，因为它对k-邻近算法的结果会产生重大影响。 （1）如果选择较小的k值，就相当于用较小的领域中的训练实例进行预测，“学习”近似误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是“学习”的估计误差会增大，换句话说，k值的减小就意味着整体模型变得复杂，容易发生过拟合。 （2）如果选择较大的k值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少学习的估计误差，但缺点是学习的近似误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且k值的增大就意味着整体的模型变得简单。 （3）k=N，则完全不足取，因为此时无论输入实例是什么，都只是简单的预测它属于在训练实例中最多的类，模型过于简单，忽略了训练实例中大量有用的信息。 实际应用中，k值一般取一个比较小的数值，例如采用交叉验证法（简单来说，就是一部分样本做训练集，一部分做测试集）来选择最优的k值。 k-邻近算法的一般流程 （1）收集数据：可以使用任何方法（如：提供文本文件）。 （2）准备数据：距离计算所需要的数值，最好是结构化的数据格式（如：使用程序语言解析文本文件，将待处理数据的格式改变为分类器可以接受的格式：训练样本矩阵和类标签向量。）。 （3）分析数据：可以使用任何方法（如：使用程序语言绘制二维散点图，一般来说，我们会采用色彩或其他的记号来标记不同样本分类，以便更好地理解数据信息。）。 （4）训练算法：此步骤不适用于k-邻近算法。 （5）测试算法：计算错误率（如：使用部分数据作为测试样本。测试样本和非测试样本的区别在于：测试样本是已经完成分类的数据，如果预测分类与实际分类不同，则标记为一个错误。）。 （6）使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-邻近算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。 k-邻近算法的伪代码 对未知类别属性的数据集中的每个点依次执行以下操作： （1）计算已知类别数据集中的点与当前点之间的距离； （2）按照距离递增次序排序； （3）选取与当前点距离最小的k个点； （4）确定前k个点所在类别的出现频率； （5）返回前k个点出现频率最高的类别作为当前点的预测分类。 k-邻近算法的测试 为了测试分类器的效果，我们可以使用已知答案的数据，当然答案不能告诉分类器，检验分类器给出的结果是否符合预期结果。通过大量的测试数据，我们可以得到分类器的错误率——分类器给出错误结果的次数除以测试执行的总数。错误率是常用的评估方法，主要用于评估分类器在某个数据集上的执行效果。完美分类器的错误率为0，最差分类器的错误率为1.0，在这种情况下，分类器根本就无法找到一个正确答案。 k-邻近算法的缺点 k-邻近算法是分类数据最简单有效的算法。k-邻近算法是基于实例的学习，使用算法时我们必须有接近实际数据的训练样本数据。k-邻近算法必须保存全部数据集，如果训练数据集很大，必须使用大量的存储空间。此外，由于必须对数据集中的每个数据计算距离，实际使用时可能非常耗时。 k-邻近算法的另一个缺陷是它无法给出任何数据的基础结构信息，因此我们也无法知晓平均实例样本和典型实例样本具有什么特征。我们可以使用概率测量方法处理分类问题，这种算法可以解决这个问题。 通过微信学习的知识只能是碎片化的知识，作为新时代的我们希望能够构建自己的知识结构，使我们的知识体系化，系统化，以后在遇到碎片化的知识，我们做的只是融合到自己的知识结构中，故我们将推出“与LSGO一起学”系列课程，帮助大家来构建知识框架，初步规划有：
如果对这些内容感兴趣，可以一起来学习讨论。 我们的官网： www.lsgogroup.com
|
|
|
