梁仁華 彭 鑫 Zhenchang Xing 趙文耘

1(復(fù)旦大學(xué)軟件學(xué)院 上海 201203) 2(上海市數(shù)據(jù)科學(xué)重點(diǎn)實(shí)驗(yàn)室 上海 201203) 3(澳大利亞國(guó)立大學(xué)計(jì)算機(jī)科學(xué)研究院 堪培拉 2615)

基于知識(shí)抽取的軟件問答網(wǎng)站搜索優(yōu)化設(shè)計(jì)

梁仁華1,2彭 鑫1,2Zhenchang Xing3趙文耘1,2

1(復(fù)旦大學(xué)軟件學(xué)院 上海 201203)2(上海市數(shù)據(jù)科學(xué)重點(diǎn)實(shí)驗(yàn)室 上海 201203)3(澳大利亞國(guó)立大學(xué)計(jì)算機(jī)科學(xué)研究院 堪培拉 2615)

軟件問答網(wǎng)站基于關(guān)鍵詞的搜索機(jī)制往往并不能很好地幫助用戶找到問題的答案。眾多的返回結(jié)果造成信息迷航，用戶需要花費(fèi)額外的時(shí)間來篩選出自己所需要的信息。針對(duì)這種情況，基于Stack Overflow提供的文本信息，提出通過文本主題聚類結(jié)合多刻面技術(shù)的方法。對(duì)搜索結(jié)果以及鏈接關(guān)系等信息進(jìn)行知識(shí)抽取，幫助用戶理解搜索結(jié)果的主題以及方向。設(shè)計(jì)一種力導(dǎo)引加樹形布局的可視化模型對(duì)知識(shí)進(jìn)行表達(dá)。實(shí)現(xiàn)了一個(gè)基于Web的動(dòng)態(tài)交互可視化工具，基本達(dá)到了解決信息迷航，幫助用戶定位問題答案的搜索優(yōu)化目的。

知識(shí)抽取 文本主題聚類 多刻面 可視化 軟件問答網(wǎng)站

0 引 言

軟件問答網(wǎng)站是一種基于用戶知識(shí)分享行為的交互網(wǎng)站。其獨(dú)特的可交互性及社交化吸引了越來越多的人們。以軟件領(lǐng)域的大型問答網(wǎng)站——Stack Overflow為例，截止到2017年1月，Stack Overflow上已發(fā)布了13 085 624個(gè)帖子，涉及到程序員在軟件領(lǐng)域中遇到的各類問題，受到眾多程序員的關(guān)注。當(dāng)我們想在軟件問答網(wǎng)站上發(fā)布一個(gè)帖子時(shí)，首先想到的是搜索是否已有人發(fā)布了類似問題的帖子，方便我們找到現(xiàn)有的答案。然而軟件問答網(wǎng)站基于關(guān)鍵詞的搜索機(jī)制往往并不能很好地幫助用戶找到問題的答案。眾多的返回結(jié)果造成信息迷航，一旦用戶輸入的關(guān)鍵詞不準(zhǔn)確或者不夠概括問題的核心，用戶就需要花費(fèi)更多的時(shí)間來篩選出自己所需要的信息，無法高效地找到與自己?jiǎn)栴}最相似的帖子。而且對(duì)于用戶來說，準(zhǔn)確地輸入能描述問題的核心關(guān)鍵詞也并不是一件易事。

面對(duì)這種情況，研究人員提出了多種方法來優(yōu)化軟件問答網(wǎng)站的搜索機(jī)制。Barua等人在文獻(xiàn)[1]中用基于主題識(shí)別的算法挖掘了程序員在Stack Overflow上所關(guān)心的重要主題，幫助用戶找到合適的主題社區(qū)，縮小搜索范圍。Wei Wang等人在文獻(xiàn)[2]中提出了一種基于社交網(wǎng)絡(luò)分析以及主題挖掘的方法來幫助定義與應(yīng)用程序編程接口(API)設(shè)計(jì)的相關(guān)問題的主題描述。該方法可以推薦給API設(shè)計(jì)者與自己?jiǎn)栴}更相關(guān)的帖子。上述研究對(duì)于搜索優(yōu)化都能起到一定的效果。但是，推薦主題社區(qū)的方法返回的搜索結(jié)果數(shù)量還是較多，不利于用戶理解某個(gè)主題內(nèi)部的內(nèi)容。API信息提取相對(duì)單一，并不能解決所有的問題。

