信息熵在决策表中的应用

深碍√TFBOYSˉ_ 2021-09-29 12:36 247阅读 0赞

--------------------

### 目录 ###

*  1. 信息熵的一般形式
 *  2. 信息熵在决策表中的形式
 *   *  2.1 决策表中的信息熵公式
     *  2.2 代码实现

--------------------

# 1. 信息熵的一般形式 #

信息熵的定义形式为：  
 H ( X ) = − ∑ x ∈ X p ( x ) log ⁡ p ( x ) (1) H(X) = - \\sum\_\{x \\in X\} p(x) \\log p(x) \\tag\{1\} H(X)=−x∈X∑p(x)logp(x)(1)

有时也写作：  
 H ( X ) = − ∑ i = 1 n p ( x i ) log ⁡ p ( x i ) (2) H(X) = - \\sum\_\{i=1\}^\{n\} p(x\_i) \\log p(x\_i) \\tag\{2\} H(X)=−i=1∑np(xi)logp(xi)(2)

[更详细的信息熵请参见文章：信息熵][Link 1]

--------------------

# 2. 信息熵在决策表中的形式 #

将信息熵应用到一张决策表中，可得到如下的公式：

## 2.1 决策表中的信息熵公式 ##

H ( X ) = − ∑ i = 1 n p ( x i ) log ⁡ p ( x i ) = − ∑ i = 1 k C i n ⋅ log ⁡ C i n = − ∑ i = 1 k C i ⋅ log ⁡ C i ∑ i = 1 k C i + log ⁡ ∑ i = 1 k C i (3) \\begin\{aligned\} H(X) &= - \\sum\_\{i=1\}^\{n\} p(x\_i) \\log p(x\_i) \\\\ &= - \\sum\_\{i=1\}^k \\frac\{C\_i\}\{n\} \\cdot \\log \\frac\{C\_i\}\{n\} \\\\ &= \\frac\{- \\sum\_\{i=1\}^\{k\} C\_i \\cdot \\log C\_i\}\{\\sum\_\{i=1\}^\{k\} C\_i\} + \\log \\sum\_\{i=1\}^\{k\} C\_i \\end\{aligned\} \\tag\{3\} H(X)=−i=1∑np(xi)logp(xi)=−i=1∑knCi⋅lognCi=∑i=1kCi−∑i=1kCi⋅logCi\+logi=1∑kCi(3)  
其中， k k k表示某个属性的不同属性值个数， C i C\_i Ci表示决策表按照这个属性分类后，第 i i i个属性值拥有的对象数， n n n为决策表所有的对象数，即 n = C 1 + C 2 + ⋯ + C k n = C\_1 + C\_2 + \\dots + C\_k n=C1\+C2\+⋯\+Ck。

