基于改進(jìn)型數(shù)據(jù)挖掘模型的研究

奚中陽

摘 要：近年來在人工智能領(lǐng)域極具突出研究價值的是數(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ù)中的挖掘，遺傳算法有獨特的優(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ù)中同時發(fā)生的概率。假定是數(shù)據(jù)項的集合。給定一個交易數(shù)據(jù)庫D，定義支持度（support）為D中事務(wù)同時包含事件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）找出所有頻繁項集：即找出所有支持度大于設(shè)定的最小支持度閾值的項目集。

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

1.3 遺傳算法

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

圖1

3 算法實現(xiàn)

3.1 編碼策略

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

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

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

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

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

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

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

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

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

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

4 應(yīng)用實例

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

對于表 1 中的幾個屬性，季節(jié)分別用 1，2，3，4 表示；平均氣溫這一屬性，分別用 1～8 對應(yīng) 8 個不同的等級（酷寒，嚴(yán)寒，寒冷，涼，涼爽，溫暖，炎熱，高溫），其中每個等級均在一定的溫度范圍內(nèi)；降雨量分別用 1～3 對應(yīng) 3 個不同的等級（小，中，大）；日照分別用 1～3 對應(yīng) 3 個不同的等級（短，中，長）；而災(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)害：重澇>，其含義為：降雨量大且日照時間短的地區(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)大量有價值的信息，將其應(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é)合具體的實例提出了基于遺傳算法的關(guān)聯(lián)規(guī)則的提取算法。 并將其應(yīng)用到農(nóng)業(yè)氣象數(shù)據(jù)庫的災(zāi)害分析中，得到了較好的應(yīng)用。