模式识别十--k-均值聚类算法的研究与实现

2024-06-12 20:38

本文主要是介绍模式识别十--k-均值聚类算法的研究与实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 文章转自:http://www.kancloud.cn/digest/prandmethod/102852

本实验的目的是学习和掌握k-均值聚类算法。k-均值算法是一种经典的无监督聚类和学习算法,它属于迭代优化算法的范畴。本实验在MATLAB平台上,编程实现了k-均值聚类算法,并使用20组三维数据进行测试,比较分类结果。实验中初始聚类中心由人为设定,以便于实验结果的比较与分析。

一、技术论述

1.无监督学习和聚类

在之前设计分类器的时候,通常需要事先对训练样本集的样本进行标定以确定类别归属。这种利用有标记样本集的方法称为“有监督”或“有教师”方法。这一类方法的使用固然十分广泛,也有着很坚实的理论基础,但在实际运用中这类方法经常会遇到以下瓶颈:

  1. 收集并标记大量样本集是一件相当费时费力的前期工作;
  2. 现实中存在很多应用,其分类模式的性质会随着时间发生变化,单单使用已标记样本无法满足这类情况;
  3. 有人希望能逆向解决问题:先用大量未标记的样本集来自动地训练分类器,再人工地标记数据分组的结果,如数据挖掘的大型应用,因为这些应用往往不知道待处理数据的具体情况。

可以看到,无监督学习方法的提出是十分必要的。事实上,在任何一项探索性的工作中,无监督的方法均向我们揭示了观测数据的一些普遍规律。很多无监督方法都可以以独立于数据的方式工作,为后续步骤提供“灵巧的预处理”和“灵巧的特征提取”等有效的前期处理。在无监督的情况下,聚类算法是模式识别研究中著名的一类技术。

2.分类与聚类的差别

分类(Classification):对于一个分类器,通常需要你告诉它“这个东西被分为某某类”这样一些例子。通常情况下,一个分类器会从它得到的训练数据中进行学习,从而具备对未知数据进行分类的能力,这种提供训练数据的过程通常叫做有监督学习。

聚类(Clustering):简单地说就是把相似的东西分到一组。聚类的时候,我们并不关心某一类是什么,这里需要实现的目标只是把相似的东西聚到一起。因此,一个聚类算法通常只需要知道如何计算相似度就可以开始工作了。因此,聚类方法通常并不需要使用训练数据进行学习,因此桔类方法属于无监督学习的范畴。

3.常见的分类与聚类算法

所谓分类,就是根据数据样本的特征或属性,划分到已有的类别中。前面使用到的模式分类方法主要有:贝叶斯分类算法(Bayesian classifier) 、PCA主分量分析法、Fisher线性判别分析法、Parzen窗估计法、k-最近邻法(k-nearest neighbor,kNN)、基于支持向量机(SVM)的分类器、人工神经网络(ANN)和决策树分类法等等。

分类作为一种有监督学习方法,要求必须在分类之前明确知道各个类别的必要特征和信息,并且标记所有训练样本都有一个类别与之相对应。但是很多情况下这些条件往往无法满足,尤其是在处理海量数据的时候,数据预处理的代价非常大。

聚类算法中最经典的当属k均值聚类(K-means clustering)算法。该算法又称为“c均值算法”,因为它的目标就是找到c个均值向量作为聚类中心:μ1,μ2,…,μc,实际上k与c是等价的。

以上是对二维随机样本进行聚类的实例。

4.聚类任务的基本步骤

假设所有模式都用一组特征表示,模式被表示为L维的特征矢量。聚类任务需包含以下步骤:

  1. 特征选择。选择特征尽可能与感兴趣的任务相关。特征之间的信息冗余度要尽可能小。
  2. 相似性测度。一个基本的保证是所有选择的特征对相似性测度计算的贡献都是均衡的,没有那一个特征是绝对占优的。
  3. 聚类准则。聚类准则依赖于专家判断的在数据集合内部隐含类的类型解释。聚类准则可以被表示为代价函数和其它类型的规则。
  4. 聚类算法。在确定相似性测度和聚类准则后,这一步就是要选择一个具体的算法方案将数据集合分解为类结构。
  5. 结构的有效性。一旦聚类算法获得了结果,需要采用合适的检验方法检验其正确性。
  6. 结果的解释。应用领域的专家必须结合其它的试验证据和分析解释聚类结果,以便得到正确的结论。

5.k-均值聚类算法

