摘  要： 提出了一種基于Dirichlet過程的Deep Web數據源聚類方法,，該方法采用層次Dirichlet過程（HDP）進行特征提取,。首先將查詢接口中原本高維稀疏的文本表示為主題特征，該過程能自動確定特征數,。然后將文本看成多項式模型,，采用Dirichlet過程混合模型聚類。該模型無需人工事先指定聚類個數,，由Dirichlet過程根據數據自動計算得到,，特別適用于Deep Web數據源數量大、變化快的特點,。在通用數據集TEL-8上進行驗證實驗,，并與其他聚類方法在F-measure和熵值兩個指標上進行對比，均取得較好的結果,。

　　關鍵詞： Deep Web,；數據集成；特征提??；dirichlet過程；混合模型

0 引言

　　萬維網中不能被傳統(tǒng)搜索引擎通過靜態(tài)鏈接索引到的內容稱為Deep Web。要獲取這部分內容只能通過表單提交查詢的方式獲得[1-2],。Deep Web數據源的分類是指把所有發(fā)現的數據源按照領域進行劃分,，是Deep Web數據源集成的關鍵步驟之一[3]。目前Deep Web數據源分類,，多數研究采用的是有監(jiān)督的分類方法,。而一個標注好的數據集，需要大量的人工知識,，并且隨著萬維網的快速發(fā)展,，訓練集要考慮更新與擴展。這些對于自動化的數據集成都是很大的阻礙,。在最新的Deep Web研究進展與綜述中[4],，也明確指出結合機器學習，數據挖掘等領域的無監(jiān)督的研究方法是今后的研究重點,。

　　目前也有一部分研究人員關注聚類方法的研究,。B.He[5]提出了MDhac方法，將表單屬性看做分類數據（categorical data）,，采用基于模型的聚類,，用卡方檢驗來作為距離函數，進行聚類,。L.Barbosa[6]等人提出了基于表單內容和表單頁面上下文的K-Means聚類方法,。Zhao Pengpeng[7]等人提出基于圖模型的聚類方法，算出數據源兩兩間的權值并連接成有權圖,，然后進行劃分聚類。Xu Guangyue[8]等人提出了先聚類后分類的方法,。先用LDA模型進行主題劃分,，用主題數代表聚類數目，將達到聚類精度的數據作為訓練集,，訓練出分類模型,，對前一步中聚類效果不好的數據進行后分類。

　　通過對國內外相關文獻的閱讀與研究,，在了解目前的主要方法后發(fā)現,，目前在Deep Web數據源特征提取和聚類數目的自動化確定方面還未有研究工作。正如前面提到的這些方法,，都需要事先設定聚類個數或者特征個數,。而在實際應用中聚類數目往往并不能事先知道，并會隨著數據的增多而不斷變化,。

　　Dirichlet過程[9]（Dirichlet Process）則是一種具有代表性的非參數貝葉斯模型,，基于Dirichlet過程的方法可以自動地學習特征數目和聚類個數。結合Deep Web數據源分類問題自身的需求與Dirichlet過程的特點，提出了基于Dirichlet過程的Deep Web數據源聚類方法,。

1 聚類策略及相關步驟

　　Deep Web數據源聚類分為表單特征抽取,、特征提取、聚類和結果評估四個主要步驟,，如圖1所示,。

　　1.1 表單特征抽取

　　從形式上來說，Deep Web查詢接口均以表單的形式出現在頁面中,，因此利用表單的特征作為Deep Web分類的判斷依據是一種合理的解決方式,。這也是目前多數研究人員采用的Pre-query[10]方式。觀察互聯網上的各種表單,，一個查詢接口中包含了豐富的語義信息,，其主要的表現形式為文本信息[11]。以下為一個圖書查詢接口表單信息,。

　　<from>

　　<attrgroup>

　　<attr name="Author"ename="author">

　　<domain format="text_box">

　　</domain>

　　</attr>

　　<attr name="Title"ename="title">

　　<domain format="text_box">

　　</domain>

　　</attr>

　　<attr name="Keyword"ename="keyword">

　　<domain format="text_box">

　　</domain>

　　</attr>

　　<attr name="ISBN"ename="isbn">

　　<domain format="text_box">

　　</domain>

　　</attr>

　　</attrgroup>

　　</form>

　　從以上代碼可以看到,，每個控件的name屬性包含了該接口所屬領域的絕大多數關鍵字，比如在圖書領域,，“ISBN”,、“Title”、“Author”等詞都能很好地表達其所屬的類別,。對通用實驗數據集TEL-8進行統(tǒng)計分析后發(fā)現,，在數據集中共472個查詢接口，含有name屬性的接口共463個,，覆蓋率達到98.1%,。每個類別的情況如表1所示。

　　提取出name屬性的值作為查詢接口的表示文本,，則可以將Deep Web數據源聚類問題轉化為文本聚類問題進行研究,。這些抽取出來的文本中含有噪聲，對其進行去停用詞和詞干提?。úㄌ卦~干器Porter Stemmer）,，可以提高聚類的效率和效果。

　　1.2 特征提取

　　概率主題模型假設文檔由服從某種概率分布的主題組成,，而每個主題則由服從某種概率分布的單詞組成,。Deep Web數據源也符合這種假設。Deep Web數據源由一些潛在的主題構成,，比如“書籍”,、“音樂”、“車輛”,、“機票”等,，這些潛在的主題又分別由主題內的詞構成,。每個詞按照一定的概率屬于某個主題內，比如“輪胎”,、“引擎”等詞就會以較高的概率屬于“車輛”這一主題,。

　　將查詢接口進行特征抽取并處理為文本后,，若直接應用向量空間模型將文本表示為向量,，將造成特征向量高維稀疏的問題,，影響聚類的效率與效果?？紤]到以上對應關系,，本文采用層次Dirichlet過程（HDP）進行特征提取。

　　與LDA模型一樣,，HDP也屬于概率主題模型的范疇,。不同的是LDA是參數貝葉斯模型，主題數目需要事先設定,；而HDP屬于非參數貝葉斯模型,，不需要事先設定主題數目。主題數目將作為參數之一由模型根據具體的數據學習得到,。

　　HDP模型[12]如圖2所示,。其中H為基分布，γ和α0為集中度參數,。首先,，以基分布H和集中度參數γ構成Dirichlet過程，產生全局分布G0,。這就使得各個文檔的主題可以共享,。然后，再以G0為基分布,，以α0為集中度參數,，分別為文檔集中的每一個文檔構造Dirichlet過程。這個過程產生的Gj將作為θji的分布,，然后從中抽取хji作為文檔中每個特征的類別,。本文采用HDP模型可以將查詢接口抽取出來的文本表示為主題特征,，為下一步的聚類做好準備,。

　　整個生成過程如式（1）~式（4）：

　　1.3 聚類模型

　　特征提取后，采用Dirichlet過程混合模型進行聚類,。用X={x1,，x2，…,，xn}表示Deep Web數據源,，N表示數據源中包含的樣本個數,，xi={xi1，xi2,，…,，xin}表示第i個數據源，xij表示第i個數據源的第j個特征值,?；谀Ｐ偷木垲愃枷胝J為，X由K個模型混合而成,，每個模型的混合系數由πk表示,，即πk表示每個模型占的比重，并滿足πk≥0,，k={1,，2，…,，K},，且。有限混合模型和無限混合模型的區(qū)別在于,，K是否事先已知,。有限混合模型的K需要事先指定并且固定不變，而無限混合模型則把K作為模型參數,，根據數據學習得到,。本文建立Dirichlet過程混合模型如式（5）所示：

　　其中，取多項式分布,，則該模型中的未知參數θ={π1,，π2，…,，πk,；θ1，θ2,，…,，θK；K},，其服從Dirichlet過程DP（α,，G0）。最后采用Gibbs采樣對模型中未知參數θ進行求解,，找出K值及其對應的混合系數πk,，以及各個多項式分布中的未知參數θi，達到聚類目的,。

2 實驗結果與分析

　　2.1 實驗設置

　　實驗中使用了Deep Web數據源分類的通用數據集TEL-8進行試驗,。實驗數據集總共包含472個Deep Web數據源查詢接口,，取其中含有name屬性的查詢接口，共463個,。在進行表單特征抽取和數據預處理后,，去除含有單詞數少于3個的簡單接口（共34個），最終得到429個查詢接口,，覆蓋了機票,、汽車、書籍,、租車,、酒店、工作,、電影和音樂共8個領域,。

　　本文采用在文本聚類領域常用的F-measure和熵值兩種指標來評價本文聚類方法的效果。同時與同樣使用TEL-8數據集的其他三種聚類方法進行比較,，分別是B.He提出的MDhac方法,、Zhao Pengpeng等人提出的FGC方法以及Xu Guangyue等人提出的基于LDA的先聚類后分類的方法，為下文方便對比,，將該方法簡稱XU,。

　　2.2 結果及分析

　　2.2.1 特征提取

　　建立HDP模型進行特征提取，經過100次Gibbs采樣,，估計出特征數,，并將查詢接口中的name屬性詞表示為對應的特征，達到降維的目的,。特征數目隨迭代次數變化的過程如圖3所示,。從圖中可見，特征數目穩(wěn)定在15左右,，在迭代30次左右時達到穩(wěn)定,。經過特征提取后，特征值（接口中出現的不重復單詞數）由原本的847降到15,。

　　2.2.2 聚類結果比較

