邵曉艷，劉 寧，李玲玲，胡欣茹

（鄭州航空工業(yè)管理學(xué)院計(jì)算機(jī)科學(xué)與應(yīng)用系，河南鄭州 450015）

Ant－Miner算法改進(jìn)及在地震預(yù)測(cè)中的應(yīng)用①

邵曉艷，劉 寧，李玲玲，胡欣茹

（鄭州航空工業(yè)管理學(xué)院計(jì)算機(jī)科學(xué)與應(yīng)用系，河南鄭州 450015）

首先闡述了Ant－Miner算法的原理，然后從不同角度對(duì)Ant－Miner算法進(jìn)行研究分析，并針對(duì)該算法的不足之處提出了相應(yīng)的改進(jìn)和優(yōu)化方案。最后將經(jīng)過(guò)改進(jìn)的Ant－Miner算法應(yīng)用到地震預(yù)測(cè)中。結(jié)果證明優(yōu)化后的Ant－Miner算法比傳統(tǒng)C4．5分類(lèi)算法能達(dá)到更好的效果。

蟻群算法；分類(lèi)規(guī)則；地震預(yù)測(cè)

Abstract：The principle and realization of Ant－Miner algorithm are summarized firstly．Then the Ant－Miner algorithm is analyzed from different views，and an improving and optimizing method are proposed in order to overcome the problems existed in the algorithm．Finally，the improved Ant－Miner algorithm is used in earthquake prediction．The experiments show that，optimization algorithm can achieve better results than C4．5algorithm．

Key words：Ant colony algorithm；Classification rule；Earthquake prediction

0 引言

數(shù)據(jù)分類(lèi)在數(shù)據(jù)挖掘中是一項(xiàng)非常重要的任務(wù)?；谙伻核惴ǖ姆诸?lèi)研究是一種新型的挖掘算法，該算法訓(xùn)練分類(lèi)規(guī)則庫(kù)的過(guò)程實(shí)質(zhì)上也是從大的數(shù)據(jù)集中發(fā)現(xiàn)知識(shí)的過(guò)程。Parpinelli等人提出了最早的Ant－Miner系統(tǒng)［1］，其后國(guó)內(nèi)也有很多研究者對(duì)其進(jìn)行了深入的研究［2－5］。

本文首先分析Ant－Miner算法的工作原理，然后針對(duì)Ant－Miner算法的不足之處進(jìn)行改進(jìn)，最后將該算法應(yīng)用到地震預(yù)測(cè)中，以證明優(yōu)化后的算法比傳統(tǒng)C4．5分類(lèi)算法能達(dá)到更好的效果。

1 基于蟻群算法的分類(lèi)規(guī)則挖掘

求分類(lèi)規(guī)則就是要求出IF＜conditions＞THEN＜class＞。其中規(guī)則的conditions部分的形式是：terml and term2and term3…．．，每個(gè)term都是一個(gè)元組（attribute，operator，value）。

value是屬性，attribute是值域中的某個(gè)值，operator是比較運(yùn)算符；class部分則是預(yù)測(cè)滿(mǎn)足該條規(guī)則conditions部分的記錄所屬的類(lèi)別。

螞蟻構(gòu)造規(guī)則的過(guò)程分為三個(gè)階段：第一個(gè)階段是螞蟻從一條空規(guī)則開(kāi)始，重復(fù)選擇屬性節(jié)點(diǎn)到路徑上，直到得到一條完整的路徑，即一條分類(lèi)規(guī)則；第二個(gè)階段是進(jìn)行剪枝，以解決過(guò)渡擬合問(wèn)題；第三個(gè)階段是進(jìn)行信息素更新，對(duì)下一只螞蟻施加影響。

1．1 路徑選擇策略

螞蟻選擇路徑時(shí)依據(jù)兩個(gè)因素，一是該term上與問(wèn)題相關(guān)的啟發(fā)函數(shù)值；二是與路徑選擇歷史相關(guān)的信息素，即term以前被選擇的越多，term上的信息素值越大。

