matlab - K均值质心被边缘化为没有数据点[Matlab]

Question

所以我有一个奇怪的问题。我有一个240点的数据集，我试图用k均值将其聚类为100个聚类。我正在使用Matlab，但无法访问统计信息工具箱，因此必须编写自己的k-means函数。这很简单，所以应该不难，对吧？好吧，我的代码似乎出了点问题：

function result=Kmeans(X,c)
[N,n]=size(X);
index=randperm(N);
ctrs = X(index(1:c),:);
old_label = zeros(1,N);
label = ones(1,N);

iter = 0;
while ~isequal(old_label, label)
    old_label = label;
    label = assign_labels(X, ctrs);

    for i = 1:c
        ctrs(i,:) = mean(X(label == i,:));
        if sum(isnan(ctrs(i,:))) ~= 0
            ctrs(i,:) = zeros(1,n);
        end
    end
    iter = iter + 1;
end

result = ctrs;

function label = assign_labels(X, ctrs)
[N,~]=size(X);
[c,~]=size(ctrs);
dist = zeros(N,c);
for i = 1:c
    dist(:,i) = sum((X - repmat(ctrs(i,:),[N,1])).^2,2);
end

[~,label] = min(dist,[],2);

似乎发生了什么事，当我去重新计算质心时，有些质心没有分配数据点，所以我不太确定该怎么做。在对此进行了一些研究之后，我发现如果您提供任意初始质心，则可能会发生这种情况，但是在这种情况下，初始质心是从数据点本身获取的，因此这实际上没有任何意义。我尝试将这些质心重新分配给随机数据点，但这会导致代码无法收敛（或者至少在整夜运行之后，代码从未收敛）。基本上，它们会被重新分配，但这会导致其他质心被边缘化并重复。我不太确定我的代码有什么问题，但是我通过R的k-means函数运行了相同的数据集，其中k = 100进行了1000次迭代，并且设法收敛了。有人知道我在这里搞砸吗？谢谢。

Answer 1

让我们一次一步地完成代码，并就我对k -means算法的了解讨论您在做什么。

function result=Kmeans(X,c)
[N,n]=size(X);
index=randperm(N);
ctrs = X(index(1:c),:);
old_label = zeros(1,N);
label = ones(1,N);

该函数看起来像一个采用大小为 N x n的数据矩阵的函数，其中 N是数据集中的点数，而 n是数据集中的点的维数。此函数还接受 c：所需的输出簇数。 index在 1到任意数量的数据点之间提供随机排列，然后从该排列中选择随机的 c点，您曾经用来初始化集群中心。

iter = 0;
while ~isequal(old_label, label)
    old_label = label;
    label = assign_labels(X, ctrs);

    for i = 1:c
        ctrs(i,:) = mean(X(label == i,:));
        if sum(isnan(ctrs(i,:))) ~= 0
            ctrs(i,:) = zeros(1,n);
        end
    end
    iter = iter + 1;
end

result = ctrs;

对于 k-均值，我们基本上保持迭代，直到前一次迭代中每个点的群集成员资格与当前迭代匹配为止，这就是您使用 while循环进行的操作。现在， label确定数据集中每个点的集群成员。现在，对于每个存在的群集，您可以确定平均数据点是什么，然后将该平均数据点分配为每个群集的新群集中心。出于某种原因，如果您对群集中心的任何维度遇到任何 NaN，请将新群集中心设置为全零。这对我来说看起来很不正常，稍后我会提出建议。编辑：现在我明白了您为什么这样做了。这是因为，如果您有任何集群为空，则只需使该集群的中心都为零，因为您将无法找到集群的平均值。我可以在本文结尾处建议使用重复的初始群集来解决此问题。

function label = assign_labels(X, ctrs)
[N,~]=size(X);
[c,~]=size(ctrs);
dist = zeros(N,c);
for i = 1:c
    dist(:,i) = sum((X - repmat(ctrs(i,:),[N,1])).^2,2);
end

[~,label] = min(dist,[],2);

此函数获取数据集 X和当前迭代的当前聚类中心，并且应返回每个点属于每个聚类的位置的标签列表。这看起来也是正确的，因为对于 dist的每一列，您正在计算每个点到每个聚类的距离，其中这些距离在第i个聚类的ith列中。我将使用的一种优化技巧是避免在此处使用 repmat并使用 bsxfun在内部处理复制。因此，请改为：

function label = assign_labels(X, ctrs)
[N,~]=size(X);
[c,~]=size(ctrs);
dist = zeros(N,c);
for i = 1:c
    dist(:,i) = sum(bsxfun(@minus, X, ctrs(i,:)).^2, 2);
end

[~,label] = min(dist,[],2);

现在，这一切看起来都是正确的。我还自己进行了一些测试，并且只要初始群集中心是唯一的，所有这些似乎都可以解决。 k -means的一个小问题是我们隐式地假设所有聚类中心都是唯一的。如果它们不是唯一的，那么您将遇到一个问题，即两个群集（或更多群集）具有完全相同的初始群集中心...。因此，应将数据点分配给哪个群集？在 min函数中执行 assign_labels时，如果您有两个相同的聚类中心，则将点分配给的聚类标签将是这两个数字中的最小值。这就是为什么您将拥有一个没有任何点的群集的原因，因为应该分配给该群集的所有点都将被分配给另一个。

因此，您可能拥有两个（或多个）初始聚类中心，它们在随机化时是相同的。即使要选择的索引的排列是唯一的，但实际数据点本身在选择时可能也不是唯一的。我可以施加的一件事是遍历排列，直到获得唯一的没有重复的初始簇集。因此，请尝试在代码开头执行此操作。

[N,n]=size(X);
index=randperm(N);
ctrs = X(index(1:c),:);

while size(unique(ctrs, 'rows'), 1) ~= c
    index=randperm(N);
    ctrs = X(index(1:c),:);
end

old_label = zeros(1,N);
label = ones(1,N);

iter = 0;

%// While loop appears here

这样可以确保在继续执行代码之前，您拥有一组唯一的初始集群。现在，回到 NaN循环内的 for内容。老实说，如果您的数据没有任何 NaN，计算平均值后，我看不出任何维度如何导致 NaN。我建议您在代码中摆脱这种情况，因为（对我而言）它看起来不是很有用。编辑：您现在可以删除 NaN检查，因为初始群集中心现在应该是唯一的。



这有望解决您遇到的问题。祝好运！