数据分析课件：聚类分析之层次聚类法

数据分析课件聚类分析之层次聚类法层次聚类是数据挖掘和机器学习中重要的无监督学习方法，通过分析数据点之间的相似性构建层次化的聚类结构本课程将深入探讨层次聚类的基本原理、算法实现和实际应用，帮助您掌握这一强大的数据分析工具课程内容概览1聚类分析概述介绍无监督学习基础和聚类分析的核心概念2层次聚类原理深入理解层次聚类的基本思想和实现机制3算法类型与应用探讨不同层次聚类算法的特点和适用场景实践操作指导聚类分析概述无监督学习方法相似对象分组广泛应用场景聚类分析是机器学习中重要的无监督聚类分析的核心目标是将具有相似特在商业智能、生物信息学、图像处学习技术，不需要预先定义的目标变征的对象归为同一类别，使得类内对理、社交网络分析等领域有着广泛应量或类别标签，通过发现数据中隐藏象相似性高，类间对象差异性大，从用，如客户细分、基因分析、市场细的模式和结构来进行知识发现而揭示数据的内在结构分等重要任务聚类分析的主要方法分类划分聚类法层次聚类法如、等算法本课程重点学习内容K-means K-medoids•需要预先指定聚类数量•不需要预设聚类数12•计算效率较高•形成树状结构•适合球形聚类•可视化效果好其他方法密度聚类法网格聚类和模型聚类如、等算法DBSCAN OPTICS•基于网格的快速聚类43•基于数据密度分布•基于统计模型的聚类•能发现任意形状聚类•特定场景优化•对噪声鲁棒什么是层次聚类核心特征独特优势层次聚类是一种基于簇间相似度的多层次数据分析方法，其最大与其他聚类方法相比，层次聚类提供了丰富的聚类信息，用户可特点是能够形成树形的聚类结构，称为聚类树或树状图以在不同的层次上观察聚类结果，从而获得对数据结构的深入理（）这种方法不需要预先指定簇的数量，可以解这种层次化的视角使得层次聚类在探索性数据分析中特别有Dendrogram根据数据的自然结构形成层次化的聚类结果价值层次聚类的基本思想相似性计算计算数据点之间的相似性或距离逐步操作通过合并或分裂操作构建聚类层次结构形成嵌套的层次聚类树多层观察在不同层次查看聚类结果层次聚类的主要类型凝聚型层次聚类分裂型层次聚类采用自下而上的合并策略，也称为（采用自上而下的分裂策略，也称为（AGNES AgglomerativeDIANA Divisive）算法这种方法从每个数据点作为独立的簇开始，通）算法这种方法从所有数据点在一个大簇开始，通Nesting Analysis过不断合并最相似的簇对，逐步减少簇的数量，最终形成完整的过不断分裂最不均匀的簇，逐步增加簇的数量，直到每个数据点聚类树凝聚型方法在实际应用中更为常见成为独立的簇分裂型方法计算复杂度较高凝聚型层次聚类详解初始化阶段将每个样本点视为一个独立的簇，此时簇的数量等于样本数量这是凝聚型聚类的起始状态，为后续的合并操作奠定基础迭代合并过程在每次迭代中，算法会寻找距离最近或相似度最高的两个簇进行合并，形成新的更大的簇这个过程会持续进行，直到所有样本都归入同一个簇中树状图构建每次合并操作都会在树状图中记录下来，包括合并的簇标识和合并时的距离值最终形成完整的层次聚类树，提供丰富的聚类信息凝聚型聚类算法流程距离矩阵计算1计算所有样本点对之间的距离，构建完整的距离矩阵作为聚类的基础数据结构2初始簇设定将每个样本点视为单独的簇，建立初始的簇集合最近簇合并3找到距离最近的两个簇并将其合并为一个新簇4距离矩阵更新重新计算新簇与其他簇之间的距离，更新距离矩阵迭代终止5重复合并过程直到只剩下一个包含所有样本的簇分裂型层次聚类详解单一大簇所有样本在一个簇中1选择分裂点2识别最异质的簇执行分裂3将选中的簇分为两个子簇重复过程4继续分裂直到满足终止条件分裂型聚类算法流程全局初始化1将所有样本视为一个大簇开始分析异质性评估2评估当前所有簇的内部异质性程度最优分裂3选择最异质的簇进行分裂操作条件判断4检查是否达到预期簇数或终止条件两种层次聚类方法对比凝聚型优势分裂型优势计算相对简单，实现难度较低，特别适合识别小规模的紧密聚计算复杂度较高，但在识别大规模聚类方面表现优异由于采用类在处理噪声数据时表现稳定，算法收敛性好由于其自下而自上而下的策略，能够更好地把握全局结构，适合处理层次结构上的特性，能够很好地保留局部结构信息明显的数据集•计算复杂度相对较低•适合发现大聚类•适合发现小聚类•全局视角更好•实现简单易懂•层次结构清晰层次聚类的距离度量方法欧氏距离曼哈顿距离闵可夫斯基距离最常用的距离计算两点间的度量方法，计城市街区距欧氏距离和曼算两点间的直离，适用于离哈顿距离的一线距离，适用散型数据和降般化形式，通于连续型数据低离群点影响过参数控制距p分析离特性余弦相似度测量向量间夹角，适合高维稀疏数据如文本分析和推荐系统欧氏距离详解数学定义适用场景欧氏距离是最直观的距离度量方法，计算公式为欧氏距离特别适合处理连续型数值数据，在图像处理、模式识别dx,y=它表示维空间中两点之间的直线距离，是几何等领域应用广泛但需要注意的是，欧氏距离对数据的尺度非常√Σxi-yi²n学中最基本的距离概念在高维空间的扩展敏感，不同量纲的特征可能会导致距离计算的偏差这种距离度量假设各个维度具有相同的重要性，并且数据在各个在实际应用中，当数据特征具有相似的物理意义或经过适当的归方向上的变化具有相同的意义因此，在使用欧氏距离之前，通一化处理后，欧氏距离能够提供可靠的相似性度量常需要对数据进行标准化处理曼哈顿距离详解计算原理独特优势曼哈顿距离的计算公式为与欧氏距离相比，曼哈顿距离，表示在网对离群点的敏感性较低，因为dx,y=Σ|xi-yi|格状路径中从一点到另一点的它使用绝对值而非平方差这最短路径长度这种距离度量使得曼哈顿距离在处理包含异模拟了在城市街区中行走的实常值的数据集时表现更加稳际情况，因此得名曼哈顿距健，特别适合离散型数据的分离析应用场景曼哈顿距离在处理高维稀疏数据、文本挖掘、以及存在明显异常值的数据集时表现优异在某些特定领域，如城市规划、物流配送等，曼哈顿距离更能反映实际问题的本质闵可夫斯基距离详解余弦相似度详解计算方法应用优势余弦相似度通过计算两个向量之间夹角的余弦值来衡量相似性，余弦相似度特别适合处理高维稀疏数据，如文本分析、推荐系公式为取值范围在之间，值统、信息检索等领域在这些应用中，数据的绝对大小往往不如cosθ=x·y/||x||×||y||[-1,1]越接近表示两个向量越相似，越接近表示越不相似其模式和方向重要1-1与传统的距离度量不同，余弦相似度关注的是向量的方向而非大此外，余弦相似度对数据的缩放不敏感，即使向量的模长发生变小，这使得它在处理不同尺度的数据时具有天然的优势化，只要方向保持一致，相似度值就会保持稳定，这在许多实际应用中是非常有价值的特性簇间距离计算方法概览最小距离法最大距离法方法方法Single LinkageComplete Linkage•基于最近点对距离•基于最远点对距离12•容易产生链式效应•生成紧凑簇•适合非椭圆形簇•对异常值敏感方法平均距离法Ward基于方差的方法方法Average Linkage43•最小化组内方差•所有点对距离平均•生成相似大小簇•平衡各种特性•广泛应用•计算复杂度较高最小距离法详解基本原理计算两簇之间所有点对的距离，选择其中的最小值作为簇间距离数学表达∈∈，寻找跨簇的最近点对dCi,Cj=min{dx,y:x Ci,y Cj}特征分析倾向于发现细长型或非椭圆形的聚类结构，但容易受噪声影响产生链式效应最大距离法详解计算原理最大距离法计算两簇之间所有点对距离的最大值，公式为dCi,Cj=∈∈这种方法确保合并的两个簇之间即使最远max{dx,y:x Ci,y Cj}的点对也保持相对较近的距离聚类特性最大距离法倾向于生成紧凑、球形的聚类，簇内点之间的距离相对较小这种方法产生的聚类结构通常比较均匀，簇的形状趋于规则，适合处理具有明显分离的数据集应用限制由于关注最远点对的距离，最大距离法对数据中的异常值和噪声比较敏感单个离群点可能会显著影响簇间距离的计算，从而影响整个聚类结果的质量平均距离法详解计算方式平衡特性平均距离法计算两簇所有点对之平均距离法有效平衡了最小距离间距离的平均值，公式为法和最大距离法的特点，既避免∈了链式效应，又不会过分强调紧dCi,Cj=avg{dx,y:x Ci,∈这种方法综合考虑了簇凑性这使得它在处理各种形状y Cj}间所有点对的距离信息，提供了的聚类时都能获得相对稳定的结更全面的簇间相似性度量果计算复杂度由于需要计算所有点对之间的距离并求平均值，平均距离法的计算复杂度相对较高，特别是在处理大规模数据集时，计算成本会显著增加但其稳定的聚类效果通常能够证明这种额外开销的价值重心法详解1重心计算计算每个簇的几何重心作为簇的代表点2距离度量使用重心之间的距离作为簇间距离dCi,Cj=dmi,mj3效率优势计算效率高，特别适合大规模数据处理4潜在问题可能出现距离倒置现象，影响聚类层次结构方法详解Ward核心思想应用特点方法基于误差平方和增量的概念，选择合并后使得组内方方法倾向于生成大小相近的球形聚类，这使得它在处理具Ward Ward差增加最小的簇对进行合并这种方法的目标是在每一步合并操有相似密度分布的数据时表现优异该方法在实际应用中非常受作中，尽可能保持簇内数据的紧密性，最小化信息损失欢迎，特别是在市场细分、客户分析等领域具体来说，方法计算每种可能的簇合并方案所导致的组内但需要注意的是，方法对异常值比较敏感，异常值可能会Ward Ward平方和增量，然后选择增量最小的方案进行实际合并操作显著影响聚类结果的质量，因此在使用前通常需要进行适当的数据预处理层次聚类算法实现步骤距离矩阵计算数据预处理根据选择的距离度量方法计算所有样本2包括缺失值处理、异常值检测、特征标点对之间的距离1准化和降维等关键步骤执行聚类算法3运行凝聚型或分裂型层次聚类算法5评估与解释结果可视化对聚类结果进行质量评估和业务解释4绘制树状图并确定最佳聚类数量数据预处理的重要性缺失值处理异常值检测特征标准化识别和处理数据中的缺失通过统计方法或可视化技对不同量纲的特征进行标值，可以采用删除、插值术识别数据中的异常值，准化或归一化处理，消除或使用特殊值标记等策略，根据业务需求决定是否删量纲差异对距离计算的影确保数据的完整性和分析除、转换或单独处理这些响，确保所有特征在聚类的可靠性异常观测过程中具有相等的权重降维处理在高维数据情况下，可以考虑使用主成分分析（）等降维技术，减PCA少计算复杂度并消除特征间的多重共线性树状图的构建与解读图形构成树状图由水平线和垂直线组成，水平线表示样本或簇，垂直线表示合并操作距离信息纵轴表示合并或分裂时的距离值，数值越大表示簇间差异越大聚类层次通过在不同高度切割树状图，可以获得不同数量的聚类结果模式识别观察树状图的分支模式，识别数据中的自然分组结构确定最佳聚类数的方法树状图分析法通过观察树状图中距离的显著跳跃来确定自然的聚类数寻找纵轴上相邻合并操作之间距离差异较大的位置，这些位置通常对应着合理的聚类划分点这种方法直观易懂，是最常用的聚类数确定方法轮廓系数法轮廓系数衡量每个样本与其所在簇的相似性以及与其他簇的差异性系数值范围在[-1,1]之间，值越接近1表示聚类效果越好通过计算不同聚类数下的平均轮廓系数，选择系数最大的聚类数肘部法则绘制聚类数与簇内误差平方和的关系图，寻找曲线中的肘部位置在肘部位置，增加聚类数对减少误差的贡献开始显著下降，该点对应的聚类数通常是较好的选择指数Davies-Bouldin该指数综合考虑簇内紧密度和簇间分离度，值越小表示聚类效果越好通过比较不同聚类数下的DB指数，选择指数最小的方案作为最优聚类数层次聚类算法伪代码算法凝聚型层次聚类（AGNES）输入数据集D={x1,x2,...,xn}，距离度量函数dist，链接准则linkage

1.初始化-创建n个簇，每个簇包含一个数据点-计算距离矩阵M，M[i][j]=distxi,xj-初始化聚类树T

2.重复以下步骤直到只剩一个簇a在当前所有簇对中找到距离最小的簇对Ci,Cj min_dist=∞for each簇对Ci,Cj:d=linkageCi,Cj,distif dmin_dist:min_dist=dbest_pair=Ci,Cjb合并最近的簇对-创建新簇Ck=Ci∪Cj-从簇列表中删除Ci和Cj，添加Ck-在聚类树T中记录合并操作c更新距离矩阵-计算新簇Ck与其他所有簇的距离-删除Ci和Cj对应的行列

3.输出完整的层次聚类树T时间复杂度On³空间复杂度On²本伪代码展示了凝聚型层次聚类的核心算法流程在实际实现中，可以通过优化数据结构和使用堆等技术来提高算法效率不同的链接准则（如单链接、完全链接、平均链接等）会影响聚类结果的特性，需要根据具体应用场景选择合适的方法。