針對(duì)上述問題，本文提出了一種搜索優(yōu)化方法。該方法結(jié)合文本主題聚類和多刻面技術(shù)，對(duì)基于關(guān)鍵詞搜索的返回結(jié)果進(jìn)行知識(shí)抽取。本文選取被廣泛使用的軟件問答網(wǎng)站——Stack Overflow的站內(nèi)數(shù)據(jù)進(jìn)行分析。在文本主題聚類中，將Stack Overflow中表示鏈接行為的Linked信息加入到主題抽取中，形成更多的帖子聚類來幫助用戶理解搜索結(jié)果的主題以及方向。在多刻面技術(shù)分析中，定義了刻面信息，并針對(duì)用戶主動(dòng)選擇的不合理性，用層次聚類的方法自動(dòng)分析多刻面的分類結(jié)果。最后設(shè)計(jì)了一種將主題聚類和刻面信息應(yīng)用于力導(dǎo)引加樹形布局的可視化模型。最終實(shí)現(xiàn)了一個(gè)基于Web的動(dòng)態(tài)交互可視化工具，基本達(dá)到了解決信息迷航，幫助用戶方便、快速地理解搜索結(jié)果以及定位問題答案的搜索優(yōu)化目的。

1 相關(guān)工作

1.1 文本聚類算法

文本聚類算法是一種根據(jù)輸入的文本信息進(jìn)行聚類以及定義各個(gè)聚類主題的算法。早期的文本聚類算法大都基于數(shù)據(jù)而劃分。如K-means算法，是一種基于距離的聚類算法。這種算法能很好的對(duì)文本數(shù)據(jù)進(jìn)行處理，但是有一個(gè)顯著的問題，即對(duì)聚類主題的產(chǎn)生。針對(duì)如何產(chǎn)生幫助用戶理解的聚類主題問題，Zamir等人在文獻(xiàn)[4]中提出了后綴樹聚類算法(STC)。該算法生成了一個(gè)基于輸入文本的廣義后綴樹，并通過廣義后綴樹統(tǒng)計(jì)高頻單詞和短語作為基本聚類，之后對(duì)基本聚類進(jìn)行合并，最終形成聚類結(jié)果。相對(duì)于先生成聚類再生成聚類主題的STC算法，Stanislaw Osinski等人在文獻(xiàn)[5]中提出了一種基于奇異值分解的聚類算法(Lingo)。Lingo算法先提取聚類主題，再將各個(gè)文本分配到不同的聚類中去，最終形成聚類。相較于STC算法，Lingo算法產(chǎn)生的聚類主題具有更多的描述，本文主要采用Lingo聚類算法。

1.2 Stack Overflow相關(guān)研究

近年來Stack Overflow的相關(guān)研究中，對(duì)于發(fā)帖問題的相關(guān)性研究越來越多。而Stack Overflow的Linked信息記錄了用戶自主地對(duì)相同或相關(guān)問題進(jìn)行鏈接的行為。因此，Linked信息擁有反映帖子之間文本相似性以及語義關(guān)系的作用也吸引了眾多研究者的關(guān)注。Yun Zhang等人在文獻(xiàn)[6]中實(shí)現(xiàn)了一個(gè)在Stack Overflow上查找相同問題的工具DupPredictor。該工具通過用戶輸入問題的tag、title等信息查找是否存在相同的問題，幫助網(wǎng)站管理員人工進(jìn)行Duplicate和Linked信息的補(bǔ)充。Deheng Ye等人在文獻(xiàn)[7]中結(jié)合Linked信息對(duì)軟件工程知識(shí)的相關(guān)性進(jìn)行了研究，得到了卷積神經(jīng)網(wǎng)絡(luò)(CNN)模型，并用于對(duì)Stack Overflow上兩個(gè)帖子是否是相同問題的判定。而Dasha Bogdanova等人在文獻(xiàn)[8]中，通過對(duì)問題的文本信息進(jìn)行分析，提取出基于Wikipedia的軟件領(lǐng)域詞匯，并使用支持向量機(jī)(SVM)和CNN模型對(duì)問題的相似性進(jìn)行判斷。與這些抽取知識(shí)來判斷問題相關(guān)性以及相同性的工作相比，我們主要基于具有Linked關(guān)系的帖子的文本相似性進(jìn)行主題聚類，提取帖子的主題詞，來幫助用戶更好地理解搜索結(jié)果。

1.3 可視化布局

