1,a) 1, 2,b) (Parallel Coordinate Plot PCP) PCP 2 PCP Active Grpah Interface 2 VisLAMP Naohiro Ohta 1,a) Ken Wakita 1, 2,b) 1. 1 (Parallel Coordinate Plot, PCP) PCP PCP PCP 1 Presently with Tokyo Insitute of Technology 2 JST/CREST a) ohta.n.aa@m.titech.ac.jp b) wakita@is.titech.ac.jp PCP c 2016 Information Processing Society of Japan 1
AGI AGI (Multi-dimensional Projection Plot, MPP) PCP 2 MPP PCP Visualization System Linked and Apposed MPP to PCP (VisLAMP) AGI MPP (PCA) MPP AGI PCP AGI PCP MPP PCP VisLAMP Cars MPP PCP 2 2. (Parallel Coordinate Plot, PCP)[6][7] X 1,X 2,...,X m n m n D = {d ij } X i x =(i 1)/(m 1) (d 1j,d 2j,...,d mj ) j (d 1j, 0), (d 2j, 1/m 1),...,(d mj, 1) PCP PCP PCP PCP PCP 1 Palmas Bezier [11] Biclustering PCP [14] k-means [1][3] PCP PCP Classen [2] Cheng GBC[10] PCP [12] GBC PCP Yuan SPPC[15] PCP MDS PCP PCP c 2016 Information Processing Society of Japan 2
Giménez PCP star coordinates [4] PCP star coordinates AGI[5] (Multi-Dimensional Scaling, MDS) 2 Kruskal [8] AGI [13] 3. PCP 2 3 1 PCP PCP AGI AGI AGI AGI (Multi-dimensional Projection Plot, MPP) PCP PCP PCP 2 AGI MPP PCP MPP PCP MPP PCP MPP PCP Visualization System Linked and Apposed MPP to PCP (VisLAMP) 6 4. AGI MPP MPP AGI c 2016 Information Processing Society of Japan 3
MPP AGI MPP MPP PCP 4.1 n m D = {d ij } : m n [0, 1] D MPP (Principal Component Analysis, PCA ) W D m WD MPP PCA λ i PCA P P =(e 1,e 2 ) e i = f i / f i (1) f 1 =( λ 1, 0, λ 3, 0,...) (2) f 2 =(0, λ 2, 0, λ 4,...) (3) P j ˆp =(d 1j,d 2j,...) T p = PWˆp PWD 4.2 MPP MPP AGI MPP (P ) AGI [5] p ˆp P p AGI p = P ˆp MPP AGI C (j, i) i j C P PC MPP AGI 5. PCP MPP AGI PCP MPP MPP PCP PCP MPP 5.1 PCP 2 PCP PCP c 2016 Information Processing Society of Japan 4
MPP PCP PCP n m D = {d ij } : m n Y Y =(i 1)/(m 1), 1 i m PCP i (i + 1) 0 r i 1 i<m r i = 1. j (d 1j,d 2j,...,d mj ) ((d 1j, 0), (d 2j,r 1 ), (d 3j,r 1 + r 2 ), (d 4j,r 1 + r 2 + r 3 ),...,(d mj, 1)) MPP PCP 9 MPP PCP MPP A 1,A 2,... A i A i+1 α i MPP PCP α 8 α 7 α 9 A 7 A 6 α 6 α5 A 5 A 8 α3 α 4 α 1 α 2 A 4 A 9 A 1 A 2 A 3 A 8 α 8 A 9 A 1-3 MPP A 8,A 9,A 1,A 2,...,A 7 PCP PCP MPP MPP A 4 A 5 α 4 PCP A 4 A 5 MPP A 4 A 5 A 6 PCP MPP A 7 α 9 α 3 α 4 α 5 α 6 PCP MPP PCP 5.2 MPP MPP 2 AGI MPP AGI 3 3 D = d ij ˆp j =(d 1j,d 2j,...) ( ˆp j ˆp k <θ) MPP G =(V = {1, 2,...,m},E = V 2 ) θ ϕ G V = {v V deg θ (v) >ϕ} E = {(v j,v k ) V 2 ˆp j ˆp k <θ} G =(V,E ) MPP PCP c 2016 Information Processing Society of Japan 5
情報処理学会研究報告 見つけたい あるいは 逆に PCP の特定の座標軸におい て 値の分布に明瞭な傾向が見られた場合 その軸の特定 の範囲の値を持つデータ項目群の多次元空間における分散 状況を MPP で観察したい場合もある このような要請に答えるために MPP PCP それぞれ の表示画面においてデータ項目群を選択し 自動的に着色 する機能を用意した 一方の表示画面において選択された データ項目群については 他方の画面において対応する (a) 初期状態 (b) クラスタをさらに分割した結果 (c) 燃費と排気量 重量の関係 (d) (c) の PCP を可変にした結果 データ項目を同じ色で彩色する MPP 表示においてはデータ項目は点として表示され データ群は一群の点である 本システムにおいては ド ラッグ操作で指定される矩形領域 あるいは多角形領域内 の点群が選択される これらの点群には 自動的に彩色が なされる このため 複数の領域を順次選択した場合 そ れらの分布を色の違いとして認知できる PCP 表示においてはデータ項目は折れ線として表示さ れ データ群は折れ線の集合である MPP 表示において 図 1 Cars データセットを可視化した結果 指定されたデータ項目群に対応する折れ線群はそれぞれ MPP 表示におけるのと同一の色で着色される この連携 機能により MPP で発見されたクラスタに属するデータ 項目群の属性ごとの傾向を観察することができる 6.1 計算量に対する考察 まず可視化を行う前に本手法における計算量について考 察する 最初に初期状態を生成するための計算量について PCP 表示においても I ツール [7] と同様の方法でデータ 考える 最初の高次元配置においては主成分分析で求めた 項目群を選択することができる PCP 表示において あ 際は固有値の計算量と等しくなるので O(m3 ) になる 項 る属性軸に沿ってドラッグ操作を行うと その属性に関し 目同士の類似度の計算は m 次元の配置に対し n 個の項目 て ドラッグした範囲の値を持つデータ項目が選択され 間について計算するので O(mn2 ) となる 初期の射影を求 MPP における選択機能と同様に彩色される PCP で選択 める際は m 個の固有値を成分とした 2 本の射影ベクトル されたデータ項目群への彩色は MPP 画面にも反映される を求めるため O(m) である 項目数を n としたとき通常 n > m と考えてよいので よって初期配置を求めるのに必 5.3 部分データ項目群の可視化 要な計算量は O(mn2 ) となる ここまで 多次元データに MPP と PCP を組合せた可 次にユーザの操作により射影の更新が行われた場合の 視化を実施し それらを連携させて複数のデータ項目群に 操作について考える MPP における射影の更新について 分離できることを述べた 複雑な多次元データの場合 選 は AGI と違い 項目だけでなく属性についても更新を行 択したデータ項目群のなかにさらに部分構造が見つかる場 う必要がある よって O(m(n + m)) である 次に幅可変 合がある ここでは このような多次元データに内在する PCP の更新の際に計算量について考える これはどちら 階層的な構造を分析するための機能について述べる も属性数 m のみが関係する 角度を使った計算方法の場 基本的には前述した方法で選択されたデータ項目群を新 合 ソートの計算量が更新の中において最も多くなるので たな多次元データと見做し これを表す行列 D を構成し O(m log m) であるとしてよい よって更新にかかる計算 提案手法を再適用する ただしこの部分集合において全項 量は O(m(n + m)) である また提案手法全体の計算量は 目での値が一定値である属性, つまり任意の j1, j2 に関し O(mn2 ) となる て dij1 = dij2 をみたす属性 Xi は MPP において PCA で 高次元配置を求める際に無意味なので取り除く このよう な属性を取り除いた多次元データ行列 D を MPP PCP 双方を用いて再び可視化する 6. 評価 考察 6.2 Cars データセットの可視化 本研究で提案した手法による可視化結果の評価検証にあ たり 多次元データ可視化の研究においてよく用いられる 前節までで提案した手法を可視化システム VisLAMP と Cars データセット [9] を扱う このデータセットの項目は して実装することで可視化を行う これらの結果について 車種を表しており その数は 398 である また 8 の属性を 評価および議論し 本手法の有用性を示す 持つ まず本システムで可視化を行い それを元に既存手 c 2016 Information Processing Society of Japan 6
Cars 1(a) 3 1 2 3 1 2 3 1 2 1 2 3 3 3 1(b) MPP 3 3-1 3-2 3-3 MPP 3-1 3-2 3-3 1 2 3 PCP 1 2 1 2 PCP PCP Cars 4 PCP PCP PCP 1(c) MPP 180 1(b) PCP 1(d) MPP PCP MPP PCP 6.3 Cars Cheng [12] Cars Palmas Cars [11] PCP MPP SPPC[15] MDS PCP 5 MPP MDS 6.1 O(m(m + n)) O(n 3 ) PCP MPP 1(b) c 2016 Information Processing Society of Japan 7
Palmas [11] PCP PCP 1(c) 7. PCP MPP AGI MPP PCP MPP PCP VisLAMP Cars MPP PCP PCP MPP (JST, CREST) [1] Ankerst, M., Berchtold, S. and Keim, D.: Similarity clustering of dimensions for an enhanced visualization of multidimensional data, Information Visualization, 1998. Proceedings. IEEE Symposium on, pp. 52 60, 153 (online), DOI: 10.1109/INFVIS.1998.729559 (1998). [2] Claessen, J. and van Wijk, J.: Flexible Linked Axes for Multivariate Data Visualization, Visualization and Computer Graphics, IEEE Transactions on, Vol. 17, No. 12, pp. 2310 2316 (online), DOI: 10.1109/TVCG.2011.201 (2011). [3] Ferdosi, B. J. and Roerdink, J. B.: Visualizing High- Dimensional Structures by Dimension Ordering and Filtering using Subspace Analysis, Computer Graphics Forum, Vol. 30, No. 3, pp. 1121 1130 (online), DOI: 10.1111/j.1467-8659.2011.01961.x (2011). [4] Giménez, A., Rosenbaum, R., Hlawitschka, M. and Hamann, B.: Using R-Trees for Interactive Visualization of Large Multidimensional Datasets, Proceedings of the 6th International Symposium on Visual Computing, Springer, pp. pp 554 563 (2010). [5] Hosobe, H.: A High-dimensional Approach to Interactive Graph Visualization, Proceedings of ACM Symposium on Applied Computing (SAC 2004), New York, NY, USA, ACM, pp. 1253 1257 (online), DOI: 10.1145/967900.968155 (2004). [6] Inselberg, A. and Dimsdale, B.: Parallel coordinates: a tool for visualizing multi-dimensional geometry, Visualization, 1990. Visualization 90., Proceedings of the First IEEE Conference on, pp. 361 378 (online), DOI: 10.1109/VISUAL.1990.146402 (1990). [7] Inselberg, A. and Dimsdale, B.: Parallel coordinates, Human-Machine Interactive Systems, Languages and Information Systems, Springer US, pp. 199 233 (1991). [8] Kruskal, J. B. and Seery, J. B.: Designing network diagrams, In proceedings of the First General Conference on Social Graphics, Leesburg,VA,USA, pp. 22 50 (1978). [9] Lichman, M.: UCI Machine Learning Repository (2013). [10] Meyer, M., Barr, A., Lee, H. and Desbrum, M.: Generalized Barycentric Coordinates on Irregular Polygons, Graphics Tools, Vol. 7, No. 1, pp. 13 22 (online), DOI: 10.1080/10867651.2002.10487551 (2002). [11] Palmas, G., Bachynskyi, M., Oulasvirta, A., Seidel, H. and Weinkauf, T.: An Edge-Bundling Layout for Interactive Parallel Coordinates, Pacific Visualization Symposium (PacificVis), 2014 IEEE, pp. 57 64 (online), DOI: 10.1109/PacificVis.2014.40 (2014). [12] S. Cheng, K. M.: Improving the Fidelity of Contextual Data Layouts Using a Generalized Barycentric Coordinates Framework, Proceedings of IEEE Pacific Visualization Symposium 2015, IEEE Pacific Visualization Symposium 2015 (2015). [13] Wakita, K., Takami, M. and Hosobe, H.: Interactive high-dimensional visualization of social graphs, Visualization Symposium (PacificVis), 2015 IEEE Pacific, pp. 303 310 (online), DOI: 10.1109/PACI- FICVIS.2015.7156391 (2015). [14] Watanabe, K., Wu, H.-Y., Niibe, Y., Takahashi, S. and Fujishiro, I.: Biclustering Multivariate Data for Correlated Subspace Mining, Proceedings of IEEE Pacific Visualization Symposium 2015 (2015). [15] Yuan, X., Guo, P., Xiao, H., Zhou, H. and Qu, H.: Scattering Points in Parallel Coordinates, Visualization and Computer Graphics, IEEE Transactions on, Vol. 15, No. 6, pp. 1001 1008 (online), DOI: 10.1109/TVCG.2009.179 (2009). c 2016 Information Processing Society of Japan 8