基于改進型數據挖掘模型的研究

奚中陽

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

關鍵詞：數據挖掘；關聯規則； 遺傳算法

1 相關概念

1.1 關聯規則

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

1.2 關聯規則挖掘的過程

關聯規則的挖掘可以分為兩部分：

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

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

1.3 遺傳算法

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

圖1

3 算法實現

3.1 編碼策略

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

3.2 適應度函數的設計

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

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

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

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

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

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

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

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

4 應用實例

實驗數據來源于農業氣象數據庫，該數據庫信息如表1所示。

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

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

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

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

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

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

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

5 結束語

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