盧秀蕓

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

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

盧秀蕓

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

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

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

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

1 粗糙集

粗糙集一般用于處理具有不確定性的知識(shí)和模糊知識(shí)。研究粗糙集，重點(diǎn)是在保持知識(shí)庫(kù)分類能力的條件下，對(duì)知識(shí)庫(kù)中的知識(shí)屬性進(jìn)行約簡(jiǎn)，推導(dǎo)需要研究知識(shí)的決策規(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的約簡(jiǎn)[3-4]。知識(shí)的約簡(jiǎn)并不是唯一的?，F(xiàn)在對(duì)具有不確定性知識(shí)進(jìn)行處理的理論非常多。相對(duì)而言，粗糙集理論所依靠的僅僅是問題所提供的數(shù)據(jù)集合，不需要其他的先驗(yàn)知識(shí),同時(shí)，還能和其他理論如模糊學(xué)和證據(jù)理論、概率與數(shù)理統(tǒng)計(jì)理論等互補(bǔ)。它在數(shù)據(jù)挖掘、決策分析、模式的分類和識(shí)別、人工智能等方面都有較成功的應(yīng)用。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

約簡(jiǎn)算法的流程圖如圖2所示。

圖2 約簡(jiǎn)算法流程圖

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

圖3 差別矩陣

圖4信息系統(tǒng)

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

圖5 修改后的差別矩陣

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

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

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

4 結(jié)束語

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

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

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

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

[4] 苗奪謙,陳玉明,王睿智,等.圖表示下的知識(shí)約簡(jiǎn)[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] 崔洪晶.基于粗糙集的屬性約簡(jiǎn)算法研究[D].哈爾濱:哈爾濱工程大學(xué),2007:1-5.

[8] 吳尚智.基于粗糙集理論的屬性約簡(jiǎn)算法研究[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ù)庫(kù)研究。

TP274

： A

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