數(shù)據(jù)可視化是一種將圖形、圖像等可視化方法應(yīng)用于傳統(tǒng)數(shù)據(jù)的分析或者解釋的技術(shù)。它可以聚焦并且形象化地展示數(shù)據(jù)信息中的核心部分，有助于人們快速的獲得以及理解數(shù)據(jù)信息。文本數(shù)據(jù)可視化大都針對(duì)詞匯、主題等信息進(jìn)行可視化布局。如PNNL(Pacific Northwest National Laboratory)開發(fā)的IN-SPIRETM[9]是基于文本主題抽取的可視化工具。該工具提出了兩種可視化布局，一種是3D地勢(shì)圖，基于距離的遠(yuǎn)近定義文本間的相似度，并把相近的文本形成山峰；另一種是平面上的星云圖來展示聚類的文本相似程度以及離散形態(tài)。另外，還有一些針對(duì)層次化聚類結(jié)果繪制的樹狀圖、金字塔圖等可視化布局。這些研究工作大都基于靜態(tài)數(shù)據(jù)的可視化分析，交互手段相對(duì)單一。我們主要根據(jù)主題聚類結(jié)果以及多刻面信息，使用力導(dǎo)引加以樹形布局，動(dòng)態(tài)地從橫向擴(kuò)展、垂直深入兩種交互方式展示聚類結(jié)果的可視化信息。

2 聚類及多刻面可視化設(shè)計(jì)

文本主題聚類可以根據(jù)搜索結(jié)果的帖子內(nèi)容提取出相關(guān)主題。這些主題作為知識(shí)抽取的結(jié)果，可以很好地區(qū)分出不同帖子集合的內(nèi)容，但是還是會(huì)產(chǎn)生帖子數(shù)目相對(duì)較多的聚類，不利于用戶快速理解某個(gè)聚類中帖子的內(nèi)容。而多刻面技術(shù)是基于帖子內(nèi)容的不同特征，定義出一些基本刻面詞來對(duì)知識(shí)進(jìn)行表達(dá)，之后分析每個(gè)帖子的文本內(nèi)容，抽取出刻面信息來特征化每個(gè)帖子。這種方法能很好地對(duì)文本進(jìn)行分類，但是對(duì)用戶查找合適搜索結(jié)果的有效性主要基于用戶對(duì)刻面的選擇。用戶選出的刻面組合往往并不能很好地劃分搜索結(jié)果集合，返回的搜索結(jié)果數(shù)目會(huì)出現(xiàn)過多或者過少的狀況。針對(duì)上述情況，我們提出了文本主題聚類與多刻面技術(shù)相結(jié)合的知識(shí)抽取方法，在文本主題聚類的基礎(chǔ)上，對(duì)每個(gè)聚類結(jié)果進(jìn)行多刻面分析并對(duì)刻面信息進(jìn)行層次聚類，幫助用戶更好地理解搜索結(jié)果，快速地尋找合適的搜索答案。

文本主題聚類結(jié)合多刻面技術(shù)的可視化設(shè)計(jì)如圖1所示。我們首先對(duì)Stack Overflow上所有帖子的文本信息利用全文搜索引擎——Lucene建立了文本索引。用戶輸入關(guān)鍵詞，我們用Lucene進(jìn)行關(guān)鍵詞搜索得到搜索結(jié)果，并返回了包含帖子各部分的文本信息。之后，我們將這些搜索結(jié)果的文本信息進(jìn)行數(shù)據(jù)預(yù)處理，對(duì)搜索結(jié)果進(jìn)行主題聚類，在這個(gè)過程中，我們采取的文本聚類算法是Lingo算法。然后對(duì)每個(gè)聚類結(jié)果進(jìn)行多刻面分析。最后，我們將這些聚類信息和刻面信息用力導(dǎo)引加以樹形結(jié)構(gòu)的布局進(jìn)行可視化，并實(shí)現(xiàn)了多種交互手段。在文本顯示方面主要有兩種方式：一種是橫向擴(kuò)展，基于Linked信息，對(duì)某個(gè)聚類中的所有帖子找到與之有Linked關(guān)系的相關(guān)帖子，進(jìn)行再聚類；另一種是垂直深入，對(duì)某個(gè)聚類中的帖子進(jìn)行多刻面分析。該可視化布局可以更方便地使用戶理解搜索結(jié)果，并能通過這些交互模式快速地找到相關(guān)答案。

圖1 可視化模型概述

2.1 文本主題聚類

主題聚類之前對(duì)數(shù)據(jù)的操作主要有數(shù)據(jù)預(yù)處理和數(shù)據(jù)選取兩方面，應(yīng)用聚類算法的數(shù)據(jù)除了根據(jù)關(guān)鍵詞返回的搜索結(jié)果，還包括基于這些搜索結(jié)果擴(kuò)展出的Linked信息。本文選取的文本主題聚類算法是Lingo算法。

2.1.1 數(shù)據(jù)預(yù)處理

