ツリーマッピング

情報の視覚化とコンピューティングにおいて、ツリーマッピングは、ネストされた図形 (通常は長方形) を使用して階層データを表示する方法です。

ツリーマップは、階層的（ツリー構造）なデータをネストされた長方形のセットとして表示します。ツリーの各ブランチには長方形が割り当てられ、サブブランチを表す小さな長方形が並べられます。リーフノードの長方形の面積は、データの指定された次元に比例します。^[1]多くの場合、リーフノードはデータの別の次元を示すために色分けされます。

色とサイズの次元がツリー構造と何らかの形で相関している場合、特定の色が特に関連しているかどうかなど、他の方法では見つけにくいパターンを簡単に確認できることがよくあります。ツリーマップの 2 つ目の利点は、構造上、スペースを効率的に使用できることです。その結果、何千もの項目を同時に画面上に読みやすく表示できます。

ツリーマップを作成するには、タイリング アルゴリズム、つまり、領域を指定されたエリアのサブ領域に分割する方法を定義する必要があります。理想的には、ツリーマップ アルゴリズムは次の基準を満たす領域を作成します。

1. 小さいアスペクト比（理想的には1に近い値）。アスペクト比が小さい領域（つまり、太い物体）は認識されやすくなります。^[2]
2. 入力データの順序をある程度保持します (順序付き)。
3. 基礎データの変更を反映するように変更します (高い安定性)。

これらの特性は逆の関係にあります。アスペクト比が最適化されると、配置順序は予測しにくくなります。順序が安定すると、アスペクト比は低下します。^{[例が必要]}

現在までに、15 の主要な長方形ツリーマップ アルゴリズムが開発されています。

長方形のツリーマップには、最悪の場合、アスペクト比が任意に高くなる可能性があるという欠点があります。簡単な例として、ツリーのルートに 1 つの重みが でもう1 つの重みがの 2 つの子しかない場合、小さい方の子のアスペクト比は になり、任意に高くなる可能性があります。この問題に対処するために、必ずしも長方形である必要はなく、一般的な凸多角形の領域を使用するアルゴリズムがいくつか提案されています。 ${\displaystyle 1/n}$${\displaystyle 1-1/n}$${\displaystyle n}$

凸型ツリーマップはいくつかのステップで開発され、各ステップでアスペクト比の上限が改善されました。上限は、ツリー内のノードの総数と、ツリーの深さの合計の関数として与えられます。 ${\displaystyle n}$${\displaystyle d}$

1. OnakとSidiropoulos ^[15]は上限を証明した。${\displaystyle O((d\log {n})^{17})}$
2. De-BergとOnakとSidiropoulos ^[16]は上限を に改善し、 の下限を証明した。${\displaystyle O(d+\log {n})}$${\displaystyle O(d)}$
3. De-BergとSpeckmannとvan-der-Weele ^[17]は、理論上の下限と一致するように上限を に改善しました。(深さが1の特殊なケースでは、彼らは45度多角形の4つのクラス(長方形、直角三角形、直角台形、45度五角形)のみを使用し、最大で34/7のアスペクト比を保証するアルゴリズムを提示しています。)${\displaystyle O(d)}$

後者の 2 つのアルゴリズムは 2 つのステップで動作します (わかりやすくするために大幅に簡略化されています)。

1. 元のツリーはバイナリ ツリーに変換されます。つまり、2 つ以上の子を持つ各ノードは、各ノードがちょうど 2 つの子を持つサブツリーに置き換えられます。
2. ノードを表す各領域（ルートから始まる）は、エッジ間の角度を可能な限り大きく保つ線を使用して 2 つに分割されます。凸多角形のすべてのエッジが少なくとも の角度で分離されている場合、そのアスペクト比は であることが証明できます。深さ のツリーでは、角度が最大 の係数で分割されることを保証できます。これがアスペクト比保証です。${\displaystyle \phi}$${\displaystyle O(1/\phi )}$${\displaystyle d}$${\displaystyle d}$

凸型ツリーマップでは、アスペクト比は一定ではなく、ツリーの深さに応じて大きくなります。一定のアスペクト比を実現するために、 正凸型ツリーマップ^[17]を使用できます。このツリーマップでは、すべての領域はアスペクト比が最大 64 の正凸直線多角形であり、 葉はアスペクト比が最大 8 の長方形、またはアスペクト比が最大 32 の L 字型または S 字型です。

深さが 1 である特殊なケースでは、長方形と L 字型のみを使用し、アスペクト比が最大 であるアルゴリズムが提示されています。内部ノードは、アスペクト比が最大 の長方形のみを使用します。 ${\displaystyle 2+2/{\sqrt {3}}\approx 3.15}$${\displaystyle 1+{\sqrt {3}}\approx 2.73}$

