朱小剛

南昌大學,江西南昌330096

基于計算機粗糙集的數(shù)據(jù)挖掘設計與應用分析

朱小剛

南昌大學,江西南昌330096

計算機與網(wǎng)絡的日益普及，帶來大量繁雜的數(shù)據(jù)與信息處理。數(shù)據(jù)挖掘技術能夠從大量的數(shù)據(jù)中提取隱含的信息，而粗糙集是數(shù)據(jù)挖掘中最常用的方法。本文簡單概括了粗糙集的基本屬性，并分析了數(shù)據(jù)挖掘的設計與應用。

數(shù)據(jù)挖掘;粗糙集;應用分析

在過去的幾十年中，計算機技術和網(wǎng)絡技術日漸普及，隨之而來的還有各種各樣豐富的數(shù)據(jù)資源。人們在享受著這些大量的數(shù)據(jù)所帶來的便利的同時，也逐漸認識到一個嚴重的問題：數(shù)據(jù)豐富而知識匱乏?，F(xiàn)在，數(shù)據(jù)庫系統(tǒng)能夠幫助我們對數(shù)據(jù)進行提取搜索修改等功能，但是我們還需要認識到數(shù)據(jù)背后所隱藏的規(guī)則和有關知識，依靠這些來進行預測[1]。

數(shù)據(jù)挖掘技術就是在這種情況下應運而生的，它是從眾多繁雜的數(shù)據(jù)中尋找有用的知識的有效的方法[2,3]。數(shù)據(jù)挖掘涉及到了包括數(shù)據(jù)庫、數(shù)學、計算機、人工智能等許多學科的知識[4]。數(shù)據(jù)挖掘的主要方法是粗糙集。粗糙集最初是由Pawlak Z提出來的，最開始是用來對不完善不準確的知識進行整理的數(shù)學方法[5]。它的基本理念[6]是將知識進行簡化，提煉出問題的解決方法或者分類準則，前提是分類能力沒有改變。由于粗糙集理論能夠在有限的條件下對知識進行處理和提取，所以已經(jīng)被應用到了機器、模式、醫(yī)療、決策等多個領域，并且在這些領域取得了相當明顯的成就。粗糙集理論中主要的一個研究方向就是屬性約簡[7]，屬性約簡能夠?qū)⒎彪s的信息簡化為規(guī)則庫，來方便人們進行使用。在這一方面，國內(nèi)外的許多學者都做了相關研究，但都沒有取得重大突破，所以，尋快速的約簡算法仍然是眾多學者們研究的熱點問題。

1 數(shù)據(jù)挖掘技術簡介

1.1 概念

數(shù)據(jù)挖掘，簡單來說，是一個從數(shù)據(jù)到知識的轉(zhuǎn)換。數(shù)據(jù)挖掘能夠用比人類更迅速的方法，從大量數(shù)據(jù)中搜尋到有用的信息，并嘗試建立模型，用來簡單地敘述復雜的信息。

被挖掘的數(shù)據(jù)來源可以來自網(wǎng)絡，也可以來自數(shù)據(jù)庫。

數(shù)據(jù)挖掘有兩種不同的學習方法：推理，歸納。推理需要結合已有信息去尋找未知信息。歸納則致力于尋找隱藏在不同數(shù)據(jù)中的模式。對于數(shù)據(jù)挖據(jù)來講，歸納學習是一種重要且實用的方法[8]。

數(shù)據(jù)挖掘方法主要有遺傳算法、決策樹方法、模糊集合論、粗糙集方法等。

1.2 數(shù)據(jù)挖掘流程

按照數(shù)據(jù)挖掘的過程可以分為以下幾個主要步驟：

（1）數(shù)據(jù)準備：對于數(shù)據(jù)庫中的數(shù)據(jù)，通常是通過長時間積累下來的，用來進行處理很困難。

數(shù)據(jù)準備過程就是將這些數(shù)據(jù)進行篩選、凈化、推算和簡化。這些過程之后會形成數(shù)據(jù)倉庫。這一步驟做的工作將直接影響到數(shù)據(jù)挖掘的效率，精確度和模式的效果；

