余宏，胡曉蓉

（豫章師范學院信息科學系，南昌330013）

一種基于DCFC的XML檢索結果聚類方法

余宏，胡曉蓉

（豫章師范學院信息科學系，南昌330013）

提出一種有效的XML文檔檢索結果聚類方法，基于PB-DCFC的思路，根據XML文檔的特點，對XML文檔包含的顯著標簽路徑進行聚類，是一種間接的聚類方法。該方法具有聚類效率高，聚類結果的簇標簽表達自然，容易理解。

江西省社會科學“十二五”（2015年）規(guī)劃項目（No.15TQ01）

0 引言

目前大多數的搜索引擎都存在著對用戶查詢意圖不明確，返回結果過多等問題。搜索引擎返回的內容中有相當大一部分并非查詢用戶真正想要的信息，用戶需要逐條打開返回的結果進行人工甄別以找到相關的信息。為此，如何對搜索引擎返回的查詢結果進行挖掘，幫助用戶提取相關知識是近年來的一個研究熱點。其中，對檢索結果按主題內容進行聚類挖掘，抽取聚類結果簇的語義標簽，方便用戶在與自己的查詢意圖相符的聚類結果簇中查找所需的信息，或者根據聚類反饋的結果進一步提出更準確的查詢表達式。從而達到減少用戶瀏覽無關信息的數量，縮短用戶檢索相關信息的時間。

XML已經成為Web上進行數據表示和交換的通用格式之一，其應用也越來越廣泛。與普通的扁平文檔不同，XML文檔是一種半結構化數據，具有層次性，而且能進行自描述，因此，XML文檔除了具有內容信息，還攜帶有一定的結構和語義信息。對檢索結果進行聚類挖掘能有效的改善搜索引擎的服務質量，因此，針對XML文檔檢索，本文利用XML文檔的結構和語義信息進行檢索結果的聚類分析，以提高用戶進行XML查詢的質量和效率。

1 相關工作

1.1 XML檢索介紹

XML數據模型：XML屬于典型的半結構化數據，具有層次性，而且能進行自描述，既可以用它表示關系、對象等結構化數據，也可用于半結構化及非結構化數據的描述。典型的XML文檔結構如下（文檔1）所示。

XML文檔一般建模為有序標簽樹，將XML文檔中每個元素（或屬性）抽象為一個結點，父元素與子元素之間、元素與其屬性之間的關系均用對應結點間的實線邊表示，包含文本信息的葉子結點、元素屬性與屬性值之間的關系則用虛線表示。示例文檔1對應的標簽樹如圖1所示。

圖1 示例文檔1對應的標簽樹

XML檢索查詢：傳統(tǒng)的文本檢索僅限于內容（CO）的查詢，而XML檢索不僅支持CO查詢，而且還有內容和結構查詢（CAS）查詢。一般，用Xpath表達式來表示查詢的結構約束，用about（path,string）函數表達內容約束。例如：/article/body/sec[about（.XML retrieval）]。

定義1標簽路徑（Tag Path）[7]:對XML標簽樹中的任一結點V，其標簽路徑記為從根結點到V結點所經歷的標簽有序列表。如圖1中sec結點的標簽路徑為：article.Body.sec。

1.2 檢索結果聚類

對檢索結果進行聚類挖掘的研究大多針對無結構的平面文檔，諸如對Web搜索結果進行聚類，而針對半結構化的XML數據的檢索結果進行聚類的研究還不多見。對XML檢索結果進行組織的方法大體可以分為兩類：基于文檔（document-based）的方法和基于標簽（label-based）的方法。

基于文檔（document-based）的方法，其聚類的過程如圖2（a）所示。該類方法一般使用文檔特征間的相似性來對文檔集進行聚類，文檔的特征比較多的采用關鍵詞向量表示。聚類成一個個簇后，再從每個簇中抽取有代表性的詞或句子作為簇的標簽來對簇進行描述Anton Leuski[1]和Scatter/Gather[2]就是采用該類方法。基于文檔的方法通常產生non-over-lapped簇，并且標簽質量易受聚類的準確性的影響。盡管可以用簇的數目和相似性閾值來控制聚類的過程，但還是很難選出適合于用戶閱讀和理解的標簽值。

