奚中陽

摘 要：近年來在人工智能領(lǐng)域極具突出研究價(jià)值的是數(shù)據(jù)挖掘技術(shù)。數(shù)據(jù)挖掘技術(shù)就是從大量的無規(guī)則的數(shù)據(jù)中提取出潛在的人們感興趣的知識。提取出的知識表現(xiàn)形式可以為概念、規(guī)則、規(guī)律、模式等等。目前數(shù)據(jù)挖掘算法有許多種，如經(jīng)典的Apriori算法，F(xiàn)P-Tree等。而遺傳算法自1975年由J.Holland提出以來，因其結(jié)構(gòu)簡單，采用模擬自然選擇，適用于解決非線性問題，對于解決存在大量的無序的數(shù)據(jù)中的挖掘，遺傳算法有獨(dú)特的優(yōu)勢。本文基于遺傳算法的優(yōu)勢，采用遺傳算法進(jìn)行關(guān)聯(lián)規(guī)則的挖掘。

關(guān)鍵詞：數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則； 遺傳算法

1 相關(guān)概念

1.1 關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則是用來發(fā)現(xiàn)一組數(shù)據(jù)中同時(shí)發(fā)生的概率。假定是數(shù)據(jù)項(xiàng)的集合。給定一個(gè)交易數(shù)據(jù)庫D，定義支持度（support）為D中事務(wù)同時(shí)包含事件A與事件B的百分比；定義置信度（confidence）為D中事務(wù)在已經(jīng)包含事件A的情況下，包含Y的百分比，即條件概率。如果滿足設(shè)定的最小支持度閾值和最小置信度閾值，則認(rèn)為所得到的規(guī)則是潛在有用的。

1.2 關(guān)聯(lián)規(guī)則挖掘的過程

關(guān)聯(lián)規(guī)則的挖掘可以分為兩部分：

（1）找出所有頻繁項(xiàng)集：即找出所有支持度大于設(shè)定的最小支持度閾值的項(xiàng)目集。

（2）由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則；即通過第一步中得到的頻繁項(xiàng)集中選取置信度大于給定的最小置信度閾值。

1.3 遺傳算法

遺傳算法是一種模擬生物優(yōu)勝劣汰自然選擇與遺傳機(jī)理的隨機(jī)搜索算法。相比于傳統(tǒng)的搜索算法，遺傳算法隨機(jī)產(chǎn)生一組稱為種群的初始解。種群中的每個(gè)個(gè)體都是問題中的一個(gè)解，稱為染色體。染色體通過不斷的選擇，交叉，變異等操作產(chǎn)生優(yōu)良個(gè)體。這樣，經(jīng)過若干代之后，算法收斂于最好的染色體，它很可能就是問題的最優(yōu)解或次優(yōu)解。遺傳算法的結(jié)構(gòu)如圖1所示：

圖1

3 算法實(shí)現(xiàn)

3.1 編碼策略

對于參數(shù)比較多的問題，我們可以采用多參數(shù)編碼技術(shù)，其基本思路：把每個(gè)參數(shù)先進(jìn)行編碼得到子串，再把這些子串連成一個(gè)完整的染色體，一個(gè)染色體代表一個(gè)關(guān)聯(lián)規(guī)則，作為數(shù)據(jù)挖掘的對象。 在此采用了二進(jìn)制編碼技術(shù)。

3.2 適應(yīng)度函數(shù)的設(shè)計(jì)

由于遺傳算法的針對性很強(qiáng)，每一個(gè)遺傳算法的實(shí)現(xiàn)都是基于某一個(gè)具體的問題，在遺傳算法總的框架不變的情況下，針對這個(gè)具體的問題采用構(gòu)造一個(gè)“好”的適應(yīng)度函數(shù)至關(guān)重要，直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解。

對于關(guān)聯(lián)規(guī)則挖掘，首先要形成頻繁項(xiàng)集，衡量的標(biāo)準(zhǔn)只有支持度。支持度是覆蓋項(xiàng)集的事務(wù)的數(shù)目在事務(wù)數(shù)據(jù)庫所有事務(wù)數(shù)目中所占的比例。

一個(gè)項(xiàng)集是否頻繁項(xiàng)集的唯一標(biāo)準(zhǔn)是：項(xiàng)集的支持度要大于用戶所給的最小支持度閾值（MinSupp）。因此適應(yīng)度函數(shù)中最好包含項(xiàng)集的適應(yīng)度和MinSupp，最好通過函數(shù)計(jì)算能分辨出支持度和MinSupp的大小關(guān)系。因此擬定群體中個(gè)體適應(yīng)度函數(shù)為：

Fitness（X） = X代表項(xiàng)集的支持度/最小支持度閾值MinSupp。

3.3 選擇算子、交叉算子、變異算子的確定

