基于信息熵的离散化算法的研究与实现

The Study and Implementation of Discretization Algorithm Based on Information Entropy

摘要: 离散化算法将连续属性的取值范围划分为很多个小的区间,每个区间都对应着自己的离散化符号，合理的离散化能够更准确的表达信息。本课题研究并实现了一种基于信息熵的离散化算法，通过赋予断点信息熵来度量断点的重要性从而对集合S进行划分。首先计算连续的属性的候选断点属性集，其次从候选断点集合中选取一个使信息熵最小的断点加入到断点集合中，该断点把集合S分成了两个部分，之后对于每一个子集合确定断点直到对于集合S的划分足够表达不同信息，满足最小区分长度准则完成。本文最后用实验验证了此算法的正确性和有效性，并对多组数据进行了测试和比较。

Abstract: The values range of continuous attributes is divided by discretization algorithm into several parts, each of which corresponds to its own discrete symbol. The reasonable discretization determines the accuracy of information expressing. This article studies and implements a discretization algorithm based on information entropy. The set S is divided by measuring the importance of the breakpoint by giving the breakpoint information entropy. First, a set of candidate breakpoint attributes of continuous attribute are calculated. Secondly, a breakpoint from the set of candidate breakpoints is selected to add the breakpoint with the smallest value of information entropy to the set of breakpoints, which breaks up the set S into two parts. The third determines the breakpoint for each set of instances until the partitioning for set S satisfies the minimum discrimination length criterion. In the last part of the article, the correctness and validity of the algorithm are verified by experiments, and test as well as comparison of different groups of data is given.

1. 引言

离散化是数据挖掘中非常重要的一步，它属于数据预处理阶段，是对连续属性数据进行的分析处理。具体离散化算法会把连续属性的数据取值范围划分为很多个小区间，划分的原则分为有监督和无监督，有监督的分为等宽度，等频率 [1] 等，而无监督就是指没有指定要求的情况下的根据具体算法具体分析。而基于信息熵的离散化算法即是其中一种无监督的离散化方法，它通过判断断点信息熵的大小来划分实例集，达到离散化的目的。

2. 信息熵基本概念

信息是个很抽象的概念，起初人们对信息的多少无法说清楚，直到香农在1948年信息论中提出的信息熵 [2] 这一概念才使的量化度量信息的问题得以解决。在信息论中，信息熵被视为接收到的每条信息种包含的信息量的平均值，也被称为信源熵、平均自信息量。

用X表示随机变量，随机变量的取值为( $x_1,x_2,\cdots ,x_n$ )， $p\left(x_i\right)$ 表示事件x_i发生的概率，且有 $\sum p\left(x_i\right)=1$。定义事件x_i的信息量是它发生概率对数的负数，记为I(x_i)，即： $I\left(x_i\right)=-\log \left(p\left(x_i\right)\right)$。

而H(X)为随机变量X的平均信息量，即X的信息熵。

$H\left(X\right)=E\left[-\log P\left(x_i\right)\right]=-{\displaystyle \underset{i=1}{\overset{N}{\sum }}P\left(x_i\right)\log P(xi)}$

其中 $P\left(x_i\right)$ 表示事件x_i发生的先验概率，且 $\sum P\left(x_i\right)=1$。

另外，公式中的log的底和信息熵的单位有关。被广泛应用的是以2为底，它的单位是bit。当使用以e为底，单位为Nat。

3. 最小信息熵的离散化方法

在智能化信息处理中，经常遇到的技术难点主要是离散化问题和数据的不完整性问题。在应用粗糙集理论来处理信息决策表时，需要满足的是决策表中的值应该是离散的。不管是连续属性还是离散化的数据，都是需要进行离散化，连续属性在处理前必须进行离散化处理；对于离散化的数据，可以使用离散化方法将本来也就是离散的数据合并或者抽象得到更好的离散值。离散化算法应该满足：

1) 离散化后的信息系统的空间维数应该尽量少，即离散化后信息系统剩余的属性个数尽量少。

2) 离散化后的信息丢失尽量少。

1993年，Fayyad和Irani于提出最小信息熵离散化方法 [3]。离散的门限边界值由候选区间的类信息熵来选择。子集S₁和子集S₂的信息熵为Ent(S₁)和Ent(S₂)，则由断点T关于属性A的类信息熵可以表示为

$E\left(A,T;S\right)=\left|S_1\right|/\left|S\right|\cdot Ent\left(S_1\right)+\left|S_2\right|/\left|S\right|\cdot Ent(S2)$

|S|表示集合中元素个数。