　　聚類結果得到9個Cluster,，分別與8個領域的對應關系如表2所示。理想的聚類情況應該得到8個Cluster,，但是由于本文聚類方法并沒有事先指定聚類數目,，所以存在較小的誤差。認真觀察第九個Cluster可以發(fā)現,，在其中的接口數很少,，只占總接口數的2%,，明顯少于前8個Cluster,?？紤]到本文方法的完全無監(jiān)督的特性，認為該誤差在可以接受的范圍內,。

　　對上面的聚類結果應用F-measure和熵值（Entropy）兩種指標進行檢驗,，并與其他使用相同數據集的方法進行比較，比較結果如表3,、表4所示（注：由于MDhac方法的原文中并沒有提供F-measure值,，故表3中用“\”表示，同理對XU的Entropy值也用“\”表示）,。

　　實驗結果顯示,，本文方法在F-measure上取得的聚類均值優(yōu)于FGC和XU兩種方法，原因在于本文實驗結果在8個領域上的F-measure值較為平均,，沒有小于0.8的情況,。而在熵值這一評價指標上，FGC方法效果最佳,。本文方法在電影,、汽車和書籍三個領域上的熵值最優(yōu)，但是由于在音樂和酒店兩個領域的熵值過大,，而使得平均值不理想,。結合表2分析可以看到，原本屬于酒店領域的接口比較容易被錯誤分到機票領域,，而音樂和電影領域也存在類似情況,。同時，分析第九個Cluster可以看到,，這個導致誤差的小聚類中,，主要是來自音樂和電影類的接口，其原因主要在于酒店和機票領域,，以及電影和音樂領域本來就存在一定的相似性,。考慮其接口屬性,，以酒店領域和機票領域為例,，它們基本上都會包含日期、地點,、價格等關鍵詞,，在提取主題特征時容易將其視為同一特征。

3 結束語

　　Deep Web數據源分類是大規(guī)模Deep Web數據源集成的關鍵問題之一,。結合Deep Web數據源分類問題自身的需求與Dirichlet過程的特點,，本文提出了一種基于Dirichlet過程的Deep Web數據源聚類方法。實驗表明,，本文提出的方法可以有效實現Deep Web數據源聚類,，并使整個聚類過程不需要人工干預,，但是在聚類效果上，比如如何有效區(qū)分比較相似的領域,，使得聚類結果更精確,，還需要進一步探究。

參考文獻

　　[1] BERGMAN M K. The deep web： surfacing hidden value[J]. The Journal of Electronic Publishing,，2001,，7（1）：8912-8914.

　　[2] 王成良，桑銀邦.Deep Web集成系統(tǒng)中同類主題數據源選擇方法[J].計算機應用研究,，2011,，28（9）：3364-3367.

　　[3] EL-GAMIL B R， WINIWARTER W,， BO?譕IC B,， et al. Deep web integrated systems： current achievements and open issues[C]. Proceedings of the 13th International Conference on Information Integration and Web-based Applications and Services. ACM， 2011：447-450.

　　[4] NAYAK R,， SENELLART P,， SUCHANEK F M， et al. Discovering interesting information with advances in Web technology[J]. ACM SIGKDD Explorations Newsletter,， 2013,， 14（2）： 63-81.

　　[5] HE B， TAO T,， CHANG K C C. Organizing structured web sources by query schemas： a clustering approach[C]. Proceedings of the Thirteenth ACM International Conference on Information and Knowledge Management,，ACM，2004：22-31.

　　[6] BARBOSA L,， FREIRE J,， SILVA A. Organizing hidden-web databases by clustering visible web documents[C]. IEEE 23rd International Conference on Data Engineering. IEEE， 2007： 326-335.

　　[7] Zhao Pengpeng,， Huang Li,， Fang Wei， et al. Organizing structured deep web by clustering query interfaces link graph[M]. Berlin： Springer,， 2008：683-690.

　　[8] Xu Guangyue,， Zheng Weimin， Wu Haiping,， et al. Combining topic models and string kernel for deep web categorization[C]. Fuzzy Systems and Knowledge Discovery （FSKD）,， 2010 Seventh International Conference on. IEEE， 2010：2791-2795.

　　[9] ISHWARAN H,， JAMES L F. Gibbs sampling methods for stick-breaking priors [J]. Journal of the American Statistical Association,， 2001，96（453）：161-173.

　　[10] MORAES M C， HEUSER C A,， MOREIRA V P,， et al. Prequery discovery of domain-specific query forms： a survey[J]. Knowledge and Data Engineering， IEEE Transactions on,， 2013，25（8）：1830-1848.

　　[11] 祝官文,，王念濱,，王紅濱.基于主題和表單屬性的深層網絡數據源分類方法[J].電子學報，2013,，41（2）：260-266.

　　[12] TEH Y W,， JORDAN M I， BEAL M J,， et al. Hierarchical dirichlet processes [J]. Journal of the American Statistical Association,， 2006，101（476）：1566-1581.