グラフデータに対する知識融合型クラスタリング技法の開発代表研究者濵	  砂	  幸	  裕近畿大学	  理工学部情報学科	  講師1 はじめに大量のデータを扱う様々な分野において、大規模データマイニングの重要性は極めて強く認識されている。
データ解析手法の中でも、クラスタリングはデータの規則性や構造を明らかにする有用な手法として知られている。クラスタリングとは、対象とするデータを複数のクラスタに分割するデータ解析手法である[1]。クラスタとは複数のデータの集まりであり、類似した特徴や性質を持つデータが同じクラスタに含まれるよう分類される。クラスタリングの応用分野は自然科学、社会科学など多岐に渡り、情報通信機器の性能向上、低コスト化により、様々な自然現象や社会現象が観測され、大規模・複雑なデータベース上に蓄積されている。特に近年では、ソーシャルデータや EC サイト上の商品ネットワークなど、大規模データに潜む因果関係や相互作用の解析を目的として、グラフデータに対するクラスタリング（グラフクラスタリング）が大きな期待を寄せられている[2]。
クラスタリングを構成する技法の中でも、ファジィクラスタリングは、人間の感覚に合った柔軟な処理を実現することから、理論・応用の両面において、盛んに研究が進められており、その有用性は高く評価されている[3,4]。申請者がこれまでに取り組んできた知識ベースに基づくクラスタリング（知識融合型クラスタリング）の高度化においても、ファジィクラスタリングの諸技法は重要な役割を担ってきた[5,6,7]。例えば、「欠損データは特徴空間の全ての値を取り得る」、「同じクラスタに所属する個体は互いに近い位置に存在する」、「データが密な領域をコアクラスタとする」、といった人間が持つ知識を、ファジィクラスタリングの諸技法を援用することでクラスタリングの枠組みに取り込み、不確実データ解析、半教師学習、クラスタ数推定などを実現する新たなクラスタリング技法を開発した。これらの成果から、人間が持つ知識とクラスタリングの融合により柔軟な処理を実現する知識融合型クラスタリングにおいては、解析対象や目的に適合した知識が人間の直感にあった柔軟な処理を実現することを明らかにした。しかしながら、グラフデータに対する知識融合型クラスタリングはほとんど議論されておらず、これまでに蓄積されたファジィクラスタリングに関する数々の技法や知見が活用されていない現状にある。	  そこで本研究では、大規模グラフデータのマイニングをターゲットとして、新たな知識融合型クラスタリング技法を開発することを目的とする。特に、ファジィクラスタリングの技法を用いて、グラフデータに対して人間が持つ知識をモデル化することで、新たなデータ解析の方法論を確立する。先に述べたように、知識融合型クラスタリングでは、解析対象に適合した知識ベースを構築することで人間のような柔軟な処理が可能となる。そこで、この発想を基に、グラフデータに対する知識ベースを構築すれば、既存のクラスタリングでは成し得なかった、大規模グラフデータの柔軟な解析が可能となる。簡潔に言うと、本研究課題の大要は、グラフデータに対する人間の知識のモデル化を着想とする新たな知識融合型クラスタリングの確立である。	  本研究課題では、グラフデータに対する知識ベースの構築とファジィクラスタリングの技法を用いたモデル開発を通じて、大規模グラフデータに対する新たなデータ解析の方法論を確立するという観点から、課題 1：グラフデータに対する知識ベース構築と数理モデル開発、課題 2：構築したモデルに基づくグラフクラスタリング手法の新規開発、課題 3：実データを用いた数値実験による開発手法の評価と技法の包括的発展、以上 3 つの課題を設定した。課題 1 は、グラフデータの性質、アルゴリズムの分類規則、クラスタ構造の評価などの観点から、グラフクラスタリングに関する知識ベースの構築および数理モデルの開発を目的としている。次に課題 2 は、構築した知識ベースと開発した数理モデルに基づいて、新たな知識融合型クラスタリングの開発および評価を目的としている。また課題 3 は、開発した知識融合型クラスタリングを用いた実データの解析事例を蓄積し、実用化に必要となる項目の改善を目的としている。これまでのところ、課題 1 に関する検討として、グラフクラスタリングにおける代表的な評価基準である Modularity[8]とクラスタリングにおける伝統的な評価指標である妥当性基準[9]との比較を行った（発表資料 1）。次に、課題 1 の検討を基に、妥当性基準の一つである Dunn’s index[10]に基づくアルゴリズムを開発した（発表資料 2）。また、大規模グラフデータの解析を目的として、比較的規模の大きなデータを用いた解析事例の蓄積を進めている。以降、本申請課題の関連研究および実施内容を述べ、最後に今後の展望と自己評価を述べる。
1	 	 （公財）電気通信普及財団 研究調査助成報告書 No.32 2017	 

