Differences

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

--- keynote:lesson02 [2010/03/26 21:18]
10921007
+++ keynote:lesson02 [2010/05/24 15:37]
10921038 微小改变，Bayes公式错了
@@ Line 74: / Line 74: @@
 	٧（Outlook=Rain ٨ Wind=Weak）
 则得到的结果如下图所示\\
-{{:keynote:decisiontree1.jpg|}}
+{{:keynote:decisiontree1.jpg|}}\\
 归纳的主循环可以按如下步骤进行：
   * A←Attributes中分类Examples能力最好的属性
@@ Line 80: / Line 80: @@
   * 对于A的每个可能值vi
   * 在Root下加一个新的分支对应测试A= vi
-  * 令Examples==== vi ====
+  * 将训练样本排序后，依次添加到叶子节点上。
-为Examples中满足A属性值为vi的子集
+  * 如果所有的训练样本都被完美的分类，那么结束
-  * 如果 为空
+  * 否则迭代执行上面的循环
-  * 在这个新分支下加一个叶子结点，结点的label=Examples中最普遍的Target_attribute值
-  * 否则在这个新分支下加一个子树ID3（ , Target_attribute, Attributes-{A}）
+那么，哪个属性是最佳的分类属性呢？\\
+这就需要用到“奥坎姆剃刀”原则\\
+**奥坎姆剃刀**：优先选择拟合数据的最简单假设。\\
+这是一个心理学问题，哲学家们以及其他学者已经对这样的问题争论几个世纪了，而且这个争论至今还未解决。\\
+决策树遵照这个原则：**较短的树比较长的优先**\\
+那么怎么确定一个属性能够较好的划分训练数据呢？这就用到了信息论(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>
@@ Line 94: / 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$
@@ Line 112: / Line 132: @@
+<note important> Revised by Bin Xu(徐斌), <xu_bin@zju.edu.cn> </note>
 ===== 2.4 支持向量机(SVM) =====
@@ Line 123: / Line 144: @@
   -注意到一般情况下这种超平面会有无数多个可能，所以定义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的应用====

Applied Mathematics for Computer Science

User Tools

Site Tools

Differences

Page Tools