2 2. d T = (V, E) d i D d i.time d i D (d i) = {d D ; d.time < d i.time} d i d D (d i) ρ(d, d i) ˆd d i V V {d i}, P (d i) = ˆd = arg max d D (d i ) ρ

Size: px

Start display at page:

Download "2 2. d T = (V, E) d i D d i.time d i D (d i) = {d D ; d.time < d i.time} d i d D (d i) ρ(d, d i) ˆd d i V V {d i}, P (d i) = ˆd = arg max d D (d i ) ρ"

のぶあきつくとの
5 years ago
Views:

1 DEIM Forum 207 G {fushimi,satoh}@ce.slis.tsukuba.ac.jp Web. Web Minimum Spanning TreeRelative Neighborhood Graphk-NN Graph 2 3 [] Principal Component AnalysisMulti-Dimensional Scaling Sammon Mapping Kernel PCA Fisher s linear Discriminant Analysist-distributed Stochastic Neighbor Embedding [2] Parametric Embedding [3] ISOMAP [4]Locally Linear Embedding [5]Laplacian Eigenmaps [6] ISOMAP D = {d,..., d N } W = {w,..., w M } M b i = [b i,j] M j= b i,j d i w j d i d j ρ(d i, d j) = cos(b i, b j) α ρ(d i, d j) > α D α

2 2 2. d T = (V, E) d i D d i.time d i D (d i) = {d D ; d.time < d i.time} d i d D (d i) ρ(d, d i) ˆd d i V V {d i}, P (d i) = ˆd = arg max d D (d i ) ρ(d, d i) E E {( ˆd d i)} P (d i) d i d D (d i) d i α d i ρ( ˆd, d i) = max d D (d i ) ρ(d, d i) α (ρ( ˆd, d i) > α) ˆd d i d i rootp (d i) = d i P (d i) = arg max ρ(d, d i) (ρ( ˆd, d i) > α) d D (d i ) d i (otherwise) α α < α = 0 λ d i d i.time d j.time λ exp( λ(d i.time d j.time)) root 0 s V s = {d; dist(d, root(d)) = s} s N s = V s d i C(d i) C(d i) C(d i) P (d i).time < d i.time P (d i) d i d j C(d j).time > d i.time [7] s s + X s X s+ V s V s+ r sr s+ 2 A = [a i,j] N,N 2 i=,j= Ã = [ã i,j] X X 2 N N 2 J(X, X 2) = i= j= ã i,j x T i r x j r 2 + N λ i(r 2 x T i x i) 2 i= + N 2 µ j(r2 2 x T j x j). () 2 j= λ i µ j () xt i x j r r 2 = cos θ i,j J(X, X 2) X 2 x i x i = r x i xi, N2 xi = ã i,jx j (2) j= d i x i 2 x j r X 2 x j x j = r2 x j xj, N xj = ã i,jx i (3) i= X X 2 2 X 2 x i 3 X x j 4 J(X, X 2) 5 2 HITS [8] 2 2 [9]

3 ) TF2) 3) 4) Minimum Spanning TreeMST Yahoo! 6,450 3,090 [0] Bag Of Words STAP MLB 3. 2 TF α α MST (a) TF 0 MST α K α T k (k =,..., K α) N (k) = V (k) Kα Kα k= h= N (k) N (h) (K α ) K α. (4) k= (a) α = 0. α α = 0.23 (b) a DegDist(degree) = b degree a (b) MST TF 0 < α < < a < 3 α = 0 TF MST MST TF (c) TF MST (c) α = 0 TF (d) V ρ(d, P (d)) d V (d) α TF ρ(d i, d j) > α (d) α α > 0. MST (e) (e) MST TF TF MST TF (f) V d.time P (d).time. d V (f) MST 3. 3 TF 3 α =

4 #Trees (a) Gini coefficient on tree sizes Average exponent of degree distribution (b) Average depth of each tree (c) Average similarity between adjacent nodes Average gini coefficient on node category Average interval between adjacent nodes (d) (e) α TF (f) 3. 4 PCE A = [a u,v] u, v G = [g u,v] (b) SF K(X) = N N 2g 2 m= n=m+ m,n (c) CE N C(X) = N m= n=m+ (g m,n x m x n ) 2 {a m,n ln ρ(m, n)+( a m,n) ln( ρ(m, n))} (d) G-MDS M(X) = 2 x T 2 (h)(h N GH N )x (h) h= (e) SE S(X) = 2 h= x T (h)lx (h) α = 0 TF H N = I N N N T N L x (h) h ρ(m, n) = exp( x m x n 2 /2) (f) ISOMAP k-nn 2 2(a) 2(b) (c) SF CE PCE HITS 2(d) (e)

5 (a) 提案手法 TF+PCE (b) TF+SF (c) TF+CE (d) TF+G-MDS (e) TF+SE (f) ISOMAP 4-NN+G-MDS 図 2 α = 0 の TF の可視化結果が不鮮明である G-MDS 法と SE 法は線形な手法であるため間の関連が反映された結果となっているツリーを構築する提高速である一方で解の品質が良くなくこのような結果になっ案手法とは異なり k-nn グラフを構築するため閉路が存在したと考えられる文書間の順序関係が反映できない一方提案手法では TF 構図 2(f) を見ると同一カテゴリの文書が近傍に位置し文書築時に順序関係を考慮しているため文書群の流れが陽にわか

