張子愷 齊航 王上 蔡仕偉 姚宇 李丹

(東北林業(yè)大學(xué)，哈爾濱，150040)

基于Apriori算法的森林蟲害預(yù)測(cè)方法1)

張子愷 齊航 王上 蔡仕偉 姚宇 李丹

(東北林業(yè)大學(xué)，哈爾濱，150040)

針對(duì)現(xiàn)階段對(duì)已出現(xiàn)森林蟲害數(shù)據(jù)未能完成全面、及時(shí)地統(tǒng)計(jì)，以及難以準(zhǔn)確預(yù)測(cè)森林蟲害爆發(fā)的潛在外來(lái)誘因的問(wèn)題，提出使用面向Web挖掘的主題網(wǎng)絡(luò)爬蟲搜集病蟲害相關(guān)數(shù)據(jù)，并利用大數(shù)據(jù)挖掘頻繁模式與關(guān)聯(lián)規(guī)則的Apriori算法，挖掘結(jié)果得到滿足最小支持度閾值的頻繁2項(xiàng)集，并進(jìn)一步從中篩選2種重要的特征子集，包括害蟲與寄主之間的頻繁模式，寄主與外來(lái)樹種之間的頻繁模式。解決了已出現(xiàn)的病蟲害數(shù)據(jù)難以統(tǒng)計(jì)的難題；同時(shí)預(yù)測(cè)出針對(duì)某一地區(qū)害蟲可能誘發(fā)森林蟲害的外來(lái)樹種。結(jié)果表明該方法能達(dá)到可靠、有效的森林蟲害預(yù)測(cè)目的。

Apriori算法；頻繁模式；特征子集；病蟲害預(yù)測(cè)

//Journal of Northeast Forestry University，2017,45(8)：93-96.

The experiment was conducted to solve the problem that the forest pest data failed to complete the comprehensive and timely statistics, and it is difficult to accurately predict the potential extrinsic incentive of forest pest outbreaks. It was proposed to use the web-based reptile for Web mining to collect pest and disease-related data, and use large data Apriori algorithm of mining frequent patterns and association rules to extract the frequent 2 itemsets in satisfying the minimum support thresholds, and two important feature subsets were selected including the frequent patterns between pests and hosts, and the host and alien species between the frequent patterns. The experiment solved the pests and diseases in statistics, and predicted the alien species from the induced forest pests in a certain area.

森林蟲害是我國(guó)森林災(zāi)害中常見的生物災(zāi)害，我國(guó)林木種類豐富，所以森林蟲害種類很多，實(shí)現(xiàn)統(tǒng)計(jì)與防治有較大的難度。同時(shí)又普遍存在區(qū)域性的樹種引進(jìn)種植現(xiàn)象，使得潛在蟲害爆發(fā)的可能性增大。Nair K S S[1]對(duì)引發(fā)外來(lái)樹種蟲害的蟲源因素和導(dǎo)致蟲害爆發(fā)的原因進(jìn)行了研究，結(jié)果顯示:當(dāng)在本地林業(yè)生態(tài)系統(tǒng)中引進(jìn)外來(lái)樹種，特別是當(dāng)害蟲遭遇與其原寄主親緣關(guān)系較近的樹種，例如同屬內(nèi)的不同樹種時(shí)，蟲害的爆發(fā)風(fēng)險(xiǎn)極大。所以，提取害蟲、寄主和同屬樹種間的相關(guān)性十分重要。Apriori算法[2]是數(shù)據(jù)挖掘領(lǐng)域挖掘頻繁模式及發(fā)掘關(guān)聯(lián)規(guī)則的重要應(yīng)用算法。常用于在大量數(shù)據(jù)集中發(fā)現(xiàn)相關(guān)性和關(guān)聯(lián)規(guī)則，提取隱含在大量數(shù)據(jù)集中不明顯的潛在聯(lián)系[3]。經(jīng)常用于商業(yè)銷售方面，但未見在林業(yè)領(lǐng)域的應(yīng)用。針對(duì)森林蟲害預(yù)測(cè)方法研究，首次提出使用Apriori算法。分析誘發(fā)森林蟲害的因素，結(jié)合林業(yè)信息數(shù)據(jù)頻繁模式的挖掘、蟲害相關(guān)特征子集的提取。在引進(jìn)外來(lái)樹種前，應(yīng)對(duì)當(dāng)?shù)乩ハx的區(qū)系、當(dāng)?shù)睾οx寄主、引進(jìn)樹種三者進(jìn)行相關(guān)性調(diào)查。預(yù)測(cè)外來(lái)樹種引進(jìn)時(shí)存在的潛在危險(xiǎn)，從而降低對(duì)分析人員的技術(shù)水平要求和時(shí)間成本。