（2）數(shù)據(jù)挖掘：在前一步驟所整理出來的數(shù)據(jù)倉庫上進行數(shù)據(jù)挖掘。單獨或者綜合運用各種數(shù)據(jù)挖掘方法對數(shù)據(jù)處理，根據(jù)用戶需要選擇數(shù)據(jù)挖掘的算法，這些算法（分類，匯總，回歸等）將用來提取數(shù)據(jù)下的模式；

（3）對結果進行分析同化：對上面得到的模型進行評估，看它是不是能夠應用于實際，應當確定它是有效的可用的。評估的過程不一致，可以根據(jù)用戶自己的經(jīng)驗，也可以根據(jù)某些數(shù)據(jù)標準來進行驗證。評價并描述數(shù)據(jù)挖掘這一過程所得到的模式和規(guī)則，使得用戶能夠理解這些知識。

圖1 數(shù)據(jù)挖掘過程Fig.1 Process of data mining

2 基于計算機粗糙集的數(shù)據(jù)挖掘設計

2.1 粗糙集理論

粗糙集是一種從大量數(shù)據(jù)中導出相關決策和模式的工具，能夠?qū)Ω鞣N不完整的信息分析處理。

在粗糙集理論中，將對對象進行整理的能力稱作知識，通常利用決策表來實現(xiàn)這個功能。對象可以是任何能想到的食物，比如抽象概念，數(shù)據(jù)，時間，狀態(tài)等。知識必定要與許多分類模式有關，叫做論域[9]。粗糙集理論是建立在集合論上面的，所以知識表示也是基于集合論的。

定義2.1信息系統(tǒng)和信息表將客觀世界看成為一個信息系統(tǒng)，也叫做知識庫。信息系統(tǒng)S可以用四元組來表示：S={U,A,V,f}.

在這個四元組中,U表示對象的有限集合,U={x1,x2……xn};A是關于屬性的有限集合，A={a1,a2……am}；V是關于屬性的值域集合，V={v1,v2……vm}，屬性ai對應的值域是vi，f表示信息函數(shù)，f :A×U→V,f (xi,aj)∈vj。

定義2.2不可分辨關系不可分辨關也被叫做等價關系，它的定義如下：R(B)={（X1,X2）|f(x1,b)=f(x2,b),b∈B}。

在上面的定義中，A的子集是B，意思是，如果有，都有(x1,x2)∈R，對于x1∈Xi,x2∈Xj,i≠j,都有(xi,xj)?R 。x1,x2∈Xi

U被R(B)分成k個等價類，表示為R*(B)={X1,X2……XK}。在下面的敘述中，將R(B)記作R，R*(B)記作R*。就等價類Xi來講,{Xi}指的是集合Xi的基數(shù)。

在定義中，論域中不能區(qū)分的對象組成了等價類。

定義2.3上近似，下近似如果有組對象X?U，條件屬性為R?C，R代表等價關系，那么X相對于R的下近似寫成：；X相對于R的上近似可以寫成。下近似說的是，由R能夠確定U中的元素組成的一定是X的子集；上近似指的是，根據(jù)R判斷出，U中的可能屬于X的集合。有時，我們也將下近似稱之為X的R正域，記作posR(X)，叫做X的負域，記作negR(X)。

定義2.4決策系統(tǒng)若一個信息系統(tǒng)的屬性集合中包含決策屬性，叫做決策系統(tǒng)。決策系統(tǒng)記作，屬性A分成集合C和D，有，C代表條件屬性的集合，即條件維集，D代表決策屬性的集合，即決策維集。

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

建立模型的過程：

(1)準備數(shù)據(jù)。從原始數(shù)據(jù)開始，選定條件屬性及其對應的值域，選定結論屬性及其對應的值域，同時轉(zhuǎn)換原始數(shù)據(jù)，最后會得到符合定義的一個決策系統(tǒng)，表示為(U,C{d })。

(2)衍生節(jié)點。對SRED(C,yigoaga)進行計算，將計算結果作為模型建立的初始節(jié)點，對于屬性相同的節(jié)點，放在模型的一層里。其次，將每個節(jié)點中的一個屬性刪掉，會得到后繼節(jié)點，重復這一過程，直至遇到空節(jié)點，也就是沒有條件屬性的節(jié)點，如下圖2所示。

圖2 模型中各節(jié)點關系圖Fig.2 The relationship of each node in model

(2)停止條件。若某個節(jié)點中有前向節(jié)點，該前向節(jié)點的置信度小于μ0，那么計算在此時停止。

