统计计算算法

《统计计算算法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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

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

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

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

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

6、反例（我们采用记号[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的子集。换句话来讲，