面向拓?fù)涓兄膶哟谓Y(jié)構(gòu)信息可視探索方法

譚博友，韓永國(guó)，王桂娟，趙韋鑫，周 銳，蔡夢(mèng)杰，吳亞?wèn)|

(1.西南科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，四川 綿陽(yáng) 621000；2.四川輕化工大學(xué) 計(jì)算科學(xué)與工程學(xué)院，四川 自貢 643000)

0 引 言

層次結(jié)構(gòu)數(shù)據(jù)不僅常見于文件系統(tǒng)、動(dòng)植物分類、系譜圖等領(lǐng)域，還能將復(fù)雜領(lǐng)域通過(guò)層次結(jié)構(gòu)的形式進(jìn)行簡(jiǎn)化表示[1]。層次數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu)，能直觀地反映某一事物的分類特征，幫助數(shù)據(jù)分析人員探尋結(jié)構(gòu)信息并理解層次數(shù)據(jù)的分類模式等。因此，探索層次數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu)信息是層次數(shù)據(jù)分析的一項(xiàng)重要環(huán)節(jié)。

通過(guò)可視化的方式探索層次數(shù)據(jù)比較常見。現(xiàn)有的層次數(shù)據(jù)可視化技術(shù)主要分為連接式、空間填充和混合式[2]。層次拓?fù)浣Y(jié)構(gòu)的繪制技術(shù)通常基于Reingold和Tilford`s[3]算法，利用模塊化方法來(lái)定位節(jié)點(diǎn)，其中子節(jié)點(diǎn)位于父節(jié)點(diǎn)下方(自上而下的方向)，或者位于右側(cè)(從左向右的方向)。由于顯示空間的限制，原始的經(jīng)典布局主要在一維上擴(kuò)展，降低了層次結(jié)構(gòu)數(shù)據(jù)可視探索的實(shí)用性，同時(shí)伴隨節(jié)點(diǎn)數(shù)的增多也帶來(lái)了節(jié)點(diǎn)遮蔽和分支擁擠等情況。為了克服上述限制，各種交互技術(shù)應(yīng)運(yùn)而生，例如縮放、魚眼視圖和一維扭曲。流行的交互式可視化方法則通過(guò)顯示感興趣的子結(jié)構(gòu)同時(shí)縮小其他子結(jié)構(gòu)來(lái)提供焦點(diǎn)+上下文視圖。如SpaceTree和DOITree。此外，視覺線索提供有關(guān)隱藏分支內(nèi)容的持續(xù)信息，并以平滑的動(dòng)畫顯示節(jié)點(diǎn)何時(shí)被聚焦或縮小。對(duì)隱藏分支使用視覺編碼提示在探索大型層次結(jié)構(gòu)方面已經(jīng)證明是有效的[4-5]。但在尋找目標(biāo)子結(jié)構(gòu)或相似子結(jié)構(gòu)時(shí)，需頻繁地點(diǎn)擊視覺提示展開隱藏的分支，這將浪費(fèi)用戶大量的時(shí)間，同時(shí)對(duì)用戶的瞬時(shí)記憶也帶來(lái)了挑戰(zhàn)。對(duì)于采用興趣度進(jìn)行分支隱藏的方法，需要用戶指定各節(jié)點(diǎn)的初始興趣度，這對(duì)于用戶來(lái)說(shuō)具有一定的挑戰(zhàn)性。若節(jié)點(diǎn)未指定興趣度，如何確定那些分支應(yīng)該隱藏并確保未隱藏的分支能為用戶呈現(xiàn)更多的結(jié)構(gòu)信息，降低用戶在探索的過(guò)程中頻繁點(diǎn)擊的隱藏分支的時(shí)間消耗也具有挑戰(zhàn)性。

基于以上問(wèn)題，該文提出了一個(gè)面向拓?fù)涓兄膶哟谓Y(jié)構(gòu)信息探索框架。該框架通過(guò)評(píng)估重要節(jié)點(diǎn)來(lái)解決無(wú)興趣度標(biāo)記時(shí)分支隱藏的問(wèn)題并保留更多的結(jié)構(gòu)信息。通過(guò)提取關(guān)鍵子結(jié)構(gòu)對(duì)整體層次結(jié)構(gòu)進(jìn)行概要，同時(shí)引入圖嵌入算法對(duì)結(jié)構(gòu)進(jìn)行向量化來(lái)提高用戶探索子結(jié)構(gòu)和相似子結(jié)構(gòu)的效率。最后，基于該框架實(shí)現(xiàn)了一個(gè)交互式的可視探索系統(tǒng),通過(guò)案例分析和用戶實(shí)驗(yàn)來(lái)驗(yàn)證該方法的有效性。

1 層次拓?fù)浣Y(jié)構(gòu)信息計(jì)算

層次結(jié)構(gòu)信息計(jì)算主要由三大模塊組成，分別為重要節(jié)點(diǎn)評(píng)估模塊、關(guān)鍵子結(jié)構(gòu)提取模塊、相似子結(jié)構(gòu)提取模塊。

1.1 重要節(jié)點(diǎn)評(píng)估

為解決在無(wú)興趣度標(biāo)記的層次結(jié)構(gòu)數(shù)據(jù)分支隱藏的問(wèn)題，該文引入網(wǎng)絡(luò)分析領(lǐng)域中提取重要節(jié)點(diǎn)的分析方法，對(duì)層次數(shù)據(jù)中的重要節(jié)點(diǎn)進(jìn)行提取。在對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行重要節(jié)點(diǎn)評(píng)估的算法中，常采用度指標(biāo)、接近度指標(biāo)和介數(shù)指標(biāo)。其中接近度指標(biāo)和介數(shù)指標(biāo)都需要計(jì)算各節(jié)點(diǎn)之間的最短路徑，但層次結(jié)構(gòu)數(shù)據(jù)大多都只有一個(gè)根節(jié)點(diǎn)，大多路徑都將通過(guò)根節(jié)點(diǎn)，這將影響算法的計(jì)算結(jié)果，因此接近度指標(biāo)和介數(shù)指標(biāo)不適用層次結(jié)構(gòu)的節(jié)點(diǎn)重要性評(píng)估。度指標(biāo)則采用計(jì)算節(jié)點(diǎn)的度值來(lái)確定節(jié)點(diǎn)的重要性。除度指標(biāo)以外，張玫等[6]提出的合度評(píng)估算法以及DN(delete node based on both degree)評(píng)估算法均圍繞節(jié)點(diǎn)的度值進(jìn)行評(píng)估，為確定最佳的評(píng)估算法，依次對(duì)上述算法進(jìn)行實(shí)驗(yàn)，結(jié)果如圖1所示。從圖中可以看出，在保證沒(méi)有節(jié)點(diǎn)遮蔽以及分支擁擠的情況下，DN算法的結(jié)果保留了更多的節(jié)點(diǎn)、分支結(jié)構(gòu)和深度信息。

A:原始布局 B:度指標(biāo)評(píng)估算法結(jié)果 C:合度算法結(jié)果 D:DN算法結(jié)果

通過(guò)以上實(shí)驗(yàn)結(jié)果，該文采用DN評(píng)估算法來(lái)對(duì)層次數(shù)據(jù)的節(jié)點(diǎn)的重要性進(jìn)行評(píng)估。由于不同數(shù)據(jù)的節(jié)點(diǎn)數(shù)量不一樣，其所要收縮隱藏的節(jié)點(diǎn)數(shù)是不確定的，因此，在實(shí)際應(yīng)用中基于DN算法進(jìn)行了擴(kuò)展。以此適應(yīng)不同的節(jié)點(diǎn)數(shù)量的層次數(shù)據(jù)。其算法主要流程為:

Step1：根據(jù)DN算法計(jì)算各節(jié)點(diǎn)重要度;

Step2：根據(jù)重要度排序,取Top-k節(jié)點(diǎn),k默認(rèn)取10;

Step3：將這些重要節(jié)點(diǎn)及其子節(jié)點(diǎn)進(jìn)行隱藏，保存這些重要節(jié)點(diǎn)；

Step4：通過(guò)布局算法計(jì)算各節(jié)點(diǎn)位置;

Step5：當(dāng)前兄弟節(jié)點(diǎn)之間圓心距離減去一個(gè)直徑后是否小于閾值n,是則將當(dāng)前繪制出的所有節(jié)點(diǎn)重復(fù)Step1～Step4;

Step6：輸出重要節(jié)點(diǎn)序列。

流程中的布局算法主要指基于節(jié)點(diǎn)連接方法的正交布局和徑向布局兩種，空間填充和混合式涉及的布局算法并不適用于該文。文中食物分類數(shù)據(jù)為實(shí)驗(yàn)數(shù)據(jù)，通過(guò)調(diào)節(jié)閾值n來(lái)對(duì)比兩種算法對(duì)于重要節(jié)點(diǎn)數(shù)量的影響。實(shí)驗(yàn)結(jié)果顯示，在相同的閾值n下徑向布局算法提取的重要節(jié)點(diǎn)數(shù)量少于正交布局，且伴隨n的增長(zhǎng)，徑向布局的效果越明顯。采用正交布局時(shí)，其對(duì)于層次結(jié)構(gòu)的分層效果展示更加直觀，徑向布局的直觀效果沒(méi)有正交布局那么好。因此，如果考慮隱藏更少的重要節(jié)點(diǎn)，建議采用徑向布局；如果追求更好的層次分明可視化效果，建議采用正交布局。

1.2 關(guān)鍵子結(jié)構(gòu)提取

Ben Shneiderman曾提出“Overview first, zoom and filter, then detail on demand”的標(biāo)準(zhǔn)分析流程[7]。該流程指出在可視分析中概覽屬于第一步。因此，要更好地對(duì)層次數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu)進(jìn)行探索分析，需提供關(guān)于結(jié)構(gòu)的概覽?；赥F-IDF算法提取文本關(guān)鍵詞的思想，該文通過(guò)提取關(guān)鍵子結(jié)構(gòu)來(lái)高度概括整體層次結(jié)構(gòu)。

在提取關(guān)鍵子結(jié)構(gòu)之前，首先要解決子結(jié)構(gòu)的定義問(wèn)題，定義一種類似于文本中的詞的子結(jié)構(gòu)，這樣才能更好地提取關(guān)鍵子結(jié)構(gòu)。

在層次結(jié)構(gòu)中，其最小單元為節(jié)點(diǎn)，但一個(gè)節(jié)點(diǎn)并不能算是一個(gè)拓?fù)浣Y(jié)構(gòu)，一個(gè)拓?fù)浣Y(jié)構(gòu)至少應(yīng)包含邊。因此，定義的子結(jié)構(gòu)應(yīng)由節(jié)點(diǎn)和邊組成。在層次結(jié)構(gòu)中，由邊和節(jié)點(diǎn)組成的最小單元為父子節(jié)點(diǎn)連接而成的結(jié)構(gòu)。因此，為便于對(duì)整個(gè)層次結(jié)構(gòu)進(jìn)行分解，對(duì)子結(jié)構(gòu)定義如下：非葉子節(jié)點(diǎn)和其直接相連的節(jié)點(diǎn)構(gòu)成一個(gè)子結(jié)構(gòu)(如圖2中A區(qū)域所示)。

由于TF-IDF算法由詞頻TF和逆文檔頻率指數(shù)IDF兩部分組成，因此要提取關(guān)鍵子結(jié)構(gòu)，首先需計(jì)算TF和IDF值。計(jì)算TF值相當(dāng)于計(jì)算子結(jié)構(gòu)的頻率。由于文本中計(jì)算IDF時(shí)通常需要文檔庫(kù)，因此計(jì)算層次結(jié)構(gòu)的IDF時(shí)也需要類似于文檔庫(kù)的東西。但是層次結(jié)構(gòu)數(shù)據(jù)往往是一個(gè)整體，如果直接將整體作為一個(gè)文檔計(jì)算IDF將得到0值。因此，在計(jì)算IDF值時(shí)應(yīng)定義層次結(jié)構(gòu)的文檔庫(kù)。

該文采用以下方法定義層次結(jié)構(gòu)的文檔庫(kù)。首先，假設(shè)根節(jié)點(diǎn)直接相連的節(jié)點(diǎn)有多個(gè)，這時(shí)刪除根節(jié)點(diǎn)，可得到多個(gè)如圖2中B區(qū)域A、B、C所示的子結(jié)構(gòu)。將圖2B區(qū)域A、B、C這樣的子結(jié)構(gòu)單獨(dú)作為一個(gè)層次結(jié)構(gòu)數(shù)據(jù)，那么A、B、C就可以構(gòu)成當(dāng)前層次結(jié)構(gòu)的文檔庫(kù)。

根據(jù)以上定義，列出如下TF和IDF計(jì)算公式:

(1)

(2)

公式(1)中，Cij表示子結(jié)構(gòu)i在結(jié)構(gòu)文檔j中出現(xiàn)的次數(shù)，分母表示結(jié)構(gòu)文檔j中k個(gè)子結(jié)構(gòu)出現(xiàn)次數(shù)和。公式(2)中，T表示結(jié)構(gòu)文檔總數(shù),分母表示j結(jié)構(gòu)文檔中子結(jié)構(gòu)i出現(xiàn)在所有結(jié)構(gòu)文檔中的次數(shù)。tfij與idfi的乘積代表j結(jié)構(gòu)文檔中i子結(jié)構(gòu)的tf-idf值。然后將各結(jié)構(gòu)文檔中的各子結(jié)構(gòu)的tf-idf值進(jìn)行降序排序，取前n個(gè)作為該結(jié)構(gòu)文檔中的關(guān)鍵子結(jié)構(gòu)。最后將所有結(jié)構(gòu)文檔的關(guān)鍵子結(jié)構(gòu)進(jìn)行匯總?cè)ブ睾螅Ｓ嗟淖咏Y(jié)構(gòu)作為整個(gè)層次結(jié)構(gòu)的關(guān)鍵子結(jié)構(gòu)。

1.3 相似子結(jié)構(gòu)提取

相似子結(jié)構(gòu)是對(duì)整體結(jié)構(gòu)的一種過(guò)濾，能幫助用戶快速定位與用戶焦點(diǎn)子結(jié)構(gòu)相似的結(jié)構(gòu)特征。

相似子結(jié)構(gòu)的匹配實(shí)際為對(duì)相似子圖挖掘。現(xiàn)有的許多工作總結(jié)了近年來(lái)的子圖挖掘相關(guān)算法，如VF2plus[8]、VF3[9]等。這些算法雖然能夠得到完全匹配的子圖，但在匹配的過(guò)程中存在會(huì)匹配大量不符合的結(jié)構(gòu)導(dǎo)致大量的運(yùn)算時(shí)間消耗。

筆者希望用戶在使用該可視探索系統(tǒng)時(shí)能在較短的交互時(shí)間內(nèi)獲取結(jié)果，若采用VF3等算法，將導(dǎo)致在探索的過(guò)程中浪費(fèi)用戶大量的時(shí)間而影響交互體驗(yàn)。潘嘉鋮[10]和李珍[11]等人的研究表明，通過(guò)表示學(xué)習(xí)將網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行向量化，能減少無(wú)關(guān)的子結(jié)構(gòu)的匹配次數(shù)，極大地提高相似子結(jié)構(gòu)的提取效率，同時(shí)生成的節(jié)點(diǎn)向量更能體現(xiàn)“鄰居緊密性”。因此，該文采用表示學(xué)習(xí)的方法對(duì)層次結(jié)構(gòu)的節(jié)點(diǎn)進(jìn)行向量化。

采用GraphWave[12]算法對(duì)層次結(jié)構(gòu)進(jìn)行向量化。所需提取的相似子結(jié)構(gòu)存在于整個(gè)結(jié)構(gòu)的不同位置，只需局部結(jié)構(gòu)特征具有相似性即可。GraphWave算法已被證明能很好地提取圖中局部特征相似的結(jié)構(gòu)。

為保證提取出來(lái)的相似子結(jié)構(gòu)的準(zhǔn)確性，采取以下步驟提取相似子結(jié)構(gòu)：

Step1：對(duì)向量化后的節(jié)點(diǎn)使用高斯混合聚類模型進(jìn)行聚類，目的是將相似的節(jié)點(diǎn)聚集到同一類簇，在相同聚類簇中的節(jié)點(diǎn)所構(gòu)成的子結(jié)構(gòu)的相似性也更接近。

Step2：將用戶當(dāng)前所選子結(jié)構(gòu)的節(jié)點(diǎn)向量所屬的所有聚類簇中的所有節(jié)點(diǎn)作為相似子結(jié)構(gòu)匹配候選集。

Step3：剔除用戶所選子結(jié)構(gòu)上的節(jié)點(diǎn)，在剩余的節(jié)點(diǎn)集中構(gòu)建子結(jié)構(gòu)集合。由于構(gòu)建出的子結(jié)構(gòu)存在其節(jié)點(diǎn)數(shù)量遠(yuǎn)小于或者遠(yuǎn)大于用戶所選子結(jié)構(gòu)節(jié)點(diǎn)數(shù)量的問(wèn)題，因此將該部分結(jié)構(gòu)刪除，得到候選的相似子結(jié)構(gòu)集合。

Step4：采用Weisfeiler-Lehman圖核[13]對(duì)候選相似子結(jié)構(gòu)集合中的子結(jié)構(gòu)分別與用戶所選的子結(jié)構(gòu)進(jìn)行相似度分?jǐn)?shù)計(jì)算，相似度分?jǐn)?shù)越高的子結(jié)構(gòu)其相似度越高。按相似度分?jǐn)?shù)降序排序，取前k(默認(rèn)k=6)個(gè)相似子結(jié)構(gòu)呈現(xiàn)在相似子結(jié)構(gòu)查看面板中。

為證明文中相似子結(jié)構(gòu)提取算法的效率，與VF3算法在食物分類數(shù)據(jù)(總共463個(gè)節(jié)點(diǎn))上進(jìn)行了對(duì)比，通過(guò)測(cè)試的數(shù)據(jù)顯示，VF3算法的平均時(shí)間在15到20秒之間，而文中算法平均在5秒內(nèi)就能返回結(jié)果。因此，采用圖表示學(xué)習(xí)將節(jié)點(diǎn)向量化后，對(duì)相似子結(jié)構(gòu)的效率是有所提升的。

2 可視化系統(tǒng)設(shè)計(jì)

為便于用戶交互式地探索層次數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu)，基于層次結(jié)構(gòu)探索框架開發(fā)了原型系統(tǒng)，系統(tǒng)界面如圖3所示。系統(tǒng)主要分為三個(gè)模塊:(1)數(shù)據(jù)概覽模塊(A1、A2、A3)；(2)主視圖模塊(B1、B3)；(3)相似子結(jié)構(gòu)探索模塊(C1、C2、C3、C4)。

2.1 數(shù)據(jù)概覽模塊

數(shù)據(jù)概覽模塊主要目的是為用戶提供層次數(shù)據(jù)的概覽。其主要由向量聚類投影視圖(A1)、節(jié)點(diǎn)統(tǒng)計(jì)概覽視圖(A2)、度分布概覽視圖(A3)組成。

由于GraphWave算法生成的節(jié)點(diǎn)向量為高維向量，難以直接可視化呈現(xiàn)。為便于用戶更直觀地探索相似子結(jié)構(gòu)和對(duì)節(jié)點(diǎn)的整體特征進(jìn)行概覽，首先使用高斯混合模型將節(jié)點(diǎn)向量聚類得到各節(jié)點(diǎn)的聚類標(biāo)簽，然后通過(guò)T-SNE將各節(jié)點(diǎn)高維向量投影到二維平面，最后基于聚類標(biāo)簽對(duì)投影平面中的各節(jié)點(diǎn)進(jìn)行顏色編碼。在向量聚類投影視圖中用戶可通過(guò)點(diǎn)擊不同顏色的點(diǎn)，以查看相同顏色編碼的節(jié)點(diǎn)在節(jié)點(diǎn)連接視圖中的分布情況。

由于主視圖只是對(duì)層次結(jié)構(gòu)的呈現(xiàn)，對(duì)于如節(jié)點(diǎn)度值分布等信息無(wú)法很好地體現(xiàn)。因此,設(shè)計(jì)了兩個(gè)統(tǒng)計(jì)性的數(shù)據(jù)概覽視圖幫助用戶更好地了解數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu)信息。以堆疊柱狀圖(A2)的方式顯示了當(dāng)前系統(tǒng)所探索的層次結(jié)構(gòu)數(shù)據(jù)在總體上的層數(shù)、每層節(jié)點(diǎn)的數(shù)量、葉節(jié)點(diǎn)和非葉子節(jié)點(diǎn)在各層之間的占比。同時(shí),通過(guò)氣泡圖(A3)的形式來(lái)呈現(xiàn)每層節(jié)點(diǎn)的度值統(tǒng)計(jì)情況,氣泡的大小為度值相同的節(jié)點(diǎn)數(shù)量。這能幫助用戶直觀地了解當(dāng)前探索的層次數(shù)據(jù)各層節(jié)點(diǎn)孩子節(jié)點(diǎn)數(shù)的分布情況。

2.2 主視圖模塊

主視圖中的節(jié)點(diǎn)連接視圖(B1)為用戶探索層次結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)信息的主要視圖，在該視圖中，結(jié)合了節(jié)點(diǎn)重要性評(píng)估算法的評(píng)估結(jié)果，將對(duì)布局質(zhì)量影響較大的節(jié)點(diǎn)進(jìn)行隱藏。在其父節(jié)點(diǎn)處進(jìn)行視覺編碼(B2)以提示用戶該節(jié)點(diǎn)處存在隱藏的節(jié)點(diǎn)及其子結(jié)構(gòu)。橢圓的短軸表示其隱藏的子結(jié)構(gòu)的深度，長(zhǎng)軸表示隱藏子結(jié)構(gòu)所包含的節(jié)點(diǎn)數(shù)量。用戶可以通過(guò)點(diǎn)擊橢圓節(jié)點(diǎn)，展開隱藏的結(jié)構(gòu)。主視圖模塊中的關(guān)鍵子結(jié)構(gòu)如圖3 B3所示。用戶可以通過(guò)點(diǎn)擊相關(guān)子結(jié)構(gòu)，在節(jié)點(diǎn)連接視圖中將高亮顯示與關(guān)鍵子結(jié)構(gòu)匹配的結(jié)構(gòu)，若隱藏的結(jié)構(gòu)中包含與關(guān)鍵子結(jié)構(gòu)相匹配的結(jié)構(gòu),其對(duì)應(yīng)的視覺提示也將高亮顯示。

2.3 相似結(jié)構(gòu)探索模塊

相似結(jié)構(gòu)探索模塊主要由用戶焦點(diǎn)結(jié)構(gòu)(C2)、相似子結(jié)構(gòu)(C3)、結(jié)構(gòu)探索歷史(C4)組成。

用戶焦點(diǎn)結(jié)構(gòu)為用戶當(dāng)前點(diǎn)擊的關(guān)鍵子結(jié)構(gòu)或框選的子結(jié)構(gòu)。相似子結(jié)構(gòu)部分呈現(xiàn)相似子結(jié)構(gòu)匹配算法所提取的top-k個(gè)相似子結(jié)構(gòu)。結(jié)構(gòu)探索歷史則將用戶探索過(guò)的子結(jié)構(gòu)相關(guān)信息進(jìn)行保存，通過(guò)走馬燈效果來(lái)回切換用戶探索過(guò)的歷史子結(jié)構(gòu)。通過(guò)這樣的方式保證用戶能夠及時(shí)切換前后關(guān)注的結(jié)構(gòu)，從而對(duì)不同的子結(jié)構(gòu)進(jìn)行對(duì)比分析等。

同時(shí)，為便于用戶更好地探索數(shù)據(jù)，設(shè)計(jì)了如圖3 C1所示的控制面板。用戶可以通過(guò)控制面板來(lái)控制主視圖是否采用重要節(jié)點(diǎn)評(píng)估算法顯示優(yōu)化布局或者原始布局，這可幫助用戶對(duì)比采用重要節(jié)點(diǎn)算法前后差異。對(duì)于布局方式可選擇采用正交布局或者徑向布局。除此之外，用戶可使用框選工具在節(jié)點(diǎn)連接視圖中框選感興趣的子結(jié)構(gòu)。

3 實(shí) 驗(yàn)

為驗(yàn)證該方法在對(duì)層次數(shù)據(jù)結(jié)構(gòu)信息進(jìn)行探索的有效性，采用用戶評(píng)估以及案例研究來(lái)進(jìn)行證明。

3.1 用戶評(píng)估

實(shí)驗(yàn)?zāi)康模涸谖墨I(xiàn)[4]的研究中，證明了采用視覺提示的方式對(duì)于用戶探索具有良好的幫助。但未說(shuō)明是否只需部分的子結(jié)構(gòu)采用視覺提示，就能加快數(shù)據(jù)探索。為證明所采用的節(jié)點(diǎn)重要性評(píng)估方法的有效性，將與文獻(xiàn)[4]的Tree Cues方法進(jìn)行用戶對(duì)照實(shí)驗(yàn)。同時(shí)，為驗(yàn)證所提方法對(duì)于尋找相似子結(jié)構(gòu)在精確度、完成時(shí)間上的有效性，將與文獻(xiàn)[14]的BarcodeTree方法進(jìn)行用戶對(duì)照實(shí)驗(yàn)。

實(shí)驗(yàn)設(shè)計(jì)：用戶對(duì)照實(shí)驗(yàn)方法參考文獻(xiàn)[4,14]的方法進(jìn)行展開。在實(shí)驗(yàn)之前，招募了48位志愿者，這些志愿者的年齡分布為20到30歲。為避免志愿者在完成不同實(shí)驗(yàn)過(guò)程中對(duì)數(shù)據(jù)產(chǎn)生了一定的熟悉度，將這48位志愿者分成兩組來(lái)進(jìn)行規(guī)避。第一組志愿者完成文中方法與Tree Cues的對(duì)照實(shí)驗(yàn)A，第二組完成文中方法與文獻(xiàn)[14]的用戶對(duì)照實(shí)驗(yàn)B。對(duì)照實(shí)驗(yàn)A設(shè)計(jì)主要針對(duì)節(jié)點(diǎn)級(jí)別上的探索，其實(shí)驗(yàn)內(nèi)容參考文獻(xiàn)[4]中的實(shí)驗(yàn)任務(wù)進(jìn)行設(shè)計(jì)，以此保證在實(shí)驗(yàn)任務(wù)上的一致性。其任務(wù)詳細(xì)設(shè)計(jì)為：TA1 標(biāo)識(shí)層次結(jié)構(gòu)中第二層(根節(jié)點(diǎn)為第一層)直接子節(jié)點(diǎn)數(shù)量10以內(nèi)的節(jié)點(diǎn)。TA2 標(biāo)識(shí)層次結(jié)構(gòu)中第三層中直接子節(jié)點(diǎn)最多的節(jié)點(diǎn)。TA3 標(biāo)識(shí)層次結(jié)構(gòu)中第二層和第三層各10個(gè)直接子節(jié)點(diǎn)數(shù)量超過(guò)10個(gè)的節(jié)點(diǎn)。TA4 標(biāo)識(shí)第三層的所有葉節(jié)點(diǎn)。

對(duì)照實(shí)驗(yàn)B的實(shí)驗(yàn)任務(wù)設(shè)計(jì)以子結(jié)構(gòu)為主，其任務(wù)詳細(xì)設(shè)計(jì)為：TB1 標(biāo)識(shí)指定子結(jié)構(gòu)在第二層和第五層的位置及數(shù)量。TB2 標(biāo)識(shí)指定子結(jié)構(gòu)，在第二層及第四層最相似的子結(jié)構(gòu)。TB3 標(biāo)識(shí)指定子結(jié)構(gòu)，在第二層及第四層最相似的10個(gè)子結(jié)構(gòu)

實(shí)驗(yàn)過(guò)程：對(duì)于對(duì)照實(shí)驗(yàn)A和B，進(jìn)行重復(fù)方差分析，將a設(shè)置為0.05。實(shí)驗(yàn)A共進(jìn)行576次,實(shí)驗(yàn)B共進(jìn)行432次。在重復(fù)實(shí)驗(yàn)過(guò)程中，為避免用戶對(duì)實(shí)驗(yàn)數(shù)據(jù)的熟悉程度產(chǎn)生依賴，每隔三到四天做一次實(shí)驗(yàn)，同時(shí)將對(duì)數(shù)據(jù)中每一層節(jié)點(diǎn)的位置在該層進(jìn)行打亂布局順序，進(jìn)行重排。實(shí)驗(yàn)A中的每項(xiàng)任務(wù)都能獲取準(zhǔn)確值。因此，對(duì)于實(shí)驗(yàn)A，只收集用戶的完成時(shí)間。由于實(shí)驗(yàn)B中涉及尋找相似子結(jié)構(gòu)，用戶在尋找過(guò)程中是會(huì)存在錯(cuò)誤情況的。因此在對(duì)照實(shí)驗(yàn)B中收集完成時(shí)間和錯(cuò)誤率。

實(shí)驗(yàn)結(jié)果：圖4顯示了對(duì)照實(shí)驗(yàn)A完成實(shí)驗(yàn)的平均完成時(shí)間。表1中顯示了各項(xiàng)任務(wù)完成時(shí)間的顯著性檢驗(yàn)結(jié)果。從表1的結(jié)果顯示可知，在任務(wù)TA1、TA2、TA3的完成時(shí)間上，文中方法與文獻(xiàn)[4]的方法具有顯著性差異，說(shuō)明在這三類任務(wù)的完成時(shí)間上文中方法是優(yōu)于Tree Cues的。但對(duì)于類似任務(wù)TA4這種直接尋找葉節(jié)點(diǎn)，不需要其他額外的交互操作，兩種方法在完成時(shí)間上并沒(méi)有大的差異，也不具有顯著性差異。這表明，文中采用的基于節(jié)點(diǎn)重要性對(duì)部分子結(jié)構(gòu)采用視覺提示的方式，對(duì)于執(zhí)行類似TA1、TA2、TA3這些任務(wù)時(shí)相比于Tree Cues中只采用視覺提示的方法在完成時(shí)間上具有一定的優(yōu)勢(shì)。

對(duì)照實(shí)驗(yàn)B中采用文中方法與文獻(xiàn)[14]中方法完成各項(xiàng)任務(wù)的時(shí)間和錯(cuò)誤率，如圖4所示。表1顯示對(duì)照實(shí)驗(yàn)B中各項(xiàng)任務(wù)完成時(shí)間和錯(cuò)誤率的顯著性檢驗(yàn)結(jié)果。從表1可知，在對(duì)照實(shí)驗(yàn)B中，完成時(shí)間上文中方法與文獻(xiàn)[14]中的方法具有顯著性差異。在任務(wù)錯(cuò)誤率上，文中方法與文獻(xiàn)[14]中的方法在TB1任務(wù)上不具有顯著性差異，在TB2和TB3任務(wù)上具有顯著性差異。該結(jié)果表明，文中方法在完成類似實(shí)驗(yàn)B中的任務(wù)時(shí)，在完成時(shí)間上相對(duì)于文獻(xiàn)[14]中的方法更為高效。在完成任務(wù)錯(cuò)誤率上的表現(xiàn)除TB1外具有顯著差異。從對(duì)照實(shí)驗(yàn)B的結(jié)果可以得出，文中方法與文獻(xiàn)[14]中的方法在精確度和完成時(shí)間總體上具有一定的優(yōu)勢(shì)。

表1 對(duì)照實(shí)驗(yàn)

3.2 案例分析

該文設(shè)計(jì)了兩個(gè)案例來(lái)說(shuō)明該方法對(duì)于探索大型層次數(shù)據(jù)的有效性。

兩個(gè)案例所使用的數(shù)據(jù)分別來(lái)源于中國(guó)政府統(tǒng)計(jì)網(wǎng)2021年成都市統(tǒng)計(jì)用區(qū)劃和城鄉(xiāng)劃分代碼和食安通網(wǎng)站上的農(nóng)藥殘留限量數(shù)據(jù)。區(qū)劃和城鄉(xiāng)劃分代碼數(shù)據(jù)集是一個(gè)典型的層次數(shù)據(jù)集，詳細(xì)反映了一個(gè)區(qū)域的行政層級(jí)劃分情況。農(nóng)藥殘留限量數(shù)據(jù)收集了19版和14版的數(shù)據(jù)。兩個(gè)版本的層級(jí)劃分都是以各類食物的類別進(jìn)行詳細(xì)劃分，如水果類、蔬菜類等。

在兩項(xiàng)案例分析中，分別招募了一位對(duì)案例分析數(shù)據(jù)陌生的志愿者參與案例研究中，避免志愿者的先驗(yàn)知識(shí)對(duì)實(shí)驗(yàn)產(chǎn)生影響。

案例一:以成都市的區(qū)劃分代碼數(shù)據(jù)為例進(jìn)行案例分析。證明該系統(tǒng)能幫助用戶通過(guò)交互式的方式從未知的大型層次數(shù)據(jù)中獲取見解。

在對(duì)相似子結(jié)構(gòu)進(jìn)行探索的過(guò)程中，發(fā)現(xiàn)成都市的錦江區(qū)(圖5A)、成華區(qū)(圖5B)和青羊區(qū)(圖5C)的區(qū)劃分的局部結(jié)構(gòu)特征最為相似。同時(shí)這三個(gè)子結(jié)構(gòu)的向量投影聚類結(jié)果也屬于同一類簇。通過(guò)圖5中顯示可知，這三個(gè)區(qū)的子結(jié)構(gòu)中大多由4到8個(gè)節(jié)點(diǎn)構(gòu)成。通過(guò)這一現(xiàn)象說(shuō)明這三個(gè)區(qū)的區(qū)劃分具有一定的規(guī)律。查閱相關(guān)資料顯示，這三個(gè)城區(qū)都為成都市的中心城區(qū)中的第一圈層。這從側(cè)面反映了這三城區(qū)的區(qū)劃分可能與其所處的地理位置、經(jīng)濟(jì)、人口等有一定聯(lián)系。

除此之外，用戶通過(guò)探索關(guān)鍵子結(jié)構(gòu)時(shí)發(fā)現(xiàn)了部分生僻的子結(jié)構(gòu)，如圖6中的A、B兩類子結(jié)構(gòu)在整個(gè)結(jié)構(gòu)中遠(yuǎn)不如C這樣的結(jié)構(gòu)在整個(gè)區(qū)劃分?jǐn)?shù)據(jù)中分布的那么廣泛。尤其A類結(jié)構(gòu)的子節(jié)點(diǎn)數(shù)遠(yuǎn)多于B、C兩類結(jié)構(gòu)。為探知出現(xiàn)這一現(xiàn)象的原因，與用戶一起查閱了相關(guān)資料。資料顯示出現(xiàn)A類結(jié)構(gòu)的新都區(qū)其面積在成都市排名第三，這一數(shù)據(jù)間接反映出A類結(jié)構(gòu)的出現(xiàn)可能因其地理因素影響較大。出現(xiàn)B類結(jié)構(gòu)的城區(qū)為金牛區(qū)和武侯區(qū)作為一圈城的城區(qū)，出現(xiàn)該情況可能跟其他因素有關(guān)如人口等。

案例二:探索不同版本的層次數(shù)據(jù)之間的差異，可幫助用戶快速了解版本之間的演變過(guò)程，同時(shí)也能協(xié)助對(duì)錯(cuò)誤進(jìn)行追蹤[15]等。選擇19版和14版農(nóng)藥殘留限量數(shù)據(jù)證明該方法可用于輔助探索具有版本迭代地層次數(shù)據(jù)的結(jié)構(gòu)差異性。

為探索兩個(gè)版本之間的差異，志愿者首先對(duì)比兩版本的數(shù)據(jù)的概覽模塊。對(duì)比發(fā)現(xiàn)，在19版中第四層總的節(jié)點(diǎn)數(shù)由14版的170多增加到200。其增加節(jié)點(diǎn)類型以葉節(jié)點(diǎn)為主。這說(shuō)明，在19版本中引入了更多的測(cè)定對(duì)象。然后又進(jìn)行了關(guān)鍵子結(jié)構(gòu)對(duì)比，發(fā)現(xiàn)在兩個(gè)版本中，其關(guān)鍵子結(jié)構(gòu)的數(shù)量都為7種，但關(guān)鍵子結(jié)構(gòu)只有4個(gè)保持完全相同(見圖7)。志愿者接著對(duì)比了關(guān)鍵子結(jié)構(gòu)在原始布局上的整體分布。在對(duì)比的過(guò)程中發(fā)現(xiàn)，19版的第四層節(jié)點(diǎn)中刪除了部分14版中的葉節(jié)點(diǎn)，如在谷物這一大類下19版刪除了14版中的一個(gè)葉節(jié)點(diǎn)(其他麥類)。這一細(xì)微差異相對(duì)于結(jié)構(gòu)差異變化明顯的來(lái)說(shuō)是很難發(fā)現(xiàn)的(如油料油脂分類的子類在19版由四大分類變?yōu)閮纱蠓诸?。除對(duì)比兩個(gè)相同子結(jié)構(gòu)在整體上的分布外，志愿者在對(duì)比兩個(gè)相似的子結(jié)構(gòu)時(shí)，同樣發(fā)現(xiàn)了類似上述的差異情況。

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

與現(xiàn)有的方法相比，提出采用重要節(jié)點(diǎn)評(píng)估算法來(lái)評(píng)估節(jié)點(diǎn)的重要性，根據(jù)重要性來(lái)決定需視覺編碼的節(jié)點(diǎn)，這能保留更多的拓?fù)浣Y(jié)構(gòu)信息避免過(guò)多的結(jié)構(gòu)信息被視覺編碼隱藏，從而提高了探索效率。同時(shí)，采用提取關(guān)鍵子結(jié)構(gòu)對(duì)層次結(jié)構(gòu)的拓?fù)涮卣鬟M(jìn)行概括和圖嵌入算法對(duì)節(jié)點(diǎn)進(jìn)行向量化方法相結(jié)合，提升了用戶探索拓?fù)浣Y(jié)構(gòu)信息的效率與準(zhǔn)確率。實(shí)驗(yàn)案例研究表明，該方法不僅支持單一層次結(jié)構(gòu)數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu)信息探索，還適用于具有版本迭代的層次結(jié)構(gòu)信息的對(duì)比分析。

由于層次數(shù)據(jù)不僅蘊(yùn)含著結(jié)構(gòu)信息，同時(shí)各節(jié)點(diǎn)中具有屬性信息，在未來(lái)的工作中將研究或提出一種合理的方法將屬性信息加入當(dāng)前探索框架中，來(lái)幫助用戶更全面地探索層次數(shù)據(jù)中的結(jié)構(gòu)信息和屬性信息。