决策树ID3算法中选择分区背后的直觉

Question

我正在尝试理解ML中决策树分类器背后的直觉。我知道决策树中每个节点的目标是进一步划分可能标签的当前空间，以便根据该节点上给定问题的答案来消除尽可能多的候选标签。但是，这与基于最小化分区“熵”的属性选择分区有什么关系？其中“熵”的定义如下：

H(S) = −p_1*log2(p_1) −... −p_n*log2(p_n)

和分区熵：

H = q_1*H(S_1) +...+ q_m*H(S_m)

with H(S): entropy of a given subset
     H: partition entropy
     p_i's: proportions of data belonging to class i
     q_i's: proportions of data belonging to subset i based on given partition

此外，每个节点上的“问题”是否必须是是/否问题，从而将当前标签空间拆分为2个？而不是3个或更多的子集？任何明确的例子都将受到高度赞赏。

Answer 1

。但是，这与基于最小化分区“熵”的属性选择分区有什么关系？

熵(这里是香农熵)是不确定性的度量，它只是表示每个类的分离有多清晰。如果熵很高-那么就有来自不同类别的大量样本，因此在这个特征中进行拆分将是有价值的，因为显然需要更多的决策规则来分离对象。另一方面，如果熵很小-节点已经主要由来自一个类别的样本组成，因此没有进一步拆分的点。特别地，当其中一个类的概率等于1时，你将得到0熵，因此获得了最小值，如果你在这里创建一个叶子，那么正确分类的可能性是100%。

同样，每个节点的“问题”必须是一个是/否的问题，从而将当前的标签空间分成2个？

不，您可以很容易地创建具有任意数量的子代的决策树。从计算的角度来看，简单地将两部分拆分为两部分要简单得多(量化是否存在一个拆分点比是否有多个拆分点共同创建良好的拆分点更容易)。特别是，这也是为什么你可以有效地学习线性分类器(如logistic回归，感知器，支持向量机)而不是多阈值线性分类器(如多阈值熵线性分类器)的原因-构建多阈值模型要复杂得多，但仍有可能，并且在某些情况下是有利的。

Answer 2

决策树算法

该算法对分类器和回归器都有效。

用于分类器演示

import pandas as pd

import numpy as np

import matplotlib.pyplot as plt

from sklearn.tree import DecisionTreeClassifier

from sklearn.tree import export_graphviz

from sklearn.model_selection import train_test_split


df=pd.read_csv("D:\\heart.csv")

iris={"data":np.array(df[["age","sex","cp","trestbps","chol","fbs","restecg","thalach","exang","oldpeak","slope","ca","thal"]],ndmin=2),"target":np.array(df["target"]),"target_names":np.array(["No_problem","Problem"])}

X_train,X_test,Y_train,Y_test=train_test_split(iris["data"],iris["target"],random_state=0
)

dt=DecisionTreeClassifier(criterion="gini",random_state=100,max_depth=10,min_samples_leaf=2)

dt.fit(X_train,Y_train)

x_new=np.array([[71,0,0,112,149,0,1,125,0,1.6,1,0,2]])

prediction=dt.predict(x_new)

print("The value is : {}\n".format(prediction))

print("The name is : {}\n".format(iris["target_names"][prediction]))

print("Accurecy is : {:.2f}".format(dt.score(X_train,Y_train)*100))