一种新的信息熵属性约简算法

粗糙集理论研究,仅作学习交流

１０８

２００９，４５（３２）Ｃｏｍｐｕｔｅｒ

Ｅｎｇｉｎｅｅｒｉｎｇａｎｄ

Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用

◎数据库、信号与信息处理◎

一种新的信息熵属性约简算法

舒文豪－，徐章艳－．２，杨炳儒ｚ，钱文彬－

ＳＨＵＷｅｎ—ｈａ０１，ＸＵ

Ｚｈａｎｇ－ｙａｎＩ．２＇ＹＡＮＧＢｉｎｇ—ｒｕ２，ＱＩＡＮＷｅｎ－ｂｉｎｌ

１．广西师范大学计算机科学与信息工程学院，广西桂林５４１００４

２．北京科技大学信息工程学院，北京１０００８３

１．ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，Ｇｕａｎｇｘｉ

Ｎｏｒｍａｌ

Ｕｎｉｖｅｒｓｉｔｙ，Ｇｕｉｌｉｎ，Ｇｕａｎｇｘｉ５４１００４，Ｃｈｉｎａ

２．Ｓｃｈｏｏｌ

ｏｆ

ＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，ＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙＢｅｉｊｉｎｇ，Ｂｅｉｊｉｎｇ１０００８３，Ｃｈｉｎａ

Ｅ—ｍａｉｌ：ｓｈｕｗｅｎｈａｏ＠１２６．ｃｏｒｎ

ＳＨＵ

Ｗｅｎ－ｈａｏ。ＸＵＺｈａｎｇ－ｙａｎ．ＹＡＮＧＢｉｎｇ－ｒｕ．ｅｔａ１．Ｎｏｖｅｌ

ａＵｒｉｂｕｆｉｏｎｒｅｄｕｃｔｉｏｎ

ａｌｇｏｒｉｔｈｍｏｆｉｎｆｏｒｍａｔｉｏｎｅｎｔｒｏｐｙ．Ｃｏｍ—

ｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄ

Ａｐｐｌｉｃａｔｉｏｎｓ．２００９．４５（３２）：１０８－１１０．

Ａｂｓｔｒａｃｔ：Ｆｉｒｓｔｌｙ，ｔｈｅｔｈａｔ

ｄｅｆｉｎｉｔｉｏｎｏｆａｔｔｒｉｂｕｔｉｏｎｒｅｄｕｃｔｉｏｎｏｆｄｉｓｃｅｒｎｉｂｉｌｉｔｙ

ｏｆａｔｔｒｉｂｕｔｉｏｎｒｅｄｕｃｔｉｏｎ

ｓｅｔ，ａ

ｏｂｊｅｃｔ

ｐａｉｒ

ｓｅｔｉｓ

ｐｒｏｖｉｄｅｄ．Ａｔｔｈｅｓａｍｅ

ｏｎ

ｔｉｍｅ，ｉｔ

ｉｓ

ｐｒｏｖｅｄ

ｔｈｅａｂｏｖｅｄｅｆｉｎｉｔｉｏｎ

ｔｏ

ｉｓ

ｅｑｕａｌ

ｔｏｔｈｅｄｅｆｉｎｉｔｉｏｎｏｆａｔｔｒｉｂｕｔｉｏｎ

ｄｅｃｉｓｉｏｎ

ｏｎ

ｒｅｄｕｃｔｉｏｎｂａｓｅｄｔａｂｌｅｉｓ

ｉｎｆｏｒｍａｔｉｏｎ

ｅｎｔｒｏｐｙ．Ｉｎ

ｏｒｄｅｒｉｓ

ｓｅｔ

ｃｏｍｐｕｔｅ

ｄｉｓｃｅｒｎｉｂｉｌｉｔｙｏｂｊｅｃｔｐａｉｒ

ｑｕｉｃｋ

ａｌｇｏｒｉｔｈｍｆｏｒｓｉｍｐｌｉｆｉｅｄｐｒｏｖｉｄｅｄ，ｗｈｏｓｅｔｉｍｅ

ｃｏｍｐｌｅｘｉｔｙ

Ｏ（ＩＣＩＩＵｌ）．Ｏｎｔｈｉｓｃｏｎｄｉｔｉｏｎ，ａｎｅｆｆｉｃｉｅｎｔａｔｔｒｉｂｕｔｉｏｎｒｅｄｕｃｔｉｏｎａｌｇｏｒｉｔｈｍｂａｓｅｄ

ｉｓ

ｄｅｓｉｇｎｅｄ，ｗｈｏｓｅ

ｔｉｍｅ

ｃｏｍｐｌｅｘｉｔｙｅｘａｍｐｌｅｉｓ

ａｎｄｓｐａｃｅｕｓｅｄ

ｔｏ

ｉｎｆｏｒｍａｔｉｏｎｅｎｔｒｏｐｙｏｆｄｉｓｃｅｒｎｉｂｉｌｉｔｙｏｂｊｅｃｔｐａｉｒ

ａｒｅ

ｃｏｍｐｌｅｘｉｔｙ

ｏｆｔｈｅｎｅｗ

ａｌｇｏｒｉｔｈｍ

ｎｅｗ

０（ＩＣＩＩＵＩ）＋０（ＩＣＩＩＵＩＣｌ２）ａｎｄＯ（ＩＵ／Ｃ１２）＋

