blocks|key|3075404|text|我假设熵是在构建的上下文中提到的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3075405|为了说明这一点，想象一下learning将名字classify到男性/女性组中的任务。也就是说，给定一个名字列表，每个名字都标有m或f，我们希望学习一个符合数据的model，并可以用来预测一个新的看不见的名字的性别。|offset|length|style|CODE|3075406|name+++++++gender
-----------------++++++++Now+we+want+to+predict+
Ashley++++++++f++++++++++++++the+gender+of+"Amro"+(my+name)
Brian+++++++++m
Caroline++++++f
David+++++++++m|code-block|syntax|javascript|3075407|第一步是deciding，数据的与我们想要预测的目标类相关。一些示例特征包括:首字母/末尾字母、长度、元音数量、是否以元音结尾等。因此，在特征提取之后，我们的数据如下所示：|3075408|#+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|3075409|我们的目标是构建一个decision+tree。tree的一个例子是：|3075410|length<7
%7C+++num-vowels<3:+male
%7C+++num-vowels>=3
%7C+++%7C+++ends-vowel=1:+female
%7C+++%7C+++ends-vowel=0:+male
length>=7
%7C+++length=5:+male|3075411|基本上，每个节点代表对单个属性执行的测试，我们根据测试结果向左或向右移动。我们继续遍历树，直到到达包含类预测(m或f)的叶节点|3075412|所以如果我们在这棵树下运行Amro这个名字，我们首先测试"is+the+length<7?“答案是肯定的，所以我们沿着那条支路走下去。在分支之后，下一个测试"is+the+number+of+vowels<3?“再次计算为true。这导致了一个标记为m的叶节点，因此预测是男性的(我碰巧是男性，所以树预测了结果correctly)。|3075413|决策树是built+in+a+top-down+fashion，但问题是如何选择在每个节点上拆分哪个属性？答案是找到最能将目标类划分为最纯粹的子节点的功能(即:不包含男性和女性混合的节点，而不是只包含一个类的纯节点)。|3075414|这种纯度的度量被称为。它表示在给定到达节点的示例的情况下，指定新实例(名字)应该被归类为男性还是女性所需的information的expected大小。我们根据节点上的男性和女性类的数量来计算它。|3075415|另一方面，是杂质的度量(相反)。它为具有值a/b的binary+class定义为：|3075416|Entropy+=+-+p(a)*log(p(a))+-+p(b)*log(p(b))|3075417|此binary+entropy+function如下图所示(随机变量可以取两个值中的一个)。当概率为p=1/2时，它达到最大值，这意味着p(X=a)=0.5或类似的p(X=b)=0.5有50%25/50%25的机会是a或b+(不确定性最大)。当概率为p=1或p=0且完全确定(分别为p(X=a)=1或p(X=a)=0，后者意味着p(X=b)=1)时，熵函数为零最小。|3075418|​|3075419|📷|atomic|3075420|3075421|当然，熵的定义可以推广到具有N个结果(而不仅仅是两个)的离散随机变量X：|3075422|3075423|3075424|3075425|(公式中的log通常作为)|3075426|3075427|回到我们的名称分类任务，让我们来看一个例子。想象一下，在构建树的过程中，我们考虑了以下拆分：|3075428|+++++ends-vowel
++++++[9m,5f]++++++++++<---+the+[..,..]+notation+represents+the+class
++++/++++++++++\++++++++++++distribution+of+instances+that+reached+a+node
+++=1++++++++++=0
+-------+++++-------
+[3m,4f]+++++[6m,1f]|3075429|如你所见，在拆分之前，我们有9个男性和5个女性，即P(m)=9/14和P(f)=5/14。根据熵的定义：|3075430|Entropy_before+=+-+(5/14)*log2(5/14)+-+(9/14)*log2(9/14)+=+0.9403|3075431|接下来，我们将其与考虑拆分后通过查看两个子分支计算的熵进行比较。在ends-vowel=1的左分支中，我们有：|3075432|Entropy_left+=+-+(3/7)*log2(3/7)+-+(4/7)*log2(4/7)+=+0.9852|3075433|在ends-vowel=0的右侧分支中，我们有：|3075434|Entropy_right+=+-+(6/7)*log2(6/7)+-+(1/7)*log2(1/7)+=+0.5917|3075435|我们使用每个分支下的实例数作为weight+factor来组合左右熵(7个实例向左，7个实例向右)，并在拆分后获得最终的熵：|3075436|Entropy_after+=+7/14*Entropy_left+%2B+7/14*Entropy_right+=+0.7885|3075437|现在，通过比较拆分前和拆分后的熵，我们获得了的度量，或通过使用该特定特征进行拆分获得了多少信息：|3075438|Information_Gain+=+Entropy_before+-+Entropy_after+=+0.1518|3075439|您可以将上面的计算解释为:通过使用end-vowels功能进行拆分，我们能够将子树预测结果中的不确定性减少0.1518+(以度量为)。|3075440|在树的每个节点，对每个特征执行该计算，并且以greedy方式选择具有最大信息增益的特征用于分割(从而有利于产生具有低不确定性/熵的纯分割的特征)。此过程从根节点向下递归应用，并在叶节点包含具有相同类的实例时停止(不需要进一步拆分它)。|3075441|请注意，我跳过了一些details，这些内容超出了本文的范围，包括如何处理numeric+features、missing+values、overfitting和pruning树等。|3075442|entityMap|0|LINK|mutability|MUTABLE|url|https://en.wikipedia.org/wiki/Supervised_learning|1|https://en.wikipedia.org/wiki/Statistical_classification|2|https://en.wikipedia.org/wiki/Predictive_modelling|3|https://en.wikipedia.org/wiki/Feature_selection|4|https://en.wikipedia.org/wiki/Decision_tree|5|https://en.wikipedia.org/wiki/Tree_%2528data_structure%2529|6|https://en.wikipedia.org/wiki/Evaluation_of_binary_classifiers|7|https://en.wikipedia.org/wiki/ID3_algorithm|8|https://en.wikipedia.org/wiki/Self-information|9|https://en.wikipedia.org/wiki/Expected_value|10|https://en.wikipedia.org/wiki/Binary_classification|11|https://en.wikipedia.org/wiki/Binary_entropy_function|12|IMAGE|IMMUTABLE|imageUrl|https://ask.qcloudimg.com/http-save/yehe-900000/31cca456a25e079b408ced93d97e919a.png|imageAlt|13|https://ask.qcloudimg.com/http-save/yehe-900000/a390e421d809d42cf03059a91276afd7.png|14|https://en.wikipedia.org/wiki/Weighted_arithmetic_mean|15|https://en.wikipedia.org/wiki/Greedy_algorithm|16|https://en.wikipedia.org/wiki/C4.5_algorithm|17|https://en.wikipedia.org/wiki/Discretization_of_continuous_features|18|https://en.wikipedia.org/wiki/Missing_data|19|https://en.wikipedia.org/wiki/Overfitting|20|https://en.wikipedia.org/wiki/Pruning_%2528decision_trees%2529^0|0|1S|1|1U|1|C|8|0|N|8|1|29|5|2|0|0|4|8|3|0|0|A|D|4|O|4|5|0|0|1J|1|1L|1|0|3H|1|4B|9|6|0|4|R|7|0|1H|B|8|1T|8|9|0|L|1|N|1|P|C|A|0|0|1E|5|1W|A|2A|A|2W|1|2Y|1|3D|3|3H|3|3T|8|42|8|4G|8|1|N|B|0|0|0|1|C|0|0|0|0|0|1|D|0|0|5|3|0|0|0|0|P|9|Z|9|0|0|X|C|0|0|1|C|0|0|F|D|E|0|0|0|0|H|A|0|M|6|F|0|A|7|G|11|G|H|1I|E|I|1X|B|J|29|7|K|0^^$0|@$1|2|3|4|5|6|7|3W|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|3X|8|@$D|3Y|E|3Z|F|G]|$D|40|E|41|F|G]]|9|@$D|42|E|43|1|44]|$D|45|E|46|1|47]|$D|48|E|49|1|4A]]|A|$]]|$1|H|3|I|5|J|7|4B|8|@]|9|@]|A|$K|L]]|$1|M|3|N|5|6|7|4C|8|@]|9|@$D|4D|E|4E|1|4F]]|A|$]]|$1|O|3|P|5|J|7|4G|8|@]|9|@]|A|$K|L]]|$1|Q|3|R|5|6|7|4H|8|@]|9|@$D|4I|E|4J|1|4K]|$D|4L|E|4M|1|4N]]|A|$]]|$1|S|3|T|5|J|7|4O|8|@]|9|@]|A|$K|L]]|$1|U|3|V|5|6|7|4P|8|@$D|4Q|E|4R|F|G]|$D|4S|E|4T|F|G]]|9|@]|A|$]]|$1|W|3|X|5|6|7|4U|8|@$D|4V|E|4W|F|G]]|9|@$D|4X|E|4Y|1|4Z]]|A|$]]|$1|Y|3|Z|5|6|7|50|8|@]|9|@$D|51|E|52|1|53]]|A|$]]|$1|10|3|11|5|6|7|54|8|@]|9|@$D|55|E|56|1|57]|$D|58|E|59|1|5A]]|A|$]]|$1|12|3|13|5|6|7|5B|8|@$D|5C|E|5D|F|G]|$D|5E|E|5F|F|G]]|9|@$D|5G|E|5H|1|5I]]|A|$]]|$1|14|3|15|5|J|7|5J|8|@]|9|@]|A|$K|L]]|$1|16|3|17|5|6|7|5K|8|@$D|5L|E|5M|F|G]|$D|5N|E|5O|F|G]|$D|5P|E|5Q|F|G]|$D|5R|E|5S|F|G]|$D|5T|E|5U|F|G]|$D|5V|E|5W|F|G]|$D|5X|E|5Y|F|G]|$D|5Z|E|60|F|G]|$D|61|E|62|F|G]|$D|63|E|64|F|G]]|9|@$D|65|E|66|1|67]]|A|$]]|$1|18|3|19|5|6|7|68|8|@]|9|@]|A|$]]|$1|1A|3|1B|5|1C|7|69|8|@]|9|@$D|6A|E|6B|1|6C]]|A|$]]|$1|1D|3|19|5|6|7|6D|8|@]|9|@]|A|$]]|$1|1E|3|1F|5|6|7|6E|8|@]|9|@]|A|$]]|$1|1G|3|19|5|6|7|6F|8|@]|9|@]|A|$]]|$1|1H|3|1B|5|1C|7|6G|8|@]|9|@$D|6H|E|6I|1|6J]]|A|$]]|$1|1I|3|19|5|6|7|6K|8|@]|9|@]|A|$]]|$1|1J|3|1K|5|6|7|6L|8|@$D|6M|E|6N|F|G]]|9|@]|A|$]]|$1|1L|3|-4|5|6|7|6O|8|@]|9|@]|A|$]]|$1|1M|3|1N|5|6|7|6P|8|@]|9|@]|A|$]]|$1|1O|3|1P|5|J|7|6Q|8|@]|9|@]|A|$K|L]]|$1|1Q|3|1R|5|6|7|6R|8|@$D|6S|E|6T|F|G]|$D|6U|E|6V|F|G]]|9|@]|A|$]]|$1|1S|3|1T|5|J|7|6W|8|@]|9|@]|A|$K|L]]|$1|1U|3|1V|5|6|7|6X|8|@$D|6Y|E|6Z|F|G]]|9|@]|A|$]]|$1|1W|3|1X|5|J|7|70|8|@]|9|@]|A|$K|L]]|$1|1Y|3|1Z|5|6|7|71|8|@$D|72|E|73|F|G]]|9|@]|A|$]]|$1|20|3|21|5|J|7|74|8|@]|9|@]|A|$K|L]]|$1|22|3|23|5|6|7|75|8|@]|9|@$D|76|E|77|1|78]]|A|$]]|$1|24|3|25|5|J|7|79|8|@]|9|@]|A|$K|L]]|$1|26|3|27|5|6|7|7A|8|@]|9|@]|A|$]]|$1|28|3|29|5|J|7|7B|8|@]|9|@]|A|$K|L]]|$1|2A|3|2B|5|6|7|7C|8|@$D|7D|E|7E|F|G]]|9|@]|A|$]]|$1|2C|3|2D|5|6|7|7F|8|@]|9|@$D|7G|E|7H|1|7I]]|A|$]]|$1|2E|3|2F|5|6|7|7J|8|@]|9|@$D|7K|E|7L|1|7M]|$D|7N|E|7O|1|7P]|$D|7Q|E|7R|1|7S]|$D|7T|E|7U|1|7V]|$D|7W|E|7X|1|7Y]]|A|$]]|$1|2G|3|-4|5|6|7|7Z|8|@]|9|@]|A|$]]]|2H|$2I|$5|2J|2K|2L|A|$2M|2N]]|2O|$5|2J|2K|2L|A|$2M|2P]]|2Q|$5|2J|2K|2L|A|$2M|2R]]|2S|$5|2J|2K|2L|A|$2M|2T]]|2U|$5|2J|2K|2L|A|$2M|2V]]|2W|$5|2J|2K|2L|A|$2M|2X]]|2Y|$5|2J|2K|2L|A|$2M|2Z]]|30|$5|2J|2K|2L|A|$2M|31]]|32|$5|2J|2K|2L|A|$2M|33]]|34|$5|2J|2K|2L|A|$2M|35]]|36|$5|2J|2K|2L|A|$2M|37]]|38|$5|2J|2K|2L|A|$2M|39]]|3A|$5|3B|2K|3C|A|$3D|3E|3F|-4]]|3G|$5|3B|2K|3C|A|$3D|3H|3F|-4]]|3I|$5|2J|2K|2L|A|$2M|3J]]|3K|$5|2J|2K|2L|A|$2M|3L]]|3M|$5|2J|2K|2L|A|$2M|3N]]|3O|$5|2J|2K|2L|A|$2M|3P]]|3Q|$5|2J|2K|2L|A|$2M|3R]]|3S|$5|2J|2K|2L|A|$2M|3T]]|3U|$5|2J|2K|2L|A|$2M|3V]]]]

