Mapowanie drzewa — Treemapping

Mapa drzewa eksportu Singapuru według kategorii produktów, 2012. Mapy drzewa eksportu produktów to jedna z najnowszych aplikacji tego rodzaju wizualizacji, opracowana przez Harvard-MIT Observatory of Economic Complexity .

W wizualizacji informacji i obliczania , mapa drzewa jest sposób wyświetlania hierarchii danych przy zagnieżdżone dane, zwykle prostokątów.

Mapy drzewa wyświetlają dane hierarchiczne ( o strukturze drzewa ) jako zestaw zagnieżdżonych prostokątów. Każdej gałęzi drzewa przypisywany jest prostokąt, który jest następnie układany mniejszymi prostokątami reprezentującymi podgałęzie. Prostokąt węzła liścia ma obszar proporcjonalny do określonego wymiaru danych . Często węzły liści są pokolorowane, aby pokazać osobny wymiar danych.

Kiedy wymiary koloru i rozmiaru są w jakiś sposób skorelowane ze strukturą drzewa, często można łatwo dostrzec wzory, które trudno byłoby dostrzec w inny sposób, na przykład czy dany kolor jest szczególnie istotny. Drugą zaletą map drzew jest to, że dzięki swojej konstrukcji efektywnie wykorzystują przestrzeń. Dzięki temu mogą czytelnie wyświetlać na ekranie jednocześnie tysiące elementów.

Algorytmy kafelkowe

Aby utworzyć mapę drzewa, należy zdefiniować algorytm kafelkowania , czyli sposób podziału regionu na podregiony określonych obszarów. W idealnym przypadku algorytm mapy drzewa utworzyłby regiony spełniające następujące kryteria:

  1. Mały współczynnik proporcji — idealnie bliski jedności. Regiony o małym współczynniku proporcji (tj. tłuste obiekty ) są łatwiejsze do zauważenia.
  2. Zachowaj sens uporządkowania danych wejściowych.
  3. Zmień, aby odzwierciedlić zmiany w danych źródłowych.

Niestety te właściwości mają odwrotną zależność. W miarę optymalizacji proporcji kolejność umieszczania staje się mniej przewidywalna. Gdy kolejność staje się bardziej stabilna, proporcje obrazu ulegają degradacji.

Prostokątne mapy drzew

Do chwili obecnej opracowano sześć podstawowych algorytmów mapy drzewa prostokątnego:

Algorytmy map drzewa
Algorytm Zamówienie Proporcje obrazu Stabilność
Drzewo binarne częściowo zamówione wysoka stabilny
Mieszane mapy drzew niezamówiony najniższy stabilny
Zamówione i Quantum częściowo zamówione średni średnia stabilność
Plasterek i kostka zamówiony bardzo wysoko stabilny
kwadratowy niezamówiony najniższy średnia stabilność
Rozebrać się zamówiony średni średnia stabilność

Wypukłe mapy drzewa

Prostokątne mapy drzewa mają tę wadę, że w najgorszym przypadku ich proporcje mogą być dowolnie wysokie. Jako prosty przykład, jeśli korzeń drzewa ma tylko dwoje dzieci, jedno z wagą, a drugie z wagą , wtedy współczynnik proporcji mniejszego dziecka będzie wynosił , który może być dowolnie wysoki. Aby poradzić sobie z tym problemem, zaproponowano kilka algorytmów wykorzystujących regiony, które są ogólnie wypukłymi wielokątami , niekoniecznie prostokątnymi.

Mapy drzewa wypukłego zostały opracowane w kilku krokach, każdy krok poprawiał górną granicę współczynnika proporcji. Granice podane są jako funkcja - całkowitej liczby węzłów w drzewie oraz - całkowitej głębokości drzewa.

  1. Onak i Sidiropoulos okazali się górną granicą .
  2. De-Berg i Onak i Sidiropoulos poprawiają górną granicę do i udowadniają dolną granicę .
  3. De-Berg i Speckmann i van-der-Weele poprawiają górną granicę do , dopasowując się do teoretycznej dolnej granicy. (W szczególnym przypadku, gdy głębokość wynosi 1, przedstawiają algorytm, który wykorzystuje tylko cztery klasy wielokątów 45 stopni (prostokąty, trójkąty prostokątne, trapezy prostokątne i pięciokąty 45 stopni) i gwarantuje proporcje najwyżej 34/7.)

Te dwa ostatnie algorytmy działają w dwóch krokach (znacznie uproszczonych dla przejrzystości):

  1. Oryginalne drzewo jest konwertowane na drzewo binarne: każdy węzeł z więcej niż dwojgiem dzieci jest zastępowany przez poddrzewo, w którym każdy węzeł ma dokładnie dwoje dzieci.
  2. Każdy region reprezentujący węzeł (zaczynając od korzenia) jest podzielony na dwa za pomocą linii, która utrzymuje jak największe kąty między krawędziami. Można wykazać, że jeśli wszystkie krawędzie wielokąta wypukłego są rozdzielone kątem co najmniej , to jego współczynnik kształtu wynosi . Możliwe jest zapewnienie, że w drzewie o głębokości kąt jest podzielony przez współczynnik co najwyżej , stąd gwarancja proporcji.

