基于粗糙集和遺傳算法的數(shù)據(jù)挖掘方法

摘要：運(yùn)用粗糙集和遺傳算法的理論，為大型的數(shù)據(jù)挖掘提供了一種新的方法。首先通過粗糙集理論對數(shù)據(jù)進(jìn)行預(yù)處理，然后對屬性簡約，最后通過遺傳算法進(jìn)行規(guī)則提取，尋找最優(yōu)解。

關(guān)鍵詞：粗糙集；遺傳算法；數(shù)據(jù)挖掘；知識發(fā)現(xiàn)

中圖分類號：TP311文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044(2008)11-20336-02

數(shù)據(jù)挖掘[1]又稱知識發(fā)現(xiàn)，是從大量的、不完全的、有躁聲的、模糊的實(shí)際數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又很有用的知識和信息的過程。它的一般步驟如下：提出問題->數(shù)據(jù)準(zhǔn)備->數(shù)據(jù)整理->建立模型->評價(jià)和解釋。它是數(shù)據(jù)庫研究、開發(fā)和應(yīng)用最活躍的一個(gè)分支，是多學(xué)科的交叉領(lǐng)域，涉及數(shù)據(jù)庫技術(shù)、人工智能、機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)、數(shù)學(xué)、統(tǒng)計(jì)學(xué)、模式識別、知識庫系統(tǒng)、知識獲取、信息提取、高性能計(jì)算、并行計(jì)算、數(shù)據(jù)可視化等多方面的知識。

1 粗糙集與遺傳算法的基本概念

粗糙集(Rough Set， RS)[2]作為一種全新的數(shù)學(xué)概念，為處理具有不完整、不一致及不確定性特征的信息提供了新的有效工具，它的主要特點(diǎn)之一是無須提供問題所需處理的數(shù)據(jù)集合之外的任何先驗(yàn)信息。相對于許多其他處理不確定知識的方法來說更具客觀性，并且和其他分析方法有機(jī)結(jié)合，進(jìn)一步增強(qiáng)對不確定問題的處理能力。

定義1：信息系統(tǒng)S可表示為S=(U，A，V，f)，其中U是對象的非空有限集合，稱為論域;A是屬性的非空有限集合;V=∪a∈AVa，Va是屬性A的值域，f:U×A→V是一個(gè)信息函數(shù)，他為每個(gè)對象的每個(gè)屬性賦予一個(gè)信息值。

如果屬性集A可以分為條件屬性集C和決策屬性集D ，即C∪D = A ，C∩D =Ф，則該信息系統(tǒng)稱為決策系統(tǒng)或決策表，其中D 一般只含有一個(gè)屬性。

定義2：在知識表達(dá)系統(tǒng)S 中，對于一屬性集P∈A，對象x，y∈U，二元等價(jià)關(guān)系IND(P) ={(x，y)∈U×U | 所有的a∈P， f(x，a)=f(y，a)}稱為S 的不可分辨關(guān)系。不可分辨關(guān)系是一個(gè)等價(jià)關(guān)系，通過一個(gè)不可分辨關(guān)系，可以得到一個(gè)決策系統(tǒng)的劃分。

定義3：給定信息系統(tǒng)S=(U，A)，B∈A ，對B中的屬性a，如果IND(B)≠IND(B-{a})，則說屬性a是必要的(Indispensable)，否則稱a是不必要的(Dispensable)。

遺傳算法( Genetic Algorithm， GA)[3]起源于對生物系統(tǒng)進(jìn)行的計(jì)算機(jī)模擬研究，是模擬生物在環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)優(yōu)化概率搜索算法。它的流程主要模仿的 是生物遺傳進(jìn)化過程中的選擇、交叉和變異操作，從而完成對問題最優(yōu)解的自適應(yīng)搜索過程。流程主要包括染色體編碼、產(chǎn)生初始群體、計(jì)算適應(yīng)度、進(jìn)化操作等幾大部分。

遺傳算法的搜索過程是從一群初始節(jié)點(diǎn)開始搜索，而不是從單一的初始點(diǎn)開始搜索，這種機(jī)制意味著搜索過程可以有效地跳出局部極值點(diǎn)。既可以完成極值點(diǎn)領(lǐng)域內(nèi)解的求精，也可以在整個(gè)問題空間實(shí)施探索，得到問題全局最優(yōu)解的概率大大提高。

2 粗糙集與遺傳算法在數(shù)據(jù)挖掘中的應(yīng)用

粗糙集算法與遺傳算法結(jié)合，能有效地提高挖掘效果，具有實(shí)際應(yīng)用的可行性。其基本思想是：首先通過粗糙集對信息表中的數(shù)據(jù)缺損進(jìn)行處理；然后對于信息表中的數(shù)據(jù)，根據(jù)已定義的可辯識距陣，通過屬性簡約算法進(jìn)行屬性簡約和知識發(fā)現(xiàn)；最后對知識發(fā)現(xiàn)的規(guī)則通過遺傳算法進(jìn)行優(yōu)化，找出最主要的規(guī)則。主要包括以下幾個(gè)方面：