I assume entropy was mentioned in the context of building <a href="https://en.wikipedia.org/wiki/Decision_tree_learning" rel="noreferrer">decision trees</a>.

To illustrate, imagine the task of <a href="https://en.wikipedia.org/wiki/Supervised_learning" rel="noreferrer">learning</a> to <a href="https://en.wikipedia.org/wiki/Statistical_classification" rel="noreferrer">classify</a> first-names into male/female groups. That is given a list of names each labeled with either <code>m</code> or <code>f</code>, we want to learn a <a href="https://en.wikipedia.org/wiki/Predictive_modelling" rel="noreferrer">model</a> that fits the data and can be used to predict the gender of a new unseen first-name.

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

First step is <a href="https://en.wikipedia.org/wiki/Feature_selection" rel="noreferrer">deciding</a> what <a href="https://en.wikipedia.org/wiki/Feature_%28machine_learning%29" rel="noreferrer">features</a> of the data are relevant to the target class we want to predict. Some example features include: first/last letter, length, number of vowels, does it end with a vowel, etc.. So after feature extraction, our data looks like:

<pre><code># 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
</code></pre>

The goal is to build a <a href="https://en.wikipedia.org/wiki/Decision_tree" rel="noreferrer">decision tree</a>. An example of a <a href="https://en.wikipedia.org/wiki/Tree_%28data_structure%29" rel="noreferrer">tree</a> would be:

