【数据挖掘学习笔记】8.聚类基础
一、聚类分析基础
什么是聚类分析？
聚类分析的作用
– 从人类认知世界的过程中衍生出分类这一重要任务
– 通过识别类别间的共同点与差异性来进行分类
– 识别能够清晰界定各类别之间界限的关键特征
典型应用
– Marketing
– 图像处理
– 生物学
– 交通
– 房地产
- 分析内容主题
- 识别群体
- 发现行为模式
无指导 的学习：没有预定义的类编号
聚类分析的主要功能是进行数据挖掘。
它能够独立地揭示数据的整体分布特征。
为特征提取和分类任务提供必要的前期准备。
一个好的聚类分析方法会产生高质量的聚类
– 高类内相似度
– 低类间相似度
聚类分析研究的主要基础是基于距离度量的方法；
生成高质量聚类结果的关键因素在于所采用的具体聚类方法。
具体而言，
采用特定相似性测度以及详细实施步骤是影响最终分类质量的重要因素。
此外，
该方法具备挖掘潜在数据模式的能力。
聚类要求
– 可扩展性(Scalability)
• 从机器学习与统计学领域中大多数聚类算法在处理数百条数据时均展现出较高的效率
– 支持多种数据类型
• 聚类算法能够有效处理数字型；二元类型；分类型/标称型；序数型以及比例标度型等多种数据类型
– 具备捕捉任意形状能力
• 虽然基于距离的聚类算法通常倾向于发现球形形状的聚类体；但现实中的许多实际场景中的聚类呈现更为复杂的形态
– 参数选择依赖领域知识较小化
• 在面对高维数据时；参数选择变得相对复杂；且难以直接依据领域知识进行判断以保证聚类质量
– 对噪声敏感性的鲁棒性
• 聚类算法对于空缺值、离群点以及数据噪声具有较强的鲁棒性
– 不受输入数据顺序的影响
• 同一数据集无论以何种顺序输入到同一算法中都会产生相似结果
– 高维空间中的数据通常较为稀疏且具有高度倾斜性
– 基于约束条件设计聚类方法时需要综合考虑其良好的聚类特性以及实际应用场景的需求
– 聚类结果应与特定语义解释及应用场景紧密结合以提高可解释性和实用性
二、聚类分析基础
基于划分策略的数据聚类问题阐述如下：
划分聚类的基本思想
– 由于各簇的形状和大小未知性较高，因而采用逐步调整的方法
– 初始阶段通常采用随机分配或基于某种准则的分配方法
– 设定一个簇的数量k后，通常会将前k个样本作为初始中心点
– 然后依次将剩下的所有对象依次分配到这k个簇中
– 分配依据一般是基于距离最近的原则进行
– 通过不断调整直至满足收敛条件
– 达到终止条件或者没有变化后停止
K-均值算法（k-means）
– 分配依据：对象到簇的代表点距离
– 簇的代表点是簇中对象的均值
k均值算法流程
1. 首先选取k个样本作为初始质心或核心点
2. 对于剩下的每个样本对象，在所有质心中找出与之距离最近的一个质心，并将其归类于该质心对应的簇中
3. 根据各簇中的样本重新计算新的质心位置
4. 重复上述步骤2和3过程直至满足收敛条件
K均值算法 关键
- K值选取
- 起始点选取
- 距离计算
K均值算法评价
– 具有良好的可扩展性, 该算法的时间复杂度为O(nkt), 其中n表示数据集规模, k代表聚类数量, t是循环次数。
– 通常收敛于局部最优解
– 缺点如下：
• 该方法仅在簇均值有定义时适用（受限于某些分类属性不具备均值定义）
• 聚类数量需提前确定
• 难以识别非凸形状的簇或大小差异显著的簇
• 容易受到异常数据的影响
k均值算法变种
– 不同的初始k个均值的选择
– 不同的簇代表点的策略
– 不同的距离计算
k众数（mode）方法
– 将众数作为替代于簇中心的一种指标
– 引入一种新的差异性测度来评估样本间的相似性
– 通过频率统计动态调整各簇的核心代表
– 将k-均值与k-众数策略相结合以处理混合类型的数据
K中心点方法
– k均值算法对离群数据表现出高度敏感性
• 极端值对象可能明显扭曲数据分布
• 平方误差函数将严重加剧这种影响
– k中心点方法基于各簇核心位置的对象来代表各簇
• 该方法能有效增强对该类对象的数据鲁棒性
k均值方法与k中心点方法比较
在数据集中存在噪声和离群数据的情况下，采用K中心点聚类算法相较于K均值算法更具稳定性，在一定程度上能更好地抵抗异常数据的影响。
受异常数据显著影响较小的情况下，在相同的参数设置下实现更好的聚类效果。
相比之下，在时间效率方面有所欠缺。
具体而言：
- K-Means算法的时间复杂度为O(nkt)
- K-Medoids算法的时间复杂度则为O(k(n-k)^2)
值得注意的是：
当数据集规模较大时（尤其是n和k都较大），采用K-Medoids算法会带来较高的计算开销。
两种聚类算法都需要用户提供预设的簇数量k
算法总结
– 设定k个预先定义的簇，并将所有对象依次分配到各个预先设定好的簇中
• 初始阶段的选择对于算法效果至关重要（涉及参数k以及初始质心的选择）
• 对象被分配到最接近的那个质心所属的簇
– 簇的核心位置由其成员数据点坐标的均值来确定
• 基于众数中心点的方法是一种有效的聚类方式
• 通过计算各簇成员数据点的均值来确定其核心位置
• 基于中心点聚类的方法也是一种常用策略
– 分组依据如下：
• 实际上等价于计算每个对象与各质心之间的距离；那么问题在于这两者是否存在实质区别？
三、层次聚类
层次聚类
– 对给定的数据集进行层次式划分
• 自底向上方法（凝聚）：从单个元素出发逐步构建数据集中的群集结构；通过连续地将具有相似特征的对象或群集不断合并直至形成单一的整体或满足特定终止条件。
• 自顶向下方法（分裂）：从所有对象的整体出发逐步分割；通过迭代地细分单个簇来实现数据集中的群集结构逐步细化直至每个对象独立成群或达到设定的细分阈值。
– 缺点：合并或分裂的步骤不能被撤销
- 凝聚层次聚类——自底向上
- 分裂层次聚类——自顶向下
– 基于贪心的思想
– 自底向上，每次找最近的合在一起
– 自顶向下，每次找最远的分开
核心问题在于如何计算距离并区分最近与最远
• 初始阶段采用的是两点之间的距离其计算过程较为简便
• 在分析中我们主要关注点与类别之间的距离
• 类别间的相互关系则通过类别之间的距离来进行衡量
• 在划分聚类时，则采用的是样本与类别中心之间距离作为度量依据。
凝聚层次聚类
– 假设有N个待聚类的样本，对于层次聚类来说，基本步骤就是：
- （初始化）在初始阶段将每个样本分类，并计算各类间距离作为样本间相似度；
- 识别各类中相互最近的两类并将其合并（从而减少类别总数一个）；
- 随后重新评估新生成类别与其他原有类别间的相似程度；
- 反复执行上述步骤直至所有数据点最终归属于同一类别并完成整个过程。
– 这一聚类过程可以看作是构建为一棵树的过程
– 在构建过程中，在第二步设定一个阈值标准后，在任意两相邻类别之间的距离超过该阈值时将迭代终止
核心研究焦点在于不同实体间相似性评估机制的设计与实现。
在机器学习领域中，
单个样本间的相似性度量是基础研究，
而类别间相似性评估则是提升聚类效果的关键环节。
其中，
Single Linkage方法学也被称为最短连接法，
它通过最小样本间距离进行评估。
与此相对应的是Complete Linkage策略，
这种策略基于最长样本间间距进行评估。
此外，
Group Average方法则采用所有样本对之间的相似度值求均值的方式
• Group Average-middle：取两两距离的中值
距离计算：
单链 优点：能处理非椭圆状聚类
单链 缺点 ：易受噪声影响
层次聚类
– 其基本特性
– 基于距离计算的方法在选择合并和分裂点时具有重要性。
– 其主要依据是否仅限于基于距离的计算？
– 是否可以通过引入其他指标（如类别大小或类别代表间的距离）来提升聚类效果？
改进方式是与其他聚类方法组合使用
扩展
– BIRCH
• 基于树状结构对数据进行分层组织，并构建细粒度群体以实现最终聚类目标
– ROCK
• 通过评估和整合各簇间的联系性来完成最终聚类过程
– Chameleon（变色龙）
• 结合各簇间的相似性和邻近度特征实现动态聚类效果
四、聚类评估
聚类评估
– 进行聚类的可行性和聚类效果的度量
聚类评估典型任务
– 估计聚类趋势
– 预估数据集中的簇数
– 测定聚类结果质量
估计聚类趋势
– 分析数据集是否存在非随机分布特征
– 检验数据集是否具备聚类能力
– 采用抽样统计方法进行分析，在此过程中可参考霍普金斯统计量作为辅助工具
预估数据集中的簇数
– 采样
– 采用特定聚类技术进行分组
– 通过特定评估标准进行测定
– 确定类别数量与评价指标的"转折点"位置
– 如Elbow technique（肘技术）
结果评估
- 有指导的校验评估
- 无指导的校验评估
有指导的校验评估
– 个体验证过程
– 精确度（精确度）Precision = TP / (TP + FP)
– 召回效率（完整性）Recall = TP / (TP + FN)
– F值
– Fowlkes-Mallows scores
1. 真实情况为真时的正确预测被称为正确肯定（True Positive, TP）。
2. 在真实情况为假时做出无误判断的情况称为正确否定（True Negative, TN）。
3. 当模型错误地将实际为假的情况判断为真的情况即为错误肯定（False Positive, FP）。
4. 将实际应视为真的情况错误判断为假的情况则被称作错误否定（False Negative, FN）。
– 基于抽样的检验
兰德系数（Rand index）
**
**
– 基于已知类别信息C的情况下设定聚类结果为K。
– 分子部分表示属性一致性指标的具体计算方法：其值等于既归属同一类别又预测正确的一致样本数量与归属不同类别且预测也不同的样本数量之和。
分母：计算任意两个样本被归为一类的组合数相当于统计数据集中所有可能形成的元素对总数
有指导的校验评估
– 调整兰德系数（Adjusted rand index）是用于衡量聚类效果的重要指标... ...
– 互信息（Mutual Information）是一种广泛应用于机器学习领域的评估指标... ...
– 调整互信息（Adjusted mutual information）是衡量两个数据分布之间相似性的度量方法之一...
– 同质性Homogeneity是一个用于评估聚类结果一致性的关键参数
– 完整性completeness是衡量聚类算法覆盖能力的重要指标
– 调和平均V-measure是一种结合精确度与召回率的综合评价指标
无指导的校验评估
– 类内对象尽可能相似
– 类间对象尽可能不同
轮廓系数 Silhouette Coefficient
– a为同一类别内其他样本与其的距离之均值
– b为该对象与其同类别中最邻近的不同类别的样本均值
– 该分类内各对象轮廓系数之均值
其他思路
– 各种统计量，比如方差