（计算机软件与理论专业论文）基于关系数据库的属性约简研究.pdf

一 i b ， - 原创性声明和关于论文使用授权的说明 原创性声明 f 舢舢f f f f f 棚f f f f f f f f f f f f f f f f f f f f f f 朋 y 1 7 9 1 8 。9 2 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名：蕴二鱼免 e l期：丝：生! r 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：托幺2 瑰一导师签名 - 一i ， 曩 1 7 i ， e j ： 礓 山东大学硕士学位论文 目录 摘要i a b s t r a c t 第一章绪论1 1 1 研究背景l 1 2 国内外研究现状2 1 3 研究课题的主要内容3 1 4 本文所做的主要工作4 1 5 本文结构5 第二章属性约简的基础知识一6 2 1 属性约简的相关知识及术语介绍一6 2 1 1 数据浓缩6 2 1 2 信息系统6 2 1 3 不可区分关系7 2 1 4 正区域7 2 1 5 属性独立性7 2 1 6 属性约简8 2 2 属性约简的基本过程8 2 3 现有经典属性约简方法分析9 2 3 1r o u g h 集高效算法9 2 3 2 新的可区分矩阵的约简方法1 0 2 3 3 基于区分能力的粗糙集属性约简方法1 1 2 3 4 基于信息熵属性重要度的属性约简方法1 1 2 3 5 蚁群优化属性约简算法1 2 2 3 6 基于遗传算法的属性约简1 3 2 3 7 基于s q l 的粗糙集属性约简方法1 4 2 4 本章小结1 4 第三章基于数据库技术的经典算法改进1 6 山东大学硕士学位论文 3 1 本章概述1 6 3 2 属性约简的新思路1 6 3 2 1 不可区分关系的计算1 7 3 2 2 正区域的计算1 9 3 2 3 属性核心的计算2 0 3 3 改进的经典属性约简算法2 2 3 4 实验结果2 3 3 5 小结2 4 第四章属性约简的新算法2 5 4 1 属性核心计算的改进2 5 4 1 1 属性核心计算的非必须性2 5 4 1 2 属性核心计算的非必须性证明2 7 4 2 正区域的补2 8 4 3 基于正区域的补的属性核心计算2 9 4 4 属性约简新算法3 0 4 5 实验结果3 l 4 6 小结3 3 第五章基于新算法的数据库策略3 5 5 1 增加主键3 5 5 2 建立索引3 6 5 2 1 基于属性核心的索引3 8 5 2 2 基于主键的索引3 8 5 2 3 基于决策属性的索引3 9 5 3 本章小结3 9 第六章总结和展望4 l 6 1 总结4 l 6 2 展望4 2 参考文献4 3 致谢4 6 - l j 0 一 p ，l 伽 山东大学硕士学位论文 攻读学位期间发表的学术论文目录4 7 攻读学位期间参与科研项目情况4 8 i i i 山东大学硕士学位论文 t a b l eo fc o n t e n t s a b s t r a c ti nc h i n e s e 】 a b s t r a c ti ne n g l i s h i i c h a p e r t1 e x o r d i u m 1 1 2c u r r e n ta c t u a l i t y 2 1 3r e s e a r c ha r e a 3 1 4m a i nw o r k s 4 1 5o r g a n i z es t r u c t u r e 5 c h a p e r t2 c u r r e n tr e s e a r c ho na t t r i b u t er e d u c t 6 2 1t e r m i n o l o g ya n dt e c h n o l o g yo na t t r i b u t er e d u c t 6 2 1 1d a t a e n r i c h m e n t 6 2 1 2i n f o r m a t i o ns y s t e m 6 2 1 3i n d i s c e m i b i l i t yr e l a t i o n s h i p 7 2 1 4p o s i t i v ea r e a 7 2 1 5i n d e p e n d e n c eo f a t t r i b u t e 7 2 1 6a t t r i b u t er e d u c t i o n ：8 2 2m a i np r o c e s si na t t r i b u t er e d u c t 8 2 3c u r r e n tc l a s s i ca l g o r i t h m so nr e d u c t 9 2 3 1r e s e a r c ho ne f f i c i e n ta l g o r i t h mf o rr o u g hs e tm e t h o d s 二9 2 3 2a l g o r i t h mo f r e c u c tb yn e w d i s c e r n i b l em e t r i c 1 0 2 3 3r o u g hs e tr e d u c to nd i s c e m i b l ec a p a b i l i t y 11 2 3 4a l g o r i t h mo n e n t r o p y 1 1 2 3 5a n tc o l o n yo p t i m i z a t i o na p p r o a c ht oa t t r i b u t er e d u c t i o np r o b l e m 12 2 3 6r o u g hs e tr e d u c t i o nb a s e do ng e n e t i ca l g o r i t h m 1 3 2 3 7 m e t h o do f a t t r i b u t er e d u c t i o nb a s e do ns q l 1 4 c h a p e r t3i m p r o v e m e n to nc l a s s i ca l g o r i t h mo fa t t r i b u t er e d u c t 1 6 i v ， i t i i 一；li - 山东大学硕十学位论文 3 2n e wi d e a so na t t r i b u t er c d u c t 1 6 3 2 1c a l c u l a t i o no ni n d i s c e r n i b l er e l a t i o n s h i p 1 7 3 2 2c a l c u l a t i o no np o s i t i v ea r e a j 1 9 3 2 3c a l c u l a t i o no nt h ec o r e 2 0 3 3i m p r o v e dc l a s s i ca t t r i b u t er e d u c t i o na l g o r i t h m 2 2 3 4e x p e r i m e n tr e s u l t 2 3 3 5s u m m a r y 2 4 c h a p t e r4a n e w a l g o r i t h m o n a t t r i b u t e r e d u c t i o n 2 5 4 1i m p r o v e m e n to i lc a l c u l a t i o no f t h ec o r e 2 5 4 i 1t h en o n - n e c e s s i t yo f t h ec a l c u l a t i o no nt h ec o r e 2 5 4 1 2p r o o f 2 7 4 2c o m p l e m e n to f p o s i t i v ea r e a 2 8 4 3c a l c u l a t i o no nt h ec o r eb a s e do nt h ec o m p l e m e n to f p o s i t i v ea r e a 2 9 4 4an e wa t t r i b u t er e d u c t i o n 3 0 4 5e x p e r i m e n t a lr e s u l t 31 c h a p t e r5 d a t a b a s es t r a t e g yf o rm e t h o d sa b o v e 3 5 5 1a d dp r i m a r yk e y 3 5 5 2c r e a t ei n d e x 3 6 5 2 1i n d e xo nt h ec o r e 3 8 5 2 2i n d e xo nt h ep r i m a r yk e y 3 8 5 2 3i n d e xo nt h ed e c i s i o na t t r i b u t e s 3 9 c h a p t e r6s u m m a r ya n dp r o s p e c t s 4 1 r e f e r e n c e s 4 3 ， a c k n o w l e d g e m e n t 4 6 p a p e rp u b l i s h e d 4 7 r e s e a r c hd u r i n gt h em a s t e r 4 8 v 一 电 l 争 一 i 山东大学硕士学位论文 摘要 当今时代伴随着网络的迅速发展，信息传递方式的增加，越来越多的信息 能够更迅速的传递到人们面前。海量和多元化的信息在给人们生活带来便利的 同时，也给人们带来了灾难“数据炸弹 。面对铺天盖地蜂拥而至的信息， 另人们苦恼和彷徨，不禁期待找到一种方式来简化数据，只保留中心数据供自 己使用。在这种情况下，对数据进行挖掘的各种方式就应运而生，并在越来越 广阔的领域获得应用和发展。 属性约简正是这些挖掘方式中的一种很重要的形式，它是在保持数据分类 或决策能力不变的前提下，对数据中的非决策属性进行约简，从而获得人们期 望的与原数据具有相同分辨能力但是数量却少得多的精简数据。 本文从阐述在信息时代信息约减的作用开始，首先阐述了在信息系统中核 属性的重要作用以及利用区分矩阵的方式来求取属性核心的代价、求取正区域 的代价等进行了细致的分析，对当前经典的属性约简算法进行了简介，并运用 r o u g h 集的理论给出了判定一个属性子集中是否包含属性核心的充要条件。然 后，根据这些研究结论，结合当前大容量的数据都是存储在数据库中的基本现 实，充分利用了数据库技术在大容量数据存储和查询的优越性，对当前的基于 粗糙集的属性约简算法进行了改进，并在此基础上，结合求取核心属性的非必 须性和正区域的补的概念，从一个新的途径提出了新的属性约简算法。 通过对改进的经典算法和新提出的属性约简算法的实验结果的分析表明， 对于较大数据集和大数据集，两种算法解决了目前属性约简算法应对大容量数 据的窘境，并且效率远远高于现存的一些基于主存的算法。同时算法逻辑简单， 易于实现和推广，对于数据挖掘、人工智能、机器学习等领域具有一定的促进 作用。 关键词：r o u g h 集，属性约简算法，属性核心，数据库技术 山东大学硕士学位论文 a b s t r a c t n o w a d a y s ，f o l l o w e db yr a p i dd e v e l o p m e n to fi n t e m e ta n dt r a n s m i s s i o ns t y l e s a d d e d ，m o r ea n di l k ) r ei n f o r m a t i o nc o u l dr u s ht op e o p l er a p i d l y m a s sa n dv a r i e t y d a t ab r i n gn i t o r ec o n v e n i e n c et oh u m a n ，b u t 砒t h es a m et i m e ，i tb r i n g su sa l l i n f o r m a t i o nb o m b s om a n yp e o p l el o o kf o r w a r dt os e e k i n gaw a yt of i n dt h ek e y p a r tt oi n s t e a do ft h e mi nt h i ss i t u a t i o n , d a t am i n i n ge m e r g e da n di su s e di ni t l o r e a n dm o r ef i e l d s a t t r i b u t er 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 a y si nd a t am i n g ar e d u c ti sa s e to fa t t r i b u t e st h a tp r e s e r v ep a r t i t i o n i tm e a n st h a tar e d u c ti sam i n i m a ls u b s e to f a t t r i b u t e sw h i c hh a st h es a m ec l a s s i f i c a t i o na b i l i t ya st h ew h o l es e to fa t t r i b u t e si n u n i v e r s e s oi tc a n u s el e s sd a t at op r e s e n tt h es a m ei n f o r m a t i o nw en e e d w i t ht h ed e s c r i p t i o no f t h ei m p o r t a n tr o l eo f i n f o r m a t i o nr e d u c i n gi nm o d e mt i m e ， t h i sc h a p t e ra n a l y s e so nt h ei m p o r t a n tr o l eo fc o r ea t t r i b u t e s ，t h ec o s to nc a l c u l a t i n g c o r ea t t r i b u t e sb yd i s c e r n i b i l i t ym a t r i xa n dt h ep o s i t i v ea r e aa n dg i v e sas i m p l e d e s c r i p t i o no fc u r r e n tc l a s s i ca l g o r i t h m s i tp u t sf o r w a r dan e c e s s a r ya n ds u f f i c i e n t c o n d i t i o no nw h e t h e ras u b s e to fa t t r i b u t e sc o n t a i n st h ec o r ea t t r i b u t e s b a s eo nt h e s e r e s e a r c h e s r e s u l t sa n dr e f e r r i n gt h er e a l i t yt h a tm o s to ft h ed i g i t a ld a t ai ss t o r e di n d a t a b a s ec u r r e n t l y ，a ni m p r o v e da 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 ti s p r e s e n t e d ，u s i n gt h es u p e r i o r i t yo ft h et e c h n o l o g y o nd a t a b a s e m o r e o v e r ，w e p r o p o s ea n e wa l g o r i t h mb a s e do nt h eu n n e c e s s i t yo ft h ec a l c u l a t i n go nt h ec o r ea n d t h ec o m p l e m e n to f t h ep o s i t i v ea r e a e x p e r i m e n t s r e s u l t ss h o wt h a tt h et w oa l g o r i t h m sa r em o r ee f f i c i e n ti nt h el a r g e r o rl a r g e s td a t as e t s t h e yr e s o l v et h ed i l e m m ao ft h ec u r r e n ta t t r i b u t er e d u c t i o na n d l e s sc o m p l e xa n dc a nb ee a s i l yr e a l i z e di na d v a n t a g eo fd a t a b a s eq u e r yl a n g u a g e i t w i l lp r o m o t et h ed e v e l o p m e n ti nt h ea r e ao fd a t am i n g ，a r t i f i c i a li n t e l l i g e n c e ， m a c h i n el e a r n i n ga n do t h e ra r e a s k e y w 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 na l g o r i t h m , c o l i ca t t r i b u t e s ， r e l a t i o n a ld a t a b a s e s f 一 t 山东大学硕士学位论文 1 1 研究背景 第一章绪论 在当今的信息时代，伴随着互联网技术的不断成熟和应用、推广及普及，人 类获取信息变得越来越容易，生活也变得越来越方便。但是，随着需要面对的信 息量以指数的加速度疯长，当海量的未经处理的原始信息涌现在我们面前时，也 使我们的生活面临“数据灾难”。面对越来越严重的来自数据方面的灾难，人们 不得不采取措施来应付这种局面。通常人们使用两种策略来应付这种情况：一种 是“穷于应付”，另一种是“置之不理”。无怪乎未来学家奈斯比特惊呼：“人 类正被信息淹没，却饥渴于知识 。事实上，无论上述两种处理策略的哪一种， 都是对现实的一种无奈的举措。在需要对海量数据进行详细剖析后才能做出正确 决策的领域( 如经济、政治军事等) ，这是一个普遍存在又迫切需要解决的难题。 表1 1汽车数据库 n o s i z e c y i t u f u e l s y sd i s p l a c e c o m p p o w e rt r a n s w e i g h tm i l e a g e 鬟1 c o m p a c t 6 y e f im e d i u m h i g h h i g h a u t om e d i u m m e d i u m 自 曩站o 。“ ，以e “k t m 。，崩- 自k kt ；0 扎 + e 。a i 寤。 。锄 2 c o m p a c t 6ne f im e d i u mm e d i u m h i g h m a n u a lm e d i u mm e d i u m 蘩”芎”一、b o m p a c t 俐下”胃缈e f i5 穆：m e d i u m 9 ”h i g h 。? h i g h 。m a n u a l 。m e d i u m7 。i n e d i u n i l 4 c o m p a c t 4 y e f im e d i u m h i g hh i g h m a n u a l l i g h th i g h 移o m p a 西。”。矿诳秽7e f i 一。m e d i u m m e d i u m ”：i n e d i u m 。m a n u a l 一m e d i u m ”一i n e d i u m 砀 j 鬣 。一“。， o 也二二缸。0 j h ，。i 。，“k 涩 6 c o m p a c t 6n2 - b b lm e d i u mm e d i u m m e d i u ma u t o h e a v y l o w 彰彳”柳c o m p a c t ”p 9 影“e f i 缈m e d i u m m e d i u m 。h i 蛐v y m a n u a l 一”h e a v y ”彬l 耐灞 蕊4 ，t 州础“咖柚越 & l 。啦缸t 、，女舭缸。硅0 l 。玉罅l 飙 8 s u b c o m p a c t 4n2 - b b l s m a l l h i g h l o w m a n u a l l i g h th i g h 紧旷蝴m p 矗髓甲? 臂管”，2 电b l 粥s m a l l 可h i g h ，1 耐”。妇u a l ”i n e d i u m ”7 葡e d i u m 1 0 c o m p a c t 4n2 - b b ls m a l l h i g h m e d i u ma u t om e d i u mm e d i u m 黟1 1 ”s u b c o m p a 矗8 鬈书? 警弼? i 。e f i ”4 r 9 ；m a n 。8 节“h i g h 4 譬牛。l o w 帮。m a n u a l7 = l i g h t ? 嚣”h i g h 溷 * ”一灿衲。月麓j 一一 ，_ “a 昼一。 一 f ， 1 2 s u b c o m p a c t 4ne f im e d i u mm e d i u mm e d i u mm a n u a lm e d i u m h i g h 髟i 3 一譬c o m p a c t ：”虿f ”2 - b b l ”m e d i u m ”m e d i u m ：m e d i u m 。“m a n u a lm e d i u m 一m e d i u n g 敝。：t 。自- 一：。如k 。蠢= 。越：“ ，_ 靴。础“，。 一。 绸 1 4 s u b c o m p a c t 4 y e f is m a l l h i g hh i g h m a n u a lm e d i u m h i g h 黟l s 。：。 s u b c o m p a c t 矿? 。霹2 - b 藏缈 s m a l l ”h 把d i u 耐碍蹿l o w 嗍m a n u a l “m e d i u m 。鼍h i g h 浔 1 6 c o m p a c t 4 y e f im e d i u mm e d i u m h i g h m a n u a l m e d i u mm e d i u m 眵1 75 ”c o m p a c t 一硼虿哗”+ 胥彬e f e d i u 面m e d i u m h i g h 弼a u t o ：i m e d i u m 一 m e d i u n t k ，。端概。 一 。，i h 矗。盎。n 。二。乩。- ；。罐蛐；，。矗矗酣。盘，。，+ 0 1 8 c o m p a c t 4ne f im e d i u mm e d i u m h i g h a u t om e d i u mm e d i u m 髟7 f 0 。潲毓萄7 ”翟节画鼍”7 e f t 1 孵硒棚”彬h 蛳哪一谥e d i u f i a ”硫a n u a l 。i n i d i u t i i ”一h i # 焉 琵a 犯乩 。矗k 。她。以；j 蹦缸础。翟潼如。二；，傅；唾氟 ；。搿：埘。 一 瓤；翻 2 0 c o m p a c t 4ne f is m a l l h i g h m e d i u mm a n u a lm e d i u m h i g h 匿三：二：兰：! ：竺：二! ：二兰二二兰兰：二：! 竺：坚二! ! 竺二兰：竺：竺：竺竺：竺二竺竺竺竺二兰竺竺氅 山东大学硕士学位论文 为了从直观上展示这种困境，并说明使用本篇文章讲述的方法处理数据后解 决这种困境的整体效果，请看以下一个小例子：表1 1 是一个关系数据库表，它 列出y 2 1 种汽车的一些数据，描述了它们的行驶总里程的评价以及可能影响这个 评价的9 个因素。 假如，我们试图从表1 1 的数据中了解哪些因素对评价总里程数的影响是本 质的，那么面对如此多的数据信息，大多数的使用者都只能采用“穷于应付”的 处理对策，这样的做法极大的消耗了信息获取的时间。如果我们可以使用某些方 法，使数据的形式变成表1 2 所示的形式，并且从数学理论的角度上保证对于评 价总里程这个因素而言，表1 2 和表1 1 的表现能力是等价的。那么，对于关心这 个问题的使用者来说，无疑是一个相当令人相当振奋的消息。 表1 2约简后的规则集合 r u l es i z e f u e l s y sd i s p l s l o ew e i 咖tm i l e a g e 簸：。， ；。：螗“一o 。，。，o ；知，“。；。 ，丘。滋 1 。 +li8hth i 。g h 擎渺”z 喘学蟛7 h p 嘶 i i 一7 - 中簟t ”7 ，? r 伊h e a v y 7 缪咒l o w ：1 酝轨，：o - ， ，一乙如舯如、。山二；础。“互盥赫， 。捌缓 3 s u b c o m p a c t + h i g h 骖? 1 4 。”c o m p a c t ? 一j ：2 - b b l y ；掣二、。”臀：? m e d i u m ? 唧m e d i u m 强 缸怕 晓二，鼎。“二。 。，一。孙? 撇。 ；知o 。z 。，、 t 苷，；“ 二。i 曛缓 从表1 2 中的数据可以看出，获取评价总里程的因素信息已经是相当容易了。 这个变换方法从本质上考虑的是：在大量的数据中，往往存在大量的冗余信息。 如果能在保持对研究结果决策能力不变的前提下，尽可能的约减掉这些冗余的数 据，就可以得到简洁的、易于阅读的数据形式。而这，正是人们所期望的。 面对庞大的数据信息现状，人们急切寻求从数据的汪洋大海中去芜存菁、去 伪存真的方法，而“从数据库中发现知识”( i d ) 及其核心技术数据挖 掘技术便应运而生n 5 3 。数据挖掘主要有两种对数据进行精简的方式，其一是“数 据浓缩”，指将冗余的数据去除掉，其二是属性约简，除掉的是对研究结果没有 影响的属性。本文所讲的属性约简，便是数据挖掘的重要的理论方法。 。1 2 国内外研究现状 从二十世纪八十年代初期，波兰数学家z p a w l a k 提出了粗糙集理论之后，粗 2 山东大学硕士学位论文 集理论就被广泛使用于分析和处理不精确、不一致、不完整等各种不完备的数据 信息，并从中发现隐含的知识、规则，揭示数据中潜在的规律n 们。它能够在缺失 数据的先验知识的情况下，仅通过数据的分类或决策能力对模糊或者不确定的数 据进行分析和处理。一个决策表可能存在无数多个约简，人们期望从中找到具有 最少属性的约简，但这已被证明是一个n p h a r d l h - 题h 】。如果我们退而求其次，找 到一个可以接受的相对最少属性约简，对现实中决策系统研究的影响无疑也是非 常巨大的。本文所讲的属性约简，就是针对获取这种相对最小约简的方法。 目前的属性简约算法的一个最大的共同点就是这些算法基本都是基于主存 的。并且大部分都是通过先使用区分矩阵计算属性核心，然后以属性核心为基础 计算属性约简。但是，基于主存的算法有以下几个致命的缺点：第一，算法所需 的编程工作量非常大，需要研究者有很强的逻辑分析和编程能力，并且实现算法 花费的时间相当长：第二，对这些算法来说，由于主存容量的限制，无法有效处 理大规模和超大规模的数据。因为大规模的数据是无法全部存储在主存中，如果 存储在文件系统中，其后果是无法想象的( 具体可查阅数据存储的发展历程) 。 基于主存算法的这些缺点就严重制约了它们在实际研究中的应用。因此，如何高 效的获取可以接受的最小属性约简吸引了许多研究者的兴趣，也研究出了非常多 的算法和成就，但用于大数据集的实用而高效的属性约简算法仍是目前研究的一 个重要课题。 值得兴庆的是，数据库技术的迅猛发展给属性约简技术提供了另外一条快捷 的途径。首先，数据库技术已经发展了很多年，对数据的存储、查询、维护和正 确性保障方面都有了比较成熟技术，尤其是在存取大规模数据方面有着得天独厚 的优势；其次，现实中的较大规模数据一般都是存储在数据库中而不是文件系统 中，即使是使用纯主存算法也需要从数据库中取数据进行计算。但是由于无法将 全部的数据取入贮存，更增加了算法的存取负担。因此，如何将数据库技术和属 性约简紧密的结合起来，使数据库的优秀技术能为属性约简算法所用，对属性约 简乃至解决当前的“数据炸弹问题有着非常重要的意义。 1 3 研究课题的主要内容 属性约简的应用领域相当广泛，涉及科学和社会的许多领域，包括数据挖掘、 山东大学硕士学位论文 机器学习、知识获取、决策分析、人工智能以及过程控制等。由其作为核心理论 而蓬勃发展的数据挖掘、决策分析等，对我们的政治、军事、经济和生活等各方 面都起着举足轻重的作用。 本文通过对当前经典属性约简算法的研究，并结合当前数据库技术，对算法 进行了改进，极大的提高了算法应对大规模数据库的能力。同时，通过对属性约 简的深入研究，提出了一个针对大规模数据的一个新的高效算法。基于这两个算 法的特点，从数据库存储方面考虑，对数据库的存储内容进行了部分设置，从而 使算法的效率得到进一步的提升。 1 4 本文所做的主要工作 本文首先回顾了属性约简的发展以及在现实问题中所遇到的窘境，然后对属 性约简的基础知识和传统属性约简经典技术进行了阐述。通过对属性约简过程和 这些经典算法的深入分析，针对传统属性约简算法在应对大规模数据风暴中存在 的困难和不足，提出了基于关系数据库技术的属性约简算法，使人们可以更简单 更迅速的获得较小属性约简，同时简化了约简算法逻辑复杂度，更利于算法的研 究、应用和推广。 根据以往的研究可知，属性约简的重点和难点均在于如何有效的获取正区域 和求得属性核心，因为它们是获取属性约减过程的必经之路。从目前通用的属性 约简的算法来看，获取正区域的复杂度直接影响着求取属性约简整个算法的复杂 度。 基于属性约简的特点和难点，本文主要的工作包括如下几个方面： 1 、使用数据库s q l 辅助解决不可区分关系、正区域和属性核心的求取，并 阐明了其正确性和对约简效率的提高。 2 、提出了正区域的补的概念，并通过使用正区域的补来计算正区域，从而 使求取正区域的计算范围缩小，进一步提高正区域的计算效率。 3 、使用数据库技术改进了经典的属性约简算法，提高了算法的效率，增加 了算法的交互性，并使算法更简洁，更具有应对现实窘境的意义。 4 、发现并证明了属性核心在属性约简中的非必要性，并基于此提出了一种 新的高效率的属性约简算法。当然，这种新的算法的很多部分仍然是基于数据库 4 一 山东大学硕士学位论文 技术来进行的。 5 、通过增加数据在数据库中的冗余，即增加属性和建立索引的手段，使改 进的经典算法和新提出的属性约简算法的效率得到进一步的提高。 论文中将对这五个方面的革新点进行详细的阐述。 1 5 本文结构 本文共分为六章，具体内容结构安排如下： 第一章绪论部分：论文通过阐述属性约简的研究背景以及当前国内外的研究 现状，表明了本论文研究的价值和意义。同时，本部分还介绍了本文的主要工作 和总体架构，展示了文章的总体规划。 第二章：介绍了属性约简中的基本概念和常用术语，总结了当前属性约简常 用的经典方法，并对每种方法的优劣进行了简单的剖析和评价，为后续本文的理 论提出作了坚实的基础铺垫。 第三章：使用数据库技术改进当前经典的属性约简算法，解决了属性约简中 三个影响效率的求解点，并使用这三个策略改良了属性约简算法的逻辑，使其更 加缜密和高效。通过实验证明了算法的正确性，并通过和其他算法的实验结果进 行了对比，直观的展示了算法在效率上的改进。 第四章：基于正区域的概念，提出了正区域的补的概念，以减小问题规模； 提出并证明了属性核心在属性约简中的非必要性，并在此基础上提出了新的属性 约简算法。通过实验证明了算法的正确性，并通过和第三章的算法和其他算法的 实验结果进行了对比，直观的展示了算法在效率上的改进。 第五章：为了更进一步的提高三、四章算法的效率，在数据库存储方面增加 了部分冗余信息，包括增加主键和建立索引两个策略。基于属性核心的索引、基 于主键的索引和基于决策属性的索引的应用将会对算法的效率有明显的提高。 第六章：对论文的内容进行了总结，总结了属性约简的现行发展状况，并对 其发展方向做了展望和建议。 目前属性简约算