基于Apriori算法的森林虫害预测方法1)

2017-09-03张子恺齐航王上蔡仕伟姚宇李丹

东北林业大学学报 2017年8期

关键词：项集虫害害虫

张子恺齐航王上蔡仕伟姚宇李丹

(东北林业大学，哈尔滨，150040)

基于Apriori算法的森林虫害预测方法1)

张子恺齐航王上蔡仕伟姚宇李丹

(东北林业大学，哈尔滨，150040)

针对现阶段对已出现森林虫害数据未能完成全面、及时地统计，以及难以准确预测森林虫害爆发的潜在外来诱因的问题，提出使用面向Web挖掘的主题网络爬虫搜集病虫害相关数据，并利用大数据挖掘频繁模式与关联规则的Apriori算法，挖掘结果得到满足最小支持度阈值的频繁2项集，并进一步从中筛选2种重要的特征子集，包括害虫与寄主之间的频繁模式，寄主与外来树种之间的频繁模式。解决了已出现的病虫害数据难以统计的难题；同时预测出针对某一地区害虫可能诱发森林虫害的外来树种。结果表明该方法能达到可靠、有效的森林虫害预测目的。

Apriori算法；频繁模式；特征子集；病虫害预测

//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.

森林虫害是我国森林灾害中常见的生物灾害，我国林木种类丰富，所以森林虫害种类很多，实现统计与防治有较大的难度。同时又普遍存在区域性的树种引进种植现象，使得潜在虫害爆发的可能性增大。Nair K S S[1]对引发外来树种虫害的虫源因素和导致虫害爆发的原因进行了研究，结果显示:当在本地林业生态系统中引进外来树种，特别是当害虫遭遇与其原寄主亲缘关系较近的树种，例如同属内的不同树种时，虫害的爆发风险极大。所以，提取害虫、寄主和同属树种间的相关性十分重要。Apriori算法[2]是数据挖掘领域挖掘频繁模式及发掘关联规则的重要应用算法。常用于在大量数据集中发现相关性和关联规则，提取隐含在大量数据集中不明显的潜在联系[3]。经常用于商业销售方面，但未见在林业领域的应用。针对森林虫害预测方法研究，首次提出使用Apriori算法。分析诱发森林虫害的因素，结合林业信息数据频繁模式的挖掘、虫害相关特征子集的提取。在引进外来树种前，应对当地昆虫的区系、当地害虫寄主、引进树种三者进行相关性调查。预测外来树种引进时存在的潜在危险，从而降低对分析人员的技术水平要求和时间成本。

1 Apriori算法

Apriori算法是Agrawal和Srikant R[4]于1994年提出的，为布尔关联规则[5]挖掘频繁项集的原创算法。算法实现数据挖掘包括2个基本步骤：连接和剪枝。首先是将频繁项集从事物数据库中挖掘出来，然后以频繁项集为依据，生成强关联规则。在挖掘频繁项集时，必须满足最小支持度阈值(Smin)。即，

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

同时满足最小置信度阈值(Cmin)的规则为强关联规则。即，

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

1.1 算法原理

逐层搜索的迭代方法寻找频繁项集是Apriori算法的关键和核心，Apriroi算法以满足最小支持度阈值(Smin)来筛选候选项集得到频繁项集，对于每个项的集合支持度计数都需要一次数据库扫描。为了降低指数级增长所需计算时间，同时提高频繁项集逐层产生的效率，利用一种重要的先验性质(Apriroriproperty)用于压缩搜索空间。

先验性质：频繁项集的所有非空子集也一定是频繁的。

根据定义，如果项集I不满足最小支持度阈值Smin，则I不是频繁的，即P(I)

1.2 算法流程

