您的位置: 首页  >  文章  >  机器学习基础——实现基本的决策树

机器学习基础——实现基本的决策树

分类: 文章 • 2022-10-13 00:19:25

一、决策树基本流程

 决策树是常见的机器学习方法。我在学习周志华的机器学习的时候，用python实现了最基础的ID3算法，其基本思想是：
基于信息论中的信息增益理论，首先找出判断样本的最高的信息增益的属性（或者说特征），然后依次对按该属性划分成的子集
进行同样的选择信息增益最大的属性并进行划分的过程。这是一个典型的(divide-conquer)的过程。

二、最基本的决策树实现

下面，通过周志华《机器学习》（也叫西瓜书）第四章的例子，我用python实现了基于pandas的DataFrame的数据结构的数据来进行的决策树的实现（属性都是离散属性）。对
连续属性或更一般性的情况，可以调用sklearn的决策树包来做，这块放在最后。
样本如下：
机器学习基础——实现基本的决策树
[python] view plain copy
  1. # 决策树  
  2. # 习题4.3 实现基于信息熵进行划分选择的决策树算法，并为表4.3中数据  
  3. # 生成一颗决策树  
  4. # 表4.3既有离散属性，也有连续属性。  
  5. # _*_ coding:UTF-8 _*_  
  6. import pandas as pd  
  7. import numpy as np  
  8. import os  
  9. from math import log2  
  10. # 离散的特征的完成了，连续的我用sklearn可以做，就不在此处写了  
  11. def Entrop(data):  
  12.     entropy = dict()  
  13.     for i in data.keys():  
  14.         good = data[i].count('是')  
  15.         bad = data[i].count('否')  
  16.         length = len(data[i])  
  17.         p1 = good / length  
  18.         p2 = bad / length  
  19.         if p1 == 0.0 or p2 == 0.0:  
  20.             entropy[i] = 0  
  21.         else:  
  22.             entropy[i] = -(p1 * log2(p1) + p2 * log2(p2))  
  23.     return entropy  
  24.   
  25. def DecisionTree(entropy, data, MaxKey, threshold, category):  
  26.     for i in entropy:  
  27.         sub_data = data[data[MaxKey] == i]  # sub_data为子集合  
  28.         subs_entropy = entropy[i]  # subs_entropy是信息熵  
  29.         sizes = sub_data.count(0)[0]  # 这个子集合的样本数量  
  30.         if subs_entropy >= threshold:  
  31.             gains = dict()  # 信息增益  
  32.             data_sample = dict()  
  33.             Ent = dict()  # 信息熵  
  34.             for j in category:  
  35.                 data_sample[j] = sub_data['好瓜'].groupby(sub_data[j]).sum()  
  36.                 nn = len(data_sample[j])  
  37.                 he = 0  
  38.                 for m in range(nn):  
  39.                     good = data_sample[j][m].count('是')  
  40.                     bad = data_sample[j][m].count('否')  
  41.                     length = len(data_sample[j][m])  
  42.                     p1 = good / length  
  43.                     p2 = bad / length  
  44.                     if good == 0.0 or bad == 0.0 or length == 0:  
  45.                         Ent[j] = 0  
  46.                     else:  
  47.                         Ent[j] = -(p1 * log2(p1) + p2 * log2(p2))  
  48.                     he += (length * Ent[j]) / sizes  
  49.                 gains[j] = subs_entropy - he  
  50.             if len(gains) > 0:  
  51.                 maxKey = max(gains.items(), key=lambda x: x[1])[0]  
  52.                 entropys = Entrop(data_sample[maxKey])  
  53.                 category.pop(maxKey)  
  54.                 print('{0}下面的第一分类是{1}'.format(i, maxKey))  
  55.                 DecisionTree(entropys, sub_data, maxKey, threshold, category)  
  56.             else:  
  57.                 highest_class = max(sub_data['好瓜'].values)  
  58.                 if highest_class == '否':  
  59.                     print('{0}下面的瓜都是坏瓜'.format(i))  
  60.                 else:  
  61.                     print('{0}下面的瓜都是好瓜'.format(i))  
  62.         else:  
  63.             highest_class = max(sub_data['好瓜'].values)  
  64.             if highest_class == '否':  
  65.                 print('{0}下面的瓜都是坏瓜'.format(i))  
  66.             else:  
  67.                 print('{0}下面的瓜都是好瓜'.format(i))  
  68.   
  69.   
  70.   
  71. def main():  
  72.     """ 
  73.     主函数 
  74.     """  
  75.     dataset_path = './datasets'  # 数据集路径  
  76.     filename = 'watermalon_simple.xlsx'  # 文件名称  
  77.     dataset_filepath = os.path.join(dataset_path, filename)  # 数据集文件路径  
  78.   
  79.   
  80.     # step 1:读取数据  
  81.     data = pd.read_excel(dataset_filepath) # 获取数据  
  82.     header = data.columns # 获取列名  
  83.     sums = data.count()[0]  # 样本个数  
  84.     # print(type(header))  
  85.     # print(header[1:])  
  86.   
  87.     # step 2:取出6个特征中每个特征的子集  
  88.     category = dict()  
  89.     for i in header[1:-1]:  
  90.         category[i] = set(data[i])  
  91.   
  92.     # step 3:计算信息熵  
  93.     # 1) 初始样本的信息熵  
  94.     Ent = dict()  
  95.     number = data['好瓜'].groupby(data['好瓜']).sum()  
  96.     p1 = len(number['是']) / sums  # 好瓜的个数/总共个数  
  97.     p2 = len(number['否']) / sums  # 坏瓜的个数/总共个数  
  98.     Ent["总"] = -(p1*log2(p1) + p2*log2(p2))  
  99.   
  100.     # 2) 计算每个属性的信息增益  
  101.     Gain = dict()  
  102.     data_sample = dict()  
  103.     for i in category:  
  104.         data_sample[i] = data['好瓜'].groupby(data[i]).sum()  
  105.         # 每一个属性有几种维度 如色泽有 青绿、乌黑、浅白三种，则n = 3  
  106.         n = category[i]  
  107.         # print(len(data_sample[i]))  
  108.         # print(data_sample[i])  
  109.         he = 0  
  110.         for j in range(len(n)):  
  111.             good = data_sample[i][j].count('是')  
  112.             bad = data_sample[i][j].count('否')  
  113.             length = len(data_sample[i][j])  
  114.             p1 = good / length  
  115.             p2 = bad / length  
  116.             if p1 == 0.0 or p2 == 0.0:  
  117.                 Ent[j] = 0  
  118.             else:  
  119.                 Ent[j] = -(p1 * log2(p1) + p2 * log2(p2))  
  120.             he += (length * Ent[j])/sums  
  121.         Gain[i] = Ent['总'] - he  
  122.   
  123.     # 3) 找到value最大对应的key 即找到按增益准则划分的分类最佳情况  
  124.     #    这里的MaxKey是纹理  
  125.     MaxKey = max(Gain.items(), key=lambda x: x[1])[0]  
  126.     print('主分类是{}'.format(MaxKey))  
  127.   
  128.     # 4) 根据这个情况，分别计算其子分类的信息熵  
  129.     #    entropy为字典  
  130.     entropy = Entrop(data_sample[MaxKey])  
  131.     print(entropy)  
  132.     # {'清晰': 0.7642045065086203, '稍糊': 0.7219280948873623, '模糊': 0}  
  133.   
  134.     # 4.1)接下来的分类不能再用这个分了:即把这个类别扔掉  
  135.     category.pop(str(MaxKey))  
  136.     # print(category)  
  137.   
  138.   
  139.     # 5) 对信息熵大于某一阈值(threshold)的情况进行继续划分，如果小于则统一认为是某种情况，不再  
  140.     #    继续分类。例如：本例对模糊的Ent=0，所以不对模糊类别进行继续划分。  
  141.     threshold = 0.05  
  142.     DecisionTree(entropy, data, MaxKey, threshold, category)  
  143.   
  144.   
  145.   
  146.   
  147.   
  148.   
  149. if __name__ == "__main__":  
  150.     main()  
