基于層次概念格的分面導(dǎo)航

1、PAGE PAGE 9基于層次概念格的分面導(dǎo)航*何超，1982年生，男，江蘇人，博士生。何超1,2，程學(xué)旗1，郭嘉豐11中國(guó)科學(xué)院計(jì)算技術(shù)研究所，北京，1001902中國(guó)科學(xué)院研究生院，北京，100190E-mail: hechao摘 要：分面導(dǎo)航是用戶基于多維分類目錄檢索和瀏覽資源的主要方式之一。通過(guò)推薦與當(dāng)前搜索結(jié)果相關(guān)的類別，幫助用戶理解搜索結(jié)果，并有效避免查詢結(jié)果為空。然而，目前的分面導(dǎo)航難以分析所推薦類別之間的深層語(yǔ)義。本文提出了一種層次概念格作為資源集的本體，它完整并簡(jiǎn)潔地描述查詢結(jié)果間的包含關(guān)系。在此基礎(chǔ)上，我們?cè)O(shè)計(jì)了一系列導(dǎo)航操作幫助用戶基于層次概念格進(jìn)行知識(shí)發(fā)現(xiàn)。為滿足導(dǎo)航操

2、作的實(shí)時(shí)性，我們提出了格挖掘算法LMiner。它以自頂向下和深度優(yōu)先方式遍歷生成格；通過(guò)倒排索引當(dāng)前已生成的極小節(jié)點(diǎn)，進(jìn)行高效的節(jié)點(diǎn)冗余檢查和邊的增量計(jì)算。實(shí)驗(yàn)結(jié)果表明，LMiner的速度遠(yuǎn)快于現(xiàn)有算法，而索引卻小得多。關(guān)鍵詞：分面導(dǎo)航；層次概念格；頻繁項(xiàng)集挖掘Using Hierarchical Concept Lattice to Support Faceted Navigation HE Chao, CHENG Xue-Qi, GUO Jia-FengKey Laboratory of Network Science and Technology, Institute of Comput

3、ing Technology, Chinese Academy of Sciences, Beijing 100190.E-mail: hechaoAbstract: Faceted navigation is prevalent for searching and browsing multi-faceted resources。It recommends only the categories whose refining result of current search result is not empty, in order to help users understand what

4、 current search result is related to and avoid the dead end in the process of navigation. However, current approaches for faceted navigation can hardly expose deep relations between the recommended categories. In this paper, a hierarchical concept lattice is proposed which fully and concisely expres

5、ses the set containment relation between all kinds of search results. A series of navigation operations are proposed to help knowledge discovery based on the lattice. To guarantee the real-time property of these operations, a lattice mining algorithm LMiner is proposed. It generates all the nodes in

6、 a top-down and depth-first traversal of the whole lattice. By indexing all the minimal generated nodes in an inverted list, LMiner can accomplish subsumption check and incremental edge construction efficiently. Experimental results demonstrate that LMiner is much faster than current approaches whil

7、e its index size is much less. Keywords: Faceted navigation; hierarchical concept lattice; frequent itemset mining1 引 言電子商務(wù)網(wǎng)站和數(shù)字圖書(shū)館通常采用多維分類樹(shù)組織資源。對(duì)當(dāng)前查詢結(jié)果，用戶選擇新的類別對(duì)其細(xì)化或泛化。傳統(tǒng)方式下，用戶需要查看成百上千個(gè)類別，且細(xì)化結(jié)果常為空。分面導(dǎo)航(faceted navigation)只顯示與當(dāng)前查詢結(jié)果相關(guān)的類別，以及它們對(duì)應(yīng)當(dāng)前查詢結(jié)果中的資源個(gè)數(shù)7。伯克利大學(xué)的Flamenco項(xiàng)目首次實(shí)現(xiàn)了分面導(dǎo)航，利用“性別，出生地，國(guó)家，獎(jiǎng)項(xiàng)，

8、年份”五個(gè)類別供用戶查詢?yōu)g覽諾貝爾獎(jiǎng)得主。例如，當(dāng)用戶查詢“經(jīng)濟(jì)學(xué)獎(jiǎng)”，性別類別中只顯示“男性(55)”，因?yàn)樗?5位獲此獎(jiǎng)?wù)呔鶠槟行?。通過(guò)這種查詢結(jié)果分析，分面導(dǎo)航使得用戶需要查看的類別數(shù)目大大降低，避免瀏覽過(guò)程中出現(xiàn)空結(jié)果，故成為主要的多維資源查詢和瀏覽方式。目前的分面導(dǎo)航難以幫助用戶發(fā)現(xiàn)與查詢結(jié)果相關(guān)的類別之間的深層語(yǔ)義，如不同相關(guān)類別的細(xì)化結(jié)果可能存在的包含或相等關(guān)系，以及它們的不同組合對(duì)應(yīng)的細(xì)化結(jié)果可能相同。另外，用戶不清楚哪些查詢的結(jié)果與當(dāng)前結(jié)果相似（即資源集重疊程度高）。當(dāng)數(shù)據(jù)規(guī)模龐大時(shí)，無(wú)法高效地幫助用戶分析不同查詢對(duì)應(yīng)的資源集之間的關(guān)系，如它們的交集對(duì)應(yīng)哪些相關(guān)類別，或哪些

