基于粗糙集的屬性值約簡算法研究

1、141科技資訊 科技資訊SCIENCE&TECHNOLOGYINFORMATION 2007NO.34學(xué)術(shù)論壇1引言粗糙集(Roughset 1理論是一種處理模 糊和不確定信息的新型數(shù)據(jù)分析工具,目前已 成為信息科學(xué)最活躍的研究領(lǐng)域之一。基于 粗糙集的屬性值約簡是利用決策邏輯消去決 策算法中每條決策規(guī)則的不必要條件。它是 針對每條決策規(guī)則, 去掉表達該規(guī)則的冗余 值,以便進一步使決策算法最小化。屬性值約簡與屬性約簡的原理都是刪除 冗余信息過程,采用的手段都是通過求得核(核 值、 約簡(約簡值得到的。 將粗糙集理論應(yīng)用 到數(shù)據(jù)挖掘技術(shù)上,利用粗糙集的知識約簡, 精簡數(shù)據(jù)挖掘出的各類規(guī)則,

2、對復(fù)雜系統(tǒng)的策 略研究具有廣泛的意義。本文應(yīng)用粗糙集理論,分析基于粗糙集的 常用屬性值約簡算法和相應(yīng)的算法的復(fù)雜度, 并結(jié)合一種新約簡算法實例分析研究,說明這 一算法的有效性。2傳統(tǒng)的屬性值約簡算法定義 1 信息系統(tǒng) S=(U,A,V,F 是一個 決策表, 其中 U 為非空有限集合, 稱為全域。 全域 U 的元素被稱為對象或者實例; A =C D,C 為條件屬性集,即對象的特征;D=d為 決策屬性集, 稱為對象的分類, C D =; V 是屬性值的集合。設(shè) a 是任一屬性,x i 是任一 個對象,則 f(x i ,a表示x i 在 a屬性的取值。 信 息系統(tǒng)可簡化表示為 S=(U,A。屬性值約

3、簡的思想是:決策表中每一行代 表一條決策規(guī)則,即計算每一條決策規(guī)則的條 件屬性的核值?？梢圆捎孟葘⒃撔兄幸粋€條 件屬性的值從表中刪去,然后檢查剩下的該行 中條件屬性值是否可以唯一確定此行中的決 策屬性,若果不是,那么刪去的條件屬性值就 是該行決策規(guī)則的核值。在求出所有的決策 規(guī)則的核值后的基礎(chǔ)上,通過添加一些條件屬性值到核值中,并保證每個條件屬性是不可省 的 。常用的屬性值約簡算法有數(shù)據(jù)分析法和 區(qū) 分 矩 陣 法 。 2.1數(shù)據(jù)分析法其基本思想:在信息系統(tǒng)的決策表中,逐 一將屬性集 A 中的屬性刪除,每刪除一個屬性 就檢查決策表。如果沒有出現(xiàn)新的不一致,則 刪除該屬性,否則該屬性不能被刪除。

4、若決策 表可以表示成 R 1 d 1,R 2 d 2,當 d 1 d 2時 有 R 1 R 2,那么決策表就是一致的,如果存在 d 1 d 2而 R 1=R 2,那么決策表就是不一致的。 每次刪除測試是否還保持原決策表的一致性 可以轉(zhuǎn)化為檢查正區(qū)域是否被改變。計算正區(qū)域的時間復(fù)雜度為O(|A|U|Log |U|,共有|A|次計算正區(qū)域,所以算法復(fù)雜度 就是O(|A|2|U|Log|U|。 |A|為屬性數(shù),|U|為對 象數(shù)。基于粗糙集的屬性值約簡算法研究 趙慧娟駱解民(上海水產(chǎn)大學(xué)信息學(xué)院上海200090摘 要:規(guī)則提取是數(shù)據(jù)挖掘的核心步驟, 在分析常用屬性值約簡算法思想的基礎(chǔ)上, 給出基于不可

5、分辨矩陣的屬性值約簡算法描述。實 驗結(jié)果表明, 這種方法是可行的。關(guān)鍵詞:數(shù)據(jù)挖掘粗糙集屬性值約簡 中圖分類號:G 64文獻標識碼:A 文章編號:1672-3791(200712(a-0141-02的結(jié)構(gòu)和機能達到一定的發(fā)達程度,同時要善 于充分發(fā)揮大腦的機能。 根據(jù)大腦半球不對稱原理, 左腦是理性、 知識的腦,通過分析思維和集中思維來進行智 力開發(fā),而右腦則是感知、創(chuàng)造的腦,通過想 象力、直覺思維、擴散思維來進行創(chuàng)造力開 發(fā)。通過對發(fā)明發(fā)現(xiàn)過程的研究分析, 創(chuàng)造 學(xué)家們普遍認為, 由右腦所獲得的形象、直 覺、對整體的感知等是人們進行創(chuàng)造性活動 的源泉, 也是創(chuàng)造性地解決問題的關(guān)鍵?？?學(xué)史上

6、大量事例可以佐證這一成果。但是, 進行創(chuàng)造性活動不僅需要充分開發(fā)利用右腦 的功能,也需要積極調(diào)動左腦的功能,只有兩 者有效地相互配合激發(fā),才能有效地實現(xiàn)創(chuàng)造 性活動, 得到創(chuàng)造性活動的產(chǎn)品。 2.2創(chuàng)造性思維的實現(xiàn) 從以上對創(chuàng)造性活動微觀機制的討論中, 可以看到要實現(xiàn)創(chuàng)造性思維,關(guān)鍵在于如何把 人的創(chuàng)造能量由基態(tài)轉(zhuǎn)到激發(fā)態(tài),以及如何誘 導(dǎo)人的創(chuàng)造性活動由低級向高級發(fā)展。 2.2.1 創(chuàng)造性思維的激發(fā) 創(chuàng)造性思維的激發(fā)可分為外部激發(fā)和內(nèi) 部激發(fā)兩種,外部激發(fā)又可分為直接和間接之 分。譬如討論交流激發(fā)了創(chuàng)造性思維就是一 種外部直接的激發(fā)。而解除了阻礙激發(fā)創(chuàng)造 性思維的不良的外在條件,也是一種外部間

7、接 的激發(fā)。如果由于依靠自身的能動性激發(fā)了 創(chuàng)造性思維則認為是一種內(nèi)部的激發(fā)。 卓越的科學(xué)家愛因斯坦在談及自己的創(chuàng) 造活動時總是說,我不過是抱著孩子般的好奇 心去接觸問題而已。這就說明好奇心將會激 發(fā)創(chuàng)造性思維,因為強烈的好奇心將在體內(nèi)產(chǎn) 生強大的“內(nèi)驅(qū)力” , 這“內(nèi)驅(qū)力”激發(fā)了 創(chuàng)造因子,破壞了原來的創(chuàng)造體的穩(wěn)定結(jié)構(gòu), 使得創(chuàng)造因子高速運動和大量碰撞,并同時又 可能打碎創(chuàng)造核而釋放其固有能量,大大提高 了非穩(wěn)態(tài)的創(chuàng)造體的重組效率,形成了高值的 創(chuàng)造能, 導(dǎo)致了創(chuàng)造性思維的實現(xiàn)。 許多事例向我們表明,處于逆境之中,或 處于不令人滿意的狀態(tài)中,或在面臨著困難和 難題的時候, 往往會激發(fā)一個人的

8、創(chuàng)造性思 維。因為處于這種狀態(tài)的個人由于感受到一 種心理上的壓迫,而為了消除或擺脫,反抗或 解決就產(chǎn)生一種 “作用力” ,這種 “作用力” 達 到了一定的“閥值” ,就猶如前述的“內(nèi)驅(qū)力” 一樣,會激發(fā)創(chuàng)造因子,產(chǎn)生創(chuàng)造性思維。并 且,這個時候,堅強的意志對創(chuàng)造性思維的產(chǎn) 生也起著異常重要的作用。 古希臘哲學(xué)和邏輯學(xué)家蘇格拉底曾指出, 可以通過提出問題來激發(fā)創(chuàng)造性思維。因為 每個人都或強或弱具有一種要求解決問題而 “自我實現(xiàn)”的欲望, 這一欲望, 就會因為提 出了問題而又為了解決問題而產(chǎn)生一種“原 動力” , 這一原動力正如“內(nèi)驅(qū)力”那樣會 激勵創(chuàng)造能, 導(dǎo)致創(chuàng)造性思維的實現(xiàn)。 2.2.2 影

9、響創(chuàng)造性思維的諸因素 一個人的個性品質(zhì)、心理素質(zhì)、能力高 低和環(huán)境氣氛等都對創(chuàng)造性思維的產(chǎn)生或多 或少有著重要的影響。托蘭斯總結(jié)了許多研 究成果,曾列出 84項可導(dǎo)致產(chǎn)生創(chuàng)造性思維 的人格特征,其中最主要的前九項是:容忍 無秩序;甘愿冒險;勇于承擔過于困難的工作;渴望優(yōu)越;不滿、發(fā)現(xiàn)缺陷;有情緒 感受性; 不怕被人看作為“怪人” ; 好奇心強; 喜歡孤獨。同時一個人的自信心、 自尊心的大小, 思想觀念的靈活性、意志的 強弱、是否勇敢、大膽和不迷信權(quán)威, 是否 善于懷疑、具有批判精神都對創(chuàng)造性思維的 產(chǎn)生有著很重要的影響。 此外一個人的想象能力、堅持能力、自 制能力、表達能力、 質(zhì)疑能力、 洞察

10、能力、 交 際能力、 以及超越束縛的能力、 擺脫習(xí)慣的能 力、 普遍聯(lián)系的能力、 發(fā)現(xiàn)問題的能力等等對 創(chuàng)造性思維的產(chǎn)生有著決定性的作用。 3結(jié)語 創(chuàng)造性思維是一種非常重要的思維方式, 是對人們原有的思維方式和內(nèi)容的超越。要學(xué)會和掌握創(chuàng)造性思維方式,人們必須自覺地 培養(yǎng)和訓(xùn)練,才能逐步具備良好的思維功底和 思維品質(zhì)、積累豐富的知識經(jīng)驗和智慧,才能 “厚積薄發(fā)” 、 獲得靈感、 實現(xiàn)思維的飛躍、 產(chǎn)生新觀點和新辦法, 從而創(chuàng)造出新成果。 參考文獻 1 王玉琳,王諍諍.創(chuàng)造性思維的系統(tǒng)分析J. 系統(tǒng)辯證學(xué)報,2002,10(3:13-16. 2 柴建芳.創(chuàng)造性思維系統(tǒng)特征初探J.山西 高等學(xué)校社會

11、科學(xué)學(xué)報,2007,19(1:13-18.3程名,周昌樂.創(chuàng)造性思維計算模型研究綜 述J.心理科學(xué),2007,30(1:136-138. 上海水產(chǎn)大學(xué)青年科研基金(6690606093142科技資訊 科技資訊SCIENCE&TECHNOLOGYINFORMATION2007NO.34SCIENCE&TECHNOLOGYINFORMATION學(xué)術(shù)論壇表1汽車駕駛安全表表 2約簡C 2,C 3規(guī)則表示2.2區(qū)分矩陣法定義2區(qū)分矩陣是一個對稱|U|×|U|矩 陣,矩陣的每一項 Cij 定義為:使 用 區(qū) 分 矩 陣 的 屬 性 值 約 簡 算 法 有 Z1ark0和 Sha

12、n 的屬性值約簡算法 1。基本思想:首先構(gòu)造區(qū)分矩陣,該矩陣用 來分辨不同分類值下條件屬性取值間的差 異。針對每一個決策屬性值 V d , 將決策表中 的記錄分為兩部分,一個是屬于 V d 的,另外一 部分是不屬于 V d 的, 通過比較這兩部分記錄 集間條件屬性取值的不同,構(gòu)造出區(qū)分矩陣。 在該矩陣的基礎(chǔ)上求出區(qū)分函數(shù),然后應(yīng)用吸 收律化簡區(qū)分函數(shù),得到析取范式,則每個主 蘊含式均為規(guī)則約簡。計算區(qū)分矩陣的代價是O(|A|U|2,合并和 排序區(qū)分矩陣的時間復(fù)雜度為 O(2|U|2|Log |U|;遍歷區(qū)分矩陣并生成約簡的時間復(fù)雜度 是O(|A|U|2。 整個算法的時間復(fù)雜度的上限 是O(2(

13、|A|+Log|U|U|2。通過以上分析,可以發(fā)現(xiàn),如果條件屬性 的個數(shù)較大, 測試屬性組合的代價是比較大 的, 需要一種相對高效的屬性值約簡算法。3基于不可分辨矩陣的屬性值約簡算法3.1算法的基本思想對每個條件屬性進行等價類劃分,如果一 個等價內(nèi)的多個實例都在一個分類屬性的等 價類里,那么就可以由該條件屬性值確定地推 導(dǎo)出此分類屬性。 3.2不可分辨矩陣定義 3決策系統(tǒng) S的不可分辨矩陣定義如其中 ind(a i 表示條件屬性 a 等價類的個 數(shù),a i,j 表示條件屬性 a i 的第 j 個等價類。規(guī)則的屬性值約簡,要同時考慮條件屬性 值的等價類和條件屬性值的等價類是否在一 個分類屬性值所

14、在的等價類中,所以需要將條 件屬性不可分辨矩陣 Ea i,j 按照分類屬性值的 不同區(qū)別開來。 3.2算法Input:信息系統(tǒng)S(U,A d,其中A = ai,i=1,nOutput;化簡后的規(guī)則集 R Procedure:1.R 置為空集2.計算S中所有屬性的等價類和不可分 辨矩陣E3.對E中每個 e 的元素根據(jù)等價類進行 分類4.WHILE(E不為空集 5.對于E中的每個 e 6. B E G I N 7.if(e值為1 8. E =E -e 9. R =R +e10.if(U為空集break 11.else12. U =U -e 的規(guī)則號13.ENDIF 14. E N D15.對R進行

15、同分類屬性值的合并 16.IF(E不為空集17.E=非同一條件屬性項 18. E N D W H I L E 19. R E T U R N R計算等價類的代價與計算區(qū)分矩陣的代 價都在O(|A|U|2|內(nèi),計算不可區(qū)分矩陣的代價 為O(|A|U|2|內(nèi)。 最壞情況下,每個屬性的不 可區(qū)分矩陣有|U|項,分類屬性等價類也是|U|項,那么對等價類按照分類屬性值進行整理最 壞程度就是 O(|A|U|2|。最壞情況下每一條 規(guī)則的條件屬性值都不能省,while 就要循環(huán) 屬性個數(shù)|A|次,內(nèi)部E的大小最多為|U|,所以 代價為O(|A|U|。 總的屬性值約簡的代價為O(|A|U|2+O(|A|U|2

16、+O(|A|U|,即O(|A|U|2。 明顯小于區(qū)分矩陣的屬性值約簡算法的 O (2(|A|+LogU|U|2。 3.3實驗表1是一個約簡后的關(guān)于汽車駕駛安全 的信息系統(tǒng),其中 U =1,2,8,條件屬性 集為 C =是否會駕駛, 飲酒程度, 是否出車 禍,決策屬性為 D =是否出車禍.以上面的數(shù)據(jù)集為例, 分析規(guī)則提取過 程。假設(shè)該數(shù)據(jù)集含有 8個記錄,屬性數(shù)為 4, 其中第一個屬性是記錄編號,因此可以刪除。 第 4個屬性是決策屬性, 有效條件屬性為 2個。根據(jù)不可區(qū)分矩陣啟發(fā)式屬性約簡算 法,對約簡C2,C3進行規(guī)則提取,得到的規(guī) 則有 5條,如表 2所示?？梢则炞C,表 2中所 有的規(guī)則都

17、是正確的?？梢钥吹?從約簡中得到的規(guī)則,經(jīng)過屬 性值約簡算法,可以用更為簡潔的規(guī)則形式表 達, 且簡單表達形式能完全代表約簡中的規(guī)則。假如在約簡集的基礎(chǔ)上再增加一個冗余 屬 r,因為冗余屬性 r 的存在,可能會產(chǎn)生一個 簡化規(guī)則與這個冗余屬性 r 有關(guān),那么就把約 簡中的一部分規(guī)則歸入到冗余屬性r的簡化規(guī) 則中,從而影響真正約簡屬性的規(guī)則形式和規(guī) 則數(shù)目,所以簡化規(guī)則的個數(shù)和形式是要發(fā)生 改 變 的 。4結(jié)語基于粗糙集的數(shù)據(jù)挖掘方法的顯著的特 點之一就是它具有顯式的知識表達形式,屬性 值約簡是基于粗糙集理論的規(guī)則泛化步驟之 一。屬性值約簡一般是在屬性約簡的基礎(chǔ)上 進行的。在分析常用屬性值約簡算法思想的 基礎(chǔ)上,給出基于不可分辨矩陣的屬性值約簡 算法。該算法能夠抽取出最簡單的規(guī)則。經(jīng) 過實驗分析, 該方法是可行的。參考文獻1PawlakZ.RoughsettheoryanditsapplicationstodataanalysisJ.Cyber-