K近邻算法算法介绍：K最近邻(k-Nearest neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。

该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。

KNN算法中，所选择的邻居都是已经正确分类的对象。

该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。

由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。

KNN算法不仅可以用于分类，还可以用于回归。

通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。

更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。

该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。

该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。

无论怎样，数量并不能影响运行结果。

可以采用权值的方法（和该样本距离小的邻居权值大）来改进。

该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。

目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。

该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。

近邻方法是在一组历史数据记录中寻找一个或者若干个与当前记录最相似的历史纪录的已知特征值来预测当前记录的未知或遗失特征值。

近邻方法是数据挖掘分类算法中比较常用的一种方法。

K 近邻算法（简称KNN）是基于统计的分类方法。

KNN 分类算法根据待识样本在特征空间中K 个最近邻样本中的多数样本的类别来进行分类，因此具有直观、无需先验统计知识、无师学习等特点，从而成为非参数分类的一种重要方法。

大多数分类方法是基于向量空间模型的。

当前在分类方法中，对任意两个向量：x =（x1, x 2,…,x n）与x’=(x1’,x2 ’,…x n’)存在3 种最通用的距离度量：欧氏距离、余弦和内积。

有两种常用的分类策略：一种是计算待分类向量到所有训练集中的向量间的距离：如K 近邻选择K 个距离最小的向量然后进行综合，以决定其类别。

另一种是用训练集中的向量构成类别向量，仅计算待分类向量到所有 3 类别向量的距离，选择一个距离最小的类别向量决定类别的归属。

很明显，距离计算在分类中起关键作用。

由于以上 3 种距离度量不涉及向量的特征之间的关系，这使得距离的计算不精确，从而影响分类的效果。

下面分 3 种情况说明：①无用特征的影响：在分类算法的向量空间模型中，向量常常是多维的。

所谓无用特征是指与类别无关的特征。

也就是各个类别中均可以出现的特征，它不代表类别的特点,必须要进行删除，否则他们将会导致距离的计算不准确，即向量间的距离远近将被无关特征的出现所影响。

②特征间关系的影响：我们认为如果不考虑特征间的关系，距离的计算同样会存在问题。

例如在文本分类中，可分两种情况说明：一种是同义词的影响，另一种是具有某种语义关联词的影响。

③特征间地位不平等性的影响：特征对类别支持作用大小尽管可用权值大小来体现，但我们觉得还不够。

存在一些特征对类别具有较强的支持作用（决策特征），它们的存在可以在很大程度上决定类别的归属。

而在向量空间模型中，这种决策作用将被众多非决策特征的影响所淹没掉。

其次对于K近邻算法中，选取不同的K值对分类结果有较大的影响，也就是说，不同的K值直接决定分类结果的正确率。

如图 1.1 所示：图 1.1 K 值对分类的影响其中具有空心方格和实心圆圈两类数据，待测数据点（问号代表）如果采用1近邻则其所属类别应该是如图所示的属于方格类，如果采用 3 近邻则属于圆圈类。

所以说，采用怎样的K 近邻个数是分类结果正确与否的关键条件之一。

最后查找近邻的效率问题也是值得研究的一项内容。

K 近邻分类算法需要进行全局搜索，计算的时间复杂度大，速度慢。

当训练集数据量非常大时，寻找近邻就需要相应的提高效率算法，使得查找速度提高。

目前已有的一些快速K 近邻分类算法，尽管在提高快速性方面作了一些改进，但是有的需要事先进行大量复杂的训练并且存在着收敛性问题，有的同样需要进行全局搜索并且对搜索顺序有较强的敏感性。

分类算法中，KNN 算法是实现简单、分类效果较好的一种方法。

分类模式挖掘技术作为数据挖掘的重要分支将对电信、银行、保险、零售、医疗等诸多行业提供决策支持，对未来商业和人们的生活也将产生深远的影响。

数据分类（Data Classification）是数据挖掘中一项非常重要的任务，目前在商业上应用最多。

分类的目的是学会一个分类函数或者分类模型（也常常称为分类器），该模型能把数据库中的数据项映射到给定类别中的某一个。

例如：可以建立一个分类模型，对银行贷款的安全或风险进行分类。

许多分类的方法已被机器学习、专家系统、统计学和神经生物学方面的研究者提出。

数据分类实际上就是从数据库对象中发现共性，并将数据对象分成不同类别的一个过程，可分成两步进行（图 2.1）。

第一步，建立一个模型，描述预定的数据类集或概念集。

通过分析由属性描述的数据元组来构造模型。

假定每个元组属于一个预定义的类，有一个类标号属性（Class Label Attribute）的属性确定。

对于分类，数据元组也称为样本、实例或者对象。

为建立模型而被分析的数据元组形成训练数据集（Training Set）。

训练数据集中的单个元组称为训练样本，并随机的从样本集中选取。

由于预先知道每个训练样本的类标号，这个建立模型的学习过程属于有指导的学习，即模型的学习是在知道每个训练样本属于哪个类的指导下进行的。

这不同于无指导的学习（如聚类），无指导的学习中每个训练样本的类标号事先是未知的，要学习的类集合或者数量也是事先不知道，整个学习的过程是在无指导的情况下进行的。

通常，通过第一步的学习建立的模型用分类规则、决策树或数据公式的形式表示。

如给定一个顾客信用信息的数据库，通过分类算法学习得出分类规则，根据这些规则，决定顾客的信誉好坏。

即这些规则就是分类模型，可以利用这个模型对其他数据样本进行分类，同时也能对数据库的内容提供更好的理解。

图 2.1（a）表示一种学习过程：在训练数据上用分类算法学习，学习模型用分类规则的形式表示。

图2.1（a）学习过程图 2.1（b）分类过程第二步图 2.1（b）表示一种分类过程：在测试数据上评估分类规则的准确率，如果准确率可以接受，则分类规则可用于新的数据的分类。

首先要评估模型的预测准确率。

最常用的一种方法是保持（Hold Out）方法，该方法使用类标号样本测试集，这些样本随机选取，并独立于训练样本集，即测试样本集完全不同于训练样本集。

模型在测试样本集上的准确率是指被模型正确分类的测试样本的百分比。

对于每个测试样本，按照分类模型学习得出的预测类别与已知的类别标号进行比较，如果相同，则表示分类成功；不相同，表示分类不成功。

使用完全不同于训练样本集的测试样本集，是因为学习模型倾向于过分适合数据，即学习模型可能并入训练数据中某些特别的异常数据，而这些异常不出现在总体样本集中。

如果仍使用训练数据评估分类模型，则可能评估总是乐观的。

如果认为模型的准确率可以接受，就可以利用该模型对类标号未知的数据元组或对象进行分类。

如在通过分析现有顾客数据学习得到的分类规则可以预测新的顾客信誉的好坏。

分类算法具有广泛的应用，包括信誉证实、学习用户兴趣、性能预测、市场调查、新闻分发、邮件分类以及医疗诊断等。

目前，有多种分类方法和算法，主要有统计方法、机器学习方法、神经网络方法等。

分类算法一般分为Lazy 和Eager 两种类型。

Lazy 学习算法思想是从局部出发，推迟对训练例子的归纳过程，直到一个新的测试例子出现，例如K 近邻（K Nearest Neighbor）算法、局部加权回归（Locally Weighted Regression）、基于案例的推理（Case-based Reasoning）等；而Eager 学习算法则是从全局出发，在新的测试例子出现之前，由训练例子总结归纳出相似判断的目标函数，这个目标函数应用于训练数据和测试数据，例如决策树（Decision Tree）、BP （Back-Propagation）神经网络算法、径向基函数（Radial Basis Functions）、遗传分类方法、粗糙集分类方法等。

归纳学习旨在从大量的经验数据中归纳和提取一般的判定规则和模式，它是机器学习最核心、最成熟的分支。

以Quinlan 在1986 年提出的ID3 为代表决策树归纳学习算法，它是一种基于信息增益的典型自上而下的决策树归纳方法。

以决策树为知识表达形式，具有描述简单、分类速度快、计算量小的特点，能归纳出一种较“好”的决策树，且适用于大规模数据集的学习问题。

模糊ID3 算法（Fuzzy-ID3）是传统ID3 算法在模糊环境下的一种推广，这种算法能处理与人的思维和感觉相关的不确定性，因而应用更为广泛。

模糊ID3 算法的核心是使用模糊信息熵来选择扩展属性，根据所选的属性来分割决策树中当前节点的数据，从而生成一棵决策树。

模糊决策树产生过程包括以下几个步骤：①训练数据的模糊化。

将数据集按一定比例分成训练集和测试集，模糊化过程使用所有训练例子，根据迭代自组织的模糊聚类算法产生全局中心，并由此中心模糊化所有训练例子及测试例子。

②ID3 算法是在模糊化后的所有训练例子的基础上进行。

决策树的建立过程如下：对每一属性计算信息增益，用具有最大信息增益的属性来扩展根节点。

删除节点的空分支，对节点的每一非空分支计算属于这一分支的所有对象分到每一类的真实水平S。

若分到某一类的真实水平超过阈值β，则终止这一分支作为一个叶子（标记为当前类）。

否则考察另一个属性是否能继续分割这个分支并进一步增加信息增益。

如果能，则选择具有最大信息增益的属性作为决策节点，如果不能，则终止这一分支作为一个叶子。

在叶子节点，所有的对象以最高的真实水平属于同一类。

对于每一新生成的决策节点重复第 2 步，直到不能向下扩展。

决策树建立完成。

③将决策树转化为一组规则，其中每条规则是从根节点出发到叶子节点的一条路径。