粗糙集理論下的海量數據挖掘算法

劉福剛

（淮南聯合大學信息工程學院 安徽淮南 232001）

一、基于粗糙集數據挖掘步驟

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

二、基于動態聚類兩步離散化算法

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

圖1 基于粗糙集的數據挖掘處理實現簡圖

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

算法1：

輸入相應的決策表S=

輸出：S首次進行篩選操作后，斷點集CUTfirst循環歷經S每一個條件屬性k，算法執行如下：

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

初始化聚類個數為1，循環控制變量為v=e+1；

若v>e，需要執行下列循環操作：

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

①e1=v；

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

③對于聚類中心處于T中各類別數據實施調整；

（2）K=K+1；

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

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

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

（二）兩步離散化算法。

算法2：輸入：S=

輸出：S斷點集CUTfirst；

算法操作流程：

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

（2）對算法1進行調用，獲取CUTfirst；

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

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

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

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

在算法3中，輸入：S=

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

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

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

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

（6）在斷點散播環節，斷點集CUTlast自各進程L代表的實例劃分為相應的等價類集合，CUTlast=Φ，L={ }U。

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

（8）在并行處理環節；假設當前進程是Pi，Pi求解CUTi內每一個斷點c重要性WCUTlast(c)，選定斷點至主進程P1；

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

三、算法測試結果分析

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

表1 對比不同算法正確性

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

圖1 改進算法測試結果分析

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

表2 離散化處理后斷點個數

四、結語

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