[4] CNM [5] 2. Kuramochi [6] TF IDF Wu Conceptual Physical Densest Connected Subgraph [7] [1] 2 TF IDF 2 2 1

Size: px

Start display at page:

Download "[4] CNM [5] 2. Kuramochi [6] TF IDF Wu Conceptual Physical Densest Connected Subgraph [7] [1] 2 TF IDF 2 2 1"

まいかすわ
5 years ago
Views:

DEIM Forum 2016 A5-3 305-8550 1-2 422 8526 52-1 640 8510 930 E-mail: {fushimi,satoh}@ce.slis.tsukuba.ac.

1 DEIM Forum 2016 A Twitter Facebook SNS [1] [2] [3] Web PageRank HITS A B 1 1 MeanShift

2 [4] CNM [5] 2. Kuramochi [6] TF IDF Wu Conceptual Physical Densest Connected Subgraph [7] [1] 2 TF IDF 2 2 1

3 3. 2 V E G = (V, E) u V J x u u v d(u, v) d(u, v) = d(v, u) d(u, u) = 0 u d Γ d (u) = {v : d(u, v) = d} V 2 1 ρ(d; λ) = exp( λd), λ 2 ρ(d; λ) = exp( λ log d). ρ(d(u, v); F u(λ u) = x T λu)xv v V \{u} u ρ(d(u, v); λ v V \{u} u)x v. (3) (3) λ u d log(d) u d f u,d = v Γ d (u) u g u,d = x T u f u,d u d f u,d1 f u,d2 h u,d = fu,d T 1 f u,d2 d 1 +d 2 =d (3) x v D u y u = ρ(d; λ) = v V \{u} v Γ d (u) x v ρ(d(u, v); λ)x v. (1) D u = max v V d(u, v) RVwD Resultant Vector with Decay RVwD RVwD RVwD CDC(u) = x u, y u = x u, Du ρ(d; λ) v Γ d (u) x v D u ρ(d; λ) v Γ d (u) xv x u L2 1 u CDC(u) u u 3. 3 RVwD y u RVwD λ u L2 1 x u.(2) F u (λ u ) = Du exp ( λud)g u,d. 2Du exp ( λ ud)h u,d λ u D u log F u (λ u ) = log exp ( λ u d)g u,d 1 2D u 2 log exp ( λ u d)h u,d. (4) r u,d = exp ( λ u d)g u,d Du d =1 exp ( λ ud )g u,d (4) log F u (λ u ) = r u,d {( λ u d) + log g u,d } r u,d log r u,d 1 2D u 2 log exp ( λ u d)h u,d. λ u Q u (λ u ) = λ u r u,d d 1 2D u 2 log exp ( λ u d)h u,d 1 dq u (λ u ) dλ u = r u,d d + s u,d = 2 2Du exp ( λ ud) d h u,d 2 2D u exp ( λud)h u,d exp ( λ u d)h u,d 2Du d =2 exp ( λud )h u,d

4 { d 2 Q u (λ u ) = 1 2Du s dλ 2 u,d d 2 u 2 ( 2Du ) 2 } s u,d d λ u 0 0 J D h u,d O( V 2 D J) Bag of Words 600 1,299 4,412 Web Bag of Words 9, ,522 20,411 Wiki 3 Cookpad ,815 40, ,171 Recipe 4. 2 ˆλ Web ˆλ > 1 ˆλ 0 Wiki ˆλ > 1 ˆλ 0 Recipe ˆλ > 1

(b) Wiki ネットワーク (a) Web ネットワーク図3 (c) Recipe ネットワーク手動によるラベル付き可視化結果いため距離減衰重みを制御するパラメータの値が大きく推定されたと考えられる λ 0 となるようなランキング下位は様々なカテゴリのレシピを投稿するユーザが多くを占めていた様々な食材を使用するため近隣だけでなく遠方のノー

27 0.15 0.20 らないノードであるそのため距離減衰重みを制御するパラコミュニティ中心性 0.76 0.78 0.53 メータの値が小さく推定されたと考えられるこれらの結果かコンテンツベクトルの次元 0.14 0.02 0.

3 中心性ランキングに関する考察表 2 にスピアマンの順位相関係数の結果を示す評価実験この節では提案指標であるコンテンツ中心性ランキングのに用いた 3 つ全てのネットワークにおいて以下の関係が見ら結果について上位ノードの性質や他の中心性指標と比較しなれたがら考察する表 1 に各ネットワークでの上位 10 ノードを近接中心性とコミュニティ中心性はコンテンツ中心性と示す

