基于聚类分析的分类器设计

2023-06-28 理论教育版权反馈

【摘要】：基于聚类分析的分类与后面几节所述的有监督学习分类的不同之处在于，它要划分的类是未知的，也就是说事先并不知晓要把目标分为哪几个具体的类别。为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。它也基于标准的统计数字自动决定聚类的数目，考虑“噪声”数据和孤立点，从而产生健壮的聚类方法。高维数据聚类分析是聚类分析中一个非常活跃的领域，同时也是一个具有挑战性的工作。

作为统计学的一个分支，聚类就是将数据对象分组成为多个类或簇（Clus-ter），在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。相异度是根据描述对象的属性值来计算的，距离是最常采用的度量方式（见本书3.3.2节）。

如图3-2所示，在机器学习领域中，聚类是典型的无监督学习（Unsuper-vised Learning），不依赖预先定义的类别和带类标号的训练实例，也可以称之为观察式学习。基于聚类分析的分类与后面几节所述的有监督学习分类的不同之处在于，它要划分的类是未知的，也就是说事先并不知晓要把目标分为哪几个具体的类别。

图3-2 聚类在最小世界网络(Small World Network)中的应用

聚类算法的选择取决于数据的类型、聚类的目的和应用，可以对同样的数据尝试多种算法，以发现数据可能揭示的结果。主要的聚类算法大体上可以划分为如下几类：

1.划分的方法（Partitioning Method）

给定一个包含n个目标对象的数据集，一个划分方法构建对象数据的k个划分，每个划分表示一个类，并且k≤n。也就是说，它将样本划分为k个组，同时满足如下的要求：每个组至少包含一个对象；每个对象必须属于且只属于一个组。注意在某些模糊划分技术中第二个要求可以放宽。给定k，即要构建的划分的数目，划分方法首先创建一个初始划分。然后采用一种迭代的重定位技术，尝试通过对象在划分间移动来改进划分。一个好的划分的一般准则是：在同一个类中的对象之间的距离尽可能小，而不同类中的对象之间的距离尽可能大。还有许多其他划分质量的评判准则。

为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。实际上，绝大多数应用采用了以下两个比较流行的启发式方法：k-平均值（k-means）算法，在该算法中，每个簇用该簇中对象的平均值来表示；k-中心点（k-medoids）算法，在该算法中，每个簇用接近聚类中心的一个对象来表示。这些启发式聚类方法对在中小规模的数据集中发现球状簇很适用。为了对大规模的数据集进行聚类，以及处理复杂形状的聚类，基于划分的方法需要进一步的扩展。

2.层次的方法（Hierarchical Method）

层次的方法对给定数据集进行层次的分解。根据层次的分解如何形成，层次的方法可以被分为凝聚的和分裂的方法。凝聚的方法，也称为自底向上的方法，一开始将每个对象作为单独的一个组，然后继续地合并相近的对象或组，直到所有的组合并为一个（层次的最上层），或者达到一个终止条件。分裂的方法，也称为自顶向下的方法，一开始将所有的对象置于一个簇中。在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者达到一个终止条件。

层次的方法的缺陷在于，一旦一个步骤（合并或分裂）完成，它就不能被撤销。这个严格规定是有用的，所示不用担心组合数目的不同选择，计算代价会较小。但是，该技术的一个主要问题是它不能更正错误的决定。有两种方法可以改进层次聚类的结果：一种是在每层划分中，仔细分析对象间的连接，例如CURE和Chameleon中的做法；另一种是综合层次凝聚和迭代的重定位方法，首先用自底向上的层次算法，然后用迭代的重定位来改进结果，例如在BIRCH中的方法^［128］。

3.基于密度的方法（Density-based Method）

绝大多数划分方法基于对象之间的距离进行聚类。这样的方法只能发现球状的簇，而在发现任意形状的簇上遇到了困难。随之提出了基于密度的另一类聚类方法，其主要思想是：只要临近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域中必须包含至少某个数目的点。这样的方法可以用来过滤“噪声”数据，发现任意形状的簇。DBSCAN是一个有代表性的基于密度的方法，它根据一个密度阈值来控制簇的增长。OPTICS是另一个基于密度的方法，它为自动的和交互的聚类分析计算一个聚类顺序^［128］。

4.基于网格的方法（Grid-based Method）

基于网格的方法把对象空间量化为有限数目的单元，形成了一个网格结构。所有的聚类操作都在这个网格结构（即量化的空间）上进行。这种方法的主要优点是它的处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。STING是基于网格方法的一个典型例子，而CLIQUE和WaveCluster这两种算法既是基于网格的，又是基于密度的^［128］。

5.基于模型的方法（Model-based Method）

基于模型的方法为每个簇假定了一个模型，寻找数据对给定模型的最佳匹配。一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类。它也基于标准的统计数字自动决定聚类的数目，考虑“噪声”数据和孤立点，从而产生健壮的聚类方法。

COBWEB是一个常用的且简单的增量式概念聚类方法，它的输入对象是采用符号量（属性-值）对来加以描述的，采用分类树的形式来创建一个层次聚类；CLASSIT是COBWEB的另一个版本，可以对连续取值属性进行增量式聚类，它为每个节点中的每个属性保存相应的连续正态分布（均值与方差）；并利用一个改进的分类能力描述方法，即不像COBWEB那样计算离散属性（取值）和而是对连续属性求积分。

一些聚类算法集成了多种聚类方法的思想，所以有时将某个给定的算法划分为属于某类聚类方法是很困难的。此外，某些应用可能有特定的聚类标准，要求综合多个聚类技术。

传统的聚类方法已经比较成功地解决了低维数据的聚类问题，但在高维数据集中进行聚类时，却遇到了两个难以解决的问题：一是高维数据集中存在大量无关的属性使得在所有维中存在簇的可能性几乎为零；二是高维空间中数据较低维空间中数据分布要稀疏，其中数据间距离几乎相等是普遍现象，而传统聚类方法是基于距离进行聚类的，但在高维空间中无法基于距离来构建簇。

高维数据聚类分析是聚类分析中一个非常活跃的领域，同时也是一个具有挑战性的工作。信息技术的进步使得数据收集变得越来越容易，导致数据库规模越来越大、复杂性越来越高，如各种类型的贸易交易数据、Web文档、基因表达数据等，它们的维度（属性）通常可以达到成千上万维，甚至更高。目前，高维数据聚类分析在市场分析、信息安全、金融、娱乐、反恐等方面都有很广泛的应用。在图像目标识别方面，随着图像内容越来越丰富以及特征描述子的维度不断增加，进行高维数据聚类分析已经提上日程。

基于聚类分析的分类器设计

相关推荐