相反，基于標簽（label-based）的方法根據對文檔成分的統(tǒng)計分析（諸如詞條的出現(xiàn)頻率），首先從檢索結果中抽取信息項（詞或短語）作為標簽，然后把含有相同信息項的文檔形成一個個簇。其過程如圖2（b）所示。我們把這種聚類過程稱為“Description Comes First Clustering”，簡稱 DCFC。Zeng et al.[3]將聚類問題看成是顯著短語排序問題。首先抽取顯著短語（作為候選簇名）并計分排序；然后，將文檔指派給相關的顯著短語以形成候選簇；最后通過對候選簇進行歸并形成最終簇。M.Lalmas et al.[4]把聚類問題看作是對搜索結果建索引，這里的索引即為標簽列表。Hiroyuki et al.[5]提出了一些標簽選擇標準。

圖2 基于文檔和基于標簽的文檔聚類過程

2 XML檢索結果的DCFC方法

檢索結果聚類與傳統(tǒng)的文檔聚類有所差別，它要求簇標簽能精確描述類別（Browsable Summaries），一個文檔可以屬性多個簇（Overlap），聚類速度要快（Speed）。基于這些要求和XML文檔自身的特點，本文提出了一種先抽取顯著路徑作為標簽后聚類的XML檢索結果聚類方法（PB_DCFC），與其他方法直接計算XML文檔間距離不同，該方法對結果包含的顯著路徑聚類。PB_DCFC方法有兩個優(yōu)點：第一，聚類結果的簇標簽表達自然，容易理解；第二，算法的復雜度是線性的。

2.1 特征抽取和建立索引模型

文本特征抽取是指為了量化表示文本信息，從文檔中抽取出特征關鍵詞，用它對原始文檔進行建模，用于描述和代替原始文本。從而將計算機對文本的識別轉化為對該文檔模型的操作和計算。目前，比較常見的是將文檔特征詞量化為向量空間模型（VSM）。

在本文提出的XML_DCFC方法中，抽取XML文檔的標簽路徑作為文檔特征。理由是：（1）XML標簽路徑包含了文檔的結構和語義信息。標簽是對嵌入其中的文本內容的概括。（2）一篇文檔中不同的標簽路徑數目比較少，相對于傳統(tǒng)的用關鍵詞作為特征，可以降低文檔特征空間的維數，從而提高聚類的效率。

本文的方法中使用標簽路徑作為結果簇的候選標簽。我們認為，有利于瀏覽聚類結果和定位想要的文檔的路徑既不能太稀少也不能太頻繁。TF-IDF是純文本搜索引擎中對索引項計算權值得基本標準。本文對TF-IDF作相應的改進，將索引項的“粒度”放大到路徑，詞頻代之以路徑相對頻率，故本文用以下標準計算文檔D中的標簽路徑TPi的權重。

在抽取文檔的特征項后，接下來要設計特定的數據結構將特征項描述的文檔模型存儲到計算機中，以保證動態(tài)數據的高效存儲及文檔之間相似度的計算。我們使用類似倒排文檔列表（Inverted Files List）模型。倒排列表結構如圖3所示。但本文采用的倒排表的索引項不是單個詞語，而是顯著標簽路徑。

圖3 倒排表結構

2.2 相似性計算

由于本文采取的是一種間接的聚類方法，即用顯著標簽路徑來代表文檔，文檔之間的相似性就轉化為計算顯著路徑之間的相似性問題。顯著路徑用詞袋模型表示，其特征由它所包含的標簽名構成。在這里要做一些預處理：去除出現(xiàn)在結果集中50%以上或少于3篇文檔中的標簽名；其次，出現(xiàn)在查詢表達式中的標簽名也必須去除，這相當于信息檢索中的停用詞處理。另外，考慮到根結點的特殊性，把根結點單獨考慮，基于這樣的考慮，有相同的根結點的文檔相似度較高。

