本章的内容主要分为三部分，我会在第一部分对聚类分析展开介绍，主要针对基本理论，包括聚类分析的定义，类型，元素间距离的测量，评价聚类分析的结果以及启发式算法。第二部分是聚类分析的方法，这里主要介绍两种。第三部分是用python代码，对一个数据集进行聚类分析。
以下是大纲

1. Basics of Segmentation
   • Introductions
   • Cluster types
   • Distance measures
   • Evaluation criteria
   • Launch heuristics
2. Segmentation Methods
   • Partional clustering methods
   • Hierarchical clustering methods
3. python聚类分析的应用

1 Basics of Segmentation

1.1 Introductions

Segmentation和Cluster analysis说的实际上是同一个东西，即把不同的对象或实体按照某些标准分成不同的小组，这些小组也叫做群Cluster。因此Segmentation是过程，而cluster是结果。

先来思考为什么要做聚类分析：当我们拿到一组原始数据，我们希望能够快速了解这个数据中不同元素之间的关系，最好的办法就是把每个元素归为不同的类，并让属于同一个类别的元素之间差异尽可能小，同时属于不同类别的元素之间的差异尽可能大。

*注意：我们在做聚类的时候并不能事先知道共有几个类别以及每个类别中的元素，因此聚类分析跟前面讲到的逻辑回归（logistic regression，分类问题）有本质区别。在逻辑回归中，我们的数据集事先打好了标签，属于有监督学习。聚类分析属于机器学习领域的无监督学习，也就是说我们要通过代码让电脑自己判断数据集中，每个元素所属的类别

聚类分析的逻辑

1.2 Cluster types

存在多种不同的方式来实现聚类分析，换句话说，我们应采用多种方式接近数据集里面可能存在的类。不同聚类的种类会影响最终的分析结果，实际使用中可以尝试使用多种方式，并对比每种结果的好坏。

本节分为以下三种不同的Cluster types：

1. Disjunctive and exhaustive methods
2. Agglomerative and single-modal methods
3. Hierarchical and sharp methods

• Disjunctive and exhaustive methods
  Disjunctive 方法按照是否允许某个元素属于多个类别，分为disjoint和non-disjoint。Disjoint是说，每个元素只能被归类到一个类别，不同类别（看作集合）的交集是空集。Non-disjoint 正好相反，元素可以属于多个类，例如劳斯莱斯库里南，在non-disjoint的情况下，既可以是豪华车，也可以是suv。Exhaustive方法是指，在聚类分析结束后，是否允许存在某些元素不属于任何类别。同样有两种情况，exhaustive说的是每个元素都至少被分到一个类中（这里包含了disjoint和non-disjoint的情况），也就是不存在未被分类的元素。non-exhaustive则允许未分类的元素的存在。
  

  
  
  
  *注意：在上图的例子中，分别展示了disjoint和non-disjoint的情形，需要注意的是，每个类别中不能包含子类！

• Agglomerative and single-modal methods

  • agglomerative是从集合中的单个元素开始，逐步关联其他元素，从而成为一个类。相当于从基层做起，是一种从下到上的过程。 divisive方法正好相反，从上到下逐步将一个大的集合分解成小的群体

  • single-modal是将对象或者特征分类，dual-modal则是同时将对象和特征进行分类
    

• Hierarchical and sharp methods

  • hierarchical方法的特点是，位于较高聚合层次的聚类完全包含了位于较低聚合层次的相应聚类。non-hierarchical方法则是基于一种 优化过程，通过交换不同聚类中的元素逐步提升分类的质量。
  • sharp方法是和fuzzy方法相对的。sharp方法下，无论一个对象被分到哪个类或哪几个类，这个对象都是非常明确地属于这个类或这些类。也就是说此时的分类特别明确。而fuzzy方法下，一个对象并不能明确地被归属到一个类中，通常我们会采用比重（share values）来决定一个对象属于某个类的程度。
    
    
    
    hierarchy
    
    *hierarchy：a union of disjoint segmentations, An overlap of classes is excluded
    
    quasi-hierarchy
    
    *quasi-hierarchy: is a union of non-disjoint segmentations An overlap of classes is not excluded.

1.3 Distance measures