(1)连接步骤：连接Lk-1中两个项集，得到候选集合Ck。假设Lk-1包含li和lj这两个项集，li中的第j个项和li中的倒数第2项分别用li[j]和li[k-2]表示。为了简化分析过程，以按照字典顺序存储数据库中的记录为前提假设条件。用Lk-1∞Lk-1来表示Lk-1连接操作，表示如果l1和l2具有一样的前(k-2)项，可以连接Lk-1中l1和l2。为了确保项集的唯一性，必须满足l1[k-1]

(2)剪枝步骤：从候选集合Ck，进一步发现Lk。Lk的超集Ck中包含了全部k项集，其中还包括一些非频繁项集的元素，即有Lk⊆Ck。如果侯选k项集中的任一子集不属于Lk-1，则应该从Ck中删除这个侯选k项集。

2 森林虫害预测

在随着数据量的增大，挖掘频繁项集能在大量数据中寻找他们之间的关系，在生活中有着广泛的应用场合。在商业销售上，无监督学习的Apriori可用于进行相关的商业决策[7-8]；在保险业务方面，如果出现不常见的索赔要求组合，则可能为欺诈，需要进一步调查。

本地森林害虫并不会引发严重虫害，因为它与寄主之间已经形成了稳定的关系。外来森林害虫入侵到新的地区后;如果遇到与其原寄主亲缘关系较近，尤其是同属类内的本地树种时，常常发生严重的危害。这是因为基于进化上的原因这些外来森林害虫己经具备对这些本地近源树种的寄生侵害能力；但因为缺乏共同的进化历程，本地树种缺乏对这些害虫的抵御能力，容易成为害虫的适宜寄主，害虫种群迅速增长，导致灾害爆发[9]。

Apriori算法在森林虫害预防分析中的应用，主要是通过对森林虫害历史数据挖掘出频繁2项集，通过提取出的频繁2项集中去掉错误和冗余的数据，找到包含以下2种关系的特征子集：(1)已知虫害现象中的寄主和害虫；(2)已知虫害现象中的寄主和与原寄主亲缘关系较近的外地树种。

通过对提取特征子集，筛选了最有可能诱发森林虫害的树种、昆虫组合。为林业领域种植提供决策支持[10]，降低森林虫害发生的风险。

2.1 数据的收集

本文提出的研究方法中，主要包括两部分数据：虫害文章数据，林业树种、虫害元数据。其中，(1)虫害文章数据是通过单机网络爬虫森林虫害相关数据库获得；(2)林业树种、虫害元数据是通过搜集林业主题网站和之前的构建林业领域数据库获得，存放在本机[11]。虫害文章数据中的信息主要包括文章编号、文章标题、文章摘要、摘要关键词等。林业树种、虫害元数据中的信息主要包括物种编号、物种名称等。

通过搜集互联网有关森林虫害相关文章24 000条，使用Paoding分词包、中科院词典进行分词得到关键词。各项存于数据库，部分如下表1所示。

表1 森林虫害文章数据

通过搜集林业主题网站和已经构建的林业领域数据库获得。各项存于数据库，部分如下表2所示。

2.2 实验数据预处理及建立事务数据库

表2 树种和虫害元数据

研究所涉及的数据挖掘的Apriori算法结合Java语言进行应用系统开发，在考虑合理使用计算机内存的前提下，采用链表结构组织森林虫害事务数据，尽量减少内存消耗。部分如下表3所示。

表3 森林虫害事务数据

3 结果与分析

基于Apriori算法在森林虫害预测方法研究所建立的系统利用MySQL数据库、Python语言爬虫、Java语言系统开发。所有试验数据基于双核CPU 2.2 GHz以及4 G内存，并运行在Window 7操作系统之上。

根据表3的事务数据库数据(D)，该数据库有9个事务，即|D|=9。实验过程如图1所示。

(1)在算法的第一次迭代时，每个项都属于候选1项集的集合C1。算法简单的扫描所有事务，对每个项出现的次数计数。

(2)设定最小支持度计数阈值为2，即Smin=2。可以确定频繁1项集集合L1。

(4)扫描D中事务，累计C2中每个候选项集的支持度计数，其中满足最小支持度计数的为频繁2项集合L2。

