ID3决策树算法中如何计算熵?

人工智能 机器学习 分类 决策树 id3-算法
2021-11-04 18:47:28

这是熵的定义

H(S)=xXp(x)log2p(x)

维基百科对熵的描述打破了公式,但我仍然不知道如何确定X, 定义为

中的类集S

p(x), 定义为

类中元素个数的比例x到集合中的元素个数S.

任何人都可以进一步分解以解释如何找到p(x)?

1个回答

假设您有数据:

color  height  quality
=====  ======  =======
green  tall    good
green  short   bad
blue   tall    bad
blue   short   medium
red    tall    medium
red    short   medium

在此示例中计算质量的熵:

X  = {good, medium, bad}
x1 = {good}, x2 = {bad}, x3 = {medium}

X 中每个 x 的概率:

p1 = 1/6 = 0.16667
p2 = 2/6 = 0.33333
p3 = 3/6 = 0.5

对数是:

log2(p1) = -2.58496
log2(p2) = -1.58496
log2(p3) = -1.0

因此集合的熵是:

H(X) = - (0.16667 * -2.58496) - (0.33333 * -1.58496) - (0.5 * -1.0)
     = 1.45915

通过问题中的公式。

剩下的任务是为每个属性迭代这个过程以形成树的节点。