基于粗糙集的數(shù)據(jù)挖掘算法研究

許曉燕 三門峽職業(yè)技術(shù)學(xué)院

引言：粗糙集理論是由波蘭著名數(shù)學(xué)家Pawlak Z所提出的，該理論在分析與表達(dá)不完整與不準(zhǔn)確數(shù)據(jù)中非常適用，粗糙集理論是通過對一個或一組機(jī)構(gòu)中所產(chǎn)生的信息數(shù)據(jù)進(jìn)行測量與觀察，以實現(xiàn)對信息數(shù)據(jù)的分類，并從中找出數(shù)據(jù)所具備的某些特點、對象及過程等，以為認(rèn)知科學(xué)與信息科學(xué)提供可靠的研究方法與全新的科學(xué)邏輯，其也是實現(xiàn)信息智能化處理的重要處理技術(shù)。通常來說，數(shù)據(jù)挖掘作為知識發(fā)現(xiàn)中的關(guān)鍵環(huán)節(jié)，其是在某種約束的基礎(chǔ)上，通過數(shù)據(jù)發(fā)現(xiàn)與數(shù)據(jù)分析算法的應(yīng)用，以從中找出特定模式。對數(shù)學(xué)挖掘進(jìn)行研究的主要方法有回歸、分類、歸納及聚類等，正是由于數(shù)據(jù)挖掘中存在諸多不準(zhǔn)確與不完整的數(shù)據(jù)，這也使粗糙集理論成為數(shù)據(jù)挖掘中的重要方法之一。不過，由于大量數(shù)據(jù)的產(chǎn)生，使數(shù)據(jù)集也變得越來越復(fù)雜，僅僅采用粗糙集理論來對數(shù)據(jù)集進(jìn)行分類，其結(jié)果的穩(wěn)定性與精度也往往較差，而且在交互驗證方面的能力較為欠缺，因此需要將其與其他方法進(jìn)行結(jié)合應(yīng)用才能取得更好的應(yīng)用效果。為此，本文便針對上述不足，對基于粗糙集的數(shù)據(jù)挖掘算法進(jìn)行了研究，并將決策樹與粗糙集結(jié)合起來，以提高數(shù)據(jù)挖掘算法的各方面性能。

1 粗糙集理論分析

粗糙集理論是以現(xiàn)有知識來劃分特定問題中的論域，并根據(jù)劃分后論域中各個組成對概念的支持程度來進(jìn)行分類，這種支持程度包括肯定支持、不支持與可能支持。其通過上下限定域與邊界這三個近似集合來對上述三種支持程度進(jìn)行表示。

1.1 粗糙集定義

在粗糙集理論中共包含三大定義，在第一定義中，論域由U進(jìn)行表示，該論域?qū)儆谝粋€對象集合，在論域U上存在一個劃分R，由此可稱＜U，R＞是近似空間，當(dāng)并且時，則任何滿足該條件的 ，其均為論域 中的等價關(guān)系，由此可判定為和P之間具備不可分辨關(guān)系，可利用 來對這種關(guān)系進(jìn)行表示。當(dāng)時，則 的下近似集與上近似集分別可表示為與，而X的邊界域則可表示成。在第二定義中，在某一知識系統(tǒng)中，可將其表示為 ，并且在該知識系統(tǒng)中，其對象集合、屬性集合以及屬性值集合分別由U、Ω與進(jìn)行表示，各個滿足的均存在一個映射函數(shù)，可由對其進(jìn)行表示，對于來說，可將其表示為，其代表對象中第個屬性所具備的值。在第三定義中，可將論域U的分辨矩陣進(jìn)行定義，使其表述為，而在該知識表述中的，可表示為，通過該分辨矩陣的定義，能夠?qū)Υ植诩疘nd(Ω)進(jìn)行轉(zhuǎn)換，使其成為M(Ω)。

1.2 粗糙集在數(shù)據(jù)挖掘中的知識表達(dá)

精糙集在數(shù)據(jù)挖掘的知識表達(dá)中，主要是通過決策系統(tǒng)來表達(dá)知識的，其也是數(shù)據(jù)挖掘中對知識進(jìn)行表達(dá)的重要方式，可以說，決策系統(tǒng)自身便是一個包含有決定域的系統(tǒng)。設(shè)定，由 來表示決策知識系統(tǒng)，即在 中包含有一個特定子集 ，該子集代表條件屬性集合，而在 中還包括一個特定子集 ，該子集可用來對決策屬性集合進(jìn)行表示。在該決策系統(tǒng)中，可將其分辨矩陣進(jìn)行定義，即其中可表示為決策系統(tǒng)中，當(dāng)Ind(C,D)表示為時，其在該決策系統(tǒng)中具備不可分辨關(guān)系。在決策系統(tǒng)所包含的條件屬性C中，與其相對應(yīng)的約減集則屬于非空子集，則相等，其約減可表示成，而全部約減集之間的交集則可表示為之間相等。

