模式识别十--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

相关文章

pandas中位数填充空值的实现示例

《pandas中位数填充空值的实现示例》中位数填充是一种简单而有效的方法,用于填充数据集中缺失的值,本文就来介绍一下pandas中位数填充空值的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录什么是中位数填充?为什么选择中位数填充?示例数据结果分析完整代码总结在数据分析和机器学习过程中,处理缺失数

Golang HashMap实现原理解析

《GolangHashMap实现原理解析》HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持高效的插入、查找和删除操作,:本文主要介绍GolangH... 目录HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持

Pandas使用AdaBoost进行分类的实现

《Pandas使用AdaBoost进行分类的实现》Pandas和AdaBoost分类算法,可以高效地进行数据预处理和分类任务,本文主要介绍了Pandas使用AdaBoost进行分类的实现,具有一定的参... 目录什么是 AdaBoost?使用 AdaBoost 的步骤安装必要的库步骤一:数据准备步骤二:模型

使用Pandas进行均值填充的实现

《使用Pandas进行均值填充的实现》缺失数据(NaN值)是一个常见的问题,我们可以通过多种方法来处理缺失数据,其中一种常用的方法是均值填充,本文主要介绍了使用Pandas进行均值填充的实现,感兴趣的... 目录什么是均值填充?为什么选择均值填充?均值填充的步骤实际代码示例总结在数据分析和处理过程中,缺失数

Java对象转换的实现方式汇总

《Java对象转换的实现方式汇总》:本文主要介绍Java对象转换的多种实现方式,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录Java对象转换的多种实现方式1. 手动映射(Manual Mapping)2. Builder模式3. 工具类辅助映

Go语言开发实现查询IP信息的MCP服务器

《Go语言开发实现查询IP信息的MCP服务器》随着MCP的快速普及和广泛应用,MCP服务器也层出不穷,本文将详细介绍如何在Go语言中使用go-mcp库来开发一个查询IP信息的MCP... 目录前言mcp-ip-geo 服务器目录结构说明查询 IP 信息功能实现工具实现工具管理查询单个 IP 信息工具的实现服

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

python实现svg图片转换为png和gif

《python实现svg图片转换为png和gif》这篇文章主要为大家详细介绍了python如何实现将svg图片格式转换为png和gif,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录python实现svg图片转换为png和gifpython实现图片格式之间的相互转换延展:基于Py

Python利用ElementTree实现快速解析XML文件

《Python利用ElementTree实现快速解析XML文件》ElementTree是Python标准库的一部分,而且是Python标准库中用于解析和操作XML数据的模块,下面小编就来和大家详细讲讲... 目录一、XML文件解析到底有多重要二、ElementTree快速入门1. 加载XML的两种方式2.

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组