层次聚类试图在不同层次对数据集进行划分,从而形成树形的聚类结构.数据集的划分可采用"自底向上"的聚合策略,也可采用"自顶向下"的拆分策略.
AGNES
AGNES是一种自底向上的聚类算法.它先将数据集中的每个样本看做一个初始聚类簇,然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并,重复该过程,直到剩余聚类簇个数达到预期个数.
两个聚类簇直接的距离有三种计算方法:
- 最小距离,即两个聚类簇中离的最近的两个点的距离.
- 最大距离,即两个聚类簇中离的最远的两个点的距离
- 平均距离,即两个聚类簇中所有点的平均距离.
AGNES的聚类步骤如下:
步骤1:初始化每一个数据为一个类簇.
步骤2:找到距离最大的两个类簇,将其合并.
步骤3:重复步骤2,知道剩余类簇个数k等于设定值.
聚类特征
BIRCH使用聚类特征概括描述各簇的信息,其定义如下:
其中N为该簇中数据点的数量,矢量
为各数据点的线性求和,标量
为各数据点的平方和.
CF有一个很好的性质,就是满足线性关系.设和分别表示两个不相交的簇的聚类特征,如果将这两个簇合并成一个大簇,则大簇的聚类特征为
假设簇1有三个数据点(2,5)、(3,2)和(4,3),簇1的聚类特征是
聚类特征本质上是给定簇的统计汇总,可以有效地对数据进行压缩,而且基于聚类特征可以很容易地推导出簇的许多统计量和距离度量。假设给定簇中有N个D维的数据点,,则在簇的统计量方面可以推导出形心、半径和直径:
其中,ρ是簇内数据点到簇形心的平均距离,δ是簇内两两数据点的平均距离,这两个统计量都反映了簇内紧实度。
更加方便的是,可以直接基于聚类特征中的三项计算出不同簇间的距离度量。假设簇1,簇2的聚类特征分别为:,,簇1和簇2可合并成簇3.在此假设下,可定义下述5个距离以度量簇1和簇2之间的相异性:
上述距离中,称为形心欧基里得距离,称为形心曼哈顿距离,称为簇连通平均距离,称为全连通平均距离,称为散布恶化距离.
BIRCH
BIRCH是一种自顶向下的聚类算法,它利用了一个树结构来帮助我们快速的聚类,称之为聚类特征树(Clustering Feature Tree,简称CF Tree)。
CF树由根节点、枝节点和叶节点构成.CF树有两个参数:平衡因子、和空间阈值。所有节点的分支不得多于个,所有类簇的半径不得大于。
每个叶节点中都包含指针prev指向前一个叶节点和指针next指向后一个叶节点,方便后续查询叶节点.
CF树的生长由一根空树开始,是逐个插入聚类特征到CF树的过程,方法步骤如下:
步骤1: 创建根节点.此时CF树只有一个节点.
步骤2:把每一个数据当做一个类簇C,从root节点递归寻找距C最近的节点,直至找到最近的叶节点以及该叶节点下距离最近的类簇.然后检查一下项:
- 如果距离类簇质心的距离小于,合并入该类簇,步骤2结束,否则继续下面步骤.
- 如果最近的叶节点分支数小于,添加类簇C为该叶节点的类簇,步骤2结束,否则继续下面步骤.
- 此时需要分裂CF树,先将类簇C添加至距离最近的类簇,然后将该类簇分裂为两个聚类比较远的类簇,将这两个类簇添加到叶节点,递推检测父节点是否需要分裂。
步骤3:循环步骤2,直至所有数据均并入到CF树中.
不知道你是否注意到,所有的枝节点和叶节点都是分裂出来的.所以我们可以在分裂函数中用指针将叶节点串联起来,这样方便以后查询.
当以CF树构建完成之后,每个类簇的CF特征的线性和就是类簇的聚类中心.
编程实现:
https://www.kaggle.com/swimmingwhale/agnes
https://www.kaggle.com/swimmingwhale/birch
参考:
周志华<机器学习>
https://www.cnblogs.com/tiaozistudy/p/6129425.html
https://www.cnblogs.com/pinard/p/6179132.html