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

余宏，胡曉蓉

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

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

余宏，胡曉蓉

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

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

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

0 引言

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

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

1 相關(guān)工作

1.1 XML檢索介紹

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

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

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

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

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

1.2 檢索結(jié)果聚類

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

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

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

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

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

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

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

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

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

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

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

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

2.2 相似性計算

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

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

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

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)定性。本文對以上兩類算法進行了綜合并加以改進，以克服它應(yīng)用于檢索結(jié)果聚類的不足。

算法描述：

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

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

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

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

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

4 結(jié)語

本文提出的基于標簽路徑對XML檢索結(jié)果進行聚類的方法綜合考慮了XML文檔具有語義結(jié)構(gòu)性的特點和檢索結(jié)果聚類不同于普通文檔聚類的特點，具有效率高，聚類結(jié)果可讀性強等優(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].北京：機械工業(yè)出版社，2002.

[7]余宏,萬常選.基于XML的檢索結(jié)果聚類方法研究,計算機工程,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é)果；聚類；標簽路徑

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

XML;Retrieval Results;Clustering;Tag Path