大数据挖掘技术：KNN分类方法

1.回归分类方法

回归分类法指利用数据统计原理，对大量统计数据进行数学处理，并确定因变量与某些自变量的相关关系，建立一个相关性较好的回归方程（函数表达式）并加以外推，用于预测今后因变量的变化的分析方法。根据因变量和自变量的个数分为一元回归分析和多元回归分析；根据因变量和自变量的函数表达式分为线性回归分析和非线性回归分析。

回归分析法主要解决的问题：确定变量之间是否存在相关关系，若存在，则找出数学表达式。根据一个或几个变量的值，预测或控制另一个或几个变量的值，且要估计这种控制或预测可以达到何种精确度。

回归分析法的步骤如下：根据自变量与因变量的现有数据以及关系，初步设定回归方程；求出合理的回归系数；进行相关性检验，确定相关系数；在符合相关性要求后，即可将已得的回归方程与具体条件相结合，来确定事物的未来状况，并计算预测值的置信区间。

有效性和注意事项：第一，有效性。用回归分析法进行预测，首先要对各个自变量做出预测。若各个自变量可以由人工控制或易于预测，而且回归方程也较为符合实际，则应用回归预测是有效的，否则就很难应用。第二，注意事项。首先，为使回归方程较能符合实际，首先应尽可能地定性判断自变量的可能种类和个数，并在观察事物发展规律的基础上定性判断回归方程的可能类型。其次，力求掌握较充分的高质量统计数据，再运用统计方法，利用数学工具和相关软件从定量方面计算或改进定性判断。

2.支持向量机

支持向量机（Support Vector Machines，SVM）是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机。SVM还包括核技巧，这使它成为实质上的非线性分类器。SVM的学习策略就是间隔最大化，可形式化为一个求解凸二次规划的问题，也等价于正则化的合页损失函数的最小化问题。SVM的学习算法就是求解凸二次规划的最优化算法。

支持向量机是一类按监督学习（Supervised Learning）方式对数据进行二元分类的广义线性分类器（Generalized Linear Classifier），其决策边界是对学习样本求解的最大边距超平面（Maximum-margin Hyperplane）。

Svm使用铰链损失函数（Hinge Loss）计算经验风险（Empirical Risk），并在求解系统中加入了正则化项以优化结构风险（Structural Risk），是一个具有稀疏性和稳健性的分类器。Svm可以通过核方法（Kernel Method）进行非线性分类，是常见的核学习（Kernel Learning）方法之一。

稳健性与稀疏性：SVM的优化问题同时考虑了经验风险和结构风险最小化，因此具有稳定性。从几何观点，SVM的稳定性体现在其构建超平面决策边界时要求边距最大，因此间隔边界之间有充裕的空间包容测试样本。SVM使用铰链损失函数作为代理损失，铰链损失函数的取值特点使SVM具有稀疏性，即其决策边界仅由支持向量决定，其余的样本点不参与经验风险最小化。在使用核方法的非线性学习中，SVM的稳健性和稀疏性在确保了可靠求解结果的同时降低了核矩阵的计算量和内存开销。

与其他线性分类器的关系：SVM是一个广义线性分类器，通过在SVM的算法框架下修改损失函数和优化问题可以得到其他类型的线性分类器。例如，将SVM的损失函数替换为logistic损失函数就得到了接近于logistic回归的优化问题。SVM和logistic回归是功能相近的分类器，二者的区别在于logistic回归的输出具有概率意义，也容易扩展至多分类问题，而SVM的稀疏性和稳定性使其具有良好的泛化能力并在使用核方法时计算量更小。

作为核方法的性质：SVM不是唯一可以使用核技巧的机器学习算法，logistic回归、岭回归和线性判别分析（Linear Discriminant Analysis，LDA）也可通过核方法得到核logistic回归（Kernel Logistic Regression）、核岭回归（Kernel Ridge Regression）和核线性判别分析（Kernelized LDA，KLDA）方法。因此SVM是广义上核学习的实现方法之一。

