層次數據可視化主講人：劉天亮liutl@

TEL京郵電大學圖像處理與圖像通信江蘇省重點實驗室提綱層次數據層次數據的可視化節點鏈接法及其應用空間填充法及其應用混合型層次數據

(HierarchicalData)層次數據（樹結構）層次數據著重表現個體之間的隸屬關系社會、自然界中的從屬關系機構的組織結構，

物種關系信息的組織形式文件列表邏輯承接關系決策樹我們通過分類來理解事物，層次結構是我們認知行為的基礎——PeterMorville為什么要層次結構？層次結構是復雜系統中有效的管理組織形式，以及穩定、可持續的發展機制"TheArchitectureofComplexity:HierarchicSystems"

社會系統

生物和物理系統

符號系統層次結構中

個體元素的相對獨立性層級結構中的個體元素

相關的子系統(interrelatedsubsystems)

相對獨立(semi-independent)子系統之間的關系

影響往往是通過子系統之間的功能(輸入、輸出）

和一個子系統內部實現其功能的具體方式無關可拆分(decomposability)或準可拆分(neardecomposability/2011/06/27/organizational-charts/公司組織結構圖六大計算機公司的組織結構圖，生動地反映了獨特的企業文化：亞馬遜有嚴格的等級制度；谷歌也有清晰等級，但部門之間相互交錯，由google的三駕馬車CEO埃里克·施密特（EricSchmidt）、Google聯合創始人拉里·佩奇（LarryPage）和塞吉·布林（SergeyBrin）共同領導；Facebook像一張分布式網絡；微軟各自占山為王，且相互競爭，但其實應該更接近于Apple的情況，即以扎克伯格為核心；蘋果是各小團隊相互平等靈活作戰，但喬布斯的作用非常明顯；甲骨文法務部門遠大于工程部門國內公司結構圖1.騰訊，產品與部門關系千絲萬縷，QQ是所有產品與服務的基石。2.百度崇尚簡單；3.華為，技術創新引發矩陣結構變化；4.阿里巴巴，馬云的影子無時無處不在；5.360掐架大王，總要有人在后面擦屁股家譜樹希臘神話中眾神的家譜（局部），其中字母F表示一個由父母（在字母F之上的黑色圓點）和子女（在字母F之下的黑色圓點）組成的家庭。A.Bezerianos,P.Dragicevic,J.-D.Fekete,J.Bae,B.Watson.GeneaQuilts:ASystemforExploringLargeGenealogiesGeneaQuilts家譜樹物種發展這棵樹清晰地呈現了不同物種之間的遺傳關系，所有物種通過生物發展史的基因鏈接關系相連。本數據包含93891個物種，占今天地球上的1億物種的極小部分。根節點"LifeonEarth''(紅色字體)被置于樹的西南角，它的西南方向鏈接了``Greenplants''（綠色植物，綠色）分支，東南方向鏈接了''Protista''（原生動物，淡紅色）分支，西北方向鏈接的是''Fungi''（菌類，黃色）分支。數據來源：/tree/圖片來源：/~yifanhu/TOL/思維導圖層次數據的表達:圖結構圖G由一個頂點（或節點）集合V和一個邊集合E組成

G={V,E}每條邊exy=(x,y)連接圖G的兩個頂點x,y例如：V={1,2,3,4},E={(1,2),(1,3),(2,3),(3,4),(4,1)}顯然，這種表達對于非專業人士來說，還是比較難懂的層次數據的圖形化表達G={V,E}V={1,2,3,4},E={(1,2),(1,3),(2,3),(3,4),(4,1)}圖的結構表達無向圖;(b)加權圖;(c)不連通圖;(d)頂點的度;(e)回路;(f)無回路圖;(g)有根結點的層次樹;(h)結點深度圖的結構表達圖的結構表達樹形結構和網絡結構是層次和網絡數據可視化的基本型邊的方向和權重，是可視編碼的重要組成部分結點的度、平面性、連通性，是圖結構的基本性質，對樹、網絡的挖掘至關重要但對于大的層級結構來說，

圖形化的展示面臨一些挑戰物種發展數據來源：/tree/圖片來源：/~yifanhu/TOL/主要的挑戰把節點和邊信息展示出來

點和邊的空間排布組織形式允許用戶對層次數據進行交互式分析探索

對層次數據的相關部分進行觀察分析

展示：合理的利用顯示空間交互：和任務相關的功能工具

微觀細節和

宏觀背景

對子系統進行匯總、比較不同的子系統等層次數據的可視化層次數據的展現方式按數據的理解方式不同，層次數據的構建分：自上而下和自下而上層次數據可視化的核心：1、如何表達層次關系的樹形結構2、如何表達樹形結構中的父結點和子結點3、如何表現父子結點、具有相同父結點的兄弟結點之間的關系等層次數據的展現方式

按布局策略，主流方法可分為：節點鏈接法：結構清晰型表達(structure-clarity)節點鏈接樹雙曲樹三維樹空間填充法：空間利用率高(space-efficiency)樹圖(Treemap)Voronoi樹圖混合型：利用上述兩種方法的互補性，彈性層次圖為代表Jürgensmann和Schulz對樹結構可視化技術進行了總結和分類，并制作了海報。他們采用的分類思路與上面介紹的基本一致：顯性，隱性與混合三種。顯性方法基本等同于節點鏈接法，而隱性方法則對應空間填充法。在此基礎上，根據空間維度（二維或三維）及布局方法（正交、徑向、自由布局）做了更進一步分類。這樣的層層分類本身也是一個層次結構，可采用空間填充方法進行可視化。

作品贏得了2010年IEEEInfoVis會議的最佳海報獎，其后又演化成在線互動版()Jürgensmann和Schulz對樹結構可視化技術進行了總結和分類，并制作了海報以及在線東臺書可視化檢索系統。

圖8.2層次數據可視化分類。

分類延續了結點鏈接、空間填充和混合型的思路，分界線的粗細表達了層次的深度。8.1.1節點鏈接法節點鏈接法是圖論中樹形的擴展，可視化繪制的核心是結點和邊的位置編碼和視覺符號編碼。為了達到結點鏈接法實用性和美觀性，繪圖算法設計往往需遵循一些原則：盡量避免邊的交叉。邊的教材可能會導致對圖的錯誤理解。結點和邊盡量均勻分布在整個布局界面上。邊的長度統一可視化效果整體對稱，保持一定的比例網絡中相似的子結構的可視化效果相似實際設計中，并不一定能完全滿足所有的原則，設置原則之間會產生矛盾，需要平衡和取舍，因此將產生對各原則有不同側重的布局根據節點與鏈接的布局策略，

可以細分為如下三種正交布局（網格型布局）縮進圖(indent)聚類樹(dendrogram)冰柱圖(icicle)徑向布局（輻射型）徑向布局圖雙曲樹三維布局dendrogram徑向布局正交布局節點在放置的時候，都按照水平或垂直對齊方向與坐標軸一致的，布局規則與視覺識別習慣吻合，非常直觀缺點對于大型的層次結構，特別是廣度比較大的層次結構，這樣的布局會導致不合理的長寬比、布局不均勻分布和較大空間浪費電路圖正交且空間高效?對機器友好，對用戶不友好電磁爐的電路圖縮進圖快速并易于實現可以使用純文本（或HTML）瀏覽大數據時需要很多滾動操作容易失去上下文(context)Flare軟件包的子目錄結構/jheer/files/zoo//?p=951美國鐵路的兼并聚類圖美國曾經也是個大量依賴鐵路貨運的國家。貨運公司遍布全國。但是近50年來，這些公司互相兼并。上面的可視化來自財富雜志的美術總監NicolasRapp的文章TheBattleofTheRails。他用這樣一個類似樹狀的結構很清晰的展示了鐵路公司兼并的歷史。在80年代，這許多公司在大量的兼并之后，只剩下屈指可數的7家。而現在上圖中用紅線標出區區四家占了全國鐵路貨運的九成。印歐語系冰柱圖常用于聚類分析，展現層次聚類結果/jheer/files/zoo/ex/hierarchies/icicle.png正交樹圖的一般實現?簡單的遞歸實現–根據樹的深度將空間沿縱軸平均分成等高的區域。每個區域對應樹的一層。樹中相同深度的節點屬于同一層。–根據葉節點的數量,將對應的區域沿橫軸平均分成等寬的區域。–將節點布置在每個區域的中心。–在節點和它的父節點之間連線。Reingold-Tilford樹算法?標準：–所有節點按照在樹中的層次進行分層繪制–避免邊相交–相似的子樹用相似（或鏡像）進行表達–表達緊湊?基本方法：–自底向上遞歸計算–對于每個父節點，確保子樹已完全繪制–盡可能緊致地包裝子樹–將父節點放在子樹的中心位置尤其注重布局的對稱性和緊湊性Reingold-Tilford樹算法?自底向上遞歸計算：–對樹進行后序遍歷?這樣對于父節點，在遍歷到的時候可以確保其左右子樹都已經布局完畢。?對于每個父節點，確保子樹已完全繪制–通過這樣的繪制順序可以保證結構相同的子樹擁有相同的表示——因為每個子樹的繪制過程都不會受到子樹外元素的影響。Reingold-Tilford樹算法?盡可能緊致地包裝子樹–對于每一個節點，計算其左子樹的右輪廓與右子樹的左輪廓，并調整左右子樹的位置直至兩者剛好錯開一個預先設定的閾值r為止。?隨后將父節點放在左右子樹的中心位置?可以推廣至多叉樹徑向布局

更加合理地利用空間 根節點位于圓心，不同層次的節點被放置在半徑不同的同心圓上

節點到圓心的距離對應于它的深度 滿足樹結構節點數量隨層次而增加的特點Radial/demo徑向布局Flare軟件包的目錄結構/jheer/files/zoo/三維樹(Cone-Tree)GeorgeRobertson,

JockD.Mackinlay,

StuartCard.ConeTrees:Animated3DVisualizationsofHierarchicalInformation.In

ProceedingsoftheACMCHI91HumanFactorsinComputingSystemsConference,pages189--194,April28-June5,1991,NewOrleans,Louisiana,June1991.AssociationforComputingMachinery三維樹(Cone-Tree)三維空間，結合二維投影優點

三維空間來擴展可用顯示空間

三維動畫來降低認知成本缺點

難以對付很大的樹

三維交互還是一個挑戰雙曲樹排布

將節點在雙曲空間分布（節點數仍然隨深度曾幾何級數增長！）雙曲樹排布利用對二維空間的非線性映射來有效地利用空間優點

很酷

在局部細節和宏觀結構的平衡缺點

操控不是很容易，非線性映射使得準確控制節點的空間位置變得困難節點鏈圖的問題節點數隨著深度增加呈幾何級數增長解決方案——交互使用變形對節點進行匯總、過濾魚眼變形DOI樹（節點過濾）DOI:DegreeofInterestSpaceTree(Grosjea,etal.,2002)樹的展示根據用戶的需求進行動態的調整支持實時的查找并根據查找來調整樹的展示8.1.2空間嵌套填充法一種基于區域的可視化方法，直接采用顯示空間中的分塊區域表示數據中的個體。三個可計算的評價指標：可讀性、距離相關性、穩定性包含/被包含關系Enclosure

為了表達節點的父-子關系，將子節點整個封裝在父節點中樹圖(Treemaps)Johnson和Shneiderman在1991年提出 假設每個葉節點具有一個“尺寸”屬性（例如磁盤中的文件，或者機構圖中的薪水等）

父節點的尺寸是所有子節點尺寸之和例：磁盤瀏覽類別數據的樹圖

倫敦個人房產交易數據的樹圖可視化類別數據的層次類別數據本身沒有層次關系類別的層次安排對結果影響很大把類別對數據的影響程度作為層次房產數據地區：鬧市、郊區房子類型：別墅、商品房周邊環境利用樹圖的幾個原則層次數據層次之間的關系比較清晰、容易理解每個子系統有一個統一的數字化度量

文件尺寸、股票價格等最好允許用戶控制樹圖中元素的展示粒度層次上行/下行樹圖的一個問題逐級縱橫切割細分會產生狹長的四邊形難以與內部節點交互交替縱橫切分法嚴格的正等分法Voronoi樹圖Voronoi樹圖

采用凸多邊形代替矩形，同時解決圓填充圖中利用率不高和經典樹圖算法的長寬比等問題Voronoi樹圖Squarified樹圖原始樹圖

(slice-and-dice)BalzerM,DeussenO.VoronoiTreemaps美國家庭消費結構可視化/interactive/2008/05/03/business/20080403_SPENDING_GRAPHIC.html混合型彈性層次圖ZhaoS,McGuffinM

J,ChignellM

H.Elastichierarchies:combiningtreemapsandnode-linkdiagrams彈性層次圖文件系統瀏覽器

(FileSystemNavigator,FSN)混合法在三位中的應用—節點和連線來表示目錄之間的關系—文件和目錄(最后一級)用空間填充法其他方法可縮放交互空間(zoomableuserin