基于粗糙集的实属性值约简算法

《基于粗糙集的实属性值约简算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2010年1月内蒙古大学学报(自然科学版)Jan．2010第41卷第1期JournalofInnerMongoliaUniversityVol_41No．I文章编号：100O一1638(2010)01—0097—05基于粗糙集的实属性值约简算法。赵连胜，施纪华(包头师范学院信息科学与技术学院，内蒙古包头014030)摘要：在A．Skowron关于属性值约简研究的基础上，给出截断点集的逻辑抽取方法，并基于复杂度的考虑提出一种改进的启发式算法，使属性的值集规模有实质性的约简．关键词：粗糙集；属性值约简；截断点集；逻辑抽取中图分类号：TP301．6文献标志码：A数据挖掘的对象主要是大数据集的数据

2、库或数据仓库，随业务而增长的海量数据，给数据挖掘带来新的挑战．虽然数据挖掘技术研究不断深入，可挖掘算法的效率提高越来越不明显，作为挖掘算法实施的起点，经过预处理的数据的质量严重影响着挖掘的效果．于是数据预处理工作就显得越来越重要．数据预处理包括数据清理、数据集成和变换、数据约简等操作，把原始的数据库或者数据仓库变换成适合挖掘的模式，为进一步的数据挖掘做准备．已有一些比较成熟的数据预处理技术n，但面对日益增长的海量数据和日趋复杂的数据结构数据预处理还有很多工作要做，数据约简是数据预处理的一个重要环节，粗糙集理论是用来处理模糊和不确定性知识的数学工具，是一种有效的软计算方法．其主要思想是在保持

3、分类能力不变的前提下，通过数据约简，导出问题的决策或分类规则，利用粗糙集进行数据约简主要有属性的约简和属性值约简，属性约简的研究已经比较充分。，而对属性值约简的研究相对较少．本文在A．Skowron关于属性值离散化约简研究的基础上，给出截断点集的逻辑抽取方法，并基于复杂度的考虑提出一种改进的启发式算法．1基本理论1．1决策系统定义1．1S为决策系统，可表示成S一{U，A，d)，其中是所有对象的集合U一{z，X⋯⋯z)，A是条件属性集合，d是决策属性．V—YaEAV，其中是口的值域．，：×A—是一函数，对每一口∈A，z∈U有f(xf，n)∈V．1．2不可分辨关系定义1．2在中定义二元关系IN

4、D称为不可分辨关系，是指对任意BA，设f(x，p)一p(z)INDp=((，z)∈U×U：对VP∈B，户(z)一P(z))此时称z，z是中在属性召下是不可分辨的．由于不可分辨关系满足自反性、对称性、传递性，所以不可分辨关系为一等价关系．1．3等价类定义1．3在中，Bc，／B一(E，E⋯⋯E)称为由等价关系IND／B在上划分的等价类，其中E，一{『1，五2⋯⋯‰jf(x¨B)：f(西2，B)=⋯f(x，B)x；j∈)．·收稿日期：2009—11-11基金项目：内蒙古自治区高等学校科学研究项目(NJo9152)作者简介：赵连胜(1963一)，男，内蒙古包头人，副教授，硕士，研究方向为数据库、数

5、据挖掘．98内蒙古大学学报(自然科学版)一个关系型数据库，其中列被标识成属性，行被标识成对象，若选定其中一个属性称为决策属性，其余属性称为条件属性，则也可认为关系型数据库是一决策系统．2属性值约简Skowron离散化处理。定义2．1S===(己，，A，)是一决策系统，V一[1a，ra)CR，口EA，laura．偶对(口，c)，VnEA，cEVa称作Va的截断点．定义2．2V∈A，对实值序列<<⋯<，其中{，，⋯，<屹)一{口(z)：∈U)，口的截断点集表示为：Ba={(口，(+g)／2)，(n，(+)／2)，⋯，(n，(屹一+屹)／2)，)．而U口EABa称作的截断点集．示例1“给一个决策

6、系统如表1，属性口，b的值域一Fo，2)；Vb=Eo，4)．口，b在中的值集为：口()一{0．8，1．0，1．3，1．4，1．6}．6(【，)={0．5，1．0，2．0，3．0)．口，b的截断点集为B一{(n，0．9)，(口，1．15)；(口，1．35)，(口，1．5))B6一((6，0．75)，(6，1．5)，(6，2．5))表1初始决策系统S表2S的c一分辨决策系统Table1OrginialdeeitionsystemSTable2C_discretizationofdecitionsystemS定义2．3S一(U，A，)，称作的C分辨决策系统，其中S一(，A，)，口EA，Ca一{(

7、口，f)，(口，c；)，⋯，(口，cD)是口的某一截断点集，且c<，C。a<，⋯，C对表1，令c—B。UB，容易得出的C分辨决策系统如表2所示．由于分辨处理的目的是约简属性的值集，以上方法中，不同的截断点集会有不同分辨决策系统，也即有不同的属性值集缩减效果，当找最优截断点集为