非线性SVM算法原理：对于输入空间中的非线性分类问题，可以通过非线性变换将它转化为某个维特征空间中的线性分类问题，在高维特征空间中学习线性支持向量机。由于在线性支持向量机学习的对偶问题里，目标函数和分类决策函数都只涉及实例和实例之间的内积，所以不需要显式地指定非线性变换，而是用核函数替换当中的内积。核函数表示通过一个非线性转换后的两个实例间的内积。

3.KNN

邻近算法，或者说K最近邻（K-Nearest Neighbor，KNN）分类算法是数据挖掘分类技术中最简单的方法之一。所谓K最近邻，就是K个最近的邻居的意思，说的是每个样本都可以用它最接近的K个邻居来代表。Cover和Hart在1968年提出了最初的邻近算法。KNN是一种分类（Classification）算法，它输入基于实例的学习（Instance-based Learning），属于懒惰学习（Lazy Learning），即KNN没有显式的学习过程，也就是说没有训练阶段，数据集事先已有了分类和特征值，待收到新样本后直接进行处理，其与急切学习（Eager Learning）相对应。

KNN是通过测量不同特征值之间的距离进行分类。思路是如果一个样本在特征空间中的k个最邻近的样本中的大多数属于某一个类别，则该样本也划分为这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。(www.chuimin.cn)

KNN使用的模型实际上对应于对特征空间的划分。K值的选择、分类和距离度量决策规则是该算法的三个基本要素：

第一，K值的选择会对算法的结果产生重大影响。K值较小意味着只有与输入实例较近的训练实例才会对预测结果起作用，但容易发生过拟合。如果K值较大，优点是可以减少学习的估计误差，但缺点是学习的近似误差增大，这时与输入实例较远的训练实例也会对预测起作用，使预测发生错误。在实际应用中，K值一般选择一个较小的数值，通常采用交叉验证的方法来选择最优的K值。随着训练实例数目趋向于无穷和K=1时，误差率不会超过贝叶斯误差率的2倍。如果K也趋向于无穷，则误差率趋向于贝叶斯误差率。

第二，该算法中的分类决策规则往往是多数表决，即由输入实例的K个最临近的训练实例中的多数类决定输入实例的类别。

第三，距离度量一般采用Lp距离，当p=2时，即为欧氏距离，在度量之前，应该将每个属性的值规范化，这样有助于防止具有较大初始值域的属性比具有较小初始值域的属性的权重过大。

KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的K个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值（Weight），如权值与距离成反比。该算法在分类时有个主要的不足：当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。可以采用权值的方法（和该样本距离小的邻居权值大）来改进。

KNN方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。

实现KNN时，主要考虑的问题是如何对训练数据进行快速K近邻搜索，这在特征空间维数大及训练数据容量大时非常必要。

4.神经网络分类方法

人工神经网络是基于对人脑组织结构、活动机制的初步认识提出的一种新型信息处理体系。它实际上是一个由大量简单元件相互连接而成的复杂网络，具有高度的非线性，能够进行复杂的逻辑操作和非线性关系实现的系统。通过模仿脑神经系统的组织结构以及某些活动机理，人工神经网络可呈现出人脑的许多特征，并具有人脑的一些基本功能。利用这一特性，可以设计出具有类似大脑某些功能的智能系统来处理各种信息，解决不同问题。下面对几种具体的神经网络进行介绍：

（1）感知器网络。感知器是由美国学者Rosenblatt在1957年首次提出的，感知器可谓是最早的人工神经网络。感知器具有分层结构，信息从输入层进入网络，逐层向前传递到输出层。感知器是神经网络用来进行模式识别的一种最简单模型，属于前向神经网络类型。单层感知器是指只有一层处理单元的感知器，它的结构与功能都非常简单，通过读网络权值的训练，可以使感知器对一组输入矢量的响应达到元素为0或1的目标输出，从而实现对输入矢量分类的目的。目前在解决实际问题时很少被采用，但由于它在神经网络研究中具有重要意义，是研究其他网络的基础，而且较易学习和理解，因此适合作为学习神经网络的起点。多层感知器是对单层感知器的推广，它能够成功解决单层感知器所不能解决的非线性可分问题，在输入层与输出层之间引入隐层作为输入模式的“内部表示”，即可将单层感知器变成多层感知器。

