统计计算算法

1、分类算法-决策树 常用的分类算法包括：决策树分类法，朴素的贝叶斯分类算法(native Bayesian classifier)、基于支持向量机(SVM)的分类器，神经网络法，k-最近邻法(k-nearest neighbor，kNN)，模糊分类法等等。监督学习与无监督学习机器学习发展到现在，一般划分为 监督学习(supervised learning)，半监督学习(semi-supervised learning)以及无监督学习(unsupervised learning)三类。常见的分类算法属于监督学习，聚类则属于无监督学习而在支持向量机导论一书给监督学习下的定义是：当样例是输入/输出对给

2、出时，称为监督学习，有关输入/输出函数关系的样例称为训练数据。而在无监督学习中，其数据不包含输出值，学习的任务是理解数据产生的过程。第一部分、决策树学习1.1、什么是决策树机器学习中，决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。从数据产生决策树的机器学习技术叫做决策树学习, 通俗点说就是决策树，说白了，这是一种依托于分类、训练上的预测树，根据已知预测、归类未来。来理论的

3、太过抽象，下面举两个浅显易懂的例子：第一个例子那么这个可以用下图表示女孩的决策逻辑：第二个例子此例子来自Tom M.Mitchell著的机器学习一书： 小王的目的是通过下周天气预报寻找什么时候人们会打高尔夫，他了解到人们决定是否打球的原因最主要取决于天气情况。而天气状况有晴，云和雨；气温用华氏温度表示；相对湿度用百分比；还有有无风。如此，我们便可以构造一棵决策树，如下（根据天气这个分类决策这天是否合适打网球）：上述决策树对应于以下表达式：（Outlook=Sunny Humidity<=70）V （Outlook = Overcast）V （Outlook=Rain Wind=Weak）

4、1.2、ID3算法、决策树学习之ID3算法 ID3算法是一个由Ross Quinlan发明的用于决策树的算法:越是小型的决策树越优于大的决策树（be simple简单理论）。尽管如此，该算法也不是总是生成最小的树形结构，而是一个启发式算法。从信息论知识中我们知道，期望信息越小，信息增益越大，从而纯度越高。ID3算法的核心思想就是以信息增益度量属性选择，选择分裂后信息增益最大的属性进行分裂。该算法采用自顶向下的贪婪搜索遍历可能的决策树空间。 Step1:“哪一个属性将在树的根节点被测试”开始； Step2:使用统计测试来确定每一个实例属性单独分类训练样例的能力，分类能力最好的属性作为树的根结点测

5、试，Step3:为根结点属性的每个可能值产生一个分支，并把训练样例排列到适当的分支之下。 Step4：重复这个过程，用每个分支结点关联的训练样例来选取在该点被测试的最佳属性。下图所示即是用于学习布尔函数的ID3算法概要：、哪个属性是最佳的分类属性1、信息增益的度量标准：熵熵：它刻画了任意样例集的纯度。给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个布尔型分类的熵为：上述公式中，p+代表正样例，比如在本文开头第二个例子中p+则意味着去打羽毛球，而p-则代表反样例，不去打球(在有关熵的所有计算中我们定义0log0为0)。 举例来说，假设S是一个关于布尔概念的有14个样例的集合，它包括9

6、个正例和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为子集合中不同性(而二元分类即

7、正样例和负样本)的样例的比例。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的值后可以节省的二进制位数。接下来，有必要

8、提醒读者一下：关于下面这两个概念 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个样例得到的信息增益可以计算如下。运用在本文开头举得第二个根据天气情况是否决定打羽毛球的例子上，得到的最佳分类属性如下

9、图所示：在上图中，计算了两个不同属性：湿度(humidity)和风力(wind)的信息增益，最终humidity这种分类的信息增益0.151>wind增益的0.048。说白了，就是在星期六上午是否适合打网球的问题诀策中，采取humidity较wind作为分类属性更佳，决策树由此而来。、ID3算法决策树的形成下图为ID3算法第一步后形成的部分决策树。这样综合起来看，就容易理解多了。1、overcast样例必为正，所以为叶子结点，总为yes；2、ID3无回溯，局部最优，而非全局最优，还有另一种树后修剪决策树。下图是ID3算法第一步后形成的部分决策树：如上图，训练样例被排列到对应的分支结点。分

