李 睿，聶晨光，龍文磊，沈春青，徐 征

（南京航空航天大學(xué)，南京 210016）

1 當(dāng)下的搜索引擎技術(shù)發(fā)展現(xiàn)狀

搜索引擎成為我們最為常用的信息檢索工具已經(jīng)成為了不爭的事實(shí)，到2014年底，我國的網(wǎng)民規(guī)模已達(dá)6.5億。有超過82％的用戶使用百度等常用搜索引擎作為獲取信息的主要手段。顯而易見，搜索引擎技術(shù)的發(fā)展對于推動(dòng)互聯(lián)網(wǎng)的進(jìn)步和發(fā)展具有重要的意義。然而，目前的搜索引擎還存在著很大的局限性。

其一是結(jié)果呈現(xiàn)形式，其二是語義。主流搜索引擎呈現(xiàn)形式以列表為主，其主要工作原理是利用網(wǎng)絡(luò)爬蟲，通過用戶輸入的關(guān)鍵字，遍歷信息集并采集相關(guān)條目，根據(jù)相關(guān)性順序列表展現(xiàn)。用戶根據(jù)列表，依次瀏覽搜索結(jié)果的標(biāo)題和摘要來確定他們所感興趣的信息。由于語義多義性廣泛存在，用戶也時(shí)常無法準(zhǔn)確地表達(dá)自身需求，導(dǎo)致歧義的搜索結(jié)果混合在一起。用戶在瀏覽搜索結(jié)果時(shí)需要人為將不感興趣的結(jié)果篩選出來并定位自己感興趣的信息，大大降低效率。［1］

2 信息可視化技術(shù)的發(fā)展

可視化技術(shù)的概念在20世紀(jì)80年代中被提出，而“信息可視化”的概念最初出現(xiàn)在1989年?？偟膩碚f，信息可視化技術(shù)是可視化技術(shù)在非空間數(shù)據(jù)領(lǐng)域的應(yīng)用，其核心是一個(gè)將數(shù)據(jù)和數(shù)據(jù)包含的信息轉(zhuǎn)化為直觀的符合人思維習(xí)慣的圖形的過程。信息可視化技術(shù)使用戶能夠以直觀的方式實(shí)現(xiàn)對數(shù)據(jù)和數(shù)據(jù)間的關(guān)系進(jìn)行觀察，進(jìn)而更全面地發(fā)現(xiàn)數(shù)據(jù)中隱藏的特征、關(guān)系和模式。

經(jīng)過近20年的發(fā)展，信息可視化技術(shù)已經(jīng)被細(xì)化到多個(gè)領(lǐng)域，包括：基于幾何的可視化方式；基于圖標(biāo)的可視化方式；基于時(shí)間序列的可視化方式；基于層次的可視化方式等。本文將著重闡述基于層次的可視化方式。

層次信息是一種常見的信息類型。我們每天接觸的文本信息就包含許多層次。層次信息的可視化主要包含節(jié)點(diǎn)連接圖和樹圖兩種方法。

節(jié)點(diǎn)鏈接圖：節(jié)點(diǎn)鏈接圖［2］是將層次信息組織成一個(gè)樹狀圖，根據(jù)層次的類屬關(guān)系分別形成父類和子類節(jié)點(diǎn)，以樹狀結(jié)構(gòu)連接，節(jié)點(diǎn)和連接線分別用來表示信息項(xiàng)和它們之間的關(guān)系。節(jié)點(diǎn)鏈接圖的優(yōu)點(diǎn)是能清晰直觀地展現(xiàn)層次數(shù)據(jù)內(nèi)的關(guān)系。缺點(diǎn)是子類分支之間的空白會(huì)浪費(fèi)展示空間。

樹圖：樹圖的概念（treemap）由Johnson等在1991年提出［3］。樹圖依靠一系列的圖塊的嵌套來展示信息和信息的層。，其優(yōu)點(diǎn)是能夠在有限的空間下展示更多的信息數(shù)據(jù)。其缺點(diǎn)是難以展示節(jié)點(diǎn)的內(nèi)容細(xì)節(jié)。

3 可視化技術(shù)在搜索引擎結(jié)果知識(shí)體系化輸出的方案設(shè)計(jì)

