基于層次概念格的分面導航

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

2、作的實時性，我們提出了格挖掘算法LMiner。它以自頂向下和深度優(yōu)先方式遍歷生成格；通過倒排索引當前已生成的極小節(jié)點，進行高效的節(jié)點冗余檢查和邊的增量計算。實驗結(jié)果表明，LMiner的速度遠快于現(xiàn)有算法，而索引卻小得多。關(guān)鍵詞：分面導航；層次概念格；頻繁項集挖掘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ǎng)站和數(shù)字圖書館通常采用多維分類樹組織資源。對當前查詢結(jié)果，用戶選擇新的類別對其細化或泛化。傳統(tǒng)方式下，用戶需要查看成百上千個類別，且細化結(jié)果常為空。分面導航(faceted navigation)只顯示與當前查詢結(jié)果相關(guān)的類別，以及它們對應當前查詢結(jié)果中的資源個數(shù)7。伯克利大學的Flamenco項目首次實現(xiàn)了分面導航，利用“性別，出生地，國家，獎項，

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

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

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

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

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

13、，R(Y) R(X)。因為不同查詢得到的結(jié)果可能相同，故(查詢)類別集和查詢結(jié)果是多對一的關(guān)系。但是，極細化類別集和查詢結(jié)果是一對一的關(guān)系。定理 1 令X 是極細化類別集。對任意不可約類別集Y，若R(X) = R(Y)，則X C Y。證明 假設X C Y不成立。 u Y，必有：(1) u與X中類別兩兩獨立；或 (2) v X，u c v。對情況(1)，R(X) R(X u) = R(X) R(u) R(X) R(Y) = R(X)，推得R(X) = R(X u)。這與X是極細化類別集矛盾，故(1)不成立。對情況(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)成立。因為u 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)。因為Z C X，這與X是極細化類別集矛盾。綜上所述，假設不成立，必有X C Y。性質(zhì) 1 查詢結(jié)果和極細化類別集是一一對應的。查詢結(jié)果對應一個或多個極泛化類別集。性質(zhì) 2 令X1和X2

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

16、上界。令Y1, Y2, , Ym為X1, X2, , Xk的所有公共上界。令查詢結(jié)果S = R(i = 1.m Yi)的極細化類別集為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)中資源個數(shù)不小于給定閾值且Z是其極細化類別集。則 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的最大公共下界。當S 中資源個數(shù)小于閾值時，易知C r是X1, X2, , Xk的最大公共下界。綜上所述， Z Q C r ，Z為X1, X2, , Xk的最大公共下界。根據(jù)定理2，給定多個查詢，存在最小的極細化查詢，其結(jié)果同時包含每個給定查詢的結(jié)果；也存在最大的極細化查詢，其結(jié)果同時被每個給定查詢的結(jié)果包含。給定頻繁閾值min_sup = 2，圖1中論文數(shù)據(jù)庫對應的層次概念圖如圖2所示。3 基于層次概念格的分面導航3.1 導航操作層次概念格完整簡潔地表達了查詢結(jié)果間的關(guān)系，而用戶的瀏覽過程就是在格中不同節(jié)點之間轉(zhuǎn)移。我們提供如下操作幫助

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

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

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

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

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

23、每個元素為二元組，滿足：ref_item可將X的查詢結(jié)果細化為較小結(jié)果trans。根節(jié)點N 1的supp為6，即所有資源數(shù)目。因為所有類別中只有a, c, f對應所有資源，而a是c的超類，所以N 1的極細化類別集為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é)點的收縮對。圖 3 類別集枚舉樹Fig.3 An enumeration tree for category sets對當前節(jié)點Ni，依次考察其每個收縮對Rj。若任何已生成的樹

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

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

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

27、u的節(jié)點，其中X是節(jié)點X的極細化類別集。若X u不頻繁，則N (u|X) 為空。節(jié)點之間的偏序關(guān)系定義為其極細化類別集之間的偏序關(guān)系。圖4(b)給出了N 7生成后已挖掘格結(jié)構(gòu)的變化情況?？梢?，除新節(jié)點N 7和其父節(jié)點N 5外，其余節(jié)點的后繼不發(fā)生變化。性質(zhì) 4 令N i(j+1) 是N ij的新孩子，對應N ij的收縮對。此時路徑上各節(jié)點的后繼為：(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 當前路徑上節(jié)點為黑色，已輸出節(jié)點為白色。(b)和(c)分別是生成N 7和N8后的格結(jié)構(gòu)。Fig.4 The nodes in current path are black, while those already outputted are white.冗余檢測(subsumption check)可通過如下方式實現(xiàn)。令當前樹節(jié)點為X，所有已生成的節(jié)點為G，X中待檢測的收縮對為。是冗余的當且僅當Y X .succs(G)，N (u|Y)非空且其supp等于|S|。例如，當對N8的收縮對進行

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

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

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

32、細化類別集，而CHARM-L用倒排表索引所有已生成的節(jié)點極細化類別集。因此，二者的索引大小之比可估計為格中極小節(jié)點數(shù)目除以所有節(jié)點數(shù)目。圖5表明LMiner的索引遠小于CHARM-L的索引。例如，在chess中，當min_sup為60%時，極小節(jié)點數(shù)為3323，而所有節(jié)點數(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é)點數(shù)(#FCI)和極小節(jié)點數(shù)(#MFI)。Fig.5 The number of all the nodes and all the minimal nodes in the lattices.4.2 格挖掘速度LMiner和CHARM-L的節(jié)點生成方式是一致的，即對同樣的收縮對排序方式，所有節(jié)點的生成順序相同。它們的主要區(qū)別在于冗余檢測和邊增量生成采用了不同的數(shù)據(jù)結(jié)構(gòu)和算法。我們考察了三種收縮對排序方式，表示按其細化類別的標識符大小排序，表示按其細化結(jié)果的大小升序排序，表示按其細化結(jié)果的大小降序

34、排序。對于每個格，我們測試了LMiner和CHARM-L在這三種序下的挖掘時間，結(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對序的變化不敏感，而CHARM-L在序下的速度明顯慢于其它序；(2) LMiner在任意序下的速度均快于或接近于CHARM-L在特定序下達到的最快速度，且隨著格的增加，前者遠快于后者；(3) 隨著格大小增加(即min_sup減

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

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

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

38、應不同屏幕大小的分面導航方式。7 結(jié)論本文提出了一種新的分面導航方式實現(xiàn)搜索結(jié)果理解。其主要貢獻包括：(1) 提出了描述所有查詢和查詢結(jié)果之間關(guān)系的本體，層次概念格。(2) 提出了基于層次概念格的導航操作，用以知識發(fā)現(xiàn)。(3) 提出了格挖掘算法LMiner，并基于公開數(shù)據(jù)集進行了廣泛深入的性能分析。進一步的工作包括原型系統(tǒng)實現(xiàn)，個人信息或行業(yè)網(wǎng)站的資源管理，等。參 考 文 獻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