余宏，胡曉蓉

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

一種基于DCFC的XML檢索結(jié)果聚類方法

余宏，胡曉蓉

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

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

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

0 引言

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

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

1 相關(guān)工作

1.1 XML檢索介紹

XML數(shù)據(jù)模型：XML屬于典型的半結(jié)構(gòu)化數(shù)據(jù)，具有層次性，而且能進(jìn)行自描述，既可以用它表示關(guān)系、對象等結(jié)構(gòu)化數(shù)據(jù)，也可用于半結(jié)構(gòu)化及非結(jié)構(gòu)化數(shù)據(jù)的描述。典型的XML文檔結(jié)構(gòu)如下（文檔1）所示。

XML文檔一般建模為有序標(biāo)簽樹，將XML文檔中每個元素（或?qū)傩裕┏橄鬄橐粋€結(jié)點，父元素與子元素之間、元素與其屬性之間的關(guān)系均用對應(yīng)結(jié)點間的實線邊表示，包含文本信息的葉子結(jié)點、元素屬性與屬性值之間的關(guān)系則用虛線表示。示例文檔1對應(yīng)的標(biāo)簽樹如圖1所示。

圖1 示例文檔1對應(yīng)的標(biāo)簽樹

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

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

1.2 檢索結(jié)果聚類

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

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

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

圖2 基于文檔和基于標(biāo)簽的文檔聚類過程

2 XML檢索結(jié)果的DCFC方法

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

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

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

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

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

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

圖3 倒排表結(jié)構(gòu)

2.2 相似性計算

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

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

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

2.3 聚類算法

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

算法描述：

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

輸出：M個簇，使得簇內(nèi)文檔相似或相關(guān)

3 PB-DCFC的系統(tǒng)體系結(jié)構(gòu)

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

圖4 PB_DCFC的系統(tǒng)體系結(jié)構(gòu)

4 結(jié)語

本文提出的基于標(biāo)簽路徑對XML檢索結(jié)果進(jìn)行聚類的方法綜合考慮了XML文檔具有語義結(jié)構(gòu)性的特點和檢索結(jié)果聚類不同于普通文檔聚類的特點，具有效率高，聚類結(jié)果可讀性強(qiáng)等優(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.數(shù)據(jù)挖掘：概念與技術(shù)[M].北京：機(jī)械工業(yè)出版社，2002.

[7]余宏,萬常選.基于XML的檢索結(jié)果聚類方法研究,計算機(jī)工程,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-），男，碩士，講師，研究方向為數(shù)據(jù)挖掘、數(shù)字媒體技術(shù)

2017-03-28

2017-06-05

1007-1423（2017）17-0040-05

10.3969/j.issn.1007-1423.2017.17.008

XML；檢索結(jié)果；聚類；標(biāo)簽路徑

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

XML;Retrieval Results;Clustering;Tag Path