10、支Overcast的所有样例都是正例，所以成为目标分类为Yes的叶结点。另两个结点将被进一步展开，方法是按照新的样例子集选取信息增益最高的属性。1.3、C4.5算法C4.5用信息增益率来选择属性。ID3选择属性用的是子树的信息增益。 1对非离散数据也能处理。 2能够对不完整数据进行处理针对上述第一点，解释下：一般来说率就是用来取平衡用的，就像方差起的作用差不多，比如有两个跑步的人，一个起点是10m/s的人、其10s后为20m/s；另一个人起速是1m/s、其1s后为2m/s。如果紧紧算差值那么两个差距就很大了，如果使用速度增加率(加速度，即都是为1m/s2)来衡量，2个人就是一样的加速度。因此，

11、C4.5克服了ID3用信息增益选择属性时偏向选择取值多的属性的不足。C4.5算法之信息增益率。一个可以选择的度量标准是增益比率gain ratio。增益比率度量是用前面的增益度量Gain(S，A)和分裂信息度量SplitInformation(S，A)来共同定义的，如下所示：其中，分裂信息度量被定义为(分裂信息用来衡量属性分裂数据的广度和均匀)：其中S1到Sc是c个值的属性A分割S而形成的c个样例子集。注意分裂信息实际上就是S关于属性A的各值的熵。这与我们前面对熵的使用不同，在那里我们只考虑S关于学习到的树要预测的目标属性的值的熵。、C4.5算法实现中的几个关键步骤在上文中，我们已经知道了决策

12、树学习C4.5算法中4个重要概念的表达，如下：一 Boosting 算法的起源boost 算法系列的起源来自于PAC Learnability(PAC 可学习性)。定义了学习算法的强弱弱学习算法-识别错误率小1/2(即准确率仅比随机猜测略高的学习算法)强学习算法-识别准确率很高并能在多项式时间内完成的学习算法二 Boosting算法的发展历史Boosting算法是一种把若干个分类器整合为一个分类器的方法。1）bootstrapping方法的主要过程主要步骤：i)重复地从一个样本集合D中采样n个样本ii)针对每次采样的子样本集，进行统计学习，获得假设Hiiii)将若干个假设进行组合，形成最终的假

13、设Hfinaliv)将最终的假设用于具体的分类任务2）bagging方法的主要过程 -bagging可以有多种抽取方法主要思路：i)训练分类器从整体样本集合中，抽样n* < N个样本 针对抽样的集合训练分类器Ciii)分类器进行投票，最终的结果是分类器投票的优胜结果. 现在的adaboost算法，其主要框架可以描述为：i)循环迭代多次更新样本分布寻找当前分布下的最优弱分类器计算弱分类器误差率ii)聚合多次训练的弱分类器三 Adaboost 算法AdaBoost 是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器，即弱分类器，然后把这些弱分类器集合起来，构造一个更强的最终分类器。

14、算法本身是改变数据分布实现的，它根据每次训练集之中的每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改权值的新数据送给下层分类器进行训练，然后将每次训练得到的分类器融合起来，作为最后的决策分类器。完整的adaboost算法如下简单来说，Adaboost有很多优点:1)adaboost是一种有很高精度的分类器2)可以使用各种方法构建子分类器，adaboost算法提供的是框架3)当使用简单分类器时，计算出的结果是可以理解的。而且弱分类器构造极其简单4)简单，不用做特征筛选5)不用担心overfitting！四 Adaboost 举例下面我们举一个简单的例子来看看ada

15、boost的实现过程：图中，“+”和“-”分别表示两种类别，在这个过程中，我们使用水平或者垂直的直线作为分类器，来进行分类。第一步：根据分类的正确率，得到一个新的样本分布D2,一个子分类器h1其中划圈的样本:被分错的。在右边:比较大的“+”表示对该样本做了加权.第二步：根据分类的正确率，得到一个新的样本分布D3，一个子分类器h2第三步：得到一个子分类器h3整合所有子分类器：因此可以得到整合的结果，从结果中看，及时简单的分类器，组合起来也能获得很好的分类效果，在例子中所有的。每次迭代都要把分错的点的权值变大这样也许提高错误点可以让后面的分类器权值更高.六 总结最后，我们可以总结下adaboost

