一、决策树算法简介

决策树算法是机器学习的经典算法之一，产生于上世纪六十年代，当下主要分为ID3算法、C4.5算法以及CART算法。ID3算法和C4.5算法核心思想均为通过计算样本信息熵进行分类，两者的区别在于ID3算法基于信息增益作为特征选择的指标，而C4.5则是基于信息增益率作为特征选择的指标，本例中使用ID3算法进行分类。CART算法则是使用基尼指数作为特征选择的指标。

二、ID3算法的基本思想

ID3算法的核心是统计学中信息熵的概念，通过计算信息熵来判断该数据样本的“纯度”，信息熵越大，数据样本越不“纯”，分类需要的数据量就越大。

信息熵的计算公式：

$info(D)$=- $\displaystyle\sum_{i=1}^{k} p_i*\log_2(p_i)$
其中 $p_i$是概率

下面介绍一下ID3算法的步骤

1.计算类别信息熵

将所得到的数据集按照类别逐个计算其信息熵再相加，假设在数据集D中有k个类别，且第i个类别在数据集中所占的概率为 $p_i$，则信息类别熵为：
$info(D)$=- $\displaystyle\sum_{i=1}^{k} p_i*\log_2(p_i)$

2.计算每个特征的信息熵

将数据集根据某个特征进行分类后，计算该种特征的条件下各种类别的类别信息熵，也称条件熵。假设将数据集按照特征A进行分类，且A有m个类别，则其计算公式为：
$info_A(D)$=- $\displaystyle\sum_{j=1}^{m} |D_j|/|D|*info(D_j)$
其中的 $D_j$是指数据集的类别在A特征的各个类别下的样本数量
（注意数据集的类别和A特征的类别是不同的概念，比如要在一个数据集中判断一个人在某天心情的好坏，好和坏就是数据集的类别，而一天中有一个特征是天气，天气的类别是晴天、雨天和阴天，我们要算的是心情好和坏分别在晴天，雨天和阴天中的分布的离散情况）
其他特征的条件熵也是相同的计算方法

3.计算信息增益

通过前面两个步骤我们得到了数据集的信息熵和属于各个特征的条件熵，根据第二个步骤我先进行的分类再进行信息熵（或者说条件熵）的计算，分类之后数据的混乱程度肯定降低，也就是说条件熵会小于数据集的信息熵，信息增益则是条件熵和信息熵之间的差值，用来衡量使用该特征分类的效果好坏，假设用特征A进行分类，其信息增益公式为：
$Gain(A)$= $info(D)$- $info_A(D)$
通常我们选择信息增益最大的特征作为分类的节点

三、基于ModelArts平台实现ID3算法

1.数据集来源

数据集选用的是AIGallery的表格类型数据集《硬盘故障预测数据集》
网址链接：https://marketplace.huaweicloud.com/markets/aihub/datasets/detail/?content_id=1b5d6ec0-adc0-4fdd-b03f-fecad119eab5

2.sklearn实现模型部署

#导入相关库
import matplotlib.pyplot as plt
import pandas as pd
import numpy as np
from sklearn.model_selection import train_test_split
from sklearn import tree
from sklearn.metrics import accuracy_score
import time

#载入数据集
train_test_set = pd.read_csv("dataset_2020.csv",header=0)
data = train_test_set.values

#分出标签集和特征集
features = data[::,5::2]
lables = data[::,4]
features = pd.DataFrame(features)
lables = pd.DataFrame(lables)
lables = lables.astype("float32")

#删去整列都是空值的列
features = features.dropna(axis=1,how="all")

#将缺失值用中位数填充
features = np.array(features)
for i in range(features.shape[1]):
    temp = np.array(features)[:,i].tolist()
    median = np.nanmedian(temp)
    features[np.argwhere(pd.isna(features[:,i].T)),i] = median
features = pd.DataFrame(features,dtype="float32")

#分出训练集和测试集
train_features,test_features,train_lables,test_lables = train_test_split(features,lables,test_size=0.33,random_state=0)
time_1 = time.time()

#选用ID3算法
clf = tree.DecisionTreeClassifier(criterion='entropy',
                                  random_state=10,
                                  splitter='random',
                                  )
clf.fit(train_features,train_lables)
time_2 = time.time()
print('Training cost:{}s'.format(time_2-time_1))
#预测
test_predict = clf.predict(test_features)
time_3 = time.time()
print("Predicting cost:{}s".format(time_3-time_2))
#得分
score = accuracy_score(test_lables,test_predict)
print("score is {}".format(score))

#学习曲线
scores1 = []
for x in range(4,20):
    clf = tree.DecisionTreeClassifier(criterion='entropy',
                                  random_state=10,  #使得每一次生成的树都一样
                                  splitter='random',#分类的特征随机,减少过拟合的可能性
                                  max_depth=x       #树的最大深度
                                  )
    clf.fit(train_features,train_lables)
    test_predict = clf.predict(test_features)
    score = accuracy_score(test_lables,test_predict)
    scores1.append(score)
plt.plot(range(4,20),scores1,color='red',label="max_depth")
plt.legend()
plt.show()

scores2 = []
for y in range(2,30):
    clf = tree.DecisionTreeClassifier(criterion='entropy',
                                  random_state=10,
                                  splitter='random',
                                  max_depth=18,
                                  min_samples_split=y  #至少有y个样本才会分枝
                                  )
    clf.fit(train_features,train_lables)
    test_predict = clf.predict(test_features)
    score = accuracy_score(test_lables,test_predict)
    scores2.append(score)
plt.plot(range(2,30),scores2,color='red',label="min_samples_split")
plt.legend()
plt.show()

#手动调参到目前为止效果最好的参数
clf = tree.DecisionTreeClassifier(criterion='entropy',
                                  random_state=10,
                                  splitter='random',
                                  max_depth=18,
                                  min_samples_split=16,
                                  )
clf.fit(train_features,train_lables)
test_predict = clf.predict(test_features)
score = accuracy_score(test_lables,test_predict)
print(score)    
#目前最好的预测得分达到0.7815

3.部分参数解释

tree.DecisionTreeClassifier():
criterion：决策树衡量划分质量的方法，默认值为‘gini’（基尼指数），默认值下为CART算法，另外一个可选参数为 ‘entropy’(信息增益),选择此参数为ID3算法。
random_state：默认值为 ‘None’，可任意设为一个常数，设为常数时可以简单理解为使得每次运行模型都会得到一个相同的树。
splitter：节点划分策略，默认值为 ‘best’(最优划分)，模型会在特征的所有划分点中找出最优的划分点；可选参数有 ‘random’(随机局部最优划分)，模型会随机地在部分划分点中找到局部最优的划分点。'best’适合样本量不大的情况下， 'random’适合样本量比较大的时候,是减少过拟合的方法之一。
max_depth:树的最大深度，默认值为 ‘None’,指定模型中树的的最大深度。
min_samples_split:内部节点能继续划分所包含的最小样本数，是防止过拟合的方法之一。