统计计算算法

分类算法-----决策树常用的分类算法包括：决策树分类法，朴素的贝叶斯分类算法(nativeBayesianclassifier)、基于支持向量机(SVM)的分类器，神经网络法，k-最近邻法(k-nearestneighbor，kNN)，模糊分类法等等。监督学习与无监督学习机器学习发展到现在，一般划分为监督学习(supervisedlearning)，半监督学习(semi-supervisedlearning)以及无监督学习(unsupervisedlearning)三类。常见的分类算法属于监督学习，聚类则属于无监督学习而在支持向量机导论一书给监督学习下的定义是：当样例是输入/输出对给出时，称为监督学习，有关输入/输出函数关系的样例称为训练数据。而在无监督学习中，其数据不包含输出值，学习的任务是理解数据产生的过程。第一部分、决策树学习1.1、什么是决策树机器学习中，决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。从数据产生决策树的机器学习技术叫做决策树学习,通俗点说就是决策树，说白了，这是一种依托于分类、训练上的预测树，根据已知预测、归类未来。来理论的太过抽象，下面举两个浅显易懂的例子：第一个例子那么这个可以用下图表示女孩的决策逻辑：第二个例子此例子来自TomM.Mitchell著的机器学习一书：小王的目的是通过下周天气预报寻找什么时候人们会打高尔夫，他了解到人们决定是否打球的原因最主要取决于天气情况。而天气状况有晴，云和雨；气温用华氏温度表示；相对湿度用百分比；还有有无风。如此，我们便可以构造一棵决策树，如下（根据天气这个分类决策这天是否合适打网球）：上述决策树对应于以下表达式：（Outlook=Sunny^Humidity=70）V（Outlook=Overcast）V（Outlook=Rain^Wind=Weak）1.2、ID3算法1.2.1、决策树学习之ID3算法ID3算法是一个由RossQuinlan发明的用于决策树的算法:越是小型的决策树越优于大的决策树（besimple简单理论）。尽管如此，该算法也不是总是生成最小的树形结构，而是一个启发式算法。从信息论知识中我们知道，期望信息越小，信息增益越大，从而纯度越高。ID3算法的核心思想就是以信息增益度量属性选择，选择分裂后信息增益最大的属性进行分裂。该算法采用自顶向下的贪婪搜索遍历可能的决策树空间。Step1:“哪一个属性将在树的根节点被测试”开始；Step2:使用统计测试来确定每一个实例属性单独分类训练样例的能力，分类能力最好的属性作为树的根结点测试，Step3:为根结点属性的每个可能值产生一个分支，并把训练样例排列到适当的分支之下。Step4：重复这个过程，用每个分支结点关联的训练样例来选取在该点被测试的最佳属性。下图所示即是用于学习布尔函数的ID3算法概要：1.2.2、哪个属性是最佳的分类属性1、信息增益的度量标准：熵熵：它刻画了任意样例集的纯度。给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个布尔型分类的熵为：上述公式中，p+代表正样例，比如在本文开头第二个例子中p+则意味着去打羽毛球，而p-则代表反样例，不去打球(在有关熵的所有计算中我们定义0log0为0)。举例来说，假设S是一个关于布尔概念的有14个样例的集合，它包括9个正例和5个反例（我们采用记号[9+，5-]来概括这样的数据样例），那么S相对于这个布尔样例的熵为：Entropy（[9+，5-]）=-（9/14）log2（9/14）-（5/14）log2（5/14）=0.940。So，根据上述这个公式，我们可以得到：S的所有成员属于同一类，Entropy(S)=0；S的正、反样本的数量相等，Entropy(S)=1；S的正反样本的数量不等，熵介于0，1之间，如下图所示：信息论中对熵的一种解释，熵确定了要编码集合S中任意成员的分类所需要的最少二进制位数。更一般地，如果目标属性具有c个不同的值，那么S相对于c个状态的分类的熵定义为：Pi为子集合中不同性(而二元分类即正样例和负样本)的样例的比例。2、信息增益度量期望的熵降低2、信息增益Gain(S,A)定义定义属性分类训练数据的效力的度量标准。简单的说，一个属性的信息增益就是由于使用这个属性分割样例而导致的期望熵降低(或者说，样本按照某属性划分时造成熵减少的期望)。更精确地讲，一个属性A相对样例集合S的信息增益Gain(S,A)被定义为：其中Values(A)是属性A所有可能值的集合，是S中属性A的值为v的子集。换句话来讲，Gain(S,A)是由于给定属性A的值而得到的关于目标函数值的信息。当对S的一个任意成员的目标值编码时，Gain(S,A)的值是在知道属性A的值后可以节省的二进制位数。接下来，有必要提醒读者一下：关于下面这两个概念or公式，第一个Entropy(S)是熵定义，第二个则是信息增益Gain(S,A)的定义，而Gain(S,A)由第一个Entropy(S)计算出，记住了。下面，举个例子，假定S是一套有关天气的训练样例，描述它的属性包括可能是具有Weak和Strong两个值的Wind。像前面一样，假定S包含14个样例，[9+，5-]。在这14个样例中，假定正例中的6个和反例中的2个有Wind=Weak，其他的有Wind=Strong。由于按照属性Wind分类14个样例得到的信息增益可以计算如下。运用在本文开头举得第二个根据天气情况是否决定打羽毛球的例子上，得到的最佳分类属性如下图所示：在上图中，计算了两个不同属性：湿度(humidity)和风力(wind)的信息增益，最终humidity这种分类的信息增益0.151wind增益的0.048。说白了，就是在星期六上午是否适合打网球的问题诀策中，采取humidity较wind作为分类属性更佳，决策树由此而来。1.2.3、ID3算法决策树的形成下图为ID3算法第一步后形成的部分决策树。这样综合起来看，就容易理解多了。1、overcast样例必为正，所以为叶子结点，总为yes；2、ID3无回溯，局部最优，而非全局最优，还有另一种树后修剪决策树。下图是ID3算法第一步后形成的部分决策树：如上图，训练样例被排列到对应的分支结点。分支Overcast的所有样例都是正例，所以成为目标分类为Yes的叶结点。另两个结点将被进一步展开，方法是按照新的样例子集选取信息增益最高的属性。1.3、C4.5算法C4.5用信息增益率来选择属性。ID3选择属性用的是子树的信息增益。1对非离散数据也能处理。2能够对不完整数据进行处理针对上述第一点，解释下：一般来说率就是用来取平衡用的，就像方差起的作用差不多，比如有两个跑步的人，一个起点是10m/s的人、其10s后为20m/s；另一个人起速是1m/s、其1s后为2m/s。如果紧紧算差值那么两个差距就很大了，如果使用速度增加率(加速度，即都是为1m/s^2)来衡量，2个人就是一样的加速度。因此，C4.5克服了ID3用信息增益选择属性时偏向选择取值多的属性的不足。C4.5算法之信息增益率。一个可以选择的度量标准是增益比率gainratio。增益比率度量是用前面的增益度量Gain(S，A)和分裂信息度量SplitInformation(S，A)来共同定义的，如下所示：其中，分裂信息度量被定义为(分裂信息用来衡量属性分裂数据的广度和均匀)：其中S1到Sc是c个值的属性A分割S而形成的c个样例子集。注意分裂信息实际上就是S关于属性A的各值的熵。这与我们前面对熵的使用不同，在那里我们只考虑S关于学习到的树要预测的目标属性的值的熵。1.3.3、C4.5算法实现中的几个关键步骤在上文中，我们已经知道了决策树学习C4.5算法中4个重要概念的表达，如下：一Boosting算法的起源boost算法系列的起源来自于PACLearnability(PAC可学习性)。定义了学习算法的强弱弱学习算法---识别错误率小1/2(即准确率仅比随机猜测略高的学习算法)强学习算法---识别准确率很高并能在多项式时间内完成的学习算法二Boosting算法的发展历史Boosting算法是一种把若干个分类器整合为一个分类器的方法。1）bootstrapping方法的主要过程主要步骤：i)重复地从一个样本集合D中采样n个样本ii)针对每次采样的子样本集，进行统计学习，获得假设Hiiii)将若干个假设进行组合，形成最终的假设Hfinaliv)将最终的假设用于具体的分类任务2）bagging方法的主要过程-----bagging可以有多种抽取方法主要思路：i)训练分类器从整体样本集合中，抽样n*N个样本针对抽样的集合训练分类器Ciii)分类器进行投票，最终的结果是分类器投票的优胜结果.现在的adaboost算法，其主要框架可以描述为：i)循环迭代多次更新样本分布寻找当前分布下的最优弱分类器计算弱分类器误差率ii)聚合多次训练的弱分类器三Adaboost算法AdaBoost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器，即弱分类器，然后把这些弱分类器集合起来，构造一个更强的最终分类器。算法本身是改变数据分布实现的，它根据每次训练集之中的每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改权值的新数据送给下层分类器进行训练，然后将每次训练得到的分类器融合起来，作为最后的决策分类器。完整的adaboost算法如下简单来说，Adaboost有很多优点:1)adaboost是一种有很高精度的分类器2)可以使用各种方法构建子分类器，adaboost算法提供的是框架3)当使用简单分类器时，计算出的结果是可以理解的。而且弱分类器构造极其简单4)简单，不用做特征筛选5)不用担心overfitting！四Adaboost举例下面我们举一个简单的例子来看看adaboost的实现过程：图中，“+”和“-”分别表示两种类别，在这个过程中，我们使用水平或者垂直的直线作为分类器，来进行分类。第一步：根据分类的正确率，得到一个新的样本分布D2,一个子分类器h1其中划圈的样本:被分错的。在右边:比较大的“+”表示对该样本做了加权.第二步：根据分类的正确率，得到一个新的样本分布D3，一个子分类器h2第三步：得到一个子分类器h3整合所有子分类器：因此可以得到整合的结果，从结果中看，及时简单的分类器，组合起来也能获得很好的分类效果，在例子中所有的。每次迭代都要把分错的点的权值变大这样也许提高错误点可以让后面的分类器权值更高.六总结最后，我们可以总结下adaboost算法的一些实际可以使用的场景：1）用于二分类或多分类的应用场景2）用于做分类任务的baseline无脑化，简单，不会overfitting，不用调分类器3）用于特征选择（featureselection)4）Boosting框架用于对badcase的修正只需要增加新的分类器，不需要变动原有分类器由于adaboost算法是一种实现简单，应用也很简单的算法。Adaboost算法通过组合弱分类器而得到强分类器，同时具有分类错误率上界随着训练增加而稳定下降，不会过拟合等的性质，应该说是一种很适合于在各种分类场景下应用的算法。Bootstrap方法基本思想是：因为观测样本包含了潜在样本的全部的信息，那么我们不妨就把这个样本看做“总体”。那么相关的统计工作（估计或者检验）的统计量的分布可以从“总体”中利用MonteCarlo模拟得到。其做法概括为：既然样本是抽出来的，那我何不从样本中再抽样。bootstrap基本方法1、采用重抽样技术从原始样本中抽取一定数量（自己给定）的样本，此过程允许重复抽样。2、根据抽出的样本计算给定的统计量T。3、重复上述N次（一般大于1000），得到N个统计量T。其均值可以视作统计量T的估计。4、计算上述