16、算法的一些实际可以使用的场景：1）用于二分类或多分类的应用场景2）用于做分类任务的baseline无脑化，简单，不会overfitting，不用调分类器3）用于特征选择（feature selection)4）Boosting框架用于对badcase的修正只需要增加新的分类器，不需要变动原有分类器由于adaboost算法是一种实现简单，应用也很简单的算法。Adaboost算法通过组合弱分类器而得到强分类器，同时具有分类错误率上界随着训练增加而稳定下降，不会过拟合等的性质，应该说是一种很适合于在各种分类场景下应用的算法。Bootstrap方法基本思想是：因为观测样本包含了潜在样本的全部的信息，那

17、么我们不妨就把这个样本看做“总体”。那么相关的统计工作（估计或者检验）的统计量的分布可以从“总体”中利用Monte Carlo模拟得到。其做法概括为：既然样本是抽出来的，那我何不从样本中再抽样。bootstrap基本方法1、采用重抽样技术从原始样本中抽取一定数量（自己给定）的样本，此过程允许重复抽样。2、根据抽出的样本计算给定的统计量T。3、重复上述N次（一般大于1000），得到N个统计量T。其均值可以视作统计量T的估计。4、计算上述N个统计量T的样本方差，得到统计量的方差。上述的估计我们可以看成是Bootstrap的非参数估计形式，它基本的思想是用频率分布直方图来估计概率分布。当然Boots

18、trap也有参数形式，在已知分布下，我们可以先利用总体样本估计出对应参数，再利用估计出的分布做Monte Carlo模拟，得到统计量分布的推断。值得一提的是，参数化的Bootstrap方法虽然不够稳健，但是对于不平滑的函数，参数方法往往要比非参数办法好，当然这是基于你对样本的分布有一个初步了解的基础上的。bootstrap推断与bootstrap置信区间Bootstrap估计偏差既然Bootstrap将获得的样本样本看成了”总体“，那么估计量T自然是一个无偏的估计，Bootstrap数据集构造的”样本“的统计量T与原始估计量T的偏差自然就是估计量偏差的一个很好的估计。具体做法是：1. 从原始样

19、本x 1 ,x n 中有放回的抽取n个样本构成一个Bootstrap数据集，重复这个过程m次，得到m个数据集。2. 对于每个Bootstrap数据集，计算估计量T的值，记为T j 。3. T j 的均值是T的无偏估计，而其与T的差是偏差的估计。利用Bootstrap估计方差估计量T的方差的估计可以看做每个Bootstrap数据集的统计量T的值的方差。以我们遗留的问题，求1到100中随机抽取10个数的中位数的方差为例来说明。plain view plaincopyprint?n <- 10 x <- sample(1:100, size = n) Mboot <- replic