本文從Stack Exchange網(wǎng)站上得到Stack Overflow的數(shù)據(jù)源。首先將帖子的原始數(shù)據(jù)中title、tag、body等文本信息用Lucene建立索引。之后，根據(jù)用戶輸入的關(guān)鍵詞用Lucene進(jìn)行搜索。本文設(shè)置搜索結(jié)果的最大數(shù)目為10 000。由于用戶往往希望短時(shí)間內(nèi)對(duì)搜索結(jié)果有一定的理解，過多的文本信息會(huì)對(duì)用戶篩選符合的帖子產(chǎn)生干擾，所以將返回的搜索結(jié)果中與關(guān)鍵詞匹配度最高的300個(gè)搜索結(jié)果，用于下一步聚類操作。這些搜索結(jié)果作為聚類的輸入，需要提取有含義的聚類主題詞，所以對(duì)這些搜索結(jié)果中每個(gè)帖子的title、tag和body等文本信息進(jìn)行了如下幾步操作：(1)分詞：以非字母字符作為分割符號(hào)進(jìn)行詞匯的分析和分割，并去除如標(biāo)點(diǎn)符號(hào)等一些無意義的特殊字符。(2)去除停用詞：文本描述中經(jīng)常出現(xiàn)一些常見詞，但是并無太大價(jià)值，例如“the”、“a”等詞語，這些字詞被稱作停用詞。(3)詞根化：出于語法上不同語境的要求，在文本描述時(shí)通常會(huì)用一個(gè)詞的不同形態(tài)進(jìn)行表達(dá)。比如implement、implements和implementing。另外，文本中也存在許多意思相近的同源詞，比如history、historic和historical。詞根化可以統(tǒng)一文本內(nèi)容的描述，減少表達(dá)形式的變化。本文使用MIT的計(jì)算機(jī)科學(xué)與人工智能實(shí)驗(yàn)室開發(fā)的WordNet和jwi工具對(duì)文本信息進(jìn)行去除停用詞和詞根化操作。

2.1.2 Linked信息

只根據(jù)搜索結(jié)果的文本信息進(jìn)行主題聚類的結(jié)果有時(shí)不能很好地表達(dá)文本信息的含義。而Stack Overflow上的Linked信息基于用戶自主地對(duì)相同或相關(guān)問題進(jìn)行鏈接的行為，具有描述帖子之間文本相似性以及語義上的關(guān)系的作用。用每個(gè)帖子擴(kuò)展出的有Linked關(guān)系的帖子進(jìn)行文本聚類，可以聚類出更反映文本信息中心的主題詞，幫助用戶理解帖子的文本內(nèi)容以及搜索方向。對(duì)于由主題聚類產(chǎn)生的每個(gè)聚類，本文用廣度優(yōu)先算法選取至多與該聚類中的帖子有Linked關(guān)系的300個(gè)帖子進(jìn)行再聚類，作為該聚類擴(kuò)展出的聚類結(jié)果。每個(gè)聚類的擴(kuò)展過程如下：聚類中的所有帖子作為初始層，依次遍歷初始層的每個(gè)帖子，選取所有與之有Linked關(guān)系的帖子，去除冗余帖子，作為下一層。重復(fù)迭代，直到選取出300個(gè)帖子或者下一層中不存在沒被選取過的帖子。如果最后一層的帖子數(shù)目與之前所有帖子數(shù)目相加超出300個(gè)，最后一層的帖子按與搜索關(guān)鍵詞的文本相似度排序，選取相似度最高的帖子，直到數(shù)目達(dá)到300個(gè)。

2.1.3 Lingo算法

Lingo算法來自于開源聚類項(xiàng)目Carrot2，是一種基于奇異值分解(SVD)的聚類算法[5]。主要步驟分為聚類特征提取、歸納聚類標(biāo)記以及聚類內(nèi)容挖掘。本文使用了Carrot2提供的jar包中的Lingo算法。根據(jù)實(shí)際結(jié)果，設(shè)置了desiredClusterCountBase參數(shù)的值為12。該參數(shù)可以很好地控制聚類的個(gè)數(shù)，根據(jù)輸入的文本個(gè)數(shù)的大小，產(chǎn)生合適的聚類數(shù)量，數(shù)值越大，產(chǎn)生的聚類數(shù)量越多。相較于STC算法，Lingo算法提供的每個(gè)聚類的主題詞長(zhǎng)度更長(zhǎng)，描述更加準(zhǔn)確，并能產(chǎn)生帖子數(shù)目少但主題相關(guān)度高的聚類。本文用關(guān)鍵詞搜索返回的結(jié)果進(jìn)行初始聚類，之后對(duì)每個(gè)聚類基于Linked關(guān)系提供擴(kuò)展聚類。

2.2 多刻面技術(shù)

