读书笔记 -- 006_数据挖掘_聚类_概念知识
作为一种独立的数据挖掘功能聚类分析不仅可以用于揭示数据分布规律还可以用来识别特定簇中的典型特征以及进一步聚焦于感兴趣的目标群体进行深入研究。
此外它还可以作为其他高级算法如特征提取与选择以及分类模型训练的重要前处理步骤从而提高后续模型的效果与准确性。
在实际应用中根据具体需求可以选择基于距离度量的传统聚类方法如k-均值算法（k-means）或k-中心点算法（k-medoids）等来进行具体实现。
这些方法已经被成功集成到多种统计软件包中如S-Plus SPSS及SAS系统中供研究人员进行实际操作与应用开发。
1、对聚类分析的要求
数据挖掘对聚类分析的典型要求如下：
1、）可伸缩性： 聚类算法不仅要在小数据集(比如，几百个数据对象)上运行良好，而且要求在大型数据集上也能运行良好，结果不能有偏差。
2、）处理不同属性类型的能力： 许多算法是为数值(基于区间)的数据设计的。然而，用于可能要求聚类其他类型的数据。最近，越来越多的应用需要对诸如图、序列、图像和文档这样的复杂类型进行聚类的技术。
3、）发现任意形状的簇： 许多聚类算法是基于欧几里得或者曼哈顿距离度量来确定簇。基于这些距离度量的算法趋向于发现具有相近尺寸和密度的球状簇。然而，一个簇可能是任意形状的。
4、）对于确定输入参数的领域知识的要求： 许多聚类算法都要求用户以输入参数(如希望产生的簇的数目)的形式提供领域知识。因此，聚类结果可能对这些参数十分敏感。通常，参数很难确定，对于高维数据集和用户尚未深入理解的数据来说更是如此。要求提供领域知识不仅加重了用户的负担，而且使得聚类的质量难以控制。
5、）处理噪声数据的能力： 现实世界中的大部分数据集都包含离群点和/或缺失数据、未知或错误的数据。一些聚类算法可能对噪声敏感，从而产生低质量的聚类结果。
6、）增量聚类和对输入次序不敏感： 在许多应用中，增量更新(提供新数据)可能随时发生。一些新算法不能将新插入的数据(如数据库更新)合并到已有的聚类结构中去，而使需要从头开始重新聚类。一些聚类算法还可能对输入数据的次序敏感。
7、）聚类高维数据的能力： 数据集可能包含大量的维或者属性。许多算法擅长处理低维的数据。发现高维空间中的数据对象的簇是一个挑战，特别是考虑这样的数据可能非常稀疏，并且高度倾斜。
8、）基于约束的聚类： 现实世界的应用可能需要在各种约束条件下进行聚类。找到既满足特定的约束又具有良好聚类特性的数据分组是一项具有挑战性的任务。
9、）可解释性和可用性： 用户希望聚类结果是可解释的、可理解的和可用的。也就是说，聚类结果可能需要与特定的语义解释和应用相联系。重要的是研究应用目标如何影响聚类特征和聚类方法的选择。
2、比较现有的聚类方法可以从以下几个方面展开：
1）划分准则： 在某些算法中，默认情况下所有数据样本都会被划分为若干个簇（cluster），这些簇之间不存在层次结构关系，并且这些簇处于同一层次中。然而，在其他算法中则采用分层的方式对数据样本进行划分（hierarchical clustering），其中各个簇可能存在于不同的语义层次中。
2）簇间分离性： 大多数聚类方法将数据样本划分为互不相交（disjoint）的簇集合（cluster set），即每个数据样本仅属于一个特定的簇集合中的一个成员（cluster member）。但也存在一些算法允许一个数据样本同时属于多个簇集合（multi-cluster membership）。
3）相似性度量： 许多聚类算法通过计算两个样本之间的距离来衡量它们的相似程度（similarity measure）。这种距离可以在欧氏空间、道路网格或其他向量空间中进行定义与计算。然而，在另一种思路下，则采用基于密度连接性和邻近关系的方式来定义相似性度量（similarity metric），这种方法并不直接依赖于两个样本之间的绝对距离值（absolute distance value）。无论采用哪种方式设计聚类算法的核心都在于构建有效的相似性度量机制（similarity measure mechanism）。值得注意的是，在基于欧氏距离等传统指标的方法中通常能够利用最优化技术来提高效率与效果；而基于密度或连通性的方法则更适合发现形状复杂的非凸型或多维结构中的潜在簇结构（underlying cluster structure）。
4）多维空间中的聚类分析： 大多数传统的聚类算法会在整个给定的数据空间中搜索并提取潜在的簇结构（cluster structure）。这种方法对于低维数据集来说是合理的并且有效可行；但随着数据维度的增长问题变得愈发复杂难以处理——高维数据集中可能存在大量冗余属性导致计算出的结果不可靠甚至失去实际意义。因此在面对高维数据集时应该优先考虑在不同子空间范围内进行探索与分析——子空间聚类分析正是这种思路的具体体现。
综上所述，在机器学习领域中存在多种聚类算法设计标准。这些标准主要包括系统的可伸缩性特性以及其能够有效处理不同类型的数据（包括噪声数据），支持增量式更新机制的能力（即支持增量式更新机制），能够识别任意形状数据模式的能力（即具备灵活多变的模式识别能力），以及满足特定约束条件的需求（即满足特定约束条件）。同样重要的是其可解释性和实用性（即具备良好的可解释性与实用性）。此外，在实际应用中对层次划分策略的选择、簇间互斥性的考虑、所采用的距离度量方法以及在高维子空间中的聚类行为等方面都可能带来不同的聚类方法选择（即不同场景下会选择不同的聚类方法）。
3、基本聚类方法概述
1、）划分方法： 划分方法在数据集上进行一层划分。典型地，基于划分方法采取互斥的簇进行划分，即每个对象必须恰好属于一个组。这个要求，可以在模糊划分技术中，可以放宽。为了达到全局最优，基于划分的聚类可能要穷举所有可能的划分，计算量极大。实际上，大多数应用都采用了流行的启发式方法，如k-均值和k-中心点算法，渐近地提高聚类质量，逼近局部最优解。这些启发式聚类方法很适合发现中小规模的数据库中的球状簇。为了发现具有复杂形状的簇和对超大型数据集进行聚类，需要进一步扩展基于划分的方法。
2、）层次方法：
层次方法创建给定数据对象集的层次分解。根据层次分解如何形成，层次方法可以分为凝聚的 或分裂的方法 。凝聚的方法，也称自底向上的方法，开始将每个对象作为一个组，然后组词合并相近的对象或组，指导所有的组合并为一个组(层次的最顶层)，或者满足某个终止条件。分裂的方法，也成自顶向下的方法，开始将所有的对象置于一个簇中。在每次相继迭代中，一个簇被划分为更小的簇，直到每个对象在单独的一个簇中，或者满足某个终止条件。
层次聚类方法包括以距离为基础的方法以及以密度和连通性为基础的方法。这些方法中的一些主要扩展涉及子空间聚类技术。
层次聚类方法存在局限性，在完成一次合并或分裂操作后就无法进行修改。这种严格的规定是有益的,因为它将产生较小的计算开销.然而,这一技术无法纠正错误决定.
基于密度的方法中大多数划分方法依据的是对象之间的距离来进行聚类分析.这些方法只能识别具有球形特征的数据簇,在识别具有任意形状数据簇时存在局限性.其主要思想是只要'邻域'中的密度(即对象或数据点数目)超过某个阈值就继续增长给定的簇,也就是说,对于给定的一个数据点所在簇中的每一个点,在其指定半径范围内的邻域内必须至少包含预定最少数量的数据点
该密度算法能把对象集合分割成多个不重叠的簇或以层次形式存在的簇结构。
一般而言，在基于密度的方法中，则只关注不重叠的簇。
此外，在扩展应用方面，则可以将这种方法从全局空间聚类推广至子空间聚类。
第4节所述之网格方法：该方法将对象的空间划分为有限数量的基本单元。
所有的聚类操作均在该网络架构（即量化后所形成的网格体系）内完成。
该方法的优势在于运行效率显著较高。
数据量的变化对该方法的时间影响微乎其微。
对于大量空间数据挖掘问题（特别是聚类分析），将数据划分为网格单元通常会带来显著的效果。这表明将基于网格的分类技术与其它聚类方法相结合能够进一步提升分析效果