k-均值聚类算法的目标是找到k个均值向量或“聚类中心”。算法的实现步骤如下所示,其中n表示模式的数量,c表示类别的数量,通常的做法是从样本中随机取出c个作为初始的聚类中心。当然,初始的聚类中心也可以通过人为来确定:

该算法的计算复杂度为:

其中d代表样本的维数,T是聚类的迭代次数,一般来说,迭代次数通常远少于样本的数量。

该算法是一种典型的聚类算法,把它归入迭代优化算法的范畴是因为算法规定的c个均值会不断地移动,使得一个平方误差准则函数最小化。在算法的每一步迭代中,每个样本点均被认为是完全属于某一类别。

二、实验结果讨论

实验所使用的样本:

设计步骤主要包括以下几个部分:

编写程序,实现以上所述的k-均值聚类算法。其中,在算法中样本与聚类中心的距离采用欧氏距离的形式。

类别数目和聚类中心初始值选为以下参数进行实验:

再将类别数目和聚类中心初始值改变为以下参数进行实验。

下图得到两次聚类的结果,可以看到当分类类别为2时,初始聚类中心对分类结果影响不大(至少对于样本少的情况是这样的),最终两种情况都能得到一样的最终聚类中心。

下面测试将样本分为三类的情况。将类别数目和聚类中心初始值选为以下参数进行实验:

再将类别数目和聚类中心初始值改变为以下参数进行实验:

下图得到两次聚类的结果,可以看到当分类类别为3时,分类复杂度增加,随着聚类中心的移动,对于同一组测试样本可能有不同的划分结果。虽然初始聚类中心的作用只是将样本初步地分为几个区域,但事实上不同的初始中心会给分类结果带来巨大的差异。

在程序中,使用欧氏距离作为样本到聚类中心的距离,事实上也可以使用其他多种距离度量进行运算,如街区距离(1范数)、棋盘距离(∞范数)等等。

三、完整代码

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% k-均值聚类函数
% 输入参数:
%   w:需要分类的样本
%   k:分类数
%   m:初始聚类中心
%   iteration:迭代次数
% 中间参数:
%   class_id:存放各个样本属于一类的下标
%   dist:计算样本到聚类中心的距离
% 输出参数:
%   class_result:存放样本的分类结果
%   class_num:存放被分到各类的样本个数
%   center:迭代结束时的聚类中心
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [class_result, class_num, center] = kmeans(w, k, m, iteration)
[n,d] = size(w);class_result = zeros(1,n);
class_num = zeros(1,k);    
time = 1;% 以下步骤计算每个样本到聚类中心的距离
while time < iteration % 迭代次数限制for i = 1:ndist = sqrt(sum((repmat(w(i,:), k, 1) - m).^2, 2));   % 欧氏距离% dist = sum(abs(repmat(x(i,:), k, 1) - nc), 2);      % 街区距离[y,class_id] = min(dist); % 计算样本对三类中哪一类有最小距离并存放在class_idclass_result(i) = class_id;endfor i = 1:k% 找到每一类的所有数据,计算平均值,其值作为新的聚类中心class_id = find(class_result == i);m(i, :) = mean(w(class_id, :));  % 更新聚类中心% 统计每一类样本的个数class_num(i) = length(class_id);endtime = time + 1;
end
center = m;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 样本分类结果的绘图函数
% 输入参数:
%   w:需要分类的样本
%   class:聚类后的样本分类结果
%   flag:分类类别数
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%function draw(w, class, center)[flag x] = size(center);
[n, d] = size(w);% figure;
if flag == 2 % 若将样本分成两类for i=1:nif class(i) == 1plot3(w(i,1),w(i,2),w(i,3),'r+'); % 显示第一类hold on;grid on;elseif class(i) == 2plot3(w(i,1),w(i,2),w(i,3),'go'); %显示第二类hold on;grid on;endendfor j = 1:flagif j == 1plot3(center(j,1),center(j,2),center(j,3),'rd'); % 聚类中心elseif j == 2plot3(center(j,1),center(j,2),center(j,3),'gd'); % 聚类中心endend
endif flag == 3 % 若将样本分成三类
% 显示分类结果for i = 1:nif class(i) == 1plot3(w(i,1),w(i,2),w(i,3),'r+'); % 显示第一类hold on;grid on;elseif class(i) == 2plot3(w(i,1),w(i,2),w(i,3),'go'); % 显示第二类hold on;grid on;elseif class(i) == 3plot3(w(i,1),w(i,2),w(i,3),'b*'); % 显示第三类hold on;  grid on;endendfor j = 1:flagif j == 1plot3(center(j,1),center(j,2),center(j,3),'rd'); % 聚类中心elseif j == 2plot3(center(j,1),center(j,2),center(j,3),'gd'); % 聚类中心elseif j == 3plot3(center(j,1),center(j,2),center(j,3),'bd'); % 聚类中心endend
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% k-均值聚类的研究与实现主函数
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
clear all;
close all;

