本文基于《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决定是否二分
    [x-means] 1.x-means简介-LMLPHP

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_i\in D_k}{\left\|x_i-\mu_k\right\|}^2\)
    文中使用无偏估计,即\(\sigma^2=\frac{1}{M(R-K)}\sum_{k=1}^{K}\sum_{x_i\in D_k}{\left\|x_i-\mu_k\right\|}^2\)
  • \(p_{\phi}\)自由参数个数
    K-1个高斯函数选择到的概率,MK 个每个高斯函数每个维度上的mean,1个方差
    所以\(p_{\phi}=(M+1)K\)

KD-tree加速K-means

05-08 08:31