Differences

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

--- keynote:lesson02 [2010/03/26 21:00]
10921007
+++ keynote:lesson02 [2021/04/13 21:35]
@@ 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）
-<note important> Revised by Li Xin （李昕）, <lixin@zjucadcg.com> </note>
-===== 2.3 朴素贝叶斯分类 =====
-问题是如何基于数据的观测值，给出结果的预测，如已知某天关于天气、温度、风等情况的观测（X的值），预测运动员是否进行训练（Y的值）
-即要计算P(Y|X)
-根据贝叶斯公式：
-<note>$P(Y|X) = \frac{P(X)P(Y|X)}{P(Y)}$</note>
-于是我们需要计算P(X),P(Y|X)即可
-构造一个分类器（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)$，取概率最大的结果作为分类结果
-===== 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最大的超平面就是最优的超平面。
-  -很多时候数据集并不是线性可分的，也就是说找不到合适的超平面把数据集严格的分成两类，这是有两种方法：
-    -引入训练误差，即允许少量数据点被分在错误的类。
-    -使用非线性的分类方式，也就是高维可分。
-====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