9、查詢的返回結(jié)果同時(shí)包含它們。簡(jiǎn)言之，目前的分面導(dǎo)航無(wú)法將不同查詢結(jié)果之間的關(guān)系簡(jiǎn)潔有效地呈現(xiàn)給用戶，并據(jù)此進(jìn)行知識(shí)發(fā)現(xiàn)。我們提出了一種層次概念格作為資源集的本體，它完整并簡(jiǎn)潔地表達(dá)了查詢結(jié)果間的包含關(guān)系。層次概念格是無(wú)環(huán)有向圖。格中節(jié)點(diǎn)和查詢結(jié)果一一對(duì)應(yīng)，只保存對(duì)應(yīng)查詢結(jié)果的最細(xì)化語(yǔ)義。節(jié)點(diǎn)間的邊表示它們之間存在極小細(xì)分/泛化關(guān)系。圖1給出了某論文數(shù)據(jù)庫(kù)的多維分類目錄和每個(gè)資源所屬類別，其層次概念格如圖2所示。我們?cè)O(shè)計(jì)了一系列導(dǎo)航操作幫助用戶基于層次概念格進(jìn)行知識(shí)發(fā)現(xiàn)。例如，定位操作找出給定查詢所對(duì)應(yīng)的格中節(jié)點(diǎn)；語(yǔ)義范圍操作給出當(dāng)前查詢結(jié)果的最細(xì)化分類語(yǔ)義和極泛化分類語(yǔ)義；放大和縮小操作基于用

10、戶指定比例泛化和細(xì)化當(dāng)前查詢結(jié)果；相似操作基于用戶指定比例查找相似節(jié)點(diǎn)；等等。因此，層次概念格是一張包含所有查詢結(jié)果間關(guān)系的地圖，導(dǎo)航操作方便用戶對(duì)其瀏覽。為滿足分面導(dǎo)航的實(shí)時(shí)性，我們進(jìn)一步提出了格挖掘算法LMiner以進(jìn)行格的生成與索引。LMiner采用自頂向下且深度優(yōu)先方式遍歷生成格中所有節(jié)點(diǎn)，并通過(guò)動(dòng)態(tài)維護(hù)每個(gè)節(jié)點(diǎn)在當(dāng)前已生成節(jié)點(diǎn)中的后繼來(lái)同步生成邊。利用倒排索引當(dāng)前已生成的極小節(jié)點(diǎn)，高效地完成節(jié)點(diǎn)冗余檢查和邊的增量計(jì)算。當(dāng)格生成后，該索引支持高效的格導(dǎo)航算法。最后，我們針對(duì)公開(kāi)數(shù)據(jù)集進(jìn)行了性能分析。實(shí)驗(yàn)結(jié)果表明，LMiner的速度遠(yuǎn)快于現(xiàn)有算法，而索引卻小得多。圖 1 論文數(shù)據(jù)庫(kù)中多維

11、分類目錄及每篇論文對(duì)應(yīng)的類別Fig.1 A paper database2 層次概念格概念格(Concept Lattice) 6被廣泛應(yīng)用于基于對(duì)象和屬性的本體構(gòu)建。傳統(tǒng)概念格無(wú)法處理類別層次關(guān)系。我們證明當(dāng)類別間存在即層次關(guān)系時(shí)，所有查詢結(jié)果構(gòu)成格，稱為層次概念格。在多維分類目錄中，某類別可以是多個(gè)類別的超類或子類。故多維分類目錄可表示為偏序集，其中C是所有類別，對(duì)類別u, v C，u c v當(dāng)且僅當(dāng)u 是v的子類。定義 1 類別集C 不可約 當(dāng)且僅當(dāng)u, v C (u v)，u和v互相獨(dú)立。對(duì)任意不可約類別集X和Y，X C Y當(dāng)且僅當(dāng) u Y， v X，滿足v c u。圖 2 層次概念格

