聚类分析中如何度量两个对象之间的相似性呢？一般有两种方法，一种是对所有对象作特征投影，另一种则是距离计算。前者主要从直观的图像上反应对象之间的相似度关系，而后者则是通过衡量对象之间的差异度来反应对象之间的相似度关系。

机器学习常见距离计算

机器学习常见距离

一般来说，有两种类型的层次聚类方法：

凝聚层次聚类：采用自底向上策略，首先将每个对象作为单独的一个原子簇，然后合并这些原子簇形成越来越大的簇，直到所有的对象都在一个簇中（层次的最上层），或者达到一个终止条件。绝大多数层次聚类方法属于这一类。
分裂层次聚类：采用自顶向下策略，首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一个簇，或者达到某个终止条件，例如达到了某个希望的簇的数目，或者两个最近的簇之间的距离超过了某个阈值.

举例:下图描述了一种凝聚层次聚类算法AGNES(Agglomerative Nesting)和一种分裂层次聚类算法DIANA（Divisive Analysis）对一个包含五个对象的数据集合{a,b,c,d,e}的处理过程:

初始，AGNES将每个对象自为一簇，然后这些簇根据某种准则逐步合并，直到所有的对象最终合并形成一个簇。

例如，如果簇C1中的一个对象和簇C2中的一个对象之间的距离是所有属于不同簇的对象间欧氏距离中最小的，则C1和C2合并。

在DIANA中，所有的对象用于形成一个初始簇。

根据某种原则（如，簇中最近的相邻对象的最大欧氏距离），将该簇分裂。簇的分裂过程反复进行，直到最终每个新簇只包含一个对象。

在凝聚或者分裂层次聚类方法中，用户可以定义希望得到的簇数目作为一个终止条件。

聚类中常用的距离计算公式

四个广泛采用的簇间距离度量方法如下，其中 $P_i ,P_j$ 是两个簇中的两个对象或点，mi是簇Ci的均值，而ni是簇Ci中对象的数目。

簇间最小距离： $d_{\min }\left(C_{i}, C_{j}\right)=\min _{p \in C_{i}, p^{\prime} \in C_{j}}\left|p-p^{\prime}\right|$

含义：簇类C1和C2的距离由该两个簇的最近样本决定。

使用该度量方法作为计算两个簇间的距离的算法又称单连接算法。

簇间最大距离： $d_{\max }\left(C_{i}, C_{j}\right)=\max _{p \in \mathbb{C}_{i}, p^{\prime} \in C_{j}}\left|p-p^{\prime}\right|$

含义：簇类C1和C2的距离由该两个簇的最远样本决定。

使用该度量方法作为计算两个簇间的距离的算法又称最近邻聚类算法。

簇间平均距离：

$\text { dist average }(C_1, C_2)=\frac{1}{|C_1| \bullet|C_2|} \sum_{P_{i} \in C_1, P_{j} \in C_{2}} \text { dist }\left(P_{i}, P_{j}\right)$

含义：簇类C1和C2的距离等于两个簇类所有样本对的距离平均。

使用该度量方法作为计算两个簇间的距离的算法又称最远邻聚类算法。

簇间样本间中心距离： $d_{c e n}\left(C_{i}, C_{j}\right)=\operatorname{dist}\left(\mu_{i}, \mu_{j}\right)$ ，其中 $\mu=\frac{1}{|C|} \sum_{1 \leq i \leq|C|} x_{i}$ 被称作簇C的中心点。

簇内距离度量方法：

簇内平均距离： $\operatorname{avg}(C)=\frac{2}{|C|(|C|-1)} \sum_{1 \leq i<j \leq|C|} \operatorname{dist}\left(x_{i}, x_{j}\right)$

簇内最小距离： $\operatorname{diam}(C)=\max _{1 \leq i<j \leq|C|} \operatorname{dist}\left(x_{i}, x_{j}\right)$

资源推送

举例：

给出在二维平面的5个点，每个点代表一个样本数据，记录x1，x2两个特征的计量值。

将五个样本都分别看成是一个簇，生成距离矩阵，最靠近的两个簇是3和4，因为他们具有最小的簇间距离D（3，4）=5.0。 n 第一步：合并簇3和4，得到新簇集合1，2，（34），5。
更新举例矩阵

$\begin{array}{l} \mathrm{D}(1,(34))=\min (\mathrm{D}(1,3),\mathrm{D}(1,4))=\min (20.6, 22.4)=20.6 \\ \mathrm{D}(2,(34))=\min (\mathrm{D}(2,3), \mathrm{D}(2,4))=\min (14.1, 11.2)=11.2 \\ \mathrm{D}(5,(34))=\min (\mathrm{D}(3,5), \mathrm{D}(4,5))=\min (25.0,25.5)=25.0 \end{array}$