大数据聚类技术.pdf

⼤数据聚类技术 1.聚类的基本有关概念 聚类分析：将物理或抽象对象的集合分成相似的对象类的过程称为聚类。 簇：数据对象的集合，对象与同⼀簇中的对象批次相似，⽽与其他簇中的对象相异。 ⽆监督学习：没有事先定义好的类 典型应⽤： 作为获得数据集中数据分布的⼯具 作为其他数据挖掘算法的预处理步骤 2.聚类⽅法的分类 基于划分的聚类（partitioning methods）： 给定⼀个由n个对象组成的数据集合，对此数据集合构建k个划分（k<=n）,每个划分代表⼀个簇，即将数据集合分成多个簇的算法。每个簇 ⾄少有⼀个对象，每个对象必须仅且属于⼀个簇。具体算法包括：K-均值和K-中⼼点算法等。 基于层次的聚类（hierarchical clustering）： 对给定的数据集进⾏层层分解的聚类过程。 （1）凝聚法：将每个对象被认为是⼀个簇，然后不断合并相似的簇，知道达到⼀个令⼈满意的终⽌条件； （2）分裂法：先把所有的数据归于⼀个簇，然后不断分裂彼此相似度最⼩的数据集，使簇被分裂成更⼩的簇，直到达到⼀个令⼈满意的终 ⽌条件。 根据簇间距离度量⽅法的不同，可分为：最⼩距离、最⼤距离、平均值距离和平均距离等。 典型算法：CURE，Chameleon和BIRCH等。 基于密度的聚类（Density-Based Clustering）： 只要某簇邻近区域的密度超过设定的某⼀阈值，则扩⼤簇的范围，继续聚类。可以得到任意形状的簇 典型算法：DBSCAN、OPTICS和DENCLUE。 基于⽹格的聚类： 将问题空间化为有限数⽬的单元，形成⼀个空间⽹格结构，随后聚类在这些⽹格之间进⾏。算法速度较快。 典型算法：STING、WaveCluster和CLIQUE等。 上述⽅法属于传统聚类⽅法，对于维度较低的数据集有效，⽽当维度较⾼，就可能不适合了。 ⼆、评价标准 ⼆、评价标准 ⼀各好的聚类算法有两个表现： · high intra-class similarity 簇内⾼的相似度 · low inter-class similarity 簇间低的相似度 相似度的衡量标准是由距离函数d(i,j)表⽰，距离函数对于不同类型的问题⼀般不同。 其中⼆元变量： 具体应⽤： ⽽对于连续型变量，经常使⽤的是 Minkowski distance 聚类学习是⼀种⽆监督的学习⽅式，事先并不清楚数据的结构，所以任何算法，聚类结果的合理性和有效性都有待评价。 可伸缩性 即算法中模式数发⽣变化的情况。有些算法在模式数⼩的条件下，算法的性能很好，但是模式数增⼤后，算法性能下降。 如 PAM算法是⼀种k-中⼼点算法，它对⼩的数据集合⾮常有效，但对⼤的数据集合则没有良好的可伸缩性。 ⾼维性 即算法中模式属性个数发⽣变化的情况。有些算法只擅长处理低维数据。在⾼维空间中聚类是⼀个挑战，特别是数 据有可能⾮常 稀疏和偏斜。 可解释性和可⽤性 就要求聚类结果可解释、易理解。 发现任意形状的聚类 ⼀个簇可能是任意形状的，但⼀般的聚类算法是基于欧⽒距离和曼哈顿距离度量实现聚类，更 趋于发现球状簇。在 这⽅⾯，基于密度的聚类⽅法较好。 处理噪声数据的能⼒ 噪声数据可能是数据本⾝不完整，也可能是孤⽴点数据（Outlier）。 ⽤于决定输⼊参数的领域知识最⼩化和输⼊记录顺序敏感性 ⼀⽅⾯要求降低算法对输⼊参数的敏感程度，另⼀⽅⾯要求输⼊记录顺序对 算法的结果影响⼩。 如经典的k-均值算法，需要预先给出簇的数⽬。 三、经典算法 三、经典算法 （1）K均值算法 K均值（k-means）是⼀种⽆监督的聚类算法，这个算法需要事先知道簇的个数 具体步骤： 算法分析： 优势：执⾏和收敛过程相对较快，易理解。 局限性：必须事先知道聚类数； 算法要求簇是密集的、簇和簇之间的差异⽐较⼤；数据集的平均值的计算必须有适当的定义；不能⽤于⾮ 凸⾯的聚类；对于某些孤⽴数据和"噪声" 点敏感等。 （2）层次⽅法 部分参考 之前已经介绍层次⽅法的基本概念，其包括两种形式凝聚法和分裂法。 层次凝聚的代表是AGNES(AGglomerative NESting)算法。AGNES 算法最初将每个对象作为⼀个簇，然后这些簇根据某些准则被⼀步步 地合并。两个簇间的相似度有多种不同的计算⽅法。聚类的合并过程反复进⾏直到所有的对象最终满⾜簇数⽬。 算法步骤 AGNES（⾃底向上凝聚算法）算法的具体步骤如下所⽰： 输⼊： 输⼊：包含n个对象的数据库。 输出： 输出：满⾜终⽌条件的若⼲个簇。 (1) 将每个对象当成⼀个初始簇； (2) REPEAT (3) 计算任意两个簇的距离，并找到最近的两个簇； (4) 合并两个簇，⽣成新的簇的集合； (5) UNTIL 终⽌条件得到满⾜。 距离计算 上述算法的关键在于如何计算聚类簇之间的距离？实际上每个簇是⼀个 大数据聚类技术是数据分析领域的重要方法，主要用于无监督学习，即在没有先验类别信息的情况下，通过对数据集的分析来发现内在的结构和群组。聚类的目标是将相似的对象分到同一簇，而使不同簇的对象尽可能相异。聚类分析广泛应用在数据分布探索、预处理和其他数据挖掘任务中。 聚类方法主要分为四大类： 1. **基于划分的聚类**，如K-均值和K-中心点算法，它们通过迭代优化将数据分配到预设数量的簇中，直到满足一定的收敛条件。这种方法简单快速，但需要预先指定簇的数量，并对初始聚类中心敏感。 2. **基于层次的聚类**，包括凝聚法和分裂法。凝聚法从单个对象开始逐步合并，直至形成期望的簇数；分裂法则从整体开始逐渐分裂，直至满足终止条件。常见的算法有CURE、Chameleon和BIRCH。层次聚类灵活性较高，可以直观地展示簇的关系，但计算复杂度较高。 3. **基于密度的聚类**，如DBSCAN、OPTICS和DENCLUE，这类方法关注数据点的密度，能发现任意形状的簇，特别适合处理噪声数据和非规则形状的簇，但在高维数据中可能效率较低。 4. **基于网格的聚类**，如STING、WaveCluster和CLIQUE，通过构建网格结构进行聚类，速度较快，但可能会丢失部分信息，尤其在数据分布不均匀时。 评价聚类算法的标准通常包括簇内的高相似度和簇间的低相似度，这依赖于特定的距离函数，如Minkowski距离。其他重要的评估指标包括算法的可伸缩性（处理大量数据的能力）、高维性（在多维数据上的表现）、可解释性和可用性（结果是否易于理解和解释）、处理任意形状簇的能力以及对噪声数据的容忍度。 例如，K-均值算法执行速度快，但需要预知簇的数量，对初始点选择敏感，且容易受到异常值或噪声的影响。而层次聚类中的AGNES算法是一种自底向上的凝聚方法，通过计算和合并相似簇来构建层次结构，能发现不同规模的簇，但计算成本较高。 在实际应用中，选择合适的聚类算法取决于具体场景和数据特性，需要权衡算法的效率、精度和对数据的理解。同时，聚类结果的解释性和实用性也是评估算法优劣的重要标准。对于大数据集，可能需要考虑分布式计算和内存效率的优化策略，以适应大规模数据的处理需求。