<pre><code>length&lt;7
| num-vowels&lt;3: male
| num-vowels&gt;=3
| | ends-vowel=1: female
| | ends-vowel=0: male
length&gt;=7
| length=5: male
</code></pre>

basically each node represent a test performed on a single attribute, and we go left or right depending on the result of the test. We keep traversing the tree until we reach a leaf node which contains the class prediction (<code>m</code> or <code>f</code>)

So if we run the name Amro down this tree, we start by testing "is the length&lt;7?" and the answer is yes, so we go down that branch. Following the branch, the next test "is the number of vowels&lt;3?" again evaluates to true. This leads to a leaf node labeled <code>m</code>, and thus the prediction is male (which I happen to be, so the tree predicted the outcome <a href="https://en.wikipedia.org/wiki/Evaluation_of_binary_classifiers" rel="noreferrer">correctly</a>).

The decision tree is <a href="https://en.wikipedia.org/wiki/ID3_algorithm" rel="noreferrer">built in a top-down fashion</a>, but the question is how do you choose which attribute to split at each node? The answer is find the feature that best splits the target class into the purest possible children nodes (ie: nodes that don't contain a mix of both male and female, rather pure nodes with only one class).

This measure of purity is called the <a href="https://en.wikipedia.org/wiki/Information_theory" rel="noreferrer">information</a>. It represents the <a href="https://en.wikipedia.org/wiki/Expected_value" rel="noreferrer">expected</a> amount of <a href="https://en.wikipedia.org/wiki/Self-information" rel="noreferrer">information</a> that would be needed to specify whether a new instance (first-name) should be classified male or female, given the example that reached the node. We calculate it
based on the number of male and female classes at the node.

<a href="https://en.wikipedia.org/wiki/Information_entropy" rel="noreferrer">Entropy</a> on the other hand is a measure of impurity (the opposite). It is defined for a <a href="https://en.wikipedia.org/wiki/Binary_classification" rel="noreferrer">binary class</a> with values <code>a</code>/<code>b</code> as:

<pre><code>Entropy = - p(a)*log(p(a)) - p(b)*log(p(b))
</code></pre>

This <a href="https://en.wikipedia.org/wiki/Binary_entropy_function" rel="noreferrer">binary entropy function</a> is depicted in the figure below (random variable can take one of two values). It reaches its maximum when the probability is <code>p=1/2</code>, meaning that <code>p(X=a)=0.5</code> or similarly<code>p(X=b)=0.5</code> having a 50%/50% chance of being either <code>a</code> or <code>b</code> (uncertainty is at a maximum). The entropy function is at zero minimum when probability is <code>p=1</code> or <code>p=0</code> with complete certainty (<code>p(X=a)=1</code> or <code>p(X=a)=0</code> respectively, latter implies <code>p(X=b)=1</code>).

<img src="https://i.stack.imgur.com/OUgcx.png" alt="https://en.wikipedia.org/wiki/File:Binary_entropy_plot.svg">

Of course the definition of entropy can be generalized for a discrete random variable X with N outcomes (not just two):

<img src="https://i.stack.imgur.com/vIFD7.png" alt="entropy">

(the <code>log</code> in the formula is usually taken as the <a href="https://en.wikipedia.org/wiki/Binary_logarithm" rel="noreferrer">logarithm to the base 2</a>)

<hr>

Back to our task of name classification, lets look at an example. Imagine at some point during the process of constructing the tree, we were considering the following split:

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

As you can see, before the split we had 9 males and 5 females, i.e. <code>P(m)=9/14</code> and <code>P(f)=5/14</code>. According to the definition of entropy:

<pre><code>Entropy_before = - (5/14)*log2(5/14) - (9/14)*log2(9/14) = 0.9403
</code></pre>

Next we compare it with the entropy computed after considering the split by looking at two child branches. In the left branch of <code>ends-vowel=1</code>, we have:

<pre><code>Entropy_left = - (3/7)*log2(3/7) - (4/7)*log2(4/7) = 0.9852
</code></pre>

and the right branch of <code>ends-vowel=0</code>, we have:

<pre><code>Entropy_right = - (6/7)*log2(6/7) - (1/7)*log2(1/7) = 0.5917
</code></pre>

We combine the left/right entropies using the number of instances down each branch as <a href="https://en.wikipedia.org/wiki/Weighted_arithmetic_mean" rel="noreferrer">weight factor</a> (7 instances went left, and 7 instances went right), and get the final entropy after the split:

<pre><code>Entropy_after = 7/14*Entropy_left + 7/14*Entropy_right = 0.7885
</code></pre>

Now by comparing the entropy before and after the split, we obtain a measure of <a href="https://en.wikipedia.org/wiki/Information_gain_in_decision_trees" rel="noreferrer">information gain</a>, or how much information we gained by doing the split using that particular feature:

<pre><code>Information_Gain = Entropy_before - Entropy_after = 0.1518
</code></pre>

You can interpret the above calculation as following: by doing the split with the <code>end-vowels</code> feature, we were able to reduce uncertainty in the sub-tree prediction outcome by a small amount of 0.1518 (measured in <a href="https://en.wikipedia.org/wiki/Bit" rel="noreferrer">bits</a> as <a href="https://en.wikipedia.org/wiki/Units_of_information" rel="noreferrer">units of information</a>).

At each node of the tree, this calculation is performed for every feature, and the feature with the largest information gain is chosen for the split in a <a href="https://en.wikipedia.org/wiki/Greedy_algorithm" rel="noreferrer">greedy</a> manner (thus favoring features that produce pure splits with low uncertainty/entropy). This process is applied recursively from the root-node down, and stops when a leaf node contains instances all having the same class (no need to split it further).

Note that I skipped over some <a href="https://en.wikipedia.org/wiki/C4.5_algorithm" rel="noreferrer">details</a> which are beyond the scope of this post, including how to handle <a href="https://en.wikipedia.org/wiki/Discretization_of_continuous_features" rel="noreferrer">numeric features</a>, <a href="https://en.wikipedia.org/wiki/Missing_data" rel="noreferrer">missing values</a>, <a href="https://en.wikipedia.org/wiki/Overfitting" rel="noreferrer">overfitting</a> and <a href="https://en.wikipedia.org/wiki/Pruning_%28decision_trees%29" rel="noreferrer">pruning</a> trees, etc..

blocks|key|3075458|text|当我实现一个算法来计算图像的熵时，我找到了这些链接，请参阅here和here。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|3075459|这是我使用的伪代码，你需要修改它来处理文本而不是图像，但是原理应该是一样的。|3075460|//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%2B1,j)+-+array(i,j)
+++++++if+diff+lt+(array_size%2B1)/2+and+diff+gt+-(array_size%2B1)/2+then+begin
++++++++++++prob_array(diff%2B(array_size-1)/2)+=+prob_array(diff%2B(array_size-1)/2)+%2B+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)|code-block|syntax|javascript|3075461|我从什么地方拿到这段代码，但我找不出其中的联系。|3075462|entityMap|0|LINK|mutability|MUTABLE|url|http://www.icaen.uiowa.edu/~dip/LECTURE/DataCompression.html#properties|1|http://en.wikipedia.org/wiki/Entropy_%2528information_theory%2529^0|T|4|0|Y|4|1|0|0|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@]|9|@$A|X|B|Y|1|Z]|$A|10|B|11|1|12]]|C|$]]|$1|D|3|E|5|6|7|13|8|@]|9|@]|C|$]]|$1|F|3|G|5|H|7|14|8|@]|9|@]|C|$I|J]]|$1|K|3|L|5|6|7|15|8|@]|9|@]|C|$]]|$1|M|3|-4|5|6|7|16|8|@]|9|@]|C|$]]]|N|$O|$5|P|Q|R|C|$S|T]]|U|$5|P|Q|R|C|$S|V]]]]

