粗糙集理論下的海量數(shù)據(jù)挖掘算法

劉福剛

（淮南聯(lián)合大學(xué)信息工程學(xué)院 安徽淮南 232001）

一、基于粗糙集數(shù)據(jù)挖掘步驟

隨著信息技術(shù)、計(jì)算機(jī)技術(shù)的發(fā)展，信息展現(xiàn)出指數(shù)上升的增長速度，也出現(xiàn)大量數(shù)據(jù)庫，涉及銀行存款、制造業(yè)等領(lǐng)域，信息量迅速增長，導(dǎo)致傳統(tǒng)分析方法難以達(dá)到現(xiàn)實(shí)需求。應(yīng)對(duì)海量數(shù)據(jù)，如何充分挖掘有價(jià)值的數(shù)據(jù)或者知識(shí)，是一項(xiàng)艱巨的任務(wù)，必須提供一項(xiàng)去偽存真的技術(shù)。數(shù)據(jù)挖掘則是一種具有強(qiáng)大功能、潛在的技術(shù)，可以幫助用戶自海量、隱含的數(shù)據(jù)內(nèi)找出重要、有價(jià)值的信息，從而預(yù)測(cè)未來的行為，有利于用戶做出準(zhǔn)確的決策。數(shù)據(jù)挖掘作為近些年數(shù)據(jù)庫領(lǐng)域研究的新興熱點(diǎn)，也成為提升管理決策支持能力重要的手段及工具，其主要任務(wù)在于由大量數(shù)據(jù)內(nèi)提取未知、隱含有價(jià)值的知識(shí)。數(shù)據(jù)挖掘研究熱點(diǎn)也從單一的數(shù)據(jù)挖掘轉(zhuǎn)變?yōu)槎喾N方法結(jié)合起來獲取知識(shí)[1-4]。本研究提出依托粗糙集開展數(shù)據(jù)挖掘的方法，粗糙集理論用于處理海量數(shù)據(jù)，從而消除一系列冗余信息。粗糙集理論就是用于研究不完備、不精確信息處理的重要工具，其研究對(duì)象是具備多個(gè)屬性描述的一組對(duì)象集合，并把對(duì)象以等價(jià)關(guān)系為依托在整個(gè)空間實(shí)施劃分，從而劃分成正域、負(fù)域及其邊界[5-7]。其特點(diǎn)就是由實(shí)際數(shù)據(jù)入手，不再依賴對(duì)象模型，無需先驗(yàn)知識(shí)，結(jié)論也是客觀的。自波蘭數(shù)學(xué)家首次提出粗糙集相關(guān)知識(shí)后，通過幾十年的研究及發(fā)展，該理論在實(shí)際應(yīng)用方面獲取長足進(jìn)展，也受到不同領(lǐng)域的廣泛重視及關(guān)注。粗糙集理論就是創(chuàng)建在分類機(jī)制上，將分類理解為在特定空間內(nèi)的等價(jià)關(guān)系，這種關(guān)系就是對(duì)空間實(shí)施劃分，旨在利用已有知識(shí)庫，把不確定或并沒有精確的知識(shí)通過已有知識(shí)庫內(nèi)的知識(shí)進(jìn)行近似劃分。如今，粗糙集理論在人工智能、故障分析、決策支持等方面得到成功的應(yīng)用。采用粗糙集相關(guān)理論，對(duì)一般信息系統(tǒng)執(zhí)行數(shù)據(jù)挖掘，其步驟如圖1所示。具體操作步驟如下：（1）數(shù)據(jù)抽取：自數(shù)據(jù)庫或數(shù)據(jù)表內(nèi)，依托合并、聚合等手段，在海量數(shù)據(jù)內(nèi)提取相關(guān)數(shù)據(jù)，組成相應(yīng)的數(shù)據(jù)集；（2）預(yù)處理：把數(shù)據(jù)集合內(nèi)非數(shù)值屬性列實(shí)施編碼處理，補(bǔ)齊缺值，組成數(shù)值化數(shù)據(jù)集。離散化：把處于連續(xù)狀態(tài)的屬性值展開離散化處理，最終組成決策表[8-13]。屬性約簡：對(duì)第3步形成的決策表展開屬性約簡操作，刪除冗余屬性及其不必要性，求解屬性核。對(duì)屬性約簡之后決策表內(nèi)的冗余屬性值執(zhí)行刪除處理，提取精煉、有效的規(guī)則知識(shí)；規(guī)則解釋：對(duì)數(shù)據(jù)提取后，將各條規(guī)則屬性值翻譯成沒有編碼或離散化前的描述。粗糙集理論主要特點(diǎn)如下：不得不說，粗糙集方法比較簡單、實(shí)用，它在創(chuàng)立后迅速得到應(yīng)用，其具有下列特點(diǎn)：粗糙集理論支持處理各類數(shù)據(jù)，包含不完整數(shù)據(jù)、具有多變量數(shù)據(jù)；它可以處理數(shù)據(jù)不精確性，包含確定性與非確定性這兩種情況；它可以求出知識(shí)的最小表達(dá)及知識(shí)不同顆粒層次；它可以由海量數(shù)據(jù)內(nèi)揭示概念簡單，方便操作的模式；它能夠產(chǎn)生精確、便于檢查、證實(shí)的規(guī)則，尤其適合用在智能控制規(guī)則自動(dòng)生成過程中[14]。

