-
2021-01-31 21:37:47
文章目录
图像聚类算法
一、分类与聚类
1.1 分类
分类其实是从特定的数据中挖掘模式,作出判断的过程。
分类学习的主要过程:
(1)训练数据集存在一个类标记号,判断它是正向数据集(起积极作用,如非垃圾邮件),还是负向数据集(起抑制作用,如垃圾邮件);
(2)然后需要对数据集进行学习训练,并构建一个训练的模型。
(3)通过该模型对预测数据集进行预测,并计算其结果的性能。1.2 聚类
从广义上说,聚类就是将数据集中某些方面相似的数据成员放在一起。一个聚类就是一些数据实例的集合,其中处于相同聚类中的数据元素彼此相似,但是处于不同聚类中的元素彼此不同。由于在聚类中那些表示数据类别的分类或分组信息是没有的,即这些数据是没有标签的,所以聚类通常被归为无监督学习(Unsupervised Learning)。
聚类的目的是把数据分类,但是事先不知道如何分的,完全是算法自己来判断各条数据之间的相似性,相似的就分到一起。在聚类结论出来之前,完全不知道每一类有什么特点,一定要根据聚类的结果通过人的经验来分析,看看聚成的这一类大概有什么特点。
总之,聚类主要是“物以类聚”,通过相似性把相似元素聚集在一起,它是没有标签的,这是与分类最大的区别,分类是通过标签来训练得到一个模型,对新数据预测的过程,其数据存在标签。
二、聚类常见的算法
聚类算法分为三大类:
- 原型聚类
- 层次聚类
- 密度聚类
2.1 原型聚类
K-Means聚类是最常用的聚类算法,是一种原型聚类算法,最初起源于信号处理,其目标是将数据点划分为K个类簇。该算法的最大优点是简单、便于理解,运算速度较快,缺点是在聚类前需要指定聚集的类簇数。
2.1.1 K-means聚类算法的分析流程:
第一步,确定K值,即将数据聚集成K个类簇或小组;
第二步,从数据集中随机选择K个数据点作为质心(Centroid)或数据中心;
第三步,分别计算每个质心之间的距离,并将每个点划分到离最近质心的小组;
第四步,当每个质心都聚集一些点后,重新定义算法选出质心。(对于每个簇,计算其均值,即得到新的K个质心点);
第五步,迭代执行第三步到第四步,直到迭代终止条件满足为止(分类结果不再变化)。在图像处理中,通过K-Means聚类算法可以实现图像分割、图像聚类,图像识别等操作。通过K-Means可以将这些像素点聚类成K个簇,然后使用每个簇内的质心点来替换簇内所有的像素点,这样就能实现在不改变分辨率的情况下量化压缩图像颜色层级分割。
2.1.2 K-Means聚类与图像处理
- 优点:
- 解决聚类问题的一种经典算法,简单、快速;
- 对处理大数据集,该算法保持高效率;
- 当结果簇是密集的,它的效果较好。
- 缺点:
- 必须事先给出K(要生成的簇的数目);
- 对噪声和孤立点数据敏感。
2.2 层次聚类
层次聚类是一种很直观的算法,顾名思义就是样一层一层地进行聚类。层次法(Hierarchicalmethods) 先计算样本之间的距离,每次将距离最近的点合并到同一个类,然后,再计算类与类之间的距离,将距离最近的类合并成一个大类。不停地合并,直到合成一个类。其中类与类的计算方法有:最短距离法,最长距离法,中间距离法,类平均法等。比如最短距离法,将类与类的距离定义为类与类之间样本的最短距离。
层次聚类算法根据层次分解的顺序分为:自底向上和自上向下,即凝聚的层次聚类算法和分裂的层次聚类算法(agglomerative和divisive),也可以理解为自下而上法(bottom-up)和自上而下(top-down)法。
2.1 凝聚层次聚类的流程
凝聚型层次聚类的策略是先将每个对象作为一个簇,然后合并这些原子簇为越来越大的簇,直到所有对象都在一个簇中,或者某个终结条件被满足。对大多数层次聚类属于凝聚型层次聚类,它们只是在簇间相似度的定义有所不同。这里给出采用最小距离的凝聚层次聚类算法流程:
(1)将每个对象看作一类,计算两两之间的最小距离;
(2)将距离最小的两个类合并成一个新类;
(3)重新计算新类与所有类之间的距离;
(4)重复(2)(3),直到所有类最后合并成一类。特点:
- 凝聚的层次聚类并没有类似K均值的全局目标函数,没有局部极小问题或是很难选择初始点的问题。
- 合并的操作往往是最终的,一旦合并两个簇之后就不会撤销。
- 当然其计算存储的代价是昂贵的。
优点:
- 距离和规则的相似度容易定义,限制少;
- 不需要预先制定聚类数;
- 可以发现类的层次关系;
- 可以聚类成其它形状。
缺点:
- 计算复杂度太高;
- 奇异值也能产生很大影响;
- 算法很可能聚类成链状。
每一类方法都有其特定的数据结构,对于服从高斯分布的数据用K-Means来进行聚类效果会比较好。而对于类别之间存在层结构的数据,用层次聚类会比较好。
2.3 密度聚类(DBSCAN)
算法:
需要两个参数: ϵ \epsilon ϵ 和 形成高密度区域所需要的最少点数 (minPts).- 它由一个任意未被访问的点开始,然后探索这个点的 ϵ \epsilon ϵ- 邻域,如果 ϵ \epsilon ϵ- 邻域有足够的点,则建立一个新的聚类,否则这个点被标签为杂音。
- 注意,这个点之后可能被发现在其它点的 ϵ \epsilon ϵ- 邻域里,而该 ϵ \epsilon ϵ- 邻域可能有足够的点,届时这个点会被加入该聚类中。
优点:
- 对噪声不敏感;
- 能发现任意形状的聚类。
缺点:
- 聚类结果与参数有很大的关系;
- 用固定参数识别聚类,但当聚类的稀疏程度不同时,相同判定标准可能会破坏聚类的自然结构,即较稀疏的聚类会被划分为多个类或密度较大且离得较近的类会被合并成一个聚类。
更多相关内容 -
基于聚类算法的图像分割技术综述
2020-02-04 13:24:38基于聚类算法的图像分割技术综述,马义德,,图像分割是指将一幅图像分解成若干互不相交区域的集合,其实质是一个像素的聚类过程。本文以图像分割的聚类实质为线索,对近几年 -
基于K-means聚类算法的图像分割方法比较及改进
2020-05-24 10:02:21为了探讨K-means算法应用于图像分割时在不同颜色空间中的聚类效果,选用了不同分辨率的多对图像进行研究,分析了基于RGB和YUV颜色空间的分割结果,并提出一种新的混合模型,即在YUV聚类距离公式中引入图像的二维信息熵的... -
k-均值聚类算法 用于 图像分割
2018-07-22 19:44:25基于opencv3 实现 基于聚类的图像分割,k-means聚类效果好,但需要注意需认为设定聚类数量,可在代码中更改。 -
聚类算法在图书馆微信公众号传播效果中的应用研究——以国家图书馆微信公众号为例.pdf
2021-08-18 23:44:58聚类算法在图书馆微信公众号传播效果中的应用研究——以国家图书馆微信公众号为例.pdf -
基于聚类算法的图像分割技术
2021-10-24 13:32:51因聚类本身是一种具有主观性且能获得良好效果的研究手段,无严格意义上的对错之分,只有“类内的相似和类它的排斥”这一基本准则。1974年,Everitt对聚类作出基础定义:基于任一相似度准则,同一类簇的样本数据具有...本科毕业设计,在此总结。
1. 聚类概念
如今,学术界并未对聚类作出一个具体定义。目前,认可度最高的观点是:聚类是一种无监督的分类手段。无标签的数据集可通过聚类分析中设定的相似性度量进行分类,形成多个类簇,满足实验的分析需要。因聚类本身是一种具有主观性且能获得良好效果的研究手段,无严格意义上的对错之分,只有“类内的相似和类它的排斥”这一基本准则。1974年,Everitt对聚类作出基础定义:基于任一相似度准则,同一类簇的样本数据具有相似特性,不同类簇的样本数据不相似。相似度准则由研究所需实验效果而定。类簇指数据集中相似样本点的汇聚。聚类要求同一类簇中的点相对密集,不同类簇间点的最小距离大于任意两个同一类簇点的距离。
1.1 基于划分的聚类算法
基于划分的聚类算法基本思想是将数据集中的样本点分成若干个子集(簇),且每个样本点只属于一个子集(簇),数学表达如下所示。划分聚类需预先给定聚类的数目或聚类中心,根据相似性度量的取值结果进行划分,使数据值靠近聚类中心。并设定聚类收敛准则,通过迭代计算更新聚类中心,对数据进一步划分,当目标函数收敛时即达到理想的聚类效果。
1.2 基于层次的聚类算法
基于层次的聚类算法基本思想是将数据样本进行层次分解。该算法是一种树形结构算法,基本思想是通过计算所属不同类簇的数据间的相似性度量,构建一个嵌套型聚类树。按照树形结构不同,可分为凝聚型层次聚类(Agglomerative Hierarchical Clustering)和分裂型层次聚类(Divisive Hierarchical Clustering)两种类型。凝聚型层次聚类运算形式为自底向上,即每个数据对象都放在不同的类簇中,通过相似性度量计算逐渐融合相近的类簇,直至融合为一类或达到某个阈值而终止。与之相反,分裂型层次聚类是自顶向下,所有数据对象都置于同一类簇,每一次运算后将会把大类簇分为更小的类簇。通过不断迭代,直至将每个数据对象置于不同类或达到某个收敛条件而终止。数学形式如下所示:
1.3 基于密度的聚类算法
基于密度的聚类算法创新性地提出了数据集是低密度区域与高密度类簇的集合这一新的认识角度。基于密度的聚类算法的中心思想是:若数据样本间的密度高于某个阈值,则将继续进行分割。即每个类簇中必须包含一定密度的数据点。
1.4基于网格的聚类算法
基于网格的聚类算法将整个数据集划分为数目有限个独立单元,构成可以实现聚类的网络结构。所有的数据处理均在网络结构上实现。该算法的优点在于运算速度快,可结合多种聚类算法形成不同的类簇结果。
2 基于K-Means算法的图像分割实验
K-means算法归属于基于划分的聚类算法,由于具有易于实现和分割效果好等优点,故在各个领域具有广阔的应用前景。K-means算法的基本步骤为:
(1)根据样本特征设定K个聚类中心。
(2)计算各个聚类中心邻域内的像素与该中心的相似性度量,将像素划分给相似性度量取值最大所属的簇,再计算每个簇数据的均值。
(3)将该均值作为新的聚类中心,不断迭代计算。当优化函数满足收敛条件(即聚类中心点不再更新),则停止计算,得到聚类结果。该算法将误差平方和作为判定聚类中心是否发生变化的评判准则。计算各个类簇内所含样本点距离中心的欧式距离的平方,也即计算每个类簇的误差。因初始设定类簇个数不同,划分的类簇也会有差异。若在两次初始参数设置不同的实验中,误差平方和越小,分割效果越好。若在同一次实验中,前后两次误差平方和在一个很小的范围内波动,则认为已收敛,结束运算。算法原理如下所示:
3. 实验结果
将每幅样本图像的聚类数从2取至9,逐一比较叶片图像的分割结果,实验结果如图上所示。22/4/9 填坑了
*4 算法实现
首先是主程序`
*`clc close all I=imread('xx.bmp'); ##输入一个二维图像,对格式没有要求 I=double(I)/255; #处理为二值 L=GLCM(I); #提取图像中的灰度纹理 subplot(2,3,1) imshow(I) title('原始图像') for i=2:6 F=imkmeans(I,i); subplot(2,3,i); imshow(F,[]); title(['聚类个数=',num2str(i)]) end
其次,着重看一下这个进行kmeans函数:
function [F,C]=imkmeans(I,C) #两个输入量分别是图像矩阵和聚类个数 if nargin~=2 error('IMKMEANS:InputParamterNotRight','只能有两个输入参数!'); end if isempty(C) K=2; C=[]; elseif isscalar(C) K=C; C=[]; else K=size(C,1); end X=exactvecotr(I); #提取特征向量 if isempty(C) C=searchintial(X,'sample',K); #寻找初始点函数 end Cprev=rand(size(C)); while true D=sampledist(X,C,'euclidean'); #用欧氏距离判断样本点是否属于这个类簇 [~,locs]=min(D,[],2); for i=1:K C(i,:)=mean(X(locs==i,:),1); end if norm(C(:)-Cprev(:))<eps break end Cprev=C; end [m,n,~]=size(I); F=reshape(locs,[m,n]);
接着,提取特征向量:
function vec=exactvecotr(img) #输入变量依旧是图像矩阵 [m,n,~]=size(img); vec=zeros(m*n,3); img=rgb2lab(img); #图像颜色模型转换 img=double(img); for j=1:n for i=1:m color=img(i,j,:);#这里聚类特征仅用了图像的颜色 wx=1;wy=1; dist=[wx*j/n,wy*i/m]; % dist=[]; #可以自己添加距离和纹理这项特征 texture=[]; % GLCM(img); vec((j-1)*m+i,:,:)=[color(:)];#堆叠在这就行 end end
对样本点之间进行欧氏距离计算,提取特征:
function D=sampledist(X,C,method,varargin) [n,p]=size(X); K=size(C,1); D=zeros(n,K); switch lower(method(1)) case 'e' for i=1:K D(:,i)=(X(:,1)-C(i,1)).^2; for j=2:p D(:,i)=D(:,i)+(X(:,j) - C(i,j)).^2; end end case 'c' for i=1:K D(:,i)=abs(X(:,1) - C(i,1)); for j=2:p D(:,i)=D(:,i) + abs(X(:,j) - C(i,j)); end end end
然后,寻找初始点和聚类中心:(这块原理忘得有点多,后续补)
function C=searchintial(X,method,varargin) switch lower(method(1)) case 's' K=varargin{1}; C=X(randsample(size(X,1),K),:); case 'u' Xmins=min(X,[],1); Xmaxs=max(X,[],1); K=varargin{1}; C=unifrnd(Xmins(ones(K,1),:), Xmaxs(ones(K,1),:)); end
function [center]=searchcenter(X,kratio) [n,~]=size(X); isleft=true(n,1); count=zeros(n,1); center=[]; kind=0; dist=0; for i=1:n for j=i+1:n dist=dist+weightdist(X(i,:),X(j,:)); end end dist=dist/((n-1)*(n-1)/2); radius1=dist*kratio(1); radius2=dist*kratio(2); while any(isleft) for i=1:n count(i)=0; if isleft(i) for j=1:n if isleft(j) dist=weightdist(X(i,:),X(j,:)); count(i)=count(i) + dist<=radius1; end end end end [~,locs]=max(count); iscenter=true; for i=1:kind dist=weightdist(X(locs,:),center(i,:)); iscenter=iscenter && dist>=radius2; if ~iscenter break; end end if iscenter kind=kind+1; center(end+1,:)=X(locs,:); for i=1:n if isleft(i) dist=weightdist(X(i,:),X(locs,:)); if dist <= radius1 isleft(i)=false; end end end else isleft(locs)=false; end end
这样就可以进行基本的聚类了。
有问题留言就行,一起进步。 -
基于加权K近邻的改进密度峰值聚类算法
2021-04-30 13:32:21密度峰值聚类算法是一种新颖的密度聚类算法,但是原算法仅仅考虑了数据的全局结构,在对分布不均匀的数据集进行聚类时效果不理想,并且原算法仅仅依据决策图上各点的分布情况来选取聚类中心,缺乏可靠的选取标准。... -
聚类算法DBSCAN的实现
2020-10-09 17:05:29DBSCAN聚类算法的实现,对图片内的物体进行分类,综合考虑了像素和像素点的位置,运行速度较慢。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。 -
针对三维点云的Mean Shift聚类算法(Matlab版)
2020-05-18 14:01:06针对点云数据进行Mean shift聚类,可以通过调整聚类算法的阈值以及搜索半径,来达到不同的聚类效果,内附有示例,运行test.m即可。 -
一种改进的数据场和决策图联合聚类算法
2021-06-07 17:05:14针对传统聚类算法在复杂多变的电磁环境中聚类质量低、参数需要预先人为设定、噪声孤立点难识别等问题,本文提出一种改进的数据场和决策图联合聚类算法。该算法主要是利用数据对象的势值和到最近大密度点的距离来实现... -
4-2 图像聚类算法
2020-08-28 21:31:322 图像聚类算法目录1 分类与聚类1.1 分类1.2 聚类1.3 聚类样本间的属性1.4 聚类的常见算法2 K-Means聚类2.1 概念2.2 步骤2.3 例子2.4 K-Means聚类与图像处理2.5 K-Means聚类优缺点优点:缺点3 层次聚类3.1 概念3.2 ...4-2 图像聚类算法
目录
- 分类与聚类
- K-Means聚类
- 层次聚类
- 密度聚类
- 谱聚类
1 分类与聚类
1.1 分类
- 分类其实是从特定的数据中挖掘模式,作出判断的过程。
- 分类学习主要过程:
(1)训练数据集存在一个类标记号,判断它是正向数据集(起积极作用,不垃圾邮件),还是负向数据集(起抑制作用,垃圾邮件);
(2)然后需要对数据集进行学习训练,并构建一个训练的模型;
(3)通过该模型对预测数据集进预测,并计算其结果的性能。
1.2 聚类
- 从广义上说,聚类就是将数据集中在 某些方面相似的数据 成员放在一起。
- 一个聚类就是一些数据实例的集合,其中处于相同聚类中的数据元素彼此相似,但是处于不同聚类中的元素彼此不同。
- 由于在聚类中那些表示数据类别的分类或分组信息是没有的,即 这些数据是没有标签 的,所以聚类通常被称为
无监督学习(Unsupervised Learning)
。 - 聚类的的 目的 也是把数据分类,但是事先是不知道如何去分的,完全是算法自己来判断各条数据之间的相似性,相似的就放在一起。
在聚类的结论出来之前,完全不知道每一类有什么特点,一定要根据聚类的结果通过人的经验来分析,看看聚成的这一类大概有什么特点。
总
-
聚类主要是"物以类聚",通过相似性把相似元素聚集在一起,它没有标签;
-
而分类通过标签来训练得到一个模型,对新数据集进行预测的过程,其数据存在标签。
-
聚类:通过相似性,把相似的元素聚集到一起,没有标签 —— 无监督
-
分类:有标签,通过标签来训练得到一个模型,对新数据进行预测 —— 有监督
1.3 聚类样本间的属性
- 有序属性 西瓜的甜度 0.1 0.5 0.9
- 无序属性 性别
1.4 聚类的常见算法
聚类算法分为三大类:
- 原型聚类(包含3个子类算法):
• K均值聚类算法
• 学习向量量化
• 高斯混合聚类 - 层次聚类
- 密度聚类
原型聚类: 算法首先对原型(原始数据)初始化,然后对原型迭代更新求解
2 K-Means聚类
2.1 概念
K-Means聚类
是最常用的聚类算法,最初起源于信号处理,其目标是将数据点划分为K个类簇,找到每个簇的中心并使其度量最小化。- k-means算法是一种原型聚类算法。
- 优缺:
- 该算法的最大优点是简单、便于理解,运算速度较快;
- 缺点是只能应用于连续型数据,并且要在聚类前指定聚集的类簇数。
[注]
- 图例是由自己观察分析得出
- 聚类算法只能聚成想要的堆数(按照相似,就放在一起)
2.2 步骤
k-means聚类算法的分析流程:
第一步,确定K值,即将数据集聚集成K个类簇或小组。
第二步,从数据集中随机选择K个数据点作为质心(Centroid)或数据中心。
第三步,分别计算每个点到每个质心之间的距离,并将每个点划分到离最近质心的小组。
第四步,当每个质心都聚集了一些点后,重新定义算法选出新的质心。(对于每个簇,计算其均值,即得到新的k个质心点)
第五步,迭代执行第三步到第四步,直到迭代终止条件满足为止(分类结果不再变化)2.3 例子
2.4 K-Means聚类与图像处理
- 在图像处理中,通过K-Means聚类算法可以实现图像分割、图像聚类、图像识别等操作。
- 我们通过K-Means可以将这些像素点聚类成K个簇,然后使用每个簇内的质心点来替换簇内所有的像素点,这样就能实现在不改变分辨率的情况下量化压缩图像颜色,实现图像颜色层级分割。
2.5 K-Means聚类优缺点
优点:
1.是解决聚类问题的一种经典算法,简单、快速
2.对处理大数据集,该算法保持可伸缩性和高效率
3.当结果簇是密集的,它的效果较好缺点
1.在簇的平均值可被定义的情况下才能使用,可能不适用于某些应用
2.必须事先给出k(要生成的簇的数目),而且对初值敏感,对于不同的初始值,可能会导致不同结果。
3.不适合于发现非凸形状的簇或者大小差别很大的簇
4.对躁声和孤立点数据敏感
3 层次聚类
3.1 概念
- 层次聚类 是一种很直观的算法。顾名思义就是要一层一层地进行聚类。
- 层次法(Hierarchicalmethods) 先计算样本之间的距离。每次将距离最近的点合并到同一个类。然后,再计算类与类之间的距离,将距离最近的类合并为一个大类。不停的合并,直到合成了一个类。其中类与类的距离的计算方法有:最短距离法,最长距离法,中间距离法,类平均法等。比如最短距离法,将类与类的距离定义为类与类之间样本的最短距离。
- 层次聚类算法根据层次分解的顺序分为:自下底向上和自上向下,即凝聚的层次聚类算法和分裂的层次聚类算法(agglomerative和divisive),也可以理解为自下而上法(bottom-up)和自上而下法(topdown)
3.2 凝聚层次聚类的流程
-
凝聚型层次聚类的策略是先将每个对象作为一个簇,然后合并这些原子簇为越来越大的簇,直到所有对象都在一个簇中,或者某个终结条件被满足。绝大多数层次聚类属于凝聚型层次聚类,它们只是在簇间相似度的定义上有所不同。
-
这里给出采用最小距离的凝聚层次聚类算法流程:
(1) 将每个对象看作一类,计算两两之间的最小距离;
(2) 将距离最小的两个类合并成一个新类;
(3) 重新计算新类与所有类之间的距离;
(4) 重复(2)、(3),直到所有类最后合并成一类。 -
特点:
• 凝聚的层次聚类并没有类似K均值的全局目标函数,没有局部极小问题或是很难选择初始点的问题。
• 合并的操作往往是最终的,一旦合并两个簇之后就不会撤销。
• 当然其计算存储的代价是昂贵的。
3.3 层次聚类的优缺点
- 优点:
1.距离和规则的相似度容易定义,限制少;
2.不需要预先制定聚类数;
3.可以发现类的层次关系;
4.可以聚类成其它形状 - 缺点:
1.计算复杂度太高;
2.奇异值也能产生很大影响;
3.算法很可能聚类成链状
3.4 树状图分类判断
- 想分两类时,就从上往下数有两根竖线时进行切割,那么所对应的竖线下面所连接的为一类
- 想分三类时,就从上往下数有三根竖线时进行切割,那么所对应的竖线下面所连接的为一类
3.5 K-Means与层次聚类
- 每一种聚类方法都有其特定的数据结构,对于服从高斯分布的数据用K-Means来进行聚类效果会比较好。
- 而对于类别之间存在层结构的数据,用层次聚类会比较好。
4 密度聚类
4.1 密度聚类DBSCAN算法:
需要两个参数:ε (eps) 和形成高密度区域所需要的最少点数 (minPts)
• 它由一个任意未被访问的点开始,然后探索这个点的 ε-邻域,如果ε-邻域里有足够的点,则建立一个新的聚类,否则这个点被标签为杂音。
• 注意,这个点之后可能被发现在其它点的 ε-邻域里,而该 ε-邻域可能有足够的点,届时这个点会被加入该聚类中。4.2 密度聚类DBSCAN的优缺点
- 优点:
- 对噪声不敏感;
- 能发现任意形状的聚类。
- 缺点:
- 但是聚类的结果与参数有很大的关系;
- 用固定参数识别聚类,但当聚类的稀疏程度不同时,相同的判定标准可能会破坏聚类的自然结构,即较稀的聚类会被划分为多个类或密度较大且离得较近的类会被合并成一个聚类。
5 谱聚类
5.1 概念
- 根据数据构造一个 图结构(Graph),Graph的每一个节点对应一个数据点,将相似的点连接起来,并且边的权重用于表示数据之间的相似度。把这个 Graph 用邻接矩阵的形式表示出来,记为 W 。
- 把 W 的每一列元素加起来得到 N 个数,把它们放在对角线上(其他地方都是零),组成一个 N * N的矩阵,记为 D 。并令 L = D-W。
- 求出 L 的前 k 个特征值,以及对应的特征向量。
- 把这 k 个特征(列)向量排列在一起组成一个 N * k 的矩阵,将其中每一行看作 k维空间中的一个向量,并使用 K-means 算法进行聚类。聚类的结果中每一行所属的类别就是原来 Graph 中的节点亦即最初的N 个数据点分别所属的类别。
5.2 步骤
简单抽象谱聚类过程,主要有两步:
- 构图,将采样点数据构造成一张网图。
- 切图,即将第一步构造出来的按照一定的切边准则,切分成不同的图,而不同的子图,即我们对应的聚类结果
-
使用FCM聚类算法进行图像分割
2020-06-16 22:07:37FCM进行图像分割的评价指数使用FCM聚类算法进行图像分割Bezdek划分系数Xie_Beni系数重构错误率V_RE如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、...FCM进行图像分割的评价指数
使用FCM聚类算法进行图像分割
使用无监督算法进行图像分割,往往这类图像没有真实值,没办法用有监督的指标进行评价;这里介绍三种内部评价指标:Bezdek划分系数、Xie_Beni系数、重构错误率V_RE和PBM指标。
Bezdek划分系数
V P C V_{PC} VPC 是Bezdek划分系数,它主要目的是重新刻画分割后的像素的隶属度,定义如下:
V P C = 1 n ∑ i = 1 c ∑ j = 1 n u i j 2 V_{P C}=\frac{1}{n}\sum_{i=1}^{c} \sum_{j=1}^{n} u_{i j}^{2} VPC=n1i=1∑cj=1∑nuij2即所有元素隶属于各个分类隶属度的平方和,对图像进行分割时,性能较优的聚类算法是使图像中
像素归属于某一类的隶属度尽可能地大,反之属于其他聚类的隶属度尽可能的小,即 V P C V_{PC} VPC 的值越大,表明聚类的效果越好。1Xie_Beni系数
V X B V_{XB} VXB是 Xie-Beni系数,其定义为:
V X B = ∑ i = 1 c ∑ j = 1 n u i j 2 ∥ x j − v i ∥ 2 n ( min j ≠ k ∥ v j − v k ∥ 2 ) V_{\mathrm{XB}}=\frac{\sum_{i=1}^{c} \sum_{j=1}^{n} u_{i j}^{2}\left\|x_{j}-v_{i}\right\|^{2}}{n\left(\min _{j \neq k}\left\|v_{j}-v_{k}\right\|^{2}\right)} VXB=n(minj=k∥vj−vk∥2)∑i=1c∑j=1nuij2∥xj−vi∥2该系数反映了图像聚类内部的一种距离度量,在进行图像分割时,期望聚类内部的像素更加紧密,即 V X B V_{XB} VXB 越小,则说明聚类的效果越好。
重构错误率V_RE
V R E V_{RE} VRE是图像的重构错误率,其定义如下:
V R E = 1 n ∑ i = 1 n ∥ I ′ ( i ) − I ( i ) ∥ 2 V_{RE}=\frac{1}{n} \sum_{i=1}^{n}\left\|I^{\prime}(i)-I(i)\right\|^{2} VRE=n1i=1∑n∥I′(i)−I(i)∥2
它是分析分割后的重构图像与初始图像间的差距, I ′ ( i ) I^{\prime}(i) I′(i)为重构图像的第 i i i个像素的灰度值,定义为:
I ′ ( i ) = ∑ k = 1 c u k i 2 I ( i ) ∑ k = 1 c u k i 2 I^{\prime}(i)=\frac{\sum_{k=1}^{c} u_{k i}^{2} I(i)}{\sum_{k=1}^{c} u_{k i}^{2}} I′(i)=∑k=1cuki2∑k=1cuki2I(i)对图像进行分割后,新的隶属度和聚类中心对图像进行重构,重构后的图像应与原图像尽可能的相似,即表明 V R E V_{RE} VRE的值越小,算法的分割效果越好。
PBM指标
PBM指标是一种聚类有效性指标,定义如下:
P B M = ( 1 K × E 1 E K × D K ) 2 P B M =\left(\frac{1}{K} \times \frac{E_{1}}{E_{K}} \times D_{K}\right)^{2} PBM=(K1×EKE1×DK)2P B M PBM PBM由三部分组成,分别是 1 / K 1 / K 1/K 、 E 1 / E k E_{1} / E_{k} E1/Ek 和 D K D_{K} DK。第一项中 K K K是提前给定的图像分割类别数,第二项中 E 1 E_{1} E1对于一个给定的数据集,为一个常值。而 E k E_{k} Ek是待分类数据与个体中聚类中心的模糊距离之和, P B M PBM PBM值会随着 E k E_{k} Ek的减小而增大。第三项中 D K D_{K} DK是个体中的所有聚类中心对之间的最大距离。 P B M PBM PBM指标达到最大值,取得最优划分。
代码2
function [Bezdek_V, Xie_Beni_V, V_RE, V_PBM] = Evaluation_index(I, U, V) % Evaluation_index为聚类分割评价指数 % 输入: 原始待聚类数据I, 隶属度矩阵U, 聚类中心V % 输出: Bezdek划分系数, Xie_Beni系数, 重构错误率V_RE,V_PBM %% % 原始待聚类数据I,n代表样本数目,d代表每个样本的维数 [n,d] = size(I); % 隶属度矩阵U,c代表聚类类别数目,n代表样本数目 [c,n] = size(U); % 聚类中心V,c为聚类中心的数目,d代表每个样本的维数 [c,d] = size(V); %% Bezdek划分系数 % 所有元素隶属于各个分类隶属度的平方和 Bezdek_V = sum(sum(U.^2)) / n ; %% Xie_Beni系数、重构错误率V_RE % Xie_Beni系数 Xie_Beni_V = 0; % 初始化重构图像像素值 I_RE = zeros(n,d); % XB指数分母项,最近类间距离 % 初始化最近的类间距离的平方为 前两个聚类中心的距离平方 % 欧氏距离:向量按元素求幂,再求和 min_V = sum((V(1,:)-V(2,:)).^2); for i = 1:c for j = 1:c if(i-j ~= 0 && sum((V(i,:)-V(j,:)).^2) < min_V) % 排除自己和自己之间的距离0之后,遇到更小的类间距离 即 更新初始类间距离 min_V = sum((V(i,:)-V(j,:)).^2); end end end %% % 遍历样本 for i = 1:n % temp表示重构图像像素值的分子,temp1表示其分母 temp = 0; temp1 = 0; % 遍历类别 for j = 1:c % XB指数的分子 Xie_Beni_V = Xie_Beni_V + U(j,i)^2 * sum((I(i,:)- V(j,:)).^2); % 重构图像像素值的分子和分母 temp = temp + U(j,i)^2*I(i,:); temp1 = temp1 + U(j,i)^2; end % 重构图像像素值 I_RE(i,:) = temp / temp1; end % 最终的XB指数等于分子除以分母,n为样本数目,min_V为最小类间距离 Xie_Beni_V = Xie_Beni_V / (n * min_V); % 重构错误率V_RE V_RE = sum(sum((I_RE - I).^2)) / n; %% PBM指标 % 计算最大类间距离 max_V = sqrt(sum((V(1,:)-V(2,:)).^2)); for i = 1:c for j = 1:c if(i-j ~= 0 && sqrt(sum((V(i,:)-V(j,:)).^2)) > max_V) % 排除自己和自己之间的距离0之后,遇到更大的类间距离 即 更新初始类间距离 max_V = sqrt(sum((V(i,:)-V(j,:)).^2)); end end end % 初始化Ek Ek = 0; for i = 1:n for j = 1:c Ek = Ek + U(j,i) * sqrt(sum((I(i,:)- V(j,:)).^2)); end end % 初始化E1 E1 = 0; for i = 1:n E1 = E1 + U(1,i) * sqrt(sum((I(i,:)- V(1,:)).^2)); end % V_PBM V_PBM = (E1 * max_V / (c * Ek))^2; end
参考资料
王民, 李媛, 张立材. 基于纹理特征的盲道区域分割算法[J]. 信息通信, 2017(7). ↩︎
-
聚类算法 ---- 大数据聚类算法综述
2021-08-19 22:53:14文章大纲简介聚类算法的分类相似性度量方法大数据聚类算法聚类算法对比参考文献 简介 随着数据量的迅速增加如何对大规模数据进行有效的聚类成为挑战性的研究课题,面向大数据的聚类算法对传统金融行业的股票投资... -
常用的聚类算法及聚类算法评价指标
2021-12-27 00:21:39作者 |荔枝boy来源 |磐创AI引用 | 基于图的聚类分析研究—张涛【导读】:本文介绍了常用的聚类算法及聚类算法评价指标。1. 典型聚类算法1.1 基于划分的方法代表:kmeans算... -
基本蚁群聚类算法及其改进算法Matlab源代码
2018-01-31 19:51:34该算法,解决了不收敛的问题,聚类效果非常好(效果图如附件图片所示)。改进的蚁群算法是基于遗传算法的改进,在基本遗传算法的基础之上,加入了变异因子,产生变异,从而更快的收敛。 -
基于Kmeans聚类算法实现图像分割(从原理开始实现)
2020-03-12 15:53:55一、Kmeans聚类算法基本原理 K-Means算法的思想很简单,对于给定的样本集,按照样本之间的距离大小,将样本集划分为K个簇。让簇内的点尽量紧密的连在一起,而让簇间的距离尽量的大。 以彩色图像为例:基于彩色图像的... -
基于K均值聚类算法的图像分割(Matlab)
2021-11-25 22:22:01文章目录一、K均值聚类算法是什么?1、什么是聚类?2、初探K均值聚类算法3、K均值算法的原理与理解二、K均值聚类算法如何在图像分割上应用?三、Matlab仿真 一、K均值聚类算法是什么? 1、什么是聚类? 聚类是指通过... -
[python] Kmeans文本聚类算法+PAC降维+Matplotlib显示聚类图像源码
2016-01-20 05:07:01[python] Kmeans文本聚类算法+PAC降维+Matplotlib显示聚类图像 http://blog.csdn.net/eastmount/article/details/50545937 包括输入文档txt,共1000行数据,每行都是分词完的文本。 本文主要讲述以下几点: 1.通过... -
基于聚类的“图像分割”案例——K-means聚类算法
2020-04-05 20:35:15Machine_learning/基于聚类的整图分割/demo1.jpg' imgData, row, col = loadData(filePath= path) print(imgData) print(row) print(col) #加载Kmeans聚类算法 km = KMeans(n_clusters= 3) #聚类获取每个像素所属的... -
【OpenCv】图像分割——聚类算法
2022-03-25 11:15:44KMeans算法的作者是MacQueen, KMeans的算法是对数据进行分类的算法,采用的硬分类方式,是属于非监督学习的算法; 对于给定的样本集,按照样本之间的距离大小,将样本划分为K个簇,让簇内的点尽量紧密的连接在一起... -
覆盖聚类算法 (2005年)
2021-05-12 12:34:02该算法采用覆盖的概念将比较集中的样本聚合在一起,从而发现隐含在样本集中的类,对于周围稀疏的样本结合最短距离法,获得聚类效果,并用实验数据对分层聚类方法、LBG方法与覆盖聚类算法进行比较,证明了覆盖聚类... -
【聚类算法】10种Python聚类算法完整操作示例(建议收藏
2021-03-12 15:23:01点击上方,选择星标,每天给你送干货!来源:海豚数据科学实验室著作权归作者所有,本文仅作学术分享,若侵权,请联系后台删文处理聚类或聚类分析是无监督学习问题。它通常被用作数据分析技术,用于发现... -
聚类算法实现流程
2022-04-06 13:44:11聚类算法实现流程 -
图解机器学习算法(13) | 聚类算法详解(机器学习通关指南·完结)
2022-03-10 18:42:33聚类是最常见的无监督学习算法。本文讲解聚类问题常见算法及用途,包括划分聚类的K-Means算法、K-Medoids算法,层次聚类的Single-Linkage 算法、Complete-Linkage算法,和DB-SCAN算法。 -
机器学习(聚类十一)——不同聚类算法在不同数据分布情况下的聚类效果
2020-12-21 11:28:07这篇博客来一个汇总的实例,分别创建圆形数据、月牙形数据、聚团数据以及随机数据,并测试不同数据在各种不同聚类算法中的聚类效果以及消耗时间。 import time import warnings import numpy as np import ... -
Velodyne Lidar点云聚类算法
2019-04-01 17:12:19输入Velodyne Lidar数据,对点云进行聚类,基于Qt图像界面开发,算法满足实时性,分割效果好,可用于16线,32线,64线激光雷达数据. -
谱聚类算法
2021-12-26 16:12:11谱聚类算法小组作业 -
混合编码方式的图像聚类算法
2021-01-14 13:19:52基于群体智能优化算法的图像聚类分析,大多数都采用...在仿真实验中,采用4组数据集对算法进行聚类有效性测试,并将其与4种常用的聚类算法进行对比,实验结果表明该算法具有较强的全局搜索能力,稳定性高、聚类效果好。 -
【机器学习】聚类算法详细介绍(理论+图解)
2021-07-16 22:14:29一、聚类算法的定义 像一些经典的算法比如随机森林、支持向量机这些算法我们都知道,他们都是基于对数据标签进行学习,但是往往有的时候我们获得的数据是没有标签的,只有特征列数据等,这个时候我们就不能够使用... -
【图像分割】基于谱聚类算法实现图像分割matlab源码
2021-08-25 12:52:23谱聚类在最近几年变得受欢迎起来,主要原因就是它实现简单,聚类效果经常优于传统的聚类算法(如K-Means算法)。刚开始学习谱聚类的时候,给人的感觉就是这个算法看上去很难,但是当真正的深入了解这个算法的时候,...