对于给定的属性A，将使得E(A;T;S)值最小的点作为离散化的划分点，并将其记为Tmin。划分点Tmin将区间划分为两个部分，样本集合也被分为两个集合S₁和S₂。在分别计算S₁和S₂的所有划分点的时候，假设T₁和T₂分别为S₁和S₂的最好的划分点，而它们所对应的类信息熵分别为E(A,T₁,S₁)和E(A,T₂,S₂)；如果E(A,T₁,S₁) > E(A,T₂,S₂)，就继续对S₁进行划分，反之则是S₂。也就是说，哪个大就划分哪个。然后递归调用他们，直到满足递归停止条件。停止条件是利用最小区分长度准则作为判断递归离散化是否停止，就是说集合S中的递归的划分区间，当满足下列条件时停止，

$Gain\left(A,T;S\right)<{\log }_2\left(N-1\right)/N+\Delta \left(A,T;S\right)/N$

其中：N是集合S中的样本数量， $Gain\left(A,T;S\right)=Ent\left(S\right)-Ent\left(A,T,S\right)$，

$\Delta \left(A,T;S\right)={\log }_2\left(3^k-2\right)-\left[k\cdot Ent\left(S\right)-k_1\cdot Ent\left(S_2\right)-k_2\cdot Ent\left(S_2\right)\right]$

其中k₁和k₂分别是集合S₁和S₂中的类别数量，即k = |S|，k₁ = |S₁|，k₂ = |S₂|。

4. 基于最小信息熵的离散化算法的设计及实现

基于信息熵的离散化算法有很多，比如文献 [4] [5] 等。本文采取的基于最小信息熵的离散化算法的主要步骤为：第一，计算一个连续属性的候选断点属性集。第二，从第一步得到的候选断点属性集中选取一个使信息熵的值最小的点，此断点把实例集合划分为两个部分，将此断点加入到断点集合中。第三，确定每个实例集合的断点，划分实例集合S直到它满足递归停止条件则退出程序，完成离散化工作。该算法是一个比较基础的算法，它每次仅从单个条件属性的候选断点中选择断点 [6]，得到的最终结果断点数目较多，但时间复杂度较低。但本文中是以针对该算法采用多组数据进行比较，实验结果表明此算法是有效的。

具体算法描述表示如下：

步骤1：计算连续属性的候选断点属性集。

步骤2：从第一步得到的候选断点属性集中选取一个使信息熵的值最小的点，此断点把实例集合划分为两个部分，将此断点加入到断点集合中。信息熵计算方法如下：对于一个给定的实例的集合S，一个属性A，一个分类的边界T（把S分为S₁和S₂两个部分），那么由分类边界T确定的分类的信息熵为：

$E\left(A,T;S\right)=\left|S_1\right|/\left|S\right|\cdot Ent\left(S_1\right)+\left|S_2\right|/\left|S\right|\cdot Ent(S2)$

信息熵计算公式为 $Ent\left(S\right)=-{\displaystyle \underset{j=1}{\overset{k}{\sum }}{P}_j\log (Pj)}$

步骤3：对每个实例集合都调用步骤2中的方法进行划分，确定断点。递归停止条件为：

$Gain\left(A,T;S\right)<{\log }_2\left(N-1\right)/N+\Delta \left(A,T;S\right)/N$

具体算法伪代码如下：

5. 结果分析

5.1. 简单例子

测试一个较为简单的例子，条件属性：4个；决策属性：1个；记录条数：75条；属性名称：A，B，C，D，E；属性类型：float，float，float，float，integer。离散化前后结果如图1~2所示：

Figure 1. Before discretization

图1. 离散化前

Figure 2. After discretization

图2. 离散化后

测试结果表明，对于float类型的属性进行离散化后得到了离散化后的属性符号，并且该例中本是离散属性的Ｅ不需要再离散化。由于数据量小，离散化时间几乎为0。

5.2. 性能分析

本次测试主要测试了75~4000条数据，具体运行时间折线图如图3所示。

Figure 3. The comparison of time with different data scale

图3. 运行时间比较图

从图上可以看出，随着数据量的增大，离散化时间也在增大。但增长又不是线性的，这是因为离散化时间不但和记录的条数有关，还和断点的个数、需要离散化属性的个数以及属性的类型等有关。

6. 总结与展望

本文研究并实现了基于最小信息熵的离散化算法，它可以从这些含有连续属性的数据集中取得好的数据样本，得到简洁且有效的规则，如此可以方便数据在后续挖掘中的处理，并帮助企业及用户更有效的挖掘需要的数据。

基金项目

本项目得到网络文化与数字传播北京市重点实验室开放课题资助；促进高校内涵发展–科研水平提高项目(5221823410)资助。

参考文献