2 3 4 5 6 7 8 9 0 2 3 4 5 2 3 4 5 6 7 8 9 0 2 3 4 5 6 α = 0.23 TF 5 7 6 2 3 4 7 8 MVP 2 4 Twitter tweet 2 ips 4 STAP STAP STAP 6 A 3 MST TF 3.

6 α = 0.23 TF MVP 2 4 Twitter tweet 2 ips 4 STAP STAP STAP 6 A 3 MST TF 3. 5 PCE N H X = {x,, x N } T 0 N i= xi = 0 h ( < = h < = H) N i= x2 i,h = j 2 H = 2 3 MST+SF y = [b,j,, b N,j] T N H f f = H h= f 2 h = f N Xf y f F (f) = y T Xf. (5) PCE X (5) F (y) Xf y (5) r = F (f) (5) ˆf ˆf = X T y XT y. (6) (6) (5) F (ˆf) = X T y. (7) y H (6) (7) Annot(y) = X T y. (8) y (6) j y 4 α = 0.23 TF 3 5

7 (a) r = 0.49 r = 0.45 r = 0.44 r = 0.42 r = 0.4 (b) 2 r = 0.57 r = 0.54 r = 0.49 r = 0.48 r = 0.46 (c) 3 STAP r = 0.48 r = 0.45 r = 0.44 r = 0.44 r = α = 0.23 TF 4(a) 4(a) 5 4(b) 5 4(c) 4(a) 4. Ishikawa T-Scroll [] k-means MemeTracker [2] EventRiver [3]CloudLines [4]STREAMIT [5] Keim EventRiver [3] temporal-locality Krstajic CloudLines [4]

8 Alsakran STREAMIT [5] 2 STREAMIT 5. TF PCE TF DAG TFIDF JSPS 6K654 [] A. Šilić and B.D. Bašić, Visualization of text streams: A survey, pp.3 43, Springer Berlin Heidelberg, Berlin, Heidelberg, 200. [2] L. van dermaaten and G.E. Hinton, Visualizing highdimensional data using t-sne, Journal of Machine Learning Research, vol.9, pp , [3] T. Iwata, K. Saito, N. Ueda, S. Stromsten, T.L. Griffiths, and J.B. Tenenbaum, Parametric embedding for class visualization, Advances in Neural Information Processing Systems 7, eds. by L.K. Saul, Y. Weiss, and L. Bottou, pp , MIT Press, [4] J.B. Tenenbaum, V. Silva, and J.C. Langford, A Global Geometric Framework for Nonlinear Dimensionality Reduction, Science, vol.290, no.5500, pp , [5] S.T. Roweis and L.K. Saul, Nonlinear dimensionality reduction by locally linear embedding, SCIENCE, vol.290, pp , [6] M. Belkin and P. Niyogi, Laplacian eigenmaps and spectral techniques for embedding and clustering, Advances in Neural Information Processing Systems 4, pp , MIT Press, 200. [7] T. Fushimi, Y. Kubota, K. Saito, M. Kimura, K. Ohara, and H. Motoda, Ai 20: Advances in artificial intelligence: 24th australasian joint conference, perth, australia, december 5-8, 20. proceedings, chapter Speeding Up Bipartite Graph Visualization Method, pp , Springer Berlin Heidelberg, 20. [8] J.M. Kleinberg, Authoritative sources in a hyperlinked environment, J. ACM, vol.46, pp , Sept [9] T. Kamada and S. Kawai, An algorithm for drawing general undirected graphs, Inf. Process. Lett., vol.3, pp.7 5, April 989. [0] G. Salton, A. Wong, and C.S. Yang, A vector space model for automatic indexing, Commun. ACM, vol.8, no., pp , Nov [] Y. Ishikawa and M. Hasegawa, T-scroll: Visualizing trends in a time-series of documents for interactive user exploration, pp , Springer Berlin Heidelberg, Berlin, Heidelberg, [2] J. Leskovec, L. Backstrom, and J.M. Kleinberg, Memetracking and the dynamics of the news cycle, KDD, pp , [3] D.A. Keim, D. Luo, J. Yang, W. Ribarsky, and M. Krstajic, Eventriver: Visually exploring text collections with temporal references, IEEE Transactions on Visualization & Computer Graphics, vol.8, pp.93 05, 200. [4] M. Krstajic, E. Bertini, and D.A. Keim, Cloudlines: Compact display of event episodes in multiple time-series., IEEE Trans. Vis. Comput. Graph., vol.7, no.2, pp , 20. [5] J. Alsakran, Y. Chen, D. Luo, Y. Zhao, J. Yang, W. Dou, and S. Liu, Real-time visualization of streaming text with a force-based dynamic system, IEEE Comput. Graph. Appl., vol.32, no., pp.34 45, Jan. 202.

2. Eades 1) Kamada-Kawai 7) Fruchterman 2) 6) ACE 8) HDE 9) Kruskal MDS 13) 11) Kruskal AGI Active Graph Interface 3) Kruskal 5) Kruskal 4) 3. Kruskal

2. Eades 1) Kamada-Kawai 7) Fruchterman 2) 6) ACE 8) HDE 9) Kruskal MDS 13) 11) Kruskal AGI Active Graph Interface 3) Kruskal 5) Kruskal 4) 3. Kruskal 1 2 3 A projection-based method for interactive 3D visualization of complex graphs Masanori Takami, 1 Hiroshi Hosobe 2 and Ken Wakita 3 Proposed is a new interaction technique to manipulate graph layouts