algorithm - 使用 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使用的特殊情况 才合适

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中的公式以下(this answer)我可以看到他们没有将公式简化为您正在使用的公式(完整公式请参见他们链接论文中的第 4 页。请注意，他们提出了一种更复杂的算法，该算法在每次迭代时考虑每个质心和它的区域针对同一区域的几个质心，并使用 BIC 模型选择比较这两个模型。如果您想保留您的模型，则必须更改论文中的公式以考虑给定 k 的整个模型方法)。

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

您将 k 均值算法中的 k 插入到公式的自由参数惩罚元素中。

来自 wikipedia

where

[...]

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

在above linked x-mean paper在第 4 页第二列的顶部，他们计算了在 d 维空间中具有 k 质心的 k-means 模型的自由变量数为 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 个随机生成的点上运行它，我得到了一个小于最大 k (50) 的最小化 k: