正規化最尤符号化に基づくグラフクラスタリング

摘要

本論文では記述長最小化原理に基づく新たなグラフクラスタリングの手法を提案する．グラフクラスタリングとは，グラフが与えられたとき，そのノードを類似する特徴を持つノード同士が同じクラスター（グループ）に入るように分割する問題である．ここでは，グラフの確率構造にナイーブベイズモデルを導入し，グラフを符号化したときの記述長を最小化するという基準のもとでクラスター数を最適化することを考える．具体的にはデータの記述長を最小化することで知られている正規化最尤符号化を用いる．また，既存のAICやBICといった基準と収束速度を比較することによって本手法の有効性を検証することとする．%This paper addresses the issue of graph clustering, i.e., assigning nodes for a given graph into a number of clusters, in each of which similar nodes are grouped together. We propose a novel method of graph clustering from the view of the minimum description length principle. In it we employ a Naive Bayes model for the representation of a probabilistic structure of a graph and select the number of optimal clusters so that the total codelength required for encoding the graph is minimum. Specifically we employ the normalized maximum likelihood coding technique in the codelength computation, which achieves the shortest codelength over possible coding ones and is implemented efficiently. We empirically demonstrate the effectiveness of the proposed method in terms of the rate of convergence of the selected number of clusters in comparison with AIC and BIC.