統計觀點下的叢集偵測問題

Community Detection: A Statistical Approach

林宗毅(Chung-Yi Lin)

指導教授 ： 王奕翔

國立臺灣大學/電機資訊學院/電信工程學研究所/碩士(2018年)

https://doi.org/10.6342/NTU201803335

摘要

此論文旨在探究隨機區塊模型 (SBM) 中的叢集偵測問題。上半部討論叢集偵測問題從一般圖至超圖中的延伸。我們提出一更一般化之超圖生成模型 (d-hSBM)，且完成其中漸進極小化極大錯誤率之刻畫。上界部分，於數量級為 3 時首先由最大似然估計元達成；其後，我們提出一有效率之二步驟演算法，並證明其可於任意數量級之隨機超圖模型中，有此極小化極大最佳錯誤率之表現。下界部分之匹配，則是經由指認一包含最主要錯誤事件之子參數空間所達成。此論文之下半部份考慮如何估計叢集個數此一分群問題中之子問題。作為一初步理論嘗試，我們證明了最大似然估計元之統計一致性；所得之上界結果也間接暗示了此叢集個數估計問題允許一數量級上更稀疏之隨機圖。此外，我們亦提出一基於頻譜間隔之 EigenGap 演算法，並展示其統計一致性。於生成資料點與實際資料集上的實驗結果在在印證了我們的理論發現。

關鍵字

分類 ； 叢集偵測 ； 隨機區塊模型 ； 超圖 ； 極小化極大錯誤率 ； 瑞尼發散項 ； 二步驟演算法 ； 區塊個數估計 ； 圖拉普拉斯矩陣 ； 克-史門檻 ； 頻譜演算法

並列摘要

The problem of community detection in the Stochastic Block Model SBM is considered. The first half of this thesis is devoted to the community detection problem extended from graphs to hypergraphs. We propose a more general hypergraph generative model termed d-hSBM, and characterize the asymptotic misclassification ratio in the minimax sense under it. Achievability part is settled first information-theoretically with the Maximum Likelihood Estimator (MLE) under 3-hSBM and then computation-efficientlly with a two-step algorithm for any order d-hSBM. The converse lower bound is set by finding a smaller parameter space which contains the most dominant error events. The second half of this thesis considers the problem of estimating the number of communities itself apart from the clustering task. As an attempt to characterize the fundamental limit in such formulation, we demonstrate that the MLE, which is optimal under a Bayesian perspective, is consistent, whose form might further endorse a sparser connectivity level. In addition, an efficient spectral method EigenGap is proposed along with a theoretical guarantee. Experimental results on both synthetic data and real-world data consolidate our theoretical finding.

並列關鍵字

clustering ； community detection ； stochastic block model ； hypergraph ； minimax risk ； Rényi divergence ； two-step algorithms ； block-number estimation ； graph Laplacian ； Kesten-Stigum threshold ； spectral algorithms

參考文獻

[1] E. Abbe. Community detection and stochastic block models: recent developments. Journal of Machine Learning Research, 18(177):1 – 86, 2017.

[2] E. Abbe, A. S. Bandeira, and G. Hall. Exact recovery in the stochastic block model. IEEE Transactions on Information Theory, 62(1):471–487, 2016.

[3] E. Abbe and C. Sandon. Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery. 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 670–688, Oct 2015.

[4] E. Abbe and C. Sandon. Recovering communities in the general stochastic block model without knowing the parameters. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems 28, pages 676–684. Curran Associates, Inc., 2015.

[5] E. Abbe and C. Sandon. Achieving the ks threshold in the general stochastic block model with linearized acyclic belief propagation. In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems 29, pages 1334–1342. Curran Associates, Inc., 2016.