GraphX Advent Calendar - Day 16 - クラスタリング・モジュラリティ計算

f:id:teppei-studio:20100306105411j:plain

GraphX Advent Calendar 2014 - Adventar 16日目です。

今日からはクラスタリングを見ていきます

クラスタリングで一般的なのは K-means 法に代表される距離によって分類していくやり方ですが、グラフ分析では「密度」で計測します。辺による繋がりによる頂点の密度が高くなるグループを作って、クラスタリングしていきます。

グラフ分析でもクラスタリングの手法にはいろいろありますが、今日はそのクラスタリングの指標の計算を見ていきます。この指標をモジュラリティと言います。

モジュラリティ計算方式

※ 当初はこのスライドを使って計算式の説明をしていましたが、いくつか誤りがあるようなので、訂正します。

モジュラリティの計算方式は、以下のようになります。

{ \displaystyle
Q = \sum_{i}\left(e_{ii} - \left(\sum_{j}e_{ij}\right)^2\right) = \sum_{i}\left(e_{ii} - a_{i}^2\right)
}

数式ワカラナイ…

でも頑張って説明したいと思います。

まずは、考え方ですが、一言で言うと、「クラスタ内部の辺の数が、クラスタ間の辺の数と比べて、多ければ密度が高い」というような考え方になります。

次に式中の記号については、それぞれ以下の通りになります。

{ \displaystyle e_{ii} } 「総エッジ本数」に対する、コミュニティi内部における「ノード毎のエッジ本数の総和」の割合
{ \displaystyle e_{ij} } 「総エッジ本数」に対する、コミュニティiからjに張られているエッジ本数の割合
{ \displaystyle a_{i} } 「総エッジ本数」に対する、コミニティiから張られているエッジ本数の割合

次に、以下のようなグラフとクラスタリングのモジュラリティ計算について見てみます。

f:id:teppei-studio:20150104215525p:plain

A B C D E F G H I J K
総エッジ数 クラスタ クラスタ内エッジ本数 C/A クラスタ1エッジ数 クラスタ2エッジ数 クラスタ3エッジ数 E/A F/A G/A D-(D+H+I+J)^2
24 Cluster1 6 0.25 0 1 1 0 0.04167 0.04167 0.1389
24 Cluster2 6 0.25 1 0 1 0.04167 0 0.04167 0.1389
24 Cluster3 6 0.25 1 1 0 0.04167 0.04167 0 0.1389

このK列の値を合計すると、0.4167になります。これがモジュラリティの値となります。

実装

上記の式を実装してみました。

def modurality(graph:Graph[Int, Int]):Float = {

	// クラスタ内のEdge数を取得(双方向で計上するので2倍しておく)
	def edgesCntOfCluster(graph:Graph[Int, Int], cluster:Int):Float = {
		graph.subgraph(vpred = (vid, attr) => attr == cluster).edges.count.toFloat * 2
	}

	// クラスタ間にまたがるEdge数を取得(これは重複カウントしない)
	def edgesCntBetweenClusters(graph:Graph[Int, Int], clusterAandB:Set[Int]):Float = {
		if(clusterAandB.size != 2) throw new Exception("Args Set of clusterAandB must be size 2")
		graph.subgraph(epred = { edge => 
			if(edge.srcAttr == clusterAandB.head && edge.dstAttr == clusterAandB.tail.head) true
			else if(edge.srcAttr == clusterAandB.tail.head && edge.dstAttr == clusterAandB.head) true
			else false
		}).edges.count.toFloat
	}

	def clusterPairsContains(clusterPairs:Set[Set[Int]], cluster:Int):Set[Set[Int]] = {
		clusterPairs.filter(cp => cp.contains(cluster))
	}

	// グラフ内Edge総数(双方向で計上するので2倍しておく)
	val edgesCnt:Float = graph.edges.count.toFloat * 2
	// println("--- edgesCnt : " + edgesCnt)

	// クラスタIDのリストを取得する
	val clusters:Array[Int] = graph.vertices.map(v => (v._2,1)).groupBy(g => g._1).map(g => g._1).collect

	// println("--- clusters")
	clusters.foreach(println(_))

	var clusterPairs = Set[Set[Int]]()
	for( c1 <- clusters ) yield {
		for( c2 <- clusters ) {
			if(c1 != c2) clusterPairs = clusterPairs + Set(c1, c2)
		}
	}
	// println("--- clusterPairs.size : " + clusterPairs.size)
	// println("--- clusterPairs")
	clusterPairs.foreach(println(_))

	var mod:Float = 0.0F
	for( c <- clusters ){
		val ecoc = edgesCntOfCluster(graph, c)
		// println("------ edgesCntOfCluster : " + ecoc)

		var aii = ecoc / edgesCnt

		val cpc = clusterPairsContains(clusterPairs, c)

		for(cp <- cpc) {
			val ecbc = edgesCntBetweenClusters(graph, cp)
			aii = aii + (ecbc / edgesCnt)
		}

		mod = mod + (( ecoc / edgesCnt ) - ( aii * aii))
	}

	// println("--- mod : " + mod )
	return mod
}

なんかもっといい実装がありそうな気がしますが、ひとまずは動きました。

次回予告

ひきつづき、クラスタリングに関わる処理を見ていきたいと思います。

今日のソースは、こちらをご参照ください。

graphx-advent-samples/Day16.scala at master · ironpeace/graphx-advent-samples · GitHub