logo

层次聚类

层次聚类试图在不同层次对数据集进行划分,从而形成树形的聚类结构.数据集的划分可采用"自底向上"的聚合策略,也可采用"自顶向下"的拆分策略.

AGNES

AGNES是一种自底向上的聚类算法.它先将数据集中的每个样本看做一个初始聚类簇,然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并,重复该过程,直到剩余聚类簇个数达到预期个数.

image

两个聚类簇直接的距离有三种计算方法:

image

AGNES的聚类步骤如下:
步骤1：初始化每一个数据为一个类簇.
步骤2：找到距离最大的两个类簇,将其合并.
步骤3：重复步骤2,知道剩余类簇个数k等于设定值.

聚类特征

BIRCH使用聚类特征概括描述各簇的信息，其定义如下：
\vec {CF} = \langle N, \vec {\Sigma}_l, {\Sigma}_s \rangle
其中N为该簇中数据点的数量，矢量
\begin{equation} \vec {\Sigma}_l = \sum_{n=1}^N \vec x _n = \left(\sum_{n=1}^N x_{n1}, \sum_{n=1}^N x_{n2}, ..., \sum_{n=1}^N x_{nD} \right)^T \end{equation}

为各数据点的线性求和，标量
\begin{equation} {\Sigma}_s = \sum_{n=1}^N \vec x _n^2 = \sum_{n=1}^N \vec x _n^T \vec x_n = \sum_{n=1}^N \sum_{i=1}^D x_{ni}^2 \end{equation}

为各数据点的平方和.

CF有一个很好的性质，就是满足线性关系.设 \vec {CF}_1 = \langle N_1, \vec {\Sigma}_{l1}, {\Sigma}_{s1} \rangle 和 \vec {CF}_2 = \langle N_2, \vec {\Sigma}_{l2}, {\Sigma}_{s2} \rangle 分别表示两个不相交的簇的聚类特征，如果将这两个簇合并成一个大簇，则大簇的聚类特征为
\begin{equation} \vec {CF}_1 + \vec {CF}_2 = \langle N_1+N_2, \vec {\Sigma}_{l1} + \vec {\Sigma}_{l2}, {\Sigma}_{s1} + {\Sigma}_{s2} \rangle \end{equation}

假设簇1有三个数据点(2,5)、(3,2)和(4,3)，簇1的聚类特征是

\begin{split} \vec{CF}_1 & = \langle 3, (2+3+4, 5+2+3), (2^2+5^2)+(3^2+2^2)+(4^2+3^2) \rangle \\ & = \langle 3, (9,10), 67 \rangle \end{split}

聚类特征本质上是给定簇的统计汇总，可以有效地对数据进行压缩，而且基于聚类特征可以很容易地推导出簇的许多统计量和距离度量。假设给定簇中有N个D维的数据点， \{\vec x_n : n=1,2,...,N\} ，则在簇的统计量方面可以推导出形心 \bar {\vec x} 、半径 \rho 和直径 \delta ：

\begin{equation} \bar {\vec x} = \frac 1N \sum_{n = 1} ^N \vec x_n = \frac {\vec {\Sigma}_l}{N} \end{equation}

\begin{equation} \rho = \sqrt{\frac{\sum_{n=1}^N (\vec x_n - \bar {\vec x})^2}{N}} = \sqrt{\frac{N \Sigma_s - \vec{\Sigma}_l^2}{N^2}} \end{equation}

\begin{equation} \delta = \sqrt{\frac{\sum_{m=1}^N \sum_{n=1}^N (\vec x_m - \vec x_n)^2}{N(N-1)}} = \sqrt{\frac{2N {\Sigma}_s - 2 \vec {\Sigma}_l^2}{N(N-1)}} \end{equation}

其中，ρ是簇内数据点到簇形心的平均距离，δ是簇内两两数据点的平均距离，这两个统计量都反映了簇内紧实度。