2 関連研究2-1 k-medoids 型クラスタリング代表的なクラスタリング手法である k-means では、クラスタの代表点としてクラスタに所属する個体の中心を用いる[1]。一方、k-medoids では、メドイドと呼ばれるクラスタの代表点を解析対象となる個体から選択するため、距離行列、隣接行列、類似度行列で表されるデータを分割することが可能である[11]。k-medoidsの目的関数𝐽!" 、帰属度に関する制約条件𝑈! 、メドイドの重みに関する制約条件𝑊! は以下で表される。	 	 	 	 	 	 	 	 	 
	 	 ここで、𝑢!" は帰属度と呼ばれ、個体 k のクラスタ i への所属度合いを意味している。𝑤!" はメドイドを決定する重みであり、k-medoids では、𝑤!" = 1となる t 番目の個体がクラスタ i の代表点となる。また、𝑟!" は k 番目の個体と t 番目の個体間の関係性を表しており、隣接行列をはじめとして類似度行列や非類似度行列を用いることも可能である。	  𝑢!" 、𝑤!" の解は以下で表される。	 	 	 	 	 	 	 	 	  k-medoids のアルゴリズムは、式(1)、（2）を用いた交互最適化により構成され、与えられた n 個のデータを c 個のクラスタに分割する。k-medoids のアルゴリズムを以下に示す。	 	 	 	 	 	 	 	 	 	 
	 	 アルゴリズムの収束条件として、最大繰り返し回数の設定、目的関数の収束、各変数の収束が用いられる。	 
	 	 2	 	 （公財）電気通信普及財団 研究調査助成報告書 No.32 2017	 2-2 妥当性基準妥当性基準はクラスタ分割を定量的に評価し、適切なクラスタ数を決定する際に用いられる指標であり、古くから研究が進められている[9]。妥当性基準の多くは、クラスタ内の個体が密集している度合いを表す凝集度、クラスタ間が分離している度合いを表す分離度の 2 つで構成される。代表的な妥当性基準として、本研究では主に、Dunn’s index[10]、Davies-Bouldin’s index[12]、ファジィ共分散行列のトレース[13]、Xie-Beni’sindex[14]を用いた。それぞれの指標について以下に示す。
Dunn’s index はクラスタの凝集度をdia(𝐺! )、クラスタ間の分離度をdis(𝐺! , 𝐺! )とし、以下で表される[10]。	 	 	 	 	 	 	 	 	 	 𝑑(𝑥, 𝑦)はクラスタリングに用いられる非類似度である。dia(𝐺! )は各クラスタ内で最大となる非類似度を意味しており、dis(𝐺! , 𝐺! )は 2 つのクラスタ間で最小となる個体間の非類似度を意味している。Dunn’s index はその値 DI が大きいときに、良好なクラスタ分割であると評価する指標である。
Davies-Bouldin’s index は、クラスタ内の個体とクラスタ中心との非類似度の平均𝑠! 、クラスタ間非類似度𝑅!"を用いて以下で表される[12]。	 	 	 	 	 	 	 	 	 
	 	 ここで、|𝐶! |はクラスタ i 内の個体数を意味している。Davies-Bouldin’s index は、その値 DB が小さいときに良好なクラスタ分割であると評価する指標である。また、Davies-Bouldin’s index の帰属度をファジィ化した指標も提案されている[15]。ファジィ共分散行列のトレースは、ファジィなクラスタ分割に基づいた指標として提案されている[13]。
トレースではなく行列式を用いた指標も提案されているが、本研究では幾何的形状を考察するという観点から以下で表されるトレースのみを用いた。	 	 	 	 	 	 	 
	 	 ここで、𝑚 > 1はファジィ化パラメータである。ファジィ共分散行列のトレースは、その値が小さいとき