1 Apriori算法

Apriori算法是Agrawal和Srikant R[4]于1994年提出的，為布爾關(guān)聯(lián)規(guī)則[5]挖掘頻繁項(xiàng)集的原創(chuàng)算法。算法實(shí)現(xiàn)數(shù)據(jù)挖掘包括2個(gè)基本步驟：連接和剪枝。首先是將頻繁項(xiàng)集從事物數(shù)據(jù)庫(kù)中挖掘出來(lái)，然后以頻繁項(xiàng)集為依據(jù)，生成強(qiáng)關(guān)聯(lián)規(guī)則。在挖掘頻繁項(xiàng)集時(shí)，必須滿足最小支持度閾值(Smin)。即，

S(A?B)=P(A∪B)。

同時(shí)滿足最小置信度閾值(Cmin)的規(guī)則為強(qiáng)關(guān)聯(lián)規(guī)則。即，

C(A?B)=P(B|A)=Cs/Cs,

1.1 算法原理

逐層搜索的迭代方法尋找頻繁項(xiàng)集是Apriori算法的關(guān)鍵和核心，Apriroi算法以滿足最小支持度閾值(Smin)來(lái)篩選候選項(xiàng)集得到頻繁項(xiàng)集，對(duì)于每個(gè)項(xiàng)的集合支持度計(jì)數(shù)都需要一次數(shù)據(jù)庫(kù)掃描。為了降低指數(shù)級(jí)增長(zhǎng)所需計(jì)算時(shí)間，同時(shí)提高頻繁項(xiàng)集逐層產(chǎn)生的效率，利用一種重要的先驗(yàn)性質(zhì)(Apriroriproperty)用于壓縮搜索空間。

先驗(yàn)性質(zhì)：頻繁項(xiàng)集的所有非空子集也一定是頻繁的。

根據(jù)定義，如果項(xiàng)集I不滿足最小支持度閾值Smin，則I不是頻繁的，即P(I)

1.2 算法流程

(1)連接步驟：連接Lk-1中兩個(gè)項(xiàng)集，得到候選集合Ck。假設(shè)Lk-1包含li和lj這兩個(gè)項(xiàng)集，li中的第j個(gè)項(xiàng)和li中的倒數(shù)第2項(xiàng)分別用li[j]和li[k-2]表示。為了簡(jiǎn)化分析過(guò)程，以按照字典順序存儲(chǔ)數(shù)據(jù)庫(kù)中的記錄為前提假設(shè)條件。用Lk-1∞Lk-1來(lái)表示Lk-1連接操作，表示如果l1和l2具有一樣的前(k-2)項(xiàng)，可以連接Lk-1中l(wèi)1和l2。為了確保項(xiàng)集的唯一性，必須滿足l1[k-1]

(2)剪枝步驟：從候選集合Ck，進(jìn)一步發(fā)現(xiàn)Lk。Lk的超集Ck中包含了全部k項(xiàng)集，其中還包括一些非頻繁項(xiàng)集的元素，即有Lk?Ck。如果侯選k項(xiàng)集中的任一子集不屬于Lk-1，則應(yīng)該從Ck中刪除這個(gè)侯選k項(xiàng)集。