如termij的形式為Ai＝Vij。Ai是第i個(gè)屬性，Vij是第i個(gè)屬性的第j個(gè)值域，那么termij被選擇加入當(dāng)前的部分規(guī)則的概率由式（1）得到，每次都選擇概率最大的term加入當(dāng)前的部分規(guī)則：

其中ηij是termij上與問(wèn)題相關(guān)的啟發(fā)函數(shù)值；Γij（t）是termij上的信息素（時(shí)刻t）；α是屬性數(shù)目；bi是屬性i的值域個(gè)數(shù)；I是當(dāng)前的螞蟻所有未用過(guò)的屬性集合。

（1）啟發(fā)函數(shù)

式（1）中啟發(fā)函數(shù)ηij的構(gòu)造

其中，k是類(lèi)的數(shù)目，a是分析對(duì)象中的屬性個(gè)數(shù)；bi是對(duì)應(yīng)屬性i的值域個(gè)數(shù)。式（2）中infoTij的構(gòu)造

其中Tij是包含termij的記錄的集合，也就是屬性Ai的值為Vij的所有記錄的集合；｜Tij｜是集合Tij包含的記錄的數(shù)目；freqTij是集合Tij中所屬類(lèi)別為w的記錄的數(shù)目。

從式中可以看到，每個(gè)termij的infoTij值自始自終都是定值，因此在初始規(guī)則構(gòu)建時(shí)計(jì)算即可，不需要每次更新。還有特別要注意的是，如果Tij是一個(gè)空集合，也即不存在屬性Ai的值為Vij的記錄，那么此時(shí)應(yīng)該盡量避免此termij（Ai＝Vij）被選擇加入規(guī)則。這里可以設(shè)infoTij的值為最大值，如設(shè)infoTij＝log2（k），那么式（1）、（2）的值均為0，這就使termij成為最不可能被選中的term［1，5］。

（2）信息素

所有term的信息素都初始化為相同的值，式（1）中信息素的計(jì)算方法如下：

termij上的信息素初始化

其中a是挖掘?qū)ο笾械膶傩詡€(gè)數(shù)；bi對(duì)應(yīng)第i個(gè)屬性的值域個(gè)數(shù)；t＝0也即在t＝0時(shí)刻信息素的值。

信息素的更新策略可以描述如下。每構(gòu)造完一條規(guī)則后，需要修改所有term上的信息素，而下一個(gè)agent（ant）構(gòu)造規(guī)則進(jìn)行路徑選擇時(shí)依據(jù)的是本次修改過(guò)的新的信息素。修改信息素的過(guò)程包括兩部分，即削減所有未在本次所構(gòu)造規(guī)則中用到的term上的信息素，這步相當(dāng)于蟻群中信息素的揮發(fā)；同時(shí)增加出現(xiàn)在規(guī)則中的term上的信息素。對(duì)兩種情況的更新策略分別下：

其中，a是挖掘?qū)ο笾械膶傩詡€(gè)數(shù)；bi是對(duì)應(yīng)第i個(gè)屬性的值域個(gè)數(shù)；Q是對(duì)所構(gòu)造的規(guī)則優(yōu)劣（quality）的一個(gè)衡量值，對(duì)規(guī)則所涉及到的所有term的信息素增加量與該規(guī)則的質(zhì)量高低（quality）大小成正比。需要說(shuō)明的是，這里假設(shè)時(shí)間t是離散的，以整數(shù)單位計(jì)算，t就表示t時(shí)刻，t＋1即表示t的下一時(shí)刻。

1．2 規(guī)則構(gòu)造與規(guī)則剪枝

