《基于粗糙集理论的属性约简算法研究》由会员分享，可在线阅读，更多相关《基于粗糙集理论的属性约简算法研究（53页珍藏版）》请在金锄头文库上搜索。
1、青岛大学硕士学位论文基于粗糙集理论的属性约简算法研究姓名：史军申请学位级别：硕士专业：计算机软件与理论指导教师：刘遵仁20090603基于粗糙集理论的属性约简算法研究摘要粗糙集理论是2 0 世纪8 0 年代发展起来的种新的处理含糊性和不确定性问题的数学工具，它是智能信息处理的一种重要方法，基于不可区分性思想和知识简化方法。属性约简算法是粗糙集理论的核心内容。粗糙集属性约简的研究在知识获取、机器学习、模式识别、决策分析、模型建立等实际应用中有重要的意义，但是，由于属性约简被证明是一个N P h a r d 问题，因此，研究更为有效的属性约简算法，有效地获取较优的属性约简，降低算法的时间复杂度，寻
2、求快速的约简算法仍是粗糙集理论的主要研究课题之一。本文首先介绍了粗糙集理论的基本概念和相关知识，对粗糙集理论中基于区分矩阵、属性重要度、信息熵的属性约简算法进行了系统综述，并且详细分析了算法的时间复杂度和空间复杂度。由于传统的粗糙集模型没有与关系数据库系统结合，该模型许多计算的基本操作都是在平面文件上进行的，没有利用高性能的数据库集合操作。鉴于此，研究人员提出了新的基于数据库系统的粗糙集模型，在关系代数的基础上对核属性和约简进行重新定义，从而利用高效的面向集合的数据库系统操作。在此基础上，提出了一种新的基于数据库系统的属性约简算法。最后，将此算法与几种典型的属性约简算法从算法运行时间和约简结果
3、的准确性进行了对比，得出了相应的结论。关键字：粗糙集，属性约简，数据库系统S t u d yo nA t t r i b u t eR e d u c t i o nA l g o r i t h mb a s e do nr o u g hs e tA b s t r a c tR o u g hS e tt h e o r yi san e wm a t h e m a t i c a lt o o lw h i c hc a nt a c k l ea m b i g u i t ya n du n c e r t a i n t yd e v e l o p e df r o mt h
4、 e1 9 8 0 s I ti sa ni m p o r t a n tm e t h o do fi n t e l l e c t i v ei n f o r m a t i o nt r a n s a c t i o n ，w h i c hb a s e do fn o n d i s t i n g u i s ha n dk n o w l e d g er e d u c t i o n F i n d i n gt h em i n i m a lr e d u c t i o ni so n eo ft h em o s ti m p o r t a n tw o r
5、 k si nt h er e s e a r c ho fr o u g hs e tt h e o r y , a sa ni m p o r t a n tp a r to fs o f tc o m p u t i n g ，a t t r i b u t er e d u c t i o np l a y sa p p l i c a t i o n sh a v ep l a y e da ni m p o r t a n tr o l e ，e s p e c i a l l yi nt h ea r e a so fk n o w l e d g ea c q u i s i
6、t i o n ，m a c h i n el e a n i n g ，p a t t e r nr e c o g n i t i o n ，d e c i s i o na n a l y s i sa n dm o d e l i n ge t c H o w e v e r , i th a sb e e np r o v e dt h a tf i n d i n gt h em i n i m a lr e d u c t i o n si saN P - h a r dp r o b l e m S oi ti st h em a i ns t u d ya r e ao nr
7、 o u g hs e ti nr e s e a r c h i n ge f f e c t i v ea t t r i b u t er e d u c t i o na l g o r i t h m ，a c q u i r i n gt h ep e r f e c tr e s u l to fa t t r i b u t er e d u c t i o na n dr e d u c i n gt h et i m ec o m p l e x i t y F i r s t l y , t h et h e s i sr e v i e w st h et h e o
8、r i e sa n dm e t h o d so fr o u g hs e ts y s t e m a t i c a l l y ,a n da n a l y z e st h ea l g o r i t h m so fa t t r i b u t er e d u c t i o nb a s e do nd i s c e r n i b i l i t ym a t r i x ，a t t r i b u t es i g n i f i c a n c e ，i n f o r m a t i o ne n t r o p y T h et i m ec o m p
9、 l e x i t ya n ds p a c ec o m p l e x i t yo ft h e s ea l g o r i t h m sh a v eb e e na n a l y z e dd e t a i l e d l y T h et r a d i t i o n a lr o u g hs e t sm o d e ld i d n tc o m b i n ew i t ht h er e l a t i o nd a t a b a s es y s t e ma n da l lt h ei n t e n s i v ec o m p u t a t i
10、 o n a lo p e r a t i o n sa r ep e r f o r m e di nf l a tf i l e s ，r a t h e rt h a nt a k ea d v a n t a g e so ft h ev e r ye f f i c i e n ts e t - o r i e n t e dd a t a b a s eo p e r a t i o n s I nv i e wo ft h a t ，t h er e s e a r c h e r sp r o p o s e dan e wr o u g hs e t sm o d e lb
11、a s e do nd a t a b a s es y s t e ma n dr e d e f m e dt h ec o r ea t t r i b u t e sa n dr e d u c t i o nb a s e do nr e l a t i o na l g e b r ai no r d e rt ot a k ea d v a n t a g e so ft h ev e r ye f f i c i e n ts e t o r i e n t e dd a t a b a s eo p e r a t i o n s B a s e do nt h i s ，w
12、 ep r o p o s et h ea t t r i b u t er e d u c t i o na l g o r i t h mb a s e do nd a t a b a s e F i n a l l y , w ec o m p a r et h ep r o p o s e da l g o r i t h mw i t ho t h e ra t t r i b u t er e d u c t i o na l g o r i t h mo nt h er u n t i m eo ft h ea l g o r i t h ma n dt h ea c c u r
13、 a c yo fr e d u c t i o nr e s u l ta n dd r a ws o m ec o n c l u s i o n K e yw o r d s ：r o u g hs e t , a t t r i b u t er e d u c t i o n ，d a t a b a s es y s t e m学位论文独创性声明、学位论文知识产权权属声明学位论文独创性声明本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文中依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上已属于他人的任何形式的研究成果，也不包含本人己用于其他学
14、位申请的论文或成果。本人如违反上述声明，愿意承担由此引发的一切责任和后果。论文作者签名：它埠 1眺卟钿户学位论文知识产权权属声明本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为青岛大学。本学位论文属于：保密口，在年解密后适用于本声明。 不保利( 请在以上方框内打“4 “ )论文作者签名导师签名：5 1钿今日?多月乡日雌中么易第一章绪论1 1 研究的背景和意义第一章绪论近十几年，随着科学技术飞速的发展，经济和社会都取得了极大的进步，随
15、着计算机、网络和通讯等信息技术的高速发展，信息处理在整个社会规模上迅速产业化，在技术上表现为整个社会对大规模数据操作的产业化。这使得人们所积累的数据越来越多，并且数据与信息系统中的不确定性更加显著。海量杂乱的数据背后隐藏着许多重要的信息，人们希望能够对其进行深入分析，以便更好地利用这些数据所隐藏的信息。目前的数据库系统可以高效地实现数据的录入、查询、统计等功能，但无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势。缺乏挖掘数据背后隐藏的知识的手段，导致了“数据爆炸但知识贫乏“ 的现象。同样，传统的统计技术也面临了极大的挑战。这就急需有新的方法来处理这些海量般的数据。于是，人们
16、结合统计学、数据库、机器学习等技术，提出数据挖掘来解决这一难题一1 。数据挖掘是最近几年来随着数据库和人工智能发展起来的一门新兴的技术。其处理对象是大量的日常业务数据，目的是为了从这些数据中抽取一些有价值的知识或信息。它的出现为自动和智能地把海量数据转化为有用的知识提供了有力的手段。人们把原始数据看作是形成知识的源泉，就像从矿石中采矿一样。原始数据可以是结构化的，如关系数据库中的数据；也可以是半结构化的，如文本、图形、图像数据甚至是非结构化的异构数据，如分布在网络上的W e b 数据。发现知识的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。发现的知识可以用于信息管理、查询优化、决策支持、过程控制等，还可以用于数据自身的维护。因此，数据挖掘融合了数据库、人工智能、机器学习、统计学等多个领域的理论和技术是- - l 广义的交叉学科。数据预处理是数据挖掘中的重要一环n 叭。实际系统中的数据一般都具有不完全性、冗余性和模糊性，很少能直接满足数据挖掘算法的要求。另外，海量的实际数据中无意义的成分很多，严重影响了数据挖掘算法的执行
