转载自https://www.cnblogs.com/porco/p/xmeans_intro.html，后续有时间看完原论文后再更新，先占坑。

本文基于《X-means》和《BIC-notes》（原论文中BIC公式有误，这是对BIC的补充）

K-means的缺点

• 每一轮迭代的计算花费大
• 需要用户指定K
• 易于收敛到局部最优解

X-means的改进

• 使用kd-tree加速原K-means的每一轮迭代
• 用户指定K所属的范围，根据BIC score选到最优K
• 每一轮迭代只进行2-means（2-means对局部最优解不敏感）

X-means算法步骤

算法

用户输入 kmin k m i n <script type="math/tex" id="MathJax-Element-2844">k_{min}</script>, kmax k m a x <script type="math/tex" id="MathJax-Element-2845">k_{max}</script>，数据集 D D <script type="math/tex" id="MathJax-Element-2846">D</script>
1、运行Kmin−means $K_{min}-means$<script type="math/tex" id="MathJax-Element-2847">K_{min}-means</script>。
2、在每个聚类上，运行2-means。
3、根据BIC score（只在该聚类上计算，即只计算本聚类数据只分成1类和两类时的BIC score）决定是否二分聚类。
4、如果 K<Kmax K < K m a x <script type="math/tex" id="MathJax-Element-2848">K

样例
1、首先将DD分成3个聚类
2、再将每个子聚类分成2个聚类
3、计算BIC score决定是否二分

BIC score(Bayesian Information Criterion)

• BIC(ϕ)=lϕ^(D)−pϕ2⋅logR B I C ( ϕ ) = l ϕ ^ ( D ) − p ϕ 2 ⋅ l o g R <script type="math/tex" id="MathJax-Element-2849">BIC(ϕ)=\hat{l_ϕ}(D)−\frac{p_ϕ}{2}⋅logR</script>
  其中 ϕ ϕ <script type="math/tex" id="MathJax-Element-2850">ϕ</script>表示模型，lϕ^(D) $\widehat{l_{\varphi }}(D)$<script type="math/tex" id="MathJax-Element-2851">\hat{l_ϕ}(D)</script>为likelihood， pϕ p ϕ <script type="math/tex" id="MathJax-Element-2852">{p_ϕ}</script>为模型的复杂度（自由参数个数）
• X-means的假设：identical spherical assumption
  数据由 X X <script type="math/tex" id="MathJax-Element-2853">X</script>个高斯函数产生，每个高斯函数有一样的方差σ $\sigma$<script type="math/tex" id="MathJax-Element-2854">σ</script>(每个维度上的变量不相关，协方差矩阵为diag(σ))、不同的 μi μ i <script type="math/tex" id="MathJax-Element-2855">μ_i</script>；
  数据生成时，根据概率 pi p i <script type="math/tex" id="MathJax-Element-2856">p_i</script>选择一个高斯函数 gi g i <script type="math/tex" id="MathJax-Element-2857">g_i</script>，然后生成一个点。
  所以似然函数为：
  lϕ(D)=∑Ri=1[logp(g(i))+logp(xi)] l ϕ ( D ) = ∑ i = 1 R [ l o g p ( g ( i ) ) + l o g p ( x i ) ] <script type="math/tex" id="MathJax-Element-2858">l_ϕ(D)=\sum_{i=1}^{R}[log p(g_{(i)})+log p(x_i)]</script>
  其中 p(g(i)) p ( g ( i ) ) <script type="math/tex" id="MathJax-Element-2859">p(g_{(i)})</script>为生成点 xi x i <script type="math/tex" id="MathJax-Element-2860">x_i</script>的高斯函数被选到的概率。
• 计算BIC，需要计算最大化的 lϕ^(D) l ϕ ^ ( D ) <script type="math/tex" id="MathJax-Element-2861">\hat{l_ϕ}(D)</script>,所以需要对参数进行估计
  p(gk)=RkR p ( g k ) = R k R <script type="math/tex" id="MathJax-Element-2862">p(g_k)=\frac{R_k}{R}</script>
  σ2=1MR∑Kk=1∑xi∈Dk∥xi−μk∥∥2 σ 2 = 1 M R ∑ k = 1 K ∑ x i ∈ D k ∥ x i − μ k ∥ 2 <script type="math/tex" id="MathJax-Element-2863">σ^2=\frac{1}{MR}\sum_{k=1}^{K}\sum_{x_i \in D_k}^{ }∥x_i−μ_k∥^2</script>
  文中使用无偏估计，即 σ2=1M(R−K)∑Kk=1∑xi∈Dk∥xi−μk∥∥2 σ 2 = 1 M ( R − K ) ∑ k = 1 K ∑ x i ∈ D k ∥ x i − μ k ∥ 2 <script type="math/tex" id="MathJax-Element-2864">σ^2=\frac{1}{M(R-K)}\sum_{k=1}^{K}\sum_{x_i \in D_k}^{ }∥x_i−μ_k∥^2</script>
• pϕ p ϕ <script type="math/tex" id="MathJax-Element-2865">p_ϕ</script>自由参数个数
  K-1个高斯函数选择到的概率，MK 个每个高斯函数每个维度上的mean，1个方差
  所以 pϕ=(M+1)K p ϕ = ( M + 1 ) K <script type="math/tex" id="MathJax-Element-2866">p_ϕ=(M+1)K</script>