When I was implementing an algorithm to calculate the entropy of an image I found these links, see <a href="http://www.icaen.uiowa.edu/~dip/LECTURE/DataCompression.html#properties" rel="noreferrer">here</a> and <a href="http://en.wikipedia.org/wiki/Entropy_%28information_theory%29" rel="noreferrer">here</a>.

This is the pseudo-code I used, you'll need to adapt it to work with text rather than images but the principles should be the same.

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

I got this code from somewhere, but I can't dig out the link.

blocks|key|324105|text|我真的推荐你阅读有关信息论、贝叶斯方法和MaxEnt的知识。从David+Mackay写的这本书(在线免费下载)开始：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|324106|http://www.inference.phy.cam.ac.uk/mackay/itila/|offset|length|324107|这些推理方法真的比文本挖掘要通用得多，如果不学习本书或其他关于机器学习和MaxEnt贝叶斯方法的介绍性书籍中包含的一些一般基础知识，我真的无法设计如何将其应用于自然语言处理。|324108|熵和概率论与信息处理和存储之间的联系真的很深。为了体验一下，香农的一个定理表明，通过嘈杂的通信通道可以无差错地传递的最大信息量等于噪声过程的熵。还有一个定理，将压缩一段数据以占用计算机中最小内存的程度与生成数据的过程的熵联系起来。|324109|我不认为你真的有必要去学习所有这些关于沟通理论的定理，但如果不学习关于熵的基础知识，它是如何计算的，它与信息和推理的关系，等等，你就不可能学习这些定理。|324110|entityMap|0|LINK|mutability|MUTABLE|url^0|0|0|1C|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|T|8|@]|9|@$D|U|E|V|1|W]]|A|$]]|$1|F|3|G|5|6|7|X|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|Y|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|Z|8|@]|9|@]|A|$]]|$1|L|3|-4|5|6|7|10|8|@]|9|@]|A|$]]]|M|$N|$5|O|P|Q|A|$R|C]]]]

