農(nóng)業(yè)信息搜索可視化平臺研究

王　恬　李書琴　王志偉

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

?

農(nóng)業(yè)信息搜索可視化平臺研究

王恬李書琴*王志偉

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

針對傳統(tǒng)搜索引擎檢索返回結果數(shù)量龐大、專業(yè)性差且只能為用戶提供一維、線性搜索結果的問題，在分析研究農(nóng)業(yè)垂直搜索引擎的基礎上，構建農(nóng)業(yè)信息搜索可視化服務平臺。基于農(nóng)業(yè)文獻，對數(shù)據(jù)進行信息抽取、關聯(lián)分析，并設計了一種基于最大距離法選取初始質(zhì)心的K-means層次聚類算法來發(fā)現(xiàn)領域概念間關系；在此基礎上，利用信息可視化模型與基于Java的Prefuse插件包為用戶提供圖形化的結果呈現(xiàn)方式，實現(xiàn)信息的交互控制，優(yōu)化檢索過程。通過實驗驗證，改進的層次聚類算法提高了領域概念間關系聚類效果的同時降低了聚類總耗時，平臺滿足用戶檢索的專業(yè)性需求。

農(nóng)業(yè)搜索引擎關聯(lián)分析層次聚類算法信息可視化Prefuse

0　引　言

隨著信息技術在農(nóng)業(yè)領域的廣泛應用和農(nóng)業(yè)信息化技術的快速發(fā)展，農(nóng)業(yè)信息用戶的需求量大幅增加、規(guī)模日益擴大。然而面對巨大的“三農(nóng)”網(wǎng)絡信息資源，用戶在信息搜索時會查出很多與目標信息無關的網(wǎng)頁[1]。與通用搜索引擎相比，農(nóng)業(yè)領域內(nèi)的垂直搜索引擎已經(jīng)為用戶提供了更加專業(yè)的搜索結果。

國外的農(nóng)業(yè)垂直搜索引擎已經(jīng)取得了一定的成果[2]，如WEBSearch、Agrisearchsearch等。但我國的農(nóng)業(yè)搜索引擎出現(xiàn)相對較晚，目前國內(nèi)農(nóng)業(yè)搜索引擎主要有農(nóng)搜網(wǎng)、搜農(nóng)網(wǎng)等，仍然處在發(fā)展時期，存在一些不完善的地方：首先搜索結果中仍包含了大量的信息[3]，搜索準確率和用戶滿意度較低；其次用戶往往需要順序瀏覽搜索結果列表來查找他們所需要的信息，忽略了用戶在瀏覽時的交互作用。

本文結合國內(nèi)外研究成果的優(yōu)缺點，在農(nóng)業(yè)垂直搜索引擎基礎上對其進行二次開發(fā)，結合信息可視化技術完成農(nóng)業(yè)信息搜索可視化平臺。主要在如下3個方面做了改進：(1)擴展數(shù)據(jù)來源。從萬方數(shù)據(jù)知識服務平臺等Web網(wǎng)絡資源中獲取領域語料和領域詞典；(2)改進研究算法。設計了一種基于最大距離法選取初始質(zhì)心的K-means層次聚類算法，并結合信息抽取[4]、關聯(lián)分析技術發(fā)現(xiàn)領域概念間關系；(3)搜索結果可視化。利用可視化映射技術最終將搜索相關推薦詞可視化呈現(xiàn)給用戶，使用戶更快地達到興趣點，有效地幫助其快速定位搜索結果或再次選擇搜索關鍵字，增加用戶與系統(tǒng)之間的交互作用。

1　研究架構

Heer等[5]提出了基于Prefuse的信息可視化模型，Prefuse為數(shù)據(jù)建模、數(shù)據(jù)可視化及用戶交互提供了豐富的軟件庫，可以支持表格、圖和樹的顯示，還具有支持動態(tài)交互、動態(tài)查詢等功能[6]。本文在旱區(qū)農(nóng)業(yè)垂直搜索引擎的設計基礎上引入信息可視化思想，構建了農(nóng)業(yè)信息搜索可視化服務平臺框架，如圖1所示。

圖1　農(nóng)業(yè)信息搜索可視化平臺架構圖

從邏輯上分析，農(nóng)業(yè)信息搜索可視化服務平臺的構建主要劃分為3個階段：信息采集和過濾、生成可視化數(shù)據(jù)、檢索結果可視化呈現(xiàn)。整個工作流程可分為以下4個階段：(1)利用Web網(wǎng)絡資源獲取農(nóng)業(yè)領域文獻信息并進行預處理得到候選領域概念；(2)運用關聯(lián)分析和聚類技術發(fā)現(xiàn)領域概念間關系并存入關系數(shù)據(jù)庫；(3)利用基于Prefuse的可視化映射方法[7]實現(xiàn)概念空間圖的實時生成，并與用戶動態(tài)交互；(4)將檢索結果返回給用戶，利用得到的領域概念間的關系及相關度向用戶推薦搜索相關詞。

