无监督学习聚类算法详解前言无监督学习是机器学习的重要分支之一与有监督学习不同它不需要标签数据而是从数据本身发现结构和模式。本文将详细讲解无监督学习中的核心算法——聚类并深入探讨它们的数学原理和实现细节。符号说明为方便阅读本文统一使用以下符号x样本点C聚类中心k聚类数量d(·,·)距离度量N样本总数n特征维度||·||L2范数欧几里得范数μ均值向量一、有监督与无监督的区别1.1 核心差异有监督学习需要标签数据输入x和输出y目标是学习从输入到输出的映射例如分类、回归无监督学习不需要标签数据只有输入x目标是发现数据中的结构和模式例如聚类、降维1.2 聚类的本质聚类是将相似的样本归为一组使得组内相似度高组间相似度低。核心问题包括如何定义相似度如何评估聚类质量如何确定聚类数量二、数据间相似度度量2.1 余弦相似度余弦相似度Cosine Similarity是衡量两个向量在方向上相似程度的指标通过计算两个向量夹角的余弦值来评估它们的相似性。核心思想两个向量的夹角越小余弦值越大说明它们越相似余弦相似度只关注向量的方向不考虑向量的长度这使得它特别适合文本相似度计算因为文档长度不会影响相似度公式cos(x, y) (x·y) / (||x|| * ||y||)其中x·y向量x和y的点积内积||x||向量x的长度L2范数||y||向量y的长度L2范数特点取值范围[-1, 1]1表示方向完全相同夹角为0°-1表示方向完全相反夹角为180°0表示正交夹角为90°不相关应用场景文本相似度计算将文本转换为词向量后计算相似度推荐系统计算用户偏好和物品特征的相似度信息检索计算查询词和文档的相似度修正余弦相似度修正余弦相似度用于解决用户评分偏置问题常用于推荐系统。问题背景在推荐系统中不同用户的评分标准不同有的用户评分普遍偏高有的偏低这种偏置会影响余弦相似度的计算修正方法对每个向量减去其均值然后计算余弦相似度。x_i x_i - μ_x y_i y_i - μ_y 修正余弦相似度 (x·y) / (||x|| * ||y||)其中μ_x向量x的均值μ_y向量y的均值x’、y’减去均值后的修正向量2.2 Jaccard相似系数Jaccard相似系数Jaccard Similarity Coefficient用于衡量两个集合的相似度定义为两个集合的交集大小与并集大小的比值。核心思想Jaccard相似系数关注两个集合的交集占并集的比例不考虑集合的大小只考虑共同元素的比例适合处理稀疏数据如文本数据公式J(A, B) |A ∩ B| / |A ∪ B|应用场景文本相似度基于词集忽略词频推荐系统用户兴趣相似度图像相似度基于特征集合推荐系统中的物品相似度计算与余弦相似度的区别Jaccard相似度用于集合余弦相似度用于向量Jaccard相似度忽略元素频率余弦相似度考虑元素频率对于二值向量Jaccard相似度和余弦相似度有对应关系三、文本相似度评估3.1 TF-IDFTF-IDFTerm Frequency-Inverse Document Frequency是文本挖掘中的重要技术用于衡量一个词在文档中的重要性。核心思想如果一个词在文档中出现频率高TF高说明这个词对文档很重要如果一个词在所有文档中都出现IDF低说明这个词是通用词区分度低TF-IDF结合了TF和IDF既考虑了词在文档中的重要性又考虑了词在语料库中的普遍性TFTerm Frequency词频衡量词t在文档d中出现的频率。TF(t, d) 词t在文档d中出现的次数 / 文档d的总词数IDFInverse Document Frequency逆文档频率衡量词t在整个语料库中的稀有程度。词越稀有IDF值越大。IDF(t) log(文档总数 / 包含词t的文档数)TF-IDFTF-IDF值越大说明词t对文档d越重要。TF-IDF(t, d) TF(t, d) * IDF(t)DFDocument Frequency文档频率衡量词t在语料库中出现的文档数量。DF(t) 包含词t的文档数应用场景文本相似度计算搜索引擎排序文本分类关键词提取3.2 Precision和Recall在聚类评估中precision和recall用于衡量聚类质量。需要注意的是Precision/Recall本质是分类任务的指标在聚类中应用时需要先将聚类结果与真实标签匹配。重要前提聚类中使用Precision/Recall需要先将聚类结果与真实标签匹配如通过匈牙利算法映射簇标签与真实标签否则无法直接计算TP/FP/FN。这是因为K-means等算法生成的簇编号是随机的无法直接与真实标签对比。Precision精确率衡量预测为正类的样本中真正为正类的比例。Precision TP / (TP FP)Recall召回率衡量真正为正类的样本中被正确预测的比例。Recall TP / (TP FN)其中TPTrue Positive正确归类的样本数FPFalse Positive错误归类的样本数FNFalse Negative应该归类但未归类的样本数四、K-means聚类算法4.1 K-means基本原理K-meansK-均值聚类是最经典的聚类算法之一属于划分聚类方法。其核心思想是将n个样本分成k个簇使得每个样本到所属簇中心的距离最小。核心思想K-means通过迭代优化将数据分成K个簇每个簇由一个中心点centroid代表中心点是簇内所有样本的均值目标是使所有样本到其所属簇中心的距离平方和最小K代表簇的数量means代表使用均值作为簇中心算法流程初始化随机选择k个样本作为初始聚类中心分配将每个样本分配到最近的聚类中心使用欧几里得距离更新重新计算每个簇的中心簇内所有样本的均值迭代重复步骤2-3直到满足终止条件如中心点不再变化或达到最大迭代次数终止条件簇中心不再发生变化变化小于某个阈值达到最大迭代次数优点算法简单易于实现时间复杂度较低O(nkt)n为样本数k为簇数t为迭代次数适合大规模数据集可解释性强缺点需要预先指定簇数K对初始中心敏感可能陷入局部最优对噪声和异常值敏感假设簇是凸形的不适合非凸形状的簇对不同尺度的特征敏感需要先进行归一化4.2 损失函数K-means的损失函数也称为目标函数或误差平方和SSE衡量了聚类质量的好坏。损失函数越小说明聚类效果越好。公式J Σ_{i1}^k Σ_{x∈C_i} ||x - μ_i||²其中C_i第i个簇Cluster包含所有分配到该簇的样本μ_i第i个簇的中心Centroid是簇内所有样本的均值||x - μ_i||²样本x到中心μ_i的距离平方k簇的总数J总损失所有簇内距离平方和损失函数的特点非凸函数可能存在多个局部最优解随着K的增加损失函数单调递减当KN样本数时损失函数为0每个样本自己成为一个簇4.3 K值选择选择合适的K值是K-means的关键问题。K值过小会导致不同簇被合并K值过大会导致一个簇被分裂。常用方法肘部法则Elbow Method绘制损失函数随K值变化的曲线随着K增加损失函数下降速度会逐渐变缓选择曲线拐点“肘部”处的K值拐点表示增加K带来的收益开始递减4.4 二分K-meansBisecting K-means二分K-means是K-means的改进版本属于层次聚类方法。其核心思想是自顶向下地分裂簇每次选择一个簇进行二分。核心思想采用自顶向下的策略从包含所有样本的簇开始每次选择一个簇进行二分使用K-meansk2重复二分过程直到达到目标簇数二分指的是每次将一个簇分成两个子簇算法流程将所有样本作为一个簇选择当前最大的簇或SSE最大的簇进行二分使用K-meansk2将该簇分成两个子簇重复步骤2-3直到达到目标簇数选择分裂簇的策略选择样本数最多的簇选择SSE最大的簇簇内距离平方和最大选择直径最大的簇优点不需要随机初始化结果更稳定计算效率高每次只处理一个簇可以构建层次结构便于理解对初始中心不敏感缺点一旦分裂无法回溯可能不是全局最优解计算复杂度仍较高4.5 K-meansK-means是对K-means初始化的改进核心思想是让初始聚类中心尽可能分散避免陷入局部最优。核心思想K-means对初始中心敏感不同的初始中心可能导致不同的聚类结果K-means通过概率选择初始中心使初始中心尽可能分散分散的初始中心可以减少迭代次数提高聚类质量算法流程随机选择第一个中心从样本中均匀随机选择对于每个未选中的样本计算到最近中心的距离按距离比例随机选择下一个中心距离越远被选中的概率越大重复步骤2-3直到选出k个中心执行标准K-means算法选择下一个中心的概率P(x) d(x)² / Σ_{y∈X} d(y)²其中d(x)是样本x到最近中心的距离X是所有未选中的样本集合优点初始化更合理初始中心分散收敛速度更快迭代次数更少聚类效果更好更接近全局最优理论上有保证期望损失是O(log k)倍的最优解缺点初始化时间复杂度较高O(nkd)n为样本数k为簇数d为特征维度对于大规模数据集初始化可能较慢优化建议在大规模数据中可通过采样降低初始化成本先从数据中随机采样一部分样本进行初始化再用全部数据聚类4.6 Mini-batch K-meansMini-batch K-means是K-means的变体适用于大规模数据集。其核心思想是使用小批量数据更新中心而不是使用全部数据。核心思想传统K-means每次迭代需要计算所有样本到中心的距离计算量大Mini-batch K-means每次只使用一小部分样本mini-batch更新中心通过多次迭代逐渐逼近最优解类似于随机梯度下降的思想算法流程随机选择小批量数据batch_size通常为100-1000计算每个样本到中心的距离将样本分配到最近的簇更新所属簇的中心使用增量更新重复步骤1-4直到收敛中心更新公式μ_new μ_old η(x - μ_old)其中η是学习率通常取1/nn是簇中已处理的样本数x是新加入簇的样本优点计算效率高适合大规模数据集内存占用小不需要存储所有样本适合在线学习可以处理流式数据收敛速度快缺点聚类质量可能略低于标准K-means对batch size敏感可能需要更多迭代次数才能收敛4.7 Canopy聚类Canopy聚类是一种快速的预聚类方法常用于K-means的初始化或作为独立的聚类算法。其核心思想是使用宽松的距离阈值快速将数据分成多个canopy覆盖区域。核心思想使用两个距离阈值T1和T2T1 T2T1是宽松阈值T2是严格阈值快速将数据分成多个canopy每个canopy可能重叠每个canopy作为K-means的初始簇减少K-means的计算量“Canopy原意是树冠”形象地表示覆盖数据的区域算法流程初始化将所有样本放入候选集未分配样本集从候选集中随机选择一个样本作为第一个canopy的中心计算该中心到候选集中所有未分配样本的距离将距离小于T1的样本加入该canopy这些样本可以属于多个canopy将距离小于T2的样本从候选集中移除这些样本不再作为其他canopy的中心重复步骤2-5直到候选集为空终止条件重要说明未分配样本指仍在候选集中的样本即尚未被任何canopy移除的样本初始时所有样本都是未分配状态都在候选集中样本可以属于多个canopy只要距离小于T1但只能作为一次中心当候选集为空时所有样本都已被移除算法终止两个阈值的作用T1宽松阈值确定样本是否属于当前canopyT2严格阈值确定样本是否可以作为其他canopy的中心T1 T2确保canopy之间有重叠避免样本被遗漏优点计算速度快不需要计算所有样本间的距离减少距离计算次数加速K-means收敛适合大规模数据对初始中心不敏感可以处理非凸形状的簇缺点聚类结果依赖于阈值T1和T2的选择Canopy之间可能重叠不是最优聚类通常作为预聚类方法五、聚类评估方法5.1 有标签情况下的评估当有真实标签时可以使用以下指标评估聚类质量准确率Accuracy衡量聚类结果与真实标签的一致性需要解决聚类标签与真实标签的对应关系公式Accuracy (TP TN) / (TP TN FP FN)重要说明聚类中Accuracy的计算需解决簇标签与真实标签的一一映射问题如K-means的簇编号是随机的无法直接与真实标签对比需明确这一前提否则公式无实际意义。常用的解决方法包括匈牙利算法或贪心匹配。精确率Precision衡量预测为正类的样本中真正为正类的比例也称为查准率公式Precision TP / (TP FP)召回率Recall衡量真正为正类的样本中被正确预测的比例也称为查全率公式Recall TP / (TP FN)F1分数精确率和召回率的调和平均综合考虑精确率和召回率公式F1 2 * (Precision * Recall) / (Precision Recall)调整兰德指数Adjusted Rand Index, ARI衡量两个聚类结果的相似度取值范围[-1, 1]1表示完全一致调整了随机情况下的期望值使其在随机情况下接近0公式ARI (RI - Expected_RI) / (Max_RI - Expected_RI)5.2 非给定标签情况下的评估当没有真实标签时可以使用以下指标评估聚类质量轮廓系数Silhouette Coefficient衡量样本与所属簇的紧密度和与其他簇的分离度取值范围[-1, 1]值越大聚类效果越好计算每个样本的轮廓系数然后取平均值公式s(i) (b(i) - a(i)) / max(a(i), b(i))5.3 互信息评估法互信息衡量两个聚类结果的一致性公式为MI(U, V) Σ_{u∈U} Σ_{v∈V} |u ∩ v| / N * log(|u ∩ v| * N / (|u| * |v|))其中U, V两个聚类结果u, v簇N样本总数归一化互信息NMINMI(U, V) MI(U, V) / √(H(U) * H(V))其中H(U)和H(V)是熵。六、层次聚类6.1 分裂法Divisive分裂法是自顶向下的方法从包含所有样本的簇开始逐步分裂。算法流程将所有样本作为一个簇选择一个簇进行分裂重复步骤2直到达到目标簇数优点不需要预先指定簇数可以构建层次结构缺点计算复杂度高O(n³)n为样本数一旦分裂无法回溯对于大规模数据不实用6.2 凝聚法Agglomerative凝聚法是自底向上的方法从每个样本作为一个簇开始逐步合并。算法流程每个样本作为一个簇计算所有簇间距离合并距离最近的两个簇重复步骤2-3直到达到目标簇数优点不需要预先指定簇数可以构建层次结构可以通过树状图dendrogram直观展示聚类过程缺点计算复杂度高O(n³)n为样本数一旦合并无法回溯对于大规模数据不实用计算复杂度优化近邻链法Nearest Neighbor Chain可将复杂度降至O(n²)使用优先队列优化距离计算对于高维数据可以使用近似算法6.3 与K-means的比较特性K-means层次聚类需要预设簇数是否计算复杂度低高结果稳定性较低较高是否可回溯是否适用场景大规模数据小规模数据七、密度聚类7.1 DBSCANDBSCANDensity-Based Spatial Clustering of Applications with Noise是基于密度的聚类算法。核心概念ε-邻域距离样本ε以内的所有样本核心对象ε-邻域内样本数≥MinPts的样本边界点密度可达但非核心对象的样本即ε-邻域内样本数MinPts但可以通过核心对象密度可达噪声点不可密度可达的样本不属于任何簇的孤立点直接密度可达样本q在样本p的ε-邻域内密度可达存在样本链p1→p2→…→pn使得每个pi1在pi的ε-邻域内密度相连存在样本o使得p和q都从o密度可达算法流程随机选择一个未访问样本如果是核心对象创建新簇将所有密度相连的样本加入簇重复步骤1-3直到所有样本被访问参数选择方法k-距离图法计算每个样本到第k个最近邻的距离k通常取MinPts按距离从小到大排序绘制k-距离图选择拐点处的距离作为ε值拐点表示距离突然增大说明从核心区域过渡到噪声区域经验法则MinPts通常取数据维度1如2D数据取33D数据取4ε可以通过交叉验证或可视化确定启发式方法先尝试多个参数组合使用轮廓系数等评估指标选择最佳参数对于小数据集可以手动调整参数观察聚类效果优点不需要预设簇数可以发现任意形状的簇可以识别噪声点缺点对参数ε和MinPts敏感难以处理密度差异大的数据7.2 密度最大值聚类密度最大值聚类寻找密度最大的点作为簇中心。算法流程计算每个样本的密度选择密度最大的样本作为中心将密度小于阈值的样本作为噪声重复步骤2-3直到找到所有簇优点可以自动确定簇数对噪声鲁棒缺点密度计算复杂对密度阈值敏感7.3 簇中心的识别簇中心的识别方法几何中心簇内所有样本的均值密度中心密度最大的样本中心性度量到其他样本的平均距离最小八、谱聚类8.1 相似度矩阵相似度矩阵W是n×n矩阵其中W_ij表示样本i和j的相似度。常用相似度度量高斯核W_ij exp(-||x_i - x_j||² / 2σ²)k近邻W_ij 1, 如果j是i的k近邻 W_ij 0, 否则8.2 度矩阵和拉普拉斯矩阵度矩阵D对角矩阵D_ii Σ_j W_ij拉普拉斯矩阵LL D - W归一化拉普拉斯矩阵L I - D^(-1/2) * W * D^(-1/2)8.3 切图谱聚类将聚类问题转化为图划分问题目标是找到最优的切。Ratio Cut比率切min Cut(A, B) / |A| Cut(A, B) / |B|其中Cut(A, B)A和B之间的边权重和|A|A中节点的数量|B|B中节点的数量Normalized Cut归一化切min Cut(A, B) / vol(A) Cut(A, B) / vol(B)其中Cut(A, B)A和B之间的边权重和vol(A)A的度数和即A中所有节点的度之和vol(B)B的度数和Ratio Cut与Normalized Cut的区别Ratio Cut使用节点数量作为归一化因子倾向于产生大小相近的簇Normalized Cut使用度数和作为归一化因子考虑了节点的重要性在实际应用中Normalized Cut更常用算法流程构建相似度图基于样本间的相似度计算拉普拉斯矩阵L计算拉普拉斯矩阵的特征值和特征向量取前k个最小特征值对应的特征向量组成n×k矩阵对矩阵的每一行进行归一化使用K-means对归一化后的行向量进行聚类为何选择前k个特征向量拉普拉斯矩阵的特征向量对应图的连通分量前k个最小特征值对应的特征向量可以捕捉图的k个主要结构这些特征向量提供了数据的低维表示便于聚类优点可以发现非凸形状的簇对初始化不敏感理论基础扎实缺点计算复杂度高O(n³)n为样本数需要选择特征向量数量对相似度矩阵的构建敏感九、总结聚类算法各有特点选择时需考虑数据规模大规模数据用K-means小规模数据用层次聚类簇形状球状簇用K-means任意形状用DBSCAN或谱聚类噪声情况有噪声用DBSCAN无噪声用K-means簇数已知已知簇数用K-means未知用层次聚类或DBSCAN计算资源资源有限用K-means资源充足用谱聚类