2 森林蟲害預(yù)測(cè)

在隨著數(shù)據(jù)量的增大，挖掘頻繁項(xiàng)集能在大量數(shù)據(jù)中尋找他們之間的關(guān)系，在生活中有著廣泛的應(yīng)用場(chǎng)合。在商業(yè)銷售上，無(wú)監(jiān)督學(xué)習(xí)的Apriori可用于進(jìn)行相關(guān)的商業(yè)決策[7-8]；在保險(xiǎn)業(yè)務(wù)方面，如果出現(xiàn)不常見的索賠要求組合，則可能為欺詐，需要進(jìn)一步調(diào)查。

本地森林害蟲并不會(huì)引發(fā)嚴(yán)重蟲害，因?yàn)樗c寄主之間已經(jīng)形成了穩(wěn)定的關(guān)系。外來(lái)森林害蟲入侵到新的地區(qū)后;如果遇到與其原寄主親緣關(guān)系較近，尤其是同屬類內(nèi)的本地樹種時(shí)，常常發(fā)生嚴(yán)重的危害。這是因?yàn)榛谶M(jìn)化上的原因這些外來(lái)森林害蟲己經(jīng)具備對(duì)這些本地近源樹種的寄生侵害能力；但因?yàn)槿狈餐倪M(jìn)化歷程，本地樹種缺乏對(duì)這些害蟲的抵御能力，容易成為害蟲的適宜寄主，害蟲種群迅速增長(zhǎng)，導(dǎo)致災(zāi)害爆發(fā)[9]。

Apriori算法在森林蟲害預(yù)防分析中的應(yīng)用，主要是通過(guò)對(duì)森林蟲害歷史數(shù)據(jù)挖掘出頻繁2項(xiàng)集，通過(guò)提取出的頻繁2項(xiàng)集中去掉錯(cuò)誤和冗余的數(shù)據(jù)，找到包含以下2種關(guān)系的特征子集：(1)已知蟲害現(xiàn)象中的寄主和害蟲；(2)已知蟲害現(xiàn)象中的寄主和與原寄主親緣關(guān)系較近的外地樹種。

通過(guò)對(duì)提取特征子集，篩選了最有可能誘發(fā)森林蟲害的樹種、昆蟲組合。為林業(yè)領(lǐng)域種植提供決策支持[10]，降低森林蟲害發(fā)生的風(fēng)險(xiǎn)。

2.1 數(shù)據(jù)的收集

本文提出的研究方法中，主要包括兩部分?jǐn)?shù)據(jù)：蟲害文章數(shù)據(jù)，林業(yè)樹種、蟲害元數(shù)據(jù)。其中，(1)蟲害文章數(shù)據(jù)是通過(guò)單機(jī)網(wǎng)絡(luò)爬蟲森林蟲害相關(guān)數(shù)據(jù)庫(kù)獲得；(2)林業(yè)樹種、蟲害元數(shù)據(jù)是通過(guò)搜集林業(yè)主題網(wǎng)站和之前的構(gòu)建林業(yè)領(lǐng)域數(shù)據(jù)庫(kù)獲得，存放在本機(jī)[11]。蟲害文章數(shù)據(jù)中的信息主要包括文章編號(hào)、文章標(biāo)題、文章摘要、摘要關(guān)鍵詞等。林業(yè)樹種、蟲害元數(shù)據(jù)中的信息主要包括物種編號(hào)、物種名稱等。

通過(guò)搜集互聯(lián)網(wǎng)有關(guān)森林蟲害相關(guān)文章24 000條，使用Paoding分詞包、中科院詞典進(jìn)行分詞得到關(guān)鍵詞。各項(xiàng)存于數(shù)據(jù)庫(kù)，部分如下表1所示。

