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

为了说明这一点，想象将学习到分类的名字分成男性/女性组的任务。给出一个名字列表，每个名字都标记为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)。

因此，如果我们在这棵树中运行名字银行，我们从测试“长度是7吗?”开始，答案是是的，所以我们沿着这个分支向下运行。在分支之后，下一个测试“元音的数量是3吗?”再次计算为真正的。这将导致一个标记为m的叶节点，因此预测是男性(我恰好是，所以树预测的结果是正确)。

决策树是以自上而下的方式构建，但问题是如何选择在每个节点上拆分哪个属性?答案是找到能最好地将目标类划分为最纯粹的子节点的特性(即:不包含男女混合的节点，而是只有一个类的纯节点)。

另一方面，熵<强> < / >强是杂质(相反)的度量。对于值为a/b的二进制类，它被定义为:

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

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

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

(公式中的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。根据熵的定义:

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

我们使用沿着每个分支的实例数加权因子来组合左/右熵(7个实例向左，7个实例向右)，并得到分裂后的最终熵:

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

现在通过比较拆分前后的熵，我们得到了< >强信息增益< / >强的度量，或者我们通过使用特定的特征进行拆分获得了多少信息:

Information_Gain = Entropy_before - Entropy_after = 0.1518

你可以这样解释上面的计算:通过使用end-vowels特征进行拆分，我们能够将子树预测结果中的不确定性降低0.1518(以位作为单位的信息来衡量)。

在树的每个节点上，对每个特征执行此计算，并以贪婪的方式选择具有最大信息增益的特征进行分割(因此倾向于产生具有低不确定性/熵的纯分割的特征)。这个过程从根节点向下递归地应用，当叶子节点包含所有具有相同类的实例时(不需要进一步拆分它)，该过程就会停止。

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

当我实现一个算法来计算图像的熵时，我发现了这些链接，参见在这里和在这里。

这是我使用的伪代码，你需要调整它来处理文本而不是图像，但原则应该是相同的。

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

我从某处得到了这个代码，但我找不到链接。

我不能给你图表，但也许我可以给出一个明确的解释。

假设我们有一个信息通道，比如一盏灯，每天闪一次红灯或绿灯。它传达了多少信息?第一个猜测可能是每天一点点。但是如果我们添加蓝色，那么发送者就有三个选项呢?我们希望有一种信息度量，它可以处理除2的幂以外的事情，但仍然是加法(即可能消息的数量乘以两个增加了的方式)。我们可以通过取log₂(可能消息的数量)来做到这一点，但事实证明有一种更通用的方法。

假设我们回到了红色/绿色，但是红色灯泡已经烧坏了(这是常识)，所以灯必须总是闪烁绿色。该频道现在是无用的，我们知道下一个闪光会是什么所以闪光传达没有信息，没有新闻。现在我们修理灯泡，但强加了一个规则，红色灯泡不能连续闪烁两次。当灯闪红时，我们知道下一闪是什么。如果你试图通过这个通道发送一个比特流，你会发现你必须用比你拥有的比特更多的闪光来编码它(事实上，多50%)。如果你想描述一连串的闪光，你可以用更少的比特。如果每个闪光都是独立的(与上下文无关)，同样适用，但绿色闪光比红色闪光更常见:概率越偏，描述序列所需的比特就越少，它包含的信息就越少，一直到全绿色，灯泡烧坏的极限。

事实证明，有一种方法可以测量信号中的信息量，基于不同符号的概率。如果接收符号x_我的概率是p_我，那么考虑数量

-log pi

p_我越小，这个值就越大。如果x_我变得两倍的不可能，这个值增加一个固定的量(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)

这是消息的信息内容或熵。当不同的符号是等概率时，它是最大的。如果你是物理学家，你会用自然对数，如果你是计算机科学家，你会用log₂得到比特。

我真的建议你读一下信息理论，贝叶斯方法和MaxEnt。我们可以从大卫·麦凯(David Mackay)的这本书(网上免费下载)开始:

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

这些推理方法真的比文本挖掘更通用，如果不学习这本书或其他关于机器学习和MaxEnt贝叶斯方法的介绍性书籍中的一些基本知识，我真的无法设计如何将其应用到NLP中。

熵和概率论与信息处理和存储之间的联系非常非常深。让我们来了解一下，香农提出了一个定理，即在一个有噪声的通信信道中，你能无错误传递的最大信息量等于噪声过程的熵。还有一个定理把你能压缩多少数据来占用计算机中尽可能少的内存与生成数据的过程的熵联系起来。

我不认为你真的有必要去学习所有这些关于通信理论的定理，但如果不学习什么是熵，它是如何计算的，它与信息和推理的关系等基本知识，就不可能学习这些……

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

我们如何measure信息?

当一件不太可能发生的事情发生时，我们说这是一个大新闻。此外，当我们说一些可预测的事情时，它真的不有趣。所以要量化这个interesting-ness，函数应该满足

• 如果事件的概率为1(可预测)，则函数给出0
• 如果事件的概率接近于0，则函数应给出较高的数值
• 如果概率为0.5的事件发生，则给出one bit的信息。

满足约束条件的一个自然度量是

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位信息。

熵

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为底的对数。

当你在读一本关于NLTK的书时，你会很有趣地读到MaxEnt分类器模块http://www.nltk.org/api/nltk.classify.html#module-nltk.classify.maxent

对于文本挖掘分类，步骤可以是:预处理(标记化，蒸，信息增益的特征选择……)，转换为数字(频率或TF-IDF)(我认为这是理解使用文本作为只接受数字的算法的输入时的关键步骤)，然后使用MaxEnt进行分类，当然这只是一个例子。

非正式的

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

任何类型的相关信息都会减少熵，帮助我们预测更现实的未来，这些信息可以是句子中有“肉”这个词，也可以是句子中没有“肉”这个词。这被称为信息增益

正式

熵是缺乏可预测性的顺序