12、(頻繁閾值min_sup = 2)Fig.2 Hierarchical Concept Lattice易知C是不可約類別集之間的偏序關(guān)系。X C Y表明X對(duì)Y細(xì)分(或Y對(duì)X泛化)。記類別集C對(duì)應(yīng)的不可約類別集為Cr=u : u C v C (v c u)。記資源集為T(mén) =: rid是資源標(biāo)識(shí) X為該資源所屬的類別集 X不可約。故數(shù)據(jù)庫(kù)可表示為二元組。類別集C的查詢結(jié)果記為R(C)，易知R(C)= : T u C (X C u)?？疹悇e集對(duì)應(yīng)全體資源，即R( ) = T。定義 2 類別集X 是極泛化的當(dāng)且僅當(dāng)X不可約且Y C X，R(Y) R(X)。類別集X是極細(xì)化的當(dāng)且僅當(dāng)X不可約且Y C X

13、，R(Y) R(X)。因?yàn)椴煌樵兊玫降慕Y(jié)果可能相同，故(查詢)類別集和查詢結(jié)果是多對(duì)一的關(guān)系。但是，極細(xì)化類別集和查詢結(jié)果是一對(duì)一的關(guān)系。定理 1 令X 是極細(xì)化類別集。對(duì)任意不可約類別集Y，若R(X) = R(Y)，則X C Y。證明 假設(shè)X C Y不成立。 u Y，必有：(1) u與X中類別兩兩獨(dú)立；或 (2) v X，u c v。對(duì)情況(1)，R(X) R(X u) = R(X) R(u) R(X) R(Y) = R(X)，推得R(X) = R(X u)。這與X是極細(xì)化類別集矛盾，故(1)不成立。對(duì)情況(2)，令C是X中所有大于u的類別構(gòu)成的集合，則Z = X C u是不可約類別集。易

14、知R(C) R(u)。故R(X) = R(X C) C) = R(X C) R(C) R(X C) R(u) = R(Z)，即R(X) R(Z)成立。因?yàn)閡 Y，故R(u) R(Y)。又R(X) = R(Y)，故R(u) R(X)。顯然，R(X C) R(X)。故 R(Z) = R(X C u) = R(X C) R(u) R(X) R(X) = R(X)，即R(Z) R(X)成立。因此，R(Z) = R(X)。因?yàn)閆 C X，這與X是極細(xì)化類別集矛盾。綜上所述，假設(shè)不成立，必有X C Y。性質(zhì) 1 查詢結(jié)果和極細(xì)化類別集是一一對(duì)應(yīng)的。查詢結(jié)果對(duì)應(yīng)一個(gè)或多個(gè)極泛化類別集。性質(zhì) 2 令X1和X2

15、分別是任意查詢結(jié)果S1和S2的極細(xì)化類別集。則X1 C X2當(dāng)且僅當(dāng)S1 S2。某類別集C是頻繁的當(dāng)且僅當(dāng) |R(C)| min_sup (其中0 min_sup |T |)，即其查詢結(jié)果的大小不小于給定閾值。令Q是所有頻繁的極細(xì)化類別集。根據(jù)定理2，偏序集是完全格。令極細(xì)化類別集X滿足R(X) = T，顯然X Q。X和C r分別是該格的最大上界和最小下界，故是完全有界格。定理 2 對(duì)任意X1, X2, , Xk Q C r ，存在 Y，Z Q C r ，其分別為X1, X2, , Xk的最小公共上界和最大公共下界。證明 (1) 根據(jù)性質(zhì)2，易知T的極細(xì)化類別集是X1, X2, , Xk的公共

16、上界。令Y1, Y2, , Ym為X1, X2, , Xk的所有公共上界。令查詢結(jié)果S = R(i = 1.m Yi)的極細(xì)化類別集為Y。易知Y是頻繁的，故Y Q。 i 1, m，S R(Yi)，故Y C Yi。所以Y是X1, X2, , Xk的最小公共上界。(2) 令查詢結(jié)果S = R(i = 1.k Xi)中資源個(gè)數(shù)不小于給定閾值且Z是其極細(xì)化類別集。則 i 1, k，S R(Xi)。根據(jù)性質(zhì)2，易知Z是X1, X2, , Xk的公共下界。令L是X1, X2, , Xk的任意公共下界，即 i 1, k，L C Xi，故R(L) R(Xi)。因此，R(L) i = 1.k R(Xi) = S

17、。由性質(zhì)2，L C Z。所以Z是X1, X2, , Xk的最大公共下界。當(dāng)S 中資源個(gè)數(shù)小于閾值時(shí)，易知C r是X1, X2, , Xk的最大公共下界。綜上所述， Z Q C r ，Z為X1, X2, , Xk的最大公共下界。根據(jù)定理2，給定多個(gè)查詢，存在最小的極細(xì)化查詢，其結(jié)果同時(shí)包含每個(gè)給定查詢的結(jié)果；也存在最大的極細(xì)化查詢，其結(jié)果同時(shí)被每個(gè)給定查詢的結(jié)果包含。給定頻繁閾值min_sup = 2，圖1中論文數(shù)據(jù)庫(kù)對(duì)應(yīng)的層次概念圖如圖2所示。3 基于層次概念格的分面導(dǎo)航3.1 導(dǎo)航操作層次概念格完整簡(jiǎn)潔地表達(dá)了查詢結(jié)果間的關(guān)系，而用戶的瀏覽過(guò)程就是在格中不同節(jié)點(diǎn)之間轉(zhuǎn)移。我們提供如下操作幫助

