机器学习笔记-层次聚类_agnes算法流程

前言

  层次聚类和K-means聚类以及DBSCAN聚类又截然不同。层次聚类的核心思想是试图在不同层次对数据集进行划分，形成树形的结构。本章主要介绍层次聚类的思想，算法具体步骤和Matlab编程实践。

算法原理

  层次聚类有两种思路：自底向上和自顶向下，这两种思路带来的是两种不同的算法。本文主要介绍AGNES（自底向上）。
  自底向上如果从树状图中看，就是从树的最底端不断向上搜索。先将数据集中的每个样本看作一个初始聚类簇（如果有$N$个样本点，则初始时有$N$个簇），然后在算法运行的每一步中找到距离最近的两个样本点，将这两个样本点合并为一个簇，不断重复该过程，直至合并得到的簇减少到我们初始规定的最小簇数$k$。
  在这过程中最重要的就是确定距离计算公式。前面章节我们以及详细叙述了计算两个样本点的距离公式，有欧氏距离、曼哈顿距离、切比雪夫距离等等。但是这些距离公式只是适用于计算两个样本之间的距离，而在层次聚类中需要比较样本和簇、簇和簇之间的距离。所以需要定义新的计算方式，具体来看：
给定两个簇$C_i$与$C_j$，可通过如下的式子计算距离：
$$\begin{gathered} 最小距离：d_{min}(C_i,C_j)=\underset{x\in C_i,z\in C_j}{\min }dist(x,z) \\ 最大距离：d_{max}(C_i,C_j)=\underset{x\in C_i,z\in C_j}{\max }dist(x,z) \\ 平均距离：d_{avg}(C_i,C_j)=\frac{1}{|C_i||C_j|}\sum _{x\in C_i}\sum _{z\in C_j}dist(x,z) \end{gathered}$$
  显然最小距离由两个簇的最近样本距离，最大距离由两个簇的最远样本决定，而平均距离则由两个簇的所有样本共同决定，当聚类簇距离由$d_{min},d_{max}$或$d_{avg}$计算时，AGNES算法被相应的称为“单链接”、“全链接”或“均链接”算法。
下面是AGNES算法的流程

（图片来自《机器学习》-西瓜书）

实战

实战数据集仍然使用西瓜书中的数据集。
main.m

% 层次聚类
clc;
clear
tic
load data
result = AGNES(data,4);
data_index = zeros(length(data),1);
% 对结果进行处理，方便后续的可视化
for m = 1:length(result)
    data_index(result{m}) = m;
end
gscatter(data(:,1),data(:,2),data_index,'rkgby')
legend('类别1','类别2','类别3','类别4')
grid on
axis([0,1,0,0.8])
title("DBSCAN散点图")
toc
% 绘制层次聚类图
figure(2)
Y = pdist(data);
Z = linkage(Y,'single');
dendrogram(Z);
title('层次聚类树状图')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

AGNES.m

function [result] = AGNES(D,k)
%{
Solve   AGNES层次聚类算法实现
Input   D——训练数据集
        k——聚类数
OutPut  result——聚类结果
%}

% 获取样本
[Sample_number,~] = size(D);
% 初始化元胞，后续存储聚类过程
C = cell(1);
% 初始化下标，后续可以用到
Index = 1:Sample_number;
% 将当前所有样本各置一簇
for i =1:Sample_number
    C{i} = Index(i);
end

M =zeros(Sample_number);
% 计算距离矩阵
for i =1:Sample_number
    for j = i+1 :Sample_number
        M(i,j) = norm(D(C{i},:) - D(C{j},:));
        M(j,i) = M(i,j);
    end
end

% 设置当前聚类簇数
q = Sample_number;

while q > k
    % 找到最小的下标j与i
    Temp = M;
    Temp(Temp == 0) = inf;
    [minv,ind] = min(Temp,[],2);
    [~,min_i] = min(minv);
    min_j = ind(min_i);
    % 保证min_i下标小于min_j下标
    if min_j < min_i
        temp = min_j;
        min_j = min_i;
        min_i = temp;
    end
    % 将簇i与簇j合并为新簇
    C{min_i} = union(C{min_i},C{min_j});
    % 修改簇
    for j = min_j + 1:q
        C{j-1} = C{j};
    end
    % 删除最后一个簇
    C(q) = [];
    % 删除距离矩阵M的第min_j行和min_j列
    M(min_j,:) = [];
    M(:,min_j) = [];
    for i =1:q - 1
        % 计算min_i与i的距离d
        %         if i == min_i
        %             M(min_i,i) = 0;
        %         else
        %             d = 0;
        %             for j = 1:length(C{min_i})
        %                 for m = 1:length(C{i})
        %                     d  = d + norm(D(C{min_i}(j)) - D(C{i}(m)));
        %                 end
        %             end
        %             M(min_i,i) = d/(length(C{min_i})*length(C{i}));
        %         end
        dd = [];
        % 计算min_i与i的距离d
        if i == min_i
            M(min_i,i) = 0;
        else
            for j =1:length(C{min_i})
                for m =1:length(C{i})
                    dd = [dd,norm(D(C{min_i}(j),:) - D(C{i}(m),:))];
                end
            end
            M(min_i,i) = max(dd);
        end
        M(i,min_i) = M(min_i,i);
    end
    q = q - 1;
end
result = C;
end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

运行结果：

Matlab中有自带的绘制树状图的函数，我们只需要调用即可。