（計算機軟件與理論專業(yè)論文）基于關(guān)系數(shù)據(jù)庫的屬性約簡研究.pdf

一 i b ， - 原創(chuàng)性聲明和關(guān)于論文使用授權(quán)的說明 原創(chuàng)性聲明 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 本人鄭重聲明：所呈交的學(xué)位論文，是本人在導(dǎo)師的指導(dǎo)下， 獨立進行研究所取得的成果。除文中已經(jīng)注明引用的內(nèi)容外，本 論文不包含任何其他個人或集體已經(jīng)發(fā)表或撰寫過的科研成果。 對本文的研究做出重要貢獻的個人和集體，均已在文中以明確方 式標(biāo)明。本聲明的法律責(zé)任由本人承擔(dān)。 論文作者簽名：蘊二魚免 e l期：絲：生! r 關(guān)于學(xué)位論文使用授權(quán)的聲明 本人完全了解山東大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定，同 意學(xué)校保留或向國家有關(guān)部門或機構(gòu)送交論文的復(fù)印件和電子 版，允許論文被查閱和借閱；本人授權(quán)山東大學(xué)可以將本學(xué)位論 文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進行檢索，可以采用影印、 縮印或其他復(fù)制手段保存論文和匯編本學(xué)位論文。 ( 保密論文在解密后應(yīng)遵守此規(guī)定) 論文作者簽名：托幺2 瑰一導(dǎo)師簽名 - 一i ， 曩 1 7 i ， e j ： 礓 山東大學(xué)碩士學(xué)位論文 目錄 摘要i a b s t r a c t 第一章緒論1 1 1 研究背景l(fā) 1 2 國內(nèi)外研究現(xiàn)狀2 1 3 研究課題的主要內(nèi)容3 1 4 本文所做的主要工作4 1 5 本文結(jié)構(gòu)5 第二章屬性約簡的基礎(chǔ)知識一6 2 1 屬性約簡的相關(guān)知識及術(shù)語介紹一6 2 1 1 數(shù)據(jù)濃縮6 2 1 2 信息系統(tǒng)6 2 1 3 不可區(qū)分關(guān)系7 2 1 4 正區(qū)域7 2 1 5 屬性獨立性7 2 1 6 屬性約簡8 2 2 屬性約簡的基本過程8 2 3 現(xiàn)有經(jīng)典屬性約簡方法分析9 2 3 1r o u g h 集高效算法9 2 3 2 新的可區(qū)分矩陣的約簡方法1 0 2 3 3 基于區(qū)分能力的粗糙集屬性約簡方法1 1 2 3 4 基于信息熵屬性重要度的屬性約簡方法1 1 2 3 5 蟻群優(yōu)化屬性約簡算法1 2 2 3 6 基于遺傳算法的屬性約簡1 3 2 3 7 基于s q l 的粗糙集屬性約簡方法1 4 2 4 本章小結(jié)1 4 第三章基于數(shù)據(jù)庫技術(shù)的經(jīng)典算法改進1 6 山東大學(xué)碩士學(xué)位論文 3 1 本章概述1 6 3 2 屬性約簡的新思路1 6 3 2 1 不可區(qū)分關(guān)系的計算1 7 3 2 2 正區(qū)域的計算1 9 3 2 3 屬性核心的計算2 0 3 3 改進的經(jīng)典屬性約簡算法2 2 3 4 實驗結(jié)果2 3 3 5 小結(jié)2 4 第四章屬性約簡的新算法2 5 4 1 屬性核心計算的改進2 5 4 1 1 屬性核心計算的非必須性2 5 4 1 2 屬性核心計算的非必須性證明2 7 4 2 正區(qū)域的補2 8 4 3 基于正區(qū)域的補的屬性核心計算2 9 4 4 屬性約簡新算法3 0 4 5 實驗結(jié)果3 l 4 6 小結(jié)3 3 第五章基于新算法的數(shù)據(jù)庫策略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 本章小結(jié)3 9 第六章總結(jié)和展望4 l 6 1 總結(jié)4 l 6 2 展望4 2 參考文獻4 3 致謝4 6 - l j 0 一 p ，l 伽 山東大學(xué)碩士學(xué)位論文 攻讀學(xué)位期間發(fā)表的學(xué)術(shù)論文目錄4 7 攻讀學(xué)位期間參與科研項目情況4 8 i i i 山東大學(xué)碩士學(xué)位論文 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 - 山東大學(xué)碩十學(xué)位論文 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 山東大學(xué)碩士學(xué)位論文 摘要 當(dāng)今時代伴隨著網(wǎng)絡(luò)的迅速發(fā)展，信息傳遞方式的增加，越來越多的信息 能夠更迅速的傳遞到人們面前。海量和多元化的信息在給人們生活帶來便利的 同時，也給人們帶來了災(zāi)難“數(shù)據(jù)炸彈 。面對鋪天蓋地蜂擁而至的信息， 另人們苦惱和彷徨，不禁期待找到一種方式來簡化數(shù)據(jù)，只保留中心數(shù)據(jù)供自 己使用。在這種情況下，對數(shù)據(jù)進行挖掘的各種方式就應(yīng)運而生，并在越來越 廣闊的領(lǐng)域獲得應(yīng)用和發(fā)展。 屬性約簡正是這些挖掘方式中的一種很重要的形式，它是在保持?jǐn)?shù)據(jù)分類 或決策能力不變的前提下，對數(shù)據(jù)中的非決策屬性進行約簡，從而獲得人們期 望的與原數(shù)據(jù)具有相同分辨能力但是數(shù)量卻少得多的精簡數(shù)據(jù)。 本文從闡述在信息時代信息約減的作用開始，首先闡述了在信息系統(tǒng)中核 屬性的重要作用以及利用區(qū)分矩陣的方式來求取屬性核心的代價、求取正區(qū)域 的代價等進行了細致的分析，對當(dāng)前經(jīng)典的屬性約簡算法進行了簡介，并運用 r o u g h 集的理論給出了判定一個屬性子集中是否包含屬性核心的充要條件。然 后，根據(jù)這些研究結(jié)論，結(jié)合當(dāng)前大容量的數(shù)據(jù)都是存儲在數(shù)據(jù)庫中的基本現(xiàn) 實，充分利用了數(shù)據(jù)庫技術(shù)在大容量數(shù)據(jù)存儲和查詢的優(yōu)越性，對當(dāng)前的基于 粗糙集的屬性約簡算法進行了改進，并在此基礎(chǔ)上，結(jié)合求取核心屬性的非必 須性和正區(qū)域的補的概念，從一個新的途徑提出了新的屬性約簡算法。 通過對改進的經(jīng)典算法和新提出的屬性約簡算法的實驗結(jié)果的分析表明， 對于較大數(shù)據(jù)集和大數(shù)據(jù)集，兩種算法解決了目前屬性約簡算法應(yīng)對大容量數(shù) 據(jù)的窘境，并且效率遠遠高于現(xiàn)存的一些基于主存的算法。同時算法邏輯簡單， 易于實現(xiàn)和推廣，對于數(shù)據(jù)挖掘、人工智能、機器學(xué)習(xí)等領(lǐng)域具有一定的促進 作用。 關(guān)鍵詞：r o u g h 集，屬性約簡算法，屬性核心，數(shù)據(jù)庫技術(shù) 山東大學(xué)碩士學(xué)位論文 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 山東大學(xué)碩士學(xué)位論文 1 1 研究背景 第一章緒論 在當(dāng)今的信息時代，伴隨著互聯(lián)網(wǎng)技術(shù)的不斷成熟和應(yīng)用、推廣及普及，人 類獲取信息變得越來越容易，生活也變得越來越方便。但是，隨著需要面對的信 息量以指數(shù)的加速度瘋長，當(dāng)海量的未經(jīng)處理的原始信息涌現(xiàn)在我們面前時，也 使我們的生活面臨“數(shù)據(jù)災(zāi)難”。面對越來越嚴(yán)重的來自數(shù)據(jù)方面的災(zāi)難，人們 不得不采取措施來應(yīng)付這種局面。通常人們使用兩種策略來應(yīng)付這種情況：一種 是“窮于應(yīng)付”，另一種是“置之不理”。無怪乎未來學(xué)家奈斯比特驚呼：“人 類正被信息淹沒，卻饑渴于知識 。事實上，無論上述兩種處理策略的哪一種， 都是對現(xiàn)實的一種無奈的舉措。在需要對海量數(shù)據(jù)進行詳細剖析后才能做出正確 決策的領(lǐng)域( 如經(jīng)濟、政治軍事等) ，這是一個普遍存在又迫切需要解決的難題。 表1 1汽車數(shù)據(jù)庫 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 州礎(chǔ)“咖柚越 & 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 節(jié)“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 ?！癿 a n u a lm e d i u m 一m e d i u n g 敝。：t 。自- 一：。如k 。蠢= 。越：“ ，_ 靴。礎(chǔ)“，。 一。 綢 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 ”翟節(jié)畫鼉”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 蹦缸礎(chǔ)。翟潼如。二；，傅；唾氟 ；。?。簤P。 一 瓤；翻 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 匿三：二：蘭：! ：竺：二! ：二蘭二二蘭蘭：二：! 竺：堅二! ! 竺二蘭：竺：竺：竺竺：竺二竺竺竺竺二蘭竺竺氅 山東大學(xué)碩士學(xué)位論文 為了從直觀上展示這種困境，并說明使用本篇文章講述的方法處理數(shù)據(jù)后解 決這種困境的整體效果，請看以下一個小例子：表1 1 是一個關(guān)系數(shù)據(jù)庫表，它 列出y 2 1 種汽車的一些數(shù)據(jù)，描述了它們的行駛總里程的評價以及可能影響這個 評價的9 個因素。 假如，我們試圖從表1 1 的數(shù)據(jù)中了解哪些因素對評價總里程數(shù)的影響是本 質(zhì)的，那么面對如此多的數(shù)據(jù)信息，大多數(shù)的使用者都只能采用“窮于應(yīng)付”的 處理對策，這樣的做法極大的消耗了信息獲取的時間。如果我們可以使用某些方 法，使數(shù)據(jù)的形式變成表1 2 所示的形式，并且從數(shù)學(xué)理論的角度上保證對于評 價總里程這個因素而言，表1 2 和表1 1 的表現(xiàn)能力是等價的。那么，對于關(guān)心這 個問題的使用者來說，無疑是一個相當(dāng)令人相當(dāng)振奮的消息。 表1 2約簡后的規(guī)則集合 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 喘學(xué)蟛7 h p 嘶 i i 一7 - 中簟t ”7 ，? r 伊h e a v y 7 繆咒l o w ：1 醞軌，：o - ， ，一乙如舯如、。山二；礎(chǔ)?！盎ヮ潞?， 。捌緩 3 s u b c o m p a c t + h i g h 驂? 1 4 ?！眂 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 中的數(shù)據(jù)可以看出，獲取評價總里程的因素信息已經(jīng)是相當(dāng)容易了。 這個變換方法從本質(zhì)上考慮的是：在大量的數(shù)據(jù)中，往往存在大量的冗余信息。 如果能在保持對研究結(jié)果決策能力不變的前提下，盡可能的約減掉這些冗余的數(shù) 據(jù)，就可以得到簡潔的、易于閱讀的數(shù)據(jù)形式。而這，正是人們所期望的。 面對龐大的數(shù)據(jù)信息現(xiàn)狀，人們急切尋求從數(shù)據(jù)的汪洋大海中去蕪存菁、去 偽存真的方法，而“從數(shù)據(jù)庫中發(fā)現(xiàn)知識”( i d ) 及其核心技術(shù)數(shù)據(jù)挖 掘技術(shù)便應(yīng)運而生n 5 3 。數(shù)據(jù)挖掘主要有兩種對數(shù)據(jù)進行精簡的方式，其一是“數(shù) 據(jù)濃縮”，指將冗余的數(shù)據(jù)去除掉，其二是屬性約簡，除掉的是對研究結(jié)果沒有 影響的屬性。本文所講的屬性約簡，便是數(shù)據(jù)挖掘的重要的理論方法。 。1 2 國內(nèi)外研究現(xiàn)狀 從二十世紀(jì)八十年代初期，波蘭數(shù)學(xué)家z p a w l a k 提出了粗糙集理論之后，粗 2 山東大學(xué)碩士學(xué)位論文 集理論就被廣泛使用于分析和處理不精確、不一致、不完整等各種不完備的數(shù)據(jù) 信息，并從中發(fā)現(xiàn)隱含的知識、規(guī)則，揭示數(shù)據(jù)中潛在的規(guī)律n 們。它能夠在缺失 數(shù)據(jù)的先驗知識的情況下，僅通過數(shù)據(jù)的分類或決策能力對模糊或者不確定的數(shù) 據(jù)進行分析和處理。一個決策表可能存在無數(shù)多個約簡，人們期望從中找到具有 最少屬性的約簡，但這已被證明是一個n p h a r d l h - 題h 】。如果我們退而求其次，找 到一個可以接受的相對最少屬性約簡，對現(xiàn)實中決策系統(tǒng)研究的影響無疑也是非 常巨大的。本文所講的屬性約簡，就是針對獲取這種相對最小約簡的方法。 目前的屬性簡約算法的一個最大的共同點就是這些算法基本都是基于主存 的。并且大部分都是通過先使用區(qū)分矩陣計算屬性核心，然后以屬性核心為基礎(chǔ) 計算屬性約簡。但是，基于主存的算法有以下幾個致命的缺點：第一，算法所需 的編程工作量非常大，需要研究者有很強的邏輯分析和編程能力，并且實現(xiàn)算法 花費的時間相當(dāng)長：第二，對這些算法來說，由于主存容量的限制，無法有效處 理大規(guī)模和超大規(guī)模的數(shù)據(jù)。因為大規(guī)模的數(shù)據(jù)是無法全部存儲在主存中，如果 存儲在文件系統(tǒng)中，其后果是無法想象的( 具體可查閱數(shù)據(jù)存儲的發(fā)展歷程) 。 基于主存算法的這些缺點就嚴(yán)重制約了它們在實際研究中的應(yīng)用。因此，如何高 效的獲取可以接受的最小屬性約簡吸引了許多研究者的興趣，也研究出了非常多 的算法和成就，但用于大數(shù)據(jù)集的實用而高效的屬性約簡算法仍是目前研究的一 個重要課題。 值得興慶的是，數(shù)據(jù)庫技術(shù)的迅猛發(fā)展給屬性約簡技術(shù)提供了另外一條快捷 的途徑。首先，數(shù)據(jù)庫技術(shù)已經(jīng)發(fā)展了很多年，對數(shù)據(jù)的存儲、查詢、維護和正 確性保障方面都有了比較成熟技術(shù)，尤其是在存取大規(guī)模數(shù)據(jù)方面有著得天獨厚 的優(yōu)勢；其次，現(xiàn)實中的較大規(guī)模數(shù)據(jù)一般都是存儲在數(shù)據(jù)庫中而不是文件系統(tǒng) 中，即使是使用純主存算法也需要從數(shù)據(jù)庫中取數(shù)據(jù)進行計算。但是由于無法將 全部的數(shù)據(jù)取入貯存，更增加了算法的存取負擔(dān)。因此，如何將數(shù)據(jù)庫技術(shù)和屬 性約簡緊密的結(jié)合起來，使數(shù)據(jù)庫的優(yōu)秀技術(shù)能為屬性約簡算法所用，對屬性約 簡乃至解決當(dāng)前的“數(shù)據(jù)炸彈問題有著非常重要的意義。 1 3 研究課題的主要內(nèi)容 屬性約簡的應(yīng)用領(lǐng)域相當(dāng)廣泛，涉及科學(xué)和社會的許多領(lǐng)域，包括數(shù)據(jù)挖掘、 山東大學(xué)碩士學(xué)位論文 機器學(xué)習(xí)、知識獲取、決策分析、人工智能以及過程控制等。由其作為核心理論 而蓬勃發(fā)展的數(shù)據(jù)挖掘、決策分析等，對我們的政治、軍事、經(jīng)濟和生活等各方 面都起著舉足輕重的作用。 本文通過對當(dāng)前經(jīng)典屬性約簡算法的研究，并結(jié)合當(dāng)前數(shù)據(jù)庫技術(shù)，對算法 進行了改進，極大的提高了算法應(yīng)對大規(guī)模數(shù)據(jù)庫的能力。同時，通過對屬性約 簡的深入研究，提出了一個針對大規(guī)模數(shù)據(jù)的一個新的高效算法?；谶@兩個算 法的特點，從數(shù)據(jù)庫存儲方面考慮，對數(shù)據(jù)庫的存儲內(nèi)容進行了部分設(shè)置，從而 使算法的效率得到進一步的提升。 1 4 本文所做的主要工作 本文首先回顧了屬性約簡的發(fā)展以及在現(xiàn)實問題中所遇到的窘境，然后對屬 性約簡的基礎(chǔ)知識和傳統(tǒng)屬性約簡經(jīng)典技術(shù)進行了闡述。通過對屬性約簡過程和 這些經(jīng)典算法的深入分析，針對傳統(tǒng)屬性約簡算法在應(yīng)對大規(guī)模數(shù)據(jù)風(fēng)暴中存在 的困難和不足，提出了基于關(guān)系數(shù)據(jù)庫技術(shù)的屬性約簡算法，使人們可以更簡單 更迅速的獲得較小屬性約簡，同時簡化了約簡算法邏輯復(fù)雜度，更利于算法的研 究、應(yīng)用和推廣。 根據(jù)以往的研究可知，屬性約簡的重點和難點均在于如何有效的獲取正區(qū)域 和求得屬性核心，因為它們是獲取屬性約減過程的必經(jīng)之路。從目前通用的屬性 約簡的算法來看，獲取正區(qū)域的復(fù)雜度直接影響著求取屬性約簡整個算法的復(fù)雜 度。 基于屬性約簡的特點和難點，本文主要的工作包括如下幾個方面： 1 、使用數(shù)據(jù)庫s q l 輔助解決不可區(qū)分關(guān)系、正區(qū)域和屬性核心的求取，并 闡明了其正確性和對約簡效率的提高。 2 、提出了正區(qū)域的補的概念，并通過使用正區(qū)域的補來計算正區(qū)域，從而 使求取正區(qū)域的計算范圍縮小，進一步提高正區(qū)域的計算效率。 3 、使用數(shù)據(jù)庫技術(shù)改進了經(jīng)典的屬性約簡算法，提高了算法的效率，增加 了算法的交互性，并使算法更簡潔，更具有應(yīng)對現(xiàn)實窘境的意義。 4 、發(fā)現(xiàn)并證明了屬性核心在屬性約簡中的非必要性，并基于此提出了一種 新的高效率的屬性約簡算法。當(dāng)然，這種新的算法的很多部分仍然是基于數(shù)據(jù)庫 4 一 山東大學(xué)碩士學(xué)位論文 技術(shù)來進行的。 5 、通過增加數(shù)據(jù)在數(shù)據(jù)庫中的冗余，即增加屬性和建立索引的手段，使改 進的經(jīng)典算法和新提出的屬性約簡算法的效率得到進一步的提高。 論文中將對這五個方面的革新點進行詳細的闡述。 1 5 本文結(jié)構(gòu) 本文共分為六章，具體內(nèi)容結(jié)構(gòu)安排如下： 第一章緒論部分：論文通過闡述屬性約簡的研究背景以及當(dāng)前國內(nèi)外的研究 現(xiàn)狀，表明了本論文研究的價值和意義。同時，本部分還介紹了本文的主要工作 和總體架構(gòu)，展示了文章的總體規(guī)劃。 第二章：介紹了屬性約簡中的基本概念和常用術(shù)語，總結(jié)了當(dāng)前屬性約簡常 用的經(jīng)典方法，并對每種方法的優(yōu)劣進行了簡單的剖析和評價，為后續(xù)本文的理 論提出作了堅實的基礎(chǔ)鋪墊。 第三章：使用數(shù)據(jù)庫技術(shù)改進當(dāng)前經(jīng)典的屬性約簡算法，解決了屬性約簡中 三個影響效率的求解點，并使用這三個策略改良了屬性約簡算法的邏輯，使其更 加縝密和高效。通過實驗證明了算法的正確性，并通過和其他算法的實驗結(jié)果進 行了對比，直觀的展示了算法在效率上的改進。 第四章：基于正區(qū)域的概念，提出了正區(qū)域的補的概念，以減小問題規(guī)模； 提出并證明了屬性核心在屬性約簡中的非必要性，并在此基礎(chǔ)上提出了新的屬性 約簡算法。通過實驗證明了算法的正確性，并通過和第三章的算法和其他算法的 實驗結(jié)果進行了對比，直觀的展示了算法在效率上的改進。 第五章：為了更進一步的提高三、四章算法的效率，在數(shù)據(jù)庫存儲方面增加 了部分冗余信息，包括增加主鍵和建立索引兩個策略?；趯傩院诵牡乃饕?、基 于主鍵的索引和基于決策屬性的索引的應(yīng)用將會對算法的效率有明顯的提高。 第六章：對論文的內(nèi)容進行了總結(jié)，總結(jié)了屬性約簡的現(xiàn)行發(fā)展?fàn)顩r，并對 其發(fā)展方向做了展望和建議。 目前屬性簡約算