5 (b) Wiki ネットワーク (a) Web ネットワーク図3 (c) Recipe ネットワーク手動によるラベル付き可視化結果いため距離減衰重みを制御するパラメータの値が大きく推定されたと考えられる λ 0 となるようなランキング下位は様々なカテゴリのレシピを投稿するユーザが多くを占めていた様々な食材を使用するため近隣だけでなく遠方のノードのコンテンツベクトルをも合成しなければ高いコサイン類似表 2 中心性間の順位相関係数 WebNW WikiNW RecipeNW 次数中心性近接中心性媒介中心性 PageRank 度を得ることができないいわばコミュニティにあまり染ま固有ベクトル中心性 HITS らないノードであるそのため距離減衰重みを制御するパラコミュニティ中心性メータの値が小さく推定されたと考えられるこれらの結果かコンテンツベクトルの次元ら推定パラメータ λ の値はコミュニティのサイズや所属するノードのコンテンツベクトルのばらつき度に依存することが示唆されたンテンツ分布の中心に存在するようなノードを検出できる次に従来の構造に基づく中心性指標との関係を評価する 4. 3 中心性ランキングに関する考察表 2 にスピアマンの順位相関係数の結果を示す評価実験この節では提案指標であるコンテンツ中心性ランキングのに用いた 3 つ全てのネットワークにおいて以下の関係が見ら結果について上位ノードの性質や他の中心性指標と比較しなれたがら考察する表 1 に各ネットワークでの上位 10 ノードを近接中心性とコミュニティ中心性はコンテンツ中心性と示す Web ネットワークでは上位 10 ノードの全てがシラバある程度の相関があるこれはコンテンツ分布のモードはコスページであり実際にこれらのページ群には類似の単語名ミュニティなどの中心に位置していることから近接中心性詞が多く含まれておりシラバスページ群が大きなコンテンコミュニティ中心性が高いノードであるという直感に合致したツ分布を構成していることが伺える Wiki ネットワークでは結果であるほとんどすべての上位ノードがジャニーズ事務所所属のアイド次数中心性 PageRank はやや相関がある次数中心性ルに関するページであり同一グループに所属するアイドルのと PageRank の間には強い相関関係があるが次数が高いノーページは互いにつながっておりかつページ内に含まれる名ドは相対的に多くのコンテンツベクトルを強い重みで合成す詞も類似のものが多いコンテンツ中心性は類似のコンテンるためコサイン類似度も相対的に高くなるためと考えられるツベクトルを有するノードが多く分布する部分を抽出している Recipe ネットワークに対してはプライバシーの都合上ノードの名前を非表示にしているこのネットワークではほとんどすべての上位ノードがスープお弁当カレーに関す媒介中心性 HITS コンテンツベクトルの次元は相対的に相関係数が低い傾向にある 5. コンテンツの凝集性に関する評価るレシピを多く投稿するユーザコミュニティに属しているこ RVwD は近隣ノードの特徴量を含んでいるベクトルであるたれらの各コミュニティでは各料理で類似の具材を使用する傾め隣接ノードの RVwD 間の類似度は相対的に高くなるはず向にある例ジャガイモニンジンカレー粉タマネギがである RVwD でノードをクラスタリングし得られるノードグほとんどすべてのカレーで使用されるそのためそれらのループはノード同士が連結しておりかつ意味的に類似する具材コンテンツが共起する部分を抽出できていると言えるノード群になっていると期待できるこのような性質を有するコミュニティ抽出法を用いれば密につながるノード群を抽ノード群を抽出できることを確認するため複数のクラスタリ出できるしかしながら類似のコンテンツベクトルを有するング結果と比較するこれはコンテンツの凝集性を確認するノード群を抽出できる保証はない一方提案指標のように各意味も含まれているノードに対してコンテンツ分布の集中度を計算することでコ

6 1 Web Wiki Recipe hidden hidden hidden hidden hidden hidden hidden hidden hidden hidden K-medoids K-medoids V v, w V s(v, w) J (P ) = v V max w P {s(v, w)} P K = P K K-medoids K-means s(u, v) RVwD s(u, v) = y u, y v / y u y v s(u, v) = x u, x v / x u x v x CNM Clauset CNM [5] Q = K k=1 ( ekk a 2 k) e kk k a k = K h=1 e kh k Q MST MST [8] 2 J j=1 q(k) j L = K 1 log q (k) k=1 j /q (k) K 1 K q (k) = J j=1 q(k) j 5. 2 V k Z p j = u V x u,j M M M = v V J j=1 x v,j V k q (k) j = u V k x u,j V k j Z z (k) j = q(k) j M k p j Mk p j (1 p j ). M k = v V k J j=1 x v,j V k j (M k p j ) Z K = 10 Web (b) (c) (d) (c) (c) (d) Z (a) 3 Z 3 4(a)

