基于粗糙集的數(shù)據(jù)挖掘改進(jìn)屬性約簡算法研究

盧秀蕓

(江蘇聯(lián)合職業(yè)技術(shù)學(xué)院鎮(zhèn)江分院 信息工程系，江蘇，鎮(zhèn)江 212016)

基于粗糙集的數(shù)據(jù)挖掘改進(jìn)屬性約簡算法研究

盧秀蕓

(江蘇聯(lián)合職業(yè)技術(shù)學(xué)院鎮(zhèn)江分院 信息工程系，江蘇，鎮(zhèn)江 212016)

研究基于粗糙集的屬性約簡算法在數(shù)據(jù)挖掘規(guī)則提取階段的應(yīng)用。數(shù)據(jù)挖掘中對屬性進(jìn)行約簡時(shí)，經(jīng)常采用粗糙集，再按照規(guī)則進(jìn)行提取?？疾觳顒e矩陣的定義和信息系統(tǒng)比較復(fù)雜且核屬性元素所占比例較少的情況，改進(jìn)基于差別矩陣的屬性約簡算法，利用差別矩陣的結(jié)構(gòu)建立一種新的選擇屬性的依據(jù)。

粗糙集；數(shù)據(jù)挖掘；屬性約簡；改進(jìn)

數(shù)據(jù)挖掘是發(fā)現(xiàn)知識的核心步驟，主要作用是發(fā)現(xiàn)大量數(shù)據(jù)中的隱藏模式[1]。粗糙集理論是1982年由波蘭科學(xué)家提出的一種新型的處理不確定和模糊知識的數(shù)學(xué)工具，其主要優(yōu)點(diǎn)是提取知識時(shí)不靠人為的假設(shè)，全部由數(shù)據(jù)驅(qū)動(dòng)。它使用數(shù)據(jù)本身的內(nèi)部知識，在確定已經(jīng)給定的問題近似域時(shí)，主要通過不可分辨類以及不可分辨的關(guān)系自動(dòng)得到問題的內(nèi)在規(guī)律。

1 粗糙集

粗糙集一般用于處理具有不確定性的知識和模糊知識。研究粗糙集，重點(diǎn)是在保持知識庫分類能力的條件下，對知識庫中的知識屬性進(jìn)行約簡，推導(dǎo)需要研究知識的決策規(guī)則[2]。

設(shè)信息系統(tǒng)IS=(U,A,V,f)，令R?A，若滿足：

1)H(R)=H(A)，

2)a∈R，H(a|R-a)>0，則稱R是IS的約簡[3-4]。知識的約簡并不是唯一的?，F(xiàn)在對具有不確定性知識進(jìn)行處理的理論非常多。相對而言，粗糙集理論所依靠的僅僅是問題所提供的數(shù)據(jù)集合，不需要其他的先驗(yàn)知識,同時(shí)，還能和其他理論如模糊學(xué)和證據(jù)理論、概率與數(shù)理統(tǒng)計(jì)理論等互補(bǔ)。它在數(shù)據(jù)挖掘、決策分析、模式的分類和識別、人工智能等方面都有較成功的應(yīng)用。

2 數(shù)據(jù)挖掘

2.1數(shù)據(jù)挖掘的概念

數(shù)據(jù)挖掘是將隱藏在大型信息系統(tǒng)或知識庫中對人們的生活和工作具有一定潛在應(yīng)用價(jià)值的知識信息提取的過程。圖1顯示了數(shù)據(jù)庫知識發(fā)現(xiàn)的較完整的過程。

圖1 數(shù)據(jù)庫知識發(fā)現(xiàn)的過程

從圖1可以看出，數(shù)據(jù)庫通過數(shù)據(jù)的清洗和集成之后得到數(shù)據(jù)倉庫。其主要工作是得到比較一致和完整的數(shù)據(jù)，去除數(shù)據(jù)庫中的噪聲數(shù)據(jù)及與挖掘主題無關(guān)的數(shù)據(jù)，利用統(tǒng)計(jì)學(xué)方法修補(bǔ)數(shù)據(jù)庫中丟失的數(shù)據(jù)，同時(shí)把相關(guān)聯(lián)的數(shù)據(jù)源組合在一起形成數(shù)據(jù)倉庫。形成數(shù)據(jù)倉庫之后，需要了解相關(guān)的背景知識和用戶需求，提取與當(dāng)前知識發(fā)現(xiàn)相關(guān)的數(shù)據(jù)，并根據(jù)發(fā)現(xiàn)任務(wù)對數(shù)據(jù)的格式進(jìn)行轉(zhuǎn)化[5]。數(shù)據(jù)挖掘是通過一定的算法搜索某種模式或知識，并通過可視化的技術(shù)提供給用戶。