上面是我的代码，如果有不清楚的地方可以交流。下面贴上用sklearn的代码：

[python] view plain copy
  1. from sklearn import tree  
  2. import numpy as np  
  3. from sklearn.feature_extraction import DictVectorizer  
  4. # from sklearn import preprocessing  
  5. from sklearn.cross_validation import train_test_split  
  6. import xlrd  
  7. workbook = xlrd.open_workbook('watermalon_simple.xlsx')  
  8. booksheet = workbook.sheet_by_name('Sheet1')  
  9. X = list()  
  10. Y = list()  
  11. for row in range(booksheet.nrows):  
  12.         row_data = []  
  13.         ll = dict()  
  14.         # ll = list()  
  15.         mm = list()  
  16.         for col in range(1, booksheet.ncols-1):  
  17.             cel = booksheet.cell(row, col)  
  18.             val = cel.value  
  19.             cat = ['色泽', '根蒂', '敲声', '纹理', '触感']  
  20.             # ll.append(val)  
  21.             ll[cat[col-1]] = val  
  22.         for col in range(booksheet.ncols-1,booksheet.ncols):  
  23.             cel = booksheet.cell(row, col)  
  24.             val = cel.value  
  25.             mm.append(val)  
  26.         print('第{}行读取完毕'.format(row))  
  27.         X.append(ll)  
  28.         Y.append(mm)  
  29. # X = X[1:] #和下面的效果一样，即把第一列删除  
  30. X.pop(0); Y.pop(0)  
  31. # print(X)  
  32. print(X); print(Y)  
  33. # 1表示好瓜 0表示坏瓜  
  34. y = [1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0]  
  35.   
  36. # Vector Feature  
  37. dummyY = np.array(y)  
  38. vec = DictVectorizer()  
  39. dummyX = vec.fit_transform(X).toarray()  
  40.   
  41.   
  42. #拆分数据  
  43. x_train, x_test, y_train, y_test = train_test_split(dummyX, dummyY, test_size=0.3)  
  44.   
  45. # using desicionTree for classfication  
  46. clf = tree.DecisionTreeClassifier(criterion="entropy")  
  47. # 创建一个分类器，entropy决定了用ID3算法  
  48. clf = clf.fit(x_train, y_train)  
  49.   
  50.   
  51. # print(clf.feature_importances_)  
  52. answer=clf.predict(x_test)  
  53. print(u'系统进行测试')  
  54. # print(x_train)  
  55. print(answer)  
  56. print(y_test)  
  57. # print(np.mean(answer==y_train))  
  58.   
  59. # 可视化  
  60. with open("alalala.dot", "w") as f:  
  61.      f = tree.export_graphviz(clf, feature_names=vec.get_feature_names(), out_file = f)  

相关推荐