0 引言

由于处理的数据量每天都在增加，因此能够检测数据结构并识别数据集中的子集的方法变得越来越重要。聚类是这些方法中的一种。聚类或聚类分析是一项无监督的归纳学习任务，它基于各个点之间的相似性将数据组织到同质的组中。聚类是机器学习，是数据挖掘和统计中已研究的基本问题之一^[1-3]。聚类方法可以产生与分类方法相同的结果，但是不存在预定义的类，因此也可以视为无监督分类^[4-5]。

聚类算法的性能可以通过其发现数据集中某些或所有隐藏模式的能力来衡量，可以通过测量数据点之间的相似性(不相似性)来发现隐藏的模式。相似度表示在明确定义的意义上测得的数学相似度，通常使用距离函数进行定义，根据聚类算法的规则，可以测量数据点本身之间或数据点与某个特殊点之间的距离。同时，随着数据的划分，同一群集中的数据点应尽可能相似，而不同群集中的数据点应尽可能不相似^[6-7]。多年来，已经开发出多种不同的聚类方法。1998年，Fraley C和RAFTERY A E将聚类算法分为层次结构和分区两组。Han和Kamber在2006年将聚类算法分为5类：分层、分区、基于密度、基于网格和基于模型^[8]。

JOHNSON S定义的分层方法将点安排到一个基础层次结构中，该层次结构随后确定各种聚类^[9]。层次聚类分为聚集和分裂两种类型。聚集方法具有自下而上的过程，首先将每个数据点放置在其自己的聚类中，然后将聚类连续合并为更大的聚类，或者直到满足给定的终止条件(例如特定数量的聚类)为止。分裂方法与聚集法相反，并且以自顶向下的方式执行。分区方法将数据集划分为K个分区，每个分区代表一个聚类，它有两种类型的分区，即清晰分区和模糊分区。如果数据集的每个数据点仅属于一个簇，则称为“清晰”，但如果允许数据点成为多个具有不同程度的簇的成员，则称为“模糊”^[10]。K-means和K-mediods方法是两种常用的聚类方法。在K-means算法中，每个聚类由数据点的平均值表示，而在K-mediods中，一个聚类由聚类中位于最中心的数据点表示。

在基于密度的方法中，簇是数据空间中最密集的区域，被较低密度的区域隔开。ESTER M等人1996年提出的空间聚类是基于密度的方法的一个示例，只要邻域中的密度超过某个阈值，该方法就会不断地增长聚类效果^[11]。基于网格的方法将数据空间量化为有限数量的单元，这些单元形成一个网格结构，在该网格结构上执行所有用于聚类的操作，它与数据点无关，但与围绕数据点的值空间有关。基于统计信息网格是WANG W等人1997年提出的基于网格的方法对空间数据集进行聚类的典型示例，在这种方法中，将空间区域划分为由分层结构表示的矩形单元^[12]。基于模型的聚类方法假定数据是由模型生成的，并尝试从数据中发现原始模型，统计方法和神经网络方法是基于模型的两种主要方法^[13]。

本文的目的是在分层聚类的基础上优化分层算法，并使用更多的验证措施来证明提出算法的强度。该算法使用交点作为链接标准，以合理的计算复杂度提供更有效、更准确的聚类结果。该算法的第一步是为每个数据点找出最接近的邻居(NN)，以形成对，然后找出对之间的交点以形成主聚类。本文以二维示例介绍了新的层次聚类算法，解释了聚类评估，并介绍了新层次聚类算法与某些现有聚类算法进行比较的实验结果。

本文详细内容请下载:http://www.chinaaet.com/resource/share/2000003131

作者信息:

李青旭，陈天鹰，胡 波

(华北计算机系统工程研究所，北京100083)