本方案的總體功能結(jié)構(gòu)如圖1所示，主要由用戶交互、網(wǎng)頁檢索、聚類處理、可視化處理和全文搜索引擎數(shù)據(jù)庫組成。矩形方框處為本方案的核心框架。搜索引擎首先從用戶交互界面接收用戶在界面中輸入的目標(biāo)字詞，將目標(biāo)發(fā)送到檢索模塊并從數(shù)據(jù)庫中返回相應(yīng)的結(jié)果集合。聚類處理模塊將對返回結(jié)果先進(jìn)行預(yù)處理，將預(yù)處理結(jié)果完成聚類并把聚類結(jié)果傳遞至可視化處理模塊，經(jīng)過可視化處理后通過用戶界面返回至用戶。接下來將繼續(xù)闡述本文的重點(diǎn)，即聚類處理模塊與可視化處理模塊。

圖1 總體功能結(jié)構(gòu)

3.1 聚類模塊設(shè)計(jì)

聚類模塊先對搜索結(jié)果信息進(jìn)行預(yù)處理，然后對預(yù)處理過后的統(tǒng)一格式的數(shù)據(jù)集利用聚類算法對搜索結(jié)果進(jìn)行聚類。將相似度較高的搜索結(jié)果歸為一類并為每一個(gè)類定義一個(gè)具體的聚類標(biāo)簽，根據(jù)聚類后的結(jié)果子集使用排序算法依照相關(guān)性再排序。因此搜索結(jié)果聚類模塊的總體設(shè)計(jì)主要由三部分組成：數(shù)據(jù)預(yù)處理子模塊，聚類生成子模塊和聚類子集排序模塊。

3.1.1 文本預(yù)處理

（1）文檔分詞。分詞的過程是將文檔中的語句按照語言的相應(yīng)規(guī)則劃分為詞語或短語的過程。分詞結(jié)果的質(zhì)量也影響著后續(xù)短語的提取和聚類標(biāo)簽的生成?；谠~典或詞庫的分詞過程包括：詞典初始化、文本輸入、文本結(jié)構(gòu)化處理、分詞/粗分、消除歧義與識(shí)別未登錄詞、更新詞典和結(jié)果保存。

（2）詞干解析。詞干解析對于處理英文文本的意義要大于處理中文文本的意義。英文單詞的衍生詞和詞的形態(tài)變化十分常見。例如play是一個(gè)詞干，它能衍生出player，plays，played，playing等等不同時(shí)態(tài)不同人稱但意義相同的詞。

（3）去除停詞。通過文檔分詞，文檔已經(jīng)被劃分為一系列的單詞。但是這一過程并沒有過濾掉文檔的無效信息。一些語氣詞、虛詞和助詞的詞頻很高，但與用戶需求匹配度低。有時(shí)這些詞出現(xiàn)次數(shù)較多會(huì)影響接下來高頻詞提取和聚類標(biāo)簽生成的過程?？梢栽谒阉饕孢\(yùn)行前預(yù)先將停詞表加載到內(nèi)存中，在分詞后使用停用詞接口方法判定單詞是否在停用詞表中。

（4）高頻短語提取。提取文檔高頻短語的目的是高度概述文檔并提供有限個(gè)聚類標(biāo)簽的候選者。因此，高頻短語提取的準(zhǔn)確信直接關(guān)系到聚類標(biāo)簽生成的效果。針對這些要求，后綴數(shù)組是一種高效準(zhǔn)確的方法。設(shè)一個(gè)文檔T，長度為N。T的后綴數(shù)組s是指將T所有的后綴按照字符順序排序，而令后綴起始的位置（按排序后的順序）構(gòu)成的數(shù)組。［4］

3.1.2 聚類處理

我們把頻率超過一定閾值的詞條定義為高頻短語。這可以從預(yù)處理結(jié)果中獲取。通過這些數(shù)據(jù)再利用向量空間模型對文檔建模。通過隱含語義索引技術(shù)和矩陣降維可以發(fā)現(xiàn)文檔之間的主題相關(guān)性以及相關(guān)主題。根據(jù)主題對文檔進(jìn)行聚類，完成對預(yù)處理結(jié)果的二次處理。