刻面是一種對(duì)資源進(jìn)行描述的術(shù)語，一個(gè)刻面代表資源的一種特征。多刻面技術(shù)可以根據(jù)刻面信息對(duì)資源進(jìn)行特征抽取并進(jìn)行分類[3]。本文引用了復(fù)旦大學(xué)軟件工程實(shí)驗(yàn)室的刻面分類工作中的刻面定義以及基于每個(gè)帖子內(nèi)容提取出的刻面信息[10]。表1為前述工作中的刻面定義，每個(gè)大類中列舉了該類刻面集合的所有刻面詞。

表1 刻面信息

然而，傳統(tǒng)的應(yīng)用多刻面技術(shù)進(jìn)行搜索優(yōu)化的方法依賴于用戶對(duì)刻面信息的選擇。當(dāng)用戶選擇出一組刻面信息時(shí)，我們?cè)賹?duì)搜索結(jié)果進(jìn)行劃分，選取出包含這組刻面信息的搜索結(jié)果。這種交互模式就會(huì)產(chǎn)生如下問題：

(1) 刻面組合的合理性：用戶無法確定哪些刻面是作為答案的帖子中會(huì)出現(xiàn)的，一旦選擇的刻面組合不合理，就會(huì)丟失這部分可以作為答案的帖子，對(duì)搜索的有效性和正確性都會(huì)產(chǎn)生影響。

(2) 刻面組合對(duì)分類的影響：用戶并不知道刻面組合對(duì)于搜索結(jié)果的完整分類情況，當(dāng)選擇一些刻面時(shí)，可能這些刻面共同出現(xiàn)在搜索結(jié)果中的頻率較高，造成返回的分類結(jié)果數(shù)目較多，不利于用刻面來劃分搜索結(jié)果。

針對(duì)上述情況，本文用層次聚類的方法自動(dòng)分析多刻面的分類結(jié)果，使用戶掌握刻面劃分下的完整分類情況。相較于將分類結(jié)果按文本陳列的方式顯示，層次聚類可以將相近的刻面類別聚在一起，條理清晰地按樹形結(jié)構(gòu)顯示刻面的不同劃分結(jié)果。本文主要采取自底向上的凝聚方式進(jìn)行聚類。算法將主題聚類中產(chǎn)生的某個(gè)聚類中的所有帖子作為輸入，最終構(gòu)造出層次聚類的樹形結(jié)構(gòu)。算法首先將輸入中的所有帖子，按照具有完全相同刻面信息的帖子歸入一類的方法，將這些分類結(jié)果作為初始聚類節(jié)點(diǎn)，并將刻面信息作為這些聚類的文本描述。之后計(jì)算節(jié)點(diǎn)之間文本相似度，即刻面重合的個(gè)數(shù)，選取其中相似度最高的兩個(gè)節(jié)點(diǎn)合并。如果重合刻面與所有聚類節(jié)點(diǎn)的文本描述均不同，則生成一個(gè)新的聚類節(jié)點(diǎn)，將重合刻面作為這個(gè)聚類的文本描述，被選取的兩個(gè)節(jié)點(diǎn)作為這個(gè)聚類的子節(jié)點(diǎn)；如果重合刻面與某個(gè)聚類節(jié)點(diǎn)的文本描述相同，則將這兩個(gè)節(jié)點(diǎn)作為該聚類節(jié)點(diǎn)的子節(jié)點(diǎn)；如果重合刻面為這兩個(gè)節(jié)點(diǎn)中的其中一個(gè)，則將另一個(gè)節(jié)點(diǎn)作為該節(jié)點(diǎn)的子節(jié)點(diǎn)。所有子節(jié)點(diǎn)將不被作為下一輪的聚類節(jié)點(diǎn)。重復(fù)上述合并聚類節(jié)點(diǎn)的過程，直到剩下一個(gè)節(jié)點(diǎn)，或者搜索節(jié)點(diǎn)之間沒有重復(fù)刻面信息停止。最終將剩下的所有聚類節(jié)點(diǎn)作為根節(jié)點(diǎn)的子節(jié)點(diǎn)，形成層次聚類樹。

算法1層次聚類算法

輸入：某個(gè)聚類中的所有帖子Posts

輸出：層次聚類結(jié)構(gòu)樹Tree

Class Node{

String description;

List p;

List children;

}

Function cluster(Posts)

1. 將Posts按刻面信息分類，每一類用Node對(duì)象表示，添加到List TreeNode 中

2. While(TreeNode.size > 1)

3. 在TreeNode中選取重復(fù)刻面長(zhǎng)度最大的兩個(gè)

不同節(jié)點(diǎn)N1,N2;

4. if repeatFacet.length == 0 then break;

5. end if

6. if repeatFacet == N1.description then

7. N1.children.add(N2);TreeNode.remove(N2);continue;

8. end if

9. if repeatFacet == N2.description then

10. N2.children.add(N1);TreeNode.remove(N1);continue;

