https://www.toutiao.com/a6641489713536434695/

2019-01-01 19:32:04

层次聚类算法将相似的对象分组到称为聚类的组中。层次聚类算法有两种:

• 凝聚（Agglomerative ）-自下而上的方法。从许多小聚类开始，然后将它们合并到一起，创建更大的聚类。
• 分裂 （Divisive ）- 自上而下的方法。从单个聚类开始，而不是将其拆分为更小的聚类。

层次聚类的一些优缺点

优点

• 不假设特定数量的聚类（即k均值）
• 可能对应于有意义的层次关系

缺点

• 一旦决定组合两个聚类，它就无法撤消
• 遇到大机器学习数据集时太慢，O（2log（））

它时如何运作的

1.使每个数据点成为一个聚类

2.取两个最接近的聚类并使它们成为一个聚类

3.重复步骤2，直到只有一个聚类

树形图

我们可以使用树形图来显示分组的历史，并找出最佳的聚类数。

• 确定不与任何其他聚类相交的最大垂直距离
• 在两个末端画一条水平线
• 最佳聚类数等于通过水平线的垂直线数

例如，在下面的例子中，没有的最佳选择。集群将是4。

连接标准（Linkage Criteria）

与梯度下降类似，您可以调整某些参数以获得截然不同的结果。

连接标准指的是如何计算聚类之间的距离

Single Linkage

两个聚类之间的距离是每个聚类中两点之间的最短距离

Complete Linkage

两个聚类之间的距离是每个聚类中两点之间的最长距离

Average Linkage

簇之间的距离是一个聚类中每个点与另一个聚类中每个点之间的平均距离

Ward Linkage

聚类之间的距离是所有聚类内的平方差的总和

距离度量

用于计算数据点之间距离的方法将影响最终结果。

欧几里德距离

两点之间的最短距离。例如，如果x =（a，b）和y =（c，d），则x和y之间的欧几里德距离为√（（a-c）²+（b-d）²）

曼哈顿距离

想象一下，你在一个大城市的市中心，你想要从A点到达B点。你将无法跨越建筑物，而是你必须沿着各条街道行走。例如，如果x =（a，b）和y =（c，d），则x和y之间的曼哈顿距离是| a-c | + | b-d |。

python中的示例

让我们看看如何使用层次凝聚聚类来标记机器学习数据的具体示例。

import pandas as pd
import numpy as np
from matplotlib import pyplot as plt
from sklearn.cluster import AgglomerativeClustering
import scipy.cluster.hierarchy as sch

在本教程中，我们使用包含客户列表的csv文件及其gender, age, annual income 和 spending score。机器学习数据库的下载地址：http://www.kankanyun.com/data/Mall_Customers.csv

为了在以后的图表上显示我们的数据，我们只能采用两个变量（annual income 和spending score）。

dataset = pd.read_csv('./data.csv')
X = dataset.iloc[:, [3, 4]].values

观察树状图，与任何聚类不相交的最高垂直距离是中间的绿色。假设5条垂直线超过阈值，则最佳聚类数为5。

dendrogram = sch.dendrogram(sch.linkage(X, method='ward'))

我们利用欧几里得距离来创建AgglomerativeClustering的实例，其中该欧几里得距离是指点之间的距离和用于计算聚类的接近度的距离。

model = AgglomerativeClustering(n_clusters=5, affinity='euclidean', linkage='ward')
model.fit(X)
labels = model.labels_

该labels_属性返回一个整数数组，其中值对应于不同的类。

我们可以使用简写表示法将属于某个类的所有样本显示为特定颜色。

plt.scatter(X[labels==0, 0], X[labels==0, 1], s=50, marker='o', color='red')
plt.scatter(X[labels==1, 0], X[labels==1, 1], s=50, marker='o', color='blue')
plt.scatter(X[labels==2, 0], X[labels==2, 1], s=50, marker='o', color='green')
plt.scatter(X[labels==3, 0], X[labels==3, 1], s=50, marker='o', color='purple')
plt.scatter(X[labels==4, 0], X[labels==4, 1], s=50, marker='o', color='orange')
plt.show()

old ， but useful .

两种产生层次聚类的基本方法：

• 凝聚的： 从点作为个体簇开始，每一步合并两个最近的簇，
  需要定义簇的邻近性概念（开始每个点都是一个簇，然后不断合并减少簇的数量）。

• 分裂的； 从包含所有点的某个簇开始，每一步分裂一个簇，直到仅剩下单点簇。
  在这种情况下，我们需要确定每一步分裂哪个簇，以及如何分裂？

   下面将先介绍凝聚层次聚类技术。
  

