什么是“熵和信息增益”？
我正在阅读这本书 (NLTK)，它令人困惑。 熵是 defined as：
熵是每个标签的概率乘以同一标签的对数概率的总和
如何在文本挖掘方面应用熵和最大熵？有人可以给我一个简单，简单的例子（视觉）吗？
我假设在构建 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，我们首先测试“is the length<7?”，答案是 yes，所以我们沿着那个分支走。在分支之后，下一个测试“is the number of vowels<3?”再次评估为 true。这导致一个标记为 m 的叶节点，因此预测是 male（我恰好是，所以树预测了结果 correctly）。
决策树是 built in a top-down fashion，但问题是如何选择在每个节点处拆分哪个属性？答案是找到最能将目标类划分为最纯粹的子节点的特征（即：不包含男性和女性混合的节点，而是只有一个类的纯节点）。
这种纯度的度量称为information。它表示指定到达节点的示例是否应将新实例（名字）分类为男性或女性所需的 information 的 expected 数量。我们根据节点上的男性和女性类的数量来计算它。
另一方面，Entropy 是 杂质 的度量（相反）。它是为具有值 a/b 的 binary class 定义的：
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）时，熵函数的最小值为零。
https://i.stack.imgur.com/OUgcx.png
当然，熵的定义可以推广到具有 N 个结果（不仅仅是两个）的离散随机变量 X：
https://i.stack.imgur.com/vIFD7.png
（公式中的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 个实例向右），并得到拆分后的最终熵：
Entropy_after = 7/14*Entropy_left + 7/14*Entropy_right = 0.7885
现在通过比较拆分前后的熵，我们获得了 information gain 的度量，或者我们通过使用该特定特征进行拆分获得了多少信息：
Information_Gain = Entropy_before - Entropy_after = 0.1518
您可以将上述计算解释为：通过使用 end-vowels 特征进行拆分，我们能够将子树预测结果中的不确定性减少 0.1518（在 bits 中测量为 { 2})。
在树的每个节点上，对每个特征都执行此计算，并以 greedy 的方式选择具有最大信息增益的特征进行拆分（因此有利于产生 具有低不确定性/熵的纯分裂）。此过程从根节点向下递归应用，并在叶节点包含所有具有相同类的实例时停止（无需进一步拆分）。
请注意，我跳过了一些超出本文范围的 details，包括如何处理 numeric features、missing values、overfitting 和 pruning 树等。
首先，最好理解 the measure of information。
我们如何衡量信息？
当一些不太可能发生的事情发生时，我们说这是一个大新闻。此外，当我们说一些可预测的事情时，它并不是很有趣。所以要量化这个interesting-ness，函数应该满足
如果事件的概率为 1（可预测），则函数给出 0
如果事件的概率接近 0，那么函数应该给出高数
如果发生 0.5 个事件的概率，它会提供一位信息。
满足约束的一种自然度量是
I(X) = -log_2(p)
其中 p 是事件 X 的概率。并且单位在bit，同位计算机使用。 0 或 1。
示例 1
公平硬币翻转：
我们可以从一次硬币翻转中获得多少信息？
答案：-log(p) = -log(1/2) = 1 (bit)
示例 2
如果明天有流星撞击地球，p=2^{-22} 那么我们可以获得 22 位信息。
如果明天太阳升起，p ~ 1 那么它是 0 位信息。
熵
因此，如果我们对事件 Y 的 interesting-ness 取期望，那么它就是熵。即熵是事件有趣性的期望值。
H(Y) = E[ I(Y)]
更正式地说，熵是事件的预期位数。
例子
= 1：事件 X 以概率 p 发生
= 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。
我不能给你图形，但也许我可以给出一个清晰的解释。
假设我们有一个信息通道，例如每天闪烁一次红色或绿色的灯。它传达了多少信息？第一个猜测可能是每天一个比特。但是如果我们添加蓝色，让发送者有三个选项呢？我们希望有一个可以处理除 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 并获取位。
我真的建议你阅读信息论、贝叶斯方法和 MaxEnt。从 David Mackay 的这本书（可在线免费获得）开始：
http://www.inference.phy.cam.ac.uk/mackay/itila/
这些推理方法确实比文本挖掘更通用，如果不学习本书或其他机器学习和 MaxEnt 贝叶斯入门书籍中包含的一些一般基础知识，我无法真正设计出如何将其应用于 NLP方法。
熵和概率论与信息处理和存储之间的联系非常非常深刻。试一试，香农有一个定理，它指出您可以通过嘈杂的通信通道而没有错误地传递的最大信息量等于噪声过程的熵。还有一个定理将您可以压缩多少数据以占用计算机中尽可能少的内存与生成数据的过程的熵联系起来。
我不认为你真的有必要去学习所有那些关于通信理论的定理，但是如果不学习什么是熵、它是如何计算的、它与信息和推理有什么关系等基础知识，就不可能学习这个...
非正式地
熵是信息或知识的可用性，缺乏信息将导致难以预测未来，即高熵（文本挖掘中的下一个词预测），而信息/知识的可用性将帮助我们更现实地预测未来（低熵）。
任何类型的相关信息都将减少熵并帮助我们预测更现实的未来，这些信息可以是句子中存在单词“meat”或不存在单词“meat”。这称为信息增益
正式地
熵是缺乏可预测性的顺序
当我实施一种算法来计算图像的熵时，我发现了这些链接，请参阅 here 和 here。
这是我使用的伪代码，您需要对其进行调整以处理文本而不是图像，但原理应该相同。
//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)
我从某个地方得到了这个代码，但我无法挖掘出链接。
当您阅读有关 NLTK 的书时，您会很感兴趣阅读有关 MaxEnt 分类器模块 http://www.nltk.org/api/nltk.classify.html#module-nltk.classify.maxent
对于文本挖掘分类，步骤可能是：预处理（标记化，蒸汽，使用信息增益的特征选择......），转换为数字（频率或 TF-IDF）（我认为这是使用时理解的关键步骤文本作为仅接受数字的算法的输入），然后使用 MaxEnt 进行分类，这只是一个示例。