選擇算子最常用的是基于適應(yīng)度比例的選擇，如賭輪選擇。而根據(jù)賭輪選擇的特點(diǎn)，個(gè)體被選中的概率與其適應(yīng)度占群體適應(yīng)度總和的比例成正比，那么就有可能出現(xiàn)這樣一種情況：初始群體中少數(shù)適應(yīng)度較大的超級個(gè)體，在下一代中會得到較高的復(fù)制概率，它們在隨后進(jìn)化的少數(shù)幾代內(nèi)將會統(tǒng)治整個(gè)群體。賭輪選擇在進(jìn)化開始時(shí)的選擇壓力過大是導(dǎo)致遺傳算法早熟的一個(gè)主要原因。另外，當(dāng)進(jìn)化終了時(shí)，同一群體中不同個(gè)體之間的適應(yīng)度差異變得很小，其選擇概率相近，使得選擇趨于隨機(jī)選擇，可能使遺傳算法失去進(jìn)化能力。具體對于關(guān)聯(lián)規(guī)則的挖掘，兩個(gè)適應(yīng)度很高的個(gè)體，未必會繁殖出一個(gè)高適應(yīng)度的個(gè)體。所以，雖然賭輪盤選擇是遺傳算法中非常常用的一種選擇算子，但并不適合于本文的問題求解。

因此擬采用的選擇操作是將適應(yīng)度值大于1的規(guī)則都遺傳下來，也就是說，只要滿足要求的規(guī)則都將被保留下來。這與一般的選擇方法有所區(qū)別，這里并沒有使用選擇概率，而是只要超過用戶規(guī)定閾值的規(guī)則都會被選擇。

交叉算子及變異算子由于采用動態(tài)參數(shù)時(shí)導(dǎo)致計(jì)算量大，故采用經(jīng)驗(yàn)值，從而減少算法運(yùn)行時(shí)間。

4 應(yīng)用實(shí)例

實(shí)驗(yàn)數(shù)據(jù)來源于農(nóng)業(yè)氣象數(shù)據(jù)庫，該數(shù)據(jù)庫信息如表1所示。

對于表 1 中的幾個(gè)屬性，季節(jié)分別用 1，2，3，4 表示；平均氣溫這一屬性，分別用 1～8 對應(yīng) 8 個(gè)不同的等級（酷寒，嚴(yán)寒，寒冷，涼，涼爽，溫暖，炎熱，高溫），其中每個(gè)等級均在一定的溫度范圍內(nèi)；降雨量分別用 1～3 對應(yīng) 3 個(gè)不同的等級（小，中，大）；日照分別用 1～3 對應(yīng) 3 個(gè)不同的等級（短，中，長）；而災(zāi)害分別用 1～5 對應(yīng) 5 種不同的自然災(zāi)害（正常，干旱，澇，重澇和冷凍）。轉(zhuǎn)換后并利用前面提出的算法，在農(nóng)業(yè)氣象數(shù)據(jù)庫的基礎(chǔ)上對氣候與自然災(zāi)害間的關(guān)系進(jìn)行了挖掘，挖掘產(chǎn)生的部分規(guī)則如下：

<0031>∥><4>（21% support，100% confidence）

即：<降雨量：大，日照：短>∥> <自然災(zāi)害：重澇>，其含義為：降雨量大且日照時(shí)間短的地區(qū)中有21%地區(qū)容易發(fā)生澇災(zāi)。

<071>∥><02>（18% support，90% confidence）

即：<溫度：炎熱，降雨量：小>∥> <自然災(zāi)害：干旱>，其含義為：天氣炎熱并且降雨量非常少的地區(qū)中有 18%容易發(fā)生干旱現(xiàn)象。

<140>∥><05>（30% support，90% confidence）

即：<季節(jié)：冬季，溫度：涼>∥><自然災(zāi)害：冷凍>，其含義為：在冬季并且地面溫度在 0 度以下的地區(qū)中有 30%容易發(fā)生冷凍災(zāi)害。通過對農(nóng)業(yè)氣象數(shù)據(jù)庫關(guān)聯(lián)規(guī)則的挖掘，可以發(fā)現(xiàn)大量有價(jià)值的信息，將其應(yīng)用于農(nóng)業(yè)氣象災(zāi)害的分析中，從而能夠提前防災(zāi)減災(zāi)，加大物資投入力度，以達(dá)到高產(chǎn)高效益的目的。

5 結(jié)束語

本文對關(guān)聯(lián)規(guī)則的挖掘算法進(jìn)行研究，提出了將遺傳算法應(yīng)用于關(guān)聯(lián)規(guī)則的提取，并結(jié)合具體的實(shí)例提出了基于遺傳算法的關(guān)聯(lián)規(guī)則的提取算法。 并將其應(yīng)用到農(nóng)業(yè)氣象數(shù)據(jù)庫的災(zāi)害分析中，得到了較好的應(yīng)用。