This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
keynote:lesson02 [2010/03/26 20:34] 10921007 |
keynote:lesson02 [2023/08/19 21:02] (current) |
||
---|---|---|---|
Line 16: | Line 16: | ||
|4 |Sunny |Warm |High |Strong |Cool |Change |Yes | | |4 |Sunny |Warm |High |Strong |Cool |Change |Yes | | ||
**实例空间X**:概念是定义在一个实例集合上的,本例中X是所有可能的日子,而Sky,AirTemp之类是日子的属性;\\ | **实例空间X**:概念是定义在一个实例集合上的,本例中X是所有可能的日子,而Sky,AirTemp之类是日子的属性;\\ | ||
- | **目标函数C**:代学习的函数,可以是定义在实例集X上的任意布尔函数,形式化为C:X->{0,1};\\ | + | **目标函数C**:待学习的函数,可以是定义在实例集X上的任意布尔函数,形式化为C:X->{0,1};\\ |
**训练样本D**:是为学习概念而提供的训练实例,训练样本中的每一个条目为X中的一个实例加上此实例对应的目标函数的值C(x);\\ | **训练样本D**:是为学习概念而提供的训练实例,训练样本中的每一个条目为X中的一个实例加上此实例对应的目标函数的值C(x);\\ | ||
**假设空间H**:所有可能假设的集合,它中的每一个假设h表示X上定义的布尔函数,即h:X->{0,1};\\ | **假设空间H**:所有可能假设的集合,它中的每一个假设h表示X上定义的布尔函数,即h:X->{0,1};\\ | ||
Line 64: | Line 64: | ||
决策树通过把实例从根结点排列(sort)到某个叶子结点来分类实例,叶子结点即为实例所属的分类。树上的每一个结点指定了对实例的某个属性(attribute)的测试,并且该结点的每一个后继分支对应于该属性的一个可能值。分类实例的方法是从这棵树的根结点开始,测试这个结点指定的属性,然后按照给定实例的该属性值对应的树枝向下移动。这个过程再在以新结点为根的子树上重复。\\ | 决策树通过把实例从根结点排列(sort)到某个叶子结点来分类实例,叶子结点即为实例所属的分类。树上的每一个结点指定了对实例的某个属性(attribute)的测试,并且该结点的每一个后继分支对应于该属性的一个可能值。分类实例的方法是从这棵树的根结点开始,测试这个结点指定的属性,然后按照给定实例的该属性值对应的树枝向下移动。这个过程再在以新结点为根的子树上重复。\\ | ||
{{:keynote:decisiontree.jpg|}}\\ | {{:keynote:decisiontree.jpg|}}\\ | ||
+ | **图2-1 概念PlayTennis的决策树**\\ | ||
+ | 分类一个样例的方法是,将其沿根结点排列到合适的叶子结点,然后返回与这个叶子结点关联的分类(本例中为Yes或No)。这棵决策树根据天气分类“星期六上午是否适合打网球”。\\ | ||
+ | 图2-1画出了一棵典型的学习到的决策树。这棵决策树根据天气情况分类“星期六上午是否适合打网球”。例如,下面的实例:\\ | ||
+ | < Outlook=Sunny,Temperature=Hot,Humidity=High,Wind=Strong > | ||
+ | 将被沿着这棵决策树的最左分支向下排列,因而被评定为反例(也就是这棵树预测这个实例PlayTennis=No)。这棵树以及表3-2中用来演示ID3学习算法的例子摘自(Quinlan 1986)。\\ | ||
+ | 通常决策树代表实例属性值约束的合取(conjunction)的析取式(disjunction)。从树根到树叶的每一条路径对应一组属性测试的合取,树本身对应这些合取的析取。例如,图2-1表示的决策树对应于以下表达式: | ||
+ | (Outlook=Sunny ٨ Humidity=Normal) | ||
+ | ٧(Outlook=Overcast) | ||
+ | ٧(Outlook=Rain ٨ Wind=Weak) | ||
+ | 则得到的结果如下图所示\\ | ||
+ | {{:keynote:decisiontree1.jpg|}}\\ | ||
+ | 归纳的主循环可以按如下步骤进行: | ||
+ | * A←Attributes中分类Examples能力最好的属性 | ||
+ | * Root的决策属性←A | ||
+ | * 对于A的每个可能值vi | ||
+ | * 在Root下加一个新的分支对应测试A= vi | ||
+ | * 将训练样本排序后,依次添加到叶子节点上。 | ||
+ | * 如果所有的训练样本都被完美的分类,那么结束 | ||
+ | * 否则迭代执行上面的循环 | ||
- | <note important> lixin@zjucadcg.cn </note> | + | 那么,哪个属性是最佳的分类属性呢?\\ |
+ | 这就需要用到“奥坎姆剃刀”原则\\ | ||
+ | **奥坎姆剃刀**:优先选择拟合数据的最简单假设。\\ | ||
+ | 这是一个心理学问题,哲学家们以及其他学者已经对这样的问题争论几个世纪了,而且这个争论至今还未解决。\\ | ||
+ | 决策树遵照这个原则:**较短的树比较长的优先**\\ | ||
+ | 那么怎么确定一个属性能够较好的划分训练数据呢?这就用到了信息论(information theory)\\ | ||
+ | 信息论是一个数学分支,由Claude shannon在20世纪40年代创建。信息论是一门用数理统计方法来研究信息的度量、传递和变换规律的科学。它主要是研究通讯和控制系统中普遍存在着信息传递的共同规律以及研究最佳解决信息的获限、度量、变换、储存和传递等问题的基础理论。\\ | ||
+ | 信息就是不确定性的减少,并获取新的知识。\\ | ||
+ | **信息是确定性的增加**----逆Shannon信息定义。\\ | ||
+ | 一个事件的信息量与它出现的概率最为相关。在信息论中,使用的基本单位是位(**bits**)。\\ | ||
+ | 如果一个确定发生的事件发生了,那么确定性没有任何变化,所以得到的信息为0。而如果小概率的事件发生了,那么将得到比可能发生的事情更多的信息量。所以信息量与事件发生的概率成反比。\\ | ||
+ | 举例来说:设字母表为{$S_1,S_2,S_3,。。。S_n$} | ||
+ | 那么每个符号$S_i$的概率为$P(S_i)=P_i(P_i>=0 且 \sum_{i=1}^{n}P_i=1)$\\ | ||
+ | 对两个不相关的事件来说,I($S_iS_j)=I(S_i)+I(S_j)$\\ | ||
+ | P($S_iS_j)=P(S_i)P(S_j)$ | ||
+ | 从这两个关系式中可以看出,I($S_i$)应该以P($S_i$)对数形式给出,所以有\\ | ||
+ | I($S_i$)=-$log_2P_i$\\ | ||
+ | 所以每个符号的平均信息是 $E_t=-\sum_{i=1}^{M}P_ilog_2P_i$ | ||
+ | 这就是“熵”\\ | ||
+ | 用熵建立一个信息增量的方程\\ | ||
+ | {{:keynote:infogain.jpg|}}\\ | ||
+ | 信息增量最大的属性就是最佳的属性\\ | ||
+ | <note important> Revised by Li Xin (李昕), <lixin@zjucadcg.com> </note> | ||
===== 2.3 朴素贝叶斯分类 ===== | ===== 2.3 朴素贝叶斯分类 ===== | ||
Line 73: | Line 114: | ||
根据贝叶斯公式: | 根据贝叶斯公式: | ||
- | <note>$P(Y|X) = \frac{P(X)P(Y|X)}{P(Y)}$</note> | + | <note>$P(Y|X) = \frac{P(Y)P(X|Y)}{P(X)}$</note> |
- | 于是我们需要计算P(X),P(Y|X)即可 | + | 于是我们需要计算P(Y),P(X|Y)即可 |
构造一个分类器(Naive Beyes Classifier),即目标函数$f:X \to Y$ | 构造一个分类器(Naive Beyes Classifier),即目标函数$f:X \to Y$ | ||
Line 91: | Line 132: | ||
+ | <note important> Revised by Bin Xu(徐斌), <xu_bin@zju.edu.cn> </note> | ||
===== 2.4 支持向量机(SVM) ===== | ===== 2.4 支持向量机(SVM) ===== | ||
Line 102: | Line 144: | ||
-注意到一般情况下这种超平面会有无数多个可能,所以定义margin:超平面距离两类数据集中最近的点的和。使得margin最大的超平面就是最优的超平面。 | -注意到一般情况下这种超平面会有无数多个可能,所以定义margin:超平面距离两类数据集中最近的点的和。使得margin最大的超平面就是最优的超平面。 | ||
-很多时候数据集并不是线性可分的,也就是说找不到合适的超平面把数据集严格的分成两类,这是有两种方法: | -很多时候数据集并不是线性可分的,也就是说找不到合适的超平面把数据集严格的分成两类,这是有两种方法: | ||
- | -引入训练误差,即允许少量数据点被分在错误的类。 | + | -引入训练误差,即允许少量数据点被分在错误的类。详细来说就是加入一些松弛变量 (slack variables) $\xi_i$ ,使得数据 $x_i$ 即使不能被超平面线性分割而是有 $\xi_i$ 那么大的误差也是允许的,同时,为了避免无限制的松弛,将 slack variables 也加入需要最小化的目标函数中,并(通常)使用一个参数 $C$ 来控制原本的目标函数和松弛变量的权重,即加入 $C\sum_{i=1}^l\xi_i$ 这样一项。 |
- | -使用非线性的分类方式,也就是高维可分。 | + | -使用非线性的分类方式,也就是高维可分。这是通过 Kernel 方法来实现,具体来说,在原始空间中无法线性可分的数据,我们希望通过一个映射 $\Phi(\cdot)$ 将原始空间中的数据映射到一个更高维度(甚至是无穷维度)的空间中。这样的做法的可行性在于考虑到 SVM (以及许多相关线性算法)中使用数据的方式仅仅是依靠于数据之间的内积 $<x_i,x_j>$ ,而我们可以通过核方法直接使用低维的数据计算出高维空间中映射后的数据点的内积:$K(x_i,x_j) = <\Phi(x_i),\Phi(x_j)>_\mathcal{H}$ (其中 $<\cdot,\cdot>_\mathcal{H}$ 表示在高维空间 $\mathcal{H}$ 中的内积)。通过这样的方法,就能有效地解决了线性不可分的问题。 |
+ | |||
+ | <note important> | ||
+ | Extended by //[[pluskid@gmail.com|张弛原]] 2010/04/26 13:28// | ||
+ | </note> | ||
====2.4.3 SVM的应用==== | ====2.4.3 SVM的应用==== | ||
Line 123: | Line 169: | ||
==== 2.5.1 Boosting 算法概述 ==== | ==== 2.5.1 Boosting 算法概述 ==== | ||
- | Boosting算法的形式多种多样,通常都是由多个弱分类器在一定的分布下通过循环迭代,最后组成形成一个强分类器的。当这些弱分类器被组合在一起的时候,它们总是会根据各自的准确度而在组合中占一定的权重。当一个弱分类器被加进来时,所有的数据都被重新赋予权重:那些被分错的点的权重会上升,而分对的点的权重则会下降。因此,接下来,分类器会着重注意对待之前被分错类的点。 | + | Boosting算法的形式多种多样,通常都是由多个弱分类器在一定的分布下通过循环迭代,最后组合形成一个强分类器的。当这些弱分类器被组合在一起的时候,它们总是会根据各自的准确度而在组合中占一定的权重。当一个弱分类器被加进来时,所有的数据都被重新赋予权重:那些被分错的点的权重会上升,而分对的点的权重则会下降。因此,接下来,分类器会着重注意对待之前被分错类的点。 |
==== 2.5.2 AdaBoost 算法介绍 ==== | ==== 2.5.2 AdaBoost 算法介绍 ==== |