3	 	 （公財）電気通信普及財団 研究調査助成報告書 No.32 2017	 に良好なクラスタ分割であると評価する指標である。	  Xie-Beni’s index もファジィなクラスタ分割に基づいた指標として提案されており、ファジィ c-means の目的関数を個体数で割った値を凝集度とし、クラスタ中心間の最小距離を分離度として構成された指標である[14]。	 	 	 	 
	 	 Xie-Beni’s index は、その値 XB が小さいときに良好なクラスタ分割であると評価する指標である。	  ここで紹介した妥当性基準の他にも帰属度のみで構成される分割係数[9]などの指標も知られているが、詳細な説明は省略する。また、妥当性基準はカーネル法を用いた拡張も提案されており、複雑なデータの定量的評価あるいは最適なクラスタ数の決定に適用することも可能である[15]。	 
2-3 ModularityModularity はグラフデータの定量的な評価基準として提案された指標である。グラフデータに対する代表的な分類手法である Louvain 法は、Modularity の局所最適化に基づく手法として知られている[8]。Modularityはクラスタ内のエッジが密で、クラスタ間のエッジが疎であるときに良好なクラスタ分割であると評価する指標である。Modularity は以下で表される。	 	 	 
	 	 ここで、𝑎!" は隣接行列の成分を意味し、𝑀は隣接行列の総和、deg! は k 番目のノードの次数を表している。
隣接行列の代わりに類似度行列を用いることも可能である。Modularity は、その値 Q が大きいときに良好なクラスタ分割であると評価する指標である。	 

3 妥当性基準によるグラフデータの評価はじめに、本研究課題で取り組んだ、妥当性基準によるグラフデータの評価について説明する。先に述べたように、妥当性基準はクラスタリングにおける伝統的な評価指標であり、Modularity はグラフデータに対する定量的な評価指標であることから、これらの指標の有用性、関連性を議論し、その性質を明らかにすることを目的として数値実験による比較を行った。はじめに、数値実験の条件と使用したデータセットについて説明する。次に、数値実験の詳細を述べ、その後、グラフデータに対する妥当性基準の有用性を示す。
今回実施した数値実験では、以下に図示する 6 種類の人工データを用いた。各データのエッジ上の数値はエッジの重みを意味しており、ノード上の数値はノード番号を意味している。これらのデータセットに対して、k-medoids を適用し、得られたクラスタ分割に対して、それぞれの妥当性基準および Modularity による評価を行った。k-medoids を適用する際に、エッジが存在しないノード間の重みはダイクストラ法を用いて最小距離を計算し、その値をエッジの重みとした。また、初期値を変えて 100 回実行し、その平均値、標準偏差、目的関数の値が最小になったときの指標の値を評価した。また、以下の式により重みを類似度に変換したLouvain 法を比較対象とした。	 	 	 	 	 4	 	 （公財）電気通信普及財団 研究調査助成報告書 No.32 2017	 さらに、k-medoids で得られたメドイドを基に、2 種類のファジィ c-means[3,4]から得られる帰属度の更新式を用いて、ファジィな分割による評価も行った。ファジィな分割を得るための帰属度の更新式は以下で表される。	 	 	 	 	 
	 	 これらの更新式は、標準型ファジィ c-means（sFCM）、エントロピー型ファジィ c-means（eFCM）から得られるものであり、ファジィな分割の形状が異なっている。ここで、𝑚 > 1、𝜆 > 0はファジィ化パラメータであり、本実験では𝑚 = 2、𝜆 = 0.1とした。
実験に使用した 6 種類の人工データの詳細を以下に示す。また、適切なクラスタ分割を想定した結果について以下に図示する。	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 5	 	 （公財）電気通信普及財団 研究調査助成報告書 No.32 2017	 これらの人工データに対して、クラスタ数を 2 から 6 まで変化させて実行した結果を次に示す。ここでは、特徴的な結果となった Data 3 と Data 5 に対する Dunn’s index と Modularity の結果をそれぞれ示す。	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 	 
	 	 妥当性基準の平均値を見ると、4 つのクラスタを想定した Data 3 に対して、Dunn’s index、Modularity はともに最適なクラスタ数の推定に失敗していることが確認できる。また、5 つのクラスタを想定した Data 5に対しては Dunn’s index のみが適切なクラスタ数の推定に成功していることが確認できる。このような評価を 6 種類の人工データに対して、それぞれの妥当性基準を適用した結果を Table 2 に示す。Table 2 の中で、「○」は適切なクラスタ数の推定に成功したことを意味しており、「-」は失敗を意味している。また、sFCM、eFCM はそれぞれの更新式を用いてファジィ化妥当性基準を用いた場合に推定が成功したことを意味している。表中の PC、PE、MPC は 2-2 で省略した帰属度のみで構成された分割係数による指標を意味している。
