劉福剛

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

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

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

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

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

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

（一）改進處理的離散化算法。

算法1：

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

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

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

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

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

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

①e1=v；

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

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

（2）K=K+1；

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

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

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

（二）兩步離散化算法。

算法2：輸入：S=

輸出：S斷點集CUTfirst；

算法操作流程：

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

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

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

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

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

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

在算法3中，輸入：S=

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

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

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

（5）進行斷點補充修復(fù)階段，與算法2相同；

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

由進程P1對CUT1這個斷點集實施處理，···，Pk對CUTk進行處理；

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

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

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

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

表1 對比不同算法正確性

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

圖1 改進算法測試結(jié)果分析

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

表2 離散化處理后斷點個數(shù)

四、結(jié)語

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