表1 森林蟲害文章數(shù)據(jù)

通過(guò)搜集林業(yè)主題網(wǎng)站和已經(jīng)構(gòu)建的林業(yè)領(lǐng)域數(shù)據(jù)庫(kù)獲得。各項(xiàng)存于數(shù)據(jù)庫(kù)，部分如下表2所示。

2.2 實(shí)驗(yàn)數(shù)據(jù)預(yù)處理及建立事務(wù)數(shù)據(jù)庫(kù)

表2 樹種和蟲害元數(shù)據(jù)

研究所涉及的數(shù)據(jù)挖掘的Apriori算法結(jié)合Java語(yǔ)言進(jìn)行應(yīng)用系統(tǒng)開發(fā)，在考慮合理使用計(jì)算機(jī)內(nèi)存的前提下，采用鏈表結(jié)構(gòu)組織森林蟲害事務(wù)數(shù)據(jù)，盡量減少內(nèi)存消耗。部分如下表3所示。

表3 森林蟲害事務(wù)數(shù)據(jù)

3 結(jié)果與分析

基于Apriori算法在森林蟲害預(yù)測(cè)方法研究所建立的系統(tǒng)利用MySQL數(shù)據(jù)庫(kù)、Python語(yǔ)言爬蟲、Java語(yǔ)言系統(tǒng)開發(fā)。所有試驗(yàn)數(shù)據(jù)基于雙核CPU 2.2 GHz以及4 G內(nèi)存，并運(yùn)行在Window 7操作系統(tǒng)之上。

根據(jù)表3的事務(wù)數(shù)據(jù)庫(kù)數(shù)據(jù)(D)，該數(shù)據(jù)庫(kù)有9個(gè)事務(wù)，即|D|=9。實(shí)驗(yàn)過(guò)程如圖1所示。

(1)在算法的第一次迭代時(shí)，每個(gè)項(xiàng)都屬于候選1項(xiàng)集的集合C1。算法簡(jiǎn)單的掃描所有事務(wù)，對(duì)每個(gè)項(xiàng)出現(xiàn)的次數(shù)計(jì)數(shù)。

(2)設(shè)定最小支持度計(jì)數(shù)閾值為2，即Smin=2?？梢源_定頻繁1項(xiàng)集集合L1。

(4)掃描D中事務(wù)，累計(jì)C2中每個(gè)候選項(xiàng)集的支持度計(jì)數(shù)，其中滿足最小支持度計(jì)數(shù)的為頻繁2項(xiàng)集合L2。

圖1 森林蟲害事務(wù)數(shù)據(jù)庫(kù)產(chǎn)生頻繁2項(xiàng)集過(guò)程

本次試驗(yàn)采用24 000條森林蟲害文章數(shù)據(jù)作為提取森林蟲害事務(wù)數(shù)據(jù)的數(shù)據(jù)集。根據(jù)研究課題，在選取數(shù)據(jù)集的過(guò)程中也考慮了復(fù)雜度以及在數(shù)據(jù)數(shù)量上能夠達(dá)到普遍性的要求。

試驗(yàn)結(jié)果是針對(duì)森林蟲害事務(wù)數(shù)據(jù)庫(kù)，挖掘?qū)Ρ菊n題研究?jī)r(jià)值較大的頻繁2項(xiàng)集，為方便計(jì)算，用0～100%間的值而不是0～1.0間的值表示支持度，且預(yù)先定義最小支持度閾值Smin=2.00%。

從表4中可以看出，在頻繁2項(xiàng)集挖掘得到的部分結(jié)果中，包含了進(jìn)行蟲害預(yù)測(cè)需要的兩類有研究?jī)r(jià)值的頻繁模式，包括：(1)已知蟲害現(xiàn)象中的寄主和害蟲；(2)已知蟲害現(xiàn)象中的寄主和與原寄主親緣關(guān)系較近的外地樹種。

