一種文檔的檢索方法和裝置的製作方法

2023-06-28 10:51:31

專利名稱：：一種文檔的檢索方法和裝置的製作方法
技術領域：
：本發明涉及一種檢索技術，特別是指可以應用於網頁檢索的文檔的檢索裝置及方法。
背景技術：
：隨著計算機和網絡的普及，極大的改變了人們獲取資訊的方式。但是如何從浩如煙海的全球資訊網資訊中快速獲得使用者所需的資料成為重要的研究課題。在全球資訊網上，每一個網頁都可以視為一個文檔，而全球資訊網可以認為是一個由無數個超級連結組合在一起的文檔的集合。因此對於文檔的檢索中，其中很重要的一種方式就是基於超連結關係的分析。在現有技術的超連結關係的分析技術中，廣泛應用到了隨機遊走。隨機遊走是基於隨機數學理論，形式化地表述了行進隨機步數的軌跡。例如現有的PageRank算法，其使用了隨機遊走技術通過全球資訊網中的連結分析得到了每個頁面的相對重要性程度。從直觀上講，一個網頁如果出現在其他重要頁面的超連結中，那麼這個網頁很可能也是一個重要的網頁。其他基於隨機遊走的方法也相繼提出，例如HITS。現有的隨機遊走方法僅僅使用了單一數值表示一個頁面或文檔的重要性，而沒有考慮到其所講述的內容中包含的話題信息。而異構網絡中包含了豐富的潛在話題信息。因此，如果使用傳統的隨機遊走模型對文檔重要性進行排序，那些集中討論熱門話題的文檔將更容易佔領"統治"地位。例如，一個有關產品介紹或者在線訂購的頁面可能被大量的包含該產品信息的廣告頁面指向，這將會導致搜索系統在進行排序時會將其放置在靠前的位置上。因此，理想的解決辦法就是該系統可以考慮頁面中包含的潛在話題信息，並且根據不同的話題對於頁面進行排序。對於不同話題的查詢關鍵詞，該模型根據話題層次的排序得分，系統可以返回給用戶不同話題下的排序列表。近些時期，沿著該研究思路，有一些研究工作已經展開。例如話題敏感隨機遊走試圖通過為每個頁面引入分值向量突破單一重要性得分的限制。具體來講，該方法假設每個頁面都有很多相關聯的話題，並使用偏向因子表示特定話題上的重要性。Nie等人研究了全球資訊網搜索中的話題連結分析問題，並提出了話題PageRank以及話題HITS模型。但是，在這些方法中存在著嚴重的不足所有的話題都需要預先指定，因此這些排序模型不易於擴展到新的領域中。
發明內容針對現有技術中存在的缺陷和不足，本發明的目的是提供一種文檔重要性的排序裝置及方法，以及應用上述的排序裝置和方法對網頁和文檔進行檢索的檢索裝置及方法，有效地解決現有的檢索中排序不能夠很好的適用於異構學術網絡的問題。為了達到上述目的，本發明還提出了一種文檔的檢索裝置，其特徵在於，包括話題識別模塊，所述話題識別模塊利用概率話題模型從文檔集中識別話題，並根據識別到的話題得到文檔的話題分布；5隨機遊走模塊，所述隨機遊走模塊根據話題分布對每個文檔計算隨機遊走排序得分；檢索模塊，所述檢索模塊根據查詢關鍵字計算文檔對於該查詢關鍵字的相關性得分，並根據隨機遊走排序得分與相關性得分結合得到檢索結果。其中，所述話題識別模塊包括參數計算子模塊，所述參數計算模塊根據Gibbs採樣方法計算話題z上的後驗概率分布"2+a";二+/其中d為文檔集D中的一個文檔，z為文檔d中的話題；^為文檔中的每個單詞w《對應的話題A表示文檔d中的第i個單詞，，",表示除&外的統計數值；然後根據後驗概率分布計算e和(k其中e為|d|個文檔相關的文檔-話題分布矩陣；小為ITI個話題相關的話題_單詞的分布矩陣；話題識別子模塊，所述話題識別模塊根據9和小，使用LDA話題模型從文檔集中識別話題，其中文檔集D的似然度為屍(z,wi0,①)二nrK"nn《。其中9d為文檔d在話題上的多項式分布，c^為話題z在單詞上的多項式分布；ndz是將話題z關聯到文檔d的次數，、是單詞wv由話題z生成的次數；V為互異單詞的集合.多項式分布子模塊，所述多項式分布模塊根據所述話題識別模塊識別的話題，生成文檔的話題的多項式分布{P(z|d)};其中P(zld)是文檔d生成話題Z的概率。其中，所述隨機遊走模塊包括隨機遊走排序得分計算子模塊，以根據文檔話題的多項式分布計算隨機遊走排序得分WWI+(1一"*S屍("，；1"'，Zv)W,z,]"丄屍(z,l力+(1一義)J]I"I丄乂'W其中，r[d，z]為文檔d在話題z上的排序得分；D為所有文檔的集合；T為所有話題的集合；z為文檔d中的話題；A為預設的隨機跳躍參數，即遊動者以等概率隨機跳到文檔集中的不同文檔；Y為隨機遊走者點擊一條連結訪問相同話題的文檔4的概率，(1-Y)為隨機遊走者點擊一條連結訪問不同話題的文檔4的概率；其中，P(d」dk，Zi)是從文檔dk到4在相同話題Zi上的轉移概率，表示為P(dld'，Zi);P(dyZj|dk，Zi)是從話題Zi的文檔dk到話題Zj的文檔4的轉移概率，表示為P(d，zjd'，Zj);則屍WI=rF^JP(^I《,=Ic/,)屍0,1《)iM"』q其中，所述檢索模塊包括6概率計算子模塊，所述概率計算模塊計算由話題模型生成查詢關鍵詞q的概率PLDA(q|d)，屍皿",=n屍i《=niz'&i"a)we《其中ed為特定文檔d在話題上的多項式分布；(^為特定的話題z在單詞上的多項式分布；並採用語言模型計算查詢關鍵詞q從文檔d中生成概率P^(qld);查詢關鍵詞q與文檔相關性得分P(q|d)=PLM(q|d)XPLDA(q|d);步驟34、將步驟2所得話題層次隨機遊走的排序得分r[d，z]和相關性得分P(q|d)相結合得到檢索結果。其中，所述裝置還包括關鍵字擴展模塊，所述關鍵字擴展模塊對查詢關鍵字進行擴展，並對擴展的查詢關鍵詞q中的每個單詞％,，根據以下公式的概率採樣話題z:一i、《+屍k.l-+)2>:;+<v+a.其中nqz是查詢關鍵詞q按照多項式分布採樣話題z的次數；aq是查詢關鍵詞q的相關多項式LDA先驗；nd表示在步驟l全部文檔數目，a和13分別為多項式分布9和小的Dirichlet先驗。同時，本發明還提出了一種文檔的檢索方法，包括步驟1、使用概率話題模型從文檔集中識別話題，並根據識別到的話題得到文檔的話題分布；步驟2、利用話題分布對每個文檔計算其話題層次的隨機遊走排序得分；步驟3、根據查詢關鍵詞及話題，計算文檔相對於該查詢關鍵詞的相關性得分，將話題層次隨機遊走的排序重要性得分和相關性得分相結合得到檢索結果。其中，所述步驟1具體為步驟11、根據Gibbs採樣方法計算話題Z上的後驗概率分布,'za__其中d為文檔集D中的一個文檔，Z為文檔d中的話題；、為文檔中的每個單詞W",對應的話題A表示文檔d中的第i個單詞，，",表示除&外的統計數值；步驟12、根據後驗概率分布計算e和cK其中e為|d|個文檔相關的文檔-話題分布矩陣；小為|T|個話題相關的話題-單詞的分布矩陣；步驟13、使用LDA話題模型從文檔集中識別話題，其中文檔集D的似然度為，，W|0，o)=nncne其中9d為文檔d在話題上的多項式分布，(K為話題z在單詞上的多項式分布；7ndz是將話題z關聯到文檔d的次數，、是單詞wv由話題z生成的次數；V為互異單詞的集合.步驟14、計算文檔的話題的多項式分布{p(z|d)};其中P(zld)是文檔d生成話題z的概率。其中，所述步驟2具體為採用以下公式獲得話題Z的隨機遊走排序得分4"]=/1^7屍(;|00+(1-/1)J]^W,;)+(1-"去Z屍"Z,I""》其中，r[d，z]為文檔d在話題z上的排序得分；D為所有文檔的集合；T為所有話題的集合；z為文檔d中的話題；A為預設的隨機跳躍參數，即遊動者以等概率隨機跳到文檔集中的不同文檔；Y為隨機遊走者點擊一條連結訪問相同話題的文檔4的概率，(1-Y)為隨機遊走者點擊一條連結訪問不同話題的文檔4的概率；其中，P(dld'，Zi)是從文檔dk到c^在相同話題Zi上的轉移概率，表示為P(d」dk，Zi);P(d，Zi，|d'Zj)是從話題Zi的文檔dk到話題Zj的文檔4的轉移概率，表示為P(dpZj|dk，Zi);則屍WI")=r^7^P("''Z'1《，2')=屍(~1"')P(Z'1《)其中，所述步驟3具體為步驟31、計算由話題模型生成查詢關鍵詞q的概率P皿(qld);屍磁(《i=n屍oi",《w=nspoi&&)屍oi"，&)we《we《，步驟32、採用語言模型計算查詢關鍵詞q從文檔d中生成概率PM(q|d);步驟33、關鍵詞q與文檔相關性得分P(qld)=P^(qld)XP皿(qld);步驟34、將步驟2所得話題層次隨機遊走的排序得分r[d，z]和相關性得分P(q|d)相結合得到檢索結果。其中，所述步驟2和步驟3之間還包括步驟a、對查詢關鍵詞進行擴展，並對擴展的查詢關鍵詞q中的每個單詞wqi，根據以下公式的概率採樣話題z:w'm《+(、1、,W)-》《,+)》《+《+/).其中nqz是查詢關鍵詞q按照多項式分布採樣話題z的次數；aq是查詢關鍵詞q的相關多項式LDA先驗；nd表示在步驟1全部文檔數目。上述技術方案具有如下優點本發明提出了一種文檔檢索裝置及方法，能夠使用統計話題模型自動從文檔集中抽取話題，並根據話題層次隨機遊走，基於抽取的話題將每個文檔的話題相關重要性進行打分，並給定查詢關鍵詞。然後根據發現的話題，計算文檔相對於該查詢關鍵詞的相關性得分，並根據話題層次隨機遊走的排序重要性得分和相關性得分相結合得到檢索結果。因此本發明相比較現有技術能夠自動抽取話題，並使能夠根據話8題隨機遊走得分與相關性得分結合得到更好的檢索結果。圖1是本發明優選實施例流程示意圖；圖2是異構網絡具體實例的結構示意圖；圖3是調整參數Y後搜索結果的變化示意圖；圖4是搜索論文的結果和搜索專家的結果示意圖；圖5是調整參數t後搜索結果的變化示意圖。具體實施例方式下面結合附圖和實施例，對本發明的具體實施方式作進一步詳細描述。以下實施例用於說明本發明，但不用來限制本發明的範圍。全球資訊網中的網頁或其他存在關聯的實體網絡可以用含有連結的文檔的集合表示，即G=(D，E)，其中D表示所有文檔的集合，E表示所有超級連結的結合，有向邊—d2GE表示文檔4有指向d2的超級連結。實施例1本發明提出的文檔重要性的排序方法，其優選實施例包括步驟一話題建模步驟一的目的是使用概率話題模型從文檔集中發現話題。概率話題模型可以有效地在文檔集中挖掘話題。在這些方法中，通常假設文檔是從|T|個概率模型的混合中生成。潛在Dirichlet分配(LDA)是一種廣泛使用的話題模型。在該模型中，文檔集D的似然度定義為，,wi,=nnexnne其中，ndz是將話題z關聯到文檔d的次數，nzv是單詞wv由話題z生成的次數。直觀上講，該方法假設在文檔集D中共討論了|T|個不同的話題。每個文檔有P(zld)的概率討論話題z。而有最大概率的那個話題在一定程度上揭示了文檔d的語義內容。根據話題模型，每個文檔根據如下隨機過程生成首先文檔(如網頁等)的作者會根據文檔的話題分布P(zld)決定撰寫的話題z，之後根據該話題上單詞的分布P(wlz)從話題z上採樣得到單詞。在話題模型中，推理的目的是為了估計LDA模型中的未知參數(l)|D|個文檔相關的文檔-話題分布矩陣9和|T|個話題相關的話題-單詞分布矩陣小；(2)文檔d中的每個單詞w《對應的話題、。該方法使用Gibbs採樣方法估計參數。具體來講，該方法不直接估計模型的參數，相反僅僅估計z上的後驗概率分布，再用z推理e和小。後驗分布定義為w，a'一.,.嚴zv(2)9其中，/7、的上標^/,表示除當前實例(文檔d中的第i個單詞)的統計數值。步驟二話題層次隨機遊走在文檔集上使用話題模型後，該方法得到了每個文檔的話題分布。形式化講，對於每個文檔，使用{P(z|d)}(等價的寫為edz)表示話題的多項式分布。之後定義話題層次的隨機遊走。對於每個文檔d，在該方法中關聯著一個排序得分向量{r[d，z]L，其中每一個元素對應一個話題z。隨機遊走既在同一個話題的範疇內，同時也跨越不同的話題，沿著文檔之間的超級連結進行。對於包含指向文檔的超級連結的文檔dk，該方法定義兩種類型的文檔間轉移概率話題內轉移概率和話題間轉移概率，即formulaseeoriginaldocumentpage10(3)其中，P(djdk，Zi)是從文檔dk到在相同話題Zi上的轉移概率；P(dyZj|dk，Zi)是從話題Zi的文檔dk到話題Zj的文檔的轉移概率。接下來在該方法中引入參數Y表示對於話題內轉移或者話題間轉移的偏好。因此該轉移圖如下形式化地描述了一個隨機遊走者的行為隨機遊走者有Y的概率點擊某一條連結訪問相同話題的文檔4，並且有(1-Y)的概率點擊某一條連接訪問不同話題的文檔V和PageRank類似，為每個文檔d定義隨機遊走排序得分的公式formulaseeoriginaldocumentpage10其中，P(zId)是文檔d生成話題z的概率；和PageRank類似，可以定義隨機跳躍參數A，它允許遊動者以等概率隨機跳到文檔集中的不同文檔。步驟三查詢關鍵詞建模步驟三是為了找到和查詢關鍵詞相關的文檔。儘管這一步並不是必須的，但是該步驟有助於發現查詢關鍵詞的語義信息。由於查詢關鍵詞的長度通常較短，可見為查詢關鍵詞建模並不容易。為了確保能夠找到正確的話題描述用戶的查詢意圖，該方法中使用信息檢索中通常使用的方法，即進行查詢關鍵詞擴展。具體來講，對於查詢關鍵詞q中的每一個單詞w，該方法從文檔集中抽取若干高頻共現詞，並將它們添加到查詢關鍵詞中。考慮單詞w的窗口大小鄰域中出現的單詞作為共現詞，也就是說w前後的單詞。該應用中設置窗口大小為1。之後，該方法在擴展的查詢關鍵詞上應用話題模型找到查詢關鍵詞相關的話題。對於擴展查詢關鍵詞q中的每個單詞,,，最後根據如下的概率採樣話題z:formulaseeoriginaldocumentpage10(5)其中，r^是查詢關鍵詞q按照多項式分布採樣話題z的次數；aq是查詢關鍵詞相關多項式的Dirichlet先驗；有上標d的nd表示在步驟一的推理過程之後統計的全部文檔數目。例如，nj表示在所有文檔中單詞w被分配到話題z中的次數。特別重要的是，該方法為查詢關鍵詞q額外進行一次生成過程。該生成過程和步驟一中的類似，只是為了查詢關鍵詞建模，該方法結合了文檔建模的結果。具體的講，該方法從Dirichlet先驗aq中為每一個查詢關鍵詞q採樣得到一個多項式分布；之後，對於每一個查詢關鍵詞中的單詞％.，從多項分布中採樣得到話題、。生成過程依賴於查詢關鍵詞和文檔的相關性。該過程後，該方法得到查詢關鍵詞-對應話題的分布(P(zlqM，它包含了查詢詞的語義信息。步驟四用話題層次隨機遊走進行搜索在最後一步中，該方法使用話題層次隨機遊走進行搜索。具體來講，對於每一個文檔d，該方法結合查詢關鍵詞q和文檔的相關性得分以及在話題層次隨機遊走中得到的文檔d的重要性排序得分。相似性得分根據如下公式計算formulaseeoriginaldocumentpage11但是，由於根據話題模型學到的話題通常是通用的，並不針對某個具體的查詢關鍵詞，因此在搜索中僅僅使用話題模型會造成結果過於粗糙。之前進行的實驗中也證實了在信息檢索中僅僅使用話題模型會降低檢索性能。因此，為了在通用和具體中間找到平衡，該方法得到LDA模型和基於單詞的語言模型的組合形式。P(q|d)=PLM(q|d)XPLDA(q|d)(7)其中，P"qld)是根據語言模型，計算查詢關鍵詞q從文檔d中生成概率。而P皿(qld)是由話題模型生成查詢關鍵詞的概率。該方法首先考慮兩種將相關性得分和隨機遊走重要性排序得分相結合的方法，即formulaseeoriginaldocumentpage11其中，P(zld)表示文檔d生成話題z的概率，r[d，z]表示文檔d在話題z上的重要性得分。上述方法對於所有話題上的查詢關鍵詞的生成概率進行求和。同樣可以考慮使用查詢關鍵詞建模的結果。組合得分如下定義STPRq)=LM(《I")'$^，z].屍(z|《)(其中，在採樣過程中，^為查詢關鍵詞q中的單詞w所選擇的話題。實施例2本發明提出的文檔的檢索裝置，其優選實施例包括話題識別模塊，所述話題識別模塊利用概率話題模型從文檔集中識別話題，並根據識別到的話題得到文檔的話題分布；隨機遊走模塊，所述隨機遊走模塊根據話題分布對每個文檔計算隨機遊走排序得分；檢索模塊，所述檢索模塊根據查詢關鍵字計算文檔對於該查詢關鍵字的相關性得分，並根據隨機遊走排序得分與相關性得分結合得到檢索結果。其中，所述話題識別模塊包括參數計算子模塊，所述參數計算模塊根據Gibbs採樣方法計算話題z上的後驗概率分布《t+/其中d為文檔集D中的一個文檔，z為文檔d中的話題；為文檔中的每個單詞w《對應的話題A表示文檔d中的第i個單詞，"^,表示除&外的統計數值；然後根據後驗概率分布計算9和(K其中e為|D|個文檔相關的文檔-話題分布矩陣；小為ITI個話題相關的話題_單詞的分布矩陣；話題識別子模塊，所述話題識別模塊根據9和小，使用LDA話題模型從文檔集中識別話題，其中文檔集D的似然度為闊屍(z,wi0，。)nn^xnne其中9d為文檔d在話題上的多項式分布，c^為話題z在單詞上的多項式分布；ndz是將話題Z關聯到文檔d的次數，、是單詞Wv由話題Z生成的次數；V為互異單詞的集合.多項式分布子模塊，所述多項式分布模塊根據所述話題識別模塊識別的話題，生成文檔的話題的多項式分布{P(z|d)};其中P(zld)是文檔d生成話題Z的概率。其中，所述隨機遊走模塊包括隨機遊走排序得分計算子模塊，以根據文檔話題的多項式分布計算隨機遊走排序得分4^，z,]=;ilpo;義)ZWWw",)+(l—"+J]/v，z,i《~)其中，r[d，z]為文檔d在話題z上的排序得分；D為所有文檔的集合；T為所有話題的集合；z為文檔d中的話題；A為預設的隨機跳躍參數，即遊動者以等概率隨機跳到文檔集中的不同文檔；Y為隨機遊走者點擊一條連結訪問相同話題的文檔4的概率，(1-Y)為隨機遊走者點擊一條連結訪問不同話題的文檔4的概率；其中，P(dld'，zi)是從文檔dk到c^在相同話題Zi上的轉移概率，表示為P(d」dk，Zi);P(d，Zi|d'，Zj)是從話題Zi的文檔檔dk到話題Zj的文檔C^的轉移概率，表示為P(dyZj|dk，Zi);則P(《I《'z,)=[T^7j屍(化1《,Z')=1I《)其中，所述檢索模塊包括概率計算子模塊，所述概率計算模塊計算由話題模型生成查詢關鍵詞q的概率PLDA(q|d)，formulaseeoriginaldocumentpage13並採用語言模型計算查詢關鍵詞q從文檔d中生成概率PM(q|d);關鍵詞q與文檔相關性得分P(qld)=PLM(q|d)XPLDA(q|d);步驟34、將步驟2所得話題層次隨機遊走的排序得分r[d，z]和相關性得分P(q|d)相結合得到檢索結果。其中，所述檢索裝置還包括關鍵字擴展模塊，所述關鍵字擴展模塊對查詢關鍵字進行擴展，並對擴展的查詢關鍵詞q中的每個單詞％,,根據以下公式的概率採樣話題z:其中nqz是查詢關鍵詞q按照多項式分布採樣話題z的次數；aq是查詢關鍵詞q的相關多項式LDA先驗；nd表示在步驟1全部文檔數目。下面應用一個具體事例對本發明進行進一步說明。(1)實驗集本發明可以用於異構網絡中多種類型結點的搜索。在實驗評估環節，我們重點在學術網絡中進行分析研究。學術網絡中中包含多種類型的結點，例如論文、期刊會議、作者等，如圖2所示。在圖中，相同類型的結點之間存在著若干的關聯，例如論文之間有向的引用關係，作者之間有無向的合作關係。不同類型的結點之間也存在著某些關係，如作者會發表論文，論文會發表在期刊會議中等等。這些結點和邊組成了異構學術網絡。我們在學術研究者社會網絡搜索系統ArnetMiner的環境中進行評估。200個示例話題及其有代表性的研究者，論文可以參見示例話題頁面(http:〃arnetminer.org/topicBrowser.do)。每篇論文用標題表示其文檔內容，對於作者(專家)，用他的全部論文的標題串表示，當然也可以使用論文的摘要或者全文表示論文的文檔內容。我們在ArnetMiner的一個子數據集(包含14，134個作者以及10，716篇論文)上進行實驗。由於目前並沒有一個標準答案的數據集，我們從ArnetMiner的日誌中選擇並列出了若干最頻繁的查詢詞。處於評估的考慮，我們使用合併相關評估方法並結合人為判斷。具體來講，對於每個查詢關鍵詞，我們首先從三個相似的系統Libra(http:〃libra.msra.cn/)、Rexa(http://rexa.info/)以及ArnetMiner(http://www.arnetminer.org)的前30個查詢結果中合併結果。然後，兩個計算機專業的教師和五個研究生對結果進行人工標註。四個評價等級(3、2、1以及0)分別用來表示絕對權威、權威、臨界權威以及不權威。我們通過該方法分別進行論文搜索和專家搜索，並在測試集上對於這兩類應用的性能進行評測。[OH7](2)評估方法在這些實驗中，我們使用P@5、P@10、P@20、R_pre和均值平均查準率(MAP)進行評估。其中Ptk表示系統對於查詢關鍵詞返回的前k個結果的查準率，定義為。。，前^個結果中相關文檔的數目A:R-pre表示檢索出R篇文檔時的準確率，其中R是在標準答案集中與查詢關鍵詞相關的文檔的數目。MAP表示每個查詢關鍵詞對應的準確率的平均值。具體來說，對於一個給定的查詢關鍵詞，根據前k個結果的查準率，首先計算平均查準率M=.4是相關的_相關文檔數目而MAP是在全部數據集上AP的平均值。(3)基線方法我們使用基於單詞的語言模型(LM)、BM25、LDA、PageRank(PR)作為基線方法。在基於單詞的語言模型中，我們計算查詢關鍵詞短語和論文或者專家之間的相關性。在BM25中，我們計算查詢關鍵詞和論文或者專家的相似度，記為SBM25(d，q)。對於PageRankSpJd)，我們使用Page介紹的方法計算論文或者專家的重要性。對於話題PageRankS，，我們使用Nie描述的方法。同時考慮上述基線方法的若干組合形式，包括LM+LDA、LM*LDA、LM*PR、LM+PR、LM*LDA*PR以及BM25*PR。SLM+LDA(d，q)=(1-t)PLM(dIq)+tPLDA(d|q)SLM*LDA(d，q)=PLM(dIq)PLDA(d|q)S,(d，q)=PLM(dIq)PR(d)(11)S,(d，q)=(l-t)PLM(d|q)+tPR(d)SLM*LDiWK(d，q)=PLM(d|q)PLDA(d|q)PR(d)SBM25*PK(d，q)=SBM25(d，q)PR(d)(4)實驗結果實驗中的參數如下設置對於LDA模型，設置超參數a=0.1以及|3=0.l，話題的數目設置為不同的值(分別為5、15以及80)。在話題層次隨機遊走中，設置隨機跳轉因子A=0.15，而將因子y設置為以0.1為間隔從0取到1.0。公式11中LM和LDA的組合權重t分別在0、0.1、0.2、0.4、0.6、0.8和1.0取值上進行試驗，調整這些參數，並報告最佳性能。表格1和表格2展示了使用發明的方法(TPR+、TPR*和TPRq)與基線方法的實驗結果比較。從中可見該方法在大部分的評價指標中勝過基線方法。使用TPR+方法獲得了最佳的性能。表l搜索論文的結果14tableseeoriginaldocumentpage15tableseeoriginaldocumentpage16(5)參數調整(A)調整參數Y圖3(a)通過MAP展示了使用TPR+和TPR*進行論文搜索的性能，其中將Y取O到1.0之間的某個固定值(選取間隔為O.l)，記為constantY，在圖中用坐標點表示。同時還將Y設為隨話題和文檔變化的動態的值P(zld')，並記為variableY，在圖中用一條虛線表示。對於搜索專家，如見圖3(b)所示，使用同樣的參數值設置調節該參數。可以看出對於不同的Y設置，搜索專家更為穩定，即對於Y的變化影響較小。(B)調整參數lT對於參數話題個數lTl，調整|T|分別為5、15和80。搜索論文的結果在圖4(a)中展示，搜索專家的結果在圖4(b)中展示。在論文搜索，當把|T|設置為15時，使用大部分方法都能得到最佳的結果。在專家搜索中，當把話題數目設置為5時，得到最佳的結果。這或許是因為相比於確定一篇論文的話題，更難準確判斷一個專家所感興趣的領域。(C)調整參數t如圖5所示，調整參數t從0變化到l.O，間隔為O.2。可以看出當t在O.2和0.8之間變化時結果較為穩定。(6)實例分析為了進一步表明研究話題層次隨機遊走的動機，我們進行一個具體的案例研究。我們選擇兩個查詢關鍵詞分析他們的語義，查詢關鍵詞為"naturallanguageprocessing"(自然語言處理)和"intelligentagents"(智能代理)。對於這兩個查詢關鍵詞中的每一個單詞，我們為其挑選最有代表性的若干話題，也就是說我們從15個話題中刪除那些和這些單詞關聯性均較弱的話題(通常他們之間的生成概率僅僅是模型中的平滑係數)。我們得到單詞在話題#4、#7、#10、#13上的分布，如表3所示。從中可見，查詢關鍵詞"natu:rallanguageprocessing，，主要對應於話題#10，而"intelligentagents，，主要對應話題#4和#7。表4展現了分別通過PageRank和話題層次隨機遊走(TPR+)計算得到的重要性得分。當使用TPR+用查詢關鍵詞"naturallanguageprocessing"搜索論文時，第一個文檔VerifiableSemanticsforAgentCommunicationLanguages(代理通訊語言中驗證語義)並沒有被檢索得到，這主要是因為該文檔在話題#10上的重要性得分較低，而第二個文檔ProbabilisticParsingUsingLeftCornerLangimgeModels(用左角落語言模型進行概率句法分析)被TPR+檢索出。但是，當使用PagePank用"naturallanguag印rocessing"搜索論文時，第一個文檔由於其較高的PageRank得分被檢索得到，而第二個文檔沒有被檢索到。上述過論在一定程度上說明了我們的方法的合理性。當我們用查詢關鍵詞"intelligentagents"搜索論文時，第四個文檔Agent-BasedBusinessProcessManagement(基於代理的商務流程管理)可以被我們的TPR+方法成功檢索出來，但是PageRank並不能做到，而相反PageRank選擇了沒有被TPR+檢索出的第三個文檔TheGRAILconceptmodelinglanguageformedicalterminology(醫學術語的GRAIL概念建模語言)，這主要是由於該文檔被大量的論文引用。表3查詢關鍵詞中單詞的概率分布單詞話題#4話題#7話題#10話題#13natural0.0000180.0000180.0189660.000022l肌gimge0.0000180.0029460.0433220.000022processing0.0000180.0000180.0126520.000022intelligent0.0023630.0221580.0000230.000022agents0.0375410.0347840.0000230.000022表4用TPR+和PageRank搜索四篇文檔的重要性得分論文TPR+話題#4話題#7話題#10話題#13VerifiableSemanticsforAgentCommunicationLanguages0細H30細0260細0070扁0050.000612ProbabilisticParsingUsingLeftComerLanguageModels0.0000020.0000020.0000550.0000140細306TheGRAILconceptmodelinglanguageformedicalterminology0.0000620.0000520,0000500,0000370.003042Agent-BasedBusinessProcessManagement0.0002360.0001790.0000270細0290.00227917從實驗結果可以看出，發明的方法在兩個不同任務上的測試結果都優於基線方法。實驗表明，我們提出的話題層次隨機遊走是切實有效的。以上所述僅是本發明的優選實施方式，應當指出，對於本
技術領域：
的普通技術人員來說，在不脫離本發明技術原理的前提下，還可以做出若干改進和變型，這些改進和變型也應視為本發明的保護範圍。權利要求一種文檔的檢索裝置，其特徵在於，包括話題識別模塊，所述話題識別模塊利用概率話題模型從文檔集中識別話題，並根據識別到的話題得到文檔的話題分布；隨機遊走模塊，所述隨機遊走模塊根據話題分布對每個文檔計算隨機遊走排序得分；檢索模塊，所述檢索模塊根據查詢關鍵字計算文檔對於該查詢關鍵字的相關性得分，並根據隨機遊走排序得分與相關性得分結合得到檢索結果。2.根據權利要求1所述的文檔的檢索裝置，其特徵在於，所述話題識別模塊包括參數計算子模塊，所述參數計算模塊根據Gibbs採樣方法計算話題Z上的後驗概率分布其中d為文檔集D中的一個文檔，z為文檔d中的話題；&為文檔中的每個單詞W《對應的話題A表示文檔d中的第i個單詞，，",表示除&外的統計數值；然後根據後驗概率分布計算9和小，其中9為|D|個文檔相關的文檔-話題分布矩陣；小為ITI個話題相關的話題_單詞的分布矩陣；話題識別子模塊，所述話題識別模塊根據9和小，使用LDA話題模型從文檔集中識別話題，其中文檔集D的似然度為屍(z,wi，。)=nnexnne其中9d為文檔d在話題上的多項式分布，小z為話題Z在單詞上的多項式分布；ndz是將話題Z關聯到文檔d的次數，nzv是單詞Wv由話題Z生成的次數；V為互異單詞的集合；多項式分布子模塊，所述多項式分布模塊根據所述話題識別模塊識別的話題，生成文檔的話題的多項式分布{P(z|d)};其中P(zld)是文檔d生成話題Z的概率。3.根據權利要求1所述的文檔的檢索裝置，其特徵在於，所述隨機遊走模塊包括隨機遊走排序得分計算子模塊，以根據文檔話題的多項式分布計算隨機遊走排序得分4A]4丄P(z,l力+(l-A)J]"(W，Z;)+(1—"去Z屍W,W，z》其中，r[d，z]為文檔d在話題z上的排序得分；D為所有文檔的集合；T為所有話題的集合；Z為文檔d中的話題；A為預設的隨機跳躍參數，即遊動者以等概率隨機跳到文檔集中的不同文檔；Y為隨機遊走者點擊一條連結訪問相同話題的文檔4的概率，(1-Y)為隨機遊走者點擊一條連結訪問不同話題的文檔4的概率；其中，P(d」dk，Zi)是從文檔dk到4在相同話題Zi上的轉移概率，表示為P(dld'，Zi);P(dpZjIdk，Zi)是從話題Zi的文檔dk到話題Zj的文檔的轉移概率，表示為P(d，ZiId'，Zj);則屍W=777^/)(化I=P(Z/1《)P(z,I《)4.根據權利要求1所述的文檔的檢索裝置，其特徵在於，所述檢索模塊包括概率計算子模塊，所述概率計算模塊計算由話題模型生成查詢關鍵詞q的概率formulaseeoriginaldocumentpage3其中ed為特定文檔d在話題上的多項式分布；小z為特定的話題z在單詞上的多項式分布；並採用語言模型計算查詢關鍵詞q從文檔d中生成概率P^(qld);查詢關鍵詞q與文檔相關性得分formulaseeoriginaldocumentpage3步驟34、將步驟2所得話題層次隨機遊走的排序得分r[d，z]和相關性得分P(qld)相結合得到檢索結果。5.根據權利要求1所述的文檔的檢索裝置，其特徵在於，還包括關鍵字擴展模塊，所述關鍵字擴展模塊對查詢關鍵字進行擴展，並對擴展的查詢關鍵詞q中的每個單詞^.，根據以下公式的概率採樣話題z:formulaseeoriginaldocumentpage3其中nqz是查詢關鍵詞q按照多項式分布採樣話題z的次數；aq是查詢關鍵詞q的相關多項式LDA先驗；nd表示在步驟l全部文檔數目，a和13分別為多項式分布9和小的Dirichlet先驗。6.—種文檔的檢索方法，包括步驟1、使用概率話題模型從文檔集中識別話題，並根據識別到的話題得到文檔的話題分布；步驟2、利用話題分布對每個文檔計算其話題層次的隨機遊走排序得分；步驟3、根據查詢關鍵詞及話題，計算文檔相對於該查詢關鍵詞的相關性得分，將話題層次隨機遊走的排序重要性得分和相關性得分相結合得到檢索結果。7.根據權利要求6所述的文檔的檢索方法，其特徵在於，所述步驟1具體為步驟11、根據Gibbs採樣方法計算話題z上的後驗概率分布其中d為文檔集D中的一個文檔，z為文檔d中的話題；^為文檔中的每個單詞w《對應的話題；di表示文檔d中的第i個單詞，，《表示除&外的統計數值；步驟12、根據後驗概率分布計算e和(K其中9為|D|個文檔相關的文檔-話題分布矩陣；小為|T|個話題相關的話題-單詞的分布矩陣；步驟13、使用LDA話題模型從文檔集中識別話題，其中文檔集D的似然度為formulaseeoriginaldocumentpage3其中9d為文檔d在話題上的多項式分布，小z為話題z在單詞上的多項式分布；ndz是將話題Z關聯到文檔d的次數，nzv是單詞Wv由話題Z生成的次數；V為互異單詞的集合；步驟14、計算文檔的話題的多項式分布{p(Z|d)};其中P(zld)是文檔d生成話題Z的概率。8.根據權利要求6所述的文檔的檢索方法，其特徵在於，所述步驟2具體為採用以下公式獲得話題Z的隨機遊走排序得分,Kz,]"丄戶(z,i力+(i-義);^w《z,)+(i—"*2;iv，si《~)其中，r[d，z]為文檔d在話題z上的排序得分；D為所有文檔的集合；T為所有話題的集合；Z為文檔d中的話題；A為預設的隨機跳躍參數，即遊動者以等概率隨機跳到文檔集中的不同文檔；Y為隨機遊走者點擊一條連結訪問相同話題的文檔4的概率，(1-Y)為隨機遊走者點擊一條連結訪問不同話題的文檔4的概率；其中，P(dld'，Zi)是從文檔dk到C^在相同話題Zi上的轉移概率，表示為P(d」dk，Zi);P(d，ZiId'，Zj)是從話題Zi的文檔dk到話題Zj的文檔的轉移概率，表示為P(dpZjIdk，Zi);則p(《1《，z》=1《，z')=屍(z'1《)屍(z'1《)9.根據權利要求6所述的文檔的檢索方法，其特徵在於，所述步驟3具體為步驟31、計算由話題模型生成查詢關鍵詞q的概率P皿(qld);;a(《iri屍oi=nzp(wiz,ai"，&)w叫wegzer步驟32、採用語言模型計算查詢關鍵詞q從文檔d中生成概率P^(qId);步驟33、關鍵詞q與文檔相關性得分P(qld)=PLM(q|d)XPLDA(q|d);步驟34、將步驟2所得話題層次隨機遊走的排序得分r[d，z]和相關性得分P(qld)相結合得到檢索結果。10.根據權利要求6所述的文檔的檢索方法，其特徵在於，所述步驟2和步驟3之間還包括步驟a、對查詢關鍵詞進行擴展，並對擴展的查詢關鍵詞q中的每個單詞,,，根據以下/入二W式的概率採樣話題Z:formulaseeoriginaldocumentpage4其中nqz是查詢關鍵詞q按照多項式分布採樣話題z的次數；aq是查詢關鍵詞q的相關多項式LDA先驗；nd表示在步驟1全部文檔數目。全文摘要本發明公開了一種文檔的檢索裝置和方法，針對現有話題模型無法自動識別話題的問題而發明。本發明的裝置包括話題識別模塊、隨機遊走模塊、檢索模塊。方法包括使用概率話題模型從文檔集中識別話題，並根據識別到的話題得到文檔的話題分布；對每個文檔計算其話題層次的隨機遊走排序得分；根據查詢關鍵詞及話題，計算文檔相對於該查詢關鍵詞的相關性得分，將話題層次隨機遊走的排序重要性得分和相關性得分相結合得到檢索結果。文檔編號G06F17/30GK101706812SQ200910238289公開日2010年5月12日申請日期2009年11月24日優先權日2009年11月24日發明者唐傑,楊子申請人:清華大學