问1
机器学习算法之决策树（Decisiontree）
决策树- 基础概念
算法思想
基本思想是以信息熵为度量构造⼀棵熵值下降最快的树，到叶⼦节点处的熵值为零，此时每个叶节点中的实例都属于同⼀类。
就是通过⼀棵按照属性分裂出来的⼆叉树，多叉树，最后决定这⼀组样本所属的类别。
走廊的英文内部节点标⽰属性、叶⼦节点存放所属的类别。
图⽰如下：
西⽠决策树
通过根节点根据这些属性对下⾛，很容易判断出来这组属性的⽠是属于好⽠还是坏⽠。
信息熵下降越快，说明信息越明确，就是寻找纯度最好的分类⽅法，纯度通俗点理解就是⽬标变量要分得⾜够开（y=1的和y=0的混到⼀起就会不纯）。
决策树分裂算法
决策树使⽤⽐较简单，那么如何构建就成了关键。
⼀般来说，可以选择的属性很多，那么每⼀步应该选择哪个分⽀，这是根据前⾯的原来判断信息熵下降最快的分⽀作为分裂的分⽀。
⽽判断信息熵下降情况的有三种算法：
ID3算法： 使⽤信息增益作为不纯度，核⼼思想是以信息增益度量属性选择，选择分裂后的信息增益最⼤的，也就是熵在分裂前后差值最⼤的属性进⾏分裂。
根据log(x)的函数可知，p值越⼩，熵越⼤，所以当分组完全是会出现p=0此时熵最⼤，概率为0说明已经最纯了。学习数据挖掘技术的最好⽅法是找到详细案例和看懂计算过程。有时算法虽然不难，但公式表达很难理解。
案例分享
表中S、M和L分别表⽰⼩、中和⼤。
设L、F、H和R表⽰⽇志密度、好友密度、是否使⽤真实头像和账号是否真实，试⽤ID3算法构造决策树。
解：设D为10个样本集，其中决策属性（真实账户/R）有7个YES、3个NO。决策属性信息熵为：
决策属性信息熵
如果按照⽇志密度来分类：计算⽇志密度熵值，⽇志密度分为3类S，L，M
其中L分类，样本总数10，L类3，L类中假账号0 真实账号3
L+M+S
所以：
所以gain(L) = 0.876-0.603 = 0.273
同理计算好友密度信息增益：
image.png
计算真实头像的信息增益：
因为好友密度（F）具有最⼤的信息增益（好友密度信息熵最⼩，最易分割），所以第⼀次分裂选择好友密度F为分裂属性（实际中如果特征⾮常多是随机选择⼀些特征然后计算后选取的不能遍历所有情况），分裂后的结果如下：
茄汁
第⼀次分裂的结果
图中：按好友密度（F）分割树，⽔平M和L为单⼀⽔平决策属性分⽀（树叶），没有必要继续分割。⽔平S包含决策属性的不同⽔平，应该继续分割。待分割决策信息表为：
带分裂决策表
此时，设D为4个样本集，其中决策属性（真实账户/R）有1个YES、3个NO。决策属性信息熵为：
决策属性信息熵
⽇志密度属性期望信息熵为：
⽇志密度属性信息熵
真实头像属性期望信息熵为：
真实头像信息熵
信息增益
因为⽇志密度（L）具有最⼤的信息增益，所以第⼆次分裂选择⽇志密度（L）为分裂属性，分裂后的结果如下图表⽰：坚持到底的成语
⽇志密度分裂
图中，⽇志密度为M时，⽆法做出判断、也⽆法继续进⾏分裂。⾄此，决策树构建完毕。
设某⼈在SNS社区中的好友密度为L或M，⽆论其它属性⽔平取值如何，均可判定为是真实账户；如果某⼈在SNS社区中的好友密度为S、⽇志密度也为S，可判定为是虚假账户；如果某⼈在SNS社区中的
好友密度为S、⽇志密度为M，应根据真实头像信息做出判断，由于样本过少，⽆法继续进⾏。龙虾怎么清洗
C4.5算法：使⽤信息增益率作为不纯度。
ID3算法是决策树的⼀个经典的构造算法，但ID3算法也存在⼀些问题，⽐较突出的缺陷是信息增益的计算依赖于特征⽔平较多的特征，⽽属性取
值最多的属性并不⼀定最优。例如，投掷⼀枚分币和⼀个⾊⼦这两个随机试验，所有可能的期望信息熵为：
信息熵
通过信息熵的定义可知，在给定特征⽔平数条件下，各⽔平发⽣概率相等（如掷筛⼦6个数字发⽣的概率都为1/6。期望信息熵最⼤。所以，当决策信息中某个变量特征⽔平较多时，ID3算法按信息增益指标往往会选择该变量或属性做为分割节点。
I、“分裂信息”公式
C4.5算法⾸先定义了“分裂信息”，其定义可以表⽰成：
分裂信息
II、增益率
增益率
拜月亭故事梗概III、分裂信息和增益率计算实例
在ID3算法案例中（SNS社区中不真实账号检测），决策属性信息熵为：
决策属性信息熵
把决策属性替换成其它属性，即为各属性分裂信息熵。
⽇志密度分裂信息：炸藕片
⽇志密度分裂信息
好友密度分裂信息：
好友密度分裂
真实头像分裂信息：
>白木通