其中第一類頻繁模式挖掘搜集并統(tǒng)計(jì)了已發(fā)生的森林蟲害；第二類頻繁模式統(tǒng)計(jì)了親緣關(guān)系較近的樹種，可以結(jié)合已經(jīng)出現(xiàn)的蟲害寄主，預(yù)測(cè)潛在可能發(fā)生的蟲害。

表4 滿足最小支持度閾值的2項(xiàng)集部分結(jié)果

表5給出了試驗(yàn)結(jié)果中部分外來(lái)樹種可能會(huì)誘發(fā)本地森林蟲害的部分?jǐn)?shù)據(jù)。從預(yù)測(cè)結(jié)果來(lái)看，蕭氏松莖象初始都沒(méi)有引起注意或被發(fā)現(xiàn)定名，是在引進(jìn)我國(guó)引進(jìn)北美松樹樹種如濕地松后[12]，1988年我國(guó)在江西省吉安市安?？h武功山林場(chǎng)首次被發(fā)現(xiàn)，逐漸擴(kuò)散蔓延。這說(shuō)明外來(lái)樹種引進(jìn)種植確實(shí)是森林蟲害爆發(fā)的潛在誘因。蘭矩瘤蠣蚧是一種在我國(guó)南方部分地區(qū)被發(fā)現(xiàn)的主要以香樟作為寄主的害蟲，通過(guò)Apriori算法挖掘出香樟與楠屬植物之間的頻繁模式，從而預(yù)測(cè)楠屬植物如金絲楠可能會(huì)誘發(fā)新的森林蟲害。其余幾種害蟲各自也都對(duì)應(yīng)可能誘發(fā)森林蟲害的外來(lái)樹種，例如白蠟窄吉丁蟲是在我國(guó)引進(jìn)北美白蠟樹種時(shí)被命名發(fā)現(xiàn)，對(duì)于花曲柳和雪柳同樣也存在著潛在的誘發(fā)蟲害的可能性。

表5 不同樹種森林蟲害預(yù)測(cè)部分結(jié)果

4 結(jié)束語(yǔ)

本文首次提出了在森林蟲害預(yù)測(cè)時(shí)使用Apriori算法，該方法有以下特點(diǎn)：(1)實(shí)現(xiàn)了挖掘和統(tǒng)計(jì)已出現(xiàn)的大部份森林蟲害的功能；(2)引入相關(guān)性分析解決了在引進(jìn)種植外來(lái)樹種時(shí)預(yù)測(cè)潛在可能爆發(fā)的森林蟲害問(wèn)題。(3)經(jīng)過(guò)可視化處理使得大量數(shù)據(jù)得以直觀的展示，易于分析、理解。但是沒(méi)有考慮算法本身的時(shí)間特性，該方法在分析中存在先天缺陷。以后將針對(duì)該算法的改進(jìn)主要集中在壓縮候選項(xiàng)集(尤其是的選擇決定了挖掘的性能)和減少掃描數(shù)據(jù)庫(kù)次數(shù)兩方面。例如Parketal.提出了使用哈希散列技術(shù)壓縮候選項(xiàng)集[13]；AgrawalR[2]提出的AprioriHybrid算法；以及在分布式和并行環(huán)境下發(fā)掘關(guān)聯(lián)規(guī)則的分布式挖掘算法。甚至改變使用其他算法進(jìn)行優(yōu)化，例如使用垂直數(shù)據(jù)格式[14]的FP-growth的頻繁模式增長(zhǎng)樹算法[15]。提高其在實(shí)際應(yīng)用中的分析能力?？傮w上講，該方法為森林蟲害的分析和預(yù)防提供了一種簡(jiǎn)易、有效的途徑。

[1]NAIRKSS.Pestoutbreaksintropicalforestplantations:isthereagreaterriskforexotictreespecies[M].Jakarta:CenterforInternationalForestryResearch,2001.