2.1 數(shù)據(jù)預(yù)處理

數(shù)據(jù)預(yù)處理用于對原始數(shù)據(jù)的采樣、收集、整理，對于不同途徑獲取來的數(shù)據(jù)不一定能夠得到有效的信息，所以數(shù)據(jù)的預(yù)處理是非常必要的。包括連續(xù)屬性的離散化和不完備數(shù)據(jù)的填補(bǔ)，由于粗糙集只能處理離散的數(shù)據(jù)，所以還必須對連續(xù)的數(shù)據(jù)離散化，而屬性離散化的關(guān)鍵在于選取合適的斷點(diǎn)對條件屬性進(jìn)行劃分[4]，如可采用基于屬性重要性的離散化算法。由于數(shù)據(jù)采集的不完整性，使數(shù)據(jù)庫中很大一部分?jǐn)?shù)據(jù)都存在缺失，因此對輸入的數(shù)據(jù)必須進(jìn)行必要的處理如采用均值法、頻率統(tǒng)計(jì)法等對數(shù)據(jù)進(jìn)行補(bǔ)齊。

2.2 屬性簡約

粗糙集處理決策表時(shí)，數(shù)據(jù)約簡是核心內(nèi)容，一般是約去過剩的條件屬性，用最少的屬性區(qū)分不同的決策，提供同樣多的信息，使決策表的決策屬性和條件屬性的依賴關(guān)系不發(fā)生變化。簡約后的屬性集稱為屬性的約簡集，約簡集通常不唯一，找到一個(gè)信息表中的約簡集不是在一個(gè)多項(xiàng)式時(shí)間里能夠解決的問題，求最小約簡集（含屬性個(gè)數(shù)最少的約簡集）同樣是一個(gè)困難的問題，實(shí)際上它是一個(gè)NP-hard問題，因此根據(jù)已定義的可辯識距陣，有如下的屬性簡約算法：

① 計(jì)算屬性表的可辯識距陣。

② 對于可辯識距陣中的所有取值為非空集合的元素Cij建立相應(yīng)的析取邏輯表達(dá)式。

③ 將所有析取邏輯表達(dá)式進(jìn)行合取運(yùn)算，得到一個(gè)合取范式。

④ 將合取范式轉(zhuǎn)換為析取范式形式。

⑤ 輸出屬性約簡結(jié)果，其中析取范式中的每個(gè)合取項(xiàng)對應(yīng)一個(gè)屬性約簡的結(jié)果，每個(gè)合取項(xiàng)中所包含的屬性組成的約簡后的條件屬性集合。

2.3 決策規(guī)則提取

經(jīng)過第二步屬性簡約后，屬性個(gè)數(shù)減少了，但是得出的規(guī)則數(shù)量依然可能過多，不利于得到用戶最想要，最重要的規(guī)則，因此我們會更希望關(guān)心具有較多共同特性的規(guī)則，必須把簡約后生成的規(guī)則集里那些具有大量共同特征的規(guī)則再次提取出來，面對這種優(yōu)化問題，遺傳算法是個(gè)強(qiáng)有力的工具。其步驟是編碼產(chǎn)生原始種群，計(jì)算個(gè)體適應(yīng)度，選擇個(gè)體，交叉，變異操作，然后一代一代進(jìn)化最后找出最優(yōu)解。

（1）編碼，是進(jìn)行遺傳算法的重要步驟，編碼方案的選取很大程度上決定于問題的性質(zhì)和要求，同時(shí)也決定了對隨后的遺傳算子的設(shè)計(jì)。如可以將數(shù)據(jù)離散化后的屬性值定義在2的n次方之間[5]，采用二進(jìn)制編碼方法對每個(gè)數(shù)字編碼，像屬性值3用編碼表示就是0011；

（2）產(chǎn)生初始種群。隨機(jī)選取一些個(gè)體作為初始種群；

（3）確定評價(jià)函數(shù)。數(shù)據(jù)挖掘的目的是挖掘出具有最多相同特征的規(guī)則，因此評價(jià)函數(shù)的選取時(shí)應(yīng)當(dāng)把能夠匹配簡約表中最多的屬性的規(guī)則評價(jià)為最優(yōu)規(guī)則；

（4）遺傳操作。交叉操作是將規(guī)則編碼的某幾位互相置換，變異操作是將規(guī)則編碼的某些二進(jìn)制位按位取反。這樣通過規(guī)則集中任意的兩兩組合會形成新的規(guī)則集。然后經(jīng)過每個(gè)規(guī)則的評價(jià)函數(shù)確定當(dāng)前的最優(yōu)規(guī)則，這樣經(jīng)歷數(shù)代遺傳之后就可得到相對最優(yōu)的規(guī)則。

