【matlab】KMeans KMeans++实现手写数字聚类

news/2024/5/20 7:54:24 标签: matlab, kmeans, 聚类

目录

matlab%E4%BB%A3%E7%A0%81kmeans-toc" style="margin-left:0px;">matlab代码kmeans

matlab%E4%BB%A3%E7%A0%81kmeans%2B%2B-toc" style="margin-left:0px;">matlab代码kmeans++

 MNIST DATABASE下载网址: http://yann.lecun.com/exdb/mnist/

聚类

将物理或抽象对象的集合分成由类似特征组成的多个类的过程称为聚类(clustering)。

对于给定N个n维向量x1，…，xN∈Rn，聚类的目标就是将这N个n维向量分成k个集合，尽量使得同一个集合中的向量彼此接近，如图2所示。

图2 聚类示意效果图

 

K-means聚类算法迭代过程

首先初始化聚类中心，如图3所示。

图3 k-means初始聚类中心

然后计算每个点到k个聚类中心的聚类，并将其分配到最近的聚类中心所在的聚类中，重新计算每个聚类现在的质心，并以其作为新的聚类中心，如图4所示。

图4 k-means迭代1次

重复迭代，直到达到给定的迭代次数或k个聚类中心的变化值小于某个阈值，形成最终的聚类结果，如图5所示。

图5 k-means最终聚类效果

 

K均值聚类算法的复杂度分析

初始化：选择K个初始聚类中心。这个步骤的时间复杂度为O(K)。

分配：对每个样本点，计算其与每个聚类中心的距离，并将其分配到距离最近的聚类中心所代表的簇。这个步骤的时间复杂度为O(N * K * d)，其中N是样本数，d是特征数。

更新：对每个簇，计算其所有样本点的平均值作为新的聚类中心。这个步骤的时间复杂度为O(N * K * d)。

重复执行第2和第3步，直到满足停止条件，例如达到最大迭代次数或聚类中心变化小于一定阈值。

因此，K均值聚类算法的总体时间复杂度主要由分配和更新两个步骤决定，为O(T * N * K * d)，其中T是迭代次数。

K-means手写数字聚类

用kmeas聚类算法对train_images.mat的前100张和前1000张手写数字图像进行聚类，重复测试10次，每次测试的正确率如图6所示，其中100张的平均正确率为59%，最高正确率为66%，平均运行时间为0.1秒，1000张的平均正确率为55%，最高正确率为62%，平均运行时间为3.6秒。

图6 K-means聚类结果

再对train_images.mat的前100张、500张、1000张、2000张和4000张手写数字图像进行聚类，每种图像张数重复测试10次，计算平均正确率和平均运行时间，结果如表1所示。

表1 K-means聚类测试

由表1可知，K-means手写数字聚类在图像数目达到4000张的时候，运行时间达到了41秒，而且平均正确率为60%左右。

K-means性能分析

由结果可以很明显地看出，K-means聚类应用在手写数字上的效果并不是很好，平均正确率只有60%左右，其中有几个原因。一是K-means假设各个簇的大小、形状和密度相似，如果数据集中的簇具有类似的分布特征，K-means能够产生较好的聚类结果，而手写数字数据集的数字并不是均匀分布的，不同的数字可能出现频率不同，而且手写数字的形状有的区别不大；二是K-means在处理高维数据时可能会遇到困难，因为高维空间下的距离计算和聚类结果评估会变得复杂，而实验中手写数字的维度达到了784。

K-means++

K-means聚类算法的一大缺点是初始类别中心的选择对聚类迭代的次数影响很大，而K-means++是想通过选择更好初始类别中心来减少K-means聚类的迭代次数。

那么什么样的初始类别中心是更好的呢？

好的初始类别中心应该能够均匀地覆盖整个数据空间，能够代表数据集中的不同特征。

K-means++算法流程

  • 从数据点中随机选择一个点作为第一个聚类中心。
  • 对于每个数据点，计算它与当前已选择的聚类中心的距离，选择与已选择的聚类中心距离最大的数据点作为下一个聚类中心。
  • 重复步骤②，直到选择出k个初始聚类中心。

K-means++手写数字聚类

用kmeas++聚类算法对train_images.mat的前100张和前1000张手写数字图像进行聚类，重复测试10次，每次测试的正确率如图7所示，其中100张的平均正确率为58%，最高正确率达到了63%，平均运行时间为0.03秒，1000张的平均正确率为57%，最高正确率为61%，平均运行时间为0.76秒。

