《電子技術(shù)應(yīng)用》
您所在的位置:首頁(yè) > 嵌入式技術(shù) > 設(shè)計(jì)應(yīng)用 > 基于Dirichlet過(guò)程的Deep Web數(shù)據(jù)源聚類方法
基于Dirichlet過(guò)程的Deep Web數(shù)據(jù)源聚類方法
2015年微型機(jī)與應(yīng)用第7期
黃 進(jìn),何中市,,李英豪
(重慶大學(xué) 計(jì)算機(jī)學(xué)院,,重慶 400044)
摘要: 提出了一種基于Dirichlet過(guò)程的Deep Web數(shù)據(jù)源聚類方法,該方法采用層次Dirichlet過(guò)程(HDP)進(jìn)行特征提取,。首先將查詢接口中原本高維稀疏的文本表示為主題特征,,該過(guò)程能自動(dòng)確定特征數(shù)。然后將文本看成多項(xiàng)式模型,,采用Dirichlet過(guò)程混合模型聚類,。該模型無(wú)需人工事先指定聚類個(gè)數(shù),由Dirichlet過(guò)程根據(jù)數(shù)據(jù)自動(dòng)計(jì)算得到,,特別適用于Deep Web數(shù)據(jù)源數(shù)量大,、變化快的特點(diǎn)。在通用數(shù)據(jù)集TEL-8上進(jìn)行驗(yàn)證實(shí)驗(yàn),,并與其他聚類方法在F-measure和熵值兩個(gè)指標(biāo)上進(jìn)行對(duì)比,,均取得較好的結(jié)果。
Abstract:
Key words :

  摘  要: 提出了一種基于Dirichlet過(guò)程Deep Web數(shù)據(jù)源聚類方法,,該方法采用層次Dirichlet過(guò)程(HDP)進(jìn)行特征提取。首先將查詢接口中原本高維稀疏的文本表示為主題特征,,該過(guò)程能自動(dòng)確定特征數(shù),。然后將文本看成多項(xiàng)式模型,采用Dirichlet過(guò)程混合模型聚類,。該模型無(wú)需人工事先指定聚類個(gè)數(shù),,由Dirichlet過(guò)程根據(jù)數(shù)據(jù)自動(dòng)計(jì)算得到,特別適用于Deep Web數(shù)據(jù)源數(shù)量大,、變化快的特點(diǎn),。在通用數(shù)據(jù)集TEL-8上進(jìn)行驗(yàn)證實(shí)驗(yàn),并與其他聚類方法在F-measure和熵值兩個(gè)指標(biāo)上進(jìn)行對(duì)比,均取得較好的結(jié)果,。

  關(guān)鍵詞: Deep Web,;數(shù)據(jù)集成;特征提??;dirichlet過(guò)程;混合模型

0 引言

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

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

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

  Dirichlet過(guò)程[9](Dirichlet Process)則是一種具有代表性的非參數(shù)貝葉斯模型,,基于Dirichlet過(guò)程的方法可以自動(dòng)地學(xué)習(xí)特征數(shù)目和聚類個(gè)數(shù),。結(jié)合Deep Web數(shù)據(jù)源分類問(wèn)題自身的需求與Dirichlet過(guò)程的特點(diǎn),提出了基于Dirichlet過(guò)程的Deep Web數(shù)據(jù)源聚類方法,。

1 聚類策略及相關(guān)步驟

  Deep Web數(shù)據(jù)源聚類分為表單特征抽取,、特征提取、聚類和結(jié)果評(píng)估四個(gè)主要步驟,,如圖1所示,。

001.jpg

  1.1 表單特征抽取

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

  <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>

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

004.jpg

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

  1.2 特征提取

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

  將查詢接口進(jìn)行特征抽取并處理為文本后,,若直接應(yīng)用向量空間模型將文本表示為向量,,將造成特征向量高維稀疏的問(wèn)題,影響聚類的效率與效果,??紤]到以上對(duì)應(yīng)關(guān)系,本文采用層次Dirichlet過(guò)程(HDP)進(jìn)行特征提取,。

  與LDA模型一樣,,HDP也屬于概率主題模型的范疇。不同的是LDA是參數(shù)貝葉斯模型,,主題數(shù)目需要事先設(shè)定,;而HDP屬于非參數(shù)貝葉斯模型,不需要事先設(shè)定主題數(shù)目,。主題數(shù)目將作為參數(shù)之一由模型根據(jù)具體的數(shù)據(jù)學(xué)習(xí)得到,。