（2）线性神经网络。线性神经网络类似于感知器，但是线性神经网络的激活函数是线性的，而不是硬限转移函数。因此线性神经网络的输出可以是任意值，而感知器的输出不是0就是1。线性神经网络最早的典型代表是在1963年由美国斯坦福大学教授Berhard Windrow提出的自适应线性元件网络，它是一个由输入层和输出层构成的单层前馈性网络。自适应线性神经网络的学习算法比感知器的学习算法的收敛速度和精度都有较大的提高，自适应线性神经网络主要用于函数逼近、信号预测、系统辨识、模式识别和控制等领域。

（3）BP神经网络。BP神经网络是1986年由以Rumelhart和McCelland为首的科学家小组提出的，是一种按误差逆传播算法训练的多层前馈网络。在人工神经网络的实际应用中，80%～90%的人工神经网络模型采用BP网络或者它的变化形式。它也是前向网络的核心部分，体现了人工神经网络最精华的部分。BP神经网络由信息的正向传播和误差的反向传播两个过程组成。输入层各神经元负责接收来自外界的输入信息，并传递给中间层各神经元；中间层是内部信息处理层，负责信息变换，根据信息变化能力的需求，中间层可以设计为单隐层或者多隐层结构；最后一个隐层传递到输出层各神经元的信息，经过进一步处理后完成一次学习的正向传播处理过程，由输出层向外界输出信息处理结果。当实际输出与期望输出不符时，进入误差的反向传播阶段。误差通过输出层，按误差梯度下降的方式修正各层权值，向隐层、输入层逐层反传。周而复始的信息正向传播和误差反向传播过程，是各层权值不断调整的过程，也是神经网络学习训练过程，此过程一直进行到网络输出的误差减少到可以接受的程度，或者达到预先设定的学习次数为止。BP网络主要应用于以下方面：函数逼近，用输入矢量和相应的输出矢量训练一个网络逼近一个函数；模式识别，用一个特定的输出矢量将它与输入矢量联系起来；分类，对输入矢量以所定义的合适的方式进行分类；数据压缩，减少输出矢量维数以便于传输或存储。

（4）反馈神经网络。美国加州理工学院物理学家J.J.Hopfield教授于1982年发表了对神经网络发展颇具影响的论文，提出一种单层反馈神经网络，后来人们将这种反馈网络称作Hopfield网。在多输入/多输出的动态系统中，控制对象特性复杂，传统方法难以描述复杂的系统。为控制对象建立模型可以减少直接进行实验带来的负面影响，所以模型显得尤为重要。但是，前馈神经网络从结构上说属于一种静态网络，其输入、输出向量之间是简单的非线性函数映射关系。实际应用中系统过程大多是动态的，前馈神经网络辨识就暴露出明显的不足，用前馈神经网络只是非线性对应网络，无反馈记忆环节，因此，利用反馈神经网络的动态特性就可以克服前馈神经网络的缺点，使神经网络更加接近系统的实际过程。

（5）径向基神经网络。径向基RBF网络是一个三层的网络，除了输入、输出层之外仅有一个隐层。隐层中的转换函数是局部响应的高斯函数，而其他前向网络、转换函数一般都是全局响应函数。由于这样的差异，要实现同样的功能，RBF需要更多的神经元，这就是RBF网络不能取代标准前向型网络的原因。但是RBF网络的训练时间更短，它对函数的逼近是最优的，可以以任意精度逼近任意连续函数。隐层中的神经元越多，逼近越精确。径向基网络的应用：用于曲线拟合的RBF网络；径向基网络实现非线性函数回归。

（6）自组织神经网络。自组织竞争型神经网络是一种无教师监督学习，具有自组织功能的神经网络。网络通过自身的训练，能自动对输入模式进行分类，一般由输入层和竞争层构成。两层之间各神经元实现双向连接，而且网络没有隐含层。有时竞争层之间还存在着横向连接。常用的自组织网络有以下几种：自组织特征映射网络、学习矢量量化网络、自适应共振理论模型、对偶传播网络。