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

Abstract

此論文旨在探究隨機區塊模型 (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.