分裂的层次聚类方法

原理解读

DIANA(Divisive Analysis):采用自顶向下的策略，最初将所有对象置于一个类中，然后根据某些准则将这些类别逐渐细分。细分过程反复进行直到类别达到预期的数目。

核心思想

1. 将所有样本都作为同一类

2. 分裂所有类别中到该类中心距离最大的样本，将其单独作为一类，按照最近邻分类，直到满足某个终止条件
$$d_{max}=\underset{C_i \subseteq C}{max} \ (\underset{x_i \in C_i}{max} \ {d(x_i,\overline C_i)}) \ , \ 其中\overline {C_i}=\frac {1}{\lvert C_i \rvert}\underset{x_i \in C_i}{\sum}{x_i}$$

DIANA

算法流程

DIANA

代码实战

代码中所用数据集可以查看相关文档，数据集(Data Set)

DIANA_main.m

clear;clc;close all;
load('..\\cluster_gauss.mat');
%输入x的矩阵
x=data;
randIndex = randperm(size(x,2));
x=x(:,randIndex);
%希望划分的类别数
class_num=3;
%样本数
sample_num=size(x,2);
%特征数目
feat_num=size(x,1);
%尺度缩放到0-1
x_scale=zeros(size(x));
for i=1:feat_num
    x_scale(i,:)=(x(i,:)-min(x(i,:)))/(max(x(i,:))-min(x(i,:)));
end
[y,class_center]=DIANA_classify(x_scale,sample_num,class_num);
%样本中心尺度复原
for i=1:feat_num
    class_center(i,:)=(max(x(i,:))-min(x(i,:)))*class_center(i,:)+min(x(i,:));
end
%如果数据的特征是二维的，可以绘图表示
if feat_num==2
    DIANA_display(x,y,class_center,sample_num,class_num);
else
    disp('The Feature Is Not Two-Dimensional');
end

DIANA_classify.m

function [y,class_center]=DIANA_classify(x_scale,sample_num,class_num)
if class_num==1
    class_center=sum(x_scale,2)/sample_num;
    y=ones(1,sample_num);
else
    %给每一个样本都视为0类
    y=zeros(1,sample_num);
    distance=zeros(sample_num);
    for i=1:sample_num
        distance(i,:)=sum((x_scale-repmat(x_scale(:,i),1,sample_num)).^2);
    end
    %找到距离最远的两个样本
    [row,col]=find(distance==max(max(distance)),1);
    %将row分为第一类,col分为第二类
    y(row)=1;
    y(col)=2;
    %设置第一类和第二类的中心
    class_center(:,1)=x_scale(:,row);
    class_center(:,2)=x_scale(:,col);
    %目前的类别数
    class_num_temp=2;
    distance_min=zeros(1,sample_num);
    while class_num_temp~=class_num
        for i=1:sample_num
            %求每个样本到每一类的距离
            distance=sum((class_center-repmat(x_scale(:,i),1,class_num_temp)).^2);
            %求出每个样本到每一类距离最小值
            distance_min(i)=distance(find(distance==min(distance),1));
        end
        %找到距离最大值作为一类
        temp=find(distance_min==max(distance_min),1);
        %类别数+1
        class_num_temp=class_num_temp+1;
        %修改类别信息
        y(temp)=class_num_temp;
        for i=1:class_num_temp
            %更新类别的中心
            class_center(:,i)=sum(x_scale(:,y==i),2)/sum(y==i);
        end
    end
    %采用最近邻进行分类
    for i=1:sample_num
        distance=sum((class_center-repmat(x_scale(:,i),1,class_num_temp)).^2);
        y(i)=find(distance==min(distance),1);
    end
end

DIANA_display.m

function DIANA_display(x,y,class_center,sample_num,class_num)
color_bar=zeros(class_num,3);
hold on;
for i=1:class_num
    color_bar(i,:)=[rand(1),rand(1),rand(1)];
    %绘制样本中心，用*表示
    plot(class_center(1,i),class_center(2,i),'color',color_bar(i,:),'marker','*')
end
for i=1:sample_num
    %绘制数据集，用o表示
    plot(x(1,i),x(2,i),'color',color_bar(y(i),:),'marker','o');
end
hold off;

实验结果

DIANA

性能比较

优点：
- 算法简单，容易理解
- 不依赖初始值的选择
- 对于类别较少的训练集分类较快

缺点：

对噪声数据敏感
分裂操作不能撤销
需要在测试前知道类别的个数
对于类别较多的训练集分类较慢
只适合分布呈凸型或者球形的数据集
对于高维数据，距离的度量并不是很好