决策表属性约简的相对划分粒度表示

小型微型计算机系统ＪｏｕｒｎａｌｏｆＣｈｉｎｅｓｅＣｏｍｐｕｔｅｒＳｙｓｔｅｍｓ２００８年１２月第１２期Ｖ０１．２９Ｎｏ．１２２００８

决策表属性约简的相对划分粒度表示

冯琴荣ｚ一，苗夺谦１，程跌１

１（同济大学计算机科学与技术系．上海．２０１８０４）

。（山西师范大学数学与计算机科学学院，山西临汾０４１００４）

Ｅ－ｍａｉｌ；Ｆｅｎｇｑｒ７２＠１６３．ＣＯｍ

摘要：粗糙集理论认为知识就是分类．表文对知识的分类能力给予了量化．提出利用划分粒度来定量地表示知识的分类能力．在划分粒度概念基础上。针对决簋表定义了相对划分粒度并研究了它的性质，相对划分粒度可以定量表示决策表的条件属性子集相对于决策属性的分类能力的强弱｝最后证明了对一致决策表的属性约简来说，相对划分粒度表示与Ｐａｗｌａｋ提出的代数表示是等价的．

关键词：粗糙集；划分粒度；决策表；相对划分粒度

中图分类号：ＴＰｌ８文献标识码：Ａ文章编号：１０００－１２２０（２００８）１２—２３０５．０４

ＰｒｅｓｅｎｔａｔｉｏｎｏｆＲｅｌａｔｉｖｅＰａｒｔｉｔｉｏｎＧｒａｎｕｌａｒｉｔｙｏｆＡｔｔｒｉｂｕｔｅｓＲｅｄｕｃｔｉｏｎｆｏｒＤｅｃｉｓｉｏｎＴａｂｌｅ

ＦＥＮＧＱｉｎ—ｔｏｎ９１“．ＭＩＡＯＤｕｏ－ｑｉａｎｌ。ＣＨＥＮＧＹｉｌ

１（Ｄｅｐａｒｔｍｅｎｔｏ，ＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ．ＴｏｎｇｊｉＵｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ２０１８０４，Ｃｈｉｎａ）

２（Ｃｏｌｌｅｇｅ０，ＭａｔｈｅｍａｔｉｃｓａｎｄＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ。ＳｈａｎｚｉＮｏｒｍａｌ

Ｕｎｉｖｅｒｓｉｔｙ?口咖ｎ０４１００４?Ｃｈｉｎａ）

Ａｂｓｔｒａｃｔ：Ｋｎｏｗｌｅｄｇｅａｎｄｃｌａｓｓｉｆｉｃａｔｉｏｎｓａｒｅｒｅｌａｔｅｄｔｏｇｅｔｈｅｒｂｙｔｈｅｔｈｅｏｒｙｏｆｒｏｕｇｈｓｅｔｓｗｈｉｃｈｃｌａｉｍｉｓｔｈａｔｋｎｏｗｌｅｄｇｅｉｓｄｅｅｐ－ｓｅａｔｅｄｉｎｔｈｅｃｌａｓｓｉｆｉｃａｔｏｒｙａｂｉｌｉｔｉｅｓｏｆｈｕｍａｎｂｅｉｎｇｓ．Ｉｎｔｈｉｓｐａｐｅｒ，ｗｅｆｉｒｓｔｌｙｇｉｖｅａｑｕａｎｔｉｔａｔｉｖｅｒｅｐｒｅｓｅｎｔａｔｉｏｎｏｆｔｈｅａｂｉｌｉｔｙｏｆｋｎｏｗｌｅｄｇｅ’ｓｃｌａｓｓｉｆｉｃａｔｉｏｎ．ａｎｄｐｒｏｖｉｄｅａｎｏｖｅｌｒｅｐｒｅｓｅｎｔａｔｉｏｎｆｏｒｋｎｏｗｌｅｄｇｅ?ｔｈａｔｉｓ，ｉｔｃａｎｂｅｅｘｐｒｅｓｓｅｄｂｙｐａｒｔｉｔｉｏｎｇｒａｎｕｌａｒ－ｉｔｙ．Ｓｅｃｏｎｄｌｙ，ｔｈｅｒｅｌａｔｉｖｅｐａｒｔｉｔｉｏｎｇｒａｎｕｌａｒｉｔｙｉｓｄｅｆｉｎｅｄ?ａｎｄｉｔｓｑｕａｌｉｔｉｅｓａｒｅｄｉｓｃｕｓｓｅｄ，ｗｈｅｒｅｔｈｅｒｅｌａｔｉｖｅｐａｒｔｉｔｉｏｎｇｒａｎｕｌａｒｉ＿ｔｙｃａｎ

