基于粒的二进制数表示的一种熵的计算方法

[摘要]很多决策树算法中，进行分裂选择测试属性的时候，都要用到对属性熵的计算和比较，提出一种方法，该方法首先将属性的等价类和粒联系起来，继而利用粒的二进制数表示来计算相应属性的熵，也就是说将等价类转化为粒的二进制数表示，这样只需要将粒的二进制数驻留内存就可以计算熵了，现在在包含数以百万计样本的非常大的训练集是很普通的，利用这种方法就可以减少在计算熵时训练样本在主存和高速缓存换进换出的次数，达到提高效率的目的。

[关键词]信息粒 熵

中图分类号：TP3文献标识码：A文章编号：1671－7597（2009）0320040－01

一、引言

由Z.Pawlak与他的合作者于70年代提出的粗糙集理论从一种全新的视觉审视知识，认为知识与分类相关，知识是有粒度的。所谓信息粒（Information Granule）是指人类在解决处理和存贮信息的有限能力上的一种反映，也就是人类在解决和处理大量复杂信息问题时，需要将大量复杂信息按其各自的特征和性能将其划分成若干较简单的块，而每个如此划分出来的块被看成一个粒。这种处理信息的过程就被称作信息粒化。信息的颗粒化相当于把原始的复杂的问题分解为多个易管理的子问题，即把大颗粒分解为小颗粒，颗粒化问题随处可见，它是许多学科的共同研究课题。粒计算是由T.Y.Lin提出的，现在已经成为数据挖掘等领域的一个重要工具。

二、有关粗糙集和粒计算的概念

一个论域U在一个等价关系R下可以得到U关于R的一个划分，划分后的所有U的子集的集合就是U关于R的一个商集U/R，商集U/R中的每个元素就是一个粒。知识的这种颗粒状结构通过等价关系的等价类表示。

既然等价类可以表示知识的颗粒状结构，那么将等价类看成是粒就是很容易理解的事情因为施行粒计算比施行等价类计算速度要快的多，灵活的多[2]。

例如表一是对AllElectronics顾客是否会买计算机所做的调查的一个决策表。按条件属性age分类，则可得商集U/IND(age)={[“<=30”]，[“31…40”]，[“>40”]}。按决策属性buys_computer分类，则可得商集U/IND(buys_computer)={[no],[yes]}。为了将等价类和粒建立联系，我们将商集中的元素作为粒，显然它是一种等价类。为了方便地表示一个粒，我们引入一个二进制数表示。表示规则为：对每个粒中的元素都可以给出它在全域U上的位置即下标表示法，然后以下标编码对应于二进制位数的位数来确定二进制位数的0、1取值，即Oi∈U且出现于某个等价类时，相应的表示该等价类的二进制数的第i位上置1，否则置0。具体的表示见表二。

设K＝（U，M）为一知识库，R∈M为一知识，在R对U形成均匀划分的情况下，R的熵值较大，而此时知识的粒度GD（R）较小；由表三可以看出它们各自的变化趋势。

接下来讨论如何利用粒的二进制数表示法来求取对应属性的熵。我们还用上面的那个例子，由表二已知U/IND(age)={[“<=30”],[“31…40”]，[“>40”]},

[“<=30”]=11000001101000，[“31,…,40”]=00100010000110，[“>40”]=00011100010001，其中sij是子集sj中类Ci的样本数，pij＝是Sj中的样本属于类Ci的概率。

因为[“<=30”]AND [no]＝11000001000000中1的个数为3，所以s11＝3，

[“<=30”]AND[yes]＝00000000101000中1的个数为2，所以s12＝2

按照公式，对于age＝”<=30”, I(s11,s12)=－3/5log2(3/5)－2/5log2(2/5)=0.971

同理对于age=”31…40”，易知I（s11,s12）=0,

age=”>40”时，I（s11,s12）=0.971

进而知道E（age）＝5/14 I（s11,s12）+4/14 I（s11,s12）+5/14 I（s11,s12）=0.694

至此，我们利用粒的二进制数表示法成功地求出了对应属性的熵。熵这个指标，在生成判定树的算法中，进行分裂选择测试属性时，一般作为判定指标。我们利用上面提到的思想来选择最佳的分裂方案，不过这里计算的不是进行分割时熵的减少量，而是分割后所产生的熵选择具有最小熵值的属性，显然，这个和计算熵的减少量是异曲同工的。

三、总结

本文讨论了粒和等价类的联系，并采用粒的二进制数表示法将它们统一了起来，因此将有关信息论的计算转化为二进制数之间的计算，提高了速度，节省了内存。

参考文献：

[1]张钹、张铃，问题求解理论及原理[M].北京：清华大学出版社，1990.

[2]刘斓、刘清，基于粒的二进制运算的关联规则提取方法[J].南昌大学学报，2003:27(1).

[3]Y.Y.Yao. On modeling data mining with granular computing[J].Proceedings of COMPSAC 2001,pp,638-643,2001.

[4]苗夺谦，范世栋. 知识的粒度计算及其应用[J].系统工程理论与实践，2002,1(1):48-56.

[5]王国胤，Rough集理论与知识获取[M].西安交通大学出版社，2001.

[6]J.W.Han,M.Kamber:Data Mining:Concepts and Techniques[M].Morgan Kaufmann Publishers,2001.

作者简介：

李洁颖，女，河南新乡人，助教，研究方向为人工智能和网络技术。