在聚类分析中，我们试图按照个体之间的相似性来判断不同个体是否属于同一类。那么如何量化这个相似性呢？我们想要的是一个相似性指标，指标越大，说明两个个体越相似。但是这很难实现，因为我们接触到的数据通常是多维的，每个个体都具有多种不同的属性，对这些个体进行聚类分析实际上就是根据多种不同的属性进行判断。

所以我们在处理数据的时候会用距离来衡量不同个体之间的不相似性dissimilarity

距离指的是样本元素之间相似性的差异，编程过程中也会将这种相似性的度量转换成多维坐标系，然后算出不同个体之间的距离。例如著名的鸢尾花数据集，我们会根据样本的花萼长度，花瓣颜色等不同的维度来判断某个个体具体属于哪一种鸢尾花

常用的距离度量有：

• euclidean distance: 欧式距离，也就是空间中两点之间的距离，初中数学学的勾股定理就是欧氏距离

  
  
  Euclidean distance

• city block distance：即城市街区距离，在城市中，我们通常不会参考欧氏距离，两点之间的距离要按照实际道路行驶的距离

  
  
  city block distance

• chebyshev distance： 车比雪夫距离，是向量空间中的一种度量，将空间坐标中两个点的距离定义为他们各自坐标数值差的绝对值的最大值。

  
  
  chebychev distance

用距离来度量相似性会导致以下问题：
如果两个特征k1和k2是存在高度相关性的，那么这两个特征为我们的聚类分析提供了有关相似性的大致相同的信息。也就是说，我们两次采用同样的信息来做聚类分析。当这两个特征拥有不同的散布特征（例如方差差距很大），那么方差大（更分散）的那个特征对聚类分析的影响更大。

1.4 Evaluation criteria

现在来评估聚类分析的结果。假设有两个不同的分类方案，那么我们应该怎样评估哪个方案更适合我们的样本？
以下是几条评判标准：

• 同一类中元素的差异，intra-class dissimilarity， heterogeneity indices
• 不同类之间的差别，interclass difference，dissimilarity indices
• quality index

1. Examples of heterogeneity indices：

• 评估两个对象之间的最大距离（同一个聚类内部）：

  
  

• 评估同一个类内部，不同对象之间加权距离和

  
  

2. Examples of dissimilarity indices：

• single linkage：Evaluation of the minimum distances of two objects from the different classes

  
  
  single linkage

• complete linkage: Evaluation of the maximum distances of two objects from the classes

  
  
  complete linkage

• Evaluation of the (weighted) sum of all distances between objects:

  
  

3. Examples of quality indices:

• Evaluation of the classification on the basis of heterogeneity

  
  
  
  

  c = 1 --> Sum of heterogeneity indices
  c = |K| --> Mean class heterogeneity

or:

• Evaluation of the classification on the basis of dissimilarity

  
  

• Evaluation of the classification on the basis of heterogeneity and on the basis of dissimilarity

  
  

quality index 的缺陷：
通常情况下，quality index会随着类别数量的增加而降低
这与我们的目标有冲突：
我们在做聚类分析时，希望类别的数量尽可能少，同时quality index的值也是尽可能小

为了克服这一缺陷，我们引入了elbow criterion：
借助这一原则，我们可以选择“最优”的类别数量s，而此时的quality index是b，这两个值应该满足下面的条件：
减少类别数量s*会导致b的剧烈提高，增加类别数量只能引起b非常轻微的增加
*即：找到一个b斜率的转折点

Elbow diagram

1.5 Launch Heuristics

也属于分类方法（segmentation methods），具有以下特点：

• 使用简单的算法
• 并不保证输出最优解
• 不需要很高的算力
• 基于一个距离矩阵（distance matrix)

启发式算法将一组对象划分为分解部分（decomposition）或重叠部分（overlap）：
** Sequence of heuristics for a decomposition**

步骤和应用：

首先选择s个不同的类别中心点（class center，cc），然后把剩余的元素分配给最近的类别中心点（cc）

使用这个启发式算法并不是最终的目的，而只是生成一个初始解，然后通过别的算法进行迭代优化（见规范性分析）。如果数据量非常大，那么进行聚类分析所消耗的算力也会非常惊人，启发式算法可以很好地处理这种问题。

算法的详细步骤

2 Segmentation Methods

这一节展开讲述聚类的两种方式，分别是基于划分的聚类Partional clustering methods和基于层次的聚类Hierarchical clustering methods。我也会在结尾时对基于密度的聚类进行简单描述，用意是引入一种其他的聚类方式。

