【搜索技术】周志华《机器学习》第九章 K均值算法问题

Z时代
2024-01-10
分类：技术分享

我在试着运行聚类算法中的K均值算法时，用了一下书中所给的例子P203，数据集为「西瓜数据集4.0」，设定聚类集数k=3，算法开始时随机选取的三个样本是x6,x12,x27。

运行过程中，第一轮迭代与书中所给答案一样，但是我按照书中伪代码编的代码智能运行一轮，而书中的用同样的数据集迭代了4轮，我看了好多遍我的代码，并且在网上找了一下别人写的基础 kmeans 算法，同样也是迭代了一轮，我想知道我的kmeans算法有什么错误，是不是书中的伪代码哪里描述的不清晰？

用 MATLAB 自带的 kmeans 算法正确运行下去，但是自带的源代码实在看不懂

function C=kmeans(data,k)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%C是返回的簇划分矩阵
%data是传入的数据集
%k是要划分k个簇
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% avgvector=randperm(k);   %在data中随机选择k个样本作为初始均值向量
avgvector=[6 12 27];
for i=1:k
mu(i,:)=data(avgvector(i),:);
end
datalength=size(data,1);  %得出矩阵的行数，即有多少个样本
while 1
C=zeros(datalength,1);
temp=0;
muold=mu;              %留作之后判断均值向量矩阵是否更新
% disp(mu);
for i=1:datalength      %计算样本x与各均值向量的距离
for j=1:k
x_mu_distance(i,j)=norm(data(i,:)-mu(j,:));  %计算x与mu的欧式距离
end
temp=find((x_mu_distance(i,:)==min(x_mu_distance(i,:))),1,'first');
C(i,1)=temp;  %在距离矩阵中找出最近的均值向量，并记录属于第几个簇
end
disp(x_mu_distance);
%对均值向量进行更新
for i=1:k
isInKGroup=0;
kthmusum=0;
isInKGroup=find(C(:,1)==i);   %在第k个簇中的样本编号
for j=1:length(isInKGroup)
kthmusum=kthmusum+data(isInKGroup(j),:);
end
mu(i,:)=kthmusum/length(isInKGroup);
end
%判断均值向量矩阵mu有没有改变
if(muold==mu)
break;
end
end
for i=1:k
plot(mu(i,1),mu(i,2),'pg');
hold on;
end
for i=1:length(C)
if(C(i)==1)
plot(data(i,1),data(i,2),'+r');
hold on;
elseif(C(i)==2)
plot(data(i,1),data(i,2),'*b');
hold on;
elseif(C(i)==3)
plot(data(i,1),data(i,2),'^m');
hold on;
elseif(C(i)==4)
plot(data(i,1),data(i,2),'.c');
hold on;
end
end

下面是西瓜数据集：
xigua =

0.6970 0.4600 0.7740 0.3760 0.6340 0.2640 0.6080 0.3180 0.5560 0.2150 0.4030 0.2370 0.4810 0.1490 0.4370 0.2110 0.6660 0.0910 0.2430 0.2670 0.2450 0.0570 0.3430 0.0990 0.6390 0.1610 0.6570 0.1980 0.3600 0.3700 0.5930 0.0420 0.7190 0.1030 0.3590 0.1880 0.3390 0.2410 0.2820 0.2570 0.7480 0.2320 0.7140 0.3460 0.4830 0.3120 0.4780 0.4370 0.5250 0.3690 0.7510 0.4890 0.5320 0.4720 0.4730 0.3760 0.7250 0.4450

0.4460 0.4590

回答

我用python也测试过，也是一轮就聚类完成，也有可能是因为数据集给得不全，数据集就几十条所以只有一轮
（更新）：
这可以和算法中随机选择质心的算法有关，因为不同的质心对最终迭代次数有影响，就像题主说的达到局部最优解
下面是可以循环三次
【搜索技术】周志华《机器学习》第九章 K均值算法问题

循环六次的：

【搜索技术】周志华《机器学习》第九章 K均值算法问题

算法核心部分：

def k_means(data_set, k, distE=distEclud, createCent=rand_cent):
    """
    data_set: 数据集
    data_set = [[1.658985, 4.285136], [-3.453687, 3.424321],
            [4.838138, -1.151539],[-5.379713, -3.362104],
            [0.972564, 2.924086]]
    k: 设置聚类簇数K值
    distE：函数, 计算数据点的欧式距离
    例如：vector1 = [[ 1.658985  4.285136]]
      vector2 = [[-3.453687  3.424321]]
    欧氏距离：distance = distE(vector1, vector2)
    createCent: 函数， 返回一个随机的质点矩阵
    """
    m = shape(data_set)[0]  # 获取行数
    clusterAssment = mat(zeros((m, 2)))  # 初始化一个矩阵， 用来记录簇索引和存储误差平方和(指当前点到簇质点的距离）
    centroids = rand_cent(data_set, k)  # 随机生成一个质心矩阵蔟
    clusterChanged = True
    print('开始')
    while clusterChanged:
        clusterChanged = False
        for i in range(m):  # 对每个数据点寻找最近的质心
            min_dist = inf  # 设置最小距离为正无穷大
            min_index = -1
            for j in range(k):  # 遍历质心簇，寻找最近质心
                dist_J = distEclud(centroids[j, :], data_set[i, :])
                if dist_J < min_dist:
                    min_dist = dist_J
                    min_index = j
            if clusterAssment[i, 0] != min_index:
                clusterChanged = True
            clusterAssment[i, :] = min_index, min_dist ** 2    # 平方的意义在于判断聚类结果的好坏
        print(centroids)
        print('==================')
        for cent in range(k):  # 更新质心，将每个簇中的点的均值作为质心
            index_all = clusterAssment[:, 0].A  # 取出样本所属簇的索引值
            value = nonzero(index_all == cent)  # 取出所有属于第cent个簇的索引值
            sampleInClust = data_set[value[0]]  # 取出属于第I个簇的所有样本点
            centroids[cent, :] = mean(sampleInClust, axis=0)
    return centroids, clusterAssment