图1 森林虫害事务数据库产生频繁2项集过程

本次试验采用24 000条森林虫害文章数据作为提取森林虫害事务数据的数据集。根据研究课题，在选取数据集的过程中也考虑了复杂度以及在数据数量上能够达到普遍性的要求。

试验结果是针对森林虫害事务数据库，挖掘对本课题研究价值较大的频繁2项集，为方便计算，用0～100%间的值而不是0～1.0间的值表示支持度，且预先定义最小支持度阈值Smin=2.00%。

从表4中可以看出，在频繁2项集挖掘得到的部分结果中，包含了进行虫害预测需要的两类有研究价值的频繁模式，包括：(1)已知虫害现象中的寄主和害虫；(2)已知虫害现象中的寄主和与原寄主亲缘关系较近的外地树种。

其中第一类频繁模式挖掘搜集并统计了已发生的森林虫害；第二类频繁模式统计了亲缘关系较近的树种，可以结合已经出现的虫害寄主，预测潜在可能发生的虫害。

表4 满足最小支持度阈值的2项集部分结果

表5给出了试验结果中部分外来树种可能会诱发本地森林虫害的部分数据。从预测结果来看，萧氏松茎象初始都没有引起注意或被发现定名，是在引进我国引进北美松树树种如湿地松后[12]，1988年我国在江西省吉安市安福县武功山林场首次被发现，逐渐扩散蔓延。这说明外来树种引进种植确实是森林虫害爆发的潜在诱因。兰矩瘤蛎蚧是一种在我国南方部分地区被发现的主要以香樟作为寄主的害虫，通过Apriori算法挖掘出香樟与楠属植物之间的频繁模式，从而预测楠属植物如金丝楠可能会诱发新的森林虫害。其余几种害虫各自也都对应可能诱发森林虫害的外来树种，例如白蜡窄吉丁虫是在我国引进北美白蜡树种时被命名发现，对于花曲柳和雪柳同样也存在着潜在的诱发虫害的可能性。

表5 不同树种森林虫害预测部分结果

4 结束语

本文首次提出了在森林虫害预测时使用Apriori算法，该方法有以下特点：(1)实现了挖掘和统计已出现的大部份森林虫害的功能；(2)引入相关性分析解决了在引进种植外来树种时预测潜在可能爆发的森林虫害问题。(3)经过可视化处理使得大量数据得以直观的展示，易于分析、理解。但是没有考虑算法本身的时间特性，该方法在分析中存在先天缺陷。以后将针对该算法的改进主要集中在压缩候选项集(尤其是的选择决定了挖掘的性能)和减少扫描数据库次数两方面。例如Parketal.提出了使用哈希散列技术压缩候选项集[13]；AgrawalR[2]提出的AprioriHybrid算法；以及在分布式和并行环境下发掘关联规则的分布式挖掘算法。甚至改变使用其他算法进行优化，例如使用垂直数据格式[14]的FP-growth的频繁模式增长树算法[15]。提高其在实际应用中的分析能力。总体上讲，该方法为森林虫害的分析和预防提供了一种简易、有效的途径。

[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] 赵同海.从昆虫与植物的进化关系看当今林业害虫的发生与治理对策[C]//第二届中国林业学术大会—S6森林昆虫与自然调控论文集.北京，2009.

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

[11] 刘汉兴,刘财兴.主题爬虫的搜索策略研究[J].计算机工程与设计,2008,29(12):3160-3162.

[12] 罗永松,孙江华.萧氏松茎象生态控制初探[J].中国森林病虫,2004,23(6):37-39.

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

[14] 陈伟.使用垂直数据格式挖掘频繁项集[J].微型机与应用,2011,30(18):6-7.

[15] 李洪波,周莉,张吉赞.用垂直数据格式构建FP增长树的算法[J].计算机工程与应用,2009,45(8):161-164.

Forest Pest Prediction Method with Apriori Algorithm//

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