篇一：机器学习总结
目录
前言................................................................................................................................. 2
Naive Bayes....................................................................................................................... 2
Linear Regression & Logistic Regression ................................................................................ 3
Bias-variance trade-off & Regularization ............................................................................... 5
SVM ................................................................................................................................. 8
Optimization ................................................................................................................... 13
EM ................................................................................................................................. 15
Mixtures of Gaussians ............................................................................................... 16
ME ................................................................................................................................. 17
HMM ............................................................................................................................. 18
MEMM ........................................................................................................................... 21
CRF ................................................................................................................................ 22
Decision Tree................................................................................................................... 23
ID3 .......................................................................................................................... 24
C4.5 ........................................................................................................................ 24
CART ....................................................................................................................... 24
Model Tree .............................................................................................................. 24
Model Combination ......................................................................................................... 26
Bagging ................................................................................................................... 27
Random Forest .................................................................................................. 28
Boosting .................................................................................................................. 28
AdaBoost .......................................................................................................... 28
Feature Selection ............................................................................................................. 29
KNN ............................................................................................................................... 29
KD Tree.................................................................................................................... 30
PCA & SVD ...................................................................................................................... 31
Collaborative filtering ....................................................................................................... 33
CF as supervised learning ........................................................................................... 34
CF as matrix factorization ........................................................................................... 35
前言
花了将近四个月时间，终于把机器学习最基本的东西大致过了一遍了，这中间还包括一个多月的时间用于复习数学了（坑爹啊），很久没有花这么大的精力学一样东西了，很高兴的是，在比较深入的去了解后，我还没有对机器学习失去兴趣?，这至少说明，这个东西是真真正正吸引我的。
这阵子杂七杂八的看了不少东西，为了避免以后全还回去了，我决定一边复习一边写个总结，把这些七七八八的东西都塞一块儿吧。
这里涵盖了绝大多数我学过的机器学习相关的东西，有一些算法可能被我略过去了，比如k-means，层次聚类，Apriori等，冠冕堂皇的原因是这些算法比较简单，相信不那么容易忘记，其实真正的原因是写到最后实在疲了，懒得继续了-_-!。
我最初对机器学习产生兴趣是源于吴军博士的《数学之美》，不能不说这本书实在是真好，反正我是结结实实的上套了，另外一个比较幸运的事情是，在我刚决定学习机器学习时，正好有一家叫“培乐园”的针对互联网高端技术的培训机构开张了，我也有幸成为了第一批学员，不得不说培乐园在机器学习方面对我的影响和《数学之美》一样巨大，正是蒋龙老师的课程让我了解了机器学习的框架，从而在后面的学习中不至于像无头苍蝇似的到处乱撞，另外，Andrew Ng和龙星计划的机器学习课程对我帮助也都非常的大，感谢这些无私分享的老师们！
最后，作为机器学习的菜鸟，我只能说，路漫漫其修远兮，努力吧！
Kejun
kjliue@gmail.com
Naive Bayes
NB是基于贝叶斯定理和条件独立性假设的分类器，贝叶斯定理简单的说就是已知条件概率p(x|y)和先验概率p(y)的情况下求p(y|x)的方法，因为有些时候计算p(x|y)和p(y)比较容易，而计算p(y|x)很困难，这时候就可以通过贝叶斯定理将困难的问题转化为简单问题解决，从另一个角度看，贝叶斯定理也可以理解为通过生成模型p(x, y)求解判别模型p(y|x)的方法，这里就必须提到条件独立性假设了，因为NB是生成模型，也就是对联合概率分布p(x,y)= p(x|y) *p(y)建模，由于x的结构一般很复杂，直接建模会很困难，因此几乎所有的生成模型都对x的结构做了一定的假设，NB做的假设是在给定y的前提下，x的各个feature是条件独立的（非常强的假设，也许这就是该分类器名字里naive的来历吧），这样就可以很容易的将p(x|y)分解为x的各个feature条件概率的乘积。
NB的模型学习采用MLE，这里有一个0概率问题，就是如果训练数据中某个(feature,y)的组合没有出现过的话，所有包含该feature的x属于类y概率会变为0，这显然不合理，一种
最简单的平滑方式是Laplace平滑（即+1平滑，分子加1，分母加上分子可能取值的个数），这样平滑后的p(feature|y)仍然是一个概率分布，或者可以引入一些先验知识，比如，采用如下的公式：(weight*assumedprob+count*prob) / count + weight，这里weight和assumedprob对应的是先验知识，而count是训练样本总数，prob是调整前的条件概率p(feathre|y)。
对条件概率p(feature|y)的估计，当feature取值为离散值时，只需要简单的统计训练样本中的频率即可，当feature取值为连续值时，有两种处理方案：1、计算给定y时feature的均值和方差，得到概率密度。2、将连续值切分为多个区间，也就是将特征离散化，这样估计方法就和离散值一样了。
NB有很多优点，训练简单，模型易于解释，不容易overfitting，在小数据集上也能工作的相当不错，缺点就是条件独立性假设似乎过强了一些，导致精度可能没有其它分类器高。 Linear Regression & Logistic Regression
Linear Regression其实就是用一条函数曲线去拟合一组数据，Regression中文翻译叫“回归”，关于这个名字，我觉得培乐园的蒋龙老师解释的非常好，数据的内在规律就像是一股力量，拉动着我们拟合的函数曲线“回归”到正确的位置。
Linear Regression的基本形式是y=wx+b，这里的Linear应该是指对w的Linear，对于x，我们可以做变换，比如添加高次feature，就可以拟合非线性的情况，因此，对于原始输入x，方程未必是线性的。
关于在Linear Regression中如何添加feature来拟合非线性情况，这就是一个很有技术含量的活儿了（至少我不懂），听说过什么feature learning啥的，以后再看吧，另外还有一种思路就是做特征离散化，我的理解就是将连续值的feature打散成许多小区间（和前面NB处理连续feature的一种思路差不多），通过这种方式，可能我们就不需要费劲的去发掘高次feature了？
Linear Regression的lost function是关于w的二次函数，通过gradient descend或者quasi newton method的lbfgs等方法可以得到全局最优解，当feature数量不是非常大时，也可以用最小二乘法求解：
这里解释下最小二乘法（不得不提下，要不最近线代就白复习了），其实，最初我们想解的是这个方程：Ax=b（这里x是前面的theta/w），但由于这个方程一般无解（一般m很大，n很小，再加上有噪声，所以无解），无解的原因是因为b不在矩阵A的列空间中，如果我们能把b映射到矩阵A的列空间中，显然这个方程就有解了，那么，怎么映射呢？在满足最小平方误差的情况下，答案显然是将b投影到A的列空间中，这样，b和投影向量的差的长度最小，自然就满足了最小平方误差（ A’ (b - Ax) = 0，也就是b减去它在A的列空间的投影应该和A的每一个列向量垂直 ）。
关于最小二乘法的另一个问题是，A’A可能不可逆，出现这个问题有两种可能，1、A的某些
，
列是完全线性相关的，2、m小于n。解决这个问题的方法是加入L2 regularization，这时求解theta的式子就变成了
一举两得，我喜欢?。
，另外还顺带解决了overfitting的问题，真是
在使用gradient descend或者quasi newton method求解w时，有几个点我想提一下：
1、 mean normalization，在训练前对每个feature的值做(x-μ) / s，这里μ是均值，s是标准
差，通过这种方式可以使各个feature的值域类似，这样lost function的等高线会更“圆”，收敛会更快。
2、 关于learning rate α，对于α的取值，太大会导致震荡，无法收敛，太小会导致收敛过
慢，因此我们需要通过多次实验来取一个合适的值，另外对于gradient descend，和quasi newton method不同的是，learning rateα不需要做动态调整，保持一个固定值即可。
3、 除了batch gradient descend外，还有一种Stochastic Gradient Descent的方法，这种方法
和batch gradient descend的区别是，每次只使用1条或者若干条样本进行训练，该方法不保证每次迭代lost function都变小，但是最终一定能收敛到全局最优值附近，非常适合大数据情况下的模型训练（属于online learning），Stochastic Gradient Descent有时候会有periodic variation，一个解决办法是动态调整α，比如设置α=4/(1.0+numIter+idxRec) + 0.01，另外一个要注意的地方就是在每轮迭代时对训练样本做随机排序。
关于Linear Regression中的参数项b，它的一个作用是，调节误差项的均值，因为对于Linear Regression来说，要求误差项是均值为0的高斯分布，这时候b就刚好可以做这个调节。
另外，估计误差项的方差时，我们采用如下的公式：，这里的p是feature个数，这也说明了，模型总是倾向于overfitting的，而且当feature越多时，越容易overfitting。
想提下的还有Locally weighted linear regression，从名字可以看出，它就是加上了权重的Linear Regression，那么权重怎么计算呢？简单的说就是，离待预测的点越近权重越大，否则越小，而且权重的衰减呈高斯分布，lost function是：，权重是：
，采用最小二乘法的计算公式是：pinv(X’WX)X’Wy（这里W是一个对角
矩阵），这应该算是一种无参数方法吧，有点像KNN，缺点就是，每来一个待预测的数据，都得重新train一个model。
这里还想记下的一个问题是，训练一个模型需要多少数据究竟是由什么因素决定的？比如，两个Linear Regression模型的参数个数一样，那它们训练需要的数据一定是一样多吗？是不是还和数据的分布有关呢？这个问题我也没想清楚，可能得等了解learning theory以后再说吧。
接下来说Logistic Regression，Logistic Regression其实就是在Linear Regression上套了一个Sigmoid function，但是这两个模型的作用就完全不一样了，Linear Regression主要用于预测连续值，用于回归问题，而Logistic Regression主要用于预测0-1值，用于分类，且输出的是概率值（属于概率模型，这点和svm不一样）。
一个有意思的事情是，log(p(y=1|x)/p(y=0|x))=wx，这个值叫做几率，解释了wx的含义。 Linear Regression的学习采用log最大似然估计，
的是，对其求导后，梯度函数
它们俩的h(x)完全不同了哦）。 ，有趣外形和Linear Regression十分相似（注意，
Bias-variance trade-off & Regularization
这应该是初学机器学习最重要的两个问题了，放在一起说吧。
当我们做模型训练时，数据一般分为training set和testing set，训练的目标有两个：
1、 模型能良好的拟合training set。
2、 模型在testing set上的表现应该和training set接近。
先上图：
结合该图可以看出，当bias较大（模型比较简单）时，模型在training set和testing set上的表现都很差，但此时两者比较接近，这就是underfitting，而当variance较大（模型比较复杂）时，模型在training set上表现很好，而在testing set上表现很差，这就是overfitting，因此，我们需要在bias和variance上做一个权衡，以期获得最好的模型，这就是cross validation的意义。
在这里模型复杂度不单单指模型本身，而是O(d/n)，d是模型的参数空间，n是训练样本数，所以，即使模型参数非常多，但如果训练样本也非常多，这个模型的variance也会很小，所以，variance过大（overfitting）的问题总能通过增加训练样本解决。
最后，再附两张bias和variance的经典图，第一张是high bias，第二张是high variance。
篇二：机器学习算法优缺点改进总结
Lecture 1 Introduction to Supervised Learning
（1）Expectatin Maximization(EM) Algorithm (期望值最大)
（2）Linear Regression Algorithm(线性回归)
（3）Local Weighted Regression(局部加权回归)
（4）k-Nearest Neighbor Algorithm for Regression(回归k近邻)
（5）Linear Classifier(线性分类)
（6）Perceptron Algorithm (线性分类)
（7）Fisher Discriminant Analysis or Linear Discriminant Analysis(LDA)
（8）k-NN Algorithm for Classifier(分类k近邻)
（9）Bayesian Decision Method(贝叶斯决策方法)
Lecture 2 Feed-forward Neural Networks and BP Algorithm
（1）Multilayer Perceptron(多层感知器)
（2）BP Algorithm
Lecture 3 Rudiments of Support Vector Machine
（1）Support Vector Machine(支持向量机) （此算法是重点，必考题）
此处有一道必考题
Lecture 4 Introduction to Decision Rule Mining
（1）Decision Tree Algorithm
（2）ID3 Algorithm
（3）C4.5 Algorithm
（4）粗糙集……
Lecture 5 Classifier Assessment and Ensemble Methods
（1）Bagging
（2）Booting
（3）Adaboosting
Lecture 6 Introduction to Association Rule Mining
（1）Apriori Algorithms
（2）FP-tree Algorithms
Lecture 7 Introduction to Custering Analysis
（1）k-means Algorithms
（2）fuzzy c-means Algorithms
（3）k-mode Algorithms
（4）DBSCAN Algorithms
Lecture 8 Basics of Feature Selection
（1）Relief Algorithms
（2）ReliefF Algorithms
（3）mRMR Algorithms最小冗余最大相关算法
（4）attribute reduction Algorithms
比较了几种分类算法性质。（以下两个表格来自两篇该领域经典论文）
Lecture 1 Introduction to Supervised Learning
（1）Expectatin Maximization(EM) Algorithm (期望值最大)
①算法思想：
EM算法又称期望最大化算法，是对参数极大似然估计的一种迭代优化策略，它是一种可以从非完整的数据集中对参数进行极大似然估计的算法,应用于缺损数据，截尾数据，带有噪声的非完整数据。
最大期望算法经过两个步骤交替进行计算：
第一步计算期望（E）：也就是将隐藏的变量对象能够观察到的一样包含在内，从而计算最大似然的期望值；
另外一步是最大化（M），也就是最大化在E步上找到的最大似然期望值，从而计算参数的似然估计。M步上找到的参数然后用于另一个E步计算。
重复上面2步直至收敛。
②优点：1）Ｍ步仅涉及完全数据极大似然，通常计算比较简单
2）收敛是稳定的，因为每次迭代的似然函数是不断增加的。
③缺点：1）表现在对缺失数据较多或是多维高斯分布的情形下，计算量大，收敛速度较慢。
2）对于某些特殊的模型，要计算算法中的M步，即完成对似然函数的估计是比较困难的。
3）在某些情况下，要获得EM算法中E步的期望显式是非常困难的。4）EM算法的收敛速度，非常依赖初始值的设置，设置不当，计算代价相当大。
5）EM算法中的M-Step依然是采用求导函数的方法,所以它找到的是极值点,即局
部最优解,而不一定是全局最优解。
④改进：针对1）改进：扩大参数空间来加快收敛
针对2）改进：ECM算法，该算法通过在Ｍ步构建计算比较简单的小循环对EM
算法进行了改进，从而使期望函数极大化更加容易和有效，从而解决这一问题。
针对3）改进：MCEM算法，将E步积分求期望用蒙特卡洛模拟方法来实现，使得E步求期望更容易实现。
针对4）初始值的获取可以通过k-means算法，层次聚类算法或是数据数据进行随
机分割，然后重复EM效果进行初始点选择。
针对5）结合遗传算法的全局搜索能力，扩大EM算法的搜索空间，有效降低EM
算法对初始值的依赖度，改善局部最优值的缺陷。
（
2）Linear Regression Algorithm(线性回归)
①算法思想：
线性回归(Linear Regression)是利用称为线性回归方程的最小平方函数对一个或多个自变量和因变量之间关系进行建模的一种回归分析。这种函数是一个或多个称为回归系数的模型参数的线性组合。只有一个自变量的情况称为简单回归,大于一个自变量情况的叫做多元回归。
回归模型：
i 其中 ?和C是未知参数，对于每个训练样本(xi，yi)可得到h(xi)，用来预测真实值y。损失函数：
即误差值的平方。
1：对于训练集，求取θ，使得损失函数最小。（使用最小二乘法，梯度下降法）
2：对于新输入x，其预测输出为θTx
②优点：结果易于理解，实现简单，计算简单
③缺点：1）对于非线性的数据拟合效果不好（原因：因为线性回归将数据视为线性的，
可能出现欠拟合现象，导致结果不能取得最好的预测效果）
2）如果训练数据如果有些数据偏差特别大，这回造成最后训练的模型可能对整体
具备很好的准确性
④改进：针对2）改进 ：局部加权回归 数据都不
（3）Local Weighted Regression(局部加权回归)
①算法思想：
给每个待预测点周围的点赋予一定的权重,越近的点权重越高,以此来选出该预测点对应的数据子集,然后在此数据子集上基于最小均方差进行普通的回归.局部加权回归实质上是对于需要预测的点，只是根据其附近的点进行训练，其他的没有改变。
对于局部线性加权算法：
1：对于输入x，找到训练集中与x邻域的训练样本
2：对于其邻域的训练样本，求取θ，使得其∈x的邻域 ）最小。其中w(i)为权重值。 3.预测输出为θTx
4.对于新输入，重复1-3过程。
其中 τ 为带宽(bandwidth)常量，距离输入越远，权重越小， 反之越大。
②优点：1）局部加权回归还是对训练数据拟合的比较好
2）不太依赖特征的选择，而且只需要用线性模型就能够训练出不错的拟合模型、
③缺点：1）计算量较大。（因为局部加权回归的损失数随着预测值的不同而不同，这样θ
就无法事先确定，每次预测时都需要扫描所有的数据并重新计算θ）
2）局部加权回归容易出现过拟合现象，过拟合现象很明显
3）关注局部的训练数据，忽略了全局数据，如果预测点在出现偏差的训练数据附
近，那么预测值会偏差很大。
④改进：
（4）k-Nearest Neighbor Algorithm for Regression(回归k近邻)
①算法思想：
通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。
如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。
KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成反比。
②优点：
1）简单、有效。
2）重新训练的代价较低（类别体系的变化和训练集的变化，在Web环境和电子商务应用中是很常见的）。
3）计算时间和空间线性于训练集的规模（在一些场合不算太大）。
4）由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。
5）该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。
③缺点：
（1）KNN在(本文来自：wwW.xIAocAofaNwEn.com 小 草范 文 网:机器学习总结)对属性较多的训练样本进行分类时，由于计算量大而使其效率大大降低，效果不是很理想。
（2）当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。
（3）对数据的局部结构比较敏感。如果查询点是位于训练集较密集的区域，那预测相对比其他稀疏集来说更准确。
（4）对k值敏感。
（5）维数灾难：临近距离可能被不相干属性主导（因此特征选择问题）
④改进：
（1）分类效率：事先对样本属性进行约简，删除对分类结果影响较小的属性，快速的得出待分类样本的类别。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。
（2）分类效果：采用权值的方法（和该样本距离小的邻居权值大）来改进，Han等人于2002年尝试利用贪心法，针对文件分类实做可调整权重的k最近邻居法WAkNN (weighted adjusted k nearest neighbor)，以促进分类效果；而Li等人于2004年提出由于不同分类的文件本身有数量上有差异，因此也应该依照训练集合中各种分类的文件数量，选取不同数目的最近邻居，来参与分类。
（3）该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。 该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。可以采用权值的方法（和该样本距离小的邻居权值大）来改进。
（4）K 值的选择会对算法的结果产生重大影响。K值较小意味着只有与输入实例较近的训练实例才会对预测结果起作用，但容易发生过拟合；如果 K 值较大，优点是可以减少学习的估计误差，但缺点是学习的近似误差增大，这时与输入实例较远的训练实例也会对预测起作用，是预测发生错误。在实际应用中，K 值一般选择一个较小的数值，通常采用交叉验证的方法来选择最优的 K 值。随着训练实例数目趋向于无穷和 K=1 时，误差率不会超过贝叶斯误差率的2倍，如果K也趋向于无穷，则误差率趋向于贝叶斯误差率。
（5）该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。
篇三：机器学习算法总结_K近邻
第一章 k近邻
1.1 K近邻简介
k近邻（k-Nearest Neighbor，k-NN）是一种基本的、有监督学习的分类方法，于1968年由Cover和Hart提出，其用于判断某个对象的类别。k近邻的输入为对象特征向量，对应于特征空间上的点；输出为对象的类别。
图1.1 k近邻实例
如上图所示，有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所示的数据则是待分类的数据。也就是说，现在，我们不知道中间那个绿色的数据是从属于哪一类（蓝色小正方形or红色小三角形），下面，我们就要解决这个问题：给这个绿色的圆分类。
所谓物以类聚，人以群分，判别一个人是一个什么样品质特征的人，常常可以从他/她身边的朋友入手。要判别上图中那个绿色的圆是属于哪一类数据，只需根据它周围的邻居即可。但一次性看多少个邻居呢？从上图中，你还能看到：
如果k=3，绿色圆点的最近的3个邻居（欧式距离）是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。
如果K=5，绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。
上面这个小例子基本上体现了k近邻算法的三个基本要素：确定度量方式（欧式距离）、选着k值（2 or 3）、分类决策规则（少数服从多数）。
k近邻算法实例引入：
下面，给出k近邻算法的数学表述： 输入：训练数据集
T?{(x1,y1),(x2,y2),
其中，xi?Rn为实例的特征向量，yi?{c1,c2,特征向量x;
输出：实例x所属的类。
,(xN,yN)}
,N;实例
,ck}为实例的类别，i?1,2,
（1）根据给定的距离度量，在训练集T中找出与x最邻近的k个点，涵盖这k个点的x的邻域记作Nk(x)；
（2）在Nk(x)中根据分类决策规则（如多数表决）决定x的类别y：
y?argmax
cj
xi?
?Nx
k(
I(yi?cj),i?1,2,
)
,N;j?1,2,,K （1-1）
其中，I为指示函数，即当yi?cj时I为1,否则I为0。
k近邻的特殊情况是k=1的情形，称为最近邻算法，对于输入的对象（特征向量）x，最近邻法将训练数据集中于x最近邻点所属的类作为x的类。 1.2 K近邻模型建立
建立数学模型的过程实质就是确定三个基本要素的过程。
1.2.1 距离度量方式的确定
样本空间（特征空间）中两个对象的距离是它们相似程度的量化反映。k近邻模型的
特征空间可被抽象为n维的向量空间R，现在两个对象之间的距离就可转化为两个向量之间的距离，这样研究起来就方便多了。在k近邻模型中，计算向量之间距离的公式列举如下：
d(X,Y)??(xi?yi)2（1） 欧式距离：（1-2）
i?1
n
?ii
（2）曼哈顿距离： （1-3） i?1
d(X,Y)?
|x?y|
n
（3）切比雪夫距离： （1-4）
d(X,Y)?max(|xi?yi|)
1?i?n
n
d(X,Y)?(?|xi?yi|)（4）闵可夫斯基距离： （1-5）
p
1
p
特点：为综合性的公式 。
i?1
T?1（5）马氏距离：d(X,Y)?X?Y)(X?Y)
?
（1-6）
特点：可排除对象间的相关性。
（6）相关距离： （1-7） DXY?1??XY（7）夹角余弦距离和Tonimoto系数：
s(X,Y)? （I）夹角余弦距离：（1-8）
X?YXT(X,Y)? （II）Tonimoto系数（夹角余弦的改进）：（1-9） 22
X
??X?Y
X?Y
下面给出计算欧式距离的C/C++ 代码：
//计算欧氏距离
double euclideanDistance(const vector<double>& v1, const vector<double>& v2)
{
assert(v1.size() == v2.size());double ret = 0.0;
for (vector<double>::size_type i = 0; i != v1.size(); ++i){
ret += (v1[i] - v2[i]) * (v1[i] - v2[i]);}
return sqrt(ret); }1.2.2 K值的选择
选择较小的K值，近似误差会减小，估计误差会增大，意味着整体模型变得复杂，容易发生过拟合；
选择较大的K值，减少估计误差，近似误差会增大，K值的增大就意味着整体的模型变得简单。
在实际应用中，K值一般取一个比较小的数值，例如采用交叉验证法（一部分样本做训练集，一部分做测试集）来选择最优的K值。
1.2.3 分类决策规则
（1）多数表决
k近邻法中的分类决策规则往往是多数表决，即由输入对象的k个邻近中的多数类决定输入对象的类，通俗点就是“少数服从多数”。 （2）误分类率
误分类率即对输入对象出现错误分类的概率。其数学表示如下： 对给定的实例
x， 其最近邻的k个训练实例点构成集合N(x).如果涵盖N(x)的区域
k
k
的类别是cj，那么误分类率是
1
k
xi?
?Nx
k(
I(yi?cj)?1?
)
1
k
xi?
?Nx
k(
I(yi?cj) （1-10）
)
要使误分类率最小即经验风险最小，就要使等价于经验风险最小化. 1.3 k近邻算法的实现
?xNx
i?k(
I(yi?cj)最大，所以多数表决规则
)
在实现k近邻法时，主要考虑的问题是如何对训练数据进行快速k近邻捜索。 k近邻法最简单的实现方法是线性扫描法（linear scan)。即计算输入对象与每一个训练对象之间的距离，然而当训练集很大时，计算非常耗时，这种方法是不可行的.
为了提高k近邻搜索的效率，我们可以构建数据的索引（因为实际数据一般都会呈现簇状的聚类形态，因此我们想到建立数据索引，然后再进行快速匹配）。索引树是一种树结构索引方法，其基本思想是对搜索空间进行层次划分。根据划分的空间是否有混叠可以分为Clipping和Overlapping两种。前者划分空间没有重叠，其代表就是kd树；后者划分空间相互有交叠，其代表为R树。下面主要介绍其中的kd树（kd tree)方法。
1.3.1 kd树的构建
该方法来自斯坦福大学的Jon Louis Bentley在ACM杂志上发表的一篇论文：Multidi-mensional Binary Search Trees Used for Associative Searching ，这篇论文中正式提出kd树，并阐述的了kd树的构建等（此时的k与kNN中的k含义是不同的）。
kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形 数据结构。kd树是二叉树，表示对k维空间的一个划分（partition)。构造k树相 当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域。kd树的每个结点对应于一个k维超矩形区域。
构造kd树的方法如下：构造根结点，使根结点对应于k维空间中包含所有对象点的超矩形区域；通过下面的递归方法，不断地对k维空间进行切分，生成子结 点。在超矩形区域（结点）上选择一个坐标轴和在此坐标轴上的一个切分点，确定一个超平面，这个超平面经过选定的切分点并垂直于选定的坐标轴，将当前超矩形区域切分为左右两个子区域（子结点）：这时，对象被分到两个子区域。重复这个过程直到子区域内没有对象时终止（终止时的结点为叶结点)。在此过程中，将所有对象保存在相应的结点上。对于三维的情形，kd树对空间的划分，如下图所示：
图1.2 三维kd树
通常，依次选择坐标轴对空间切分，选择训练对象点在选定坐标轴上的中位数为切分点，这样得到的kd树是平衡的。在确定坐标轴时，选着当前方差最大的效果较好，因为此时区分度最大。注意，平衡的树搜索时的效率未必是最优的。 下面给出构造以树的算法（见图1.3）： 算法1.1 (构造平衡kd树）