采用以下方法度量標簽路徑（Tag Path）之間的相似度：

計算簇之間的相似性類似，簇中心用簇中各標簽路徑所含的標簽名的并集表示。

2.3 聚類算法

用于文本聚類的算法常用的有以G-AHC（Agglom?erative Hierarchical Clustering）為代表的凝聚層次法和以K-means為代表的平面劃分法。這兩類算法各有優(yōu)缺點，前類算法比較健壯，并獨立于被聚類對象的順序，但計算復雜度比較高；后類算法的優(yōu)點是計算復雜度低，但很難以求出全局最優(yōu)解[7]。此外，算法中k值及初始劃分需要事先設定，而且這些預設值對聚類結果影響較大，難以保證聚類結果質量的穩(wěn)定性。本文對以上兩類算法進行了綜合并加以改進，以克服它應用于檢索結果聚類的不足。

算法描述：

輸入：檢索結果集中抽取的顯著路徑集

輸出：M個簇，使得簇內文檔相似或相關

3 PB-DCFC的系統(tǒng)體系結構

XML檢索結果首先被掃描解析以獲取有關路徑文檔頻率和標簽文檔頻率的統(tǒng)計信息，并生成顯著路徑的倒排表。數據清洗主要是去除顯著路徑中在檢索結果集中頻繁出現(xiàn)或在檢索查詢表達式中出現(xiàn)過的標簽。接下來根據相關的統(tǒng)計信息對顯著路徑執(zhí)行聚類算法。聚類算法執(zhí)行完后，簇的內容是顯著路徑，然后根據倒排列表把與顯著路徑相關聯(lián)的文檔作為簇的內容，顯著路徑作為簇標簽的形式來呈現(xiàn)聚類結果。PBDCFC的系統(tǒng)體系結構如圖4所示。

圖4 PB_DCFC的系統(tǒng)體系結構

4 結語

本文提出的基于標簽路徑對XML檢索結果進行聚類的方法綜合考慮了XML文檔具有語義結構性的特點和檢索結果聚類不同于普通文檔聚類的特點，具有效率高，聚類結果可讀性強等優(yōu)點。

[1]Anton Leuski.Evaluating Document Clustering for Interactive Information Retrieval.

[2]M.Hearst,J.Pedersen,Reexamining the Cluster Hypothesis:Scatter/gather On Retrieval Results.Proceedings of SIGIR'96，1996：76-84.

[3]Hua-jun Zeng,Qi-Cai He,et al.Learning to Cluster Web Search Results.SIGIR'04,July 25-29,2004,Shffield,South Yorkshire UK.

[4]M.Lalmas et al.Improving Quality of Search Results Clustering with Approximate Matrix Factorisations ECIR 2006,LNCS 3936,2006：167-178.

[5]Hiroyuki Toda,Ryoji Kataoka.A Search Result Clustering Method Using Informatively Named Tntities WIDM'05,November 5,2005,Bremen,Germany.

[6]韓家煒,Kamber M.數據挖掘：概念與技術[M].北京：機械工業(yè)出版社，2002.

[7]余宏,萬常選.基于XML的檢索結果聚類方法研究,計算機工程,2010（1）：85-90.

A XML Retrieval Results Clustering Method Based on DCFC

YU Hong，HU Xiao-rong
（Department of Information Science,Nanchang Teachers'College,Nanchang 330013）

Proposes a novel approach called Path-Based,Description label Comes First Clustering(PB-DCFC)for XML retrieval results.Instead of comparing XML documents structure and clustering them directly,the salient paths contains in retrieval result documents contain docu?ments a set of similar salient paths.This clustering approach offers much high performance,and provides user readable clustering result.

余宏（1977-），男，碩士，講師，研究方向為數據挖掘、數字媒體技術

2017-03-28

2017-06-05

1007-1423（2017）17-0040-05

10.3969/j.issn.1007-1423.2017.17.008

XML；檢索結果；聚類；標簽路徑

胡曉蓉（1961-），男，江西南昌人，本科，副教授，研究方向為軟件技術

XML;Retrieval Results;Clustering;Tag Path