これらの結果から、今回実験を行った妥当性基準の中では Dunn’s index が最も良好な結果を得ていることが確認できる。また、一般に有効な指標とされているファジィ共分散行列のトレースや Xie-Beni’s index がグラフデータの評価については十分な性能を有していないことが確認できる。また、グラフデータの評価に対しるベンチマーク的指標である Modularity もグラフデータの形状によっては十分に機能しないことが確認された。今回の数値実験からは、Dunn’s index がグラフデータに対する有効な指標と考えられる。しかしながら、クラスタ内の最長距離とクラスタ間の最短距離の比率で構成されるシンプルな指標であるため、なぜグラフデータの評価に有効であるかの検証には至っていない。そこで、比較的規模の大きなグラフデータに対して同様の数値実験を行い、それぞれの指標について詳細な検討を行うことが課題として挙げられる。

6	 	 （公財）電気通信普及財団 研究調査助成報告書 No.32 2017	 	 	 	 	 	 	 	 4 妥当性基準を用いたグラフクラスタリング上記の検討を基に、Dunn’s index を用いた新たなグラフクラスタリング手法を構築し、その特性についてLouvain 法との比較検討を行った。Louvain 法はグラフデータの評価指標である Modularity の局所最適化に基づく手法である[8]。これまでの検討で Dunn’s index のグラフデータに対する有効性が確認できたことから、Louvain 法と同様の手続きで構成される、妥当性基準に基づくグラフクラスタリング手法を提案した。提案手法は、妥当性基準を結合基準とする階層的クラスタリングとみなすことができるため、提案手法を妥当性基準の局所最適化に基づく階層的クラスタリング（AHCL）と呼ぶ。ACHL のアルゴリズムを以下に示す。

次に、人工データを用いた数値実験により提案手法と Louvain 法の比較を行った。ここで用いた人工データは、Polaris データと呼ばれる 2 次元空間のデータを基に作成したグラフデータであり、ノード数 51、エッジ数 205、クラスタ数 3 のデータセットである。人工データに対して、提案手法と Louvain 法をそれぞれ適用し、adjusted rand index (ARI)[16]による評価を行った。ARI は、2 つのクラスタ分割の一致度合いを測る指標であり、値が 1 のときに、2 つのクラスタ分割が完全に一致していることを示している。今回の実験結果では、提案手法による ARI の値は 1 となり、正解例と完全に一致する結果となった。一方、Louvain 法による ARI の値は、-0.023 となり非常に小さい値となった。こちらの数値実験については、解析事例を十分に蓄積したとは言い難い。そのため、同様のデータセットや比較的規模の多きベンチマークデータを用いて同様の数値実験を行い、提案手法の有効性についてより詳細に検討を進める必要があると考えている。また、Dunn’s index を変形した指標や、その他の妥当性基準を用いたアルゴリズムを検討し、どういった特性をもつ指標が、提案手法において分類性能の向上とアルゴリズムの高速化に適しているか考察し、大規模グラフデータの解析を実現するアルゴリズムの構築が不可欠と考えている。

7	 	 （公財）電気通信普及財団 研究調査助成報告書 No.32 2017	
 5 まとめ本研究課題では、グラフデータに対する知識ベースの構築とファジィクラスタリングの技法を用いたモデル開発を通じて、大規模グラフデータに対する新たなデータ解析の方法論を確立することを目的とし、課題1：グラフデータに対する知識ベース構築と数理モデル開発、課題 2：構築したモデルに基づくグラフクラスタリング手法の新規開発、課題 3：実データを用いた数値実験による開発手法の評価と技法の包括的発展、以上 3 点に取り組んだ。これまでの検討を継続的に発展させることにより、グラフクラスタリングにおける知識ベース構築、ファジィクラスタリングの技法を援用したモデル開発、新たなグラフクラスタリング手法が達成できると考えている。