**推导过程：**  
 H ( X ) = − ∑ i = 1 n p ( x i ) log ⁡ p ( x i ) = − ∑ i = 1 k C i n log ⁡ C i n = − 1 n ( ∑ i = 1 k C i ⋅ log ⁡ C i n ) = − 1 n ∑ i = 1 k C i ⋅ ( log ⁡ C i − log ⁡ n ) = − 1 n ∑ i = 1 k C i ⋅ log ⁡ C i + 1 n ∑ i = 1 k C i ⋅ log ⁡ n = − 1 n ∑ i = 1 k C i ⋅ log ⁡ C i + ( 1 n log ⁡ n ) ∑ i = 1 k C i = − 1 n ∑ i = 1 k C i ⋅ log ⁡ C i + ( 1 n log ⁡ n ) ⋅ n = − 1 n ∑ i = 1 k C i ⋅ log ⁡ C i + log ⁡ n = − ∑ i = 1 k C i ⋅ log ⁡ C i ∑ i = 1 k C i + log ⁡ ∑ i = 1 k C i (4) \\begin\{aligned\} H(X) &= - \\sum\_\{i=1\}^\{n\} p(x\_i) \\log p(x\_i) \\\\ & = - \\sum\_\{i=1\}^\{k\} \\frac\{C\_i\}\{n\} \\log \\frac\{C\_i\}\{n\} \\\\ &= - \\frac\{1\}\{n\} (\\sum\_\{i=1\}^\{k\} C\_i \\cdot \\log \\frac\{C\_i\}\{n\} ) \\\\ &= - \\frac\{1\}\{n\} \\sum\_\{i=1\}^\{k\} C\_i \\cdot (\\log C\_i - \\log n) \\\\ &= - \\frac\{1\}\{n\} \\sum\_\{i=1\}^\{k\} C\_i \\cdot \\log C\_i + \\frac\{1\}\{n\} \\sum\_\{i=1\}^\{k\} C\_i \\cdot \\log n \\\\ &= - \\frac\{1\}\{n\} \\sum\_\{i=1\}^\{k\} C\_i \\cdot \\log C\_i + (\\frac\{1\}\{n\} \\log n) \\sum\_\{i=1\}^\{k\} C\_i \\\\ &= - \\frac\{1\}\{n\} \\sum\_\{i=1\}^\{k\} C\_i \\cdot \\log C\_i + (\\frac\{1\}\{n\} \\log n) \\cdot n \\\\ &= - \\frac\{1\}\{n\} \\sum\_\{i=1\}^\{k\} C\_i \\cdot \\log C\_i + \\log n \\\\ &= \\frac\{- \\sum\_\{i=1\}^\{k\} C\_i \\cdot \\log C\_i\}\{\\sum\_\{i=1\}^\{k\} C\_i\} + \\log \\sum\_\{i=1\}^\{k\} C\_i \\end\{aligned\} \\tag\{4\} H(X)=−i=1∑np(xi)logp(xi)=−i=1∑knCilognCi=−n1(i=1∑kCi⋅lognCi)=−n1i=1∑kCi⋅(logCi−logn)=−n1i=1∑kCi⋅logCi\+n1i=1∑kCi⋅logn=−n1i=1∑kCi⋅logCi\+(n1logn)i=1∑kCi=−n1i=1∑kCi⋅logCi\+(n1logn)⋅n=−n1i=1∑kCi⋅logCi\+logn=∑i=1kCi−∑i=1kCi⋅logCi\+logi=1∑kCi(4)  
得解。

## 2.2 代码实现 ##

package com.louis.www;
    
    public class Entropy
    { 
        private static double log2(double logarithm)
        { 
            return Math.log(logarithm) / Math.log(2);
        }
        
        public static double entropy(int[] frequencyData)
        { 
            double entropyResult = 0;
            int totalInstanceNumber = 0;
            for (int i = 0; i < frequencyData.length; ++i)
            { 
                totalInstanceNumber += frequencyData[i];
                if (frequencyData[i] > 0)
                { 
                    entropyResult -= frequencyData[i] * Entropy.log2(frequencyData[i]);
                }
            }
            entropyResult /= totalInstanceNumber;
            entropyResult += Entropy.log2(totalInstanceNumber);
            return entropyResult;
        }
    }

上面的这段代码是对某个属性的信息熵进行了计算。  
**输入参数为某个属性的所有属性值频度数组；**  
**输出参数为这个属性的信息熵。**

步骤：

*  代码5–8行构造了一个底数为2的对数方法；
 *  代码10–25行计算了某个属性的信息熵；
 *  代码14–21行是一个遍历的过程；
 *  代码16行计算了  ∑ i = 1 k C i \\sum\_\{i=1\}^\{k\} C\_i ∑i=1kCi 的结果；
 *  代码17-20行计算了  − ∑ i = 1 k C i ⋅ log ⁡ C i - \\sum\_\{i=1\}^\{k\} C\_i \\cdot \\log C\_i −∑i=1kCi⋅logCi 的结果；
 *  代码22行计算了  − ∑ i = 1 k C i ⋅ log ⁡ C i ∑ i = 1 k C i \\frac\{-\\sum\_\{i=1\}^\{k\} C\_i \\cdot \\log C\_i\}\{\\sum\_\{i=1\}^\{k\} C\_i\} ∑i=1kCi−∑i=1kCi⋅logCi 的结果；
 *  代码23行计算 − ∑ i = 1 k C i ⋅ log ⁡ C i ∑ i = 1 k C i + log ⁡ ∑ i = 1 k C i \\frac\{-\\sum\_\{i=1\}^\{k\} C\_i \\cdot \\log C\_i\}\{\\sum\_\{i=1\}^\{k\} C\_i\} + \\log \\sum\_\{i=1\}^\{k\} C\_i ∑i=1kCi−∑i=1kCi⋅logCi\+log∑i=1kCi 的结果，也即是  H ( X ) H(X) H(X)。