I really recommend you read about Information Theory, bayesian methods and MaxEnt. The place to start is this (freely available online) book by David Mackay:

<a href="http://www.inference.phy.cam.ac.uk/mackay/itila/" rel="noreferrer">http://www.inference.phy.cam.ac.uk/mackay/itila/</a>

Those inference methods are really far more general than just text mining and I can't really devise how one would learn how to apply this to NLP without learning some of the general basics contained in this book or other introductory books on Machine Learning and MaxEnt bayesian methods.

The connection between entropy and probability theory to information processing and storing is really, really deep. To give a taste of it, there's a theorem due to Shannon that states that the maximum amount of information you can pass without error through a noisy communication channel is equal to the entropy of the noise process. There's also a theorem that connects how much you can compress a piece of data to occupy the minimum possible memory in your computer to the entropy of the process that generated the data.

I don't think it's really necessary that you go learning about all those theorems on communication theory, but it's not possible to learn this without learning the basics about what is entropy, how it's calculated, what is it's relationship with information and inference, etc...

blocks|key|326373|text|首先，最好理解the+measure+of+information。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|326374|我们如何measure这些信息？|326375|当一些不太可能发生的事情发生时，我们说这是个大新闻。此外，当我们说一些可预测的东西时，它并不是真的有趣。因此，要量化此interesting-ness，函数应满足|326376|326377|如果事件发生的概率为1(可预测)，则函数给出0|unordered-list-item|326378|如果事件发生的概率接近于0，则函数应给出较高的数值|326379|如果事件发生的概率为0.5，则函数应给出one+bit+of+one+bit|326380|326381|满足约束条件的一个自然度量是|326382|I(X)+=+-log_2(p)|code-block|syntax|javascript|326383|其中p是事件X的概率。这个单元是bit的，和计算机使用的是相同的位。0或1。|326384|示例1|326385|公平的掷硬币：|326386|我们能从一次抛硬币中得到多少信息？|326387|答案：-log(p)+=+-log(1/2)+=+1+(bit)|326388|示例2|326389|如果明天有一颗流星撞上地球，p=2%5E{-22}，那么我们就能得到22比特的信息。|326390|如果太阳明天升起，p+~+1，那么它就是0比特的信息。|326391|熵|326392|因此，如果我们对事件Y的interesting-ness进行期望，那么它就是熵。即熵是事件的兴趣度的期望值。|326393|H(Y)+=+E[+I(Y)]|326394|更正式地说，熵是事件的预期位数。|326395|示例|326396|Y=1:事件X发生的概率为p|326397|Y=0:事件X不会以概率1-p出现|326398|H(Y)+=+E[I(Y)]+=+p+I(Y==1)+%2B+(1-p)+I(Y==0)+
+++++=+-+p+log+p+-+(1-p)+log+(1-p)|326399|以2为底数的所有日志。|326400|entityMap^0|7|Q|0|4|7|0|1N|G|0|0|0|0|K|7|V|7|0|0|0|0|6|1|G|3|0|0|0|0|3|T|0|0|E|9|0|9|5|0|0|A|1|C|G|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|1Z|8|@$9|20|A|21|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|22|8|@$9|23|A|24|B|C]]|D|@]|E|$]]|$1|H|3|I|5|6|7|25|8|@$9|26|A|27|B|C]]|D|@]|E|$]]|$1|J|3|-4|5|6|7|28|8|@]|D|@]|E|$]]|$1|K|3|L|5|M|7|29|8|@]|D|@]|E|$]]|$1|N|3|O|5|M|7|2A|8|@]|D|@]|E|$]]|$1|P|3|Q|5|M|7|2B|8|@$9|2C|A|2D|B|C]|$9|2E|A|2F|B|C]]|D|@]|E|$]]|$1|R|3|-4|5|6|7|2G|8|@]|D|@]|E|$]]|$1|S|3|T|5|6|7|2H|8|@]|D|@]|E|$]]|$1|U|3|V|5|W|7|2I|8|@]|D|@]|E|$X|Y]]|$1|Z|3|10|5|6|7|2J|8|@$9|2K|A|2L|B|C]|$9|2M|A|2N|B|C]]|D|@]|E|$]]|$1|11|3|12|5|6|7|2O|8|@]|D|@]|E|$]]|$1|13|3|14|5|6|7|2P|8|@]|D|@]|E|$]]|$1|15|3|16|5|6|7|2Q|8|@]|D|@]|E|$]]|$1|17|3|18|5|6|7|2R|8|@$9|2S|A|2T|B|C]]|D|@]|E|$]]|$1|19|3|1A|5|6|7|2U|8|@]|D|@]|E|$]]|$1|1B|3|1C|5|6|7|2V|8|@$9|2W|A|2X|B|C]]|D|@]|E|$]]|$1|1D|3|1E|5|6|7|2Y|8|@$9|2Z|A|30|B|C]]|D|@]|E|$]]|$1|1F|3|1G|5|6|7|31|8|@]|D|@]|E|$]]|$1|1H|3|1I|5|6|7|32|8|@$9|33|A|34|B|C]|$9|35|A|36|B|C]]|D|@]|E|$]]|$1|1J|3|1K|5|W|7|37|8|@]|D|@]|E|$X|Y]]|$1|1L|3|1M|5|6|7|38|8|@]|D|@]|E|$]]|$1|1N|3|1O|5|6|7|39|8|@]|D|@]|E|$]]|$1|1P|3|1Q|5|6|7|3A|8|@]|D|@]|E|$]]|$1|1R|3|1S|5|6|7|3B|8|@]|D|@]|E|$]]|$1|1T|3|1U|5|W|7|3C|8|@]|D|@]|E|$X|Y]]|$1|1V|3|1W|5|6|7|3D|8|@]|D|@]|E|$]]|$1|1X|3|-4|5|6|7|3E|8|@]|D|@]|E|$]]]|1Y|$]]