18、用戶提高瀏覽效率：(1) locate(C)：給定查詢C，顯示相應(yīng)節(jié)點(diǎn)及其極細(xì)化類別集；(2) generator(N)：顯示當(dāng)前節(jié)點(diǎn)N對(duì)應(yīng)的極泛化類別集；(3) expand(N, )：顯示與當(dāng)前節(jié)點(diǎn)N距離不超過(guò)的極遠(yuǎn)祖先節(jié)點(diǎn)；(4) refine(N, )：顯示與當(dāng)前節(jié)點(diǎn)N距離不超過(guò)的極遠(yuǎn)后代節(jié)點(diǎn)；(5) maxsim(N, )：顯示與當(dāng)前節(jié)點(diǎn)N有公共后代且與N距離不超過(guò)的極大節(jié)點(diǎn)(非N的祖先或后代)；(6) join(N 1, N 2, , N k) 顯示節(jié)點(diǎn)N 1, N 2, ,和N k的最近公共祖先；(7) meet(N 1, N 2, , N k) 顯示節(jié)點(diǎn)N 1, N 2, ,和

19、N k的最近公共后代。任意給定節(jié)點(diǎn)N 1和N 2，其距離為對(duì)應(yīng)查詢結(jié)果S1和S2的Jaccard距離，即dist(N 1, N 2) = 1 |S1S2|/|S1S2|。該距離滿足三角不等式。locate操作幫助用戶定位查詢對(duì)應(yīng)的節(jié)點(diǎn)，其保存的極細(xì)化類別集反映了查詢結(jié)果的分類語(yǔ)義下界，其分類語(yǔ)義的上界由generator操作得到。expand和refine操作可以按比例細(xì)化和泛化，maxsim操作可以簡(jiǎn)化多個(gè)交替的細(xì)化泛化操作，它們使得用戶更易控制細(xì)化和泛化的行為和粒度，逐步逼近潛在查詢目的。join和meet操作可以用來(lái)分析多個(gè)歷史查詢。meet操作幫助用戶了解多個(gè)查詢結(jié)果的交集的分類語(yǔ)義，

20、而join操作分析它們同屬什么類別。3.2 導(dǎo)航算法preds, succs, expand, refine, maxsim的實(shí)現(xiàn)比較直觀，locate操作可基于格挖掘過(guò)程中生成的索性高效實(shí)現(xiàn)，meet可通過(guò)locate實(shí)現(xiàn)，不再贅述。性質(zhì) 3 meet(N 1, N 2, , N k) = locate(i = 1.k Xi)，其中Xi是N i的極細(xì)化類別集。令N 是當(dāng)前節(jié)點(diǎn)，其極細(xì)化類別集為X，其所有前驅(qū)節(jié)點(diǎn)的極細(xì)化類別集分別為P1, P2, , Pk。易知對(duì)任意不可約類別集G C X，G是N 的極泛化類別集當(dāng)且僅當(dāng)同時(shí)滿足：(1) i 1, k，Pi C G不成立；(2) 對(duì)任意不可約類

21、別集Y C G， i 1, k，使得Pi C Y。因此，N 的所有極泛化類別集可按如下方式求得。令U = u : X是N 的極細(xì)化類別集 uC u C X，易知N 的任意極泛化類別集必為U的子集。初始化G = 。依次考察U的大小為|U|1到1的所有子集。令當(dāng)前子集為C，約簡(jiǎn)得到其對(duì)應(yīng)的不可約類別集Cr。如果Cr不大于等于任意Pi (i 1, k)，將其放入G；否則，C的任意子集都不再考察(即剪枝)。最后，G 中極大元素為N 的極泛化類別集。join(N 1, N 2, , N k)的實(shí)現(xiàn)如下。從格的根節(jié)點(diǎn)(對(duì)應(yīng)所有資源T)開(kāi)始往下走。令當(dāng)前節(jié)點(diǎn)為NJ。若存在NJ的某后繼節(jié)點(diǎn)NS，其極細(xì)化類別集

