本科毕业设计，在此总结。

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

这样就可以进行基本的聚类了。
有问题留言就行，一起进步。

目录

1. 分类与聚类
2. K-Means聚类
3. 层次聚类
4. 密度聚类
5. 谱聚类

1 分类与聚类

1.1 分类

• 分类其实是从特定的数据中挖掘模式，作出判断的过程。
• 分类学习主要过程：
  （1）训练数据集存在一个类标记号，判断它是正向数据集（起积极作用，不垃圾邮件），还是负向数据集（起抑制作用，垃圾邮件）；
  （2）然后需要对数据集进行学习训练，并构建一个训练的模型；
  （3）通过该模型对预测数据集进预测，并计算其结果的性能。

1.2 聚类

• 从广义上说，聚类就是将数据集中在 某些方面相似的数据 成员放在一起。
• 一个聚类就是一些数据实例的集合，其中处于相同聚类中的数据元素彼此相似，但是处于不同聚类中的元素彼此不同。
• 由于在聚类中那些表示数据类别的分类或分组信息是没有的，即 这些数据是没有标签 的，所以聚类通常被称为 无监督学习（Unsupervised Learning）。
• 聚类的的 目的 也是把数据分类，但是事先是不知道如何去分的，完全是算法自己来判断各条数据之间的相似性，相似的就放在一起。
  在聚类的结论出来之前，完全不知道每一类有什么特点，一定要根据聚类的结果通过人的经验来分析，看看聚成的这一类大概有什么特点。

总

• 聚类主要是"物以类聚"，通过相似性把相似元素聚集在一起，它没有标签；

• 而分类通过标签来训练得到一个模型，对新数据集进行预测的过程，其数据存在标签。

• 聚类：通过相似性，把相似的元素聚集到一起，没有标签 —— 无监督

• 分类：有标签，通过标签来训练得到一个模型，对新数据进行预测 —— 有监督

1.3 聚类样本间的属性

1. 有序属性 西瓜的甜度 0.1 0.5 0.9
2. 无序属性 性别

1.4 聚类的常见算法

聚类算法分为三大类：

1. 原型聚类(包含3个子类算法)：
   • K均值聚类算法
   • 学习向量量化
   • 高斯混合聚类
2. 层次聚类
3. 密度聚类

原型聚类： 算法首先对原型（原始数据）初始化，然后对原型迭代更新求解

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的优缺点

• 优点：

1. 对噪声不敏感；
2. 能发现任意形状的聚类。

• 缺点：

1. 但是聚类的结果与参数有很大的关系；
2. 用固定参数识别聚类，但当聚类的稀疏程度不同时，相同的判定标准可能会破坏聚类的自然结构，即较稀的聚类会被划分为多个类或密度较大且离得较近的类会被合并成一个聚类。

5 谱聚类

5.1 概念

1. 根据数据构造一个 图结构（Graph），Graph的每一个节点对应一个数据点，将相似的点连接起来，并且边的权重用于表示数据之间的相似度。把这个 Graph 用邻接矩阵的形式表示出来，记为 W 。
2. 把 W 的每一列元素加起来得到 N 个数，把它们放在对角线上（其他地方都是零），组成一个 N * N的矩阵，记为 D 。并令 L = D-W。
3. 求出 L 的前 k 个特征值，以及对应的特征向量。
4. 把这 k 个特征（列）向量排列在一起组成一个 N * k 的矩阵，将其中每一行看作 k维空间中的一个向量，并使用 K-means 算法进行聚类。聚类的结果中每一行所属的类别就是原来 Graph 中的节点亦即最初的N 个数据点分别所属的类别。

5.2 步骤

简单抽象谱聚类过程，主要有两步：

1. 构图，将采样点数据构造成一张网图。
2. 切图，即将第一步构造出来的按照一定的切边准则，切分成不同的图，而不同的子图，即我们对应的聚类结果

使用FCM聚类算法进行图像分割

使用无监督算法进行图像分割，往往这类图像没有真实值，没办法用有监督的指标进行评价；这里介绍三种内部评价指标：Bezdek划分系数、Xie_Beni系数、重构错误率V_RE和PBM指标。

Bezdek划分系数

$V_{PC}$ 是Bezdek划分系数，它主要目的是重新刻画分割后的像素的隶属度，定义如下：
$$V_{PC}=\frac{1}{n}\sum _{i=1}^c\sum _{j=1}^n{u}_{ij}^2$$

即所有元素隶属于各个分类隶属度的平方和，对图像进行分割时，性能较优的聚类算法是使图像中
像素归属于某一类的隶属度尽可能地大，反之属于其他聚类的隶属度尽可能的小，即$V_{PC}$ 的值越大，表明聚类的效果越好。¹

Xie_Beni系数

$V_{XB}$是 Xie-Beni系数，其定义为：
$$V_{\mathrm{X}\mathrm{B}}=\frac{{\sum }_{i=1}^c{\sum }_{j=1}^n{u}_{ij}^2{\Vert x_j-v_i\Vert }^2}{n\left({\min }_{j\ne k}{\Vert v_j-v_k\Vert }^2\right)}$$

该系数反映了图像聚类内部的一种距离度量，在进行图像分割时，期望聚类内部的像素更加紧密，即 $V_{XB}$ 越小，则说明聚类的效果越好。

重构错误率V_RE

$V_{RE}$是图像的重构错误率，其定义如下：

$$V_{RE}=\frac{1}{n}\sum _{i=1}^n{\Vert I^{\prime }(i)-I(i)\Vert }^2$$

它是分析分割后的重构图像与初始图像间的差距，$I^{\prime }(i)$为重构图像的第 $i$个像素的灰度值，定义为：
$$I^{\prime }(i)=\frac{{\sum }_{k=1}^c{u}_{ki}^{2}I(i)}{{\sum }_{k=1}^c{u}_{ki}^2}$$

对图像进行分割后，新的隶属度和聚类中心对图像进行重构，重构后的图像应与原图像尽可能的相似，即表明 $V_{RE}$的值越小，算法的分割效果越好。

PBM指标

PBM指标是一种聚类有效性指标，定义如下：
$$PBM={\left(\frac{1}{K}\times \frac{E_1}{E_K}\times D_K\right)}^2$$

$PBM$由三部分组成，分别是$1/K$ 、$E_1/E_k$ 和 $D_K$。第一项中$K$是提前给定的图像分割类别数，第二项中$E_1$对于一个给定的数据集，为一个常值。而$E_k$是待分类数据与个体中聚类中心的模糊距离之和，$PBM$值会随着$E_k$的减小而增大。第三项中 $D_K$是个体中的所有聚类中心对之间的最大距离。$PBM$指标达到最大值，取得最优划分。

代码²

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

参考资料