To begin with, it would be best to understand <code>the measure of information</code>. 

<h1>How do we <code>measure</code> the information?</h1>

When something unlikely happens, we say it's a big news. Also, when we say something predictable, it's not really interesting. So to quantify this <code>interesting-ness</code>, the function should satisfy

<ul>
<li>if the probability of the event is 1 (predictable), then the function gives 0</li>
<li>if the probability of the event is close to 0, then the function should give high number</li>
<li>if probability 0.5 events happens it give <code>one bit</code> of information.</li>
</ul>

One natural measure that satisfy the constraints is

<pre><code>I(X) = -log_2(p)
</code></pre>

where p is the probability of the event <code>X</code>. And the unit is in <code>bit</code>, the same bit computer uses. 0 or 1.

<h2>Example 1</h2>

Fair coin flip : 

How much information can we get from one coin flip?

Answer : <code>-log(p) = -log(1/2) = 1 (bit)</code>

<h2>Example 2</h2>

If a meteor strikes the Earth tomorrow, <code>p=2^{-22}</code> then we can get 22 bits of information.

If the Sun rises tomorrow, <code>p ~ 1</code> then it is 0 bit of information.

<h1>Entropy</h1>

So if we take expectation on the <code>interesting-ness</code> of an event <code>Y</code>, then it is the entropy.
i.e. entropy is an expected value of the interesting-ness of an event.