11. end if

12. for everyNode in TreeNode

13. flag = false;

14. if everyNode.description == repeatFacet then

15. everyNode.children.add(N1);

everyNode.children.add(N2);

flag = true;break;

16. end if

17. end for

18. if(!flag) then

19. new Node n;n.description = repeatFacet;

n.children.add(N1);n.children.add(N2);

TreeNode.add(n);

20. end if

21. TreeNode.remove(N1);TreeNode.remove(N2);

22. end while

23. new Node Tree;Tree.addAll(TreeNode);

end Function

2.3 布局設(shè)計(jì)

本文設(shè)計(jì)的文本主題聚類以及多刻面層次聚類模型均可以用樹形結(jié)構(gòu)來表達(dá)。傳統(tǒng)的樹形可視化布局，在層與層之間父子節(jié)點(diǎn)的距離以及每層之間兄弟節(jié)點(diǎn)的距離都是統(tǒng)一的，而本文聚類結(jié)果中每個(gè)節(jié)點(diǎn)的大小用于表示聚類中帖子的數(shù)目大小。所以用于表示聚類節(jié)點(diǎn)的面積大小大都不相同，用傳統(tǒng)的樹形布局來可視化會(huì)造成界面覆蓋，節(jié)點(diǎn)之間相互遮掩的狀況出現(xiàn)。因此，本文在樹形布局基礎(chǔ)上加入了力導(dǎo)引布局來實(shí)現(xiàn)可視化模型，力導(dǎo)引布局可以通過設(shè)定不同節(jié)點(diǎn)間的作用力來改變節(jié)點(diǎn)間的距離。其中力導(dǎo)引布局主要基于d3.js的force布局來實(shí)現(xiàn)。布局針對(duì)文本主題聚類和多刻面層次聚類采取如下兩種交互手段來展示聚類結(jié)果。

2.3.1 橫向擴(kuò)展

該方式主要用來展示文本主題聚類的結(jié)果。如圖2所示：節(jié)點(diǎn)ClusterResults表示根節(jié)點(diǎn)，其子節(jié)點(diǎn)展示了基于關(guān)鍵詞搜索而返回的帖子的主題聚類結(jié)果。當(dāng)單擊某個(gè)子節(jié)點(diǎn)時(shí)，根據(jù)該子節(jié)點(diǎn)內(nèi)的所有帖子找到具有Linked關(guān)系的至多300個(gè)帖子再次進(jìn)行聚類，這些聚類結(jié)果作為該子節(jié)點(diǎn)的兒子節(jié)點(diǎn)。新生成的這些節(jié)點(diǎn)作為擴(kuò)展節(jié)點(diǎn)也可根據(jù)Linked關(guān)系再次進(jìn)行擴(kuò)展聚類。

圖2 橫向擴(kuò)展布局模型

2.3.2 垂直深入

該方式主要用來展示多刻面層次聚類的結(jié)果。如圖3所示：該布局通過雙擊圖2中的節(jié)點(diǎn)來得到。其中Cluster表示圖2中被雙擊的節(jié)點(diǎn)信息。根據(jù)層次聚類結(jié)果，Cluster代表樹形結(jié)構(gòu)的根節(jié)點(diǎn)，其余節(jié)點(diǎn)為聚類中產(chǎn)生的中間節(jié)點(diǎn)和初始時(shí)的根據(jù)刻面信息分類所產(chǎn)生的節(jié)點(diǎn)，與層次聚類產(chǎn)生的樹結(jié)構(gòu)相對(duì)應(yīng)。樹中邊的文本信息為父節(jié)點(diǎn)到子節(jié)點(diǎn)時(shí)增加的差異刻面信息。其中：無文本信息節(jié)點(diǎn)表示該節(jié)點(diǎn)只代表層次聚類產(chǎn)生的中間節(jié)點(diǎn)，并沒有帖子的刻面信息為該聚類的刻面描述。

圖3 垂直深入布局模型

兩種布局中，節(jié)點(diǎn)上的文本信息為該節(jié)點(diǎn)的聚類結(jié)果主題詞，括號(hào)部分的數(shù)字為該節(jié)點(diǎn)中包含的帖子的個(gè)數(shù)。節(jié)點(diǎn)的大小與該節(jié)點(diǎn)包含的帖子數(shù)目的大小成正比。節(jié)點(diǎn)的顏色表示節(jié)點(diǎn)中所有帖子與用戶輸入的搜索關(guān)鍵詞的相似度平均值，顏色越深代表相似度越高。鼠標(biāo)停在某個(gè)節(jié)點(diǎn)時(shí)，界面上同時(shí)會(huì)顯示該節(jié)點(diǎn)中含有的所有帖子的title，點(diǎn)擊title可以跳轉(zhuǎn)到Stack Overflow上相應(yīng)的帖子界面。兩種布局均支持拖拽和縮放功能。

