使用 BIC 的 K 均值聚类中的最佳聚类数，(MATLAB)

Question

众所周知，在 k 均值聚类中，我们可以使用贝叶斯信息准则 (BIC) 来找出最佳聚类数。最小化 BIC 分数的 k 是根据 BIC 评分方案的最佳聚类数。

BIC的公式如下：

BIC(C) = n*ln(RSS/n) + k*ln(n)

其中 n 是数据集中数据点的数量，k 是聚类的数量。 RSS 是残差平方和，我们将每个数据点与其自身簇的质心的距离相加。我们的数据包含 3100 个点，每个点有两个元素 y=(x1, x2)（每个条目有两个特征）。

我在Matlab中的代码如下：

BIC=[];% Bayesian Information Criterion 
n=3100; % number of datapoints
temp=1;  
for k=1:50  % number of clusters
    RSS=0;  % residual sum of squares
[idx,C]=kmeans(y,k);  % Matlab command for k-mean clustering
for i=1:3100
    RSS=RSS+sqrt((y(i,1)-C(idx(i),1))^2+(y(i,2)-C(idx(i),2))^2);
end
BIC(temp)=n*log(RSS/n)+k*log(n);
temp=temp+1;
end
[p,l]=min(BIC);
plot(BIC)

但是我的代码肯定有问题，我不能说是什么！我的意思是，如果我们让 k 从 1 到 100，那么最小化 BIC 的 k 将为 100。如果我们让 k 从 1 到 1000，那么使 BIC 最小化的 k 将为 1000，依此类推。但据我所知应该有一个特定的 k 最小化 BIC。感谢您的帮助

Answer 1

我可以看到一些可以解释您报告的行为的潜在问题：

1) 我认为您使用的简化公式不适合您的情况

我不确定具体细节，但是 wikipedia 使用特例 $\mathrm{BIC} = n \cdot \ln(\widehat{\sigma_e^2}) + k \cdot \ln(n) \$ 才合适

Under the assumption that the model errors or disturbances are independent and identically distributed according to a normal distribution and that the boundary condition that the derivative of the log likelihood with respect to the true variance is zero

我在该领域的知识还不多，不知道第二个条件是否成立。查看原始 X-means paper by Peleg and Moore following (this answer 中的公式，我可以看到他们没有将公式简化为您正在使用的公式（有关完整公式，请参见其链接论文中的第 4 页。请注意，他们提出了一种更复杂的算法在每次迭代中考虑每个质心及其区域与同一区域的几个质心，并使用 BIC 模型选择比较这两个模型。您必须更改论文中的公式以考虑给定的整个模型k 如果你想保持你的方法）。

2) 你混淆了两个不同上下文的 k

您将 k-means 算法中的 k 插入到公式的 free-parameters 惩罚元素中。

来自wikipedia

$\mathrm {BIC} ={\ln(n)k-2\ln({\hat {L}})}$

where

[...]

*k = the number of free parameters to be estimated.

在第 4 页第二列顶部的 above linked x-mean paper 中，他们计算 d 中具有 k 个质心的 k-means 模型的自由变量数-dimental space 为 k(d+1) 在您的情况下给出 3k 而不是 k.

更改行中的代码

BIC(temp)=n*log(RSS/n)+k*log(n);

进入

BIC(temp)=n*log(RSS/n)+(k*3)*log(n);

和运行它在 2d 中的 1000 random-generated 点上我得到了一个小于最大 k (50) 的最小化 k：

使用 BIC 的 K 均值聚类中的最佳聚类数，(MATLAB)

optimum number of clusters in K mean clustering using BIC, (MATLAB)

algorithm

matlab

cluster-analysis

bayesian

k-means