2 基于粗糙集的數(shù)據(jù)挖掘算法研究

在基于粗糙集的數(shù)據(jù)挖掘算法中，其挖掘數(shù)據(jù)庫中存在的規(guī)則需要通過以下步驟來實現(xiàn)，第一步為預(yù)處理步驟，預(yù)處理能夠?qū)崿F(xiàn)數(shù)據(jù)庫中所包含的初始數(shù)據(jù)與粗糙集之間的形式轉(zhuǎn)換，同時對決策與條件屬性進(jìn)行確定；第二步為數(shù)據(jù)約減，通過對不可分辨矩陣的生成以得到相應(yīng)的約減屬性集；第三步是挖掘規(guī)則，首先要根據(jù)約減屬性集來建立約減信息表，然后通過可信度閾值來對規(guī)則進(jìn)行挖掘。基于粗糙集的數(shù)據(jù)挖掘算法共分為兩種，第一種為分辨矩陣生成算法，該算法將 輸入到數(shù)據(jù)庫當(dāng)中，以使初始數(shù)據(jù)和粗糙集進(jìn)行形式轉(zhuǎn)換，進(jìn)而輸出相應(yīng)的分辨矩陣，即 。該算法共分為六步，第一步是將 進(jìn)行轉(zhuǎn)換，從而得到一個維度為 的空屬性集矩陣；第二步是根據(jù)得出的空屬性集矩陣來生成分辨矩陣，并由分辨矩陣得到 ；第三步是對分辨矩陣進(jìn)行求核，如果 ，在 中添加 ；第四步是把包含 的矩陣進(jìn)行元素置空；第五步是得出矩陣中次數(shù)出現(xiàn)最多的屬性，用 來表示該屬性，然后將其添加到 當(dāng)中，并將矩陣中包含的 屬性進(jìn)行元素置空；第六步是假如 不等于 ，則需要返回到第五步中進(jìn)行求核，如果相等，則算法結(jié)束。第二種為規(guī)則挖掘算法，該算法的輸入內(nèi)容包括可信度的閾值，由 來對該閾值進(jìn)行表示，此外輸入內(nèi)容還包括條件屬性。規(guī)則挖掘算法的最終輸出為規(guī)則集。規(guī)則挖掘算法在應(yīng)用過程中共分為三個步驟，第一步是將條件屬性 作為輸入條件；第二步是在 中獲得和C1屬性相一致的元素，并對元素的數(shù)量進(jìn)行統(tǒng)計，由N代表元素數(shù)量，然后找到和屬性D與C1均一致的元素，并對元素數(shù)量進(jìn)行統(tǒng)計，由M代表元素數(shù)量；第三步是如果劃分大小與N之間的商比可信度閾值高，并且挖掘出的規(guī)則不處于規(guī)則表中，則對該規(guī)則進(jìn)行輸出。

決策系統(tǒng)通過計算能夠生成該系統(tǒng)的分辨矩陣，通過該分辨矩陣能夠得出 與 相等，并以約減作為出發(fā)點，以此衍生出相應(yīng)的節(jié)點，并通過決策系統(tǒng)將各個節(jié)點中滿足 的節(jié)點規(guī)則進(jìn)行記錄，然后將其存儲到規(guī)則集當(dāng)中。粗糙理論是根據(jù)等價關(guān)系來生成近似空間的，在該近似空間中所包含的上近似集與下近似集能夠為人們在找出確定與不確定區(qū)域中帶來幫助，從而使該理論能夠適用于數(shù)據(jù)挖掘工作中。

3 基于粗糙集的數(shù)據(jù)挖掘算法的優(yōu)劣勢及解決策略

