信息熵

熵：描述不确定性。
一个随机事件越不确定，熵越大；如果完全确定，熵为0。

概率越低，信息量越大；如果概率为1，信息量为0，所以应该为一个减函数。
在取对数的情况下，ln(xy) = lnx + lny; 取负为减函数。
因此：

x	0	1
p	1-p	p
lnp	-ln(1-p)	-lnp

期望 E[lnp] = -(1-p)ln(1-p) - plnp = -Σpi*lnpi

条件熵

条件熵： H(Y|X) 在x给定的时候y的熵
H(X,Y)-H(X)
(X,Y)发生所包含的熵减去X单独发生包含的熵
（条件熵推导：KL散度？互信息？）

H(X,Y)-H(X)
= -Σp(x,y) log p(x,y)+Σp(x) log p(x) ## (这里Σp(x) = ΣΣp(x,y) = Σp(x,y)）
= -Σp(x,y) log p(x,y)+Σp(x,y) log p(x)
= -Σp(x,y) log (p(x,y)/p(x))
= -Σp(x,y) log p(y|x)
可得：
= -ΣΣp(x)p(y|x) log p(y|x)
= Σp(x) (-Σp(y|x) log p(y|x)）
= Σp(x)H(Y|X=x)

相对熵

相对熵又称互熵，交叉熵，KL散度等。
相对熵可以度量两个随机变量的距离，（贝叶斯网络，变分推导中遇到）。D(p||q) != D(q||p)
设p(x),q(x)是X取值中的两个概率分布，则q对p的相对熵是
D(p||q) = Σp(x) log (p(x)/q(x)) = Ep(x) log (p(x)/q(x))

互信息

X,Y的联合分布和独立分布乘积的相对熵就是两个随机变量X,Y的互信息。
I(X,Y) = D(P(X,Y) || P(X)P(Y))
I(X,Y) = Σp(x,y) log (p(x,y)/ (p(x)p(y)) )
联合概率与独立概率之间的距离，这个距离是互信息。

H(Y)-I(X,Y) : Y的信息熵 - 互信息 = H(Y|X)

H(Y)-I(X,Y)
= -Σp(y) log p(y) - Σp(x,y) log (p(x,y)/ (p(x)p(y)) )
= - ΣΣp(x,y) log p(y) - Σp(x,y) log (p(x,y)/ (p(x)p(y)) )
(这里Σp(y) = ΣΣp(x,y) = Σp(x,y)）
（负号提出后，两子式相加，log p(y)和后面的log分母中的p(y)约掉）
= - Σp(x,y) log (p(x,y)/ (p(x))
= - Σp(x,y) log p(y|x)
= H(Y|X)

熵，条件熵，互信息之间的等式

H(Y|X) = H(X,Y) - H(X)
H(Y|X) = H(Y) - I(X,Y)
因此互信息定义式也可以为：
I(X,Y) = H(Y) - H(Y|X)
I(X,Y) = H(X) + H(Y) - H(Y|X)

H(Y|X) <= H(X)

决策树学习算法

决策树
每一个内部节点为一个属性的测试，每个分支为一个测试的输出，每个叶子节点代表一个类别。
以信息熵为度量构造一棵熵值下降最快的树，叶子处熵值为0。

每一个特征有很多取值
如果取值是离散的，就将n个数分为n1,n2个两类
如果取值是连续的，就给定一个阈值，将小于阈值的分一类，大于的分一类
如何选择阈值？因为有不同的选择标准，如下：
ID3，C4.5, CART（classification and regression tree)

ID3 信息增益

iterative dichotomizer 迭代二分器
信息增益
当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵和条件熵为经验熵和经验条件熵。
表示：得知特征A的信息而是的类X的信息不确定性减少的程度。
特征A对数据集D的信息增益 g(D,A) = H(D) - H(D|A) (就是训练数据集D和特征A的互信息）
所以步骤为：

1. 遍历所有特征，计算每个特征对数据集D的经验条件熵： H(D|A)
2. 计算每个特征的信息增益： g(D,A) = H(D) - H(D|A)
3. 选择信息增益最大的特征作为当前分裂特征
   

决策树就是建立下一层使它的信息熵之和小于上一层，表示信息更加的确定。
决策树采用自顶向下的递归方法，找出使熵下降最快的的特征。
信息增益 ：本质是X和Fi的互信息
例：第i个特征算出熵值的下降，看谁下降的多： Fi = H(X) - H(X|Fi)
注意：如果分类很多，甚至等于样本个数的时候，它的信息增益甚至等于H(X)本身，这是不合理的。所以引出信息增益率。

C4.5 信息增益率

gr(D,A) = g(D,A) / H(A)

CART

gini系数：直线段代替曲线段的熵的近似
熵：-Σp*lnp
而 负的ln函数 y> 0的部分用直线段近似为：-x+1
替代lnp则为Σp（1-p)
（或将 f(x)=-lnx在x=1处一阶展开）

ΣX(-lnX) -> ΣX(1-x)
注：经济学中的gini系数不一样

决策树拟合的时候：均方误差
样本之间最小的样本min到max之间选择一个step，选择使得最小的均方误差的分类阈值点。
均方误差相当于n个样本的均值

解决决策树过拟合的两个方法

1. 剪枝
   原损失函数： C(T) = ΣNt H(t)
   叶节点越多，决策树越复杂，损失越大：
   当α=0时，未剪枝的决策树损失最小，当α = +∞时单根节点决策树损失最小。 Cα(T) = C(T)+α|Tleaf|
   α : 剪枝系数 r为根
   剪枝后： Cα® = C®+α
   剪枝前： Cα® = C®+α|Rleaf|
   当剪枝前后一样时，剪枝系数为：( C® - C® ) / ( Rleaf -1)

剪枝算法：
计算所有内部节点的剪枝系数
查找最小的剪枝系数节点，剪枝得到决策树
重复以上步骤，直到决策树剪到只剩一个节点
将上面每一次剪枝后得到的决策树用验证样本集选择最优子树，使用评价函数 C(T) = ΣNt H(t) （就是原损失函数）

2. 随机森林
   在某一棵树的一个维度过拟合，做N棵树平均后，会减少噪声的影响。

随机森林

随机森林

1. 从样本中bootstrap采样选出n个样本
2. 从属性中随机选择k个属性，选择最佳分割属性为节点建立CART决策树
3. 重复步骤1，2m次，建立m棵决策树
4. 形成随机森林投票表决结果决定数据属于类型

Bagging 的策略

因为决策树是弱分类器，像SVM（太强调一些支撑向量所以不适合这个策略）和Logistic回归是强分类器。
bootstrapping aggregation

1. 从样本集中有放回的重采样选出n个样本，对n个样本建立分类器 （采样率，当比较低的时候可以采到较为异常的部分）
2. 重复第一步骤得到m个分类器，得到m个分类器的分类结果投票出来的结果

一个数被选中的概率：1/n
n次都不被选中的概率为：(1-1/n)^n
所以一个数被选中的概率为：1- (1-1/n)^n
得到1-1/e 大约63.2%参与到决策树的生成。
OOB数据
剩余36.8%的数据可以做out of bag袋外数据，可以用来做测试集用于误差估计

投票机制

假设有N个用户可以为X个电影投票，不能重复投票，有1，2，3，4，5档
如何根据用户投票对电影排序？（分类问题，评分为小数则为回归）

参考方案：
Weighted Rating = （v / (v+m))R + (m / (v+m))C
R: 该电影平均得分
C：所有电影平均得分
v：该电影投票人数
m：排名前50的电影的最低票数

关于随机森林

样本不均衡的常用处理方法
降采样，训练速度也加快了
过采样，避免信息丢失 （大部分情况降采样反而更优）
数据合成（随机插值得到新样本，SMOTE）
代价敏感学习（降低A类权值，提高B类权值）

随机森林计算样本相似度
如果不同的样本落在了同一个叶子节点，那么认为这两个样本是相似的。

随机森林计算特征重要度
如果一个特征被选择的次数多，那么就说明它对分类的影响大，与y的关系强。

随机森林做异常检测：（这里不要使用过多样本，可以先做一个降采样）
一般异常值容易更快到达叶子节点