数学建模优秀讲座之聚类分析及其应用

聚类分析及其应用
聚类分析简介
• 聚类分析指将物理或抽象对象的集合分组为由类似 的对象组成的多个类的分析过程。它是一种重要的 人类行为。
• 聚类分析的目标就是在相似的基础上收集数据来分 类。聚类源于很多领域，包括数学，计算机科学， 统计学，生物学和经济学。在不同的应用领域，很 多聚类技术都得到了发展，这些技术方法被用作描 述数据，衡量不同数据源间的相似性，以及把数据 源分类到不同的簇中。
• 聚类分析法是理想的多变量统计技术，主要有分层 聚类法和迭代聚类法。 聚类分析也称群分析、点群 分析，是研究分类的一种多元统计方法
聚类分析算法用途
• 在商业上，聚类可以帮助市场分析人员从消费者 数据库中区分出不同的消费群体来，并且概括出 每一类消费者的消费模式或者说习惯。它作为数 据挖掘中的一个模块，可以作为一个单独的工具 以发现数据库中分布的一些深层的信息，并且概 括出每一类的特点，或者把注意力放在某一个特 定的类上以作进一步的分析；并且，聚类分析也 可以作为数据挖掘算法中其他分析算法的一个预 处理步骤。
聚类分析的常见方法
• 划分法
划分法(partitioning methods)，给定一个有N个元组或者纪录的 数据集，分裂法将构造K个分组，每一个分组就代表一个聚类， K<N。而且这K个分组满足下列条件： （1） 每一个分组至少包含一个数据纪录； （在某2）些每模一糊个聚数类据算纪法录中属可于以且放仅宽属）于；一个分组（注意：这个要求 对于给定的K，算法首先给出一个初始的分组方法，以后通过反 复迭代的方法改变分组，使得每一次改进之后的分组方案都较 前一次好，而所谓好的标准就是：同一分组中的记录越近越好， 而不同分组中的纪录越远越好。 使用这个基本思想的算法有：K-MEANS算法、K-MEDOIDS算法、 CLARANS算法；
• 任意形状 许多聚类算法基于欧几里得或者曼哈顿距离度量来决 定聚类。基于这样的距离度量的算法趋向于发现具有 相近尺度和密度的球状簇。但是，一个簇可能是任意 形状的。提出能发现任意形状簇的算法是很重要的。 • 领域最小化 许多聚类算法在聚类分析中要求用户输入一定的参数， 例如希望产生的簇的数目。聚类结果对于输入参数十 分敏感。参数通常很难确定，特别是对于包含高维对 象的数据集来说。这样不仅加重了用户的负担，也使 得聚类的质量难以控制。
• 图论聚类法
• 图论聚类方法解决的第一步是建立与问题相适应 的图，图的节点对应于被分析数据的最小单元， 图的边（或弧）对应于最小处理单元数据之间的 相似性度量。因此，每一个最小处理单元数据之 间都会有一个度量表达，这就确保了数据的局部 特性比较易于处理。图论聚类法是以样本数据的 局域连接特征作为聚类的主要信息源，因而其主 要优点是易于处理局部数据的特性。
聚类要求
• 可伸缩性 许多聚类算法在小于 200 个数据对象的小数据集合上 工作得很好；但是，一个大规模数据库可能包含几百 万个对象，在这样的大数据集合样本上进行聚类可能 会导致有偏的结果。我们需要具有高度可伸缩性的聚 类算法。 • 不同属性 许多算法被设计用来聚类数值类型的数据。但是，应 用可能要求聚类其他类型的数据，如二元类型(binary)， 分类/标称类型（categorical/nominal），序数型 （ordinal）数据，或者这些数据类型的混合。
• 处理“噪声”
绝大多数现实中的数据库都包含了孤立点，缺失， 或者错误的数据。一些聚类算法对于这样的数据 敏感，可能导致低质量的聚类结果
• 记录顺序
一些聚类算法对于输入数据的顺序是敏感的。例 如，同一个数据集合，当以不同的顺序交给同一 个算法时，可能生成差别很大的聚类结果。开发 对数据输入顺序不敏感的算法具有重要的意义。
• 密度算法 • 基于密度的方法(density-based methods)，基于
密度的方法与其它方法的一个根本区别是：它不 是基于各种各样的距离的，而是基于密度的。这 样就能克服基于距离的算法只能发现“类圆形” 的聚类的缺点。 • 这个方法的指导思想就是，只要一个区域中的点 的密度大过某个阈值，就把它加到与之相近的聚 类中去。 • 代表算法有：DBSCAN算法、OPTICS算法、 DENCLUE算法等；
• 层次法 • 层次法(hierarchical methods)，这种方法对给定
的数据集进行层次似的分解，直到某种条件满足 为例如，在“自底向上”方案中，初始时每一个数 据纪录都组成一个单独的组，在接下来的迭代中， 它把那些相互邻近的组合并成一个组，直到所有 的记录组成一个分组或者某个条件满足为止。 • 代表算法有：BIRCH算法、CURE算法、 CHAMELEON算法等；
• 高维度 一个数据库或者数据仓库可能包含若干维或者属性。许多 聚类算法擅长处理低维的数据，可能只涉及两到三维。人 类的眼睛在最多三维的情况下能够很好地判断聚类的质量。 在高维空间中聚类数据对象是非常有挑战性的，特别是考 虑到这样的数据可能分布非常稀疏，而且高度偏斜。 • 基于约束 现实世界的应用可能需要在各种约束条件下进行聚类。假 设你的工作是在一个城市中为给定数目的自动提款机选择 安放位置，为了作出决定，你可以对住宅区进行聚类，同 时考虑如城市的河流和公路网，每个地区的客户要求等情 况。要找到既满足特定的约束，又具有良好聚类特性的数 据分组是一项具有挑战性的任务。
• 解释性-可用性 用户希望聚类结果是可解释的，可理解的，和可用的。 也就是说，聚类可能需要和特定的语义解释和应用相 联系。应用目标如何影响聚类方法的选择也是一个重 要的研究课题。 记住这些约束，我们对聚类分析的学习将按如下的步 骤进行。首先，学习不同类型的数据，以及它们对聚 类方法的影响。接着，给出了一个聚类方法的一般分 类。然后我们详细地讨论了各种聚类方法，包括划分 方法，层次方法，基于密度的方法，基于网格的方法， 以及基于模型的方法。最后我们探讨在高维空间中的 聚类和孤立点分析（outlier analysis）。