2.3 模型的運行

當模型創(chuàng)建好之后，就可以用來處理新的數(shù)據(jù)源了，運行模型的過程如下：

(1)用數(shù)據(jù)源的條件屬性和模型中的節(jié)點（如圖2）相配合，若有匹配節(jié)點，那么選擇第一個節(jié)點進行配合；

(2)將已經(jīng)匹配上的屬性值去跟節(jié)點的規(guī)則集進行匹配，如果有匹配規(guī)則，那么之后重新回到這些規(guī)則，不然，跳到步驟3；

(3)對于該節(jié)點中全部的后續(xù)節(jié)點，都返回到步驟2中。

根據(jù)上面的分析，結果有下面幾種形式：1）返回只有一條規(guī)則；2）返回有多條規(guī)則；3）沒有任何返回規(guī)則。

第一種情況較好處理，而第三種情況表示無法給出相應解，第二種情況多有下面幾種處理辦法：

A.若兩種規(guī)則分別歸于兩個節(jié)點，那么將后續(xù)節(jié)點的規(guī)則去掉；

B.根據(jù)評判算法，選取優(yōu)先級比較高的規(guī)則進行返回；

C.而對于優(yōu)先級的評判，可以用粗糙隸屬函數(shù)或者綜合評判算法[10]來判斷。

2.4 屬性約簡

2.4.1 基本思想屬性是否能夠進行約簡取決于各屬性間關系的緊密程度。眾多屬性約簡的算法的基本思想大體是一致的，都把屬性重要性看成是啟發(fā)式信息，最佳約簡往往是從信息系統(tǒng)和決策系統(tǒng)中提取的，被叫做啟發(fā)式算法?；诓僮鞣椒ǎ梢苑譃閮煞N不同的想法：前向選擇法，后向刪除法。目前常用的算法是前向選擇法。

2.4.2 常見算法區(qū)分矩陣區(qū)分矩陣又被叫做可辨識矩陣，差別矩陣，是數(shù)學家Skowron提出的。利用區(qū)分矩陣，我們可以描述出繁雜信息系統(tǒng)中的所有不可區(qū)分的關系。

定義2.6區(qū)分函數(shù)運用布爾函數(shù)作為區(qū)分函數(shù)，記作Δ，針對屬性a∈A，都有一個相應的布爾變量a，如果，對應的為，記作；如果，則對應的布爾變量是1.將布爾函數(shù)或者區(qū)分函數(shù)Δ定義為：。

性質(zhì)：屬性集A的全部約簡是布爾函數(shù)Δ的最小析取式中的全部合取式。

分類質(zhì)量這種方法是求屬性約簡的時候，忽略核屬性，把核看成是空集，按照屬性重要度，即分類質(zhì)量來進行排列，排列的時候把重要度高的屬性納入最簡集，直到最簡集的分類能力和原表分類能力一樣，此時終止算法。

遺傳算法遺傳算法是根據(jù)達爾文遺傳學理論和自然選擇學說而逐漸發(fā)展起來的一種優(yōu)化算法，組成算子主要有三個：選擇，交叉，變異。該算法用遺傳算子來處理初始群體，將初始群體引導向最優(yōu)解。

3 應用領域

在數(shù)據(jù)挖掘方面，粗糙集顯示出了其獨特的作用，因此，近些年粗糙集的應用得到了人們的深入研究。粗糙集的應用主要在以下幾個領域：

（1）多方法結合。Jelonek學者對于粗糙集理論（Rough Set，以下簡稱RS）進行了研究，將它用作對神經(jīng)網(wǎng)絡訓練數(shù)據(jù)進行了屬性及其支予的縮減，使得在近似分類差錯率很低的情況下，提高了效率。研究人員Hu還發(fā)現(xiàn)了RS可以與一種歸納的思路相結合，這種方法運用概念樹爬升技術泛化屬性，用RS理論進行縮減生成所需的知識。

（2）縮減數(shù)據(jù)。生成規(guī)則Lenarcik等人對基于所有不相同的對象值的粗糙分類器進行了研究，思路是對每個對象重新賦予一個新的值屬性。Grzymala-Busse等人將同時對可能和確定規(guī)則以及只用確定規(guī)則進行了研究，發(fā)現(xiàn)后者的錯誤率要高于前者。