本研究課題の最終的な自己評価は、（１）新たなグラフクラスタリング手法を確立し、既存手法と比較した優位性を示せたか（２）知識融合型クラスタリングが大規模データマイニング実現の糸口となることを示せたか（３）大規模データマイニングを可能とする新たなデータ解析の方法論を構築できたか以上の 3 点から行うこととなる。これらのいずれか 1 つでも達成できれば十分な成果と考えているが、本研究は、ファジィクラスタリングを橋梁とし、人間の知識とクラスタリングを結びつけ、大規模データを柔軟に処理する解析手法を開発することにとどまらず、知識融合の観点から、新たなデータ解析の方法論の礎を築くことを見据えている。本研究の成果によって、クラスタリングのみならず、グラフのリンク予測、重み予測などの関連分野に継続的に取り組み、大規模グラフデータを解析する知識融合型クラスタリングの高度化を進めることを計画している。
	 	 【参考文献】	 [1] Jain A. K., Data clustering: 50 years beyond $K$-means, Pattern Recognition Letters, Vol. 31,No. 8, pp. 651-666, 2010.
[2] M. Newman, `Networks: An Introduction', Oxford University Press, New York, 2010.
[3] J. C. Bezdek, `Pattern Recognition with Fuzzy Objective Function Algorithms', Plenum Press,New York, 1981.
[4] S, Miyamoto, H. Ichihashi, and K. Honda, `Algorithms for Fuzzy Clustering', Springer,Heidelberg, 2008.
[5] Y. Hamasuna, Y. Endo, Y. Hasegawa, and S, Miyamoto, Two Clustering Algorithms for Datawith Tolerance based on Hard c-Means, 2007 IEEE International Conference on Fuzzy Systems(FUZZ-IEEE2007), pp. 688-691, 2007.

8	 	 （公財）電気通信普及財団 研究調査助成報告書 No.32 2017	 [6] Y. Hamasuna, Y. Endo, On Semi-supervised Fuzzy c-Means Clustering for Data withClusterwise Tolerance by Opposite Criteria, Soft Computing, Vol. 17, No. 1, pp. 71-81, 2013.
[7] Y. Hamasuna, Y. Endo, On A Family of New Sequential Hard c-Means, Journal of AdvancedComputational Intelligence and Intelligent Informatics (JACIII), Vol. 19, No. 6, pp. 759-765,2015.
[8] V. D. Blondel, J.-L. Guillaum, R. Lambiotte, and E. Lefebvre, Fast unfolding of communities inlarge networks, J. of Statistical Mechanics: Theory and Experiment, p. P10008, 2008.
[9] W. Wang, Y. Zhang, On fuzzy cluster validity indices, Fuzzy Sets and Systems, Vol. 158, No. 19,pp. 2095-2117, 2007.
[10] J. C. Dunn, Well separated clusters and optimal fuzzy partitions, Journal of Cybernetics, Vol. 4,pp. 95–104, 1974.
[11] L. Kaufman, P. J. Rousseeuw, `Finding Groups in Data: An Introduction to Cluster Analysis',Wiley, New York, 1990.
[12] D. L. Davies, D. W. Bouldin, A cluster separation measure, IEEE Transactions on PatternAnalysis and Machine Intelligence, Vol.1, No.2, pp. 224-227,1979.
[13] I. Gath, A. B. Geva, Unsupervised optimal fuzzy clustering, IEEE Trans. on Pattern Analysisand Machine Intelligence, Vol. 11, No. 7, pp. 773-780, 1989.
[14] X. L. Xie, G. Beni, A validity measure for fuzzy clustering, IEEE Transactions on PatternAnalysis and Machine Intelligence, Vol. 13, No. 8, pp. 841-847, 1991.
[15] W. Hashimoto, T. Nakamura, S. Miyamoto, Comparison and Evaluation of Different ClusterValidity Measures Including Their Kernelization, Journal of Advanced ComputationalIntelligence and Intelligent Informatics (JACIII), Vol. 13, No. 3, pp. 204-209, 2009.
[16] L. Hubert, P. Arabie, Comparing Partitions, Journal of Classification, Vol. 2, No. 1,pp. 193-218, 1985.	 
〈発	  表	  資	  料〉	 
題	  	  名	 掲載誌・学会名等	 

発表年月	 グラフクラスタリングに対する妥当性基準に関する一考察Agglomerative Hierarchical ClusteringBased on Local Optimization for ClusterValidity Measures第 26 回インテリジェント・システム・シンポジウムThe2017thInternationalConference on Systems, Man andCybernetics (IEEE SMC2017)	 	 	 	 	 	 2016 年 10 月2017 年 10 月(Accepted)

	 	 9	 	 （公財）電気通信普及財団 研究調査助成報告書 No.32 2017