层次聚类的方法及应用

姜子林

很多机器学习算法为各行各业注入新鲜血液，也使数据挖掘有了更多应用场景。由于我们生活中的大量数据是没有标注的，故很多时候我们需要聚类的算法，即根据数据本身的性质自动分类。而本文中，我们分析了聚合式层次聚类的方法步骤，并探究了其在实际问题中的应用。

【关键词】人工智能 机器学习 层次聚类 可视化

1 引言

在近几十年内，人工智能和机器学习发展迅速并且在各个领域都有着重要的应用，如数据挖掘，计算机视觉，自然语言处理等。而在大数据时代，面对海量数据，往往我们得到的数据中先验知识较少，需要从数据本身的分布结构特性去自动分析数据的属性和知识，这就是无监督学习。在无监督学习中，本文详细介绍了层次聚类的方法，包括计算点之间的距离和类之间的距离，逐步聚合，直到最后为每一类贴标签。并且为了对层次聚类有更深刻的理解我们对层次聚类做了实验，应用到一个鸢尾花花瓣的长度和宽度数据上，从可视化的结果中发现层次聚类确实把相距较远的簇成功分开了，成功的识别出了数据中的分布结构。

2 方法

主流的聚类方法包括k-means，层次聚类，mean-shift等。这些算法的共同特点都是以等长度向量（分布在同一空间中）的集合作为算法的输入，以每一个向量所属类别标签作为输出，而类别划分的原则都是越临近越容易被分到一类，但具体到效果因为方法不同而不同。其中，层次聚类的基本思想概括起来就是初始把每个点单独看做一个类别，然后依次合并两个最近的类别，直到需要合并的类别距离大于一个阈值为止。

在我们用计算机实现层次聚类的过程中，需要以下步骤：

（1）计算每两个点之间的距离，并且存储在一个向量里。这里我们用欧式距离作为距离度量。

（2）初始每个点作为一类，逐步合并最近的两类，而两类之间距离的算法是：一类和另一类各挑出一个点，算出距离，考虑所有情况，再去计算平均值。

（3）画出反映聚类合并过程的树状图。

（4）观察树状图，确定分割阈值，并且为每一个点打上聚类得到的类别标签。阈值是指最大值，而分割阈值是指设立的一个值，在该值以下所拥有的最少类的数量。

3 实验

这一节我们主要介绍在实验中我们使用到的数据以及具体处理过程，包括我们使用到的库和函数。我们使用python中sklearn库里的iris（鸢尾花）数据集，我们实验中采用其中共150个鸢尾花花瓣的长度和宽度作为样本进行聚类实验。分别引入matplotlib.pyplot（用于画图的一个库）、sklearn中的一个子库datasets（一个数据库）、以及pylab和scipy.cluster.hierarchy库。从datasets库中引入iris的属性（萼片长度（Sepal.Length）、萼片宽度（Sepal.Width）、花瓣长度（Petal.Length）、花瓣宽度（Petal.Width））选取后两种属性进行分析。设置对象为150对，设为150类。将其分别分为二、三、四类（X=2、1.25、1.15）可明显看出二类或三类更加容易区分，说明该算法对数据的分布簇型结构的发现是有效的。

在可视化过程中，首先对于树状图，进行层次聚类过程中，聚类的两类用线段连接，依次进行下去。然后对于散点图，例如分成两类的情况，则分别用两种颜色分辨两类，横坐标为花瓣长度或宽度，纵坐标为每两类的距离，最后将文字转化为图片，输入即可得到所要的图形。

4 结果展示

图1是将层次聚类用树状图的方式进行表述，横轴长度代表每一类大小，纵轴表示相对距离。而每一组连线都代表着将距离最近的两点联系起来，而这一条连线所取的高度即为两点距离。

具体画图过程：从sklearn库中挑选出datasets这个库，再从datasets子库中读取iris（鸢尾花）数据。挑选出后两种属性，即可得出图像，从这幅图中明显可以看出距离和越小越密集。依次向上进行层次聚类的过程中类间越来越大。

图2、图3、图4三幅图中，横轴表示花瓣长度，纵轴代表花瓣宽度，分别代表着将用层次聚类分为两类、三类、四类（X=2、1.25、1.15）。X=2时易得长度为1-2与3-6分别为一类，层次十分清晰。用相同方法分析X=1.25、1.15时，三类较清晰，而分为四类时层次聚类不明显，排除分为四类。

5 讨论

在该聚类过程中，有以下几点需要注意。类之间的距离的定义，我们这里选取平均距离作为两个类之间的距离定义，这里也可以选取两个类距离最近或最远的两点之间的距离作为类之间的距离。

另外，在聚类过程中，有一个需要预先定义的参数就是类的个数。类数的定义可以根据一些数学指标来确定，如使得所有平均类间距离和平均类内距离的比值最大。当然，还有一个判断标准就是可视化出来，来观察聚类效果如何，在本工作中，数据是二维的，如果维度大于二维，可以通过一些降维方法（构造一个从高维到二维空间的映射，使得原高维空间中点的邻近性在二维空间中尽量得以保留）来可视化。

6 结论

层次聚类是一种通过聚合形式逐步形成层次结构从而划分数据点类别的算法。我们通过鸢尾花数据的聚类实验验证这个算法的特性，并且用可视化方法观察了聚类结果，算法有效的发现了数据点中的簇状结构。而使用这种聚类方法可以很清晰的将大量繁杂的数据库聚类成几类，方法简单，利用图像也使聚类层次更加清晰，是一种简单直观的聚类方法。

参考文献

[1]http：//scitools.org.uk/iris/.

[2]Fisher，R.A."The use of multiple measurements in taxonomic problems" Annual Eugenics，7，Part II，179-188 （1936）；also in "Contributions to Mathematical Statistics"（John Wiley，NY，1950）.

[3]Johnson，Stephen C."Hierarchical clustering schemes."Psychometrika32.3（1967）：241-254.

[4]段明秀.層次聚类算法的研究及应用[D].中南大学，2009.

作者单位

湖北省宜昌市第一中学 湖北省宜昌市 443003