面向拓撲感知的層次結構信息可視探索方法

譚博友，韓永國，王桂娟，趙韋鑫，周 銳，蔡夢杰，吳亞東

(1.西南科技大學 計算機科學與技術學院，四川 綿陽 621000；2.四川輕化工大學 計算科學與工程學院，四川 自貢 643000)

0 引 言

層次結構數據不僅常見于文件系統、動植物分類、系譜圖等領域，還能將復雜領域通過層次結構的形式進行簡化表示[1]。層次數據的拓撲結構，能直觀地反映某一事物的分類特征，幫助數據分析人員探尋結構信息并理解層次數據的分類模式等。因此，探索層次數據的拓撲結構信息是層次數據分析的一項重要環節。

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

基于以上問題，該文提出了一個面向拓撲感知的層次結構信息探索框架。該框架通過評估重要節點來解決無興趣度標記時分支隱藏的問題并保留更多的結構信息。通過提取關鍵子結構對整體層次結構進行概要，同時引入圖嵌入算法對結構進行向量化來提高用戶探索子結構和相似子結構的效率。最后，基于該框架實現了一個交互式的可視探索系統,通過案例分析和用戶實驗來驗證該方法的有效性。

1 層次拓撲結構信息計算

層次結構信息計算主要由三大模塊組成，分別為重要節點評估模塊、關鍵子結構提取模塊、相似子結構提取模塊。

1.1 重要節點評估

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

A:原始布局 B:度指標評估算法結果 C:合度算法結果 D:DN算法結果

通過以上實驗結果，該文采用DN評估算法來對層次數據的節點的重要性進行評估。由于不同數據的節點數量不一樣，其所要收縮隱藏的節點數是不確定的，因此，在實際應用中基于DN算法進行了擴展。以此適應不同的節點數量的層次數據。其算法主要流程為:

Step1：根據DN算法計算各節點重要度;

Step2：根據重要度排序,取Top-k節點,k默認取10;

Step3：將這些重要節點及其子節點進行隱藏，保存這些重要節點；

Step4：通過布局算法計算各節點位置;

Step5：當前兄弟節點之間圓心距離減去一個直徑后是否小于閾值n,是則將當前繪制出的所有節點重復Step1～Step4;

Step6：輸出重要節點序列。

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

1.2 關鍵子結構提取

Ben Shneiderman曾提出“Overview first, zoom and filter, then detail on demand”的標準分析流程[7]。該流程指出在可視分析中概覽屬于第一步。因此，要更好地對層次數據的拓撲結構進行探索分析，需提供關于結構的概覽。基于TF-IDF算法提取文本關鍵詞的思想，該文通過提取關鍵子結構來高度概括整體層次結構。

在提取關鍵子結構之前，首先要解決子結構的定義問題，定義一種類似于文本中的詞的子結構，這樣才能更好地提取關鍵子結構。

在層次結構中，其最小單元為節點，但一個節點并不能算是一個拓撲結構，一個拓撲結構至少應包含邊。因此，定義的子結構應由節點和邊組成。在層次結構中，由邊和節點組成的最小單元為父子節點連接而成的結構。因此，為便于對整個層次結構進行分解，對子結構定義如下：非葉子節點和其直接相連的節點構成一個子結構(如圖2中A區域所示)。

由于TF-IDF算法由詞頻TF和逆文檔頻率指數IDF兩部分組成，因此要提取關鍵子結構，首先需計算TF和IDF值。計算TF值相當于計算子結構的頻率。由于文本中計算IDF時通常需要文檔庫，因此計算層次結構的IDF時也需要類似于文檔庫的東西。但是層次結構數據往往是一個整體，如果直接將整體作為一個文檔計算IDF將得到0值。因此，在計算IDF值時應定義層次結構的文檔庫。

該文采用以下方法定義層次結構的文檔庫。首先，假設根節點直接相連的節點有多個，這時刪除根節點，可得到多個如圖2中B區域A、B、C所示的子結構。將圖2B區域A、B、C這樣的子結構單獨作為一個層次結構數據，那么A、B、C就可以構成當前層次結構的文檔庫。

根據以上定義，列出如下TF和IDF計算公式:

(1)

(2)

