奚中陽

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

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

1 相關概念

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

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

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

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

（1）找出所有頻繁項集：即找出所有支持度大于設定的最小支持度閾值的項目集。

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

1.3 遺傳算法

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

圖1

3 算法實現(xiàn)

3.1 編碼策略

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

3.2 適應度函數(shù)的設計

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

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

一個項集是否頻繁項集的唯一標準是：項集的支持度要大于用戶所給的最小支持度閾值（MinSupp）。因此適應度函數(shù)中最好包含項集的適應度和MinSupp，最好通過函數(shù)計算能分辨出支持度和MinSupp的大小關系。因此擬定群體中個體適應度函數(shù)為：

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

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

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

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

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

4 應用實例

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

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

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

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

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

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

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

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

5 結束語

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