什么是“熵和信息增益”？

#1 楼

我假设在构建决策树的上下文中提到了熵。

为了说明这一点，请想象一下学习将名字分为男性/女性类别的任务。给出了一个名称列表，每个名称分别标记为m或f，我们想学习一个适合数据的模型，并可以用来预测新的看不见的名字的性别。

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

第一步是确定数据的哪些特征与我们要预测的目标类别相关。一些示例功能包括：第一个/最后一个字母，长度，元音个数，以元音结尾的等等。因此，在提取特征后，我们的数据如下所示：

# 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

目标是建立决策树。树的示例为：

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的叶节点，因此预测是男性的（我恰好是，因此树正确地预测了结果）。

决策树是自顶向下构建的，但问题是如何选择在每个节点上拆分哪个属性？答案是找到一种功能，该功能可以将目标类最好地拆分为尽可能纯的子节点（即，不包含男性和女性混合的节点，而仅包含一个类的纯节点）。

这种纯度的度量称为信息。对于到达节点的示例，它代表指定新实例（名字）是男性还是女性时所需的预期信息量。我们根据节点上男性和女性类别的数量进行计算。另一方面，熵是对杂质的一种度量（相反）。它是为值a / b的二进制类定义的，如下所示：

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

下图描述了此二进制熵函数（随机变量可以采用两个值之一） ）。当概率为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通常作为底数的对数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。根据熵的定义：接下来，我们将其与考虑两个子分支的拆分后计算出的熵进行比较。在ends-vowel=1的左侧分支中，我们有：

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

，在ends-vowel=0的右侧分支中，我们有：

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

我们使用每个分支下的实例数作为权重因子（左7个实例，右7个实例）组合左/右熵，并在拆分后得到最终熵：

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

现在，通过比较拆分前后的熵，我们可以获得信息增益的量度，或者通过使用该特定功能进行拆分而获得的信息量：

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

您可以按以下方式解释以上计算：通过使用end-vowels功能进行拆分，我们能够将子树预测结果的不确定性减少0.1518的少量量（以位为单位

在树的每个节点上，对每个特征都执行此计算，并且以贪婪的方式为分割选择了具有最大信息增益的特征（因此倾向于使用产生具有低不确定性/熵的纯裂隙）。此过程是从根节点开始递归应用的，当叶节点包含所有具有相同类的实例时，此过程将停止（无需进一步拆分）。

请注意，我跳过了一些详细信息超出了本文的范围，包括如何处理数字特征，缺失值，过度拟合和修剪树等。

#2 楼

首先，最好了解the measure of information。

我们如何查询信息？

当不太可能发生的事情时，我们说这是个大新闻。另外，当我们说出可预测的内容时，这并不是很有趣。因此，要量化此measure，如果事件的概率为1（可预测），则函数应满足


，如果事件的概率为0，则函数给出0接近0，则该函数应该给出高数值。
如果发生0.5个事件，它将给出interesting-ness的信息。

满足约束的自然度量是

I(X) = -log_2(p)

其中p是事件one bit的概率。并且单位在X中，同一位计算机使用。 0或1。

示例1

普通硬币翻转：

一次硬币翻转可以获取多少信息？

答案：bit

示例2

如果明天有一颗流星撞击地球，那么-log(p) = -log(1/2) = 1 (bit)可以得到22位信息。

如果明天明天升起p=2^{-22}，则它是0位信息。

熵

因此，如果我们对事件p ~ 1的interesting-ness期望，那么它就是熵。
ie熵是事件的趣味性的期望值。

H(Y) = E[ I(Y)]

更正式地说，熵是事件的期望位数。

示例

Y = 1：发生事件X的概率为p

Y = 0：没有发生事件X的概率为1-p

H(Y) = E[I(Y)] = p I(Y==1) + (1-p) I(Y==0) 
     = - p log p - (1-p) log (1-p)

所有日志的日志基数为2。

#3 楼

我无法为您提供图形，但是也许我可以给您一个清晰的解释。

假设我们有一个信息通道，例如每天闪烁一次红色或绿色的指示灯。它传达多少信息？第一个猜测可能是每天一次。但是，如果我们添加蓝色，以便发送方具有三个选项，该怎么办？我们希望有一种信息度量方法，它可以处理除2的幂以外的事物，但仍是可加的（将可能消息的数量乘以2的方式加一）。我们可以通过获取log2（可能的消息数）来完成此操作，但是事实证明，这是一种更通用的方法。