20、ate(1000, expr = y <- sample(x, size = n, replace = TRUE) median(y) ) print(var(Mboot) n <- 10x <- sample(1:100, size = n)Mboot <- replicate(1000, expr = y <- sample(x, size = n, replace = TRUE) median(y)print(var(Mboot)# 1 334.2这个应该是一个正确的估计了。Efron指出要得到标准差的估计并不需要非常多的Bootstrap数据集（m不需要过

21、分的大），通常50已经不错了，m>200是比较少见的（区间估计可能需要多一些）相关数据的Bootstrap推断回归数据的Bootstrap推断对于相关数据的Bootstrap推断，我们常用的方法有配对的Bootstrap（paired Bootstrap）与残差法。先说paired Bootstrap，它的基本想法是，对于观测构成的数据框，虽然观测的每一行数据是相关的，但是每行是独立的，我们Bootstrap抽样，每次抽取一行，而不是单独的抽一个数即可。例如，数据集women列出了美国女性的平均身高与体重，我们以体重为响应变量，身高为协变量进行回归，得到回归系数的估计。使用paired

22、Bootstrap：plain view plaincopyprint?m <- 200 n <- nrow(women) beta <- numeric(m) for (b in 1:m) i <- sample(1:n, size = n, replace = TRUE) weight <- women$weighti height <- women$heighti betab <- lm(weight height)$coef2 cat("the estimate of beta is", lm(weight height,

23、data = women)$coef2, "paired bootstrap estimate is", mean(beta) m <- 200n <- nrow(women)beta <- numeric(m)for (b in 1:m) i <- sample(1:n, size = n, replace = TRUE) weight <- women$weighti height <- women$heighti betab <- lm(weight height)$coef2cat("the estimate of

24、 beta is", lm(weight height, data = women)$coef2, "paired bootstrap estimate is", mean(beta)# the estimate of beta is 3.45 paired bootstrap estimate is 3.452plain view plaincopyprint?cat("the bias is", lm(weight height, data = women)$coef2 - mean(beta), "the stand error

25、 is", sd(beta) cat("the bias is", lm(weight height, data = women)$coef2 - mean(beta), "the stand error is", sd(beta)# the bias is -0.002468 the stand error is 0.126我们可以看到，估计量是无偏的，但是这个办法估计的方差变化较小，可能导致区间估计是不够稳健。残差法：1. 由观测数据拟合模型.2. 获得响应y i 与残差 i 3. 从残差数据集中有放回的抽取残差，构成Bootstrap残差

26、数据集 i （这是近似独立的）4. 构造伪响应Y i =y i + i 5. 对x回归伪响应Y，得到希望得到的统计量，重复多次，得到希望的统计量的经验分布，利用它做统计推断我们将women数据集的例子利用残差法在做一次，R代码如下：plain view plaincopyprint?lm.reg <- lm(weight height, data = women) y.fit <- predict(lm.reg) y.res <- residuals(lm.reg) y.bootstrap <- rep(1, 15) beta <- NULL for (p in

27、1:100) for (i in 1:15) res <- sample(y.res, 1, replace = TRUE) y.bootstrapi <- y.fiti + res betap <- lm(y.bootstrap women$height)$coef2 cat("the estimate of beta is", lm(weight height, data = women)$coef2, "paired bootstrap estimate is", mean(beta) lm.reg <- lm(weight

28、 height, data = women)y.fit <- predict(lm.reg)y.res <- residuals(lm.reg)y.bootstrap <- rep(1, 15)beta <- NULLfor (p in 1:100) for (i in 1:15) res <- sample(y.res, 1, replace = TRUE) y.bootstrapi <- y.fiti + res betap <- lm(y.bootstrap women$height)$coef2cat("the estimate of

29、 beta is", lm(weight height, data = women)$coef2, "paired bootstrap estimate is", mean(beta)# the estimate of beta is 3.45 paired bootstrap estimate is 3.436plain view plaincopyprint?cat("the bias is", lm(weight height, data = women)$coef2 - mean(beta), "the stand error

30、 is", sd(beta) cat("the bias is", lm(weight height, data = women)$coef2 - mean(beta), "the stand error is", sd(beta)# the bias is 0.01436 the stand error is 0.08561可以看到，利用残差法得到的方差更为稳健，做出的估计也更为的合理。这里需要指出一点，Bootstrap虽然可以处理相关数据蒙特卡洛方法与定积分计算本文讲述一下蒙特卡洛模拟方法与定积分计算，首先从一个题目开始：设0f(x)1

31、，用蒙特卡洛模拟法求定积分J=f(x)dx 的值。随机投点法设(X,Y) 服从正方形 0x1,0y1 上的均匀分布，则可知 X,Y 分别服从0,1上的均匀分布，且X,Y 相互独立。记事件A=Yf(X) ，则A 的概率为P(A)=P(Yf(X)= 1 0 f(x) 0 dydx= 1 0 f(x)dx=J 即定积分J 的值 就是事件A 出现的频率。同时，由伯努利大数定律，我们可以用重复试验中A 出现的频率作为 p 的估计值。即将(X,Y) 看成是正方形0x1,0y1 内的随机投点，用随机点落在区域yf(x) 中的频率作为定积分的近似值。这种方法就叫随机投点法，具体做法如下： 1、首先产生服从 0

32、,1 上的均匀分布的2n 个随数（n 为随机投点个数，可以取很大： n=104 ）并将其配对。2、对这n 对数据 (x(i),y(i) ),i=1,2,n记录满足不等式y i f(x(i) ) 的个数，这就是事件A发生的频数(n) ，由此可得事件A 发生的频率 (n)/ n ，则J (n)/ n 。举一实例，譬如要计算，模拟次数n=10 4 时，R代码如下：n=104; x=runif(n); y=runif(n);f=function(x) exp(-x2/2)/sqrt(2*pi) mu_n=sum(y<f(x); J=mu_n/n; J模拟次数 n=10 5 时，令n=10 5 ,

33、其余不变。精确值用integrate(f,0,1)求得2 a,b 上的定积分 首先，做线性变换令 y=(xa)/(ba) ，此时，x=(ba)y+a , 进一步如果在区间a,b 上有cg(x)d ，令则0f(y)1 。此时，可以得到 求定积分 ,a=2, b=5 c=ming(x)|2x5, d=maxg(x)|2x5，由于在 在2,5 上时单调减函数，所以c=g(5),d=g(2) ，S0=(ba)(dc) 。R中代码为a=2; b=5; g=function(x) exp(-x2/2)/sqrt(2*pi); f=function(y) (g(a+(b-a)*y)-c)/(d-c); c=

34、g(5);d=g(2);s_0=(b-a)*(d-c); n=104; x=runif(n);y=runif(n); mu_n=sum(y<=f(x); J=mu_n/n;J_0=s_0*J+c*(b-a);：精确值用integrate(g,2,5)求得)平均值法蒙特卡洛模拟法计算定积分时还有另一种方法，叫平均值法。这个原理也很简单：设随机变量 X 服从0,1 上的均匀分布，则Y=f(X) 的数学期望为 所以估计J 的值就是估计f(X) 的数学期望值。由辛钦大数定律，可以用f(X) 的观察值的均值取估计f(X) 的数学期望。具体做法：先用计算机产生n 个服从0,1 上均匀分布的随机数：x

35、(i),i=1,2,n 。对每一个x(i)，计算f(x(i) 。计算譬如，计算，R中的代码为n=104; x=runif(n); f=function(x) exp(-x2/2)/sqrt(2*pi) J=mean(f(x);Bootstraping: 名字来自成语“pull up by your own bootstraps”，意思是依靠你自己的资源，称为自助法，它是一种有放回的抽样方法，它是非参数统计中一种重要的估计统计量方差进而进行区间估计的统计方法。其核心思想和基本步骤如下：（1） 采用重抽样技术从原始样本中抽取一定数量（自己给定）的样本，此过程允许重复抽样。 （2） 根据抽出的样本计

36、算给定的统计量T。 （3） 重复上述N次（一般大于1000），得到N个统计量T。 （4） 计算上述N个统计量T的样本方差，得到统计量的方差。应该说Bootstrap是现代统计学较为流行的一种统计方法，在小样本时效果很好。通过方差的估计可以构造置信区间等，其运用范围得到进一步延伸下列方法都是上述Bootstraping思想的一种应用。bagging：bootstrap aggregating的缩写。让该学习算法训练多轮，每轮的训练集由从初始的训练集中随机取出的n个训练样本组成，某个初始训练样本在某轮训练集中可以出现多次或根本不出现，训练之后可得到一个预测函数序列h_1， h_n ，最终的预测函数

37、H对分类问题采用投票方式，对回归问题采用简单平均方法对新示例进行判别。训练R个分类器f_i，分类器之间其他相同就是参数不同。其中f_i是通过从训练集合中(N篇文档)随机取(取后放回)N次文档构成的训练集合训练得到的。对于新文档d，用这R个分类器去分类，得到的最多的那个类别作为d的最终类别。boosting: 其中主要的是AdaBoost（Adaptive Boosting）。初始化时对每一个训练例赋相等的权重1n，然后用该学算法对训练集训练t轮，每次训练后，对训练失败的训练例赋以较大的权重，也就是让学习算法在后续的学习中集中对比较难的训练例进行学习，从而得到一个预测函数序列h_1, h_m , 其中h_i也有一定的权重，预测效果好的预测函数权重较大，反之较小。最终的预测函数H对分类问题采用有权重的投票方式，对回归问题采用加权平均的方法对新示例进行判别。（类似Bagging方法，但是训练是串行进行的，第k个分类器训练时关注对前k-1分类器中错分的文档，即不是随机取，而是加大取这些文档的概率。)（pku， sewm，shinningmonster.）Bagging与Boosting的区别：二者的主要区别是取样方式不同。Bagging采用均匀取样，而Boosting根据错误率来取样，因此