22、大于等于每個(gè)Ni (i 1, k)的極細(xì)化類別集，則向下走到NS；否則，NJ即為N 1, N 2, , N k的最小公共上界。4 格挖掘算法L-Miner當(dāng)數(shù)據(jù)庫(kù)較大時(shí)，在用戶瀏覽過(guò)程中動(dòng)態(tài)生成格的代價(jià)太高，如計(jì)算當(dāng)前查詢結(jié)果的極細(xì)化類別集就需要掃描一遍數(shù)據(jù)庫(kù)。為滿足實(shí)時(shí)性，需要預(yù)先生成格。LMiner采用一棵類別集枚舉樹(shù)以自頂向下且深度優(yōu)先方式生成格節(jié)點(diǎn)，同時(shí)進(jìn)行邊的增量計(jì)算。4.1 基于類別集枚舉樹(shù)的格增量計(jì)算圖3描述了對(duì)應(yīng)圖1數(shù)據(jù)庫(kù)的類別集枚舉樹(shù)生成過(guò)程。樹(shù)節(jié)點(diǎn)和格節(jié)點(diǎn)一一對(duì)應(yīng)。每個(gè)樹(shù)節(jié)點(diǎn)表示為三元組，fci是極細(xì)化類別集，supp是其對(duì)應(yīng)資源集的大小，ref_seq是收縮對(duì)序列，序列中

23、每個(gè)元素為二元組，滿足：ref_item可將X的查詢結(jié)果細(xì)化為較小結(jié)果trans。根節(jié)點(diǎn)N 1的supp為6，即所有資源數(shù)目。因?yàn)樗蓄悇e中只有a, c, f對(duì)應(yīng)所有資源，而a是c的超類，所以N 1的極細(xì)化類別集為c, f。其余類別b, d, e, g, h的查詢結(jié)果分別為1, 3, 4, 5, 2, 4, 5, 6, 2, 4, 5, 6, 1, 3, 5, 6, 1, 2, 3, 4, 5，資源數(shù)均小于6，故均為根節(jié)點(diǎn)的收縮對(duì)。圖 3 類別集枚舉樹(shù)Fig.3 An enumeration tree for category sets對(duì)當(dāng)前節(jié)點(diǎn)Ni，依次考察其每個(gè)收縮對(duì)Rj。若任何已生成的樹(shù)

24、節(jié)點(diǎn)的資源集都不等于Rj.trans（即冗余檢測(cè) subsumption check），則生成Rj對(duì)應(yīng)的Ni的新孩子節(jié)點(diǎn)Nk，其對(duì)應(yīng)資源集為trans。值得注意的是，該枚舉樹(shù)是深度優(yōu)先生成的，故只有Nk所在的子樹(shù)均已生成后才會(huì)考察其父節(jié)點(diǎn)Ni中Rj后的收縮對(duì)。Nk的supp為|Rj.trans|。Nk的極細(xì)化類別集和可通過(guò)考察Ni中Rj后的每個(gè)收縮對(duì)與Rj的關(guān)系得到。圖3中樹(shù)節(jié)點(diǎn)生成順序和其標(biāo)識(shí)符大小一致。N 1的第一個(gè)孩子N2對(duì)應(yīng)其第一個(gè)收縮對(duì)，其trans和后面的收縮對(duì)的交分別為4, 5, 4, 5, 1, 3, 5和1, 3, 4, 5。由此可見(jiàn)，d, e, g可將N2細(xì)化為更?。ㄇ也恍?/p>

25、于閾值的）資源集，而h無(wú)法將其細(xì)化為更小。因此，N 2的極細(xì)化類別集為類別集N1.fci b h (=c, f, b, h)對(duì)應(yīng)的不可約類別集c, b, h(圖中以圓圈標(biāo)識(shí))。同理，N2的第一個(gè)收縮對(duì)對(duì)應(yīng)其第一個(gè)孩子N3。該收縮對(duì)與其后收縮對(duì)的交分別為4, 5和5。故N3.fci為N2.fci d e(=c, b, h, d, e)的不可約類別集b, h, e，且N3的收縮對(duì)序列為空(因?yàn)閙in_sup = 2)。接下來(lái)考察N2的第二個(gè)收縮對(duì)，它的trans和N2相同，故冗余，不生成新節(jié)點(diǎn)。不斷執(zhí)行上述過(guò)程直至遍歷生成整棵枚舉樹(shù)。根據(jù)18，在上述過(guò)程中：(1) 收縮對(duì)序列的初始順序可以任意；(

26、2) 若當(dāng)前考察的收縮對(duì)其trans包含或等于其后某收縮對(duì)R的trans，則可以刪除R（因?yàn)樗厝哂啵?.2 基于倒排索引的冗余檢測(cè)和節(jié)點(diǎn)后繼維護(hù)枚舉樹(shù)的節(jié)點(diǎn)生成順序和前序遍歷一致，但輸出順序和后序遍歷一致。令Q為所有格節(jié)點(diǎn)，而G為所有已生成的格節(jié)點(diǎn)（注意格節(jié)點(diǎn)和樹(shù)節(jié)點(diǎn)一一對(duì)應(yīng)）。我們維護(hù)枚舉樹(shù)中當(dāng)前路徑上每個(gè)節(jié)點(diǎn)N在G中的后繼，記為N.succs(G)。根據(jù)枚舉樹(shù)的生成過(guò)程知，當(dāng)N輸出時(shí)，N.succs(G) 即為N在Q中后繼。因此，格節(jié)點(diǎn)的后繼節(jié)點(diǎn)在它對(duì)應(yīng)的樹(shù)節(jié)點(diǎn)輸出時(shí)即完全確定。令枚舉樹(shù)中當(dāng)前路徑為N i0N i1的N ij，記所有已生成節(jié)點(diǎn)為G ij。記N (u|X) 為對(duì)應(yīng)查詢X

