基于樹圖的大規模數據集合

0可視化樹圖的應用1991年5月，美國密歇根大學的虛擬機專家貝塞爾姆提出了一種新方法來表示大數據集。這種方法采用基于二維空間填充的技術將顯示空間劃分為許多具有一定大小的矩形來可視化層次數據集合,充分利用了顯示空間的每一個象素。由于樹圖可用各個矩形的大小來表示數據元素的某一屬性,非常適合數據集合很大的情況。樹圖現在已經應用在很多領域的可視化中。1992年,德國的AlexanderJungmeiseter使用樹圖可視化了一個銷售公司的管理結構,這個應用程序可以顯示客戶、管理人員、工業部門和市場的層次結構。2001年,微軟研究小組的MarcSmith將樹圖使用在Netscan項目中用于可視化Usenet,網上最大的虛擬社會之一;微軟公司還在它的.NET開發環境中加入了樹圖組件。2003年,IBM公司也開始使用樹圖來可視化它的網絡管理系統。目前針對樹圖的研究主要集中在國外,國內幾乎沒有涉及樹圖的研究。研究樹圖主要集中在如何直觀地顯示層次結構和優化矩形長寬比這兩個方面,由于研究起步晚,方法還不夠全面,因此樹圖有進一步改進的潛力和可能。1樹圖的應用研究對于一個具有層次結構的數據集合,圖1顯示了用傳統的節點連接圖和樹圖來可視化同一個層次數據集合的結果。樹圖的生成過程如下:整個顯示空間,即初始矩形,被用來表示整個數據集合(等同于節點-連接圖中的根結點A16)。然后,根據下一層的數據元素B3、C3和D10的大小,縱切初始矩形,切出的三個矩形分別對應B3、C3和D10,并且它們的面積比例和它們對應數據元素的大小比例相同。然后如此遞歸,每次遞歸都改變切割的縱橫方向,一直切到葉子節點為止。這也就是最簡單的Slice-and-Dice算法。在數據規模比較大的時候,樹圖更能體現它相比傳統方法的優越性。圖2顯示了一個磁盤上文件系統的總體情況。這個文件系統上一共有1400多個文件,而用樹圖可以毫不費力的將他們顯示出來,這是任何傳統可視化方法都無法做到的。用戶還可以直觀的從整張圖上看出哪個文件最大,消耗了磁盤的空間等等。通過點擊方塊可以獲得對應文件的詳細信息。雖然樹圖在可視化大規模層次數據集合方面有節省空間的優勢,但從圖2中我們也不難看出,樹圖存在前文中提到的兩個明顯的缺陷:層次結構不夠直觀和生成矩形長寬比過大。因此針對樹圖的理論研究主要集中在改進樹圖的兩個缺陷上。近十年來,可視化的研究者們提出了多種樹圖生成算法,其中有改進樹圖層次結構顯示的Cushion算法,改進樹圖矩形長寬比的正方化算法,以及針對正方化算法亂序的缺陷提出的Pivot算法和Strip算法。下面介紹和比較這幾種樹圖生成算法。1.1cup實現樹圖的層次結構從圖2中可以很直觀地看到一個磁盤上文件大小的總體信息。然而,磁盤上的文件是個典型的樹型結構,每一層的文件就像葉子結點,而文件夾像中間接點。從這個樹圖上雖然可以清楚的看出葉子結點大小比例關系,但是其中a文件和b文件是同一目錄下的嗎?c文件是不是d文件上層目錄的?這些層次信息在樹圖中體現的很不明顯,不符合可視化的原則。Eindhoven大學的JarkeJ.vanWijk提出了一種用陰影來表示層次關系的樹圖生成算法。這種算法使用不同的陰影來表示整個樹圖不同的層次,使得層次結構非常直觀。圖3是一個使用陰影單方向分割的例子。圖3中,下方是顯示空間,現預將它切割成表示三層、每層兩個元素(假設大小相等)的樹圖。第一層有兩個元素,將寬等分成兩個子寬,并在其上都添加一個突起。對每個子寬又劃分兩個子寬,并添加兩個幅度為上一步一半的突起。如此劃分并添加,直到最底層元素。圖中下半部分既是使用這種算法產生的樹圖。如果我們從切面觀察樹圖,這些突起就構成了一系列的脊,這些脊清楚的將不同元素分開。而且,兩個脊中間峽谷的深度越深,說明兩個脊層次越高。圖4給出了一個較復雜的層次數據集合用Cushion算法生成的樹圖的例子。可以看出圖的層次結構信息很明顯,而且也不需要犧牲額外的顯示空間來表示層次結構。Cushion算法本身并不是一種生成樹圖的算法,不提供切割矩形的方法和策略,它所做的就是在矩形切割好以后,按照矩形的大小和切割的方向在其上添加陰影,模擬突起的效果。因此,Cushion算法可以靈活的和其他算法結合使用。但是,Cushion算法也有其不足之處。樹圖的設計方案決定了樹圖只能通過矩形的面積和矩形的顏色兩個要素,同時表示出至多二維的信息。嵌套樹圖不得不犧牲一部分矩形的面積作為邊緣來體現層次關系(改變矩形邊緣寬度事實上也是犧牲一部分矩形的面積換取一定層次關系的體現)。Cushion算法自然也不可能憑空變出另一個要素。它使用的雖然是陰影,但是陰影實際上也不過是顏色這個要素中抽取的一維。就像犧牲一部分面積會影響總體面積一樣,犧牲顏色中的一維必然也會對顏色的使用造成影響。從總體上說,Cushion算法還是很有價值的。它不像其他算法需要額外的顯示空間來表達層次信息,而且算法比較簡單,陰影深度也比較好控制。并且,樹圖使用者通常最關心的是面積較大的元素,使得小元素在Cushion樹圖中辨不甚清的缺點也可以忽略了。因此,Cushion算法的思想仍是目前對樹圖層次結構的改進最成功的思想。1.2加入本形的矩形信息進行移動假設有一個一層的數據集合T={6,6,4,3,2,2},需要在一個長為6,寬為4的矩形區域上顯示出這個數據集合。如果使用slice-and-dice算法,由于這個數據集合只有一層,所以初始矩形不是被橫切就是被縱切,如圖5,這樣生成的矩形大都呈現為長條狀,可視化效果很差;如果使用正方化算法,整個過程如下(矩形x表示面積為x的矩形):(1)首先選出當前面積最大的矩形6,擺在初始矩形的較小邊上,使生成的矩形貼著矩形的較小側邊,記錄此時矩形6的長寬比,為8/3。(2)橫向加入當前面積最大的矩形6,同樣貼著初始矩形的較小側邊,并和第一個矩形相鄰。記錄此時已加入的兩個矩形長寬比中的最大值,為3/2。(3)由于3/2<3/8,說明第二個矩形6的加入對整體的長寬比有改善,確定加入第二個矩形6。(4)橫向加入當前面積最大的矩形4。記錄此時已加入的矩形長寬比中的最大值,為4。(5)由于4>3/2,說明矩形4的加入增大了整體的長寬比,放棄加入矩形4。(6)矩形4成為當前待加入的矩形,初始矩形為當前剩余的空白區域。按照和上述步驟相同的方法進行加入,直到最后所有矩形都被加入為止。將圖6和圖5略加比較就可以看出,正方化算法大大降低了生成矩形的長寬比,可視化的效果更好。圖中的陰影部分表示當前處理的階段,每一個階段完結時,將剩下未填充的顯示區域作為下一階段的工作區域,將這一階段最后那個放棄加入的矩形作為下一個階段第一個待加入的矩形,進行下一階段的填充。正方化算法本質上是一種自適應的算法,通過密切關注每一步導致長寬比的變化來控制布局。同時它每一步也是盡可能多加入矩形,只要加入的矩形對這個階段的長寬比是有利的,那么就加入;反之結束當前階段,將這一矩形留到下一階段。正方化算法的著力點在改進樹圖的長寬比。因為矩形的長寬比取決于面積和擺放位置,正方化算法因此在這兩方面都作了考慮,也達到了非常好的效果。但是,在面積方面,由于元素在樹圖中對應矩形的位置是根據大小排序的,如果元素原來在集合中有順序的話,那么原來的順序勢必需要打亂。而在擺放策略方面,由于采用的自適應的思想,當元素面積發生變化時,會導致很明顯的布局變化;這在動態情況下會導致樹圖劇烈的抖動。因此,正方化算法并不適合元素動態變化情況下的使用。1.3pivat算法Cluster算法和正方化算法都要打亂原數據集合中元素的順序才能達到良好的顯示效果。當數據集合中元素順序無關緊要時這是可以容忍的,但當數據集合中元素順序是個比較重要的屬性的時候,就不大適合使用這兩種算法了,用戶無法從生成的樹圖上得到任何順序信息。而對于最簡單的Slice-and-Dice算法,元素的順序倒是可以很直觀地體現出來,只需在每一輪切割時保持元素的順序,那么生成的樹圖就是分塊有序的。而對于這樣分塊有序的樹圖,定位一個元素的難度很小,當元素屬性變化的時候給整個樹圖帶來的變化也很小。針對這一情況,BenShneiderman在2002年提出了順序樹圖的概念,并提出了兩種兼顧順序和長寬比的算法:Pivot算法和Strip算法。Pivot算法并不能保證樹圖中矩形的順序能絕對符合對應元素在數據集合中的順序,它采用的是一種部分有序的思想。使用Pivot算法對于某個數據集合生成的樹圖,原來位置接近的數據元素,其對應樹圖中的矩形位置也接近;原來相鄰的元素,在樹圖中對應的矩形位置不一定相鄰但也不會太遠。Pivot算法使用一個遞規的過程完成矩形的擺放,整個過程試圖在二維空間上模擬快速查找(quicksort)算法。算法的輸入是一個待切割的初始矩形R(初始顯示區)和一個有序號的有大小的的元素的集合。算法的第1步是尋找一個特殊的元素pivot,擺放在R的邊上;第2步,集合剩下的元素被分配到R剩余部分的三個大矩形里;然后算法按照此方法遞規地切割每個矩形,直到到達最底層元素。可用圖7來輔助說明算法的過程。雖然在此圖中初始矩形R的寬比高要大,但算法稍作改動就可以適合寬比高小的情況。Pivot算法:輸入:待切割的矩形R;有大小的元素L1,L2,…,Ln輸出:一系列矩形,R1,R2,…,Rn(1)如果當前集合中元素個數≤4,用Pivot算法切割,整個過程完成。(2)設集合中最大的元素為P,也就是pivot。(3)如果R的寬大于高,按圖7將R切割成R1,R2,R3,Rp四個矩形(如果R的高大于寬,只需采用沿y=x對稱的切割布局)。(4)將P放在Rp中。Rp的實際大小和位置在第5步決定。(5)將集合中除了P剩下的元素分成3組L1,L2,L3,分別放在R1,R2和R3中。L1,L2和L3都可能為空。分組原則是:L1應包含所有序號小于R的元素;L2中的元素序號都小于L3中的元素,并且應盡量使矩形Rp的長寬比接近1。(6)對于R1,R2,R3,回到第一步,按照同樣的過程對它們進行切割。根據Pivot的選取原則,Pivot算法有幾個變體。上述的Pivot算法選取面積最大的元素作為pivot,其動機是因為面積最大的元素通常最不好擺放,因此盡可能最先擺放,因此這種Pivot算法也叫做Pivot-by-size。Pivot算法能夠大致保持元素的順序。在生成的樹圖中,元素的順序大體服從從左到右和從上到下遞增的規律。Pivot算法的每一個遞規過程都是將數據元素分成四個塊來處理。當數據元素比較多的時候,這種遞規確實能夠保持較小的長寬比。但是當數據元素比較少,尤其是最后一步(數據元素的個數≤4)的時候,這種分塊就顯得太粗糙,以至于最后一步總是不能獲得好的長寬比。Benshneiderman試圖在最后一步采用其他策略布局,但是這樣又會失去Pivot算法保持順序和動態情況下穩定性好的優點。總的來說,Pivot算法在長寬比,動態穩定性和保持元素順序三者間做了一個折衷,希望生成的樹圖獲得比較小的長寬比,較好的順序性和動態穩定性,雖然不管在哪個方面都不是最好的算法。然而算法試圖在二維空間上找到一種quicksort算法的思想,卻是非常具有啟發性。1.4不平衡說的strap算法受正方化算法自適應思想的啟發,BenShneiderman提出了一種Strip算法。Strip算法同樣在長寬比,順序和動態穩定性之間做了折衷,但是Strip算法比Pivot算法更為成功。Strip算法是正方化算法的一個變體,但使得長寬比、順序性和動態穩定性最平衡。自適應的思想使得每一行的元素都不會有很大的長寬比;順序排列和條形布局使得矩形非常符合元素原來的順序,動態情況下整個布局的穩定性也很好。美中不足的地方是Strip算法最后一步的長寬比總是很差,因為通常最后一步剩下的顯示空間非常細長。BenShneiderman雖然隨后對最后一步進行了改進,最后一步的時候有選擇的向倒數第二步回溯;然而終究只能細微改進,畢竟這是strip算法的一個秉性。2pivat算法Cushion算法可以優化生成樹圖的層次結構,但本身并不是一個完整的算法,必須和其他算法結合使用。更抽取了顏色中的一個要素:陰影來表示層次結構,導致Cushion算法生成的樹圖,不便以黑白程度表示數據元素的某個屬性;正方化算法能夠顯著降低生成樹圖中矩形的平均長寬比,但打亂了元素順序,當元素屬性變化較明顯時,不適合可視化動態數據;Pivot算法巧妙將快速排序算