ｂｅｕｓｅｄｔｏｄｅｓｅｒｉｐｔｔｈｅｃｌａｓｓｉｆｉｃａｔｉｏｎａｂｉｌｉｔｙｏｆｃｏｎｄｉｔｉｏｎａｌａｔｔｒｉｂｕｔｅｓｒｅｌａｔｅｔｏｄｅｃｉｓｉｏｎａｔｔｒｉｂｕｔｅ．Ｆｉｎａｌｌｙ，ｔｈｅｅｑｕｉｖａｌｅｎｃｅｂｅｔｗｅｅｎｔｈｅａｌｇｅｂｒａｉｃｒｅｐｒｅｓｅｎｔａｔｉｏｎａｎｄｔｈｅｒｅｌａｔｉｖｅｐａｒｔｉｔｉｏｎｇｒａｎｕｌａｒｉｔｙｒｅｐｒｅｓｅｎｔａｔｉｏｎｉｓｐｒｏｖｅｄｆｏｒａｃｏｎｓｉｓｔｅｎｔｄｅｃｉｓｉｏｎｔａｂｌｅ．

Ｋｅｙｗｏｒｄｓ：ｒｏｕｇｈｓｅｔ；ｇｒａｎｕｌａｒｉｔｙｏｆｐａｒｔｉｔｉｏｎ，ｄｅｃｉｓｉｏｎｔａｂｌｅ；ｒｅｌａｔｉｖｅｇｒａｎｕｌａｒｉｔｙｏｆｐａｒｔｉｔｉｏｎ

１引官

粗糙集理论［１。。］是１９８２年由波兰学者Ｐａｗｌａｋ教授提出的，它是一种处理不完备、不精确和不确定知识的新的数学工具．粗糙集理论认为知识就是对论域的划分，而划分与等价关系是一一对应的，因此Ｐａｗｌａｋ教授基于等价关系和集合运算提出了知识的代效表示．在知识的代数表示中，粗糙集理论的许多概念与运算的直观性较差，不容易使人理解其本质，并且在此表示下许多算法的效率也不高．我们知道，同一问题在不同知识表示下的算法复杂性是不同的［“．籍于此苗夺谦教授从一个全新的角度重新审视了知识。他认为知识可以看成是论域的子集组成的争代数上的随机变量。并以信息论为基础，借助于信息熵的良好的解释性。提出利用信息嫡来表示知识。从而提出了知识的信息表示［“］，信息表示从更深层次上揭示了知识的本质，并且基于知识的信息表示可以设计一些高效的算法．

信息表示虽然有较好的解释性，然而它的运算仍较复杂．本文直接从划分出发来研究知识．我们知道，每个划分包含若干个划分块，而每个划分块又是论域的一个子集，本文称之为一个划分粒．对一个划分粒来说如何度量它的大小呢？自然会想到用集合基数来度量．由粗糙集理论知，一个划分它包含的划分粒越多，它的分类能力就越强（因为论域中元素个数是固定不变的）．而粒度是对粒大小的一种平均度量，因此对一个划分来说．可以使用其划分粒的平均大小来度量它的分类能力．本文将知识看成是定义在由它导出的划分粒基数上的随机变量，并定义了随机变量的概率分布，基于此概率分布定义了知识的划分粒度，它是划分粒大小的概率平均，从而可以使用划分粒度来定量地表示知识的分类能力．

知识约简是粗糙集理论的核，ｂ内容之一，对信息系统而言，知识约简就是在保持其分类能力不变的前提下，删除其中的冗余属性Ｉ而对决策表而言，知识约简就是在保持其条件属性集相对于决策属性分类能力不变的前提下，删除其中的冗余属性．在决策表中。如何来度量决策表的条件属性子集相对于决策属性的分类能力呢？本文在划分粒度概念基础上针对

收稿日期：２００７—０７—１６基金项目：国家自然科学基金项目（６０４７５０１９．６０７７５０３６）资助；教育部博士点专项基金项目（２００６０２４７０３９）劁Ｊ．作者简介ｔ冯琴荣．女，１９７２年生．博士研究生，副教授．研究方向为粗糙集理论、粒计算；苗夺谦，男，１９６４年生．教授．博士生导师，研究方向为粗糙集理论、粒计算、Ｗｅｂ智能，模式识别等Ｉ程映．女。１９７７年生。博士研究生．讲师。研究方向为粗糙模糊集理论、模糊粗糙集理论．

　万方数据