二、基于動(dòng)態(tài)聚類兩步離散化算法

這種算法就是運(yùn)用動(dòng)態(tài)聚類算法對(duì)決策表實(shí)施離散化處理，隨后，依托斷點(diǎn)重要性算法進(jìn)行第二次離散化處理，以此獲取相應(yīng)的斷點(diǎn)集。依托粗糙集數(shù)據(jù)挖掘算法發(fā)現(xiàn)規(guī)則需要經(jīng)過下列步驟，見圖1。先把數(shù)據(jù)庫中的初始數(shù)據(jù)轉(zhuǎn)變成為粗糙集形式，明確設(shè)定條件屬性及決策屬性；在屬性約減環(huán)節(jié)，組成不可分辨的矩陣，并在設(shè)計(jì)的矩陣上生成約減屬性集；在響應(yīng)的約減信息表內(nèi)，依據(jù)可信度閥值準(zhǔn)確發(fā)現(xiàn)規(guī)則[15]。

圖1 基于粗糙集的數(shù)據(jù)挖掘處理實(shí)現(xiàn)簡圖

（一）改進(jìn)處理的離散化算法。

算法1：

輸入相應(yīng)的決策表S=

輸出：S首次進(jìn)行篩選操作后，斷點(diǎn)集CUTfirst循環(huán)歷經(jīng)S每一個(gè)條件屬性k，算法執(zhí)行如下：

（1）對(duì)k的每個(gè)斷點(diǎn)重要性進(jìn)行求解，并遵循自小到大的原則對(duì)斷點(diǎn)值實(shí)施排序，把求解出來的結(jié)果保存到數(shù)組Importantk[]內(nèi)，m表示重要的斷點(diǎn)所處數(shù)組位置，即：

初始化聚類個(gè)數(shù)為1，循環(huán)控制變量為v=e+1；

若v>e，需要執(zhí)行下列循環(huán)操作：

建立聚類中心表T，處在l-h范圍之內(nèi)自Importantk隨機(jī)選取k個(gè)初始聚類中心；假設(shè)循環(huán)變量e1=0，如果e1≠v，執(zhí)行以下操作：

①e1=v；

②對(duì)T中每種類數(shù)值與Importantk每一個(gè)h-l距離進(jìn)行統(tǒng)計(jì)，并將上述統(tǒng)計(jì)結(jié)果同類到距離最小的類別中；

③對(duì)于聚類中心處于T中各類別數(shù)據(jù)實(shí)施調(diào)整；

（2）K=K+1；

（3） 在l=m+l，h=|Importantk|-1,n=|h-l+1|，執(zhí)行第3步至第5步。

自每一個(gè)聚類內(nèi)挑選最重要的斷點(diǎn)添加至CUTfirst內(nèi)。

決策表通過以上算法離散化后，其效果僅次于依托屬性重要性離散化算法的局部離散化效果。下文把CUTfirst輸入到斷點(diǎn)重要性算法中開展第一次全局離散化處理，以此獲得依托動(dòng)態(tài)聚類的兩步離散化算法。

（二）兩步離散化算法。

算法2：輸入：S=

輸出：S斷點(diǎn)集CUTfirst；

算法操作流程：

（1）在并未實(shí)施離散化條件下，計(jì)算S的正區(qū)域POSC(D);

（2）對(duì)算法1進(jìn)行調(diào)用，獲取CUTfirst；

（3）通過斷點(diǎn)集CUTfirst對(duì)S展開初步離散化處理明確S1正區(qū)域數(shù)值，假設(shè)S1代表離散化處理后的決策表，若不成立，實(shí)例會(huì)被CUTfirst劃分為等價(jià)類集合采用L代表，對(duì)每一個(gè)X∈L，做出下列處理；如果以上條件成立，可以轉(zhuǎn)至第5步。

（8）如果每個(gè)X∈L，且當(dāng)Cmax等價(jià)類X劃分為X1、X2，將等價(jià)類添加至L內(nèi)，并由L中將X去掉；

（9）若L內(nèi)所有等價(jià)類實(shí)例均不具備一致的決策，需要轉(zhuǎn)移至第3步；反之，所有算法操作完成。從算法2視角分析，如果數(shù)據(jù)集中包含許多候選斷點(diǎn)，此時(shí)，這種算法需要執(zhí)行較長的運(yùn)行時(shí)間，要結(jié)合并行計(jì)算思想對(duì)算法實(shí)施再次改進(jìn)。

（三）兩步并行離散化算法。

