王　恬　李书琴　王志伟

(西北农林科技大学信息工程学院　陕西 杨凌 712100)



农业信息搜索可视化平台研究

王恬李书琴*王志伟

(西北农林科技大学信息工程学院陕西 杨凌 712100)

针对传统搜索引擎检索返回结果数量庞大、专业性差且只能为用户提供一维、线性搜索结果的问题，在分析研究农业垂直搜索引擎的基础上，构建农业信息搜索可视化服务平台。基于农业文献，对数据进行信息抽取、关联分析，并设计了一种基于最大距离法选取初始质心的K-means层次聚类算法来发现领域概念间关系；在此基础上，利用信息可视化模型与基于Java的Prefuse插件包为用户提供图形化的结果呈现方式，实现信息的交互控制，优化检索过程。通过实验验证，改进的层次聚类算法提高了领域概念间关系聚类效果的同时降低了聚类总耗时，平台满足用户检索的专业性需求。

农业搜索引擎关联分析层次聚类算法信息可视化Prefuse

0　引　言

随着信息技术在农业领域的广泛应用和农业信息化技术的快速发展，农业信息用户的需求量大幅增加、规模日益扩大。然而面对巨大的“三农”网络信息资源，用户在信息搜索时会查出很多与目标信息无关的网页[1]。与通用搜索引擎相比，农业领域内的垂直搜索引擎已经为用户提供了更加专业的搜索结果。

国外的农业垂直搜索引擎已经取得了一定的成果[2]，如WEBSearch、Agrisearchsearch等。但我国的农业搜索引擎出现相对较晚，目前国内农业搜索引擎主要有农搜网、搜农网等，仍然处在发展时期，存在一些不完善的地方：首先搜索结果中仍包含了大量的信息[3]，搜索准确率和用户满意度较低；其次用户往往需要顺序浏览搜索结果列表来查找他们所需要的信息，忽略了用户在浏览时的交互作用。

本文结合国内外研究成果的优缺点，在农业垂直搜索引擎基础上对其进行二次开发，结合信息可视化技术完成农业信息搜索可视化平台。主要在如下3个方面做了改进：(1)扩展数据来源。从万方数据知识服务平台等Web网络资源中获取领域语料和领域词典；(2)改进研究算法。设计了一种基于最大距离法选取初始质心的K-means层次聚类算法，并结合信息抽取[4]、关联分析技术发现领域概念间关系；(3)搜索结果可视化。利用可视化映射技术最终将搜索相关推荐词可视化呈现给用户，使用户更快地达到兴趣点，有效地帮助其快速定位搜索结果或再次选择搜索关键字，增加用户与系统之间的交互作用。

1　研究架构

Heer等[5]提出了基于Prefuse的信息可视化模型，Prefuse为数据建模、数据可视化及用户交互提供了丰富的软件库，可以支持表格、图和树的显示，还具有支持动态交互、动态查询等功能[6]。本文在旱区农业垂直搜索引擎的设计基础上引入信息可视化思想，构建了农业信息搜索可视化服务平台框架，如图1所示。

图1　农业信息搜索可视化平台架构图

从逻辑上分析，农业信息搜索可视化服务平台的构建主要划分为3个阶段：信息采集和过滤、生成可视化数据、检索结果可视化呈现。整个工作流程可分为以下4个阶段：(1)利用Web网络资源获取农业领域文献信息并进行预处理得到候选领域概念；(2)运用关联分析和聚类技术发现领域概念间关系并存入关系数据库；(3)利用基于Prefuse的可视化映射方法[7]实现概念空间图的实时生成，并与用户动态交互；(4)将检索结果返回给用户，利用得到的领域概念间的关系及相关度向用户推荐搜索相关词。

2　系统关键技术

2.1Web信息抽取

本文参考冯硕等人[8]实现的基于包装器的Web信息抽取技术，获取相关网站中农业领域文献的题目、摘要和关键词作为领域语料。基本流程为：首先将待抽取的页面htmlFile解析为DOM(DocumentObjectModel)数结构的文档，然后根据树中对应的节点node确定目标数据项的左右边界，根据边界来定位数据项，实现对不同信息源信息的抽取。

2.2关联分析技术

(1) 中文分词