图7 K-means++聚类结果

我们再对train_images.mat的前100张、1000张、2000张、4000张和8000张手写数字图像进行聚类，每种图像张数重复测试10次，计算平均正确率和平均运行时间，结果如表2所示。

表2 K-means聚类测试

由表2可知，K-means手写数字聚类在图像数目达到8000张的时候，运行时间达到了15秒，而且平均正确率均高于50%。

K-means++性能分析

由结果可以很明显地看出，相比K-means的聚类结果，K-means++的正确率差别不大，基本上也是在60%左右，但是程序运行时间极大的减少了，这说明K-means++的优化，即选择更好的初始类别中心，可以大大的减少算法迭代的过程，迅速聚类。

但是由于K-means++只是为K-means聚类选择更好的初始化中心，这只是减少了聚类的迭代次数，并不能解决K-means聚类手写数字效果不好的问题。

matlab%E4%BB%A3%E7%A0%81kmeans" style="margin-left:0px;text-align:justify;">matlab代码kmeans

clc,clear;
load ./train_images.mat;
load ./train_labels.mat;
k=10;
dimension=2;
Dimension=28*28;
picturesNumber=1000;
sample=train_images(:,:,1:picturesNumber);
sample=reshape(sample,28*28,picturesNumber);
sample=sample';
class=zeros(1,picturesNumber);
times=[];
ratios=[];
for time=1:10
    tic;
    classCenter=sample(randperm(picturesNumber,k),:); % 随机取点
    iterator=0;
    while(true)
        iterator=iterator+1;
        nextCenter=zeros(k,Dimension);
        classNumber=zeros(1,k);
        for i=1:picturesNumber
            distances=zeros(1,k);
            for j=1:k
                distances(j)=pdist2(sample(i,:),classCenter(j,:));
            end
            [~,index]=sort(distances);
            class(i)=index(1);
            classNumber(class(i))=classNumber(class(i))+1;
            nextCenter(class(i),:)=nextCenter(class(i),:)+sample(i,:);
        end
        temp=classCenter;
        for i=1:k
            if classNumber(i)~=0
                classCenter(i,:)=nextCenter(i,:)/classNumber(i);
            end
        end
        if temp==classCenter
            break
        end
    end
    map=containers.Map('KeyType','int32','ValueType','int32');
    for i=1:k
        number=[];
        for j=1:picturesNumber
            if class(j)==i
                number=[number,train_labels(j)];
            end
        end
        map(i)=mode(number);
    end
    count=0;
    for i=1:picturesNumber
        if map(class(i))==train_labels(i)
            count=count+1;
        end
    end
    ratio=count/picturesNumber;
    ratios=[ratios,ratio];
    times=[times,toc];
end

matlab%E4%BB%A3%E7%A0%81kmeans%2B%2B" style="margin-left:0px;text-align:justify;">matlab代码kmeans++

clc;
clear;
load ./train_images.mat;
load ./train_labels.mat;
k = 10;
dimension = 2;
Dimension = 28 * 28;
picturesNumber = 100;
sample = train_images(:, :, 1:picturesNumber);
sample = reshape(sample, 28 * 28, picturesNumber);
sample = sample';
class = zeros(1, picturesNumber);
times = [];
ratios = [];
for time = 1:10
    tic;

    % K-Means++ initial center selection
    classCenter = zeros(k, Dimension);
    classCenter(1, :) = sample(randi(picturesNumber), :);
    for j = 2:k
        distances = pdist2(sample, classCenter(1:j-1, :));
        minDistances = min(distances, [], 2); % 为什么挑最近的呢？因为是挑离所有已选中心最远的
        [~, index] = max(minDistances);
        classCenter(j, :) = sample(index, :);
    end

    iterator = 0;
    while (true)
        iterator = iterator + 1;
        nextCenter = zeros(k, Dimension);
        classNumber = zeros(1, k);
        for i = 1:picturesNumber
            distances = pdist2(sample(i, :), classCenter);
            [~, index] = min(distances);
            class(i) = index;
            classNumber(class(i)) = classNumber(class(i)) + 1;
            nextCenter(class(i), :) = nextCenter(class(i), :) + sample(i, :);
        end
        temp = classCenter;
        for i = 1:k
            if classNumber(i) ~= 0
                classCenter(i, :) = nextCenter(i, :) / classNumber(i);
            end
        end
        if isequal(temp, classCenter)
            break;
        end
    end

    map = containers.Map('KeyType', 'int32', 'ValueType', 'int32');
    for i = 1:k
        number = [];
        for j = 1:picturesNumber
            if class(j) == i
                number = [number, train_labels(j)];
            end
        end
        map(i) = mode(number);
    end
    count = 0;
    for i = 1:picturesNumber
        if map(class(i)) == train_labels(i)
            count = count + 1;
        end
    end
    ratio = count / picturesNumber;
    ratios = [ratios, ratio];
    times = [times, toc];