規(guī)則的conditions部分構(gòu)造完成后，接下來(lái)要構(gòu)造規(guī)則的class部分，就是給滿(mǎn)足規(guī)則conditions部分的對(duì)象定類(lèi)名，完成規(guī)則的最初構(gòu)建。為了盡量提高規(guī)則質(zhì)量，并避免“過(guò)匹配”現(xiàn)象，還要對(duì)規(guī)則進(jìn)行剪枝，去除一些冗余的term。這兩步的完成要本著使規(guī)則的quality值達(dá)到最大的原則。

構(gòu)造規(guī)則class部分的策略是：分別把所有的class賦給規(guī)則并計(jì)算規(guī)則的quality，最后確定使規(guī)則的quality達(dá)到最大值的class作為規(guī)則最終的class類(lèi)標(biāo)記。一條規(guī)則的quality的衡量標(biāo)準(zhǔn)如下：

其中，TruePos：被規(guī)則conditions部分覆蓋，所屬類(lèi)與規(guī)則class相同的記錄的數(shù)目；FalsePos：被規(guī)則conditions部分覆蓋，所屬類(lèi)與規(guī)則class不同的記錄的數(shù)目：FalseNeg：不被規(guī)則conditions部分覆蓋，類(lèi)別與規(guī)則class一致的記錄的數(shù)目；TrueNeg：不被規(guī)則覆蓋，類(lèi)別也與規(guī)則class不同的記錄的數(shù)目［3］。

對(duì)初步構(gòu)造完成的規(guī)則進(jìn)行剪枝的方法與其它分類(lèi)分析方法類(lèi)似：依次分別剪掉所有的term，分別計(jì)算剪掉之后規(guī)則的qualily，最終選擇剪掉后使規(guī)則的quality提高最多的某個(gè)term進(jìn)行剪枝，如此循環(huán)直到?jīng)]有一個(gè)term剪掉后可以使規(guī)則的quality提高，則表示規(guī)則剪枝完成。

至此，Ant－Miner最終完成了一條規(guī)則的構(gòu)造，然后進(jìn)入下一次構(gòu)造規(guī)則的過(guò)程。

1．3 訓(xùn)練集更新

當(dāng)所有agent都各自構(gòu)造規(guī)則完成后，有三部分工作要做：第一，選擇一條最佳路徑加入規(guī)則庫(kù)，作為本輪構(gòu)建規(guī)則所得的最終規(guī)則；第二，更新訓(xùn)練集，去除訓(xùn)練集中所有被該規(guī)則覆蓋的記錄，也就是用該規(guī)則進(jìn)行分類(lèi)預(yù)測(cè)，去除所有可以被規(guī)則正確分類(lèi)的記錄，然后把剩余的記錄集作為下輪蟻群構(gòu)造規(guī)則的初始訓(xùn)練集；第三，對(duì)該條規(guī)則所包含的term信息素進(jìn)行更新，計(jì)算如式（6）所示。

2 算法優(yōu)化

由Parpinelli等所提出來(lái)的這種Ant－Miner方法試驗(yàn)已經(jīng)證明可以達(dá)到較好的分類(lèi)效果。但是在信息素更新，路經(jīng)選擇方面還有不盡人意的地方。論文針對(duì)這些不足，提出了信息素更新策略的優(yōu)化、規(guī)則庫(kù)構(gòu)建過(guò)程的優(yōu)化以及該算法出現(xiàn)死鎖問(wèn)題的解決方案。

2．1 信息素更新策略的優(yōu)化

Ant－Miner中信息素的更新是在agent每次創(chuàng)建完規(guī)則后完成的，對(duì)信息素的修改如式（5）和（6），其中式（6）是對(duì)在新構(gòu)造的規(guī)則中出現(xiàn)的term信息素的修改方案，其中式中quality的計(jì)算如式（7）。這樣做存在兩個(gè)問(wèn)題：