（1）生成聚類標(biāo)簽。通過預(yù)處理我們已經(jīng)得到了文檔的高頻短語，創(chuàng)建特征詞-文檔矩陣T，對矩陣T進(jìn)行奇異值分解（SVD），得到一個(gè)正交基向量U。根據(jù)該正交基向量與高頻短語（候選聚類標(biāo)簽）的匹配結(jié)果，確定出最終的聚類標(biāo)簽。

（2）聚類生成。根據(jù)VSM建立的文檔模型，我們已經(jīng)可以直接通過k-means方法對文檔進(jìn)行聚類。

（3）聚類內(nèi)部排序。聚類的標(biāo)簽生成后?？梢钥匆姌?biāo)簽下包含著一個(gè)文檔集。最后根據(jù)之前的特征詞-文檔矩陣計(jì)算得到的文檔對于聚類標(biāo)簽詞的TFIDF值的大小降序排列。還可以結(jié)合用戶行為統(tǒng)計(jì)數(shù)據(jù)進(jìn)行加權(quán)分析，調(diào)整最終排序結(jié)果。

3.1.3 可視化處理

本方案中的用戶交互界面設(shè)計(jì)采用輻射圖和樹圖兩種方法進(jìn)行結(jié)果的展示。樹狀結(jié)構(gòu)是輸出聚類結(jié)果的最好選擇。就單次搜索聚類得到的結(jié)果而言，可以生成一棵簡單的以搜索關(guān)鍵詞為父節(jié)點(diǎn)，結(jié)果聚類標(biāo)簽為子節(jié)點(diǎn)的樹。對于結(jié)果聚類較多的情況可以星射狀的樹結(jié)構(gòu)完成輸出。這對后面映射到樹圖的結(jié)果不會(huì)產(chǎn)生很多影響。

可視化模塊的另一個(gè)關(guān)鍵構(gòu)件是用戶行為統(tǒng)計(jì)。對每次聚類結(jié)果輸出后用戶選擇的領(lǐng)域方向進(jìn)行記錄。在一段時(shí)間后，積累了個(gè)體用戶對于某一領(lǐng)域的多次搜索記錄后，通過不同記錄樹節(jié)點(diǎn)的語義消歧和識(shí)別，可以生成一棵用戶近期對于某一領(lǐng)域探索的知識(shí)樹。這棵樹為用戶提供了一個(gè)時(shí)間維的視角來審視自己對于某個(gè)領(lǐng)域的了解發(fā)現(xiàn)過程，真正形成搜索結(jié)果的知識(shí)體系化輸出。

4 結(jié)束語

時(shí)下主流的搜索引擎工具均是單純以列表的形式為用戶呈現(xiàn)搜索結(jié)果。這一顯示方式降低了用戶尋找目標(biāo)信息的效率，并且這個(gè)問題對于學(xué)術(shù)研究人員的負(fù)面影響更為顯著。

本設(shè)計(jì)方案的主要?jiǎng)?chuàng)新之處在于添加了用戶行為統(tǒng)計(jì)模塊修正樹狀可視化結(jié)構(gòu)的個(gè)性化模塊，并且還提供了不同的可視化方式進(jìn)行聚類結(jié)果的呈現(xiàn)，另外，基于用戶在同一領(lǐng)域中多次搜索聚類結(jié)果生成知識(shí)樹，為用戶提供了審視自己階段性工作成果的能力。

［1］趙宇.計(jì)算機(jī)檢索工具的發(fā)展與應(yīng)用［J］.中小企業(yè)管理與科技，2011（4）：271-272.

［2］G Robertson，S K Card，J D Mackinlay.The Congnitive Coprocessor Architecture for Interactive User Interfaces［C］.Proceedings of the 2nd Annual ACM SIGGRAPH Symposium on User interface Software and Technology，New York，1989.

［3］張昕，袁曉如.樹圖可視化［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2012，24（9）：1113-1124.

［4］朱光楠.基于聚類的搜索可視化呈現(xiàn)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)［D］.北京：北京郵電大學(xué)，2012.

［5］周登朋.搜索引擎搜索結(jié)果的聚類研究［D］.上海：上海交通大學(xué)，2007.