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

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

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

1 粗糙集理論分析

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

1.1 粗糙集定義

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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