手动计算实现决策树分类
数据整合
X['真实用户'] = y
X
计算未划分信息熵
s = X['真实用户']
p = s.value_counts()/s.size
(p * np.log2(1/p)).sum()
按照日志密度进行划分
x = X['日志密度'].unique()
x.sort()
# 如何划分呢，分成两部分
for i in range(len(x) - 1):split = x[i:i+2].mean()cond = X['日志密度'] <= split# 概率分布p = cond.value_counts()/cond.size# 按照条件划分，两边的概率分布情况indexs =p.indexentropy = 0for index in indexs:user = X[cond == index]['真实用户']p_user = user.value_counts()/user.sizeentropy += (p_user * np.log2(1/p_user)).sum() * p[index]print(split,entropy)
按照好友密度进行划分
x = X['好友密度'].unique()
x.sort() # 排序,属性值，0,1,2
print(x)
for i in range(len(x) -2):split = x[i : i +2].mean() # 裂分值cond = X['好友密度'] <= split # 分成两边，每一边分别计算信息熵# 计算概率分布，左边概率是多少，右边的概率是多少p = cond.value_counts()/cond.sizeindexs = p.index # True,Falseentropy = 0for index in indexs:user = X[cond == index]['真实用户'] # 取出了目标值y的数据p_user = user.value_counts()/user.size# 每个分支的信息熵e = (p_user * np.log2(1/p_user)).sum() * p[index]entropy += eprint('------------',p[index],(p_user * np.log2(1/p_user)).sum())
# print(split,entropy)
按照是否使用真实头像划分
x = X['真实头像'].unique()
x.sort() # 排序,属性值，0,1,2
print(x)
for i in range(len(x) -1):split = x[i : i +2].mean() # 裂分值cond = X['真实头像'] <= split # 分成两边，每一边分别计算信息熵# 计算概率分布，左边概率是多少，右边的概率是多少p = cond.value_counts()/cond.sizeindexs = p.index # True,Falseentropy = 0for index in indexs:user = X[cond == index]['真实用户'] # 取出了目标值y的数据p_user = user.value_counts()/user.size# 每个分支的信息熵entropy += (p_user * np.log2(1/p_user)).sum() * p[index]print(split,entropy) 
筛选最佳划分条件
columns = ['日志密度','好友密度','真实头像']
lower_entropy = 1
condition = {}
for col in columns:x = X[col].unique()x.sort()print(x)# 如何划分呢，分成两部分for i in range(len(x) - 1):split = x[i:i+2].mean()cond = X[col] <= split# 概率分布p = cond.value_counts()/cond.size# 按照条件划分，两边的概率分布情况indexs =p.indexentropy = 0for index in indexs:user = X[cond == index]['真实用户']p_user = user.value_counts()/user.sizeentropy += (p_user * np.log2(1/p_user)).sum() * p[index]print(col,split,entropy)if entropy < lower_entropy:condition.clear()lower_entropy = entropycondition[col] = split
print('最佳列分条件是：',condition)
进一步列分
cond = X['好友密度'] < 0.5
X_ = X[cond]
columns = ['日志密度','真实头像']
lower_entropy = 1
condition = {}
for col in columns:x = X_[col].unique()x.sort()print(x)# 如何划分呢，分成两部分for i in range(len(x) - 1):split = x[i:i+2].mean()cond = X_[col] <= split# 概率分布p = cond.value_counts()/cond.size# 按照条件划分，两边的概率分布情况indexs =p.indexentropy = 0for index in indexs:user = X_[cond == index]['真实用户']p_user = user.value_counts()/user.sizeentropy += (p_user * np.log2(1/p_user)).sum() * p[index]print(col,split,entropy)if entropy < lower_entropy:condition.clear()lower_entropy = entropycondition[col] = split
print('最佳列分条件是：',condition)
决策树分裂指标
常用的分裂条件时：
- 信息增益
- Gini系数
- MSE（回归问题）
- 信息增益率
3.1、信息熵（ID3）
在信息论里熵叫作信息量，即熵是对不确定性的度量。从控制论的角度来看，应叫不确定性。信息论的创始人香农在其著作《通信的数学理论》中提出了建立在概率统计模型上的信息度量。他把信息定义为“用来消除不确定性的东西”。在信息世界，熵越高，则能传输越多的信息，熵越低，则意味着传输的信息越少。还是举例说明，假设 Dammi 在买衣服的时候有颜色，尺寸，款式以及设计年份四种要求，而 Sara 只有颜色和尺寸的要求，那么在购买衣服这个层面上 Dammi 由于选择更多因而不确定性因素更大，最终 Dammi所获取的信息更多，也就是熵更大。所以信息量=熵=不确定性，通俗易懂。在叙述决策树时我们用熵表示不纯度（Impurity）。
对应公式如下：
熵的变化越大，说明划分越纯，信息增益越大~
3.2、Gini系数（CART）
基尼系数是指国际上通用的、用以衡量一个国家或地区居民收入差距的常用指标。
基尼系数最大为“1”，最小等于“0”。基尼系数越接近 0 表明收入分配越是趋向平等。国际惯例把 0.2 以下视为收入绝对平均，0.2-0.3 视为收入比较平均；0.3-0.4 视为收入相对合理；0.4-0.5 视为收入差距较大，当基尼系数达到 0.5 以上时，则表示收入悬殊。
基尼系数的实际数值只能介于 0～1 之间，基尼系数越小收入分配越平均，基尼系数越大收入分配越不平均。国际上通常把 0.4 作为贫富差距的警戒线，大于这一数值容易出现社会动荡。
Gini 系数越小，代表集合中的数据越纯，所有我们可以计算分裂前的值在按照某个维度对数据集进行划分，然后可以去计算多个节点的 Gini 系数。
对应公式如下：
在对数据进行分类是gini系数的变化越大，说明划分越纯，效果越好~
3.3、信息增益率
大学期末的数学考试只有单选题。对于一个完全没有学习过的学生。该如何过关呢？
4个选项是正确选项的概率都是1/4。那么单项选择题的答案的熵就是：
在学霸圈做单项选择题有一个秘籍：三长一短选最短，三短一长选最长。姑且假设学霸的秘籍一般都是正确的。
如果在某场考试中，有10%的单项选题是三长一短，10%的选题是三短一长。计算该考试单项选题的关于长短题的条件熵：
计算条件熵（条件就是：题目不同类型）
那么信息增益是：
信息增益率在信息增益的基础上增加了惩罚项，惩罚项是特征的固有值。
写作 gr(X,Y)。定义为信息增益除以特征的固有值，如下：
计算上面单选题题目长短案例的信息增益率：
对于取值多的属性，尤其一些连续型数值，这个单独的属性就可以划分所有的样本，使得所有分支下的样本集合都是“纯的”（最极端的情况是每个叶子节点只有一个样本）。 一个属性的信息增益越大，表明属性对样本的熵减少的能力更强，这个属性使得数据由不确定性变成确定性的能力越强。 所以如果是取值更多的属性，更容易使得数据更“纯”（尤其是连续型数值），其信息增益更大，决策树会首先挑选这个属性作为树的顶点。结果训练出来的形状是一棵庞大且深度很浅的树，这样的划分是极为不合理的。
C4.5使用了信息增益率，在信息增益的基础上除了一项split information,来惩罚值更多的属性。从而使划分更加合理！
