[x-means] 1.x-means简介

本文基于《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算法步骤

• 用户输入 (k\_{min},k\_{max})，数据集 (D)

1. 运行(K_{min})-means
2. 在每个聚类上，运行2-means
   根据BIC score（只在该聚类上计算，即只计算本聚类数据只分成1类和两类时的BIC score）决定是否二分聚类
3. 如果(K<K_{max})，继续进行步骤2，否则返回结果

• 样例

1. 首先将(D)分成3个聚类
2. 再将每个子聚类分成2个聚类
   计算BIC score决定是否二分
   

BIC score(Bayesian Information Criterion)

• (BIC(phi)=hat{l_{phi}}(D)-frac{p_{phi}}{2}cdot log R)
  其中(phi)表示模型，(hat{l_{phi}}(D))为likelihood，(p_{phi})为模型的复杂度（自由参数个数）
• X-means的假设：identical spherical assumption
  数据由X个高斯函数残生，每个高斯函数有一样的方差(sigma)(每个维度上的变量不相关，协方差矩阵为(diag(sigma)))、不同的(mu_i)；
  数据生成时，根据概率(p_i)选择一个高斯函数(g_i)，然后生成一个点
  所以似然函数为：
  (l_{phi}(D) = sum_{i=1}^R [log p(g_{(i)})+log p(x_i)])
  其中(p(g_{(i)}))为生成点(x_i)的高斯函数被选到的概率
• 计算BIC，需要计算最大化的(hat{l_{phi}}(D)),所以需要对参数进行估计
  (p(g_k)=frac{R_k}{R})
  (sigma^2=frac{1}{MR}sum_{k=1}^{K}sum_{x_iin D_k}{left|x_i-mu_k ight|}^2)
  文中使用无偏估计，即(sigma^2=frac{1}{M(R-K)}sum_{k=1}^{K}sum_{x_iin D_k}{left|x_i-mu_k ight|}^2)
• (p_{phi})自由参数个数
  K-1个高斯函数选择到的概率，MK 个每个高斯函数每个维度上的mean，1个方差
  所以(p_{phi}=(M+1)K)

KD-tree加速K-means