27、u的節(jié)點(diǎn)，其中X是節(jié)點(diǎn)X的極細(xì)化類別集。若X u不頻繁，則N (u|X) 為空。節(jié)點(diǎn)之間的偏序關(guān)系定義為其極細(xì)化類別集之間的偏序關(guān)系。圖4(b)給出了N 7生成后已挖掘格結(jié)構(gòu)的變化情況?？梢?jiàn)，除新節(jié)點(diǎn)N 7和其父節(jié)點(diǎn)N 5外，其余節(jié)點(diǎn)的后繼不發(fā)生變化。性質(zhì) 4 令N i(j+1) 是N ij的新孩子，對(duì)應(yīng)N ij的收縮對(duì)。此時(shí)路徑上各節(jié)點(diǎn)的后繼為：(1) k 0, j1，Nik.succs(Gi(j+1) = N ik.succs(G ij)；(2) N i(j+1).succs(Gi(j+1) = maxN (u|X) : X N ij.succs(G ij)；(3) Nij.succs(G

28、i(j+1) = N ij.succs(G ij) N i(j+1).succs(Gi(j+1)。圖 4 當(dāng)前路徑上節(jié)點(diǎn)為黑色，已輸出節(jié)點(diǎn)為白色。(b)和(c)分別是生成N 7和N8后的格結(jié)構(gòu)。Fig.4 The nodes in current path are black, while those already outputted are white.冗余檢測(cè)(subsumption check)可通過(guò)如下方式實(shí)現(xiàn)。令當(dāng)前樹(shù)節(jié)點(diǎn)為X，所有已生成的節(jié)點(diǎn)為G，X中待檢測(cè)的收縮對(duì)為。是冗余的當(dāng)且僅當(dāng)Y X .succs(G)，N (u|Y)非空且其supp等于|S|。例如，當(dāng)對(duì)N8的收縮對(duì)進(jìn)行

29、冗余檢測(cè)時(shí)，只需查驗(yàn)N8此時(shí)的后繼N4和N6被h細(xì)化后能否得到1,3,5。因?yàn)閔 N4.fci，所以N (h|N4)= N4。又N4.supp = 3，由定理5，該收縮對(duì)是冗余的。綜上所述，待解的關(guān)鍵操作是：給定節(jié)點(diǎn)X和類別u，確定N (u|X)。令M是格中所有極小節(jié)點(diǎn)（即無(wú)后代），X為X的極細(xì)化類別集。易知N (u|X)非空僅當(dāng)Y M，Xu v : YC v，其中Y是Y的極細(xì)化類別集。若上述Y 存在，從它出發(fā)，沿著格每次往上走一步，必遇到節(jié)點(diǎn)N (u|X)。令當(dāng)前所在位置為節(jié)點(diǎn)Z。依次檢驗(yàn)Z的每個(gè)前驅(qū)節(jié)點(diǎn)P直至滿足：Xu v : PC v，P是P的極細(xì)化類別集。若存在，則從Z走到P；否則，Z

30、即為N (u|X)。因此，我們只需用倒排表索引M：Y M， v v : YC v（Y是Y的極細(xì)化類別集），將Y 的標(biāo)識(shí)符添加到倒排表里v的列表中。表1 數(shù)據(jù)集特征Tab.1 Dataset Characteristics數(shù)據(jù)集名稱總資源個(gè)數(shù)總類別個(gè)數(shù)平均類別數(shù) 最多類別數(shù)chess3,196763737connect67,5571304343mushroom8,1241192323pumsb49,046211374745 實(shí)驗(yàn)分析本節(jié)通過(guò)實(shí)驗(yàn)分析我們提出的格挖掘算法LMiner的運(yùn)行速度和索引大小。運(yùn)行環(huán)境為L(zhǎng)enovo啟天M7000，雙核2.93GHz CPU，2GB內(nèi)存，Ubuntu 9.

31、04操作系統(tǒng)。代碼用C+編寫(xiě)。我們采用UCI KDD Archive /中的公開(kāi)數(shù)據(jù)集chess, connect, mushroom和pumsb，其中每條記錄對(duì)應(yīng)一個(gè)資源，每個(gè)項(xiàng)集對(duì)應(yīng)一個(gè)類別。頻繁項(xiàng)集挖掘算法中廣泛采用這些數(shù)據(jù)集進(jìn)行性能分析。表1列舉了每個(gè)數(shù)據(jù)集的總資源個(gè)數(shù)、總類別個(gè)數(shù)、每個(gè)資源對(duì)應(yīng)的平均類別數(shù)和最多類別數(shù)。盡管大量的頻繁閉項(xiàng)集挖掘可用來(lái)計(jì)算格節(jié)點(diǎn) 11, 16 15, 18，但只有CHARM-L 18同時(shí)高效地計(jì)算邊。因此，對(duì)比算法選擇CHARM-L。以下各圖的min_sup指給定閾值占所有資源數(shù)的比例。4.1 索引大小LMiner用倒排表索引目前已生成的所有極小節(jié)點(diǎn)的極

32、細(xì)化類別集，而CHARM-L用倒排表索引所有已生成的節(jié)點(diǎn)極細(xì)化類別集。因此，二者的索引大小之比可估計(jì)為格中極小節(jié)點(diǎn)數(shù)目除以所有節(jié)點(diǎn)數(shù)目。圖5表明LMiner的索引遠(yuǎn)小于CHARM-L的索引。例如，在chess中，當(dāng)min_sup為60%時(shí)，極小節(jié)點(diǎn)數(shù)為3323，而所有節(jié)點(diǎn)數(shù)為98393，故LMiner的索引大小約占CHARM-L的索引大小的3.4% (3323/98393)。在connect (min_sup = 65%)、mushroom (min_sup = 1%)和pumsb (min_sup = 65%)中，該比例分別為3.2% (1587/49705)、13.1% (6768/516

33、40)和3.4% (18182/496070)。圖 5 表1中數(shù)據(jù)集在不同min_sup下的格中節(jié)點(diǎn)數(shù)(#FCI)和極小節(jié)點(diǎn)數(shù)(#MFI)。Fig.5 The number of all the nodes and all the minimal nodes in the lattices.4.2 格挖掘速度LMiner和CHARM-L的節(jié)點(diǎn)生成方式是一致的，即對(duì)同樣的收縮對(duì)排序方式，所有節(jié)點(diǎn)的生成順序相同。它們的主要區(qū)別在于冗余檢測(cè)和邊增量生成采用了不同的數(shù)據(jù)結(jié)構(gòu)和算法。我們考察了三種收縮對(duì)排序方式，表示按其細(xì)化類別的標(biāo)識(shí)符大小排序，表示按其細(xì)化結(jié)果的大小升序排序，表示按其細(xì)化結(jié)果的大小降序

34、排序。對(duì)于每個(gè)格，我們測(cè)試了LMiner和CHARM-L在這三種序下的挖掘時(shí)間，結(jié)果如圖6所示。圖 6 表1中數(shù)據(jù)集在不同min_sup下的格挖掘速度。Fig.6 The time of mining the lattices corresponding to different min_sup values in each dataset.可以看出：(1) LMiner對(duì)序的變化不敏感，而CHARM-L在序下的速度明顯慢于其它序；(2) LMiner在任意序下的速度均快于或接近于CHARM-L在特定序下達(dá)到的最快速度，且隨著格的增加，前者遠(yuǎn)快于后者；(3) 隨著格大小增加(即min_sup減

35、小)，LMiner的挖掘時(shí)間緩慢增長(zhǎng)，而CHARM-L在各種序下均快速增長(zhǎng)。圖 7 考察每個(gè)收縮對(duì)時(shí)需訪問(wèn)的平均節(jié)點(diǎn)數(shù)。Fig.7 The average number of accessed nodes in examining an shrinking pair.圖7描述了序下LMiner和CHARM-L在考察每個(gè)收縮對(duì)時(shí)所需訪問(wèn)的平均節(jié)點(diǎn)數(shù)。在chess中，隨著格節(jié)點(diǎn)數(shù)從5084 增加到98393，LMiner所需訪問(wèn)的平均節(jié)點(diǎn)數(shù)從13緩慢增加至21，而CHAMR-L則從58快速增加到257。在connect中，隨著格節(jié)點(diǎn)數(shù)從8253增加到49705，LMiner所需訪問(wèn)的平均節(jié)點(diǎn)數(shù)從1

36、4緩慢增加至19，而CHAMR-L則從159快速增加到659。在mushroom中，隨著格節(jié)點(diǎn)數(shù)從4885增加到51640，LMiner所需訪問(wèn)的平均節(jié)點(diǎn)數(shù)從13緩慢增加至15，而CHAMR-L則從31快速增加到120。在pumsb中，隨著格節(jié)點(diǎn)數(shù)從8510增加到496070，LMiner所需訪問(wèn)的平均節(jié)點(diǎn)數(shù)從9緩慢增加至26，而CHAMR-L則從47快速增加到752。因此，LMiner隨著格的增大具有良好的可擴(kuò)展性。6 相關(guān)工作分面導(dǎo)航在工業(yè)界和學(xué)術(shù)界都得到了廣泛應(yīng)用，如Flamenco 7、SIMILE ()和Haystack ()。目前的研究主要集中兩方面。第一，推薦給用戶更有針對(duì)性的動(dòng)

37、態(tài)目錄。早期的動(dòng)態(tài)目錄顯示所有對(duì)應(yīng)非空細(xì)分結(jié)果的類別，導(dǎo)致類別數(shù)過(guò)多。文獻(xiàn)12 在生成動(dòng)態(tài)目錄前會(huì)向用戶提問(wèn)，根據(jù)用戶的回答推薦類別。文獻(xiàn)8基于個(gè)性化推薦類別。文獻(xiàn)1, 5, 17 將分面導(dǎo)航和聯(lián)機(jī)分析處理相結(jié)合。文獻(xiàn)14自動(dòng)給出對(duì)應(yīng)當(dāng)前搜索結(jié)果的最小長(zhǎng)度類別集，從而提高瀏覽效率。第二，多維分類目錄的自動(dòng)生成。類別之間的層次關(guān)系可以有效減少用戶的瀏覽代價(jià)。文獻(xiàn)3, 4分別利用監(jiān)督和無(wú)監(jiān)督學(xué)習(xí)的方法從文本數(shù)據(jù)庫(kù)中提取多維分類目錄。文獻(xiàn)9采用無(wú)監(jiān)督學(xué)習(xí)方法自動(dòng)構(gòu)建多維分類目錄來(lái)組織用戶提供的關(guān)鍵字。其它的相關(guān)研究包括，文獻(xiàn)10, 13利用分面導(dǎo)航幫助用戶瀏覽半結(jié)構(gòu)化的RDF數(shù)據(jù)；文獻(xiàn)2提出一種能適

38、應(yīng)不同屏幕大小的分面導(dǎo)航方式。7 結(jié)論本文提出了一種新的分面導(dǎo)航方式實(shí)現(xiàn)搜索結(jié)果理解。其主要貢獻(xiàn)包括：(1) 提出了描述所有查詢和查詢結(jié)果之間關(guān)系的本體，層次概念格。(2) 提出了基于層次概念格的導(dǎo)航操作，用以知識(shí)發(fā)現(xiàn)。(3) 提出了格挖掘算法LMiner，并基于公開(kāi)數(shù)據(jù)集進(jìn)行了廣泛深入的性能分析。進(jìn)一步的工作包括原型系統(tǒng)實(shí)現(xiàn)，個(gè)人信息或行業(yè)網(wǎng)站的資源管理，等。參 考 文 獻(xiàn)O. Ben-Yitzhak, et al, “Beyond basic faceted search,” Proc. Intl Conf. Web Search and Web Data Mining (WSDM 08)

39、, pp. 33-44, 2008. R. Dachselt et al. “FacetZoom: a continuous multi-scale widget for navigating hierarchical metadata,” Proc. 26th SIGCHI Conf. Human Factors in Computing Systems (SIGCHI 08), pp. 1353-1356, 2008. W. Dakka, P. Ipeirotis, and K. Wood, “Automatic construction of multifaceted browsing

40、interfaces,” Proc. 14th Intl Conf. Information and Knowledge Management (CIKM 05), pp. 768-775, 2005. W. Dakka and P.G. Ipeirotis, “Automatic Extraction of Useful Facet Hierarchies from Text Databases,” Proc. Intl Conf. Data Engineering (ICDE 08), pp. 466-475, 2008. D. Dash, et al, “Dynamic faceted

41、search for discovery-driven analysis,” Proc. 17th Intl Conf. Information and Knowledge Management (CIKM 08), pp. 3-12, 2008.B. Ganter and R. Wille, Formal Concept Analysis: Mathematical Foundations, Springer, Heidelberg, 1999.M. Hearst, “Clustering versus Faceted Categories for Information Explorati

42、on,” Commun. of the ACM, vol. 49, no. 4, pp. 59-61, 2006.J. Koren, Y. Zhang and X. Liu, “Personalized interactive faceted search,” Proc. 17th Intl Conf. World Wide Web (WWW 08), pp. 477-486, 2008. X. Ling, et al, “Mining multi-faceted overviews of arbitrary topics in a text collection,” Proc. 14th ACM SIGKDD Intl Conf. Knowledge Dis-covery and Data Mining (KDD 08), pp. 497-505, 2008. E. Oren, R. Delbru and S. Decker, “Extending faceted navigation