2　系統(tǒng)關鍵技術

2.1Web信息抽取

本文參考馮碩等人[8]實現(xiàn)的基于包裝器的Web信息抽取技術，獲取相關網(wǎng)站中農(nóng)業(yè)領域文獻的題目、摘要和關鍵詞作為領域語料。基本流程為：首先將待抽取的頁面htmlFile解析為DOM(DocumentObjectModel)數(shù)結構的文檔，然后根據(jù)樹中對應的節(jié)點node確定目標數(shù)據(jù)項的左右邊界，根據(jù)邊界來定位數(shù)據(jù)項，實現(xiàn)對不同信息源信息的抽取。

2.2關聯(lián)分析技術

(1) 中文分詞

中文分詞是實現(xiàn)中文搜索引擎的關鍵技術之一，分詞質(zhì)量決定了搜索引擎提取文本的準確度。傳統(tǒng)的開源分詞工具IKAnalyzer僅具有簡單的分詞和排歧義功能，因此本文需要對其進行改進。基本思想是結合農(nóng)業(yè)領域詞典和正向最大匹配算法[9]進行分詞：首先將待切分的字符串從左取出長度為L(不大于最大詞長MaxLen)的字符串S；其次查找S是否在詞典中成功匹配，若匹配成功，從左起去掉S的前L個字符，將已匹配的詞添加到字符串S1，循環(huán)進行前面的操作直至S為空，若匹配不成功則去掉S的最右一個字符繼續(xù)匹配；最后輸出分詞結果S1。對分詞結果進行過濾清洗得到本文的候選領域概念。

(2) 領域相關度判斷

文本中詞語的空間維度較高，且不同的詞對文本內(nèi)容的貢獻不相等，因此需計算出詞語在文本中的權重，進而選擇相關度較高的詞語作為領域概念。本文使用TF-IDF(TermFrequencyInvertedDocumentFrequency)公式進行相關性判斷。TF-IDF非常有效地將每個詞語的局部權重和全局權重結合在一起。其計算公式為：

(1)

其中TF(fi,dj)表示詞fi在文本dj中出現(xiàn)的頻率， maxkTF(fk,dj)代表詞fk在文本集的各文本中最大的出現(xiàn)次數(shù)；N表示文本總數(shù)量，DF(fj)代表詞fj的文檔頻數(shù)。

(3) 領域概念間關系發(fā)現(xiàn)

獲取領域概念后，首先采用基于共現(xiàn)分析的理論計算得到共現(xiàn)矩陣。其次利用Jaccard系數(shù)計算領域概念間的相關度，得到領域概念的相關矩陣，從而分析領域概念間相互關聯(lián)的緊密程度。最后根據(jù)相關矩陣得到每個領域概念的向量，利用余弦夾角法求出每兩個領域概念的相似度。Jaccard系數(shù)計算公式如式(2)所示，余弦夾角法計算公式如式(3)所示。

(2)

(3)

式(2)中cij是領域概念i與領域概念j共同出現(xiàn)的次數(shù)； ci、cj分別是領域概念i和領域概念j在所有文本中出現(xiàn)的總次數(shù)。式(3)中di=(wi1,wi2,…,wik)，dj=(wj1,wj2,…,wjk)分別為兩個文本向量，wik為領域概念ti在對應的n維向量中第k維上的取值，wjk為領域概念tj在對應的n維向量中第k維上的取值。

2.3領域概念聚類

本研究所需的領域概念是為農(nóng)業(yè)信息檢索提供知識組織，根據(jù)得到的領域概念間的相似度值作為距離進行聚類，從而得到概念間的分類關系。

傳統(tǒng)的獲取領域概念間分類關系一般采用凝聚層次法實現(xiàn)，它是一種自底向上的方法。其中UPGMA(unweightedpair-groupmethodwitharithmeticmeans)算法采用度量兩個子類內(nèi)文本的兩兩相似度的均值進而確定合并的子類，它的精度較高但時間復雜度也較高，為O(n2logn)，其中n是文本總數(shù)。K-means方法是基于劃分的聚類方法，算法效率很高，它的復雜度是O(nkt)，其中n是文本總數(shù)，k是聚類數(shù)目，t是迭代次數(shù)。K-means聚類算法隨機選擇初始質(zhì)心會導致聚類過程中總迭代次數(shù)較多、聚類容易陷入局部最優(yōu)等問題。為了克服上述缺點，王超等人[10]提出了基于優(yōu)化初始質(zhì)心K-means的層次聚類算法，該算法在一定程度上提高了聚類的精度和效率，但對于初始聚類數(shù)目較大時，會出現(xiàn)迭代次數(shù)增多等問題，使算法效率降低。本文在研究以上算法的基礎上，提出了基于最大距離法選取初始質(zhì)心的K-means層次聚類算法，算法改進如下所示：