公式(1)中，Cij表示子結構i在結構文檔j中出現的次數，分母表示結構文檔j中k個子結構出現次數和。公式(2)中，T表示結構文檔總數,分母表示j結構文檔中子結構i出現在所有結構文檔中的次數。tfij與idfi的乘積代表j結構文檔中i子結構的tf-idf值。然后將各結構文檔中的各子結構的tf-idf值進行降序排序，取前n個作為該結構文檔中的關鍵子結構。最后將所有結構文檔的關鍵子結構進行匯總去重后，剩余的子結構作為整個層次結構的關鍵子結構。

1.3 相似子結構提取

相似子結構是對整體結構的一種過濾，能幫助用戶快速定位與用戶焦點子結構相似的結構特征。

相似子結構的匹配實際為對相似子圖挖掘。現有的許多工作總結了近年來的子圖挖掘相關算法，如VF2plus[8]、VF3[9]等。這些算法雖然能夠得到完全匹配的子圖，但在匹配的過程中存在會匹配大量不符合的結構導致大量的運算時間消耗。

筆者希望用戶在使用該可視探索系統時能在較短的交互時間內獲取結果，若采用VF3等算法，將導致在探索的過程中浪費用戶大量的時間而影響交互體驗。潘嘉鋮[10]和李珍[11]等人的研究表明，通過表示學習將網絡中的節點進行向量化，能減少無關的子結構的匹配次數，極大地提高相似子結構的提取效率，同時生成的節點向量更能體現“鄰居緊密性”。因此，該文采用表示學習的方法對層次結構的節點進行向量化。

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

為保證提取出來的相似子結構的準確性，采取以下步驟提取相似子結構：

Step1：對向量化后的節點使用高斯混合聚類模型進行聚類，目的是將相似的節點聚集到同一類簇，在相同聚類簇中的節點所構成的子結構的相似性也更接近。

Step2：將用戶當前所選子結構的節點向量所屬的所有聚類簇中的所有節點作為相似子結構匹配候選集。

Step3：剔除用戶所選子結構上的節點，在剩余的節點集中構建子結構集合。由于構建出的子結構存在其節點數量遠小于或者遠大于用戶所選子結構節點數量的問題，因此將該部分結構刪除，得到候選的相似子結構集合。

Step4：采用Weisfeiler-Lehman圖核[13]對候選相似子結構集合中的子結構分別與用戶所選的子結構進行相似度分數計算，相似度分數越高的子結構其相似度越高。按相似度分數降序排序，取前k(默認k=6)個相似子結構呈現在相似子結構查看面板中。

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

2 可視化系統設計

為便于用戶交互式地探索層次數據的拓撲結構，基于層次結構探索框架開發了原型系統，系統界面如圖3所示。系統主要分為三個模塊:(1)數據概覽模塊(A1、A2、A3)；(2)主視圖模塊(B1、B3)；(3)相似子結構探索模塊(C1、C2、C3、C4)。

2.1 數據概覽模塊

數據概覽模塊主要目的是為用戶提供層次數據的概覽。其主要由向量聚類投影視圖(A1)、節點統計概覽視圖(A2)、度分布概覽視圖(A3)組成。

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

由于主視圖只是對層次結構的呈現，對于如節點度值分布等信息無法很好地體現。因此,設計了兩個統計性的數據概覽視圖幫助用戶更好地了解數據的拓撲結構信息。以堆疊柱狀圖(A2)的方式顯示了當前系統所探索的層次結構數據在總體上的層數、每層節點的數量、葉節點和非葉子節點在各層之間的占比。同時,通過氣泡圖(A3)的形式來呈現每層節點的度值統計情況,氣泡的大小為度值相同的節點數量。這能幫助用戶直觀地了解當前探索的層次數據各層節點孩子節點數的分布情況。

2.2 主視圖模塊

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

2.3 相似結構探索模塊

相似結構探索模塊主要由用戶焦點結構(C2)、相似子結構(C3)、結構探索歷史(C4)組成。

用戶焦點結構為用戶當前點擊的關鍵子結構或框選的子結構。相似子結構部分呈現相似子結構匹配算法所提取的top-k個相似子結構。結構探索歷史則將用戶探索過的子結構相關信息進行保存，通過走馬燈效果來回切換用戶探索過的歷史子結構。通過這樣的方式保證用戶能夠及時切換前后關注的結構，從而對不同的子結構進行對比分析等。

