层次聚类
紧接上章，本章主要是介绍和K-Means算法思想不同而的其他聚类思想形成的聚类算法。
k-means算法却是一种方便好用的聚类算法，但是始终有K值选择和初始聚类中心点选择的问题，而这些问题也会影响聚类的效果。为了避免这些问题，我们可以选择另外一种比较实用的聚类算法-层次聚类算法。顾名思义，层次聚类就是一层一层的进行聚类，可以由上向下把大的类别（cluster）分割，叫作分裂法；也可以由下向上对小的类别进行聚合，叫作凝聚法；但是一般用的比较多的是由下向上的凝聚方法。
本章主要涉及到的知识点有：
层次聚类
BIRCH算法
层次聚类
层次聚类方法对给定的数据集进行层次的分解，直到满足某种条件为止，传统的层次聚类算法主要分为两大类算法:分裂的层次聚类和凝聚的层次聚类。
分裂的层次聚类
DIANA算法( Divisive analysis)采用自顶向下的策略。首先将所有对象置于一个簇中，然后按照某种既定的规则逐渐细分为越来越小的簇(比如最大的欧式距离)，直到达到某个终结条件(簇数目或者簇距离达到阈值)。
分裂法指的是初始时将所有的样本归为一个类簇，然后依据某种准则进行逐渐的分裂，直到达到某种条件或者达到设定的分类数目。算法构建步骤：
（1）将样本集中的所有的样本归为一个类簇；
（2）在同一个类簇（计为c）中计算两两样本之间的距离，找出距离最远的两个样本a，b；
（3）将样本a，b分配到不同的类簇c1和c2中；
（4）计算原类簇（c）中剩余的其他样本点和a，b的距离，若是dis(a)<dis(b)，则将样本点归到c1中，否则归到c2中；
（5）重复以上步骤，直到达到聚类的数目或者达到设定的条件。
这里我们可以看出，上一章所说的 K-Means算法及其优化算法就是运用这种自顶向下的策略。例如：有一些点，按照上面所说的算法构建步骤的过程可以如下图表示出来：
常见的自顶向下的算法有K-means层次聚类算法。但值得注意的是：对于以上的例子，红色椭圆框中的对象聚类成一个簇可能是更优的聚类结果，但是由于橙色对象和绿色对象在第一次K-means就被划分到不同的簇，之后也不再可能被聚类到同一个簇。
两个簇之间最近的两个点的距离作为簇之间的距离，该方式的缺陷是受噪点影响大，容易产生长条状的簇。
凝聚的层次聚类
AGNES算法( Agglomerative Nesting)采用自底向上的策略。最初将每个对象作为一个簇，然后这些簇根据某些准则被一步一步合并，两个簇间的距离可以由这两个不同簇中距离最近的数据点的相似度来确定;聚类的合并过程反复进行直到所有的对象满足簇数目。
凝聚法指的是初始时将每个样本点当做一个类簇，所以原始类簇的大小等于样本点的个数，然后依据某种准则合并这些初始的类簇，直到达到某种条件或者达到设定的分类数目。算法步骤：
（1） 将样本集中的所有的样本点都当做一个独立的类簇；
（2） 计算两两类簇之间的距离（后边会做介绍），找到距离最小的两个类簇c1和c2；
（3） 合并类簇c1和c2为一个类簇；
（4） 重复以上步骤，直到达到聚类的数目或者达到设定的条件。
根据算法构建的步骤，算法的思想可以用下图来表现出来：
[图片上传失败...(image-fbc155-1521869527009)]
8.1.1 簇间距离
在以上算法的构建过程中，我们提到了两个簇之间的距离的计算，例如对于两个簇C_1和C_2，有三种方法计算塔门之间的距离：
（1）单连锁（Single link）
两个簇之间的最小距离:
如下图所示：
图10.3単连锁图
两个簇之间最近的两个点的距离作为簇之间的距离，该方式的缺陷是受噪点影响大，容易产生长条状的簇。
（2）全连锁（Complete link）
两个簇之间的最大距离:
两个簇之间最远的两个点的距离作为簇之间的距离，采用该距离计算方式得到的聚类比较紧凑。
（3）平均连锁（Average link）
两个簇之间的平均距离:
两个簇之间两两点之间距离的平均值，该方式可以有效地排除噪点的影响。
层次聚类小结
层次聚类的优缺点：
（1）简单，理解容易
（2）合并点/分裂点选择不太容易
（3）合并/分类的操作不能进行撤销
（4）大数据集不太适合
（5）执行效率较低Ot*n2)，t为迭代次数，n为样本点数
层次聚类算法示例
Agglomerative算法
对于如下数据：
将A到F六个点，分别生成6个簇；
找到当前簇中距离最短的两个点，这里我们使用单连锁的方式来计算距离，发现A点和B点距离最短，将A和B组成一个新的簇，此时簇列表中包含五个簇，分别是{A，B}，{C}，{D}，{E}，{F}，如下图所示；
2 . 找到当前簇中距离最短的两个点，这里我们使用单连锁的方式来计算距离，发现A点和B点距离最短，将A和B组成一个新的簇，此时簇列表中包含五个簇，分别是{A，B}，{C}，{D}，{E}，{F}，如下图所示；
3 . 重复步骤二、发现{C}和{D}的距离最短，连接之，然后是簇{C，D}和簇{E}距离最短，依次类推，直到最后只剩下一个簇，得到如下所示的示意图：
4 .此时原始数据的聚类关系是按照层次来组织的，选取一个簇间距离的阈值，可以得到一个聚类结果，比如在如下红色虚线的阈值下，数据被划分为两个簇：簇{A，B，C，D，E}和簇{F}
Agglomerative聚类算法的优点是能够根据需要在不同的尺度上展示对应的聚类结果，缺点同Hierarchical K-means算法一样，一旦两个距离相近的点被划分到不同的簇，之后也不再可能被聚类到同一个簇，即无法撤销先前步骤的工作。另外，Agglomerative性能较低，并且因为聚类层次信息需要存储在内存中，内存消耗大，不适用于大量级的数据聚类，下面介绍一种针对大数据量级的聚类算法BIRCH。
BIRCH算法
B|RCH算法(平衡迭代削减聚类法):聚类特征使用3元组进行一个簇的相关信息，通过构建满足分枝因子和簇直径限制的聚类特征树来求聚类，聚类特征树其实是个具有两个参数分枝因子和类直径的高度平衡树;分枝因子规定了树的每个节点的子女的最多个数，而类直径体现了对这一类点的距离范围;非叶子节点为它子女的最大特征值;聚类特征树的构建可以是动态过程的，可以随时根据数据对模型进行更新操作。
BIRCH算法的全称是Balanced Iterative Reducing and Clustering using Hierarchies，它使用聚类特征来表示一个簇，使用聚类特征树（CF-树）来表示聚类的层次结构，算法思路也是“自底向上”的。该算法的步骤如下：
（1）构建BIRCH算法的核心—CF-树（Clustering Feature Tree），而CF-树种每个节点代表一个簇的抽象特征，包含三个数据：簇中数据个数，n个点的线性和，n个数据点的平方和；
（2）从根节点开始，自上而下选择最近的孩子节点；
到达叶子节点后，检查距离其最近的CF能否吸收此数据点：
a) 是，更新CF值
b) 否，创建一个新的CF节点，检查该节点能否加入到当前叶子节点
i. 能，添加到当前叶子节点；
ii. 否，分裂最远的一对CF节点，按最近距离重新分配其它节点；
（3）更新每个非叶子节点的CF信息，如果分裂节点，在父节点中插入新的CF节点，直到root；
算法示意图如下图：
示例
基于scikit包中的创建的模拟数据的API进行数据的创建。使用BIRCH算法对数据进行数据进行划分类，比较不同模型数量对算法的图像的影响。
- 导入模块。
#导入我们要用的包，包括算法数据创建模块，算法评估模块，算法模块。
from itertools import cycle
from time import time
import numpy as np
import matplotlib as mpl
import matplotlib.pyplot as plt
import matplotlib.colors as colors
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import Birch
from sklearn.datasets.samples_generator import make_blobs
- 创建数据
#创建呈现3个团状共3000个样本数据，样本有两个特征属性，
## 设置属性防止中文乱码 mpl.rcParams['font.sans-serif'] = [u'SimHei']
mpl.rcParams['axes.unicode_minus'] = False
## 产生模拟数据
xx = np.linspace(-22， 22， 10)
yy = np.linspace(-22， 22， 10)
xx， yy = np.meshgrid(xx， yy)
n_centres = np.hstack((np.ravel(xx)[:， np.newaxis]，
np.ravel(yy)[:， np.newaxis]))
#产生10万条特征属性是2，类别是100，符合高斯分布的数据集
X， y = make_blobs(n_samples=100000，n_features=2， centers=n_centres， random_state=28)
原始的数据集如下图所示：
- 模型构建
#创建不同的参数（簇直径）Birch层次聚类
birch_models = [
Birch(threshold=1.7, n_clusters=100),
Birch(threshold=1.7, n_clusters=None)
]
#threshold：簇直径的阈值， branching_factor：大叶子个数
#我们也可以加参数来试一下效果，比如加入分支因子branching_factor，给定不同的参数值，看聚类的结果
final_step = [ u'直径=1.7;n_clusters=100',
u'直径=1.7;n_clusters=None'
]
plt.figure(figsize=(12, 8), facecolor='w')
plt.subplots_adjust(left=0.02, right=0.98, bottom=0.1, top=0.9)
colors_ = cycle(colors.cnames.keys())
cm = mpl.colors.ListedColormap(colors.cnames.keys())
5.模型的构建
for ind, (birch_model, info) in enumerate(zip(birch_models, final_step)):
t = time()
birch_model.fit(X)
time_ = time() - t
# 获取模型结果（label和中心点）
labels = birch_model.labels_
centroids = birch_model.subcluster_centers_
n_clusters = len(np.unique(centroids))
print("Birch算法，参数信息为：%s；模型构建消耗时间为:%.3f秒；聚类中心数目:%d" % (info, time_, len(np.unique(labels))))
- 画图预测模型
## 画图
subinx = 221 + ind
plt.subplot(subinx)
for this_centroid, k, col in zip(centroids, range(n_clusters), colors_):
mask = labels == k
plt.plot(X[mask, 0], X[mask, 1], 'w', markerfacecolor=col, marker='.')
if birch_model.n_clusters is None:
plt.plot(this_centroid[0], this_centroid[1], '*', markerfacecolor=col, markeredgecolor='k', markersize=2)
plt.ylim([-25, 25])
plt.xlim([-25, 25])
plt.title(u'Birch算法%s，耗时%.3fs' % (info, time_))
plt.grid(False)
画出原始数据的图
# 原始数据集显示
plt.subplot(224)
plt.scatter(X[:, 0], X[:, 1], c=y, s=1, cmap=cm, edgecolors='none')
plt.ylim([-25, 25])
plt.xlim([-25, 25])
plt.title(u'原始数据')
plt.grid(False)
plt.show()
- 当簇的直径为0.5时候，处的数量分别为100和None时候输出的结果：
Birch算法，参数信息为：直径=0.5;n_clusters=100；模型构建消耗时间为:6.762秒；聚类中心数目:100
Birch算法，参数信息为：直径=0.5;n_clusters=None；模型构建消耗时间为:6.698秒；聚类中心数目:3205
- 输出的图画：
- 当簇的直径为0.5时候，处的数量分别为100和None时候输出的结果：
Birch算法，参数信息为：直径=1.7;n_clusters=100；模型构建消耗时间为:2.244秒；聚类中心数目:100
Birch算法，参数信息为：直径=1.7;n_clusters=None；模型构建消耗时间为:2.391秒；聚类中心数目:171
- 输出的结果如下图所示：
BIRCH算法相比Agglomerative凝聚算法具有如下特点：
（1）解决了Agglomerative算法不能撤销先前步骤的工作的缺陷；
（2）CF-树只存储原始数据的特征信息，并不需要存储原始数据信息，内存开销上更优；
（3）BIRCH算法只需要遍历一遍原始数据，而Agglomerative算法在每次迭代都需要遍历一遍数据，所以BIRCH在性能也优于Agglomerative；
（4）支持对流数据的聚类，BIRCH一开始并不需要所有的数据；
小结
本章主要介绍了聚类中的其他聚类算法的思想—层次聚类，着重介绍了算法—Agglomerative算法，BIRCH算法。以上所有的算法的实现都是依赖于机器学习库—scikit-learn库，当然还有其他聚类比如，谱聚类，Apriori关联分析等都有很好的聚类分析能力。只要掌握其思想，才能对各种聚算法融会贯通。
