[發明專利]一種基于HCT圖的層次數據對比可視分析方法

有效

• 申請號: 201810243279.4
• 申請日: 2018-03-23
• 公開（公告）號: CN108427765B
• 公開（公告）日: 2020-06-12
• 發明（設計）人: 陳誼;李玥;章蓉
• 申請（專利權）人: 北京工商大學
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/26
• 代理公司: 北京萬象新悅知識產權代理有限公司 11360
• 代理人: 黃鳳茹

本發明公布了一種基于可重疊圓形樹圖(HCT圖)的層次數據比較可視化分析方法，通過HCT圖可直觀展示節點屬性差異與結構差異；包括：通過算法生成一棵特定的集合樹，實現HCT圖的排布算法用于映射集合樹中的節點關系，使用區域比例縮放HCT圖中兩樹的差異部分。本發明通過由節點的子集分布狀態決定該節點的形狀，提高了辨識度；采用貪心的子集元素排布策略，保證了空間利用率；在集合樹可視化映射上擴展了傳統圓形樹圖，不僅能表達節點間包含關系還可以表現兩個子集的差異，用于反映兩棵樹節點之間的差異性，且可以控制不同區域之間的比例系數來達到對兩棵樹之間共性部分或差異性部分突出展示的效果。

技術領域

本發明涉及信息可視化、樹比較、排布算法領域，具體涉及一種層次數據對比可視分析的可重疊圓形樹圖(HyperCircularTreemap，HCT圖)及基于HCT圖的層次數據對比可視分析方法。

背景技術

層次結構(也稱為：樹結構)的數據在生活工作中極其常見，比如文件組織結構、生物進化樹、家譜樹等，因此層次數據的差異性比較成文了一項十分重要的任務。目前，層次結構比較方法(樹比較方法)在各個領域得到了廣泛應用，例如通過比較層次模型的差異優化模型；分析不同時間層次結構的變化；對層次異構數據尋找最優匹配；分析代碼演變過程等等。

樹可視化可以分為兩類：節點鏈接法和空間填充法。樹比較可視化方法是由樹可視化方法演變而來，一般樹比較可視化方法則是通過組合、連接、變形樹可視化中的基本圖元達到展示的效果。綜合來講，樹比較可視化有三種展示方法：(1)并置；(2)合并；(3)動畫。并置的方法一般基于點線連接形式的樹可視化，將兩棵樹并列放置并對相應的節點加入顏色映射等加以區分，直觀但是對空間的利用率不足；合并的方法是首先將兩棵樹組合成一顆集合樹，由于在集合樹上可以體現元素之間的對比關系，因此可以將樹比較任務變為樹可視化任務。一般通過空間填充的方式直接展示集合樹，具有較高的空間利用率但并不直觀；動畫則一般用于展示具有時變特征的層次數據的變化趨勢。

在使用合并的方式進行樹比較時，樹圖(Treemap)由于其可以充分利用空間展示節點屬性的特點成為了最有效的空間填充式樹可視化方法之一，也成為了樹比較可視化方法的首選。然而,在樹比較任務中除了需要可視化節點屬性差異之外仍然有額外的需求：可視化結構差異。一般樹圖在結構展示上具有明顯劣勢，而圓形樹圖(CircularTreemap)作為一種用圓形代表樹節點的特殊樹圖可以更直觀的辨識樹的結構但是極大的犧牲了空間利用率。圓形樹圖可以看作是一種特殊的韋恩圖，其特殊性體現在圖中元素只用于描述集合的包含關系。在樹可視化過程中，由于層次數據只具有包含關系因此使用圓形樹圖具有很好的可視化效果；然而在樹比較可視化中，兩棵樹之間結構的差異度可以用兩棵樹中同名節點的子節點集合之間的關系來表示(A與B的差集、B與A的差集、A與B的交集)，用一般的圓形樹圖無法直觀展示。

綜上所述，現有的基于合并方式的樹比較可視化方法存在無法在可視化節點屬性差異的同時體現結構差異的問題，難以直觀展示兩棵樹中的差異部分，對層次數據進行對比分析的效果不佳。

發明內容

為了克服現有技術的不足，本發明提供一種基于可重疊圓形樹圖(HyperCircularTreemap，HCT圖)的層次數據比較可視化分析方法，通過HCT圖可直觀展示節點屬性差異與結構差異；與圓形樹圖相比，樹節點之間具有較高的區分度用于展示結構差異；在排布上更加節省顯示空間；能夠實現對不同層次數據之間共性部分或差異性部分的突出展示。