第一，一條規(guī)則構(gòu)造完成后，不管規(guī)則的優(yōu)劣（quality）如何，所有包含在規(guī)則中的term的信息素都會(huì)增長(zhǎng)，那么這些term在以后構(gòu)建規(guī)則時(shí)肯定更容易被選擇。但是在實(shí)際應(yīng)用中，如果當(dāng)前構(gòu)造的規(guī)則質(zhì)量很差，就應(yīng)該設(shè)法減少所有出現(xiàn)在規(guī)則里的term的信息素，以使下次構(gòu)造規(guī)則時(shí)這些term不被選擇才有道理。同時(shí)還會(huì)導(dǎo)致的一個(gè)問(wèn)題是第一個(gè)agent構(gòu)建規(guī)則時(shí)選擇的term會(huì)被后來(lái)的ant重復(fù)選擇，這樣其它term被選擇添加到規(guī)則中的概率極小，這就導(dǎo)致算法過(guò)早收斂，使規(guī)則的質(zhì)量與ant的數(shù)目的關(guān)聯(lián)不大。

第二，未知類(lèi)別樣本用構(gòu)造好的規(guī)則庫(kù)進(jìn)行預(yù)測(cè)分類(lèi)時(shí)，只要樣本的各個(gè)屬性符合規(guī)則的條件部分，就被劃分為規(guī)則所預(yù)測(cè)的class。而那些不符合規(guī)則的條件部分的樣本則繼續(xù)搜索下一條規(guī)則，直到找到一條符合的規(guī)則為止。顯然，被規(guī)則覆蓋且確實(shí)屬于規(guī)則所預(yù)測(cè)的類(lèi)的樣本所占的比率是最重要的，也是衡量規(guī)則質(zhì)量的最重要的依據(jù)，而那些不被規(guī)則條件部分覆蓋的樣本數(shù)目其實(shí)是無(wú)關(guān)緊要的，所以我們?cè)谶@里修改規(guī)則質(zhì)量的衡量標(biāo)準(zhǔn)式（7）如式（7′），而修改式（6）如（6′）：

式中Q1的計(jì)算方法：

式（6′）中，一個(gè)term被選擇加入規(guī)則后并不一定信息素就會(huì)增加，這里限定了一個(gè)系數(shù)0．8，就是說(shuō)規(guī)則的質(zhì)量達(dá)到某個(gè)標(biāo)準(zhǔn)之后，該路徑上所選擇的tem的信息素才會(huì)增加；反之，如果所構(gòu)造的規(guī)則質(zhì)量很差，所選擇的term上的信息素反而會(huì)減少，而且規(guī)則的質(zhì)量越差，信息素減少的越多。

同時(shí)，式中用到的規(guī)則的衡量質(zhì)量用式（7′）來(lái)計(jì)算，即被規(guī)則前項(xiàng)覆蓋且被規(guī)則正確分類(lèi)的記錄的數(shù)目占所有被規(guī)則前項(xiàng)覆蓋的記錄數(shù)比率。這是因?yàn)橐粭l規(guī)則構(gòu)造完成后，能被規(guī)則的前項(xiàng)覆蓋，并分類(lèi)正確的準(zhǔn)確率是最重要的．至于沒(méi)有被規(guī)則前項(xiàng)覆蓋的記錄可以在后續(xù)挖掘中進(jìn)行規(guī)則提取，以對(duì)其正確分類(lèi)。所以這里強(qiáng)調(diào)了TruePos的作用。另外，式（6′）中，Q1－0．8的意義也就是用該規(guī)則進(jìn)行分類(lèi)正確率達(dá)到80%時(shí)才認(rèn)為該規(guī)則是一條理想的可用規(guī)則，否則，削減出現(xiàn)在該規(guī)則里的所有term的信息素值。

修改后的算法一方面強(qiáng)調(diào)了規(guī)則質(zhì)量，所構(gòu)建規(guī)則的質(zhì)量將決定規(guī)則中出現(xiàn)的term的信息素增加與否；另一方面也強(qiáng)調(diào)了能被規(guī)則condition部分覆蓋并能被規(guī)則正確分類(lèi)的樣本百分比的重要性。這兩部分優(yōu)化都是合理有效的。

2．2 規(guī)則庫(kù)構(gòu)建過(guò)程優(yōu)化

在Ant－Miner系統(tǒng)中，規(guī)則的構(gòu)建主要分為三部分：根據(jù)信息素和啟發(fā)函數(shù)值從高到低選擇term添加到規(guī)則中構(gòu)造規(guī)則的條件部分；選擇一個(gè)可以使規(guī)則的質(zhì)量達(dá)到最大值的類(lèi)別作為規(guī)則的類(lèi)標(biāo)記；削減所有不包含在規(guī)則中的term上的信息素，并根據(jù)規(guī)則質(zhì)量更新所有包含在規(guī)則早的term的信息素，以備下一次構(gòu)造規(guī)則時(shí)作為路徑選擇歷史信息使用，指導(dǎo)路徑選擇。

這樣做會(huì)導(dǎo)致的一個(gè)問(wèn)題是：term的信息素與各個(gè)類(lèi)別之間沒(méi)有直接關(guān)系。針對(duì)這個(gè)問(wèn)題的改進(jìn)分為兩部分：

（1）信息素不再是全局的，每個(gè)類(lèi)都對(duì)應(yīng)一張信息素表來(lái)記錄各個(gè)term與此類(lèi)別的相關(guān)程度。

（2）每構(gòu)造一條規(guī)則時(shí)不再?gòu)囊?guī)則的條件部分，而是從結(jié)果部分開(kāi)始。具體來(lái)說(shuō)，一條規(guī)則的構(gòu)造過(guò)程分為五步：

①?gòu)挠?xùn)練集中選擇一個(gè)類(lèi)別作為規(guī)則的后項(xiàng)。這步首先檢驗(yàn)剩余樣本數(shù)是否小于參數(shù)Max＿Uncovered＿Cases，如果小于，則規(guī)則提取完成，整個(gè)循環(huán)結(jié)束；否則，從樣本庫(kù)中選擇一個(gè)包含樣本數(shù)目最多的類(lèi)作為當(dāng)前要構(gòu)造的規(guī)則的后項(xiàng)。

②根據(jù)該類(lèi)別所對(duì)應(yīng)的信息素表和啟發(fā)函數(shù)值，不斷選擇term添加到規(guī)則的條件部分作為規(guī)則的前項(xiàng)。具體來(lái)說(shuō)就是，檢驗(yàn)該類(lèi)對(duì)應(yīng)的信息素表，按照式（1）計(jì)算各個(gè)termij被選擇加入當(dāng)前的規(guī)則的概率Pij。然后按照從大到小的概率依次添加到規(guī)則的條件部分，直到規(guī)則所覆蓋的樣本數(shù)小于Min＿Cases＿Per＿Rule。

③用相似于第1．3節(jié)中所描述的方法對(duì)規(guī)則進(jìn)行剪枝，依次剪掉規(guī)則中所有的term，并最終刪除能使規(guī)則的準(zhǔn)確度提高最多的term。但是，兩種剪枝辦法有個(gè)不同點(diǎn)：在第1．3節(jié)中，規(guī)則可以在剪枝過(guò)程中換類(lèi)標(biāo)記，只要令一個(gè)類(lèi)標(biāo)記可以使規(guī)則的質(zhì)量提高，但是，這里不允許更改類(lèi)標(biāo)記，只限在當(dāng)前類(lèi)標(biāo)記下能使規(guī)則提高的term，才會(huì)進(jìn)行剪枝，以提高規(guī)則的質(zhì)量?？梢钥闯?，更改后的剪枝辦法與經(jīng)典分類(lèi)分析辦法C4．5的剪枝策略類(lèi)似。至此，一條規(guī)則構(gòu)建完成。

④根據(jù)規(guī)則質(zhì)量更新該類(lèi)對(duì)應(yīng)的信息素表。