[3]AWADALLAMHA,ELFARSG.Aggregatefunctionbasedenhancedapriorialgorithmforminingassociationrules[J].InternationalJournalofComputerScienceIssues,2012,9(3):277-287.

[4]AGRAWALR,SRIKANTR.Miningsequentialpatterns[J].EleventhInternationalConferenceonDataEngineering,1995,31(6):3-14.

[5]KABIRMMJ,XUS,KANGBH,etal.AnewmultipleseedsbasedgeneticalgorithmfordiscoveringasetofiInterestingbooleanassociationrules[J].ExpertSystemswithApplications,2017,74:55-69.

[6]HANJ,KAMBERM,PEIJ.Datamining:conceptsandtechniquesconceptsandtechniques[J].DataMiningConceptsModelsMethods&AlgorithmsSecondEdition,2011,5(4):1-18.

[7]MATF，JAINAK.Unsupervisedlearningoffinitemixturemodels[J].IEEETransactionsonPatternAnalysis&MachineIntelligence,2002,24(3):381-396.

[8]SENGJL,CHENTC.Ananalyticapproachtoselectdataminingforbusinessdecision[J].ExpertSystemswithApplications,2010,37(12):8042-8057.

[9] 趙同海.從昆蟲與植物的進(jìn)化關(guān)系看當(dāng)今林業(yè)害蟲的發(fā)生與治理對(duì)策[C]//第二屆中國(guó)林業(yè)學(xué)術(shù)大會(huì)—S6森林昆蟲與自然調(diào)控論文集.北京，2009.

[10]KOHAVIR.Thepowerofdecisiontables[C]//NADLL,STEFANW.MachineLearning:ECML-95.Greece: 8thEuropeanConferenceonMachineLearningHeraclion,1995.

[11] 劉漢興,劉財(cái)興.主題爬蟲的搜索策略研究[J].計(jì)算機(jī)工程與設(shè)計(jì),2008,29(12):3160-3162.

[12] 羅永松,孫江華.蕭氏松莖象生態(tài)控制初探[J].中國(guó)森林病蟲,2004,23(6):37-39.

[13]PARKJS,CHENMS,YUPS.Aneffectivehash-basedalgorithmforminingassociationrules[M]SanJose:ACMSIGMODRecord,1995.

[14] 陳偉.使用垂直數(shù)據(jù)格式挖掘頻繁項(xiàng)集[J].微型機(jī)與應(yīng)用,2011,30(18):6-7.

[15] 李洪波,周莉,張吉贊.用垂直數(shù)據(jù)格式構(gòu)建FP增長(zhǎng)樹的算法[J].計(jì)算機(jī)工程與應(yīng)用,2009,45(8):161-164.

Forest Pest Prediction Method with Apriori Algorithm//

Zhang Zikai, Qi Hang, Wang Shang, Cai Shiwei, Yao Yu, Li Dan

(Northeast Forestry University, Harbin 150040, P. R. China)

Apriori algorithm; Frequent pattern; Feature subset; Pest prediction

張子愷，男，1996年8月生，東北林業(yè)大學(xué)信息與計(jì)算機(jī)工程學(xué)院，本科生。E-mail：zhangzikai_nefu@163.com。

李丹，東北林業(yè)大學(xué)信息與計(jì)算機(jī)工程學(xué)院，副教授。E-mail：ld@nefu.edu.cn。

2017年4月20日。

S763；TP311.13

害文章數(shù)據(jù)的各條記錄中匹配林業(yè)樹種、蟲害元數(shù)據(jù)各條記錄中物種名稱的字符串，得到所有

與物種編號(hào)和映射關(guān)系。并存入新建的森林蟲害事務(wù)數(shù)據(jù)庫(kù)中，作為Aprior算法的輸入。

1)林業(yè)公益性行業(yè)科研專項(xiàng)(201504307-03)。

責(zé)任編輯：潘 華。