更加方便的是，可以直接基于聚类特征中的三项计算出不同簇间的距离度量。假设簇1,簇2的聚类特征分别为: \vec{CF}_1 = \langle N_1, \vec {\Sigma}_{l1}, \Sigma_{s1} \rangle , \vec{CF}_2 = \langle N_2, \vec {\Sigma}_{l2}, \Sigma_{s2} \rangle ,簇1和簇2可合并成簇3.在此假设下，可定义下述5个距离以度量簇1和簇2之间的相异性：
\begin{equation} d_0 = \sqrt{(\bar{\vec x}_1 - \bar{\vec x}_2)^2} = \sqrt {\left ( \frac{\vec{\Sigma}_{l1}}{N_1} - \frac{\vec{\Sigma}_{l2}}{N_2} \right )^2} \end{equation}
\begin{equation} d_1 = | \bar{\vec x}_1 - \bar{\vec x}_2 | = \left | \frac{\vec{\Sigma}_{l1}}{N_1} - \frac{\vec{\Sigma}_{l2}}{N_2} \right | \end{equation}
\begin{equation} d_2 = \sqrt{\frac{\sum_{m=1}^{N_1} \sum_{n=1}^{N_2} (\vec x_{1m} - \vec x_{2n})^2}{N_1 N_2}} = \sqrt{\frac{\Sigma_{s1}}{N_1} - 2\frac{\vec{\Sigma}_{l1}^T}{N_1} \frac{\vec{\Sigma}_{l2}}{N_2} + \frac{\Sigma_{s2}}{N_2}} \end{equation}

\begin{equation} \begin{split} d_3 & = \sqrt{\frac{\sum_{m=1}^{N_1 + N_2} \sum_{n=1}^{N_1 + N_2} (\vec{x}_{3m} - \vec{x}_{3n})^2}{(N_1 + N_2)(N_1 + N_2 - 1)}} \\ & = \sqrt{\frac{2(N_1 + N_2)(\Sigma_{s1} + \Sigma_{s2}) - 2(\vec{\Sigma}_{l1} + \vec{\Sigma}_{l2})^2}{(N_1 + N_2)(N_1 + N_2 - 1)}} \end{split} \end{equation}

\begin{equation} \begin{split} d_4 = & \rho_3 - \rho_1 - \rho_2 \\ = & \sqrt{\frac{(N_1 + N_2)(\Sigma_{s1}+\Sigma_{s_2}) - (\vec{\Sigma}_{l1} + \vec{\Sigma}_{l2})^2}{(N_1+N_2)^2}} - \\ & \sqrt{\frac{N_1 \Sigma_{s1} - \vec{\Sigma}_{l1}^2}{N_1^2}} - \sqrt{\frac{N_2 \Sigma_{s2} - \vec{\Sigma}_{l2}^2}{N_2^2}} \end{split} \end{equation}

上述距离中， d_0 称为形心欧基里得距离， d_1 称为形心曼哈顿距离， d_2 称为簇连通平均距离， d_3 称为全连通平均距离， d_4 称为散布恶化距离.

BIRCH

BIRCH是一种自顶向下的聚类算法,它利用了一个树结构来帮助我们快速的聚类，称之为聚类特征树(Clustering Feature Tree，简称CF Tree)。

CF树由根节点、枝节点和叶节点构成.CF树有两个参数：平衡因子 \beta 、和空间阈值 \tau 。所有节点的分支不得多于 \beta 个,所有类簇的半径不得大于 \tau 。

每个叶节点中都包含指针prev指向前一个叶节点和指针next指向后一个叶节点,方便后续查询叶节点.

image

CF树的生长由一根空树开始，是逐个插入聚类特征到CF树的过程，方法步骤如下：

步骤1: 创建根节点.此时CF树只有一个节点.
步骤2：把每一个数据当做一个类簇C,从root节点递归寻找距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

posted @ 2018-09-28 18:39:13
评论加载中...
发表评论