⑤循環(huán)上邊的過(guò)程直到所有agent都各自構(gòu)造完規(guī)則，則選出一條最好的規(guī)則作為此次所有agent共同構(gòu)造的雖好的規(guī)則，也相當(dāng)于螞蟻此次選擇中所找到的最好路徑。然后，修改規(guī)則所對(duì)應(yīng)類(lèi)標(biāo)記的信息素表，并把被構(gòu)造好的規(guī)則成功覆蓋的樣本從訓(xùn)練集中刪除。

循環(huán)此構(gòu)造過(guò)程直到訓(xùn)練集中的樣本數(shù)小于參數(shù)Max＿Uncovered＿Cases，則整個(gè)規(guī)則庫(kù)構(gòu)造完成。

這樣就解決了各個(gè)term上的信息素與各個(gè)具體的類(lèi)標(biāo)根本不相關(guān)的問(wèn)題，某個(gè)termij因?yàn)闃?gòu)造了class1增長(zhǎng)的信息素不會(huì)在構(gòu)造下一條類(lèi)標(biāo)為class2的規(guī)則時(shí)，直接作用到class2上，這就解決了因?yàn)槟硞€(gè)term與class1的關(guān)聯(lián)比較大而默認(rèn)為它與class2的關(guān)聯(lián)也比較大的問(wèn)題。

2．3 死鎖問(wèn)題及其解決方案

算法還有一個(gè)隱患就是可能會(huì)出現(xiàn)死鎖。通過(guò)試驗(yàn)可以發(fā)現(xiàn)，如果有某幾條記錄屬于同一類(lèi)，而且它們對(duì)應(yīng)的某幾個(gè)特征屬性的值比較一致，且與其他記錄的值不同，如term：A1＝V12，A3＝V22，A4＝V43，Class＝classl，也就是說(shuō)這幾個(gè)term可能與它們共同的類(lèi)標(biāo)記class1具有極強(qiáng)的關(guān)聯(lián)，這種情況下它們計(jì)算得到的啟發(fā)函數(shù)值肯定會(huì)比較大，也就是說(shuō)，它們更容易被選擇加入下一條要構(gòu)造的規(guī)則，期望的規(guī)則形式應(yīng)該為

If A1＝V12and A3＝V22and A4＝V43，then Class＝classl

但是，如果這幾條記錄的條數(shù)本身就不能達(dá)到Min＿Cases＿Per＿Rule，它們就不能被選出來(lái)構(gòu)建規(guī)則，那么就會(huì)出現(xiàn)一直選出幾個(gè)term，但是卻總是不能構(gòu)造規(guī)則的局面，算法陷入死循環(huán)，而無(wú)法繼續(xù)構(gòu)造規(guī)則。

本文采用逐步降低termij上的信息素的方法，以增加其他term被選擇的概率，使規(guī)則構(gòu)建的過(guò)程跳過(guò)這2條記錄。即如果算法中出現(xiàn)這種情況，則降低term上的信息素，以避免這種“死鎖”：

（1）在添加term時(shí)，規(guī)則所覆蓋的記錄數(shù)目小于Min＿Cases＿Per＿Rule；

（2）出現(xiàn)情況"l"時(shí)，規(guī)則仍然為空。

這種情況下降低當(dāng)前被選中的term的信息素，也就降低了下次選擇時(shí)它們被選擇的概率，算法可能轉(zhuǎn)而選擇別的term添加到規(guī)則的conditions中，有效地解決了“死鎖”問(wèn)題。

3 地震試驗(yàn)及性能分析

3．1 數(shù)據(jù)背景

本實(shí)驗(yàn)所選數(shù)據(jù)資料取自中國(guó)地震局編輯的“中國(guó)歷史強(qiáng)震目錄”、“中國(guó)近代地震目錄”和全球強(qiáng)震記錄。