通過上述分析可知，基于粗糙集的數(shù)據(jù)挖掘算法是利用等價關(guān)系來對集合中的對象實施分類的，通過對集合進(jìn)行某種形式的劃分，以使其能夠和等價關(guān)系相對應(yīng)，并根據(jù)等價類粒度來進(jìn)行信息處理，從而使信息得到簡化。基于粗糙集的數(shù)據(jù)挖掘算法在應(yīng)用方面具備以下優(yōu)勢，其一，其可通過固定算法來對問題進(jìn)行表達(dá)與解決，并且能夠通過軟計算的方式來對不確定、不完整與不精確的數(shù)據(jù)進(jìn)行處理，從而使算法具備成本低與魯棒性強(qiáng)的優(yōu)勢；其二，基于粗糙集的數(shù)據(jù)挖掘算法不需預(yù)先提供某種屬性或特征來進(jìn)行數(shù)學(xué)描述，其能夠?qū)栴}所具備的潛在規(guī)律進(jìn)行直接挖掘，同時其在不確定性問題的描述方面較為客觀；其三，基于粗糙集的數(shù)據(jù)挖掘算法能夠適用于各種確定與不確定的數(shù)據(jù)分析，并且能夠?qū)Σ煌暾c不精確的多變量數(shù)據(jù)進(jìn)行分析，使數(shù)據(jù)得到簡化的同時，找出數(shù)據(jù)中存在的知識與推理決策規(guī)則，其數(shù)學(xué)意義非常清晰；其四，基于粗糙集的數(shù)據(jù)挖掘算法是對不確定性與模糊性問題進(jìn)行處理的重要工具，其能夠通過上下近似集差來對問題的不確定性進(jìn)行描述，并且能夠計算含糊元素的數(shù)量，有效降低了算法的隨意性。雖然粗糙集的數(shù)據(jù)挖掘算法具備非常明顯的應(yīng)用優(yōu)勢，但其自身也存在一定的不足，隨著數(shù)據(jù)量的不斷增長，決策表規(guī)模也不斷擴(kuò)大，僅僅通過粗糙集的應(yīng)用是難以滿足各種類型數(shù)據(jù)集處理的，而且采用粗糙集理論來對數(shù)據(jù)進(jìn)行挖掘后分類，其分類結(jié)果常常是確定的，這也使算法的交互驗證能力較差，造成數(shù)據(jù)挖掘的結(jié)果穩(wěn)定性較差，精度較低。因此，需要在基于粗糙集的數(shù)據(jù)挖掘算法中引入其他方法來對該問題進(jìn)行解決。

4 基于粗糙集與決策樹結(jié)合的數(shù)據(jù)挖掘算法

為了解決基于粗糙集的數(shù)據(jù)挖掘算法交互驗證能力差、結(jié)果穩(wěn)定性不足、精度較低的問題，需要將決策樹引入到該算法當(dāng)中，以使粗糙集理論能夠和決策樹進(jìn)行結(jié)合應(yīng)用，決策樹作為一種歸納推理算法，其在各個領(lǐng)域中的應(yīng)用十分廣泛，決策樹的分類精度較高，并且其構(gòu)造也較為簡單，非常適用于噪聲數(shù)據(jù)的處理，同時考慮到單變量決策樹往往具備較大的規(guī)模，處理全部的數(shù)據(jù)集是無法實現(xiàn)的，因此需要通過多變量決策樹來降低決策樹的規(guī)模，以使分類精度得到相應(yīng)的提高。具體實施如下：首先是對決策表進(jìn)行預(yù)處理，采用基于粗糙集的數(shù)據(jù)挖掘算法來對數(shù)據(jù)集進(jìn)行屬性約減，以使冗余屬性得以清除，進(jìn)而使決策表的維度降低，然后通過聚類技術(shù)的應(yīng)用來劃分等價類對象，以使同組對象的相似性更大，并從各個組中提取一個對象當(dāng)作處理樣本，以使數(shù)據(jù)量減少，然后將屬性作為權(quán)重，并引入到相似度求解公式中，這樣能夠使數(shù)據(jù)對象具備更高的相似度，此外，還需要將屬性集的重要程度當(dāng)作決策樹中節(jié)點的衡量標(biāo)準(zhǔn)，并將兩等價類之間的相對泛化當(dāng)作決策樹中節(jié)點檢驗的標(biāo)準(zhǔn)，同時確保各個節(jié)點的屬性個數(shù)不能超過兩個。

5 結(jié)束語

綜上所述，本文通過對粗糙集理論進(jìn)行分析，明確了粗糙集的定義及其知識表達(dá)，并對基于粗糙集的數(shù)據(jù)挖掘算法進(jìn)行了深入的研究，闡述了粗糙集理論在數(shù)據(jù)挖掘算法中的具體應(yīng)用，分析了其應(yīng)用的可行性，在此基礎(chǔ)上分析了基于粗糙集的數(shù)據(jù)挖掘算法的優(yōu)勢與不足，并針對其不足之處提出了相應(yīng)的解決策略，通過粗糙集與決策樹兩種方法的結(jié)合來進(jìn)行數(shù)據(jù)挖掘，不僅能夠改善數(shù)據(jù)挖掘算法的交互驗證能力，還能提高數(shù)據(jù)挖掘結(jié)果的精度與穩(wěn)定性，從而使基于粗糙集的數(shù)據(jù)挖掘算法更能滿足人們的數(shù)據(jù)挖掘需求。