在算法3中，輸入：S=

輸出：決策表S斷點(diǎn)集CUTlast，算法執(zhí)行步驟為：

（1）在沒有實(shí)施離散化條件下，求解出S的正區(qū)域POSc(D)；

（3）在并行處理中，若設(shè)當(dāng)前進(jìn)程是Pi，Pi依據(jù)算法2對(duì)Si內(nèi)每個(gè)條件屬性的候選斷點(diǎn)展開聚類處理。如果設(shè)定聚類后的斷點(diǎn)集是CUTfirst i，發(fā)送CUTfirst i至主進(jìn)程；

（5）進(jìn)行斷點(diǎn)補(bǔ)充修復(fù)階段，與算法2相同；

（6）在斷點(diǎn)散播環(huán)節(jié)，斷點(diǎn)集CUTlast自各進(jìn)程L代表的實(shí)例劃分為相應(yīng)的等價(jià)類集合，CUTlast=Φ，L={ }U。

由進(jìn)程P1對(duì)CUT1這個(gè)斷點(diǎn)集實(shí)施處理，···，Pk對(duì)CUTk進(jìn)行處理；

（8）在并行處理環(huán)節(jié)；假設(shè)當(dāng)前進(jìn)程是Pi，Pi求解CUTi內(nèi)每一個(gè)斷點(diǎn)c重要性WCUTlast(c)，選定斷點(diǎn)至主進(jìn)程P1；

（9）對(duì)于每一個(gè)X ∈ l，在等價(jià)類X被劃分為X1、X2，并將X1、X2添加至L內(nèi)，并將X去掉；如果L內(nèi)全部等價(jià)類內(nèi)的實(shí)例均不具有相同的決策，需要執(zhí)行第2步，反之，則算法結(jié)束。

三、算法測(cè)試結(jié)果分析

（一）改進(jìn)Rough Set算法正確性及可伸縮性。挑選UGI數(shù)據(jù)庫內(nèi)的5個(gè)數(shù)據(jù)集，對(duì)比通過CDL改進(jìn)的只是約簡算法與原始算法的正確性，結(jié)果如表1所示。根據(jù)該表數(shù)據(jù)可知，采用CGL改造之后的知識(shí)約簡算法并不影響原始算法的正確性、識(shí)別率等各項(xiàng)性能。

表1 對(duì)比不同算法正確性

在訓(xùn)練集由10萬條逐漸增加導(dǎo)致100萬條狀態(tài)下，測(cè)試集記錄的數(shù)據(jù)就是整個(gè)訓(xùn)練集30%。在此基礎(chǔ)上，組成海量數(shù)據(jù)集，其包括條件、決策屬性分別為8個(gè)、1個(gè)，其結(jié)果如圖1所示。根據(jù)下圖可知，新改進(jìn)算法能有效提升算法可伸縮性，促使其適應(yīng)更大的數(shù)據(jù)集。與此同時(shí)，這種算法具有良好的性能，不失具備正確率及識(shí)別率。對(duì)知識(shí)發(fā)現(xiàn)需要使用大量的時(shí)間，與測(cè)試所用平臺(tái)配置的SQL服務(wù)器效率存在密切的關(guān)系，運(yùn)用并行算法能提升其處理速度。

圖1 改進(jìn)算法測(cè)試結(jié)果分析

（二）基于動(dòng)態(tài)聚類兩步離散化算法并行化處理。根據(jù)UCI數(shù)據(jù)庫挑選6組數(shù)據(jù)集對(duì)算法2展開測(cè)試，其中，算法運(yùn)行時(shí)間采用T代表，規(guī)則集正確識(shí)別率以P代表。采用基于動(dòng)態(tài)聚類的離散化算法實(shí)施動(dòng)態(tài)聚類處理后，其結(jié)果如表2所示。自SONA、IRIS等方面分析，每一個(gè)數(shù)據(jù)集候選斷點(diǎn)數(shù)據(jù)均明顯降低下降。而基于動(dòng)態(tài)聚類提出的兩步離散化算法計(jì)算速度較快，從正確識(shí)別率等方面分析，貪心算法、基于斷點(diǎn)重要性、動(dòng)態(tài)聚類的算法處在一致狀態(tài)[16-18]。

表2 離散化處理后斷點(diǎn)個(gè)數(shù)

四、結(jié)語

綜上所述，基于最常應(yīng)用的數(shù)據(jù)挖掘算法，依托類分布鏈表對(duì)傳統(tǒng)算法實(shí)施改進(jìn)處理，這種改進(jìn)算法有利于直接處理海量數(shù)據(jù)，進(jìn)而實(shí)現(xiàn)處理超大規(guī)模數(shù)據(jù)集這個(gè)目標(biāo)。系統(tǒng)依托并行化求解思想，借助并行離散化算法明確類分布鏈表方法，進(jìn)而解決系統(tǒng)內(nèi)存有所限制的問題，提升所用算法運(yùn)行效率。