1.ID.3算法
1.1算法原理：
算法的核心是在决策树各个节点上，应用信息增益准则选择特征,递归的构建决策树。
算法是一种经典的决策树学习算法，由Quinlan于1979年提出。算法主要针对属性选择问题。是决策树学习方法中最具影响和最为典范的算法，该方法使用信息增益选择测试属性。当获取信息时将不确定的内容转为确定的内容，因此信息伴随不确定性，从直觉上讲，小概率事件比大概率事件包含的信息量更大，如果某件事情是百年一见，这肯定比习以为常的事件包含的信息量大。
如何度量信息量的大小呢？信息增益。
具体方法是：
下面内容引用自《李航统计学习方法》
从根节点开始对节点计算所有可能的特征的信息增益，选择信息增益最大的特征作为节点的特征，由该特征的不同取值建立此节点，再对子节点递归的调用以上方法构建决策树，直到所有特征的信息增益均最小或没有特征可以选择为止，最后得到一棵决策树，相当于用极大似然法进行概率模型的选择。
ID3算法
输入：训练数据集、特征集和阈值。
输出：决策树。
1）若D中所有实例属于同一类Ck，则T为单结点树，并将类Ck于作为该结点的类标记，返回T。
2）若A等于空集，则T为单节点数，并将D中实例数最大的类似于作为该结点的类标记返回T。
3）否则，计算A中各特征对D的信息增益选择信息增益最大的特征Ag.
4）如果Ag的信息增益小于阈值，则置T为单结点树必将D中实例数最大的类Ck作为该结点的类标记返回T。否则对Ag的每一个可能值Ai，依Ag等于Ai将D分割为若干非空子集Di，将Di中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T。
5）对第i个子结点，以Di为训练集以A-{Ag}为特征集递归的调用步骤1)到步骤5），得到子树Ti，返回Ti。
熵的公式:
条件熵计算公式：
信息增益：
Gini系数：
1.2 下面以鸢尾花数据集开始实现ID3算法吧！
首先，导包！
import numpy as np
import pandas as pd
from matplotlib import pyplot as plt
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
然后，让我们来定义两个类：Node和DeciTree
class Node:
def __init__(self,root=True,label = None, feature_name=None, feature=None):
self.root = root
self.label = label
self.feature_name = feature_name
self.feature = feature
self.tree = {}
self.result = {"label":self.label,
"feature":self.feature,
"tree":self.tree}
def __repr__(self):
return '{}'.format(self.result)
def add_node(self,val,node):
self.tree[val] = node
def predict(self,features):
if self.root is True:
return self.label
return self.tree[features[self.feature]].predict(features)
class DeciTree:
def __init__(self,epsilon=0.1):
self.epsilon = epsilon
self._tree = {}
@staticmethod
def calculate_entropy(datasets):
length = len(datasets)
label_count = {}
for i in range(length):
label = datasets[i][-1]
if label not in label_count:
label_count[label] = 0
label_count[label] +=1
entropy = -sum([(p/length)*log(p/length,2) for p in label_count.values()])
return entropy
def cal_cond_entropy(self,datasets,axis =0):
length = len(datasets)
feature_sets = {}
for c in range(length):
feature = datasets[c][axis]
if feature not in feature_sets:
feature_sets[feature] =[]
feature_sets[feature].append(datasets[c])
cond_entropy = sum([(len(p)/length)*self.calculate_entropy(p) for p in feature_sets.values()])
return cond_entropy
@staticmethod
def info_gain(entropy,cond_entropy):
return entropy-cond_entropy
def info_gain_train(self,datasets):
count = len(datasets[0])-1
entropy = self.calculate_entropy(datasets)
best_feature = []
for c in range(count):
c_info_gain = self.info_gain(entropy,self.cal_cond_entropy(datasets,axis=c))
best_feature.append((c,c_info_gain))
best_ = max(best_feature, key = lambda x:x[-1])
return best_
def train(self,train_data):
_,y_train,features = train_data.iloc[:,:-1],train_data.iloc[:,-1],train_data.columns[:-1]
#step1,对应上述ID3算法中的1）
if len(y_train.value_counts())==1:
return Node(root=True
,label = y_train.iloc[0])
#step2对应上述ID3算法中的2）
if len(features)==0:
return Node(root=True
,label = y_train.value_counts().sort_values(ascending=False).index[0])
#step3 对应上述ID3算法中的3）
max_feature,max_info_gain = self.info_gain_train(np.array(train_data))
max_feature_name = features[max_feature]
#step4 对应上述ID3算法中的4）
if max_info_gain < self.epsilon:
return Node(root=True
,label=y_train.value_counts().sort_values(ascending=False).index[0])
#step5 对应上述ID3算法中的5）
node_tree = Node(root=False
,feature_name = max_feature_name
,feature=max_feature)
feature_list = train_data[max_feature_name].value_counts().index
for f in feature_list:
sub_train_df = train_data.loc[train_data[max_feature_name]==f].drop([max_feature_name],axis=1)
sub_tree = self.train(sub_train_df)
node_tree.add_node(f,sub_tree)
return node_tree
def fit(self,train_data):
self._tree = self.train(train_data)
return self._tree
def predict(self,x_test):
return self._tree.predict(x_test)
数据处理
获得数据集，转换数据的类型为Dateframe并将数据“合并成一张表”。
#下载数据集iris
iris = load_iris()
#print(iris.feature_names)
data,target = iris.data,iris.target
data = pd.DataFrame(data,columns=iris.feature_names)
target = pd.DataFrame(target)
datasets= data.join(target)
1.3 实例化喂数据
dt = DeciTree()
tree = dt.fit(datasets)
tree
运行结果将这棵树以字典的形式打印出来。
2.使用sklearn实现决策树
step1 一如既往的从导包开始。
import numpy as np
import pandas as pd
from matplotlib import pyplot as plt
from sklearn import tree
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
step2 数据预处理
#下载数据集iris
iris = load_iris() #下载原始数据集
#print(iris.feature_names) out: ['sepal length', 'sepal width', 'petal length', 'petal width']
data,target = iris.data,iris.target
data = pd.DataFrame(data,columns=iris.feature_names)#转化数据的数据类型
target = pd.DataFrame(target)
datasets= data.join(target)
#datasets.info()
#datasets.head() 查看前五个数据
step3 种下一棵树
实例化分类器，训练分类器
x_train,x_test,y_train,y_test = train_test_split(data,target,test_size = 0.3)
clf = tree.DecisionTreeClassifier(criterion="gini") #实例化分类器。
clf.fit(x_train, y_train) #通过接口为数据。
score = clf.score(x_test, y_test) #查看分类器的性能
step4 把树画出来吧!
feature_name=['sepal length', 'sepal width', 'petal length', 'petal width']
from sklearn.tree import export_graphviz
import graphviz
fig_data = export_graphviz(clf
,feature_names = feature_name
,class_names = ['0:setosa', '1:virginica','2:versicolor']
,filled = True
,rounded = True)
#out_file = "my_tree.pdf")
graph = graphviz.Source(fig_data)
树长这样
决策树（鸢尾花数据集）
网友评论