002.jpg

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

  整個(gè)生成過(guò)程如式(1)~式(4):

  14.png

  1.3 聚類模型

  特征提取后,,采用Dirichlet過(guò)程混合模型進(jìn)行聚類。用X={x1,,x2,,…,xn}表示Deep Web數(shù)據(jù)源,,N表示數(shù)據(jù)源中包含的樣本個(gè)數(shù),,xi={xi1,xi2,,…,,xin}表示第i個(gè)數(shù)據(jù)源,xij表示第i個(gè)數(shù)據(jù)源的第j個(gè)特征值,?;谀P偷木垲愃枷胝J(rèn)為,X由K個(gè)模型混合而成,,每個(gè)模型的混合系數(shù)由πk表示,,即πk表示每個(gè)模型占的比重,并滿足πk≥0,,k={1,,2,…,,K},,且OL5%NOWMH5R[6DJR%U%[5]C.png。有限混合模型和無(wú)限混合模型的區(qū)別在于,,K是否事先已知,。有限混合模型的K需要事先指定并且固定不變,而無(wú)限混合模型則把K作為模型參數(shù),,根據(jù)數(shù)據(jù)學(xué)習(xí)得到,。本文建立Dirichlet過(guò)程混合模型如式(5)所示:

  5.png

  其中,8F`VMO0A7@$U5]C}NNJC7$N.png取多項(xiàng)式分布,,則該模型中的未知參數(shù)θ={π1,,π2,…,,πk,;θ1,θ2,,…,,θK;K},其服從Dirichlet過(guò)程DP(α,,G0),。最后采用Gibbs采樣對(duì)模型中未知參數(shù)θ進(jìn)行求解,找出K值及其對(duì)應(yīng)的混合系數(shù)πk,,以及各個(gè)多項(xiàng)式分布中的未知參數(shù)θi,達(dá)到聚類目的,。

2 實(shí)驗(yàn)結(jié)果與分析

  2.1 實(shí)驗(yàn)設(shè)置

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

  本文采用在文本聚類領(lǐng)域常用的F-measure和熵值兩種指標(biāo)來(lái)評(píng)價(jià)本文聚類方法的效果,。同時(shí)與同樣使用TEL-8數(shù)據(jù)集的其他三種聚類方法進(jìn)行比較,,分別是B.He提出的MDhac方法、Zhao Pengpeng等人提出的FGC方法以及Xu Guangyue等人提出的基于LDA的先聚類后分類的方法,,為下文方便對(duì)比,,將該方法簡(jiǎn)稱XU。

  2.2 結(jié)果及分析

  2.2.1 特征提取

003.jpg

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

  2.2.2 聚類結(jié)果比較

005.jpg

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

006.jpg

  對(duì)上面的聚類結(jié)果應(yīng)用F-measure和熵值(Entropy)兩種指標(biāo)進(jìn)行檢驗(yàn),,并與其他使用相同數(shù)據(jù)集的方法進(jìn)行比較,比較結(jié)果如表3,、表4所示(注:由于MDhac方法的原文中并沒有提供F-measure值,,故表3中用“\”表示,同理對(duì)XU的Entropy值也用“\”表示),。

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

3 結(jié)束語(yǔ)

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

參考文獻(xiàn)

  [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)中同類主題數(shù)據(jù)源選擇方法[J].計(jì)算機(jī)應(yīng)用研究,,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] 祝官文,,王念濱,,王紅濱.基于主題和表單屬性的深層網(wǎng)絡(luò)數(shù)據(jù)源分類方法[J].電子學(xué)報(bào),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.


此內(nèi)容為AET網(wǎng)站原創(chuàng),,未經(jīng)授權(quán)禁止轉(zhuǎn)載,。