3 可視化模型實(shí)例及實(shí)驗(yàn)

本節(jié)以一個(gè)問題的場(chǎng)景實(shí)例，來分析用戶如何通過本文的工具來找到Stack Overflow中可以解決該問題的帖子的過程。并設(shè)計(jì)了實(shí)驗(yàn)來分析本工具是否可以幫助用戶方便、快速地理解搜索結(jié)果并定位問題答案。

3.1 可視化模型實(shí)例

實(shí)例問題的場(chǎng)景描述如下：用戶在本地新建了一個(gè)Git庫(kù)，但是想忽略一些文件修改的追蹤信息。他對(duì)Git版本控制工具并不太了解，于是想在Stack Overflow上進(jìn)行相關(guān)搜索。針對(duì)該問題，用戶首先在圖4中的搜索框中輸入關(guān)鍵詞，例如：“how to ignore changes in git”。之后點(diǎn)擊“Analysis”按鈕，工具會(huì)對(duì)搜索結(jié)果進(jìn)行初始文本主題聚類分析，返回結(jié)果見圖5。用戶將鼠標(biāo)擱置在某個(gè)聚類時(shí)，界面右側(cè)會(huì)顯示該聚類中所有帖子的title信息，選取title可以跳轉(zhuǎn)到相應(yīng)的Stack Overflow上帖子的網(wǎng)頁(yè)。當(dāng)用戶對(duì)某一聚類感興趣時(shí)，可以通過單擊該聚類節(jié)點(diǎn)查看基于Linked信息的擴(kuò)展聚類結(jié)果。如在圖5中單擊“New Git”聚類節(jié)點(diǎn)后擴(kuò)展出的子節(jié)點(diǎn)。也可以直接查看該聚類內(nèi)部的多刻面分析結(jié)果，如圖6是雙擊圖5中“Git Gitignore”聚類節(jié)點(diǎn)后得到的可視化結(jié)果。此時(shí)，用戶可以根據(jù)邊上的刻面信息，通過路徑逐步找到存在的刻面組合，定位帖子的方向。通過這兩種交互手段，用戶可以快速地理解搜索結(jié)果主題，定位搜索方向，最終找到合適的答案。

圖4 搜索界面實(shí)例

圖5 文本主題聚類實(shí)例

圖6 多刻面分析實(shí)例

3.2 實(shí)驗(yàn)分析

本節(jié)先設(shè)計(jì)了一個(gè)對(duì)比實(shí)驗(yàn)來分析工具的有效性，并在完成對(duì)比實(shí)驗(yàn)后提出了一些驗(yàn)證性問題幫助我們分析。

實(shí)驗(yàn)方法為選取10位來自復(fù)旦大學(xué)軟件學(xué)院的學(xué)生，這些學(xué)生均有使用Stack Overflow的經(jīng)歷。實(shí)驗(yàn)選取5人一組，兩組學(xué)生分別使用工具和Stack Overflow來完成5個(gè)軟件領(lǐng)域的相關(guān)問題。這些問題均有詳細(xì)的場(chǎng)景描述，并且難易程度不等。通過分析實(shí)驗(yàn)過程，得到如表2的實(shí)驗(yàn)結(jié)果。

表2 實(shí)驗(yàn)結(jié)果

通過表2可以看出:使用工具的學(xué)生比使用Stack Overflow的學(xué)生完成問題的平均時(shí)間短，答對(duì)問題的個(gè)數(shù)也有所提高，說明工具可以快速幫助用戶找到問題的答案。而使用工具的學(xué)生輸入關(guān)鍵詞的次數(shù)的減少，表明工具可以幫助用戶理解搜索結(jié)果的主題和方向，用戶可以根據(jù)聚類得出的主題詞以及多刻面信息來減少自己主動(dòng)修正關(guān)鍵詞信息的行為。

在完成對(duì)比試驗(yàn)后，我們又設(shè)計(jì)了一些驗(yàn)證性問題詢問用工具解決問題的5名學(xué)生。問題如下：

(1) 是否覺得工具易于理解，可用性好？

(2) 主題聚類效果如何？聚類主題詞是否對(duì)用戶搜索方向有幫助？

(3) 層次聚類刻面信息是否比自主選擇更好？

(4) 可視化界面是否比文字列表效果更好？

(5) 有什么建議對(duì)該工具？