數(shù)據(jù)挖掘的主要任務(wù)是提取和分析存儲在知識庫中的業(yè)務(wù)知識，挖掘隱含在知識庫中對人們正確決策起到一定輔助作用的信息，通過容易理解的方式反饋給用戶。具有代表性又較成熟的數(shù)據(jù)挖掘技術(shù)主要有神經(jīng)元網(wǎng)絡(luò)技術(shù)、遺傳算法、統(tǒng)計(jì)分析方法、模糊集方法、粗糙集方法等[6]。

2.2數(shù)據(jù)挖掘的過程

數(shù)據(jù)挖掘主要是分析和查詢現(xiàn)場數(shù)據(jù)庫或信息系統(tǒng)中的數(shù)據(jù)，找出這些數(shù)據(jù)之間的聯(lián)系，輔助人們做出正確的決策規(guī)則。數(shù)據(jù)挖掘的過程主要包括數(shù)據(jù)處理、模型搜索、結(jié)果評估、輸出最終結(jié)果、對最終結(jié)果進(jìn)行解釋等。

2.3基于粗糙集的數(shù)據(jù)挖掘模型

粗糙集在處理知識時(shí)具有一些獨(dú)特的特征，已經(jīng)成為數(shù)據(jù)挖掘技術(shù)中重要的基礎(chǔ)理論之一。基于粗糙集的算法采用的信息表與關(guān)系數(shù)據(jù)庫用來表達(dá)知識關(guān)系的數(shù)據(jù)模型相似，能夠很容易地嵌入關(guān)系數(shù)據(jù)庫的數(shù)據(jù)處理過程，而且采用粗糙集算法的知識簡練，易于人們存儲和理解。基于粗糙集理論的數(shù)據(jù)挖掘是指在處理對象決策表的數(shù)據(jù)時(shí)，通過粗糙集的屬性約簡算法對決策表中的知識進(jìn)行約簡，最終得到一定的規(guī)則[7]。

3 屬性約簡算法的改進(jìn)研究

3.1改進(jìn)算法的提出

基于差別矩陣的屬性約簡算法主要采用差別矩陣巧妙提出信息系統(tǒng)核的計(jì)算方法。但采用這種信息系統(tǒng)，要得到所有屬性的約簡，需要對信息系統(tǒng)條件屬性集冪集中的元素進(jìn)行依次遍歷?；诓顒e函數(shù)的屬性約簡算法主要是在差別矩陣的算法基礎(chǔ)上引入邏輯運(yùn)算。這種算法需要先把差別矩陣中的每一個(gè)非空元素項(xiàng)轉(zhuǎn)化為相應(yīng)的析取式，再把全部析取式進(jìn)行合取，得到一個(gè)具有多項(xiàng)的內(nèi)析取外合取的范式，并通過一定的邏輯運(yùn)算將內(nèi)析取外合取的范式轉(zhuǎn)換為內(nèi)合取外析取范式[2]。這樣，最終得到的范式合取項(xiàng)就是當(dāng)前條件下屬性集合的約簡集。隨后的基于差別函數(shù)的改進(jìn)屬性約簡算法主要是對原始的屬性約簡算法進(jìn)行一定的優(yōu)化，其中主要的優(yōu)化是在原始的基于差別函數(shù)的屬性約簡算法建立起范式之前增加1個(gè)操作步驟，即置空所有包含有核的元素項(xiàng)，在一定程度上減少邏輯運(yùn)算的規(guī)模，提高算法的效率。如果需要處理的信息系統(tǒng)比較復(fù)雜，而且系統(tǒng)當(dāng)中核屬性的元素所占比例非常小時(shí)，那么基于差別函數(shù)以及基于差別矩陣的屬性約簡算法效率就非常低，需要利用差別矩陣建立一種效率高的算法[5]。本文主要是利用差別矩陣的結(jié)構(gòu)建立一種新的選擇屬性的依據(jù)。在信息系統(tǒng)的差別矩陣中，元素項(xiàng)主要用來區(qū)別兩個(gè)相應(yīng)對象的條件屬性。在差別矩陣中，某種條件屬性出現(xiàn)的次數(shù)較多，說明這個(gè)條件屬性能區(qū)分的對象個(gè)數(shù)較多，反之，說明這個(gè)條件屬性能區(qū)分的對象個(gè)數(shù)較少，對于整個(gè)論域的分類能力影響較?。蝗绻骋环N屬性沒有出現(xiàn)過，說明這種屬性不能用來區(qū)分任何對象，是冗余的，可以直接刪除?？梢园巡顒e矩陣中某種屬性出現(xiàn)的頻率看成啟發(fā)式信息，提出一種基于差別矩陣和屬性選擇的屬性約簡算法[8]。

