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

Question

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

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？

不，您可以轻松创建具有任意数量子项的决策树。从计算的角度来看，简单地分裂成两个要简单得多（量化是否存在一个好的分裂点比是否存在多个一起创建良好分裂的分裂点更容易）。特别是，这也是您可以有效学习线性分类器（如逻辑回归、感知器、支持向量机）而不是多阈值线性分类器（如多阈值熵线性分类器）的原因 - 构建多阈值模型要复杂得多，但仍然是可能的在某些情况下是有利的。

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))

Answer 3

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

H(S) = −p_1log2(p_1) −... −p_nlog2(p_n) 和分区熵：

H = q_1H(S_1) +...+ q_mH(S_m)

H(S)：给定子集的熵 H：分区熵 p_i's：属于 i 类的数据比例 q_i's：基于给定分区属于子集 i 的数据比例 另外，每个节点的“问题”是否必须是是/否问题，从而将当前标签空间分成2部分？而不是 3 个或更多子集？任何明确的例子将不胜感激。