常用机器学习算法简单介绍

1、一、 分类1.1 K-最近邻算法（K-NN）存在一个样本数据集合，也称作训练样本集，并且样本集中的每个数据都存在标签，即我们知道样本集中每一数据与所述分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，选择样本数据集中的前k个相似的数据。最后选择k个最相似数据中出现次数最多的分类，作为新数据的分类。伪代码:对未知类别属性的数据集中的每个点依次执行以下操作：（1） 计算已知类别数据集中的点与当前点之间的距离；（2） 按照距离递增依次排序；（3） 选取与当前点距离最小的k个点；（4） 确定前k

2、个点所在类别的出现频率；（5） 返回前k个点出现频率最高的类别作为当前点的预测分类。如图，平面有3个样本集将空间分为三类，输入新的数据点，使用欧拉距离来计算当前点与已知类别数据集中的点之间的距离，并选择K=5作为参数。在距离最近的5个特征点中，有4个点属于类别w1,1个点属于类别w2，因此分类器将输入点划分至w1类。1.2 决策树分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型：内部节点和叶节点，内部节点表示一个特征或属性，叶节点表示一个类。分类的时候，从根节点开始，对实例的某一个特征进行测试，根据测试结果，将实例分配到其子结点；此时，每一个子结点对应

3、着该特征的一个取值。如此递归向下移动，直至达到叶结点，最后将实例分配到叶结点的类中。如下图所示流程图就是一个决策树模型。在构造决策树时，需要确定当前数据集上哪个特征在划分数据分类时起到决定性的作用。为了找到决定性的特征，划分出最后的结果，必须评估每个特征。完成测试之后，原始数据集就被划分为几个数据子集。这些数据子集会分布在第一个决策点的所有分支上。如果某个分支下的数据属于同一类型，则当前的数据子集已经正确地划分数据分类，无需进一步对数据集进行分割。如果数据子集内的数据不属于同一类型，则需要重复划分数据子集的过程。如何划分数据子集的算法和划分原始数据集的方法相同，直到所有具有相同类型的数据均在一

4、个数据子集内。创建分支函数的伪代码：检测数据集中的每个子项是否属于同一分类：If so return 类标签；Else 寻找划分数据集的最好特征 划分数据集创建分支节点 for 每个划分的子集 调用创建分支函数并增加返回结果到分支节点中return 分支节点1.3 朴素贝叶斯数学知识：P(A|B)表示事件B已经发生的前提下，事件A发生的概率，叫做事件B发生下事件A的条件概率。其基本求解公式为：PAB=P(AB)P(B)贝叶斯定理：朴素贝叶斯分类原理：对于给定的待分类项，求解在此项出现的条件下，该项来自各个类别的概率，将此项划分为求解概率最大的那个类别。例如，假设我们有一个数据集，它由两类数据组

5、成，c1与c2。给定某个由(x,y)表示的数据点，根据贝叶斯准则计算p(c1|x,y)与p(c2|x,y)。若p(c1|x,y) p(c2|x,y) ,那么该数据点属于类别c1。若p(c1|x,y) p(c2|x,y) ,那么该数据点属于类别c2。1.4 基于Logistic 回归和Sigmoid函数的分类主要思想：根据现有数据对分类边界线建立回归公式，依次进行分类。Sigmoid函数计算公式如下：z=11+e-z曲线图如下图所示：当x为0时，Sigmoid函数值为0.5，随着x的增大，对应的Sigmoid函数值将逼近于1；而随着x的增大，对应的Sigmoid函数值将逼近于0，看起来很像一个阶

6、跃函数。因此，为了实现Logistic 回归分类器，我们可以在每个特征上都乘一个回归系数，如下，然后把所有值相加，如下：z=w0x0+w1x1+w2x2+wnxn将总和z代入Sigmoid函数中，进而得到一个范围在01之间的数值。任何大于0.5的数据被分为1类，小于0.5即被归入0类。确定分类器的函数形式之后，问题变为：如何确定最佳回归系数。为了找到最佳回归系数，需要用到最优化理论的一些知识：梯度上升法 or 梯度下降法，此处不做介绍。1.5 支持向量机 (Support Vector Machines, SVM)SVM是一种训练机器学习的算法，可以用于解决分类和回归问题，同时还使用了一种称之

7、为kernel trick（支持向量机的核函数）的技术进行数据的转换，然后再根据这些转换信息，在可能的输出之中找到一个最优的边界(超平面)。简单来说，就是做一些非常复杂的数据转换工作，然后根据预定义的标签或者输出进而计算出如何分离用户的数据。算法原理：如图，上述将数据集分割开来的直线称为分平面。在上图中，由于数据点都在二维平面上，所以此时分隔超平面就只是一条直线。但是，若果所给数据点是三维的，那么此时用来分割数据的就是一个平面。若为N维，则为N-1维的超平面，也就是分类的决策边界。如果数据点离决策边界越远，那么其最后的预测结果也就越可信。我们希望找到离分割平面最近的点，确保它们离分割面的距离尽