end

http://www.niftyadmin.cn/n/5174006.html

相关文章

CountDownLatch和CyclicBarrier详解

CountDownLatch和CyclicBarrier详解

1. CountDownLatch 1.1 简介 CountDownLatch 是 Java 中并发包（java.util.concurrent）提供的一种同步工具，用于在多线程环境中协调多个线程之间的执行顺序。它的作用是允许一个或多个线程等待其他线程完成操作。 CountDownLatch 通过一个计…
阅读更多...
node插件express（路由）的插件使用（二）——cookie 和 session的基本使用区别

node插件express（路由）的插件使用（二）——cookie 和 session的基本使用区别

文章目录 前言一、express 框架中的 cookie0、cookie的介绍和作用1. 设置cookie2.删除cookie3.获取cookie（1）安装cookie-parser（2）导入cookie-parser（3）注册中间件（4）获取cookie&…
阅读更多...
KubeSphere 社区双周报 | KubeSphere 3.4.1 发布 | 2023.10.27-11.09

KubeSphere 社区双周报 | KubeSphere 3.4.1 发布 | 2023.10.27-11.09

KubeSphere 社区双周报主要整理展示新增的贡献者名单和证书、新增的讲师证书以及两周内提交过 commit 的贡献者，并对近期重要的 PR 进行解析，同时还包含了线上/线下活动和布道推广等一系列社区动态。 本次双周报涵盖时间为：2023.10.27-2023.…
阅读更多...
按键精灵中的字符串常用的场景

按键精灵中的字符串常用的场景

在使用按键精灵编写脚本时，与字符串有关的场景有以下几种： 1. 用时间字符串记录脚本使用截止使用时间 Dim localTime "2023-11-12 00:15:14" Dim networkTime GetNetworkTime() TracePrint networkTime If networkTime > localTime The…
阅读更多...
GCC工具详解【Linux知识贩卖机】

GCC工具详解【Linux知识贩卖机】

很多人在喧嚣声中登场，也有少数人在静默中退出。 --单独中的洞见2 文章目录 简介程序到可执行文件链接动态链接和静态链接动态库和静态库动态库和静态库的打包打包静态库打包动态库选项 -static 总结 简介 GCC（GNU Compiler Collection） 是一…
阅读更多...
leetcode刷题日记:111. Minimum Depth of Binary Tree(二叉树的最小深度)

leetcode刷题日记:111. Minimum Depth of Binary Tree(二叉树的最小深度)

给我们一个二叉树，我们应该如何来求二叉树的最小深度呢？ 二叉树的最小深度指的是叶子结点到所处的位置最小的，这就是二叉树的最小深度，也就是说我们要找的是离根结点最近的叶子结点。如果我们从根结点向下出发寻找叶子节点&#x…
阅读更多...
C语言 判断一个素数能被几个9整除

C语言 判断一个素数能被几个9整除

完整代码&#xff1a; // 判断一个素数能被几个9整除 //就是99...99%n0,n为那个素数 #include<stdio.h>int func(int n){//num是被除数就是99..9,i记录num有多少个9int num0,i0;//死循环while (1){i;numnum*109;//直到整除才跳出循环if (num%n0){//返回值为9的个数retu…
阅读更多...
【mysql】将逗号分割的字段内容转换为多行并group by

【mysql】将逗号分割的字段内容转换为多行并group by

先说需求&#xff1a; 公司想让我通过mysql导出一个报表&#xff0c;内容为公司每个人参加会议的次数&#xff0c;现在有一个会议表fusion_meeting&#xff0c;正常的逻辑是通过人员直接group by就可以得出结果&#xff0c;但是我们的参会人是通过逗号分割这种方式存在一个字段…
阅读更多...
最新文章

Copyright @ 2022~2023