监督学习算法学习笔记.docx

监督学****br/>基本概念
监督学****又称为分类(Classification)或者归纳学****Inductive Learning)。几乎适用于所有领域,包括文本和网页处理。给出一个数据集D,机器学****的目标就是产生一个联系属性值集合A和类标集合C的分类/预测函数(Classification/Prediction Function),这个函数可以用于预测新的属性集合的类标。这个函数又被称为分类模型(Classification Model)、预测模型(Prediction Model)。这个分类模型可以是任何形式的,例如决策树、规则集、贝叶斯模型或者一个超平面。
在监督学****Supervised Learning)中,已经有数据给出了类标;与这一方式相对的是无监督学****Unsupervised Learning),在这种方式中,所有的类属性都是未知的,算法需要根据数据集的特征自动产生类属性。算法用于进行学****的数据集叫做训练数据集,当使用学****算法用训练数据集学****得到一个模型以后,我们使用测试数据集来评测这个模型的精准度。
机器学****的最基本假设是:训练数据的分布应该与测试数据的分布一致。
决策树推理
什么是决策树
决策树学****算法是分类算法中最广泛应用的一种技术,这种算法的分类精度与其他算法相比具有相当的竞争力,并且十分高效。例如,对于表2-1所示的贷款申请的数据集,可以学****到一种决策树结构,表示为图2-1。
表2-1 贷款申请数据
根据数据集建立的一种决策树结构如下:
图2-1 对应与表2-1的决策树
树中包含了决策点和叶子节点,决策点包含针对数据实例某个属性的一些测试,而一个叶子节点则代表了一个类标。
一棵决策树的构建过程是不断的分隔训练数据,以使得最终分隔所得到的各个子集尽可能的纯。一个纯的子集中的数据实例类标全部一致。
决策树的建立并不是唯一的,在实际中,我们希望得到一棵尽量小且准确的决策树。
学****算法
学****算法就是使用分治策略,第贵的对训练数据进行分隔,从而构造决策树。递归的终止条件在算法的1~4行,当所有的节点中的数据都属于同一个类时,迭代终止。学****算法中,每一个后续的递归都选择最佳分类属性作为分隔当前数据实例集的属性。最佳分类属性等的选择通过混杂度函数(Impurity Function)来实现,这个函数反映了用该属性进行数据分隔以后的数据集的混杂度。决策树学****算法如图2-2所示。
图2-2 决策树学****算法
该算法最核心的思想就是选择能最大限度降低类别混杂度的属性作为决策点。其中的第7行使用熵的公式计算:

熵在这里代表一个集合的无序程度,集合中的熵偏小,说明该集合中的大部分元素都是同质的。
第9行计算划分后的熵大小。采用如下公式:

其中v是划分后子集的个数。
信息增益计算公式如下:

信息增益用来衡量混杂度的减少量。算法第11行进行这个操作,选择最大的使得混杂度的减少量达到最大。
分类器的评估标准
主要的评估标准就是分类精度,它是用在测试集中被正确分类的数据数量除以测试集中的数据数量得到。
在一些实际应用中,我们仅对数量占少数的类别感兴趣,那些用户感兴趣的类别通常称为正例类别,其他类别称为负例类别。
查准率、查全率和F-score是评价分类器的三个常用指标,通过混合矩阵,我们可以很方便地得到查准率和查全率两个数据,混合矩阵(如表3-1)中包含数据的真实情况和分类器的预测结果。
表3-1 分类器的混合矩阵
分类器认为是正例
分类器认为是负例
实际上为正例
TP
FN
实际上为负例
FP
TN
根据上述混合矩阵,正例类别的分类查准率(p)和查全率(r)定义如下

尽管查准率和查全率理论上是不相关的,但是在实际应用中,高查准率往往实在牺牲查全率的情况下得到的。同样,高查全率是在牺牲高查准率的情况下得到的。在实际应用中到底哪个标准更重要取决于这个应用,如果仅用一个指标来衡量分类器的性能,此时常使用F-score:

F-score是查全率和查准率的调和平均值。两个数值的调和平均值更加倾向于两个数当中较小的那个。因此,如果想得到较高的F-score,则p和r都必须很高。
朴素贝叶斯分类
准备知识
条件概率:设A, B是两个事件,且称为在条件A下发生的条件事件B发生的条件概率。
乘法公式: 设则有
全概率公式:设随机事件A1,A2,...,An以及 B满足:(1) A1,A2,…,An两两互不相容;(2)或者;(3) (n=1,2,…),则有,称为全概率公式。
全概率公式的应用:把事件B看作是某一个过程的结果,把A1,A2,…,An看作该过程的若干个原因,根据历史资料,每个原因发生的概率已知(即Pr(Ai)已知),且每一个原因对结