2. 层次聚类

层次聚类常常使用称作树状图（dendrogram）的类似树的图显示，该图显示簇-子簇联系和簇合并（凝聚）或分裂的次序。度域二维点的集合，层次聚类也可以使用嵌套簇图（nested cluster diagram）表示，

2.1 基本凝聚层次聚类算法

许多凝聚层次聚类技术都是这个方法的变种，从个体点作为簇开始，相继合并两个最接近的簇，直到剩下一个簇。

2.1.1 如何定义簇之间的邻近性——簇之间满足什么条件才可以认为是邻近的？

簇的邻近性通常用特定的簇类型定义，如许多凝聚层次聚类技术都源于簇的基于图的观点。

• MIN / 单链（single link） 定义簇的邻近度为不同簇的两个最近的点之间的邻近度，（或者使用图的术语：不同的结点子集中两个结点之间的最短边）
• MAX / 全链（complete link） 取不同簇中两个最远的点之间的邻近度作为簇的邻近度（或者使用图的术语： 不同的结点子集中两个结点之间的最长边。）
• 组平均（group average）技术 它定义簇邻近度为取自不同簇的所有点对邻近度的平均值（平均边长）。
• 矩心之间的距离：
• 由目标函数驱动的其他方法，如 Ward 的方法使用平方误差

2.1.2 时间和空间复杂性

基本凝聚层次聚类算法使用邻近度矩阵，这需要存储 m ² / 2 个邻近度（假定邻近度矩阵是对称的），其中 m 是数据点的个数。 记录簇所需要的空间正比于簇的个数为 m-1，不包括单点簇，因此总的空间复杂度为 O （m²）。总的时间复杂度为 O(m²log m)。
不够详细，实践中总结

凝聚层次聚类过程

1. 从单个点的簇和邻近矩阵开始：
2. 在一些合并步骤后，我们有一些聚类：
3. 我们想合并两个最近的聚类（C2 和 C5）并更新邻近矩阵
   

聚类相似性——MIN 或单链

两个簇的相似性基于不同簇中的两个最相似（最接近）点。

• 由一对点确定，即由邻近图中的一个链接确定。如果从所有点作为单点簇开始，每次在点之间加上一条链，最短的链先加，则这些链将点合并成簇。
• 单链 擅长处理非椭圆形状的簇，但对噪声和离群点很敏感（可以从下面的演示过程看出）

1. 下图中显示了 6 个点的坐标以及他们之间的欧几里得距离矩阵。树状图中两个簇合并出的高度反映了两个簇的距离。如 点 3 和 点 6 的距离是 0.11，这就是他们在树状图里合并处的高度。
   
2. 一开始坐标中的 6 个点都作为单点簇。
   
3. 由于点 3 和 点 6 的距离最小，所以先合并点 3 和 点 6 作为一个簇，现在有 5 个簇。

4. 之后 点 2 和 点 5 合并成一个簇。
   

5. 之前的新簇（点 3 和 点 6 合并）与刚才形成的簇（点 2 和 点 5 合并） 继续合并成新簇。

6.最终形成如图的一个簇。

聚类相似性——全链或MAX或团

• 对于层次聚类的全链或 MAX版本，两个簇的邻近度定义为两个不同簇中任意两个之间的最长距离（最小相似度）。
• 如果所有点作为单点簇开始，每次在点之间加上一条链，最短的链先加，则一组点直到其中所有的点都完全被连接（即形成团）才形成一个簇。挑选两簇（两簇中之间最长的链与其他簇的最长相比链最短）
• 完全连接对噪声和离群点不太敏感，但是它可能使大的簇破裂，并且偏好球形。
  
  
  

聚类相似性——组平均