算法1基于最大距離法選取初始質(zhì)心的K-means層次聚類算法

輸入：領域概念集合

輸出：領域概念聚類樹

Step1使用基于最大距離法選取初始質(zhì)心的K-means方法生成k個約束類。

Step1.1計算數(shù)據(jù)集中M個數(shù)據(jù)點兩兩之間的距離{distance(di,dj)，(i,j=1,2,…,M) }將距離最遠的2個數(shù)據(jù)點d1、d2作為初始質(zhì)心，即滿足distance(d1,d2)≥distance(di,dj)。

Step1.2在剩余的(M-2) 個數(shù)據(jù)點中，選取到前面兩個初始質(zhì)心各自距離乘積最大值的數(shù)據(jù)點d3作為第三個初始質(zhì)心，即滿足distance(d1,d3)×distance(d2,d3)≥distance(d1,di)×distance(d2,di),di為除d1,d2,d3之外的任一數(shù)據(jù)點。

Step1.3在剩余的(M-3) 個數(shù)據(jù)點中，選取到前面三個初始質(zhì)心各自距離乘積最大值的數(shù)據(jù)點d4作為第四個初始質(zhì)心，即滿足distance(d1,d4)×distance(d2,d4) ×distance(d3,d4)≥distance(d1,di)×distance(d2,di) ×distance(d3,di),di為除d1,d2,d3,d4之外的任一數(shù)據(jù)點。

Step1.4循環(huán)Step1.3步直到找到i個初始質(zhì)心。至此確定初始質(zhì)心和k值。

Step2對每一個約束類，應用UPGMA凝聚層次聚類算法生成一顆聚類樹。

Step3將k顆聚類樹看作凝聚過程中產(chǎn)生的中間類，再次運用凝聚層次聚類法，將這k顆樹合并成為一顆完整的聚類樹。

本算法的時間復雜度為O(k(n/k)2log(n/k)+k2logk)，當k足夠大時，凝聚層次法的時間復雜度就會降低，進而大大提高了聚類效率。

通過聚類得到樹狀的領域概念聚類結果，樹中每一層的領域概念是同位關系，每個樹枝兩端的領域概念是父子關系。將得到的三元組模型(主體—關系—客體)[11]信息存入數(shù)據(jù)庫中，為數(shù)據(jù)可視化準備數(shù)據(jù)。

2.4數(shù)據(jù)可視化

數(shù)據(jù)可視化技術根據(jù)其可視化原理不同可分為基于圖標、像素、圖形和幾何理論的技術。其中基于圖形的可視化用整個圖形表示數(shù)據(jù)，包括網(wǎng)狀圖、樹形圖、維嵌圖等[12]。考慮到目前農(nóng)業(yè)搜索引擎涉及到的領域較為單一，所以本研究平臺基于農(nóng)業(yè)垂直搜索引擎結合Prefuse技術為用戶提供相關檢索詞的網(wǎng)狀和樹形可視化結構圖，輔助用戶進行二次檢索。

3　系統(tǒng)實驗與分析

3.1實驗數(shù)據(jù)準備

本文針對農(nóng)業(yè)信息搜索可視化平臺的應用進行了實驗。從萬方數(shù)據(jù)知識服務平臺獲得農(nóng)業(yè)研究相關期刊2009年至2013年五年內(nèi)2 537篇論文的關鍵詞和摘要作為領域語料，結合分詞詞典和停用詞典，應用本文改進的正向最大匹配算法對領域語料進行中文分詞。利用式(1)對術語進行領域相關度判斷，計算術語的TF-IDF值，經(jīng)篩選留取505個領域概念。通過對領域概念之間進行關聯(lián)分析，利用式(2)和式(3)計算領域概念間的相關度和相似度，得到一個505×505的農(nóng)業(yè)領域概念相似矩陣，如表1所示。

表1　領域概念相似矩陣

3.2實驗結果分析

(1) 中文分詞結果分析

對本實驗獲得的農(nóng)業(yè)領域論文數(shù)據(jù)集分別采用傳統(tǒng)的IKAnalyzer分詞工具和本文改進的分詞方法(WAnalyzer)進行分詞，統(tǒng)計兩種分詞結果中的正確率和錯誤率。實驗結果如表2所示。

表2　中文分詞結果比較

從表2中可以看出采用本文改進的分詞方法在處理農(nóng)業(yè)領域數(shù)據(jù)集時可以獲得較高的正確率。

(2) 聚類結果分析