3 公司錄取情況數(shù)據(jù)挖掘應(yīng)用實(shí)例

下面用一個(gè)實(shí)例來說明本文使用的數(shù)據(jù)挖掘方法。某公司每年都會收到大量的求職信息表，并從中雇用一定數(shù)量的員工，對于員工的雇用，公司以往都是通過面試及給領(lǐng)導(dǎo)的感覺來雇用的，因此公司希望能夠從以前的錄用中找出一個(gè)大體的評判標(biāo)準(zhǔn)以便于以后錄用時(shí)作為參考，由于以往幾年累計(jì)求職的員工太多，情況比較復(fù)雜，因此公司希望這個(gè)標(biāo)準(zhǔn)能夠簡單明了。通過本文提出的方法，可以很好的解決該公司的需求，以下以該公司求職人員的原始求職表中的一部分作為演示，“?”代表求職表中該屬性沒有寫明情況，如表1所示：

按屬性簡約的算法，通過決策表的可辯識距陣，我們可以得到算法第3步后的合取范式為：

F(d，e，f，a)=(e∨a)∧(d∨e∨a) ∧(d∨e) ∧(e∨f∨a) ∧(d∨e∨f) ∧(d∨e∨a) ∧(d∨e∨a) ∧(d∨e∨a) ∧(d∨a) ∧(e) ∧(e∨a) ∧(d∨e∨f∨a) ∧(d∨e∨f) ∧(d∨e∨f∨a) ∧(d∨e∨f) ∧(d∨e∨a)

其中每一個(gè)析取項(xiàng)對應(yīng)于可辯識距陣中的一個(gè)元素，d，e，f，a分別對應(yīng)屬性學(xué)歷、經(jīng)驗(yàn)、法語、儀表，按算法第4步簡化后可以得到F(d，e，f，a)=(e∧a) ∨(e∧d)。由此可見，在原始決策表給出的這部分信息中與決策有關(guān)的是d，e，a。

通過粗糙集的屬性約簡，可以得到以往公司錄用時(shí)真正看重的一些屬性，通過這些屬性，再用遺傳算法找出其中最主要的規(guī)則。例如約簡表中某一行在學(xué)歷、經(jīng)驗(yàn)、儀表上的值為201，則編碼就是10，00，01。隨機(jī)選取8個(gè)個(gè)體作為初始種群，評價(jià)函數(shù)以能夠匹配約簡表中最多行屬性的規(guī)則成為當(dāng)代的最優(yōu)規(guī)則。

算法定義為一個(gè)8元組：

SGA=（C，E，P0，M，Ф，Г，Ψ，T）

C表示對個(gè)體采用二進(jìn)制編碼；E表示個(gè)體適應(yīng)度評價(jià)函數(shù)f(x)；P0表示初始種群隨機(jī)選取的8個(gè)規(guī)則；Ф表示采用輪盤賭按比例選擇算子；Г表示中間位單點(diǎn)交叉算子；Ψ表示基本位變異算子；T表示執(zhí)行20代上述遺傳算法后停止。

最后得到最佳個(gè)體00，01，01，即學(xué)歷MBA，經(jīng)驗(yàn)水平一般，儀表良好的評判標(biāo)準(zhǔn)，凡在此標(biāo)準(zhǔn)附近或高于此標(biāo)準(zhǔn)的，可以考慮錄用。

4 結(jié)語

在數(shù)據(jù)挖掘中應(yīng)用粗糙集和遺傳算法，粗糙集可以解決數(shù)據(jù)不精確、不完整的問題，并進(jìn)行屬性簡約，遺傳算法可以從大量規(guī)則中提取出最優(yōu)的規(guī)則，提高了分析系統(tǒng)的效率。本文將粗糙集和遺傳算法在數(shù)據(jù)挖掘中相結(jié)合，給出實(shí)例說明該方法的可行性。在今后的研究中還將繼續(xù)結(jié)合其他的方法進(jìn)行研究，提高對知識的發(fā)現(xiàn)能力。

參考文獻(xiàn)：

[1] David Heikki Mannila， Padhraic Smyth. 數(shù)據(jù)挖掘原理[M].北京：機(jī)械工業(yè)出版社，2003.

[2] Pawlak Z. Rough Set[J].International Journal of Information and Computer Science，1982，11(5):314-356.

[3] 高雋，智能信息處理方法導(dǎo)論[M].北京：機(jī)械工業(yè)出版社，2004.

[4] 李紅梅，周桂紅，王克儉.基于粗糙集和遺傳算法的知識發(fā)現(xiàn)方法[J].計(jì)算機(jī)應(yīng)用，2007，8（1）：76-78.

[5] 胡域，張亦軍，楊冬梅.粗糙集結(jié)合遺傳算法在數(shù)據(jù)挖掘中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用，2006，6（26）：98-99.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文