ボロノイツリーマップ

^[18]はボロノイ図の計算に基づいています。このアルゴリズムは反復的であり、アスペクト比の上限は与えません。

ジグソーツリーマップ^[19]

空間充填曲線の幾何学に基づいています。重みは整数であり、その合計は平方数であると想定されています。マップの領域は直線多角形で、非直交凸性が非常に高くなっています。アスペクト比は最大 4 であることが保証されています。

ゴスパーマップ

^[20]はゴスパー曲線の幾何学に基づいています。整然としていて安定していますが、アスペクト比が非常に高いです。

エリアベースの視覚化は数十年前から存在しています。たとえば、モザイク プロット(マリメッコ図とも呼ばれます) は、長方形のタイリングを使用して結合分布を表示します (つまり、最も一般的なのは、列の幅が異なる積み上げ列プロットです)。ただし、ツリーマップの主な特徴は、任意の数のレベルの階層データに拡張できる再帰構造です。このアイデアは、1990 年代初頭に メリーランド大学ヒューマン コンピューター インタラクション ラボのBen Shneiderman教授によって発明されました。 ^{[21] [22]} Shneiderman 教授と彼の協力者は、ツリーマップをフィルタリングおよび調整するためのさまざまなインタラクティブな手法を導入することで、このアイデアを深めました 。

これらの初期のツリーマップはすべて、単純な「スライス アンド ダイス」タイリング アルゴリズムを使用していました。スライス アンド ダイス法は、多くの望ましい特性 (安定性、順序の維持、実装の容易さなど) があるにもかかわらず、細長い長方形が多数含まれるタイリングを生成することがよくあります。1994 年に、Mountaz Hascoet とMichel Beaudouin-Lafon は、長方形が正方形に近いタイリングを作成する「スクエア化」アルゴリズムを発明しました。このアルゴリズムは、後にJarke van Wijkによって普及しました。1999 年にMartin Wattenberg は、「スクエア化」アルゴリズムのバリエーションである「ピボット アンド スライス」を使用して、最初の Web ベースのツリーマップである SmartMoney Map of the Market を作成しました。このツリーマップは、米国株式市場の何百もの企業のデータを表示しました。ツリーマップのリリース後、特に金融の分野でツリーマップへの関心が高まりました。^{[引用が必要]}

ツリーマップのイノベーションの第3の波は、Marcos Weskampがニュースの見出しを表示するツリーマップであるNewsmapを作成した2004年頃に起こりました。この非分析的なツリーマップの例は、多くの模倣者に影響を与え、ツリーマップを新しい幅広い視聴者に紹介しました。^[要出典]近年、ツリーマップは、ニューヨークタイムズでの使用など、主流メディアに進出しています。^{[23] [24]} Treemap Art Project ^[25]は、米国国立科学アカデミー向けに12枚の額入り画像を制作し、ワシントンDCのEvery AlgoRiThm has ART in It展示会^[26]で展示され、ニューヨーク 近代美術館のコレクション用に別のセットが制作されました。

• ディスクスペースアナライザー
• データと情報の視覚化
• Marimekko Chart は、1 つのレベルの明示的な階層を持つ同様の概念です。

ウィキメディア・コモンズには、ツリーマップに関連するメディアがあります。

• ツリーマップアートプロジェクトがワシントンDCの国立科学アカデミーのために制作した展示会
• 「ツリーマップの視覚化を使用したビジネス インテリジェンスの発見」、Ben Shneiderman、2006 年 4 月 11 日
• ツリー可視化技術の包括的な調査と参考文献
• Vliegen, Roel; van Wijk, Jarke J.; van der Linden, Erik-Jan (2006 年 9 月～10 月)。「一般化されたツリーマップによるビジネス データの視覚化」( PDF)。IEEE Transactions on Visualization and Computer Graphics。12 ( 5): 789–796。doi : 10.1109 /TVCG.2006.200。PMID 17080801。S2CID 18891326。2011 年7 月 24 日の オリジナル(PDF)からアーカイブ。
• Ben Shneiderman によるツリーマップの歴史。
• インタラクティブな動的マップを使用したハイパーメディア探索。Zizi と Beaudouin-Lafon による論文で、正方形化されたツリーマップ レイアウト アルゴリズム (当時は「改良されたツリーマップ レイアウト」と呼ばれていました) が紹介されています。
• インディアナ大学の説明
• Flytail Groupのクラウドソーシングによる割引情報に基づくライブ インタラクティブ ツリーマップ
• The Hive Groupの英語版ツリーマップのサンプル
• Macrofocus TreeMap で作成されたツリーマップの例をいくつか紹介します。
• drasticdata による動的ツリーマップとオンライン ツリーマッピング ソフトウェアを使用した視覚化