（3）粗糙邏輯。很多學者都致力于基于RS的Rough邏輯。Lin，Liu等人根據(jù)拓撲學原理給出了上近似算子H和下近似算子L的概念，前者與模態(tài)邏輯中的必然算子十分接近，后者與模態(tài)邏輯中的必然算子十分接近。含有L和H兩個算子的相應公式被叫做Rough邏輯公式。同時，與模態(tài)邏輯類似的理論化的Rough集的邏輯演繹系統(tǒng)和規(guī)則也被建立。Yao，Lin對模態(tài)邏輯和RS進行了討論，得到一些關于擴展粗糙集的特性。

（4）大數(shù)據(jù)集。基于關聯(lián)規(guī)則挖掘算法理論，有些研究學者將其用來確認粗糙集和生成相關的規(guī)則，將粗糙集在數(shù)據(jù)挖掘中的繁雜計算進行簡化。Nfuyen等人提出了一種新的決策表分解辦法。重復遞歸這個過程，直到得到我們所需要的決策表為止。關于最后生成的小決策表，生成相應的規(guī)則。有新對象出現(xiàn)的時候，從頂部一直匹配到葉子。

4 小結

(1)數(shù)據(jù)挖掘技術中運用最多的方法就是粗糙集。粗糙集是一種從大量數(shù)據(jù)中找出潛在規(guī)則的工具。粗糙集中比較重要的內(nèi)容是知識約簡，知識約簡的過程就是對信息系統(tǒng)中的相關信息進行分析，刪除冗余信息的過程；

(2)數(shù)據(jù)挖掘模型的建立過程包括數(shù)據(jù)的準備、節(jié)點的衍生和計算、停止條件幾個步驟。模型建立好之后，就可以進行運行了；

(3)粗糙集的應用十分廣泛，目前，學者們發(fā)現(xiàn)可以運用粗糙集進行多方法結合、大數(shù)據(jù)集、縮減數(shù)據(jù)和形成規(guī)則、粗糙邏輯等操作處理。

[1]Shortland R,Scarfe R.Digging for Gold[J].IEE Review,199541(5):213-217

[2]曾黃麟.粗集理論及其應用[D].重慶:重慶大學出版社,1998

[3]韓家偉.數(shù)據(jù)挖掘中的知識分類[C]//1999年數(shù)據(jù)挖掘論文集.上海:復旦大學出版社,1999:16-18

[4]Pauray S M Tsai,Chien-Ming Chen.Discovering Knowledge from Large Databases Using Prestored Information[J], Information systems,2001,26(1):1-14

[5]Pawlak Z.Rough Sets:theoretical aspects of reasoning about data[M].Netherlands:Kluwer Academic Publishers,1991

[6]Wojciech P Ziarko.Rough Sets,Fuzzy Sets and Knowledge Discovery:Proceedings International Workshop on Rough Set and Knowledge Discovery[C].Berlin:Springer-Verlag Berlin and Heidelberg GmbH&Co.K,1993

[7]Bautista R,Millan M,Diaz J F.An Efficient Implementation to Calculate Relative Core and Reducts[C].New York:18th International Conference of the NorthAmerican on Fuzzy Information Processing Society,1999

[8]Pete C,Julian C,Randy K,et al.The CRISP-DM 1.0[M].USA:SPSS,2000

[9]張文修,吳偉志,李德玉.粗糙集理論與方法[D].北京:科學出版社,2001

[10]Aasheim O T,Solheim H G.Rough sets as a framework for data mining[R].Trondheim:Norwegian University of Science and Technology,1996

The Analysis on the Design and Application of Data Mining Based on Computer Rough Set

ZHU Xiao-gang
Nanchang University,Nanchang 330022,China

There are a lot of data and information treatment on computer with the growing popularity of the computer networks,and these complex data and information can be extracted by the method of the rough set,one of methods in technology of data mining.This paper simply introduced the basic attribute about the rough set,and described the process of the data mining,discussed the most common algorithms,and finally analyzed the application in the rough set technology.

Data mining;rough set;application analysis

G202

A

1000-2324(2015)05-0765-04

2013-06-11

2013-08-20

朱小剛(1978-),男,碩士研究生,副教授,研究方向:軟件工程及網(wǎng)絡安全.E-mail:hyxncdx@126.com