中文分词是实现中文搜索引擎的关键技术之一，分词质量决定了搜索引擎提取文本的准确度。传统的开源分词工具IKAnalyzer仅具有简单的分词和排歧义功能，因此本文需要对其进行改进。基本思想是结合农业领域词典和正向最大匹配算法[9]进行分词：首先将待切分的字符串从左取出长度为L(不大于最大词长MaxLen)的字符串S；其次查找S是否在词典中成功匹配，若匹配成功，从左起去掉S的前L个字符，将已匹配的词添加到字符串S1，循环进行前面的操作直至S为空，若匹配不成功则去掉S的最右一个字符继续匹配；最后输出分词结果S1。对分词结果进行过滤清洗得到本文的候选领域概念。

(2) 领域相关度判断

文本中词语的空间维度较高，且不同的词对文本内容的贡献不相等，因此需计算出词语在文本中的权重，进而选择相关度较高的词语作为领域概念。本文使用TF-IDF(TermFrequencyInvertedDocumentFrequency)公式进行相关性判断。TF-IDF非常有效地将每个词语的局部权重和全局权重结合在一起。其计算公式为：

(1)

其中TF(fi,dj)表示词fi在文本dj中出现的频率， maxkTF(fk,dj)代表词fk在文本集的各文本中最大的出现次数；N表示文本总数量，DF(fj)代表词fj的文档频数。

(3) 领域概念间关系发现

获取领域概念后，首先采用基于共现分析的理论计算得到共现矩阵。其次利用Jaccard系数计算领域概念间的相关度，得到领域概念的相关矩阵，从而分析领域概念间相互关联的紧密程度。最后根据相关矩阵得到每个领域概念的向量，利用余弦夹角法求出每两个领域概念的相似度。Jaccard系数计算公式如式(2)所示，余弦夹角法计算公式如式(3)所示。

(2)

(3)

式(2)中cij是领域概念i与领域概念j共同出现的次数； ci、cj分别是领域概念i和领域概念j在所有文本中出现的总次数。式(3)中di=(wi1,wi2,…,wik)，dj=(wj1,wj2,…,wjk)分别为两个文本向量，wik为领域概念ti在对应的n维向量中第k维上的取值，wjk为领域概念tj在对应的n维向量中第k维上的取值。

2.3领域概念聚类

本研究所需的领域概念是为农业信息检索提供知识组织，根据得到的领域概念间的相似度值作为距离进行聚类，从而得到概念间的分类关系。

传统的获取领域概念间分类关系一般采用凝聚层次法实现，它是一种自底向上的方法。其中UPGMA(unweightedpair-groupmethodwitharithmeticmeans)算法采用度量两个子类内文本的两两相似度的均值进而确定合并的子类，它的精度较高但时间复杂度也较高，为O(n2logn)，其中n是文本总数。K-means方法是基于划分的聚类方法，算法效率很高，它的复杂度是O(nkt)，其中n是文本总数，k是聚类数目，t是迭代次数。K-means聚类算法随机选择初始质心会导致聚类过程中总迭代次数较多、聚类容易陷入局部最优等问题。为了克服上述缺点，王超等人[10]提出了基于优化初始质心K-means的层次聚类算法，该算法在一定程度上提高了聚类的精度和效率，但对于初始聚类数目较大时，会出现迭代次数增多等问题，使算法效率降低。本文在研究以上算法的基础上，提出了基于最大距离法选取初始质心的K-means层次聚类算法，算法改进如下所示：

算法1基于最大距离法选取初始质心的K-means层次聚类算法

输入：领域概念集合

输出：领域概念聚类树

Step1使用基于最大距离法选取初始质心的K-means方法生成k个约束类。

Step1.1计算数据集中M个数据点两两之间的距离{distance(di,dj)，(i,j=1,2,…,M) }将距离最远的2个数据点d1、d2作为初始质心，即满足distance(d1,d2)≥distance(di,dj)。

Step1.2在剩余的(M-2) 个数据点中，选取到前面两个初始质心各自距离乘积最大值的数据点d3作为第三个初始质心，即满足distance(d1,d3)×distance(d2,d3)≥distance(d1,di)×distance(d2,di),di为除d1,d2,d3之外的任一数据点。

Step1.3在剩余的(M-3) 个数据点中，选取到前面三个初始质心各自距离乘积最大值的数据点d4作为第四个初始质心，即满足distance(d1,d4)×distance(d2,d4) ×distance(d3,d4)≥distance(d1,di)×distance(d2,di) ×distance(d3,di),di为除d1,d2,d3,d4之外的任一数据点。