2.1 Partional clustering methods

基于划分的聚类是一种最简单和常用的聚类方式，它将一个对象集合N划分成s个不同的类别，这些类别彼此之间是互斥的，每个对象属于且仅属于一个类别。目标函数是最小化计算出的聚类（segmentation or partition）K的quality index b(K)。

基于划分的聚类

互换原则

1. 选择初始划分K0，并计算b(K0)
2. 搜索一个对象，把这个对象换到另外一个分类后，b的值会降低
3. 把上一步找到的对象放入这个降低b的聚类中，
4. 重复2，3，直到不再存在其他这样的交换
   经过这4个步骤我们就得到了一个局部最优解，local optimum
   
   The exchange principle
   
   *注意：这个过程不会一直进行下去，我们需要设置一个停止条件，也就是最大迭代次数，当计数器达到这个最大迭代次数后，程序运行会停止。输出的结果叫做局部最优或者本地最优，要想达到全局最优，需要同时交换多个对象。本地最优解的好坏取决于我们在第一步设置的初始划分（start partition）

接下来介绍两种优化算法：k-means 和k-medoids。这两个算法是对启发式算法得出的本地最优解的优化，被称作Error minimization algorithm

a) k-means
k-均值是把数据划分成k个类别，我们用这些类别的中心或均值来表示他们。我们需要计算样本点和类别中心（均值）之间的距离，与中心距离近的样本点划分为同一个类别。K-均值通过样本之间的距离来衡量他们之间的相似程度，两个样本点距离越远，则相似性越低，越近，则相似性越高。

• 算法过程：
  1. 算出k个初始中心点（中心点不一定是样本点，可以理解为物理中的重心，重心不一定落在物体上），每个中心点表示一个类别（随机选或通过启发式算法）
  2. 计算剩余的每个样本点到k个中心点的距离（欧式），并将这些样本点归入距离最近的中心点代表的类别，
  3. 根据2中的划分情况，重新计算各个类别的中心点的位置，然后迭代计算各个样本点到各类别中心的距离，对所欲样本点重新进行划分

  4. 重复2和3，直到中心点不再发生变化或者达到了最大迭代次数

     
     
     2-dimensional， k=3

b) k-medoids or PAM(partition around medoids
PAM 算法是一种围绕中心点划分的算法，PAM算法中的中心点是一个真实的样本点，而不是通过距离计算出来的中心。PAM和k均值一样，使用贪婪策略来处理聚类流程。

• 算法流程：
  1. 随机选出k个对象（样本点）作为中心，
  2. 把剩余的每个对象分配给距离最近的中心
  3. 随机选择一个非中心对象，替换中心对象，
  4. 计算替换后的总损失（quality index）
  5. 如果计算出的总损失降低，则交换中心点和非中心点，

  6. 直到达到收敛条件

     
     
     2-dimensional， k=2

2.2 Hierarchical clustering methods

本节介绍基于层次的聚类，其核心思想是按照一个对象集N的层次，把对象划分到不同的类别，从而形成一个树形的聚类结构。

层次聚类算法可以揭示数据的分层结构，在树形结构的不同层次上进行划分，可以得到不同粒度的聚类结果。

基于层次的聚类有两种实现方式，分别是agglomerative clustering和diversive clustering。这两种方式在前面提到过，这里展开说说：

• agglomerative clustering是自底向上的聚合聚类，在初始状态下将每一个单独的对象（样本点）看作一个类别，这样我们最初拥有N个类别，然后根据一定的算法规则，逐步将不同的类别进行合并（merge），直到达到我们想要的聚类结构。

  
  
  自底向上聚合聚类
  
  

  • Starting point are n = |N| one-element classes.
  • Successive transition to coarser decompositions
  • Termination as soon as given criterion is fulfilled
  • Low computation times, good practical suitability

• diversive clustering自顶向下分裂聚类：初始状态下，将所有的对象组成的集合看作一个类别，也就是最初所有对象都属于同一个类。然后将这个大类逐步分解成子类别，这些子类别同样也能再被继续分解。整个过程直到达到我们想要的聚类结果为止。

  
  
  自顶向下分裂聚类
  
  

  • Starting point is the class of all objects.
  • Successive transition to finer decompositions
  • Termination as soon as given criterion is fulfilled

相似性的度量 Similarity measures

相似性度量是基于对跨类别差异的重新计算，based on the different recalculation of the interclass differences。
这里介绍三种相似性度量，每种度量方式都有其优劣，在实际操作中注意结合优缺点进行选择。

1. Single linkage：计算两个类别中，距离最短的两个点的距离就是single linkage，如下图：

   
   
   single linkage

2. Complete linkage：计算两个类别中，距离最远的两个元素的距离

   
   
   Complete linkage

3. average linkage：计算两个类别所有元素之间距离的平均值

   
   
   average linkage

相似性度量--举例

1. SL

   
   
   SL

初始状态下，我们一共有5个类别。
观察距离矩阵，在所有的距离中，从1到5 的距离是最短的，因此有理由相信1和5非常相似。我们首先把1和5这两个最相似的点归到同一类中，然后继续在距离矩阵中剩余的元素里面找最小值，不难发现是1到4的距离，为2.08，因此我们把4号元素归到1和5所处的类中（虽然4到5的距离2.63比1到3 的距离2.91更小，但是我们已经把1，4，5归类到一个类别，因此2.63不需要考虑）。然后按照同样的逻辑，依次选出最小的d，我们构造聚类时，所采用的顺序就是dendrogram中每个节点出现的顺序（也就是聚类的顺序）

2. CL

CL

这里需要注意，我们同样需要首先把1和5聚合到一个类别，这样我们才能得到公式里面的K和L。接下来把4聚合到现有的类别中，按照公式，从4出发，到当前聚类中2个元素有两个不同的距离，分别是d4,5 = 2.63和d4,1 = 2.08。按照CL的原则，我们选择2.63。同理，当我们聚合3的时候，也需要比较从3出发到当前聚类中每个元素的距离，分别是d3,1= 2.91, d3,4 = 4.33, d3,5 = 4.03。显然应该选择4.33

3. AL

AL

这里同样是要先分组形成K和L，也就是把1和5归为一类。然后观察4到1和5的距离，计算 (d4,5 + d4,1) / 2 = 2.355。以此类推

对dendrogram的理解和说明

如果quality index的值发生较大的变化，那么我们可以得出关于这种情况下，特定聚类数量的结论

类似的对象会更早被聚合在一起，不相似的对象会晚一些归入某个类别。outliers可以在最后阶段被归类到一个很大的聚类集合

结合我们上面的三个例子，我们可以判断：

• 符合stable，因为三种不同的方法都产生了同样的聚类结果
• 不符合intensive，因为我们一直都只有一个类别中的元素数量在增长，并没有看到多个拥有差不多数量元素的类别
• 符合weak，因为每次都是逐一加入新的元素

评估层次聚类 Assessment of a hierarcy

评估的目的是，判定不同的层次聚类的结果能否生成最优的距离矩阵D。首先要做的是从系统树图（dendrogram）中生成一个超度量的距离矩阵 D*，这个矩阵的元素计算公式如下：

超度量D*

然后再用D*矩阵和D矩阵进行比较。

D*矩阵

上图中，我们首先需要从D矩阵得到系统树图，也就是每个对象在什么时候被加入到聚类中（AL中计算了平均数），然后使用系统树图计算不相似性，再把这个数字写到D星 矩阵中。例如4号元素是在2.36处被加入到聚类中，此时聚类中只有1和5，那么我们来把2.36写入到D星矩阵中。

The Shepard-Diagram

The simplest way to evaluate the different distance matrices D and D* is the so-called Shepard diagram, in which the true distances d and the calculated distances d* are compared in a coordinate system.

Shepard

Variance-Accounted-For-Criteria

The VAF criterion can be calculated to assess the loss of information in procedures that explicitly use distances:

VAF

Cophenetic correlation coefficient

To assesses the existence of a linear relationship between the true distances d and the calculated distances d* according to:

CCC

2.3 Density based clustering methods

这一节简单介绍基于密度的聚类。基于划分的聚类和基于层次的聚类方法在聚类过程中，根据样本点之间的距离进行聚类的划分，因此只能挖掘球形类别，但是在现实的数据中，我们通常会遇到各种形状的分布，此时上述两种方法就不再适用了。

基于密度的聚类利用了密度思想，将样本中的高密度区域（即样本点分布稠密的区域）划分为类别，并将这些类别看作是样本空间中被稀疏区域（噪声）分隔开的稠密区。