全球強(qiáng)震主要分布在環(huán)太平洋地震帶和歐亞地震帶。根據(jù)全球的強(qiáng)震活動(dòng)與板塊邊界的分布以及丁國(guó)瑜院士對(duì)中國(guó)及其鄰近地區(qū)的活動(dòng)邊界的劃分，我們將全球分為16個(gè)強(qiáng)震活動(dòng)區(qū)，這些區(qū)域都分布在環(huán)太平洋地震帶和歐亞地震帶。

本文取1925－2003年的全球強(qiáng)震資料數(shù)據(jù)作為Ant－Miner算法的檢驗(yàn)。選1925－1993年問(wèn)的69個(gè)樣本作為訓(xùn)練集，然后選1994－2003年間的10年作為檢驗(yàn)樣本。所選數(shù)據(jù)的每一行的前16項(xiàng)分別是這16個(gè)強(qiáng)震區(qū)域在一年中的M≥7．0的地震次數(shù)Ni／10，當(dāng)Ni≥10時(shí)，取值為1；第17列是次年我國(guó)大陸是否發(fā)生7級(jí)以上強(qiáng)震的記錄，如果次年中國(guó)大陸發(fā)生地震，則取值為1，否則為0。

3．2 地震數(shù)據(jù)處理

數(shù)據(jù)預(yù)處理過(guò)程如下：

（1）離散化數(shù)據(jù)

由于數(shù)據(jù)的1～16列每列的值域都分布在0～1之間，如果直接用蟻群算法處理就會(huì)使訓(xùn)練過(guò)于分散而影響訓(xùn)練效果，這里先對(duì)數(shù)據(jù)集進(jìn)行分段處理：

IF dataset（i，j）＝＝0．0THEN，

dataset（i，j）＝0；

ELSEIF dataset（i，j）＞＝0．1AND dataset（i，j）＜＝0．2THEN，

dataset（i，j）＝1；

ELSEIF dataset（i，j）＞＝0．3AND dataset（i，j）＜＝0．4THEN，

dataset（i，j）＝2；

ELSEIF dataset（i，j）＞＝0．5THEN，

dataset（i，j）＝3；

ENDIF

（2）添加噪聲

這里，在數(shù)據(jù)集中加入了一行［1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，2］作為干擾樣本，設(shè)Max＿Uncovered＿Cases為1，Min＿Cases＿Per＿Rule為2。

3．3 預(yù)報(bào)結(jié)果

這里列出了蟻群算法訓(xùn)練的規(guī)則庫(kù)處理的分類(lèi)結(jié)果并把它與C4．5算法進(jìn)行比較。

部分規(guī)則：

［6，0，3，0，10，0，5，0，2，0，1，0，4，0，14，0，13，0，0］

［5，0，1，0，6，0，4，0，14，0，2，0，1］

［2，0，10，0，5，0，14，0，4，0，0］

［11，0，13，0，12，0，1］

［12，0，3，0，0］

［4，0，9，0，10，0，11，0，13，0，14，0，0］

其含義是，規(guī)則的2＊m－1（m＝1，2，…）位表示屬性的位數(shù)，規(guī)則的2＊m位表示第2＊m－1個(gè)屬性的取值，規(guī)則的最后一位表示若數(shù)據(jù)對(duì)象對(duì)應(yīng)項(xiàng)的值分別與規(guī)則中表示的相同時(shí)，規(guī)則應(yīng)該劃分到的類(lèi)。

表1 Ant－miner算法在地震預(yù)測(cè)上與C4．5算法的比較

表1表示了算法在地震數(shù)據(jù)上進(jìn)行分類(lèi)挖掘，建立規(guī)則庫(kù)，并在訓(xùn)練樣本上預(yù)測(cè)時(shí)與C4．5算法的結(jié)果比較。