Ortowypukłe mapy drzew

W wypukłych mapach drzewa współczynnik proporcji nie może być stały - rośnie wraz z głębokością drzewa. Aby uzyskać stały współczynnik proporcji, można użyć map drzewa Ortoconvex . Tam wszystkie regiony są prostoliniowymi ortowypukłymi wielokątami o współczynniku kształtu najwyżej 64; a liście są albo prostokątami o współczynniku kształtu najwyżej 8, albo kształtami w kształcie litery L lub S o współczynniku kształtu najwyżej 32.

W szczególnym przypadku, gdy głębokość wynosi 1, przedstawiają algorytm, który używa tylko prostokątów i kształtów L, a współczynnik proporcji wynosi co najwyżej ; wewnętrzne węzły używają tylko prostokątów o maksymalnym współczynniku proporcji .

Inne mapy drzew

Mapy drzew Woronoja
na podstawie obliczeń diagramu Voronoi . Algorytm jest iteracyjny i nie podaje żadnej górnej granicy współczynnika proporcji.
Mapy drzew układanki
na podstawie geometrii krzywych wypełniających przestrzeń. Zakładają, że wagi są liczbami całkowitymi, a ich suma jest liczbą kwadratową. Regiony mapy to prostoliniowe wielokąty i wysoce nieorto-wypukłe. Gwarantuje się, że ich proporcje wynoszą co najwyżej 4.
GosperMaps
na podstawie geometrii krzywych Gospera . Jest uporządkowany i stabilny, ale ma bardzo wysoki współczynnik kształtu.

Historia

Wykorzystanie miejsca na dysku twardym wizualizowane w TreeSize , oprogramowanie wydane po raz pierwszy w 1996 roku

Wizualizacje obszarowe istnieją od dziesięcioleci. Na przykład wykresy mozaikowe (znane również jako diagramy Marimekko) wykorzystują prostokątne kafelki, aby pokazać rozkłady połączeń (tzn. najczęściej są to zasadniczo ułożone w stos wykresy kolumnowe, w których kolumny mają różne szerokości). Główną cechą wyróżniającą mapę drzewa jest jednak konstrukcja rekurencyjna, która pozwala na rozszerzenie jej na dane hierarchiczne o dowolnej liczbie poziomów. Pomysł ten został wymyślony przez profesora Bena Shneidermana z University of Maryland Human – Computer Interaction Lab na początku lat 90-tych. Shneiderman i jego współpracownicy pogłębili następnie ten pomysł, wprowadzając szereg interaktywnych technik filtrowania i dostosowywania map drzew.

Wszystkie te wczesne mapy drzewa wykorzystywały prosty algorytm kafelkowania „plasterek i kostka”. Pomimo wielu pożądanych właściwości (jest stabilny, zachowuje porządek i jest łatwy do wykonania), metodą plastrowania i kostek często wytwarza się płytki z wieloma długimi, chudymi prostokątami. W 1994 roku Mountaz Hascoet i Michel Beaudouin-Lafon opracowali algorytm „kwadratyzacji”, spopularyzowany później przez Jarke van Wijka , który tworzył kafelki, których prostokąty były bliższe kwadratowi. W 1999 roku Martin Wattenberg wykorzystał odmianę algorytmu „squarifying”, który nazwał „pivot and slice”, aby stworzyć pierwszą internetową mapę drzewa, SmartMoney Map of the Market, która wyświetlała dane dotyczące setek spółek na amerykańskim rynku akcji. Po premierze mapy drzew cieszyły się dużym zainteresowaniem, zwłaszcza w kontekście finansowym.

Trzecia fala innowacji w zakresie map drzew pojawiła się około 2004 r., po tym, jak Marcos Weskamp stworzył Newsmap , mapę drzewa wyświetlającą nagłówki wiadomości. Ten przykład nieanalitycznej mapy drzewa zainspirował wielu naśladowców i wprowadził mapy drzewa do nowej, szerokiej publiczności. W ostatnich latach mapy drzew pojawiły się w mediach głównego nurtu, w tym przez New York Times. W ramach projektu Treemap Art Project powstało 12 oprawionych obrazów dla National Academies (Stany Zjednoczone) , pokazano wystawę Every AlgoRiThm has ART in It w Waszyngtonie i kolejny zestaw do kolekcji Museum of Modern Art w Nowym Jorku.

Zobacz też

Bibliografia

Linki zewnętrzne