Step1.4循环Step1.3步直到找到i个初始质心。至此确定初始质心和k值。

Step2对每一个约束类，应用UPGMA凝聚层次聚类算法生成一颗聚类树。

Step3将k颗聚类树看作凝聚过程中产生的中间类，再次运用凝聚层次聚类法，将这k颗树合并成为一颗完整的聚类树。

本算法的时间复杂度为O(k(n/k)2log(n/k)+k2logk)，当k足够大时，凝聚层次法的时间复杂度就会降低，进而大大提高了聚类效率。

通过聚类得到树状的领域概念聚类结果，树中每一层的领域概念是同位关系，每个树枝两端的领域概念是父子关系。将得到的三元组模型(主体—关系—客体)[11]信息存入数据库中，为数据可视化准备数据。

2.4数据可视化

数据可视化技术根据其可视化原理不同可分为基于图标、像素、图形和几何理论的技术。其中基于图形的可视化用整个图形表示数据，包括网状图、树形图、维嵌图等[12]。考虑到目前农业搜索引擎涉及到的领域较为单一，所以本研究平台基于农业垂直搜索引擎结合Prefuse技术为用户提供相关检索词的网状和树形可视化结构图，辅助用户进行二次检索。

3　系统实验与分析

3.1实验数据准备

本文针对农业信息搜索可视化平台的应用进行了实验。从万方数据知识服务平台获得农业研究相关期刊2009年至2013年五年内2 537篇论文的关键词和摘要作为领域语料，结合分词词典和停用词典，应用本文改进的正向最大匹配算法对领域语料进行中文分词。利用式(1)对术语进行领域相关度判断，计算术语的TF-IDF值，经筛选留取505个领域概念。通过对领域概念之间进行关联分析，利用式(2)和式(3)计算领域概念间的相关度和相似度，得到一个505×505的农业领域概念相似矩阵，如表1所示。

表1　领域概念相似矩阵

3.2实验结果分析

(1) 中文分词结果分析

对本实验获得的农业领域论文数据集分别采用传统的IKAnalyzer分词工具和本文改进的分词方法(WAnalyzer)进行分词，统计两种分词结果中的正确率和错误率。实验结果如表2所示。

表2　中文分词结果比较

从表2中可以看出采用本文改进的分词方法在处理农业领域数据集时可以获得较高的正确率。

(2) 聚类结果分析

为了便于分析，本文采用常用的聚类评价指标对算法进行评测。对于一个聚类结果，F-度量值(F-Measure)[13]是准确率和召回率的综合，因此本文通过F-度量值对其质量进行评价。一般而言，F值越大，聚类结果的质量越好。

本实验中，基于农业信息搜索可视化平台得到领域概念及其相关关系，利用上述基于最大距离法选取初始质心的K-means层次聚类算法进行聚类，将得到的聚类树记为T。实验中分别实现该算法和传统凝聚层次聚类的F值，算法进行初始聚类划分时的数目k分别取值为10、20、n/10，得到聚类结果F值比较如图2所示，算法运行效率比较如图3所示。

图2　聚类结果F值折线对比图

图3　聚类算法耗时折线对比图

从实验结果可以看出，当初始聚类划分数目较大时，采用本研究算法比传统凝聚层次聚类算法的结果有较大改进；当初始聚类划分数目较小时，虽然部分结果与传统凝聚层次聚类算法相比效果稍差，但其聚类效率与前者相比有较大提高。因此，本研究农业信息搜索可视化服务平台的总体性能相比传统农业搜索引擎来讲较好。

3.3运行实例

本文设计并实现了一个农业信息搜索可视化服务平台，向用户提供了类似Google的搜索输入界面，搜索结果返回前端可视化处理界面。图4所示为对关键词“小麦”的搜索结果，展示出了搜索相关词之间的关系。关键词之间关联度越高，节点间连线距离越近；反之亦然。图形还具有动态交互性，可以使用户集中注意力于当前节点，并可以动态渐变地发现关键词关联关系的变化。

图4　搜索“小麦”生成的可视化界面

4　结　语

本文针对农业用户信息搜索的需求，在农业垂直搜索引擎工作原理的基础上，结合Prefuse可视化技术构建了农业信息搜索可视化服务平台。通过信息抽取、关联分析技术获取领域概念，设计并实现了一种基于最大距离法选取初始质心的K-means层次聚类算法，发现并改进领域概念间关系，提高聚类效率。此外将搜索相关词以图形化的形式呈现给用户，通过网状和树形图两种方式向用户快速、直观地展示搜索结果，同时提供交互功能，通过该平台可以辅助用户进行二次检索，明显改善了用户的搜索体验。