為了便于分析，本文采用常用的聚類評價指標對算法進行評測。對于一個聚類結果，F(xiàn)-度量值(F-Measure)[13]是準確率和召回率的綜合，因此本文通過F-度量值對其質(zhì)量進行評價。一般而言，F(xiàn)值越大，聚類結果的質(zhì)量越好。

本實驗中，基于農(nóng)業(yè)信息搜索可視化平臺得到領域概念及其相關關系，利用上述基于最大距離法選取初始質(zhì)心的K-means層次聚類算法進行聚類，將得到的聚類樹記為T。實驗中分別實現(xiàn)該算法和傳統(tǒng)凝聚層次聚類的F值，算法進行初始聚類劃分時的數(shù)目k分別取值為10、20、n/10，得到聚類結果F值比較如圖2所示，算法運行效率比較如圖3所示。

圖2　聚類結果F值折線對比圖

圖3　聚類算法耗時折線對比圖

從實驗結果可以看出，當初始聚類劃分數(shù)目較大時，采用本研究算法比傳統(tǒng)凝聚層次聚類算法的結果有較大改進；當初始聚類劃分數(shù)目較小時，雖然部分結果與傳統(tǒng)凝聚層次聚類算法相比效果稍差，但其聚類效率與前者相比有較大提高。因此，本研究農(nóng)業(yè)信息搜索可視化服務平臺的總體性能相比傳統(tǒng)農(nóng)業(yè)搜索引擎來講較好。

3.3運行實例

本文設計并實現(xiàn)了一個農(nóng)業(yè)信息搜索可視化服務平臺，向用戶提供了類似Google的搜索輸入界面，搜索結果返回前端可視化處理界面。圖4所示為對關鍵詞“小麥”的搜索結果，展示出了搜索相關詞之間的關系。關鍵詞之間關聯(lián)度越高，節(jié)點間連線距離越近；反之亦然。圖形還具有動態(tài)交互性，可以使用戶集中注意力于當前節(jié)點，并可以動態(tài)漸變地發(fā)現(xiàn)關鍵詞關聯(lián)關系的變化。

圖4　搜索“小麥”生成的可視化界面

4　結　語

本文針對農(nóng)業(yè)用戶信息搜索的需求，在農(nóng)業(yè)垂直搜索引擎工作原理的基礎上，結合Prefuse可視化技術構建了農(nóng)業(yè)信息搜索可視化服務平臺。通過信息抽取、關聯(lián)分析技術獲取領域概念，設計并實現(xiàn)了一種基于最大距離法選取初始質(zhì)心的K-means層次聚類算法，發(fā)現(xiàn)并改進領域概念間關系，提高聚類效率。此外將搜索相關詞以圖形化的形式呈現(xiàn)給用戶，通過網(wǎng)狀和樹形圖兩種方式向用戶快速、直觀地展示搜索結果，同時提供交互功能，通過該平臺可以輔助用戶進行二次檢索，明顯改善了用戶的搜索體驗。

在今后的工作中系統(tǒng)的功能還可以進一步擴展，如對可視化界面進一步美觀，增加用戶體驗；對不同專業(yè)領域、大數(shù)據(jù)集數(shù)據(jù)進行更全面的驗證。

[1] 李廣麗，劉覺夫. 垂直搜索引擎系統(tǒng)的研究與實現(xiàn) [J].情報雜志,2009,28(10):144-147.

[2] 王曉琴，李書琴，景旭,等. 基于Nutch的農(nóng)業(yè)垂直搜索引擎研究[J].計算機工程與設計，2014,35(6):2239-2243.

[3] 張陽. 農(nóng)業(yè)搜索可視化平臺的研究 [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]. 現(xiàn)代圖書情報技術,2012,28(4):35-40.

[7] 陳穎，白淑琴，張學福. 基于共詞分析的中文信息檢索可視化研究[J].情報科學,2009,27(2):227-230.

[8] 馮碩,李書琴,楊會君. 基于Web挖掘的化學物質(zhì)信息提取應用研究[J]. 計算機工程與設計，2012,33(8):3040-3046.

[9] 石倩,陳榮,魯明羽. 基于規(guī)則歸納的信息抽取系統(tǒng)實現(xiàn)[J]. 計算機工程與應用，2008,44(21):166-170.

[10] 王超,李書琴,肖紅.基于文獻的農(nóng)業(yè)領域本體自動構建方法研究[J]. 計算機應用與軟件，2014,31(8):71-74.

[11] 馮穎.醫(yī)學本體融合與可視化系統(tǒng)的設計與實現(xiàn)[D]. 湖北：華中科技大學,2012.

[12] 趙華軍,鐘才明,李文,等.網(wǎng)頁搜索結果聚類與可視化[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)；中央高校基本科研業(yè)務費項目(QN2011036)。王恬，碩士生，主研領域：：智能信息系統(tǒng)。李書琴，教授。王志偉，碩士生。

TP391

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