math - 什么是 "entropy and information gain"？

Question

我正在阅读这本书 ( NLTK ) 并且令人困惑。 熵 是 defined as :

Entropy is the sum of the probability of each label times the log probability of that same label

如何在文本挖掘方面应用熵和最大熵？有人可以给我一个简单的例子(视觉)吗？

Answer 1

我假设在建筑 decision trees 的上下文中提到了熵.

为了说明，想象一下 learning 的任务至 classify名字分成男性/女性组。给出一个名称列表，每个名称都标有 m或 f ，我们要学一个model符合数据，可用于预测新的未知名字的性别。

name       gender
-----------------        Now we want to predict 
Ashley        f              the gender of "Amro" (my name)
Brian         m
Caroline      f
David         m

第一步是 deciding什么 features的数据与我们要预测的目标类别相关。一些示例特征包括:第一个/最后一个字母、长度、元音数量、是否以元音结尾等。所以在特征提取后，我们的数据看起来像:

# name    ends-vowel  num-vowels   length   gender
# ------------------------------------------------
Ashley        1         3           6        f
Brian         0         2           5        m
Caroline      1         4           8        f
David         0         2           5        m

目标是建立一个 decision tree . tree 的示例将会:

length<7
|   num-vowels<3: male
|   num-vowels>=3
|   |   ends-vowel=1: female
|   |   ends-vowel=0: male
length>=7
|   length=5: male

基本上每个节点代表对单个属性执行的测试，我们根据测试结果向左或向右移动。我们继续遍历树，直到到达包含类预测的叶节点( m 或 f )

因此，如果我们沿着这棵树运行名称 Amro，我们首先要测试“长度是否小于 7？”答案是肯定的，所以我们沿着那个分支走下去。跟着分支，下一个测试“是元音数<3？”再次评估为真。这导致标记为 m 的叶节点，因此预测是男性(我碰巧是，所以树预测了结果 correctly )。

决策树是 built in a top-down fashion ，但问题是如何选择在每个节点拆分哪个属性？答案是找到最能将目标类拆分为最纯可能的子节点的特征(即:不包含男性和女性混合的节点，而是只有一个类的纯节点)。

这种纯度度量称为 information .它代表 expected金额 information考虑到到达节点的示例，需要指定新实例(名字)应归类为男性还是女性。我们计算它
基于节点上的男性和女性类的数量。

Entropy另一方面是杂质的量度(相反)。它是为 binary class 定义的值 a/ b作为:

Entropy = - p(a)*log(p(a)) - p(b)*log(p(b))

此 binary entropy function如下图所示(随机变量可以取两个值之一)。当概率为 p=1/2 时达到最大值, 意思是 p(X=a)=0.5或类似 p(X=b)=0.5有 50%/50% 的机会成为 a或 b (不确定性最大)。当概率为 p=1 时，熵函数的最小值为零或 p=0完全确定(分别为 p(X=a)=1 或 p(X=a)=0 ，后者意味着 p(X=b)=1 )。



当然，熵的定义可以推广到具有 N 个结果(不仅仅是两个)的离散随机变量 X:



(公式中的 log 通常取为 logarithm to the base 2 )

回到我们的名称分类任务，让我们看一个例子。想象一下，在构建树的过程中的某个时刻，我们正在考虑以下拆分:

     ends-vowel
      [9m,5f]          <--- the [..,..] notation represents the class
    /          \            distribution of instances that reached a node
   =1          =0
 -------     -------
 [3m,4f]     [6m,1f]

如您所见，在拆分之前，我们有 9 名男性和 5 名女性，即 P(m)=9/14和 P(f)=5/14 .根据熵的定义:

Entropy_before = - (5/14)*log2(5/14) - (9/14)*log2(9/14) = 0.9403

接下来，我们将其与通过查看两个子分支考虑拆分后计算的熵进行比较。在 ends-vowel=1 的左分支中， 我们有:

Entropy_left = - (3/7)*log2(3/7) - (4/7)*log2(4/7) = 0.9852

和 ends-vowel=0的右分支， 我们有:

Entropy_right = - (6/7)*log2(6/7) - (1/7)*log2(1/7) = 0.5917

我们使用每个分支下的实例数将左/右熵组合为 weight factor (7个实例向左，7个实例向右)，并得到 split 后的最终熵:

Entropy_after = 7/14*Entropy_left + 7/14*Entropy_right = 0.7885

现在通过比较 split 前后的熵，我们得到了 information gain 的度量。 ，或者我们通过使用该特定功能进行拆分获得了多少信息:

Information_Gain = Entropy_before - Entropy_after = 0.1518

您可以将上述计算解释如下:通过使用 end-vowels 进行拆分特征，我们能够将子树预测结果的不确定性降低 0.1518(在 bits 中测量为 units of information)。

在树的每个节点上，对每个特征都进行这个计算，在 greedy中选择信息增益最大的特征进行 split 。方式(因此有利于产生具有低不确定性/熵的纯 split 的特征)。此过程从根节点向下递归应用，并在叶节点包含所有具有相同类的实例时停止(无需进一步拆分)。

请注意，我跳过了一些 details超出了本文的范围，包括如何处理 numeric features , missing values , overfitting和 pruning树木等。