网络数据挖掘-L9 SVM 决策树

---

title: 网络数据挖掘-L9 SVM 决策树
date: 2017-07-26 11:48:56
categories: Datamining
mathjax: true
tags: [webDataMining]

---

L9 Decision Trees & SVM

Decision Trees：ID3算法-CSDN博客

决策树的构造思路

• Choose the best attribute(s) to split the remaining instances
  and make that attribute a decision node
• Repeat this process for recursively for each child
• Stop when:
  • All the instances have the same target attribute value
  • There are no more attributes
  • There are no more instances

ID3算法：

• 每次选择信息熵增益最大的属性来做决策
• 直到结束状态

所以需要引入两个概念：

• 信息熵：
  对于属性T，当前信息熵：
  S为需要决策的属性，如yes no
  Entropy(S)=\sum -P_s * \log_2 P_s
  =-P_{(s=yes)} * \log_2 P_{(s=yes)}-P_{(s=no)} * \log_2 P_{(s=no)}
  假设按照T属性分类后，这里假设T属性有3个值：
  Entropy(S_{(T=1)})=\sum -P_s * \log_2 P_s
  Entropy(S_{(T=2)})=\sum -P_s * \log_2 P_s
  Entropy(S_{(T=3)})=\sum -P_s * \log_2 P_s
  则划分后的信息熵为：
  Entropy(S|T)=P_{S_1}*Entropy(S_1)+P_{S_2}*Entropy(S_2)
  +P_{S_3}*Entropy(S_3)

• 信息熵增益
  IG(T)=Entropy(S)-Entropy(S|T)

ID3的缺点

• Uses expected entropy reduction, not actual reduction
• 数据需是离散值

决策树的缺点

• 决策快但是构造时候慢
• errors propagating 一个结点时出错下面的判断都是错的

SVM

general idea

Paste_Image.png
在样本空间里，w^Tx+b=0划分平面，且要使得 \frac{2}{||w||} 最大,等价于||w||^2=w^Tw最小
对于测试数据，
\begin{cases}
w^Tx_i+b \geq 1, &\quad y_i = +1 \
w^Tx_i+b \leq -1,&\quad y_i = -1
\end{cases} Paste_Image.png

于||w||^2=w^Tw最小，是一个凸二次规划(convex quadratic programming)问题，用Lagrange multiplier \alpha _i \geq 0得到其对偶问题(dual problem)，可以高效求解。

Q(\alpha)=\sum \alpha_j - \frac{1}{2}\sum \sum \alpha_i \alpha_j y_i y_j x_i^Tx_j
(1)\sum \alpha_iy_i=0
(2)\alpha_i \geq 0,for all \alpha_i
w=\sum \alpha_iy_ix_i,b=y_k-\sum \alpha_i y_i y_j x_i^Tx_k ,for any a_k >0
f(x)=w^Tx+b
详见西瓜书

kernel trick 核函数

详见西瓜书

soft margin & solving

详见西瓜书