Differences

This shows you the differences between two versions of the page.

--- keynote:lesson02 [2014/05/22 16:34]
+++ keynote:lesson02 [2023/08/19 21:02] (current)
@@ Line 1: / Line 1: @@
+====== 第二课 数据分类方法 ======
+===== 2.1 概念学习 =====
+==== 2.1.1 基本概念====
+**概念学习**是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数的值，或者说，是给定某一类别的若干正例和反例，从中获得该类别的一般定义，它在预定的假设空间中搜索假设，使其与训练样例有最佳的拟合度。\\
+**举例介绍（通过例子介绍概念学习中的相关术语）**\\
+通过以下的训练数据集来学习使EnjoySport=yes的日子:\\
+^ Example ^Sky    ^AirTemp   ^Humidity ^Wind    ^Water  ^Forecast  ^EnjoySport ^
+|1        |Sunny  |Warm      |Normal   |Strong  |Warm   |Same      |Yes     |
+|2        |Sunny  |Warm      |High     |Strong  |Warm   |Same      |Yes     |
+|3        |Rainy  |Cold      |High     |Strong  |Warm   |Change    |No      |
+|4        |Sunny  |Warm      |High     |Strong  |Cool   |Change    |Yes     |
+**实例空间X**：概念是定义在一个实例集合上的，本例中X是所有可能的日子，而Sky,AirTemp之类是日子的属性;\\
+**目标函数C**：待学习的函数，可以是定义在实例集X上的任意布尔函数,形式化为C:X->{0,1};\\
+**训练样本D**：是为学习概念而提供的训练实例，训练样本中的每一个条目为X中的一个实例加上此实例对应的目标函数的值C(x);\\
+**假设空间H**：所有可能假设的集合，它中的每一个假设h表示X上定义的布尔函数，即h：X->{0,1};\\
+     注：机器学习要做的就是拟合出h，使h(x)=c(x)
+**归纳学习假设**：任一假设如果在足够大的训练样例集中很好的逼近目标函数，它也能在未见实例中很好的逼近目标函数。\\
+**一般到特殊序**：如果对于假设h<sub>1</sub>和h<sub>2</sub>,任何被h<sub>1</sub>划分为正例的实例都会被h<sub>2</sub>为分为正例，我们说h<sub>2</sub>比h<sub>1</sub>更一般（h<sub>2</sub> >= h<sub>1</sub>）\\
+**变型空间**：是H中与训练样例D一致的所有假设构成的集合，为H的子集表示为VS<sub>H,D</sub> //(个人以为引入**变型空间**的概念更容易理解假设空间H的结构和之后的列表后消除算法)//
+==== 2.1.2 算法介绍====
+  - **FIND-S:寻找最大特殊假设**\\
+    - 算法思想：从H中最特殊的假设开始，然后在该假设覆盖正实例失败时将其一般化。
+    - 算法步骤：
+      -将h初始化为H中最特殊的假设
+      -对每个正实例x，对h的每个属性约束a<sub>i</sub>,如果x满足a<sub>i</sub>,那么不做任何处理，否则将h中a<sub>i</sub>替换为x满足的下一个更一般约束
+      -输出假设h
+    -算法举例：{{:keynote:find-s.jpg?50*50}}
+  -**LIST_THEN_ELIMATION:列表后消除算法**
+    -算法思想：将变型空间初始化为包含H中所有的假设，然后从中去除与任一训练样例不一致的假设。
+    -算法步骤：
+      -变型空间包含H中所有假设的列表
+      - 对每个训练样例<x,c(x)>,从变形空间中移出所有h(x)!=C(x)的假设h
+      - 输出假设//**空间中的假设列表(输出的是一个集合)**//
+    - 算法举例：{{:keynote:list_then_elimination.jpg?50*50}}
+  -**CANDIDATE-ELIMINATION:候选消除算法**
+     -算法思想：类似前两种算法的结合
+     -算法步骤：
+       -将G初始化为最一般的假设，将S初始化为最特殊的假设
+       -对每个训练样例d，进行如下操作
+         -如果d是正例，对S使用FIND_S类似算法，但是我们要确保G必须比S更一般，否则就应该删除G中相应的项。
+         -如果d是反例，对G使用LIST_THEN_ELIMINATION类似算法
+     -算法举例：{{:keynote:1.jpg?50*50}}{{:keynote:2.jpg?50*50}}{{:keynote:3.jpg?50*50}}{{:keynote:4.jpg?50*50}}
+==== 2.1.3 概念学习的方法小结====
+  *概念学习可以看作室在预定义的假设空间中进行搜索的过程
+  *从一般到特殊的偏序假设，使我们可以使用更加有效地搜索方式，例如：候选消除算法
+  *实际的概念学习的方法必须是有归纳偏差的，否则他们只能被用来分类观察样本
+  *变形空间和候选消除算法为概念学习提供了很有用的框架，然而，他们的正确性必须要求正确的训练数据集和有能够表达未知目标概念的假设。\\
+<note important> Revised by Duanjin Chen(陈端金), <chenduanjin@zjucadcg.cn> </note>
+===== 2.2 决策树 =====
+决策树学习是一种逼近离散值目标函数的方法，在这种方法中学习到的函数被表示为一棵决策树。这种学习算法是最流行的归纳推理算法之一，是一种从一般到特殊的算法。\\
+下面的数据是一个测试用例，根据各种条件决定是否打网球。\\
+{{:keynote:playtennis.jpg|}}\\
+决策树通过把实例从根结点排列（sort）到某个叶子结点来分类实例，叶子结点即为实例所属的分类。树上的每一个结点指定了对实例的某个属性（attribute）的测试，并且该结点的每一个后继分支对应于该属性的一个可能值。分类实例的方法是从这棵树的根结点开始，测试这个结点指定的属性，然后按照给定实例的该属性值对应的树枝向下移动。这个过程再在以新结点为根的子树上重复。\\
+{{: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
+  * 将训练样本排序后，依次添加到叶子节点上。
+  * 如果所有的训练样本都被完美的分类，那么结束
+  * 否则迭代执行上面的循环
+那么，哪个属性是最佳的分类属性呢？\\
+这就需要用到“奥坎姆剃刀”原则\\
+**奥坎姆剃刀**：优先选择拟合数据的最简单假设。\\
+这是一个心理学问题，哲学家们以及其他学者已经对这样的问题争论几个世纪了，而且这个争论至今还未解决。\\
+决策树遵照这个原则：**较短的树比较长的优先**\\
+那么怎么确定一个属性能够较好的划分训练数据呢？这就用到了信息论(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 朴素贝叶斯分类 =====
+问题是如何基于数据的观测值，给出结果的预测，如已知某天关于天气、温度、风等情况的观测（X的值），预测运动员是否进行训练（Y的值）
+即要计算P(Y|X)
+根据贝叶斯公式：
+<note>$P(Y|X) = \frac{P(Y)P(X|Y)}{P(X)}$</note>
+于是我们需要计算P(Y),P(X|Y)即可
+构造一个分类器（Naive Beyes Classifier），即目标函数$f:X \to Y$
+我们要做的就是在X的属性观察值是X1、X2...Xn的时候，预测Y的值即：
+<note> $Y = argmax_{y_j \in Y} P(y_j|x_1,x_2,...,x_n)=argmax_{y_j \in Y} \frac{P(x_1,x_2,...,x_n|y_j)P(y_j)}
+{P(x_1,x_2,...,x_n)}$ </note>
+<note> $Y = argmax_{y_j \in Y} P(x_1,x_2,...,x_n|y_j)P(y_j)$ </note>
+假设观测值之间是相互独立的，那么
+<note>$P(x_1,x_2,...,x_n|y_j) = \prod_i{P(x_i|y_j)}$</note>
+而   $P(x_i|y_j)$   和   $P(y_j)$   可以通过给定的样本数据来估计出，并用估计值来计算每一个$P(y_j|x_1,x_2,...,x_n)$，取概率最大的结果作为分类结果
+<note important> Revised by Bin Xu(徐斌), <xu_bin@zju.edu.cn> </note>
+===== 2.4 支持向量机(SVM) =====
+==== 2.4.1 SVM的起源 ====
+上世纪90年代由Vapnik和他的同事开发，可以用于进行分类或回归分析. 与传统的神经网络方法相比，具有更好的普遍性和全局最优性.
+====2.4.2 什么是SVM====
+  -一组训练向量x<sub>i</sub>，把他们简单的分为两类。定义向量y<sub>i</sub>，当x<sub>i</sub>属于第一类时y<sub>i</sub>=0；当x<sub>i</sub>属于第二类时y<sub>i</sub>=1。称这个y为一个超平面，把数据集x<sub>i</sub>分成两类。
+  -注意到一般情况下这种超平面会有无数多个可能，所以定义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的应用====
+  -SVM是目前针对文本和基因数据分类问题的最有效的工具之一。
+  -SVM可以通过设计不同的核函数来完成复杂数据的分类，如图像数据，关系数据等等。
+  -SVM可以被扩展，用于回归分析，主成分分析等。
+  -优化SVM还是一件困难的工作，选择合适的核函数和参数没有很好的算法，只等采取不断尝试的方法。
+==== 2.4.4 SVM的开发工具 ====
+  -SVM-Light：http://svmlight.joachims.org
+  -LibSVM: http://www/cise.ntu.edt.tw/~cjlin/libsvm
+<note important> Revised by Yi Gao （高艺）, <qhgaoyi@gmail.com> </note>
+===== 2.5 Boosting =====
+==== 2.5.1 Boosting 算法概述 ====
+Boosting算法的形式多种多样，通常都是由多个弱分类器在一定的分布下通过循环迭代，最后组合形成一个强分类器的。当这些弱分类器被组合在一起的时候，它们总是会根据各自的准确度而在组合中占一定的权重。当一个弱分类器被加进来时，所有的数据都被重新赋予权重：那些被分错的点的权重会上升，而分对的点的权重则会下降。因此，接下来，分类器会着重注意对待之前被分错类的点。
+==== 2.5.2 AdaBoost 算法介绍 ====
+为不失一般性, 设$x$为输入数据，$y$表示输入数据的正负属性分类，其中设正类为1，负类为-1。给定$n$个数据点，即有$n$个$(x_{i},y_{i})$这样的点-属性对，其中$1 \le i \le n， i \in Z$. 进一步假设初始弱分类器的权重分布为平均分布，即初始输入数据的权重分布为$D_{1}(i)= \frac{1}{n}$，其中$ i=1,\cdots,m$
+由于AdaBoost是一个迭代递进算法,设循环迭代的计数$t=1,\cdots,T$. 我们的目的是找出在当前分布$D_{t}$下，使得分类错误最小的分类器$h_{t}$:
+\[ h_{t}= \mathop { \arg\min \epsilon_{j}} \limits_{h_{j}} \]
+其中
+\[ \epsilon_{j} = \sum_{i=1}^{n} D_{t}(i)[ y_{i} \neq h_{j}(x_{i}) ] \]
+每次迭代中, 我们需重新计算新的权重$\alpha_{t}$:
+\[ \alpha_{t} = \frac{1}{2} \ln \frac{1-\epsilon_{t}} {\epsilon_{t}} \]
+进而我们可以更新数据的权重分布
+\[ D_{t+1}(i)= \frac{D_{t}(i) \exp{ (-\alpha_{t} y_{i} {h_t}(x_{i}) )  }}{Z_{t}} \]
+其中$Z_{t}$是归一化的参数.
+由于$\sum_{i=1}^{n}D_{t+1}=1$所以
+\[ Z_{t}=\sum_{i=1}^{n}D_{t}(i) \exp{ (-\alpha_{t} y_{i} {h_t}(x_{i}) )  } \]
+可以看到，如果$y_{i}$与$h_{t}(x_{i})$的值相等的话，即当前分类器的决策是正确的，则相应的该点的权重会在下一轮迭代中下降；相反，如果$y_{i}$与$h_{t}(x_{i})$的值不相等的话，则他们符号相反，使得指数符号为正，从而使得该点的权重在下一轮迭代中上升。
+设\[f(x_{i})=\sum_{t=1}^{T} \alpha_{t} {h_t}(x_{i}) \]
+则最终的分类函数即为
+\[ H(x)=sign[f(x)] \]
+==== 2.5.3 AdaBoost 算法分析 ====
+设其最终错误函数为
+\[
+E= \frac{1}{n} \sum_{i=1}^{n}
+\begin{cases}
+& \text{if}\ y_{i} \neq H(x_{i}) \\
+& \text{otherwise}
+\end{cases}
+\]
+最小化错误，即最小化其上限
+\[ \frac{1}{n}\sum_{i=1}^{n} \exp{(-y_{i} f(x_{i}))} \]
+ 而根据
+\[ D_{t+1}(i)= \frac{D_{t}(i) \exp{ (-\alpha_{t} y_{i} {h_t}(x_{i}) )  }}{Z_{t}} \]
+我们可以得出
+\[ D_{t+1}(i) Z_{t}= D_{t}(i) \exp{ (-\alpha_{t} y_{i} {h_t}(x_{i}) ) }  \]
+\[ D_{T+1}(i) \prod_{t=1}^{T} Z_{t}= D_{1}(i) \exp{ \sum_{t=1}^{T}(-\alpha_{t} y_{i} {h_t}(x_{i}) ) }  \]
+\[ D_{T+1}(i) \prod_{t=1}^{T} Z_{t}= \frac{1}{n} \exp{( -y_{i} f(x_{i})) }  \]
+ 因此，我们的目标变成最小化
+\[ \prod_{t=1}^{T} Z_{t} \]
+因为$Z_{t}$可以表示成
+\[ Z_{t}=(1-\epsilon_{t} )\exp{(-\alpha_{t})} + \epsilon_{t} \exp{(-\alpha_{t})} \]
+取最小极值，即求偏导等于零
+\[ \frac{\partial Z_{t}}{\partial \alpha_{t}} = 0 \]
+我们可以得到
+\[ \alpha_{t} = \frac{1}{2}ln\frac{1-\epsilon_{t}}{\epsilon_{t}} \]
+这也就是在算法迭代过程中，$\alpha_{t}$取值的原因。
+==== 2.5.3 AdaBoost 算法应用 ====
+Adaboost算法已被广泛地应用于计算机视觉的人脸检测方法，目前这一算法已被包含于OpenCV程序包，可以方便通过调用来实现相关功能。
+<note important> Revised by Zhanying He（何占盈）, <hezhanying@zju.edu.cn> </note>

Applied Mathematics for Computer Science

User Tools

Site Tools

Differences

Page Tools