農業信息搜索可視化平臺研究

王　恬　李書琴　王志偉

(西北農林科技大學信息工程學院　陜西 楊凌 712100)

?

農業信息搜索可視化平臺研究

王恬李書琴*王志偉

(西北農林科技大學信息工程學院陜西 楊凌 712100)

針對傳統搜索引擎檢索返回結果數量龐大、專業性差且只能為用戶提供一維、線性搜索結果的問題，在分析研究農業垂直搜索引擎的基礎上，構建農業信息搜索可視化服務平臺?；谵r業文獻，對數據進行信息抽取、關聯分析，并設計了一種基于最大距離法選取初始質心的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僅具有簡單的分詞和排歧義功能，因此本文需要對其進行改進?；舅枷胧墙Y合農業領域詞典和正向最大匹配算法[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)；中央高?；究蒲袠I務費項目(QN2011036)。王恬，碩士生，主研領域：：智能信息系統。李書琴，教授。王志偉，碩士生。

TP391

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