在今后的工作中系统的功能还可以进一步扩展，如对可视化界面进一步美观，增加用户体验；对不同专业领域、大数据集数据进行更全面的验证。

[1] 李广丽，刘觉夫. 垂直搜索引擎系统的研究与实现 [J].情报杂志,2009,28(10):144-147.

[2] 王晓琴，李书琴，景旭,等. 基于Nutch的农业垂直搜索引擎研究[J].计算机工程与设计，2014,35(6):2239-2243.

[3] 张阳. 农业搜索可视化平台的研究 [D]. 安徽：中国科学技术大学,2010.

[4]ZhengHK，KangBY，KimHG.Anontology-basedapproachtolearnablefocusedcrawling[J].InformationScience,2008,178(23):4512-4522.

[5]HeerJ，CardSK，LandayJA．Prefuse:ATookitforInteractiveInformationVisualization[C]//ProceedingsoftheSIGCHIConferenceonHumanFactorsinComputingSystems,2005.Portland，2005.

[6] 肖明，栗文超，夏秋菊. 基于Prefuse和层次聚类的信息检索主题知识图谱研究[J]. 现代图书情报技术,2012,28(4):35-40.

[7] 陈颖，白淑琴，张学福. 基于共词分析的中文信息检索可视化研究[J].情报科学,2009,27(2):227-230.

[8] 冯硕,李书琴,杨会君. 基于Web挖掘的化学物质信息提取应用研究[J]. 计算机工程与设计，2012,33(8):3040-3046.

[9] 石倩,陈荣,鲁明羽. 基于规则归纳的信息抽取系统实现[J]. 计算机工程与应用，2008,44(21):166-170.

[10] 王超,李书琴,肖红.基于文献的农业领域本体自动构建方法研究[J]. 计算机应用与软件，2014,31(8):71-74.

[11] 冯颖.医学本体融合与可视化系统的设计与实现[D]. 湖北：华中科技大学,2012.

[12] 赵华军,钟才明,李文,等.网页搜索结果聚类与可视化[J].南京大学学报：自然科学，2010,46(5):542-551.

[13] 翟东海,鱼江,高飞,等. 最大距离法选取初始簇中心的K-means文本聚类算法的研究[J]. 计算机应用研究，2014,31(3):713-719.

RESEARCHONVISUALISEDPLATFORMOFAGRICULTURALINFORMATIONSEARCH

WangTianLiShuqin*WangZhiwei

(College of Information Engineering,Northwest A&F University,Yangling 712100, Shaanxi, China)

Aimingattheproblemoftraditionalsearchenginesthattheyreturnalargenumberofretrievingresults,bepoorinprofessionalcapabilityandcanonlyprovideuserswithone-dimensionalandlinearsearchresults,basedonanalysingandstudyingverticalagriculturalsearchengines,weconstructedthevisualisedserviceplatformforagriculturalinformationsearch.Onthebasisofagricultureliteratures,wecarriedouttheinformationextractionandassociationanalysisondata,anddesignedak-meanshierarchicalclusteringalgorithm,whichisbasedonselectinginitialcentroidwithmaximumdistancemethod,todiscovertherelationshipbetweendomainconcepts.Basedonthis,weusedthemodelofinformationvisualisationandtheJava-basedPrefusepluginspacktoprovideforusersagraphicalrepresentationmeansforresults,thusrealisedtheinteractivecontrolofinformation,andoptimisedtheretrievalprocessaswell.Itisverifiedthroughexperimentthattheimprovedhierarchicalclusteringalgorithminthispaperimprovestheeffectofcorrelationclusteringbetweendomainconceptsandmeanwhilereducestotalclusteringtimeconsumption.Theplatformcanmeettheprofessionaldemandofusersretrieval．

AgriculturalsearchengineAssociationanalysisHierarchicalclusteringalgorithmInformationvisualisationPrefuse

2014-10-16。“十二五”国家科技支撑项目 (2012BAH30F01,2013BAD15B02)；中央高校基本科研业务费项目(QN2011036)。王恬，硕士生，主研领域：：智能信息系统。李书琴，教授。王志伟，硕士生。

TP391

ADOI:10.3969/j.issn.1000-386x.2016.03.064