由表1中可以看出，Ant－Miner與C4．5算法相比，預(yù)測(cè)準(zhǔn)確率顯然比C4．5算法要高，C4．5算法在這里的預(yù)測(cè)結(jié)果并不理想，而Ant－Miner算法則達(dá)到了較為滿(mǎn)意的結(jié)果。同時(shí)，在大數(shù)據(jù)量計(jì)算中規(guī)則條數(shù)已經(jīng)成為越來(lái)越引人注意的問(wèn)題，因?yàn)樘嗟囊?guī)則條數(shù)也會(huì)制約預(yù)測(cè)判斷的速度。這里Ant－Miner算法的規(guī)則條數(shù)比C4．5也有很大優(yōu)勢(shì)。

4 小結(jié)

論文首先分析了Ant－Miner算法的工作原理，然后針對(duì)Ant－Miner算法存在的不足，提出了合理的改進(jìn)方案。最后將經(jīng)過(guò)優(yōu)化的Ant－Miner算法應(yīng)用到地震預(yù)測(cè)中，實(shí)驗(yàn)證明優(yōu)化后的Ant－Miner算法比傳統(tǒng)C4．5分類(lèi)算法能達(dá)到更好的效果。

［1］ Rafael S Parpinelli，Heitor S Lopes，Alex A Freitas．Data Mining With an Ant Colony Optimization Algorithm［J］．IEEE transactions on evolutionary computing，2004，6（4）：481－494．

［2］ 朱慶保，楊志軍．基于變異和動(dòng)態(tài)信息素更新的蟻群優(yōu)化算法［J］．軟件學(xué)報(bào)，2004，（2）：185－192．

［3］ 吳斌，史忠植．一種基于蟻群算法的TSP問(wèn)題分段求解算法［J］．計(jì)算機(jī)學(xué)報(bào)，2001，24（12）：1328－1333．

［4］ 吳慶洪，張紀(jì)會(huì)，徐心和．具有變異特征的蟻群算法［J］．計(jì)算機(jī)研究與發(fā)展，1999，36（10）：1240－1245．

［5］ Rafael S Parpinelli，Heitor S Lopes，CEFET－PR，et al．An Ant Colony Algorithm for Classification Rule Discovery［M］．Idea Group Publishing，2002．

［6］ Dorigo M，Maniezzo V，Colorni A．The Ant system：optimization by a colony of Cooperating agents［J］．IEEE Transactions on Systems，Man，and Cybernetics，l996，26（1）：28－41．

［7］ 平建軍，馮向東，楊立明．地震影響空間危險(xiǎn)度及危險(xiǎn)區(qū)預(yù)測(cè)方法研究［J］．西北地震學(xué)報(bào)，2010，32（2）：162－168．

［8］ 劉小鳳，梅秀蘋(píng)，馮建剛．青藏高原北部地區(qū)地震基本活動(dòng)狀態(tài)定量評(píng)價(jià)［J］．西北地震學(xué)報(bào)，2011，33（2）：130－136．

［9］ 師旭超，郭志濤，韓陽(yáng)．基于支持向量機(jī)的砂土液化預(yù)測(cè)分析［J］．西北地震學(xué)報(bào)，2009，31（4）：363－366．

Earthquake Prediction Using Improved Ant－Miner Algorithm

SHAO Xiao－yan，LIU Ning，LI Ling－ling，HU Xin－ru

（Department of Computer Science and Application，Zhengzhou Institute of Aeronautic Industry Management，Henan 450015，China）

P315．72

A

1000－0844（2012）03－0215－05

10．3969／j．issn．1000－0844．2012．03．0215

2011－07－11

教育部新世紀(jì)優(yōu)秀人才支持計(jì)劃（2009）；河南省重點(diǎn)科技攻關(guān)計(jì)劃項(xiàng)目（112102210024）；河南省重點(diǎn)科技攻關(guān)計(jì)劃項(xiàng)目（112102310082）；2012年河南省科技發(fā)展計(jì)劃122400450333

邵曉艷（1977－），女（漢族），河南西平人，講師，研究方向：數(shù)據(jù)挖掘，地理信息系統(tǒng)．