测试：  
现在假设有某个属性 a 1 a\_1 a1，根据其属性值 \{  V 1 a 1 , V 2 a 1 , V 3 a 1 V\_1^\{a\_1\}, V\_2^\{a\_1\}, V\_3^\{a\_1\} V1a1,V2a1,V3a1\} 将所有的对象（共计10个）分为3类，个数分别是**3**，**5**，**2**。根据公式  3 3 3 可得：  
 H ( X ) = − ∑ i = 1 3 C i n log ⁡ C i n = − ( 3 10 ∗ log ⁡ 2 3 10 + 5 10 log ⁡ 2 5 10 + 2 10 ∗ log ⁡ 2 2 10 ) ≈ 1.4855 \\begin\{aligned\} H(X) &= - \\sum\_\{i=1\}^\{3\} \\frac\{C\_i\}\{n\} \\log \\frac\{C\_i\}\{n\} \\\\ &= - ( \\frac\{3\}\{10\} \\ast \\log\_2 \\frac\{3\}\{10\} + \\frac\{5\}\{10\} \\log\_2 \\frac\{5\}\{10\} + \\frac\{2\}\{10\} \\ast \\log\_2 \\frac\{2\}\{10\} ) \\\\ &\\approx 1.4855 \\end\{aligned\} H(X)=−i=1∑3nCilognCi=−(103∗log2103\+105log2105\+102∗log2102)≈1.4855

利用代码来测试，

public static void main(String[] args)
    { 
        int[] frequencyOfAttribute = new int[]{ 3, 5, 2};
        System.out.println(Entropy.entropy(frequencyOfAttribute));
    }

结果如图所示，和预期一致。  
![在这里插入图片描述][20190712222803374.jpg]  
   
对于整个决策表来讲，

public static double entropyOfDataset(int[][] frequencyDataOfDataset, int instanceNumber)
     { 
         double entropyResult = 0;
         int numberOfInstanceUnderAttribute;
         for (int i = 0; i < frequencyDataOfDataset.length; ++i)
         { 
             numberOfInstanceUnderAttribute = 0;
             if (frequencyDataOfDataset[i] == null)
             { 
                 continue;
             }
             for (int j = 0; j < frequencyDataOfDataset[i].length; ++j)
             { 
                 numberOfInstanceUnderAttribute += frequencyDataOfDataset[i][j];
             }
    
             if (numberOfInstanceUnderAttribute == 0)
             { 
                 continue;
             }
    
             entropyResult += numberOfInstanceUnderAttribute * Entropy.entropy(frequencyDataOfDataset[i]);
         }
    
         entropyResult /= instanceNumber;
         return entropyResult;
     }

上面的这段代码是对某个属性的信息熵进行了计算。

> **输入参数为二维决策表的所有属性的属性值频度数组；**  
> **输出参数为这个二维决策表的信息熵。**

步骤：

>  *  代码5-23行通过逐行计算一维数组的信息熵，来得到整个二维决策表的信息熵；
>  *  代码12-14行统计每个一维数组的对象数目；
>  *  代码22行对每个一维数组进行按权值的信息熵计算；
>  *  代码25行得到二维决策表的最终信息熵。

利用代码来测试：

public static void main(String[] args)
    { 
        int[][] testMatrixForEntropy = { 
                { 3, 5, 2},
                { 3, 5, 2},
                { 3, 5, 2}
        };
        System.out.println(Entropy.entropyOfDataset(testMatrixForEntropy,10));
    }

结果如下图所示，与预期保持一致。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70]

--------------------

[Link 1]: https://blog.csdn.net/PursueLuo/article/details/95627975
[20190712222803374.jpg]: /images/20210923/e15ff3729bd3483bbc0343553b94c2d8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70]: /images/20210923/b001b90a0bd2471c9b0cbfa9fd87a4c9.png