下面的有些叙述基于我个人理解, 可能与专业书籍描述不同, 但是最终都是表达同一个意思, 如果有不同意见的小伙伴, 请在评论区留言, 我不胜感激.
参考:
周志华-机器学习
/xiaohukun/article/details/78112917
/fuqiuai/article/details/79456971
决策树简介
1. 问题背景
常规方式对样本进行分类, 会导致很大的性能问题, 样本需要不断重复检测每一项属性(属性之间还不能存在相关性), 例如: 人的体重由[年龄, 身高] 决定, 当获得一组样本 [20, 178], 可能我们会先将该数据归到20岁的阶段中, 然后判断身高, 最后判断体重, 我们也有可能先使用身高, 然后使用年龄, 最后判断体重, 排列组合的方式得出预测值, 这种毫无准则的选择判断会导致很大的计算量; 然而决策树使用**信息增益(当前属性对样本的贡献率) **, 根据信息增益从大到小选用对应的属性进行判断, 有针对性的选择可以有效地避免无用的计算, 通过选用合适的样本属性按照特定的规则进行判断, 对样本准确的分类, 现在遇到的问题就是如何构建一棵决策树, 构建出来的决策树还能准确预测结果, 下面将针对决策树定义, 信息量, 建立决策树需要遵守的规则, 优化等问题来讲解.
2. 决策树定义
决策树是基于树结构进行决策, 一棵决策树包含一个Root根节点(里面包含所有测试集, 测试集从Root处出发, 按照一定的决策方式, 不同的决策将导致每个样本最终拥有不同的预测结果), 以及若干内部节点和叶子节点, 叶子节点对应最终的决策结果, 每一个内部节点都是一个属性测试, 从Root到叶子节点的路径就是一个样本的决策过程, 当样本到达叶子节点的时候就是样本的预测结果.
决策树如下图:
Root: 包含所有的样本集
DECISION: 决策方式
Result: 决策结果
构造决策树
1. 问题背景
构建决策树需要有一个构建规则, 不同的构建规则将导致预测结果的不同, 当然, 不同的数据需要使用不同的构建规则, 这样才能最好地预测出结果, 下面将介绍3中不同的构建规则: 信息增益, 信息增益率, 基尼指数
2. 信息熵
信息熵是度量样本属性对最终预测结果的影响程度, 当某一属性的熵在正常情况下比其他属性的熵要大的时候, 我们就可以先选用该属性优先对样本进行分类(越是影响大的属性越容易影响预测结果, 越容易预测正确).
信息熵方程定义:
pk: 属性在样例中的比例
使用例子说明:
如下图片, 使用age, income, student, credit属性来判断一个人能否买电脑
使用buys_computer计算总的信息熵:
buys_computer包含2个子集 {yes, no}, 正例比例: 9/14, 反例比例: 5/14, 最终得到 Info(D)
同理计算age:
age包含3个子集 {youth, middle_aged, senior}, 分别计算youth, middle_aged, senior各自相对于正反例的比例值, 道理同上, 然后得到 Info_youth(D), Info_middle_aged(D), Info_senior(D).
由于不同子集样本相对于age数目不同, 所以:
Info_age(D) = youth_权重*Info_youth + middle_aged_权重*Info_middle_aged(D) + senior_权重*Info_senior(D)
最终age的信息熵计算结果:
3. 信息增益(ID3算法)
信息增益: 样本利用某一属性分类之后得到多少样本, 例如: 样本使用age属性分类, Gain(D, age) = 总的熵(即Info(D)) - Info_age(D)
信息增益方程定义:
V代表属性种类; D^V代表每种属性对应的样本数目;
Ent(D)代表Info(D); |D^v|/|D| 就是属性数目在样本中权重.
下面直接计算Gain(D, age), 计算age相对于总样本D的信息增益
在前面信息熵的计算中, 我们已经得出Info(D), Info_age(D), 按照公式只需做差
同理我们可以计算出: Gain(income) = 0.029, Gain(student) = 0.151, Gain(credit_rating)=0.048
因为Gain(age)最大, 就可以得出age对样本的影响程度最高, 因此构建决策树的时候, 选用age作为Root, 得出如下决策树:
注: 在离散型数据下, 使用过的属性就不再使用, 因为该属性对样本的影响在之前已经计算过, 再次使用会导致结果错误
这只是决策树第一层树的建立, 建立第二层的时候, 同理, 用youth对应的分类样本来说: 我们接下来从 income, student, credit来进行决策, 在当前样本正返例比例的基础上分别计算Info(D’), Info_income(D’), Info_student(D’), Info_credit(D’), 使用Info(D’) - Info_XXX(D’)计算信息增益, 然后从3个属性中选出信息增益最大的属性作为下一个节点, 根据该节点的子集进行分类决策. 整个过程是一个递归的过程, 不断重复, 直到如下条件时终止:
给定结点的所有样本属于同一类(该样本中全是正例或者反例)没有剩余属性可以用来进一步划分样本(例如: 假如样本经过一系列划分后, 现在只有income, class两个标签, 只有income一个属性, 没有多余的属性进行下一步划分, 划分停止), 在样本中可能存在一部分反例, 一部分正例, 此时使用多数表决, 根据正返例个数决定当前叶子节点的类别.
详细算法流程如下:
算法文字描述:
树以代表训练样本的单个结点开始（步骤1）。如果样本都在同一个类，则该结点成为树叶，并用该类标号（步骤2 和3）。否则，算法使用称为信息增益的基于熵的度量作为启发信息，选择能够最好地将样本分类的属性（步骤6）。该属性成为该结点的“测试”或“判定”属性（步骤7）。在算法的该版本中，所有的属性都是分类的，即离散值。连续属性必须离散化。对测试属性的每个已知的值，创建一个分枝，并据此划分样本（步骤8-10）。算法使用同样的过程，递归地形成每个划分上的样本判定树。一旦一个属性出现在一个结点上，就不必该结点的任何后代上考虑它（步骤13）
注: 上面的决策树建立方式是ID3算法, 这种算法很容易受信息增益的影响, 当某一属性对应的样本分布过于分散, 就比如使用样本id作为属性, 那么计算出来的Info_id(D)就会非常大, 对结果造成很大的影响, 下面将介绍信息增益率来减小这种影响
Python实现ID3:
from sklearn.feature_extraction import DictVectorizerimport csvfrom sklearn import treefrom sklearn import preprocessingfrom sklearn.externals.six import StringIO# Read in the csv file and put features into list of dict and list of class labelallElectronicsData = open(r'/home/zhoumiao/MachineLearning/01decisiontree/AllElectronics.csv', 'rb')#获取csv文件中内容reader = csv.reader(allElectronicsData)headers = reader.next()print(headers)featureList = []labelList = []#将每一行数据变为字典的形式存入列表中#例如:[{age:youth, income:high...}, {...}, ...]#直接使用库将这种格式的数据转变为0, 1格式for row in reader:#获取每一行数据最后的标签labelList.append(row[len(row)-1])rowDict = {}for i in range(1, len(row)-1):rowDict[headers[i]] = row[i]featureList.append(rowDict)print(featureList)# Vetorize features#使用本身的库进行转换,转变的只是每行对应0 1,并不满足sklearn需要的格式vec = DictVectorizer()dummyX = vec.fit_transform(featureList) .toarray()print("dummyX: " + str(dummyX))print(vec.get_feature_names())print("labelList: " + str(labelList))# vectorize class labels#针对每行最后的结果再进一步转换lb = preprocessing.LabelBinarizer()dummyY = lb.fit_transform(labelList)print("dummyY: " + str(dummyY))# Using decision tree for classification# clf = tree.DecisionTreeClassifier()#设置分类器,设置不同的参数,使用不同的算法clf = tree.DecisionTreeClassifier(criterion='entropy')#建模,传入x,y矩阵clf = clf.fit(dummyX, dummyY) print("clf: " + str(clf))# Visualize model#将决策树clf转变为原始信息,然后存入dot文件中with open("allElectronicInformationGainOri.dot", 'w') as f:f = tree.export_graphviz(clf, feature_names=vec.get_feature_names(), out_file=f)oneRowX = dummyX[0, :]print("oneRowX: " + str(oneRowX))#修改原始数据,根据模型进行预测newRowX = oneRowXnewRowX[0] = 1newRowX[2] = 0print("newRowX: " + str(newRowX))#获得预测结果predictedY = clf.predict(newRowX)print("predictedY: " + str(predictedY))
4. 信息增益率(C4.5算法)
相比于ID3算法来说, C4.5算法使用不同的Gain计算方式(计算角度不同, 弱化无关因素对结果预测的影响), 具体Gain计算如下:
信息增益率:
使用age对上面的公式进行解释:
Gain(D, age) = Info_age(D);
IV(a) = -5/14log(4/14) - 4/14log(4/14) - 5/14log(5/14)
Gain_ratio(D,age) = Info_age(D)/IV(a)
当属性子集越多, 则IV(a)就会越大, 得到的Gain_ratio就会越小, 从而达到: 避免因为属性子集过多而导致信息增长过大影响判断结果.
注:增长率对子集过少的属性也会有偏好, 就比如id与age, 增长率对age将会表现出偏向, 从而使用age作为节点, 而不是id, 避免结果的预测错误.
选用属性方式:
计算出所有属性的Gain_ratio, 以及平均Gain_ratio然后找出高于平均水平的属性再从步骤2中找出Gain_ratio最高的属性作为划分依据, 随后的操作就重复即可.
使用C4.5算法与ID3算法的区别就是选取的Gain不同, 其他操作都是一样的, 最后的递归终止条件与ID3是相同的.
算法描述:
while (当前节点”不纯“) (1)计算当前节点的类别信息熵Info(D) （以类别取值计算） (2)计算当前节点各个属性的信息熵Info(Ai) （以属性取值下的类别取值计算） (3)计算各个属性的信息增益Gain(Ai)=Info(D)-Info(Ai) (4)计算各个属性的分类信息度量H(Ai) （以属性取值计算） (5)计算各个属性的信息增益率IGR(Ai)=Gain(Ai)/H(Ai) end while 当前节点设置为叶子节点
代码如下:
# encoding=utf-8import cv2import timeimport numpy as npimport pandas as pdfrom sklearn.cross_validation import train_test_splitfrom sklearn.metrics import accuracy_score# 二值化def binaryzation(img):cv_img = img.astype(np.uint8)cv2.threshold(cv_img,50,1,cv2.THRESH_BINARY_INV,cv_img)return cv_imgdef binaryzation_features(trainset):features = []for img in trainset:img = np.reshape(img,(28,28))cv_img = img.astype(np.uint8)img_b = binaryzation(cv_img)# hog_feature = np.transpose(hog_feature)features.append(img_b)features = np.array(features)features = np.reshape(features,(-1,feature_len))return featuresclass Tree(object):def __init__(self,node_type,Class = None, feature = None):self.node_type = node_type # 节点类型（internal或leaf）self.dict = {} # dict的键表示特征Ag的可能值ai，值表示根据ai得到的子树 self.Class = Class # 叶节点表示的类，若是内部节点则为noneself.feature = feature # 表示当前的树即将由第feature个特征划分（即第feature特征是使得当前树中信息增益最大的特征）def add_tree(self,key,tree):self.dict[key] = treedef predict(self,features): if self.node_type == 'leaf' or (features[self.feature] not in self.dict):return self.Classtree = self.dict.get(features[self.feature])return tree.predict(features)# 计算数据集x的经验熵H(x)def calc_ent(x):x_value_list = set([x[i] for i in range(x.shape[0])])ent = 0.0for x_value in x_value_list:p = float(x[x == x_value].shape[0]) / x.shape[0]logp = np.log2(p)ent -= p * logpreturn ent# 计算条件熵H(y/x)def calc_condition_ent(x, y):x_value_list = set([x[i] for i in range(x.shape[0])])ent = 0.0for x_value in x_value_list:sub_y = y[x == x_value]temp_ent = calc_ent(sub_y)ent += (float(sub_y.shape[0]) / y.shape[0]) * temp_entreturn ent# 计算信息增益def calc_ent_grap(x,y):base_ent = calc_ent(y)condition_ent = calc_condition_ent(x, y)ent_grap = base_ent - condition_entreturn ent_grap# C4.5算法def recurse_train(train_set,train_label,features):LEAF = 'leaf'INTERNAL = 'internal'# 步骤1——如果训练集train_set中的所有实例都属于同一类Cklabel_set = set(train_label)if len(label_set) == 1:return Tree(LEAF,Class = label_set.pop())# 步骤2——如果特征集features为空class_len = [(i,len(list(filter(lambda x:x==i,train_label)))) for i in range(class_num)] # 计算每一个类出现的个数(max_class,max_len) = max(class_len,key = lambda x:x[1])if len(features) == 0:return Tree(LEAF,Class = max_class)# 步骤3——计算信息增益,并选择信息增益最大的特征max_feature = 0max_gda = 0D = train_labelfor feature in features:# print(type(train_set))A = np.array(train_set[:,feature].flat) # 选择训练集中的第feature列（即第feature个特征）gda = calc_ent_grap(A,D)if calc_ent(A) != 0: ####### 计算信息增益比，这是与ID3算法唯一的不同gda /= calc_ent(A)if gda > max_gda:max_gda,max_feature = gda,feature# 步骤4——信息增益小于阈值if max_gda < epsilon:return Tree(LEAF,Class = max_class)# 步骤5——构建非空子集sub_features = list(filter(lambda x:x!=max_feature,features))tree = Tree(INTERNAL,feature=max_feature)max_feature_col = np.array(train_set[:,max_feature].flat)feature_value_list = set([max_feature_col[i] for i in range(max_feature_col.shape[0])]) # 保存信息增益最大的特征可能的取值 (shape[0]表示计算行数)for feature_value in feature_value_list:index = []for i in range(len(train_label)):if train_set[i][max_feature] == feature_value:index.append(i)sub_train_set = train_set[index]sub_train_label = train_label[index]sub_tree = recurse_train(sub_train_set,sub_train_label,sub_features)tree.add_tree(feature_value,sub_tree)return treedef train(train_set,train_label,features):return recurse_train(train_set,train_label,features)def predict(test_set,tree):result = []for features in test_set:tmp_predict = tree.predict(features)result.append(tmp_predict)return np.array(result)class_num = 10 # MINST数据集有10种labels，分别是“0,1,2,3,4,5,6,7,8,9”feature_len = 784 # MINST数据集每个image有28*28=784个特征（pixels）epsilon = 0.001 # 设定阈值if __name__ == '__main__':print("Start read data...")time_1 = time.time()raw_data = pd.read_csv('../data/train.csv', header=0) # 读取csv数据data = raw_data.valuesimgs = data[::, 1::]features = binaryzation_features(imgs) # 图片二值化(很重要，不然预测准确率很低)labels = data[::, 0]# 避免过拟合，采用交叉验证，随机选取33%数据作为测试集，剩余为训练集train_features, test_features, train_labels, test_labels = train_test_split(features, labels, test_size=0.33, random_state=0)time_2 = time.time()print('read data cost %f seconds' % (time_2 - time_1))# 通过C4.5算法生成决策树print('Start training...')tree = train(train_features,train_labels,list(range(feature_len)))time_3 = time.time()print('training cost %f seconds' % (time_3 - time_2))print('Start predicting...')test_predict = predict(test_features,tree)time_4 = time.time()print('predicting cost %f seconds' % (time_4 - time_3))# print("预测的结果为：")# print(test_predict)for i in range(len(test_predict)):if test_predict[i] == None:test_predict[i] = epsilonscore = accuracy_score(test_labels, test_predict)print("The accruacy score is %f" % score)
5. 基尼指数(CART决策树)
CART决策树使用基尼指数(所谓的信息熵)作为判断属性是否可以作为划分依据,
特点:
CART 既能是分类树，又能是回归树.当CART是分类树时，采用GINI值作为节点分裂的依据；当CART是回归树时，采用样本的最小方差作为节点分裂的依据.
基尼指数计算:
Gini(D)描述从样本中随机抽取两个样本, 不一样概率的大小, Gini越大说明该属性的样本越少, 因此该属性对样本的总影响就越小.
a属性对样本预测结果的影响, 影响越大，Gini_index(D, a)值越小，反之，则GINI值越大.
其中，pk表示节点中属于类k的概率.
下面使用一个例子说明:
按照职业属性划分, 预测是否结婚
预测是否结婚:
Gini(married, occupation) = 3/7[1− (2/3)^2 − (1/3)^2] + 4/7[1 − (3/4)^2 − (1/4)^2]=0.4
同理可计算看电视时间, 年龄对是否结婚的Gini
CART决策树算法流程:
每次划分的时候, 需要选择基尼指数最小的属性作为最优划分属性
Python使用sklearn代码实现CRAT:
from sklearn import datasetsfrom sklearn import treefrom sklearn.externals.six import StringIOimport pydot# 加载Iris数据集iris = datasets.load_iris()#不传入参数, 使用默认算法CRAT实现分类clf = tree.DecisionTreeClassifier()clf = clf.fit(iris.data, iris.target)dot_data = StringIO() tree.export_graphviz(clf, out_file=dot_data, feature_names=iris.feature_names, class_names=iris.target_names, filled=True, rounded=True, special_characters=True) # tree.export_graphviz(clf, out_file=r"tree.dot") #把这行代码放开可以生成决策树的文件(graph,) = pydot.graph_from_dot_data(dot_data.getvalue()) graph.write_png('iris.png')
总结:
三种算法各有自己的Grain计算方式, 构建树的过程, 区别就在于Grain计算的不同, 最优属性选择的不同, 剩下都是相同的.
