数据挖掘基础及应用 课件 第6章-聚类分析-蓝橙课堂版1

第6章聚类分析01第6章聚类分析理解相似性，比较分组方法，解释聚类结果数据挖掘基础及应用本章学习路线02概念与距离明确聚类对象，选择特征和距离。划分与层次理解均值迭代，观察合并与分裂。密度、图与网格比较不同方法如何定义簇。评价与应用选择评价口径，解释簇和规则。学习目标：能手算小型数据的聚类步骤，理解主要参数，并结合指标和应用问题评价结果。图6-1聚类分析知识结构图聚类：按照特征相似性分组03原始点集K=2的一种划分两幅图使用同一8点数据。右图按教材给定初始中心完成K-Means计算，颜色表示分组，不代表预先已知的类别。图6-2聚类可视化聚类与分类的区别04比较项分类聚类学习时的标签使用已知类别标签通常不使用类别标签主要问题新样本属于哪个已知类别对象在当前特征下如何分组输出含义预先定义的类别由算法得到的簇编号评价依据与真实类别比较预测表现结合结构指标、稳定性和用途簇编号本身没有业务含义。聚类完成后，需要回到原始特征解释每个簇。距离度量与特征尺度05欧氏距离：d(x,y)=√Σⱼ(xⱼ−yⱼ)²二维手算示例P=(1,2)，Q=(4,6)。欧氏距离=√(3²+4²)=5。曼哈顿距离=|3|+|4|=7。尺度改变距离的贡献金额、次数和比例的单位不同。数值范围大的特征可能主导距离。标准化后仍需考虑特征权重。类别编码也要符合变量含义。标准化统一数值尺度，并不自动保证各特征对实际问题同等重要。聚类前的数据准备06定义对象一名客户、一次访问或一周学习记录。整理特征处理缺失和异常，去除无效编号。缩放与距离说明缩放方法，选择合适距离。保留解释信息保存原始单位，便于描述簇特征。同一对象的表示影响分组按消费金额聚类与按商品偏好聚类，可能得到不同的客户群。时间曲线也要区分总量差异和形状差异，再决定是否归一化。若要检验新对象上的适用性，应先划分验证数据，缩放和分组规则在训练部分确定。常见聚类方法的分组依据07方法家族分组依据代表方法划分方法围绕中心优化目标函数K-Means、K-Medoids层次聚类逐步合并或分裂形成层次凝聚层次、分裂层次密度聚类连接密集区域并识别噪声DBSCAN、OPTICS图论方法利用邻接关系或图的结构谱聚类、最小生成树网格方法统计密集网格并连接单元STING、CLIQUE不同方法采用不同的簇概念。选择时要考虑形状、密度、距离、数据规模和解释需求。K-Means的目标函数08SSE=ΣₖΣₓ∈Cₖ‖x−μₖ‖²均值作为簇中心μₖ是簇Cₖ中样本的均值。每个样本分配到一个簇。优化的是到中心的平方距离之和。目标函数的适用范围适合较紧凑的中心型分组。异常值影响均值和平方距离。复杂形状需比较其他方法。K-Means交替更新通常收敛到局部解。不同初始化可能产生不同划分。K-Means的交替更新09设定K与初值指定簇数，选择初始中心。分配样本比较到中心的距离，分到最近的簇。更新中心对簇内样本重新计算均值。检查停止条件中心变化足够小，或达到迭代上限。分配和更新解决不同问题中心固定时，最近中心分配不会增加SSE。分配固定时，用簇内均值作为中心也不会增加SSE。实际实现还需处理空簇与数值容差。比较距离时可直接比较平方距离，省略开平方不会改变最近中心的判断。教材的8个二维样本10样本x₁x₂P112P223P334P487P578P696P743P865设K=2，固定初始中心μ₁=(1,2)、μ₂=(8,7)。以下表格、散点图和代码均使用这组初值。第一轮分配：比较平方距离11样本坐标到(1,2)的d²到(8,7)的d²分配(1,2)074簇1(2,3)252簇1(3,4)834簇1(8,7)740簇2(7,8)722簇2(9,6)802簇2(4,3)1032簇1(6,5)348簇2例如P₈=(6,5)，到两个中心的平方距离分别为34和8，因此分入簇2。第一轮SSE为32。更新均值与下一轮分配12簇1的新中心样本为(1,2)、(2,3)、(3,4)、(4,3)。μ₁=((1+2+3+4)/4,(2+3+4+3)/4)=(2.5,3)。簇2的新中心样本为(8,7)、(7,8)、(9,6)、(6,5)。μ₂=((8+7+9+6)/4,(7+8+6+5)/4)=(7.5,6.5)。用新中心再次分配，8个样本的簇归属不变。中心随之保持不变，SSE从32下降到17。收敛结果与簇中心13样本点与簇中心蓝、橙圆点表示两个簇。深蓝菱形表示中心。μ₁=(2.5,3)。μ₂=(7.5,6.5)。中心不一定是实际样本。本例SSE=17。簇编号可以互换，划分本身不变。这个小例子用于说明步骤，不能据此断言所有数据都适合K=2。图6-3聚类算法迭代过程示意图例6.1：用NumPy复现手算14importnumpyasnpX=np.array([(1,2),(2,3),(3,4),(8,7),(7,8),(9,6),(4,3),(6,5)],float)centers=np.array([(1,2),(8,7)],float)for_inrange(100):d2=((X[:,None]-centers[None,:])**2).sum(2)labels=d2.argmin(1)new=np.array([X[labels==j].mean(0)forjinrange(2)])ifnp.allclose(new,centers):breakcenters=new代码中的两个更新argmin对应最近中心分配。mean对应簇中心更新。本例每一簇都有样本。一般实现还应检查空簇。用最终中心再次分配。这一固定初值示例可直接复现前面的分组。实际应用可比较多组初值，并设置收敛容差和迭代上限。K-Means的初始化与扩展15方法主要变化K-Means++按到已有中心的最短距离的平方，加权选择新中心多次初始化重复运行，比较最终SSE，如显式设置n_init=10K-Medoids中心选择实际样本，最小化所用距离之和Mini-BatchK-Means用小批量样本更新中心，降低大样本计算成本Elkan方法利用三角不等式的距离上下界减少重复计算模糊C均值以隶属度描述一个样本对不同簇的归属K-Means++更倾向于选择远离已有中心的点，其选择权重与距离平方成正比。它仍不保证全局最优。层次聚类的两种方向16凝聚：自底向上开始时每个样本自成一簇。根据链接准则，每次合并最接近的两个簇。保留合并顺序和对应的高度。分裂：自顶向下开始时所有样本属于一个簇。选择要继续拆分的簇，用选定方法进行二分或多分。达到簇数或其他停止条件后结束。层次结构可以保留多个尺度的分组。最终需要通过簇数、截断高度或其他准则选择一个划分。图6-4层次聚类算法流程示意图凝聚聚类的链接准则17准则两个簇之间如何比较需要注意single跨簇样本对的最小距离可能出现链式连接complete跨簇样本对的最大距离受较远样本对影响average跨簇全部样本对的平均距离需要使用完整的跨簇平均ward比较合并引起的簇内平方和增量要求欧氏特征空间链接准则改变合并顺序。Ward不是把任意距离矩阵直接取平均，不能与其他链接准则混为一谈。例6.2：原始距离矩阵18对象ABCDA02.53.07.0B2.502.06.5C3.02.005.0D7.06.55.00先找非对角最小值d(B,C)=2.0。因此先合并{B}与{C}。d(A,B)=2.5，并不是本矩阵的最小距离。本例以下采用single链接。距离矩阵是对象之间的差异，不把它的每一行直接当作原始特征。单链接更新：合并B与C之后19簇{A}{B,C}{D}{A}02.57.0{B,C}2.505.0{D}7.05.00更新新簇到其他簇的距离d({B,C},A)=min(2.5,3.0)=2.5。d({B,C},D)=min(6.5,5.0)=5.0。合并高度依次为2.0、2.5、5.0。每一步都根据相同的链接准则更新，不能保留已删除对象的错误索引。单链接合并过程的树状图20ABCD2.02.55.0截断高度为3橙线位于2.5与5之间。得到两个簇：{A,B,C}与{D}。树状图的高度表示链接值，横向排列只用于展示对象。同一棵树可以在不同高度截断。比较链接方法时，也要说明距离、缩放方式和最终簇数。例6.2：由预计算距离生成层次结构21fromscipy.spatial.distanceimportsquareformfromscipy.cluster.hierarchyimport(linkage,dendrogram,fcluster)#D为例6.2的原始4×4距离矩阵condensed=squareform(D,checks=True)Z=linkage(condensed,method='single')labels=fcluster(Z,t=3,criterion='distance')dendrogram(Z,labels=['A','B','C','D'])输入形式需要对应squareform得到压缩距离向量。linkage据此执行合并。若传入二维特征矩阵，函数会重新计算样本距离。两种输入含义不同。D需对称且对角为0。运行使用SciPy，绘图另需matplotlib。分裂层次聚类的二分过程22整体作为一簇先保留所有对象，记录原始行索引。选择待分裂簇例如选择当前SSE最大的簇。进行二分在该簇内运行K-Means等方法。更新并停止更新索引集合，达到目标簇数停止。行索引与局部标签局部模型的0、1标签只表示这一次二分的结果。更新簇成员时，应把局部结果映射回原始样本索引，不能把标签数值追加为样本。分裂方法和选择待分裂簇的准则共同决定结果。单点簇不能再进行有意义的二分。例6.3：用二分K-Means实现分裂23fromsklearn.clusterimportBisectingKMeansX_div=np.array([(2.5,3),(0,2),(3,5),(7,6.5)],float)model=BisectingKMeans(n_clusters=3,random_state=0,n_init=10,bisecting_strategy='biggest_inertia')labels=model.fit_predict(X_div)print(labels)print(model.cluster_centers_)分裂策略每轮选SSE最大的簇，再进行二分。目标簇数设为3。用labels查询样本归属。保持原始坐标含义。BisectingKMeans是分裂层次聚类的一种具体实现。原示例坐标与原距离矩阵不是同一份表示，使用时需要分开说明。DBSCAN的邻域与三种样本状态24概念判断依据eps邻域与当前样本距离不超过eps的样本集合核心点邻域内样本数达到min_samples边界点不是核心点，但位于某核心点的eps邻域中噪声点不能连接到任何核心点形成的簇本课按scikit-learn约定计数，min_samples包含样本自身。eps不是整个簇的最大直径。DBSCAN手算：6个样本的邻域25点坐标邻域点数（含自身）状态A(1,2)3核心点B(2,2)3核心点C(2,3)3核心点D(8,8)2核心点E(8,9)2核心点F(25,80)1噪声点设min_samples=2。A、B、C两两距离不超过2，D、E互相邻接，F只有自身。得到2个簇和1个噪声点。同一密度聚类结果的全图与局部26全范围：包含F=(25,80)主体局部：A至E灰色点F为噪声，局部图未显示F。蓝色为{A,B,C}，橙色为{D,E}。本例没有边界点。DBSCAN通过核心点扩展簇27检查邻域访问样本并统计eps邻域内的点。从核心点出发邻域点数达标，开始或继续扩展。连接密集区域沿核心点继续搜索，吸收邻接边界点。保留噪声标记扩展结束后，其余点记为−1。边界点与噪声的处理边界点可以加入簇，但它自身不能像核心点那样继续扩展。某个点最初未达核心条件，后续仍可能成为其他核心点的边界点。不同密度区域和高维距离会影响DBSCAN的效果。噪声是算法在当前参数下的输出，不能直接等同于实际故障。标准化后，邻域半径的含义改变28输入空间eps簇数噪声数原坐标2.021Z-score标准化2.011Z-score标准化0.321为什么会合并标准化后，A至E两两距离均小于0.9，eps=2会将它们连成一簇。本例改为eps=0.3时得到两个簇，半径应根据标准化后的距离重新选择。这里使用总体标准差的Z-score，与StandardScaler的缩放口径一致。表中结果由邻域与核心连通关系逐点核算。例6.4：明确使用哪一个距离空间29fromsklearn.clusterimportDBSCANfromsklearn.preprocessingimportStandardScalerX_db=np.array([(1,2),(2,2),(2,3),(8,8),(8,9),(25,80)],float)Z_db=StandardScaler().fit_transform(X_db)model=DBSCAN(eps=0.3,min_samples=2)labels=model.fit_predict(Z_db)core=model.core_sample_indices_print(labels,core)标签与坐标分别处理用Z_db进行模型拟合。labels与原始行顺序一致。绘图可使用原坐标X_db，沿用同一行的标签。core保存核心点行索引。这组eps只用于6点教学例子。实际数据应先检查距离尺度，再选择eps和min_samples。k-distance曲线与eps候选范围30本图的邻居计数约定30个模拟二维样本。将每点的第5邻居距离排序。计入自身的零距离，等价于第4个其他样本距离。曲线转折用于提出eps候选。k-distance转折不保证唯一的最佳半径。还需查看簇数、噪声比例、稳定性和应用含义。OPTICS与HDBSCAN的扩展思路31方法主要思路仍需关注的设置DBSCAN按给定半径扩展密集区域eps、min_samplesOPTICS保留密度连接的排序与可达距离min_samples、max_eps、提取方式HDBSCAN构建密度层次并选择稳定簇min_cluster_size、min_samples等参数与密度变化这些扩展提供观察多种密度尺度的方法，但仍然依赖距离、缩放和参数。比较结果时，同步报告噪声比例以及保留下来的簇大小。OPTICS常用max_eps限制搜索尺度。HDBSCAN也需要选择最小簇大小，不能视为完全不需要调参。图论聚类中的数据表示32构造节点每个对象对应一个节点。建立邻接关系按近邻、距离或相似度连接节点。利用图结构观察图的谱，或构建生成树。形成分组得到节点簇，映射回原始对象。边权的含义决定后续处理相似度越大通常表示越相近，距离越大通常表示越不相近。谱聚类与距离最小生成树采用的边权含义不同，构图时应明确说明。图过稀疏可能出现多个不连通分量，过稠密又可能掩盖局部结构。邻接参数也是模型的一部分。谱聚类的相似图与拉普拉斯矩阵331234相似度1相似度0.1相似度1构造矩阵W表示非负相似度。D的对角元素为各节点的加权度。非归一化拉普拉斯：L=D−W。在谱空间中分组对选定拉普拉斯矩阵求特征向量。形成嵌入后，执行K-Means等分组。特征向量选择依具体归一化方案确定。图为教学构造的四节点相似图。不要把所有谱聚类都写成必须剔除零特征值对应向量。非球形数据：双环的分组示例34原坐标中的K-Means6近邻图的归一化谱聚类双环为80点模拟数据。左图比较20组初始中心，右图按归一化谱嵌入计算；近邻图有两个连通分量。例6.5：谱聚类的核心调用35fromsklearn.datasetsimportmake_blobsfromsklearn.clusterimportSpectralClusteringX_sp,y_sp=make_blobs(n_samples=300,centers=2,cluster_std=0.60,random_state=0)model=SpectralClustering(n_clusters=2,affinity='nearest_neighbors',n_neighbors=10,assign_labels='kmeans',n_init=10,random_state=0)labels=model.fit_predict(X_sp)邻接图也需要检查n_neighbors控制近邻图。图的连通结构会影响结果。y_sp用于外部评价，不参与模型拟合。调整图参数后复核划分。上一页双环结果采用NumPy计算的教学实现，本页展示教材模拟数据的scikit-learn接口，两份数据需分开说明。最小生成树聚类的距离边权36计算距离用距离表示连接两个点的代价。构建MST连接全部对象，使树的总边权最小。剪去长边按阈值或目标簇数删除选定的边。计算连通分量每个剩余连通分量对应一个簇。距离与相似度的方向最小生成树最小化边权总和。若直接把“越大越相近”的高斯相似度作为代价，就会偏向较小的相似度。教学例子采用欧氏距离，剪去较长的连接。若需要保留高相似度连接，应采用匹配的转换或最大生成树方案，并重新解释剪边准则。六点示例：剪去连接两群的长边37本例的5条树边4条短边长度均为1。连接两群的长边约为7.07。以距离3为阈值剪边，剩余两个连通分量。蓝、橙色表示剪边后分组。该六点数据用于说明MST剪边，与例6.6的300点模拟数据不同。灰色长边是本例被剪去的连接。例6.6：按距离构建并剪切MST38fromscipy.spatial.distanceimportcdistfromscipy.sparse.csgraphimport(minimum_spanning_tree,connected_components)X_mst,_=make_blobs(n_samples=300,centers=3,cluster_std=0.60,random_state=0)D_mst=cdist(X_mst,X_mst)threshold=1.0#教学候选，需按树边长度核对tree=minimum_spanning_tree(D_mst)tree.data[tree.data>threshold]=0tree.eliminate_zeros()n_groups,labels=connected_components(tree,directed=False)阈值与距离口径对应以距离1.0作为教学候选。需按树边长度重新核对。树的存储可能只有单向边，连通分量按无向图计算。检查重复坐标与零距离。运行需要SciPy和scikit-learn。距离阈值1.0是教学候选，运行后查看簇数和边长分布，再比较其他设置。网格聚类：先统计单元，再连接39行/列12345145000256100301001400054500046本例的密集单元假设单元计数达到4即密集。按上下左右相邻连接。左上与右下形成两个区域。稀疏单元不连接这两个区域。网格分辨率会改变结果。表中计数是教学构造。网格化仍需读取样本并计算其所属单元，不能把全部计算量说成与样本数无关。STING与CLIQUE40比较项STINGCLIQUE组织结构多分辨率的层次网格不同特征子空间中的网格使用的信息单元内计数、均值和方差等统计单元密度与子空间关系处理过程利用统计摘要逐层筛选相关区域寻找密集子空间单元并连接主要设置网格层次、分辨率及筛选准则区间划分和密度阈值高维网格数可能迅速增长。方法效率既与网格设计有关，也包括样本分配和统计摘要的构建成本。聚类趋势与Hopkins统计量41H=Σᵢuᵢᵈ/(Σᵢuᵢᵈ+Σᵢwᵢᵈ)，d为特征维数两类最近邻距离w：抽取真实样本，计算到其他真实样本的最近邻距离。u：在参考空间均匀生成随机点，计算到真实数据的最近邻距离。本页定义下的解释接近0.5：接近随机空间分布。较大：提示可能存在聚集趋势。明确参考空间、距离和指数约定。重复抽样，报告结果的变化。Hopkins不直接给出最佳簇数。高维边界、相关特征和参考空间选择都会影响解释，不用单一阈值代替全部判断。簇数选择：SSE与肘部图42本例曲线的变化K=1时，SSE=91.5。K=2时，SSE=17。继续增大K，SSE仍然下降。不只按最小SSE选簇数。需结合拐点和解释需求。曲线对8点所有划分穷举，展示各K的最小SSE，不代表某一次随机初始化的输出。肘部位置可能不清楚。轮廓系数：簇内与最近其他簇43s(i)=[b(i)−a(i)]/max{a(i),b(i)}两个平均距离a(i)：本簇其他样本的平均距离。b(i)：到每个其他簇的平均距离，取其中最小值。单点簇的轮廓值通常记为0。取值与使用条件接近1：相对紧密且分离。接近0：位于分组边界附近。负值：可能更接近其他簇。本章8点的平均值约0.615。按欧氏距离计算，要求2≤簇数≤样本数−1。轮廓系数偏好紧凑的凸形簇，解释密度簇时需谨慎。内在指标与簇数选择44指标或方法判断依据一般比较方向SSE簇内到中心的平方距离之和固定K时较小，跨K看变化轮廓系数簇内与最近其他簇的平均距离通常较大更好Calinski-Harabasz簇间离散与簇内离散的相对比值通常较大更好Davies-Bouldin簇内分散与中心间隔的组合通常较小更好AIC/BIC概率模型的拟合和复杂度仅对适用的概率模型比较在相同特征空间和距离口径下比较。AIC/BIC常用于高斯混合等概率模型，不是任意K-Means结果的通用评分。外在指标不要求簇编号一致45样本参考标签聚类标签102202310410分组相同，编号不同两个划分都将1、2分为一组，将3、4分为另一组。调整兰德指数ARI=1。归一化互信息NMI=1。直接比较标签数值会误判。ARI校正随机一致性，可能为负。NMI比较分组共享的信息。参考标签参与评价，并不表示聚类时使用了标签。含噪声聚类的评价口径46fromsklearn.metricsimportsilhouette_scoremask=labels!=-1kept=X_scaled[mask]groups=labels[mask]k=len(np.unique(groups))if2<=k<len(kept):score=silhouette_score(kept,groups)else:score=np.nannoise_ratio=np.mean(labels==-1)print(score,noise_ratio)同步报告保留比例排除噪声后再计算轮廓。报告噪声比例与簇大小。仅剩1簇时不计算轮廓。排除难分样本可能提分，需同时检查整体效果。这里X_scaled表示实际拟合所用的特征空间。若采用其他距离，需要在评分中保持对应口径。聚类结果的解释与稳定性47描述簇画像回到原始单位，比较均值与中位数。检查簇规模报告每簇样本数，查看极小簇和噪声。比较重复结果更换初值或抽样，观察分组变化。结合应用复核检查命名是否合理，在新数据中验证。画像需要与整体基线比较“高消费簇”应说明它相对哪个总体、哪些指标偏高，以及组内差异有多大。二维降维图用于辅助观察，不能替代原特征空间中的分离度和稳定性检查。簇间ARI可用于比较两个分组的一致性。评价稳定性时，先保证比较的是同一批对象。聚类之后的簇内关联规则48按对象分群用客户特征得到客户簇。关联到事务将该簇客户连接到购物篮。簇内挖掘规则以簇内事务重新计算支持度。与整体比较比较基线与样本数，复核规则差异。簇内支持度的分母同一规则在不同簇中，支持度和置信度可能不同。应明确统计单位是客户还是购物篮，并用该单位重新计数，避免把不同分母混在一起。患者分群后的症状与用药共现只能用于提出研究问题，不能由共现推断药物疗效或因果关系。本章方法选择小结49主要问题可先比较的方法关键核对项中心型分组K-Means、二分K-MeansK、缩放、初始化与异常值希望保留层次凝聚或分裂层次聚类距离、链接与截断方式识别密集区域与噪声DBSCAN、OPTICS、HDBSCAN密度尺度、噪声比例、簇大小复杂连接结构谱聚类、MST聚类邻接图、边权含义与参数网格或子空间结构STING