０（ＩＵＩ）ｒｅｓｐｅｃｔｉｖｅｌｙ．Ｆｉｎａｌｌｙ，ａｎ

Ｋｅｙｗｏｒｄｓ：ｒｏｕｇｈ

ｉｌｌｕｓｔｒａｔｅ

ｔｈｅｅｆｆｉｃｉｅｎｃｙ

ｏｆｔｈｅ

ａｌｇｏｒｉｔｈｍ．

ｒｅｄａｃｔｉｏｎ；ａｌｇｏｒｉｔｈｍ

ｓｅｔ；ｉｎｆｏｒｍａｔｉｏｎ

ｅｎｔｒｏｐｙ；ｄｉｓｃｅｒｎｉｂｉｌｉｔｙ

ｏｂｊｅｃｔｐａｉｒｓｅｔ；ａｔｔｒｉｂｕｔｉｏｎｃｏｍｐｌｅｘｉｔｙ

摘要：给出一个区分对象对的属性约简定义，同时证明该属性约简的定义与基于信息熵的属性约简的定义是等价的。为求出区分对象对集，首先给出了一个快速求简化决策表的算法，其时间复杂度为Ｏ（ＩＣＩＩＵｌｏ然后在简化决策表的基础上，设计了基于区分对象对集的信息熵属性约简算法，其时间复杂度和空间复杂度分别为Ｏ（ＩＣＩＩＵｌ）＋０（ＩＣＩＩＵＩＣｌｚ）和０（ＩＵ／Ｃ１２）＋０（ＩＵＩ），最后用一个实例说明了新算法的高效性。

关键词：粗糙集；信息熵；区分对象对集；属性约简；算法复杂度ＤＯＩ：１０．３７７８／ｊ．ｉｓｓｎ．１００２—８３３１．２００９．３２．０３４

文章编号：１００２—８３３１（２００９）３２—０１０８－０３

文献标识码：Ａ

中罔分类号：ＴＰ３１１

１

引言

粗糙集理论㈣是由波兰数学家ｚ．Ｐａｗｌａｋ于１９８２年提出

别矩阵方法和二进制差别矩阵方法来设计属性约简算法最大的—个不足是：总是要先求出决策表的差别矩阵或者二进制差别矩阵。对于大型决策表而言，由于求差别矩阵不仅费时，而且也要占用大量的存储空间，这就使得算法的效率大大降低。为了尽可能地减少差别矩阵的存储空间，而又能用到差别矩阵的设计思想，结合区分对象对的方法１９１，设计了—个基于信息熵的属性约简算法，该算法无需求差别矩阵，但同时又利用了差别矩阵的思想。为了降低算法的复杂度，在简化决策表的基础上，给出了区分对象对集的属性约简的定义，并证明了该定义与基于信息熵的属性约简的定义是等价的。在此基础上设计了基于区分对象对集的信息熵属性约简算法，其时问复杂度和空间复杂度分别为：０（ＩＣＩＩＵｌ）＋０（１０ＩＵ／０２）和０（］Ｕ／Ｃ１２）＋０（Ｉ明）。

来的一种处理模糊和不确定性知识的数学工具。目前，该理论被广泛应用于人工智能、模式识别、数据挖掘和智能决策等领域，并取得了较大的成功。在粗糙集理论中，属性约简是非常重要的研究内容之一，很多学者针对不同的需求提出了许多不同的属性约简。目前，一些学者从信息论的角度提出基于信息熵的属性约简，并以信息熵作为启发信息设计了一些属性约简算法，其中文献ｆ４】中算法的时问复杂度为０（ＩＣＩＩＵｌ２）＋０（ＩＵｌ３），文献【５】中设计了两个算法，它们的时间复杂度分别为０（ＩＣＩＩＵＩｚ）＋Ｏ（ＩＵＰ）和０（Ｉｃ闩Ｍ）＋０（ＩＣＩＩＵＰ）。近来，一些学者用差别矩阵方法［６－７］和二进制差别矩阵ＩＳ］－－方法来设计该属性约简算法，但用差

基金项目：国家自然科学基金（ｔｈｅＮａｔｉｏｎａｌＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＣｈｉｎａｕｎｄｅｒＧｒａｎｔＮｏ．６０４６３００３）；广西教育厅科研基金项目（ｔｈｅ

ｓｃｉｅｎｔｉｆｉｃ

Ｒｅｓｅａｒｃｈ

ＰｒｏｊｅｃｔｏｆＤｅｐａｒｔｍｅｎｔｏｆＧｕａｎｇｘｉＥｄｕｃａｆｉｏｎｏｆＣｈｉｎａｕｎｄｅｒＧｒａｎｔＮｏ．２００８０７ＭＳ０１５）；广西研究生教育创新计

划项目。

作者简介：舒文豪（１９８５一），女，硕士研究生。主要研究方向：粗糙集理论及应用与数据挖掘；徐章艳（１９７２一），男，博士，副教授，主要研究方向：粗糙

集，模糊集，数据挖掘；杨炳儒（１９４３一），男，教授，博士生导师，主要研究方 …… 此处隐藏：7951字，全部文档内容请下载后查看。喜欢就下载吧 ……