3.2改進(jìn)屬性約簡算法的分析

約簡算法的流程圖如圖2所示。

圖2 約簡算法流程圖

如一信息系統(tǒng)IS=(U,A,V,f)，其差別矩陣如圖3所示。其中U有7個(gè)對象，如圖4所示。

圖3 差別矩陣

圖4信息系統(tǒng)

根據(jù)相應(yīng)的定義、法則，可以求出修改后的差別矩陣，如圖5所示。

圖5 修改后的差別矩陣

這種屬性約簡的算法是一種基于差別矩陣以及新的屬性選擇的算法，具有以下優(yōu)點(diǎn)：

1) 屬性約簡更加明確。這種算法主要以屬性在差別矩陣中出現(xiàn)的次數(shù)作為啟發(fā)式的信號，同時(shí)以屬性所在差別矩陣中的元素長短作為加權(quán)系數(shù)，能夠有效避免當(dāng)出現(xiàn)兩個(gè)或兩個(gè)以上屬性在差別矩陣中出現(xiàn)次數(shù)一樣時(shí)，采用任意的選擇方式得到的屬性約簡中存在冗余屬性的現(xiàn)象。

2) 提高算法的效率。和基于差別矩陣的算法相比較，這種改進(jìn)后的屬性約簡算法可以不用對所有包含核屬性元素進(jìn)行依次判斷，進(jìn)而避免組合的問題。和基于差別函數(shù)的算法相比較，改進(jìn)后的算法在時(shí)間上的優(yōu)勢更加明顯。采用改進(jìn)后的屬性約簡算法得到的屬性約簡往往是有最優(yōu)解的。這種算法是一種啟發(fā)式的算法。這種改進(jìn)后的算法存在一定的不足，主要是空間的復(fù)雜度比較高。

4 結(jié)束語

粗糙集關(guān)于規(guī)則的提取、屬性的約簡及知識定義等方面的理論，讓數(shù)據(jù)倉庫方面的數(shù)據(jù)挖掘有了更深刻的理論基礎(chǔ)。粗糙集理論在處理數(shù)據(jù)的時(shí)候較智能化，不需要對知識進(jìn)行先驗(yàn)，就能從樣本數(shù)據(jù)中挖掘出直接、簡明及容易理解的規(guī)則。總之，在對操作機(jī)屬性約簡算法進(jìn)行改進(jìn)后，數(shù)據(jù)挖掘技術(shù)的應(yīng)用領(lǐng)域會變得更多。

[1] 李丹.基于粗糙集的數(shù)據(jù)挖掘?qū)傩约s簡算法的研究[D].哈爾濱:哈爾濱工程大學(xué),2008:1-3.

[2] 吳明旺.基于粗糙集的數(shù)據(jù)挖掘?qū)傩约s簡算法研究[D].成都:電子科技大學(xué),2006:3-19.

[3] 趙永安.基于粗糙集的屬性約簡算法研究[D].呼和浩特:內(nèi)蒙古大學(xué),2008:29-42.

[4] 苗奪謙,陳玉明,王睿智,等.圖表示下的知識約簡[J].電子學(xué)報(bào),2010(8):1952-1959.

[5] 洪雪飛.基于粗糙集的數(shù)據(jù)挖掘算法的研究與應(yīng)用[D].北京:北京交通大學(xué),2008:22-45.

[6] ZHANG Z, YU D Y, LI P G， et al. An improved reduction algorithm based on the degree of attribute discernibility[J].High Technology Letters,2007,13(3):244-248.

[7] 崔洪晶.基于粗糙集的屬性約簡算法研究[D].哈爾濱:哈爾濱工程大學(xué),2007:1-5.

[8] 吳尚智.基于粗糙集理論的屬性約簡算法研究[D].蘭州:西北師范大學(xué),2006:17-27.

〔責(zé)任編輯： 盧 蕊〕

Researchontheimprovedalgorithmforattributereductioninroughsetbasedondatamining

LU Xiu-yun

(Information Engineering Department, Zhenjiang Higher Vocational Technical School, Zhenjiang 212016, China)

Application of rule extraction algorithm of attribute reduction based on Rough Set Theory is studied in data mining. The data mining of attribute reduction is often based on rough set, and then it is done in accordance with the rules extraction. Based on the investigation to the relevant definition of discernibility matrix, the information system is more complex and nuclear property element accounts for a small proportion. The algorithm of attribute reduction based on discernibility matrix is improved by using the discernibility matrix structure to establish the basis for a new selection property.

rough set; data mining; attribute reduction; improvement

2014-05-28

盧秀蕓(1982—)，女，江蘇鎮(zhèn)江人，講師，碩士，主要從事數(shù)據(jù)庫研究。

TP274

： A

：1008-8148(2015)01-0055-03