其中問題1、問題2，所有的學(xué)生均表示工具可用性好，相較于Stack Overflow的搜索機(jī)制，工具更能幫助自己找到答案并且效率較高。問題3中，4位同學(xué)表示聚類效果不錯(cuò)，對(duì)搜索方向有幫助。但是剩下的1位同學(xué)表示聚類主題詞中有一小部分不利于理解，主題詞不具有突出性。問題4中，5位同學(xué)表示可視化界面效果更優(yōu)，但是其中2位同學(xué)表示多刻面中文本選擇界面跟可視化界面共存應(yīng)該效果更好。針對(duì)問題5，參與學(xué)生對(duì)以上4個(gè)問題進(jìn)行了總結(jié)，提出了聚類算法中對(duì)于主題詞的選取應(yīng)該更貼近于軟件領(lǐng)域詞匯，與語義相結(jié)合；多刻面的自動(dòng)分析與用戶選擇相結(jié)合可以更高效定位問題答案等意見。

4 結(jié) 語

本文提出了一個(gè)基于知識(shí)抽取的軟件問答網(wǎng)站搜索優(yōu)化方法，并針對(duì)Stack Overflow中的數(shù)據(jù)，設(shè)計(jì)了一個(gè)文本主題聚類和多刻面技術(shù)相結(jié)合的可視化工具。通過實(shí)驗(yàn)表明：該工具基本解決了Stack Overflow上現(xiàn)有的關(guān)鍵詞搜索機(jī)制造成的信息迷航問題，并達(dá)到了幫助用戶理解搜索結(jié)果的主題以及方向的搜索優(yōu)化目的。

[1] Barua A, Thomas W, Hassan E. What are developers talking about? an analysis of topics and trends in stack overflow[J]. Empirical Software Engineering, 2014, 19(3):619-654.

[2] Wang W, Malik H, Godfrey M W. Recommending posts concerning api issues in developer Q&A sites[C]// Proceedings of 12th Working Conference on Mining Software Repositories (MSR), 2015:224-234.

[3] Hearst M A. Clustering versus faceted categories for information exploration[J]. Communications of the Acm, 2006, 49(4):59-61.

[4] Zamir O, Etzioni O. Web document clustering: a feasibility demonstration[C]// Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval. ACM, 1998:46-54.

[5] Osiński S, Stefanowski J, Weiss D. Lingo: Search Results Clustering Algorithm Based on Singular Value Decomposition[M]// Intelligent Information Processing and Web Mining. Springer Berlin Heidelberg, 2004:359-368.

[6] Zhang Y, Lo D, Xia X, et al. Multi-factor duplicate question detection in stack overflow[J]. Journal of Computer Science and Technology, 2015, 30(5):981-997.

[7] Ye D. On domain knowledge organization and extraction in software engineering[D]. Singapore:Nanyang Technological University, 2016.

[8] Bogdanova D, Santos C N D, Barbosa L, et al. Detecting semantically equivalent questions in online user forums[C]// Proceedings of the 19th Conference on Computational Natural Language Learning(CoNLL). Beijing, China, 2015:123-131.

[9] IN-SPIRETMVisual Document Analysis[EB/OL]. 2008-06-12. http://in-spire.pnl.gov/.

[10] Jiang Q, Peng X, Yang J, et al. Searching StackOverflow questions with multi-faceted categorization[R]. 復(fù)旦大學(xué)軟件工程實(shí)驗(yàn)室技術(shù)報(bào)告，2017.

OPTIMALDESIGNONSOFTWAREQ&AWEBSITESEARCHBASEDONKNOWLEDGEEXTRACTION

Liang Renhua1,2Peng Xin1,2Zhenchang Xing3Zhao Wenyun1,2

1(SoftwareSchool,FudanUniversity,Shanghai201203,China)2(ShanghaiKeyLaboratoryofDataScience,Shanghai201203,China)3(ResearchSchoolofComputerScience,AustralianNationalUniversity,Canberra2615,Australia)

The search mechanism of software Q&A website based on keywords can’t help users find answers very well. Numerous returns result in information loss, and users are required to spend extra time filtering out the information they need. In this situation, a method of text topic clustering and multi-faceted techniques is proposed based on text information provided by stack overflow. Knowledge extraction on search results and links helped users understand the topic and direction of the search results. And a visualization model was designed to express knowledge based on force and tree layout. A dynamic interactive visualization tool based on Web was implemented, which basically achieved the goal in solving information loss and helped users to locate the answers to questions.

Knowledge extraction Text topic clustering Multi-faceted Visualization Software Q&A website

2017-03-07。國(guó)家自然科學(xué)基金項(xiàng)目(61370079)。梁仁華，碩士生，主研領(lǐng)域：軟件演化可視化，領(lǐng)域搜索。彭鑫，教授。Zhenchang Xing，高級(jí)講師。趙文耘，教授。

TP311

A

10.3969/j.issn.1000-386x.2017.12.014