% 测试样本
w = [-7.82 -4.58 -3.97;...-6.68  3.16  2.71;...
      4.36 -2.19  2.09;...6.72  0.88  2.80;...-8.64  3.06  3.50;...
     -6.87  0.57 -5.45;...
      4.47 -2.62  5.76;...6.73 -2.01  4.18;...-7.71  2.34 -6.33;...
     -6.91 -0.49 -5.68;...
      6.18  2.18  5.28;...6.72 -0.93 -4.04;...-6.25 -0.26  0.56;...
     -6.94 -1.22  1.33;...
      8.09  0.20  2.25;...6.81  0.17 -4.15;...-5.19  4.24  4.04;...
     -6.38 -1.74  1.43;...
      4.08  1.30  5.33;...6.27  0.93 -2.78];[n, d] = size(w);

% 以下是k均值聚类的参数设定(c = 2时)
k = 2;
m = [1 1 1; -1 1 -1]; % 初始聚类中心
% m = [0 0 0; 1 1 -1]; % 初始聚类中心
iteration = 200; % k均值聚类的迭代次数
% 调用kmeans函数进行聚类
[class, class_num, center] = kmeans(w, k, m, iteration);
% 画出样本分类结果
figure;subplot(121);draw(w, class, center);
title('使用第一种初始聚类中心时,k-均值聚类算法分类结果');

% 显示信息
disp(['属于第一类的样本个数为:',num2str(class_num(1))]);
disp(['属于第二类的样本个数为:',num2str(class_num(2))]);
disp('最终的聚类中心为:');
disp(num2str(center));

% 以下是k均值聚类的参数设定(c = 2时)
k = 2;
% m = [1 1 1; -1 1 -1]; % 初始聚类中心
m = [0 0 0; 1 1 -1]; % 初始聚类中心
iteration = 200; % k均值聚类的迭代次数
% 调用kmeans函数进行聚类
[class, class_num, center] = kmeans(w, k, m, iteration);
% 画出样本分类结果
subplot(122);draw(w, class, center);
title('使用第二种初始聚类中心时,k-均值聚类算法分类结果');

% 显示信息
disp(['属于第一类的样本个数为:',num2str(class_num(1))]);
disp(['属于第二类的样本个数为:',num2str(class_num(2))]);
disp('最终的聚类中心为:');
disp(num2str(center));

% 以下是k均值聚类的参数设定(c = 3时)
k = 3;
m = [0 0 0; 1 1 1; -1 0 2]; % 初始聚类中心
% m = [-0.1 0.0 0.1; 0 -0.1 0.1; -0.1 -0.1 0.1]; % 初始聚类中心
iteration = 200; % k均值聚类的迭代次数
% 调用kmeans函数进行聚类
[class, class_num, center] = kmeans(w, k, m, iteration);
% 画出样本分类结果
figure;subplot(121);draw(w, class, center);
title('使用第一种初始聚类中心时,k-均值聚类算法分类结果');
% 显示信息
disp(['属于第一类的样本个数为:',num2str(class_num(1))]);
disp(['属于第二类的样本个数为:',num2str(class_num(2))]);
disp(['属于第三类的样本个数为:',num2str(class_num(3))]);
disp('最终的聚类中心为:');
disp(num2str(center));

% 以下是k均值聚类的参数设定(c = 3时)
k = 3;
% m = [0 0 0; 1 1 1; -1 0 2]; % 初始聚类中心
m = [-0.1 0.0 0.1; 0 -0.1 0.1; -0.1 -0.1 0.1]; % 初始聚类中心
iteration = 200; % k均值聚类的迭代次数
% 调用kmeans函数进行聚类
[class, class_num, center] = kmeans(w, k, m, iteration);
% 画出样本分类结果
subplot(122);draw(w, class, center);
title('使用第二种初始聚类中心时,k-均值聚类算法分类结果');
% 显示信息
disp(['属于第一类的样本个数为:',num2str(class_num(1))]);
disp(['属于第二类的样本个数为:',num2str(class_num(2))]);
disp(['属于第三类的样本个数为:',num2str(class_num(3))]);
disp('最终的聚类中心为:');
disp(num2str(center));

这篇关于模式识别十--k-均值聚类算法的研究与实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1055279

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo