王　恬　李書琴　王志偉

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

?

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

王恬李書琴*王志偉

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

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

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

0　引　言

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

國外的農(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ā)展時期，存在一些不完善的地方：首先搜索結(jié)果中仍包含了大量的信息[3]，搜索準(zhǔn)確率和用戶滿意度較低；其次用戶往往需要順序瀏覽搜索結(jié)果列表來查找他們所需要的信息，忽略了用戶在瀏覽時的交互作用。

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

1　研究架構(gòu)

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

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

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

2　系統(tǒng)關(guān)鍵技術(shù)

2.1Web信息抽取

本文參考馮碩等人[8]實現(xiàn)的基于包裝器的Web信息抽取技術(shù)，獲取相關(guān)網(wǎng)站中農(nóng)業(yè)領(lǐng)域文獻(xiàn)的題目、摘要和關(guān)鍵詞作為領(lǐng)域語料?；玖鞒虨椋菏紫葘⒋槿〉捻撁鎕tmlFile解析為DOM(DocumentObjectModel)數(shù)結(jié)構(gòu)的文檔，然后根據(jù)樹中對應(yīng)的節(jié)點node確定目標(biāo)數(shù)據(jù)項的左右邊界，根據(jù)邊界來定位數(shù)據(jù)項，實現(xiàn)對不同信息源信息的抽取。

2.2關(guān)聯(lián)分析技術(shù)

(1) 中文分詞

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

(2) 領(lǐng)域相關(guān)度判斷

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

(1)

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

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

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

(2)

(3)

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

2.3領(lǐng)域概念聚類

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

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

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

輸入：領(lǐng)域概念集合

輸出：領(lǐng)域概念聚類樹

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

Step1.1計算數(shù)據(jù)集中M個數(shù)據(jù)點兩兩之間的距離{distance(di,dj)，(i,j=1,2,…,M) }將距離最遠(yuǎn)的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對每一個約束類，應(yīng)用UPGMA凝聚層次聚類算法生成一顆聚類樹。

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

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

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

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

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

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

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

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

表1　領(lǐng)域概念相似矩陣

3.2實驗結(jié)果分析

(1) 中文分詞結(jié)果分析

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

表2　中文分詞結(jié)果比較

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

(2) 聚類結(jié)果分析

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

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

圖2　聚類結(jié)果F值折線對比圖

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

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

3.3運行實例

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

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

4　結(jié)　語

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

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

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

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

[3] 張陽. 農(nóng)業(yè)搜索可視化平臺的研究 [D]. 安徽：中國科學(xué)技術(shù)大學(xué),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)代圖書情報技術(shù),2012,28(4):35-40.

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

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

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

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

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

[12] 趙華軍,鐘才明,李文,等.網(wǎng)頁搜索結(jié)果聚類與可視化[J].南京大學(xué)學(xué)報：自然科學(xué)，2010,46(5):542-551.

[13] 翟東海,魚江,高飛,等. 最大距離法選取初始簇中心的K-means文本聚類算法的研究[J]. 計算機(jī)應(yīng)用研究，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(yè)務(wù)費項目(QN2011036)。王恬，碩士生，主研領(lǐng)域：：智能信息系統(tǒng)。李書琴，教授。王志偉，碩士生。

TP391

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