<pre><code>H(Y) = E[ I(Y)]
</code></pre>

More formally, the entropy is the expected number of bits of an event.

<h2>Example</h2>

Y = 1 : an event X occurs with probability p

Y = 0 : an event X does not occur with probability 1-p

<pre><code>H(Y) = E[I(Y)] = p I(Y==1) + (1-p) I(Y==0) 
 = - p log p - (1-p) log (1-p)
</code></pre>

Log base 2 for all log.

blocks|key|326418|text|当您正在阅读一本关于NLTK的书时，了解到MaxEnt分类器模块http://www.nltk.org/api/nltk.classify.html#module-nltk.classify.maxent会很有趣|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|326419|对于文本挖掘分类，步骤可以是:预处理(标记化，流，使用信息增益的特征选择...)，转换为数字(频率或TF-IDF)+(我认为这是理解将文本作为只接受数字的算法的输入时的关键步骤)，然后使用MaxEnt进行分类，当然这只是一个例子。|326420|entityMap|0|LINK|mutability|MUTABLE|url|http://www.nltk.org/api/nltk.classify.html#module-nltk.classify.maxent^0|W|1Y|0|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]]|C|$]]|$1|D|3|E|5|6|7|R|8|@]|9|@]|C|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|C|$]]]|G|$H|$5|I|J|K|C|$L|M]]]]