假设我们回到红色/绿色，但是红色灯泡已经烧坏了（这是常识），因此灯泡必须始终闪烁绿色。现在，该频道已无用，我们知道下一次闪烁将是什么，因此该闪烁将不传达任何信息，也不产生任何新闻。现在，我们修理了灯泡，但强加了一个规则，使红色灯泡不能连续闪烁两次。当指示灯闪烁红色时，我们知道下一次闪烁是什么。如果尝试通过此通道发送比特流，则会发现必须使用比位更多的闪存（实际上要多50％）来对它进行编码。而且，如果您要描述一系列闪烁，则可以用更少的位来描述。如果每个闪烁都是独立的（无上下文），则同样适用，但是绿色闪烁比红色闪烁更常见：概率越偏斜，描述序列所需的位数就越少，并且所包含的信息越少。全绿色，灯泡烧坏极限。

事实证明，有一种方法可以根据不同符号的概率来测量信号中的信息量。如果接收到符号xi的概率为pi，则考虑数量

-log pi

pi越小，该值越大。如果xi变为不可能的两倍，则该值将增加固定量（log（2））。这应该使您想起在消息中添加一点。

如果我们不知道符号将是什么（但我们知道概率），则可以通过汇总不同的可能性来计算该值的平均值，我们将得到多少：

I = -Σ pi log(pi)

这是一瞬间的信息内容。

Red bulb burnt out: pred = 0, pgreen=1, I = -(0 + 0)  = 0
Red and green equiprobable: pred = 1/2, pgreen = 1/2, I = -(2 * 1/2 * log(1/2)) = log(2)
Three colors, equiprobable: pi=1/3, I = -(3 * 1/3 * log(1/3)) = log(3)
Green and red, green twice as likely: pred=1/3, pgreen=2/3, I = -(1/3 log(1/3) + 2/3 log(2/3)) = log(3) - 2/3 log(2)

这是消息的信息内容或熵。当不同的符号相等时，它是最大的。如果您是物理学家，则使用自然对数；如果您是计算机科学家，则使用log2并获取位。

#4 楼

我真的建议您阅读有关信息论，贝叶斯方法和MaxEnt的文章。起点是大卫·麦凯（David Mackay）的这本书（在线免费提供）：

http://www.inference.phy.cam.ac.uk/mackay/itila/

那些推理方法确实比文本挖掘更通用，我无法真正设计出一种方法，而无需学习本书或其他有关机器学习和编程的入门书中包含的一些通用基础知识，就可以将其应用于NLP。 MaxEnt贝叶斯方法。

熵和概率论与信息处理和存储之间的联系确实非常深。为了体会一下，香农（Shannon）提出了一个定理，该定理指出，您可以通过一个嘈杂的通信通道无错误地传递的最大信息量等于噪声过程的熵。还有一个定理将您可以压缩一块数据以占用计算机中的最小可能内存的量与生成数据的过程的熵联系起来。

我认为这不是真的有必要去学习传播理论上的所有这些定理，但是如果不学习有关什么是熵，如何计算，它与信息和推理之间的关系等基础知识，就不可能学习到这一点。

#5 楼

当我实现一种算法来计算图像的熵时，我发现了这些链接，请参见此处和此处。

这是我使用的伪代码，您需要对其进行调整以使其适用于文本而不是图像，但是原理应该是相同的。

//Loop over image array elements and count occurrences of each possible
//pixel to pixel difference value. Store these values in prob_array
for j = 0, ysize-1 do $
    for i = 0, xsize-2 do begin
       diff = array(i+1,j) - array(i,j)
       if diff lt (array_size+1)/2 and diff gt -(array_size+1)/2 then begin
            prob_array(diff+(array_size-1)/2) = prob_array(diff+(array_size-1)/2) + 1
       endif
     endfor

//Convert values in prob_array to probabilities and compute entropy
n = total(prob_array)

entrop = 0
for i = 0, array_size-1 do begin
    prob_array(i) = prob_array(i)/n

    //Base 2 log of x is Ln(x)/Ln(2). Take Ln of array element
    //here and divide final sum by Ln(2)
    if prob_array(i) ne 0 then begin
        entrop = entrop - prob_array(i)*alog(prob_array(i))
    endif
endfor

entrop = entrop/alog(2)

我从某个地方获得了此代码，但无法挖掘链接。

#6 楼

非正式地，熵是信息或知识的可用性，信息的缺乏将导致对未来的预测困难，这是高熵（文本挖掘中的下一个单词预测），而信息/知识的可用性将帮助我们更多未来的现实预测（低熵）。

任何类型的相关信息都将减少熵，并帮助我们预测更现实的未来，即信息可以是单词“ meat”存在于句子中或单词“ meat”中不存在。这称为信息增益


形式上

熵缺乏可预测性的顺序

#7 楼

在阅读有关NLTK的书时，您会很感兴趣地阅读有关MaxEnt分类器模块的信息http://www.nltk.org/api/nltk.classify.html#module-nltk.classify.maxent

对于文本挖掘分类，步骤可能是：预处理（加标记，汽蒸，通过信息增益进行特征选择...），转换为数字（频率或TF-IDF）（我认为这是了解何时使用文本作为仅接受数字的算法的输入），然后使用MaxEnt进行分类，请确保这只是一个示例。