(a) Clustering by RVwDs (b) K-medoids clustering (c) CNM clustering (d) MST cutting 図 4 Web ネットワークのクラスタリング結果 K = 10 (a) Clustering by RVwDs (b)

clustering (d) MST cutting 図 6 Recipe ネットワークのクラスタリング結果 K = 10 図 7 意味的まとまり度の定量評価クラスタに付されたアノテーション特徴量もある程度クラス図8 構造的まとまり度の定量評価図 5 に K = 10 とした際の Wiki

提案手法では第 2 クラており本稿の目的である隣接関係を考慮できていない (c)(d) スタのような画像処理系の教員成果報告ページと第 9 クラではネットワーク構造上綺麗に分割できているが意味的なスタのような Web 系の教員成果報告ページに分けられている部分で分割されている保証はない

7 (a) Clustering by RVwDs (b) K-medoids clustering (c) CNM clustering (d) MST cutting 図 4 Web ネットワークのクラスタリング結果 K = 10 (a) Clustering by RVwDs (b) K-medoids clustering (c) CNM clustering (d) MST cutting 図 5 Wiki ネットワークのクラスタリング結果 K = 10 (a) Clustering by RVwDs (b) K-medoids clustering (c) CNM clustering (d) MST cutting 図 6 Recipe ネットワークのクラスタリング結果 K = 10 図 7 意味的まとまり度の定量評価クラスタに付されたアノテーション特徴量もある程度クラス図8 構造的まとまり度の定量評価図 5 に K = 10 とした際の Wiki ネットワークに対するノータに属するノードの特色を表すものが抽出されている特にド分割結果を示す可視化結果からわかることとして (b) で CNM クラスタリングでは教員成果報告ページとして同一は隣接するノードでも異なるクラスタ色が割り当てられクラスタに分けられていたノード群が提案手法では第 2 クラており本稿の目的である隣接関係を考慮できていない (c)(d) スタのような画像処理系の教員成果報告ページと第 9 クラではネットワーク構造上綺麗に分割できているが意味的なスタのような Web 系の教員成果報告ページに分けられている部分で分割されている保証はないしかし共起ネットワーク提案手法は意味的なまとまりを考慮するため近隣に存在しの性質上ある程度の意味的なまとまりのあるノード群が抽出ていてもコンテンツベクトルが大きく異なれば分離することがされたように見受けれるこれらと比較して推定パラメータを可能である用いた (a) の提案手法では (b) の意味的まとまりと (c) の構

8 3 WebNW WikiNW RecipeNW 1 2 node algorithm image virtual convert 3 4 research year student advisor English E page proceeding transaction press edition 9 model browser object agent function 10 5(a) 3 CNM K = 10 Recipe Z 7 10 Z 7 K-medoids RVwD CNM CNM MST 8 Assortative [1] 8 CNM K-medoids 6. 3 JSPS JSPS 15J00735 [1] Newman, M. E. J.: Assortative mixing in networks, Structure, Vol. 2, No. 4, p. 5 (2002). [2] Freeman, L.: Centrality in social networks: Conceptual clarification, Social Networks, Vol. 1, No. 3, pp (1979). [3] Newman, M. E. J.: Finding community structure in networks using the eigenvectors of matrices, Physical Review E, Vol. 74, No. 3, pp (2006). [4] 8 Web (WebDB Forum2015) (2015). [5] Clauset, A., Newman, M. E. J. and Moore, C.: Finding community structure in very large networks, Physical Review E, Vol. 70, No. 6, pp (2004). [6] Kuramochi, T., Okada, N., Tanikawa, K., Hijikata, Y. and Nishida, S.: Community Extracting Using Intersection Graph and Content Analysis in Complex Network, Proceedings of the 2012 IEEE/WIC/ACM International Joint Conferences on Web Intelligence and Intelligent Agent Technology, WI-IAT 12, Vol. 1, Washington, DC, USA, IEEE Computer Society, pp (2012). [7] Wu, Y., Jin, R., Zhu, X. and Zhang, X.: Finding Dense and Connected Subgraphs in Dual Networks, Proceedings of the IEEE 31st International Conference on Data Engineering (ICDE2015), pp (2015). [8] L1 7 Web (WebDB Forum2014) (2014).

2. Apple iphoto 1 Google Picasa 2 Calendar for Everything [1] PLUM [2] LifelogViewer 3 1 Apple iphoto, 2 Goo

DEIM Forum 2012 D9-4 606 8501 E-mail: {sasage,tsukuda,nakamura,tanaka}@dl.kuis.kyoto-u.ac.jp,,,, 1. 2000 1 20 10 GPS A A A A A A A 2. Apple iphoto 1 Google Picasa 2 Calendar for Everything [1] Email PLUM