聚类算法(Clustering Algorithms)之层次聚类(Hierarchical Clustering)

在之前的系列中，大部分都是关于监督学习（除了PCA那一节），接下来的几篇主要分享一下关于非监督学习中的聚类算法（clustering algorithms）。

一、先了解一下聚类分析（clustering analysis）

Cluster analysis or clustering is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense) to each other than to those in other groups(clusters). it is a main task of exploratory analysis, and a common technique for statistical data analysis, used in many fields, including pattern recognition, image analysis, information retrieval, bioinformatics, data compression, computer graphics and machine learning. --WIKI

聚类分析又称群分析，它是研究（样品或指标）分类问题的一种统计方法，同时也是数据挖掘的一个重要算法。聚类（cluster)分析是由若干模式（pattern)组成的，通常，模式是一个度量(measurement)的向量，或者是多维空间中的一个点。聚类分析以相似性为基础，在一个聚类中的模式之间比不在同一聚类中的模式之间具有更多的相似性。-- 百度百科

聚类分析本身不是一种特定的算法，是用来解决一般任务的方法。它可以通过不同的算法来实现，这些算法不同之处在于它们对于集群结构的理解以及如何有效地找到这些集群。流行的集群概念包括，在一个集群的成员之间距离比较小，数据空间的密集区域，间隔或特定统计分布的组。因此，可以将聚类公式化为一个多目标优化问题。合适的聚类算法和参数的设置取决于所使用的数据集和对于聚类结果的用途。设置的参数例如要使用的距离函数，密度阈值或预计要聚类的数量。

Process of clustering(聚类分析的过程):

聚类分析的整个过程包括四个基本步骤：

A. Feature Selection or Extraction (特征选择和提取)

特征选择是确定最有效的原始特征子集用于聚类的过程。特征提取是将一个或多个输入特征转换为初始显著特征的过程。聚类过程高度依赖于此步骤。对特征的轻率剔除会增加内卷involution（involution: a function, transformation, or operator that is equal to its inverse），并可能导致额外的无关紧要的簇(clusters).

B. Clustering Algorithm Design or Selection (聚类算法的设计和选择）

不可能定理指出，“没有一个单一的聚类算法可以同时满足数据聚类的三个基本公理，即scale-invariance (尺度不变性)、consistency (一致性) 和 richness (丰富性)。因此，不可能为在不同的科学、社交、医学等其它领域中建立一个通用的聚类方法框架。从而，通过对应用领域的认知来精确剔除该算法是非常重要的。通常，所有算法都基于不同的输入参数，例如聚类的数量，优化/构造标准，终止条件，邻近度等。额外设计或者剔除这些不同的参数和标准，以此来作为这个步骤的前提条件。

C. Cluster Validation (聚类验证)

将不同的聚类算法用于同一数据集可以产生不同的结果。甚至是相同的算法，不同的参数也会产生不同的聚类结果。因此，必须验证或评估该聚类方法产生的结果。评估标准分为：

1）内部指标：内部指标是通过和它的数据进行比较来评估由聚类算法产生的聚类

2）外部指标：外部指标通过利用已知的知识（例如：类别标签）来评估聚类结果。

3）相对指标：顾名思义，该标准将结果与不同算法产生的其他结果进行比较。

D. Results Interpretation 结果解析

聚类过程的最后一步涉及聚类的展示。聚类的最终目的是为了让人们更了解原始数据，以便它们更有效地分析和解决难题。

因为“Cluster（集群）”的概念无法精确地被定义，所以聚类的算法种类有很多，比较常见的有：

Connectively - based clustering (hierarchical clustering)
基于连接的聚类（层次聚类）

Centroid-based clustering – k-means
基于中心的聚类 --例如：k-means

Distribution-based clustering – Gaussian mixture models
基于分布的聚类 --例如：高斯混合模型

Density-based clustering – kernel density estimation
基于密度的聚类 – 例如：核密度估计

Grid-based clustering 基于网格的集群

---

二、再了解一下 connectively-based clustering 基于连接的聚类算法

基于连接的聚类（也称为分层聚类），是基于这样的一个核心思想：即与附近的对象而不是较远的对象更为相关。该算法根据距离将对象连接起来形成簇（cluster)。可以通过连接各部分所需的最大距离来大致描述集群。在不同的距离，形成不同簇，这可以使用一个树状图来呈现。这也解析了“分层聚类”的