As you are reading a book about NLTK it would be interesting you read about MaxEnt Classifier Module <a href="http://www.nltk.org/api/nltk.classify.html#module-nltk.classify.maxent" rel="nofollow">http://www.nltk.org/api/nltk.classify.html#module-nltk.classify.maxent</a>

For text mining classification the steps could be: pre-processing (tokenization, steaming, feature selection with Information Gain ...), transformation to numeric (frequency or TF-IDF) (I think that this is the key step to understand when using text as input to a algorithm that only accept numeric) and then classify with MaxEnt, sure this is just an example.

blocks|key|324145|text|非正式的|type|unstyled|depth|inlineStyleRanges|entityRanges|data|324146|下一词熵预测(++entropy++)是指信息或知识的可用性，缺乏信息将导致对未来预测的困难，即高熵(文本挖掘中的下一词预测)，而信息/知识的可用性将帮助我们对未来进行更现实的预测(低熵)。|offset|length|style|BOLD|324147|任何类型的相关信息都会减少熵，并帮助我们预测更现实的未来，即信息可以是“肉”字出现在句子中，也可以是“肉”字不存在。这称为信息增益|324148|324149|正式|324150|熵缺乏可预测性的阶数|324151|entityMap^0|0|8|9|0|1P|4|0|0|0|2|0|0|1|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|R|8|@$D|S|E|T|F|G]]|9|@]|A|$]]|$1|H|3|I|5|6|7|U|8|@$D|V|E|W|F|G]]|9|@]|A|$]]|$1|J|3|-4|5|6|7|X|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|Y|8|@$D|Z|E|10|F|G]]|9|@]|A|$]]|$1|M|3|N|5|6|7|11|8|@$D|12|E|13|F|G]]|9|@]|A|$]]|$1|O|3|-4|5|6|7|14|8|@]|9|@]|A|$]]]|P|$]]

<h2>Informally</h2>

entropy is availability of information or knowledge, Lack of information will leads to difficulties in prediction of future which is high entropy (next word prediction in text mining) and availability of information/knowledge will help us more realistic prediction of future (low entropy).

Relevant information of any type will reduce entropy and helps us predict more realistic future, that information can be word "meat" is present in sentence or word "meat" is not present. This is called Information Gain

<hr>

<h2>Formally</h2>

entropy is lack of order of predicability

I am reading this book (<a href="http://www.nltk.org/book" rel="noreferrer">NLTK</a>) and it is confusing. Entropy is <a href="http://www.nltk.org/book/ch06.html#entropy-and-information-gain" rel="noreferrer">defined as</a>:

<blockquote>
 Entropy is the sum of the probability of each label
 times the log probability of that same label
</blockquote>

How can I apply entropy and maximum entropy in terms of text mining? Can someone give me a easy, simple example (visual)?

What is "entropy and information gain"?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋 

腾讯云代码助手

CODING DevOps

Cloud Studio

SDK中心

API中心

命令行工具

我正在读这本书()，它令人困惑。Entropy is 熵是每个标注的概率乘以同一标注的对数概率之和如何将熵和最大熵应用于文本挖掘？谁能给我一个简单的例子(视觉)？

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

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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