8、可能远。这里点到分割面的距离被称为间隔。支持向量就是离分割超平面最近的那些点。接下来要试着最大化支持向量机到分割面的距离，需要找到此问题的优化求解方法。此处不做介绍。注意：SVM本身是一个二类分类器，对多类问题应用SVM需对代码做修改。当直线不能将数据点分开时，即非线性可分，如下图所示，可以使用一种称为核函数的工具将数据转换为易于分类器理解的形式。核函数作用是实现从一个特征空间到另一个特征空间的映射。经过空间转换之后，可以在高维空间中解决线性问题，也就等价于在低维空间中解决非线性问题。1.6 利用AdaBoost 元算法提高分类性能当作重要决定时，大家都会考虑或吸取多个专家而不只是一个人的意见

9、，机器学习处理问题也是如此。将不同分类器组合起来的方法。组合方法有多种形式：可以是不同算法的集成，也可以是同一算法在不同设置下的集成，还可以是数据集不同部分配给不同分类器之后的集成。下面会介绍基于同一种分类器多个不同实例的两种计算方法。1.6.1 bagging:基于数据随机抽样的分类器构建方法自举汇聚法（boosting aggregating），是在从原始数据集选择S个新数据集的一种技术，在S个数据集建好之后，将某个学习算法分别作用于每个数据集就得到了S个分类器。当要对新数据分类时，就可以应用这S个分类器进行分类。与此同时，选择分类器投票结果中最多的类别作为最后的分类结果。随机森林（ran

10、dom forest）就是一种更先进的bagging方法。1.6.2 boostingboosting分类器是通过串行训练而获得的，每个新分类器都根据已训练出的分类器的性能进行训练。Boosting是通过集中关注被已有分类器错分的那些数据来获得新的分类器。boosting分类结果是基于所有分类器的加权求和结果的。Bagging 中分类器权重是相等的，而boosting中分类器权重不相等，每个权重代表的是对应分类器在上一轮迭代中的成功度。接下来介绍最流行的boosting版本AdaBoost算法。算法运行过程：训练数据中的每一个样本，并赋予其一个权重，这些权重构成了向量D。一开始，这些权重都初始

11、化成相等的值。首先在训练数据上训练处一个弱分类器并计算该分类器的错误率，然后在同一数据集上再次训练弱分类器。在分类器的第二次训练当中，将会调整每个样本的权重，其中第一次分对的样本的权重会降低，而第一次分错的样本的权重将会提高。为了从所有弱分类器重病得到最终的分类结果，AdaBoost为每个分类器都分配了一个权重值alpha，这些alpha值是基于每个弱分类器的错误率进行计算的。其中，错误率定义如下：=未正确分类的样本数目总样本数alpha的计算公式如下：=12ln(1-)算法流程图如下：左边是数据集，其中直方图的不同宽度表示每个样例上的不同权重。在经过一个分类器之后，加权的预测结果会通过三角形

12、中的alpha值进行加权。每个三角形中输出的加权结构在圆形中求和，从而得到最终结果。权重向量D更新方式可参考机器学习实战。二、 聚类聚类是一种无监督机器学习方法，目标变量事先不存在。2.1 K-means聚类算法基本K-Means算法的思想很简单，事先确定常数K，常数K意味着最终的聚类类别数，首先随机选定初始点为质心，并通过计算每一个样本与质心之间的相似度(这里为欧式距离)，将样本点归到最相似的类中，接着，重新计算每个类的质心(即为类中心)，重复这样的过程，知道质心不再改变，最终就确定了每个样本所属的类别以及每个类的质心。由于每次都要计算所有的样本与每一个质心之间的相似度，故在大规模的数据集上

13、，K-Means算法的收敛速度比较慢。K-means聚类算法伪代码：创建K个点作为起始质心（经常为随机选择）当任意一个点的簇分配结构发生改变时 对数据集中的每个数据点 对每个质心 计算质心与数据之间的距离（某种距离计算） 将数据分配到距其距离最近的簇 对每一个簇计算簇中所有点的均值并将其作为质心。如下图所示为K-means聚类过程。问题和解决方案OpenCV K-means code 在core module中double cv:kmeans( / cv:InputArray data, /多维的数据样本矩阵，float型int K, / 类别数kcv:InputOutputArray bestLabels, / 每个样本最后的类别索引cv:TermCriteria criteria, / 迭代终止条件int atte