同時，為便于用戶更好地探索數據，設計了如圖3 C1所示的控制面板。用戶可以通過控制面板來控制主視圖是否采用重要節點評估算法顯示優化布局或者原始布局，這可幫助用戶對比采用重要節點算法前后差異。對于布局方式可選擇采用正交布局或者徑向布局。除此之外，用戶可使用框選工具在節點連接視圖中框選感興趣的子結構。

3 實 驗

為驗證該方法在對層次數據結構信息進行探索的有效性，采用用戶評估以及案例研究來進行證明。

3.1 用戶評估

實驗目的：在文獻[4]的研究中，證明了采用視覺提示的方式對于用戶探索具有良好的幫助。但未說明是否只需部分的子結構采用視覺提示，就能加快數據探索。為證明所采用的節點重要性評估方法的有效性，將與文獻[4]的Tree Cues方法進行用戶對照實驗。同時，為驗證所提方法對于尋找相似子結構在精確度、完成時間上的有效性，將與文獻[14]的BarcodeTree方法進行用戶對照實驗。

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

對照實驗B的實驗任務設計以子結構為主，其任務詳細設計為：TB1 標識指定子結構在第二層和第五層的位置及數量。TB2 標識指定子結構，在第二層及第四層最相似的子結構。TB3 標識指定子結構，在第二層及第四層最相似的10個子結構

實驗過程：對于對照實驗A和B，進行重復方差分析，將a設置為0.05。實驗A共進行576次,實驗B共進行432次。在重復實驗過程中，為避免用戶對實驗數據的熟悉程度產生依賴，每隔三到四天做一次實驗，同時將對數據中每一層節點的位置在該層進行打亂布局順序，進行重排。實驗A中的每項任務都能獲取準確值。因此，對于實驗A，只收集用戶的完成時間。由于實驗B中涉及尋找相似子結構，用戶在尋找過程中是會存在錯誤情況的。因此在對照實驗B中收集完成時間和錯誤率。

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

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

表1 對照實驗

3.2 案例分析

該文設計了兩個案例來說明該方法對于探索大型層次數據的有效性。

兩個案例所使用的數據分別來源于中國政府統計網2021年成都市統計用區劃和城鄉劃分代碼和食安通網站上的農藥殘留限量數據。區劃和城鄉劃分代碼數據集是一個典型的層次數據集，詳細反映了一個區域的行政層級劃分情況。農藥殘留限量數據收集了19版和14版的數據。兩個版本的層級劃分都是以各類食物的類別進行詳細劃分，如水果類、蔬菜類等。

在兩項案例分析中，分別招募了一位對案例分析數據陌生的志愿者參與案例研究中，避免志愿者的先驗知識對實驗產生影響。

案例一:以成都市的區劃分代碼數據為例進行案例分析。證明該系統能幫助用戶通過交互式的方式從未知的大型層次數據中獲取見解。

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

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

案例二:探索不同版本的層次數據之間的差異，可幫助用戶快速了解版本之間的演變過程，同時也能協助對錯誤進行追蹤[15]等。選擇19版和14版農藥殘留限量數據證明該方法可用于輔助探索具有版本迭代地層次數據的結構差異性。

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

4 結束語

與現有的方法相比，提出采用重要節點評估算法來評估節點的重要性，根據重要性來決定需視覺編碼的節點，這能保留更多的拓撲結構信息避免過多的結構信息被視覺編碼隱藏，從而提高了探索效率。同時，采用提取關鍵子結構對層次結構的拓撲特征進行概括和圖嵌入算法對節點進行向量化方法相結合，提升了用戶探索拓撲結構信息的效率與準確率。實驗案例研究表明，該方法不僅支持單一層次結構數據的拓撲結構信息探索，還適用于具有版本迭代的層次結構信息的對比分析。

由于層次數據不僅蘊含著結構信息，同時各節點中具有屬性信息，在未來的工作中將研究或提出一種合理的方法將屬性信息加入當前探索框架中，來幫助用戶更全面地探索層次數據中的結構信息和屬性信息。