正确实现k-means算法
Implementing k-means algorithm correctly
我刚刚开始学习编码,并着手编写标准的 k-means 算法。我在由三个不同的高斯生成的数据集上尝试了我的实现,它似乎运行良好。但是我在 iris 数据集上尝试过它,并且时不时地(大约三分之一的时间)我的函数 returns 只有两个集合,换句话说它 returns 只有两个集群。
我看过本地 MATLAB kmeans 函数的代码,但由于缺乏编码知识,我最终迷路了。我真的很感激任何帮助!
function [R,C,P,it] = mykmeans(X,K)
% X -- data matrix
% K -- number of clusters
% C -- partition sets
% P -- matrix of prototypes
% R -- binary indicator matrix: R(i,j) specifies whether the ith data is
% classified into jth cluster
% it -- number of iterations until convergence
% N points with M dimensions
[N,M] = size(X) ;
%% Initialisation
% At this step we randomly partition the data matrix into K equally sized
% matrices and compute the centre of each of these matrices.
% I -- randomised index vector
% v -- number of data points assigned to each cluster
% U -- randomly partitioned matrices
v = N/K ;
C = cell(K,1) ;
U = cell(K,1) ;
I = randperm(N) ;
oldR = zeros(N,K) ;
% C{1} = X(I(1:v),:) ;
% U{1} = mean(X(I(1:v),:)) ;
for k=1:K
C{k} = X(I(1+v*(k-1):k*v),:) ;
U{k} = mean(C{k}) ;
end
P = cell2mat(U) ;
converged = 0 ;
it = 0 ;
while converged ~= 1
%% Assignment step
% Each element of D{n} contains squared euclidean distance of nth data
% point from the kth prototype
D = cell(N,1) ;
R = zeros(N,K) ;
for n=1:N
D{n} = sum((repmat(X(n,:),K,1) - P).^2,2) ;
[~,k] = min(D{n}) ;
R(n,k) = 1 ;
end
%% Update step
C = cell(K,1) ; % reset C
for k=1:K
for n=1:N
P(k,:) = R(n,k)*X(n,:) + P(k,:) ; % compute numerator of mean vector
if R(n,k) == 1
C{k} = [C{k};X(n,:)] ;
end
end
end
P = P ./ (sum(R)') ; % divide by denominator of mean vectors to get prototypes
%% Check for convergence
if sum(sum(R == oldR))==N*K || it == 100 % convergence criteria
converged = 1 ;
else
oldR = R ;
it = it+1 ;
end
end %while
问题确实看起来不是编码问题而是理解问题k-means。
事实上,在 k-means 期间,集群可能会变空。您需要在代码中考虑到这一点,否则结果中的簇数可能小于 k。
可能的解决方案是:
- 分配一个随机数据点作为空簇的新簇中心
- 选择距离最大簇最远的点作为空簇的新簇中心
因此,一般方法如下:
- 初始化k个簇中心(例如:随机)
- 将所有数据点分配到最近的聚类中心
- 根据分配重新计算聚类中心
- 检查空簇
- 重复步骤 2 - 4 直到收敛(== 聚类中心在最后一次迭代中没有改变)
可以找到空簇问题的一个很好的说明 here。
我刚刚开始学习编码,并着手编写标准的 k-means 算法。我在由三个不同的高斯生成的数据集上尝试了我的实现,它似乎运行良好。但是我在 iris 数据集上尝试过它,并且时不时地(大约三分之一的时间)我的函数 returns 只有两个集合,换句话说它 returns 只有两个集群。
我看过本地 MATLAB kmeans 函数的代码,但由于缺乏编码知识,我最终迷路了。我真的很感激任何帮助!
function [R,C,P,it] = mykmeans(X,K)
% X -- data matrix
% K -- number of clusters
% C -- partition sets
% P -- matrix of prototypes
% R -- binary indicator matrix: R(i,j) specifies whether the ith data is
% classified into jth cluster
% it -- number of iterations until convergence
% N points with M dimensions
[N,M] = size(X) ;
%% Initialisation
% At this step we randomly partition the data matrix into K equally sized
% matrices and compute the centre of each of these matrices.
% I -- randomised index vector
% v -- number of data points assigned to each cluster
% U -- randomly partitioned matrices
v = N/K ;
C = cell(K,1) ;
U = cell(K,1) ;
I = randperm(N) ;
oldR = zeros(N,K) ;
% C{1} = X(I(1:v),:) ;
% U{1} = mean(X(I(1:v),:)) ;
for k=1:K
C{k} = X(I(1+v*(k-1):k*v),:) ;
U{k} = mean(C{k}) ;
end
P = cell2mat(U) ;
converged = 0 ;
it = 0 ;
while converged ~= 1
%% Assignment step
% Each element of D{n} contains squared euclidean distance of nth data
% point from the kth prototype
D = cell(N,1) ;
R = zeros(N,K) ;
for n=1:N
D{n} = sum((repmat(X(n,:),K,1) - P).^2,2) ;
[~,k] = min(D{n}) ;
R(n,k) = 1 ;
end
%% Update step
C = cell(K,1) ; % reset C
for k=1:K
for n=1:N
P(k,:) = R(n,k)*X(n,:) + P(k,:) ; % compute numerator of mean vector
if R(n,k) == 1
C{k} = [C{k};X(n,:)] ;
end
end
end
P = P ./ (sum(R)') ; % divide by denominator of mean vectors to get prototypes
%% Check for convergence
if sum(sum(R == oldR))==N*K || it == 100 % convergence criteria
converged = 1 ;
else
oldR = R ;
it = it+1 ;
end
end %while
问题确实看起来不是编码问题而是理解问题k-means。
事实上,在 k-means 期间,集群可能会变空。您需要在代码中考虑到这一点,否则结果中的簇数可能小于 k。
可能的解决方案是:
- 分配一个随机数据点作为空簇的新簇中心
- 选择距离最大簇最远的点作为空簇的新簇中心
因此,一般方法如下:
- 初始化k个簇中心(例如:随机)
- 将所有数据点分配到最近的聚类中心
- 根据分配重新计算聚类中心
- 检查空簇
- 重复步骤 2 - 4 直到收敛(== 聚类中心在最后一次迭代中没有改变)
可以找到空簇问题的一个很好的说明 here。