对于层次聚类的组平均版本，两个簇的邻近度定义为不同簇的所有点对邻近度的平均值。这是一种界于单链和全链之间的折中办法。对于组平均，簇 C _i 和 C_j 的邻近度 proximity(C_i，C_j）由下式定义：


m_i ，m_j 为簇的点个数，分子为两个簇点与点的链距离之和。

聚类相似性分析——Ward方法和质心方法

对于 Ward 方法，两个簇的邻近度定义为两个簇合并时导致的平方误差的增量。，这样一来，该方法使用的目标函数和K均值相同，好像这一特点让Ward 方法不同与其他层次聚类技术，但是可以从数学上证明，当两个点之间的邻近度取它们之间距离的平方是， Ward 方法与组平均非常相似。

质心方法通过计算簇质心之间的距离来计算两个簇之间的邻近度。看起来和 K 均值类似，但是只有 Ward 方法才真正与它类似。

质心方法还具有一种我们讨论过的其他层次聚类技术所不具备的特性（常被认为是坏的）：倒置（inversion）的可能性。合并的两个簇可能比前一步合并的簇对更相似。对于其他方法，被合并的簇之间的距离随层次聚类进展单调地增加（或者，在最坏的情况下不增加）。

簇邻近度的 Lance-Williams公式

本节讨论的任何簇邻近度都可以看做簇 Q 和 R 之间邻近度的不同参数（Lance-Williams公式）的一种选择，其中 R 是合并簇 A 和 簇 B 形成的。

任何可以使用 Lance-Williams 公式表示的层次聚类技术都不需要保留原来的数据点。

层次聚类——时间和空间要求

• O(n)空间复杂度，因为它使用邻近矩阵。n 是点数。
• O(n³)在多数情况下的时间复杂度，有 n 个步骤，并且每个步骤，必须更新和搜索大小 n² ，邻近矩阵。
• 对于一些方法，时间复杂度可以减少到 O(n²log n)。

层次聚类的主要问题

1. 一旦决定组合两个集群，无法退回。
2. 没有目标函数被直接最小化。
   凝聚层次聚类不能被视为全局优化目标函数，凝聚层次聚类技术使用各种标准，在每一步局部地确定哪些簇应当合并（或分裂），这种方法产生的聚类算法避开了解决困难的组合优化问题，这样的方法没有局部极小问题或很难选择初始点的问题。
3. 不同的方案具有以下一个或多个问题：

• 对噪声和异常值的敏感性
• 难以处理不同大小的簇和凸形
• 分离大集群

就计算量和存储需求而言，凝聚层次算法是昂贵的，所有合并都是最终的，对于噪声、高维数据，这也可能造成问题，先使用其他技术进行部分聚类，这两个问题都可以在某种程度上解决。

层次聚类

层次聚类(Hierarchical Clustering)是聚类算法的一种，通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中，不同类别的原始数据点是树的最低层，树的顶层是一个聚类的根节点。创建聚类树有自下而上合并和自上而下分裂两种方法。

作为一家公司的人力资源部经理，你可以把所有的雇员组织成较大的簇，如主管、经理和职员；然后你可以进一步划分为较小的簇，例如，职员簇可以进一步划分为子簇：高级职员，一般职员和实习人员。所有的这些簇形成了层次结构，可以很容易地对各层次上的数据进行汇总或者特征化。

如何划分才是合适的呢？

直观来看，上图中展示的数据划分为2个簇或4个簇都是合理的，甚至，如果上面每一个圈的内部包含的是大量数据形成的数据集，那么也许分成16个簇才是所需要的。

论数据集应该聚类成多少个簇，通常是在讨论我们在什么尺度上关注这个数据集。层次聚类算法相比划分聚类算法的优点之一是可以在不同的尺度上（层次）展示数据集的聚类情况。

基于层次的聚类算法（Hierarchical Clustering）可以是凝聚的（Agglomerative）或者分裂的（Divisive），取决于层次的划分是“自底向上”还是“自顶向下”。 

自底向上的合并算法

层次聚类的合并算法通过计算两类数据点间的相似性，对所有数据点中最为相似的两个数据点进行组合，并反复迭代这一过程。简单的说层次聚类的合并算法是通过计算每一个类别的数据点与所有数据点之间的距离来确定它们之间的相似性，距离越小，相似度越高。并将距离最近的两个数据点或类别进行组合，生成聚类树。

相似度的计算

层次聚类使用欧式距离来计算不同类别数据点间的距离（相似度）。

实例：数据点如下

                                              

 分别计算欧式距离值（矩阵）

 将数据点B与数据点C进行组合后，重新计算各类别数据点间的距离矩阵。数据点间的距离计算方式与之前的方法一样。这里需要说明的是组合数据点(B,C)与其他数据点间的计算方法。当我们计算(B,C)到A的距离时，需要分别计算B到A和C到A的距离均值。

经过计算数据点D到数据点E的距离在所有的距离值中最小，为1.20。这表示在当前的所有数据点中（包含组合数据点），D和E的相似度最高。因此我们将数据点D和数据点E进行组合。并再次计算其他数据点间的距离。

后面的工作就是不断的重复计算数据点与数据点，数据点与组合数据点间的距离。这个步骤应该由程序来完成。这里由于数据量较小，我们手工计算并列出每一步的距离计算和数据点组合的结果。

两个组合数据点间的距离

计算两个组合数据点间距离的方法有三种，分别为Single Linkage，Complete Linkage和Average Linkage。在开始计算之前，我们先来介绍下这三种计算方法以及各自的优缺点。

• Single Linkage：方法是将两个组合数据点中距离最近的两个数据点间的距离作为这两个组合数据点的距离。这种方法容易受到极端值的影响。两个很相似的组合数据点可能由于其中的某个极端的数据点距离较近而组合在一起。

• Complete Linkage：Complete Linkage的计算方法与Single Linkage相反，将两个组合数据点中距离最远的两个数据点间的距离作为这两个组合数据点的距离。Complete Linkage的问题也与Single Linkage相反，两个不相似的组合数据点可能由于其中的极端值距离较远而无法组合在一起。

• Average Linkage：Average Linkage的计算方法是计算两个组合数据点中的每个数据点与其他所有数据点的距离。将所有距离的均值作为两个组合数据点间的距离。这种方法计算量比较大，但结果比前两种方法更合理。

我们使用Average Linkage计算组合数据点间的距离。下面是计算组合数据点(A,F)到(B,C)的距离，这里分别计算了(A,F)和(B,C)两两间距离的均值。

 树状图

 层次聚类python

import pandas as pd

seeds_df = pd.read_csv('./datasets/seeds-less-rows.csv')
seeds_df.head()

seeds_df.grain_variety.value_counts()  

Kama wheat        14
Rosa wheat        14
Canadian wheat    14
Name: grain_variety, dtype: int64

varieties = list(seeds_df.pop('grain_variety'))

samples = seeds_df.values

samples

array([[14.88  , 14.57  ,  0.8811,  5.554 ,  3.333 ,  1.018 ,  4.956 ],
       [14.69  , 14.49  ,  0.8799,  5.563 ,  3.259 ,  3.586 ,  5.219 ],
       [14.03  , 14.16  ,  0.8796,  5.438 ,  3.201 ,  1.717 ,  5.001 ],
       [13.99  , 13.83  ,  0.9183,  5.119 ,  3.383 ,  5.234 ,  4.781 ],
       [14.11  , 14.26  ,  0.8722,  5.52  ,  3.168 ,  2.688 ,  5.219 ],
       [13.02  , 13.76  ,  0.8641,  5.395 ,  3.026 ,  3.373 ,  4.825 ],
       [15.49  , 14.94  ,  0.8724,  5.757 ,  3.371 ,  3.412 ,  5.228 ],
       [16.2   , 15.27  ,  0.8734,  5.826 ,  3.464 ,  2.823 ,  5.527 ],
       [13.5   , 13.85  ,  0.8852,  5.351 ,  3.158 ,  2.249 ,  5.176 ],
       [15.36  , 14.76  ,  0.8861,  5.701 ,  3.393 ,  1.367 ,  5.132 ],
       [15.78  , 14.91  ,  0.8923,  5.674 ,  3.434 ,  5.593 ,  5.136 ],
       [14.46  , 14.35  ,  0.8818,  5.388 ,  3.377 ,  2.802 ,  5.044 ],
       [11.23  , 12.63  ,  0.884 ,  4.902 ,  2.879 ,  2.269 ,  4.703 ],
       [14.34  , 14.37  ,  0.8726,  5.63  ,  3.19  ,  1.313 ,  5.15  ],
       [16.84  , 15.67  ,  0.8623,  5.998 ,  3.484 ,  4.675 ,  5.877 ],
       [17.32  , 15.91  ,  0.8599,  6.064 ,  3.403 ,  3.824 ,  5.922 ],
       [18.72  , 16.19  ,  0.8977,  6.006 ,  3.857 ,  5.324 ,  5.879 ],
       [18.88  , 16.26  ,  0.8969,  6.084 ,  3.764 ,  1.649 ,  6.109 ],
       [18.76  , 16.2   ,  0.8984,  6.172 ,  3.796 ,  3.12  ,  6.053 ],
       [19.31  , 16.59  ,  0.8815,  6.341 ,  3.81  ,  3.477 ,  6.238 ],
       [17.99  , 15.86  ,  0.8992,  5.89  ,  3.694 ,  2.068 ,  5.837 ],
       [18.85  , 16.17  ,  0.9056,  6.152 ,  3.806 ,  2.843 ,  6.2   ],
       [19.38  , 16.72  ,  0.8716,  6.303 ,  3.791 ,  3.678 ,  5.965 ],
       [18.96  , 16.2   ,  0.9077,  6.051 ,  3.897 ,  4.334 ,  5.75  ],
       [18.14  , 16.12  ,  0.8772,  6.059 ,  3.563 ,  3.619 ,  6.011 ],
       [18.65  , 16.41  ,  0.8698,  6.285 ,  3.594 ,  4.391 ,  6.102 ],
       [18.94  , 16.32  ,  0.8942,  6.144 ,  3.825 ,  2.908 ,  5.949 ],
       [17.36  , 15.76  ,  0.8785,  6.145 ,  3.574 ,  3.526 ,  5.971 ],
       [13.32  , 13.94  ,  0.8613,  5.541 ,  3.073 ,  7.035 ,  5.44  ],
       [11.43  , 13.13  ,  0.8335,  5.176 ,  2.719 ,  2.221 ,  5.132 ],
       [12.01  , 13.52  ,  0.8249,  5.405 ,  2.776 ,  6.992 ,  5.27  ],
       [11.34  , 12.87  ,  0.8596,  5.053 ,  2.849 ,  3.347 ,  5.003 ],
       [12.02  , 13.33  ,  0.8503,  5.35  ,  2.81  ,  4.271 ,  5.308 ],
       [12.44  , 13.59  ,  0.8462,  5.319 ,  2.897 ,  4.924 ,  5.27  ],
       [11.55  , 13.1   ,  0.8455,  5.167 ,  2.845 ,  6.715 ,  4.956 ],
       [11.26  , 13.01  ,  0.8355,  5.186 ,  2.71  ,  5.335 ,  5.092 ],
       [12.46  , 13.41  ,  0.8706,  5.236 ,  3.017 ,  4.987 ,  5.147 ],
       [11.81  , 13.45  ,  0.8198,  5.413 ,  2.716 ,  4.898 ,  5.352 ],
       [11.27  , 12.86  ,  0.8563,  5.091 ,  2.804 ,  3.985 ,  5.001 ],
       [12.79  , 13.53  ,  0.8786,  5.224 ,  3.054 ,  5.483 ,  4.958 ],
       [12.67  , 13.32  ,  0.8977,  4.984 ,  3.135 ,  2.3   ,  4.745 ],
       [11.23  , 12.88  ,  0.8511,  5.14  ,  2.795 ,  4.325 ,  5.003 ]])

#距离计算的linkage 还有树状图dendrogram
from scipy.cluster.hierarchy import linkage, dendrogram
import matplotlib.pyplot as plt

#进行层次聚类
mergings = linkage(samples, method='complete')

#树状图结果
fig = plt.figure(figsize=(10,6))
dendrogram(mergings,
           labels=varieties,
           leaf_rotation=90,
           leaf_font_size=6,
)
plt.show()

#得到标签结果
#maximum height自己指定
from scipy.cluster.hierarchy import fcluster
labels = fcluster(mergings, 6, criterion='distance')

df = pd.DataFrame({'labels': labels, 'varieties': varieties})
ct = pd.crosstab(df['labels'], df['varieties'])
ct

           

 不同距离的选择会产生不同的结果

import pandas as pd

scores_df = pd.read_csv('./datasets/eurovision-2016-televoting.csv', index_col=0)
country_names = list(scores_df.index)
scores_df.head()

#缺失值填充，没有的就先按满分算吧
scores_df = scores_df.fillna(12)

#归一化
from sklearn.preprocessing import normalize
samples = normalize(scores_df.values)

samples

array([[0.09449112, 0.56694671, 0.        , ..., 0.        , 0.28347335,
        0.        ],
       [0.49319696, 0.        , 0.16439899, ..., 0.        , 0.41099747,
        0.        ],
       [0.        , 0.49319696, 0.12329924, ..., 0.        , 0.32879797,
        0.16439899],
       ...,
       [0.32879797, 0.20549873, 0.24659848, ..., 0.49319696, 0.28769823,
        0.        ],
       [0.28769823, 0.16439899, 0.        , ..., 0.        , 0.49319696,
        0.        ],
       [0.        , 0.24659848, 0.        , ..., 0.        , 0.20549873,
        0.49319696]])

from scipy.cluster.hierarchy import linkage, dendrogram
import matplotlib.pyplot as plt

mergings = linkage(samples, method='single')
fig = plt.figure(figsize=(10,6))
dendrogram(mergings,
           labels=country_names,
           leaf_rotation=90,
           leaf_font_size=6,
)
plt.show()

mergings = linkage(samples, method='complete')
fig = plt.figure(figsize=(10,6))
dendrogram(mergings,
           labels=country_names,
           leaf_rotation=90,
           leaf_font_size=6,
)
plt.show()