type
status
date
slug
summary
tags
category
icon
password
.png?table=block&id=1e97c1d5-a1e9-80b1-941b-e49d8bb9245d&t=1e97c1d5-a1e9-80b1-941b-e49d8bb9245d)
重点介绍了两种基于密度的聚类算法：DBSCAN和基于网格的聚类。
DBSCAN通过识别数据点密集的区域来形成具有任意形状的簇，并能有效处理噪声点，但也对参数选择和处理不同密度簇的数据敏感。
基于网格的聚类则将数据空间划分为网格单元，并基于单元密度进行聚类，强调算法的高效率，但也受网格划分和密度阈值选择的影响。讲义还详细阐述了评估聚类结果的多种方法，包括衡量簇内部紧密度和簇间分离度的无监督技术，以及与已知“真实标签”对比的有监督指标，并讨论了如何确定合适的簇数量和评估数据是否存在聚类趋势。
DBSCAN
DBSCAN 代表 Density-Based Spatial Clustering of Applications with Noise。其核心思想是，簇是高密度区域，这些区域由低密度区域相互分隔开。与K-Means寻找圆形簇不同，DBSCAN可以找到任意和复杂形状的簇，例如S形、椭圆形和半圆形。
DBSCAN 的主要思想是：如果点A在一个簇中，则其周围点的密度应高于某个阈值。为了实现这一点，我们需要定义点的密度和邻域
核心點是如何定義出來的
也就是說，它跟設置參數有關，最關鍵的就是 Eps 和 MainPts 這兩個值你是如何設定的。如果滿足這兩個設定的參數要求，那麼就會發現核心点。
- 一个点A的邻域定义为半径Eps范围内的区域。
- 一个点A的密度定义为其邻域内点的数量，包括点A本身。
- 密度阈值MinPts是指一个点在其Eps邻域内的最小点数
- MinPts：最小点数，表示这个邻域内必须有多少个点才可以构成“密集”。
点的密度取决于邻域Eps。
- 如果Eps过大，所有点都将具有与数据集中点总数m相同的密度。
- 如果Eps过小，所有点都将具有密度1
比较核心的三个点的类型：
在DBSCAN中，基于给定的Eps和MinPts，有三种类型的点：
1.核心点 (Core point)：如果一个点的Eps邻域包含至少MinPts个点。核心点位于基于密度的簇的内部。
2.边界点 (Border point)：如果它不是核心点，但落在某个核心点的邻域内。一个边界点可能落在几个核心点的邻域内。
3.噪声点 (Noise point)：如果它既不是核心点也不是边界点。
這裡其實是有七個點的，包括了A點和B點。
这个其实就是通过一个连接矩阵来寻找簇。其实就是因为你定义了 EPS 和 minPTS 这两个前提条件。
那么就只有 B 会符合条件。B 跟 A 的距离是 1，B 跟 C 的距离是 2。再加上 B 本身，它们就只有这一个是满足前面两个要求的。
所以就只有一个簇。
我觉得其实很重要的一个过程就是，如果两个核心点互相在对方的邻域里，就跟他们之间画一条边。最后就会构成一个核心点之间的邻接图。
那么最后其中，也就代表着一个连通子图等于一个簇（cluster）。
🧠 可以这么理解 DBSCAN：
角色 | 作用 |
核心点 | 是“骨架”，决定簇的存在和扩展 |
边界点 | 是“外皮”，贴着核心点但不能自己当中心扩散 |
噪声点 | 是“孤儿”，不参与任何簇 |
我在这里其实有感觉到一个点， 那么就是选取 EPS 和 minPTS 的值会变得很关键。这个值不能选得很大，也不能选得很小。
關於参数的选取方式
俗称“肘部”
这里有一个前提条件，就是k=4，然后进行排序，而得出来的这 3000 个点，图是按它们的第 4 个最近邻的距离从小到大排的。前面的点彼此很近，后面的点到它的第 4 个邻居距离很远，可能是噪声点。
这个其实就是参数选取的方法。也很简单，就是通过点与点之间的 n 次遍历，从小到大排一下，就可以得出。
缺点
這裏也體現出來了這個方法的缺點。也就是說，如果我們其實拿的是一套標準來去分簇，但在一個數據集中，有可能一個簇的密度特別大，而另外一個簇的密度相較於它來說是比較稀疏的，那麼這個時候其實就是比較難進行分簇，很可能就會分不對。
💥 全局参数（Eps 和 MinPts）不适用于局部密度差异很大的数据集！
同一个标准却用于密度不同的数据区域 → 结果误判
關於時間和空間复杂度的分析
优缺点总结
网格聚类
网格聚类（Grid-based clustering）基于密度的聚类方法，它利用网格结构来组织数据
核心思想: 网格聚类的主要思想是将数据空间划分成网格单元（grid cells），然后从密度足够高的网格单元中形成簇
工作原理：
1.定义网格单元:
◦将每个属性的值分割成多个区间，从而创建网格单元。
◦一种常见的方法是将每个属性的值分割成等宽度的区间。这种方法产生的网格单元具有相同的体积（或面积/长度，取决于维度）。
◦网格单元的密度可以定义为该单元中的点数除以其体积。对于等体积的网格单元，单元中的点数可以直接衡量其密度。例如，这可以类比为每平方公里栖息地的袋鼠数量（2D）或每立方厘米气体的分子数量（3D）。
◦也存在更复杂的方法来定义网格单元:
▪将属性值分割成包含相同数量点（等频率区间）的区间。
▪使用聚类方法来确定区间。
▪最初将属性值分割成更多数量的等宽度区间，然后合并密度相似的区间。
◦网格单元的定义对聚类结果有很大影响——不同的网格单元定义会导致不同的聚类结果。
2.识别密集单元并形成簇:
◦一旦定义了网格单元并计算了每个单元的密度，就可以根据密度阈值识别出密集单元
◦从相邻的密集单元群组中形成簇。这需要定义“相邻”的概念，例如在一个二维网格中，一个单元是否有4个或8个相邻单元。
◦位于簇边界的单元可能因为密度不够高而被丢弃，这会导致簇的部分丢失。可以通过修改算法来解决这些问题。
优点和局限性：
- 优点 - 高效:
◦给定每个属性的划分，只需对数据进行一次扫描，即可确定每个对象所属的网格单元并计算每个单元的点数（密度）。
◦定义网格、将对象分配到单元以及计算单元密度的时间和空间复杂度为 O(m)，其中 m 是点数。
◦如果可以使用搜索树高效地访问相邻单元，则整个聚类过程可以非常高效，时间复杂度为 O(m log m)。
- 局限性:
◦依赖于网格划分。
◦依赖于密度阈值 t 的选择。如果 t 过高，簇会丢失；如果 t 过低，本应分开的两个簇可能会被合并。
◦对具有不同密度的簇和噪声效果不佳。因为阈值是固定的，很难找到一个适用于数据空间所有部分的值。
◦边界单元问题。边界处的单元可能因为密度不足而被忽略。
CLIQUE algorithm
CLUQUE (CLustering In QUEst)
🧠 什么是 CLIQUE 算法？
👉 CLIQUE 是一种用来在高维数据中找“密集区域（簇）”的聚类方法。
它的核心思想就是：
“我不直接在高维空间里找簇（太复杂），而是先从低维度入手，一步步扩展维度，只关注那些真的有用的子空间。”
子空间网格聚类：CLIQUE:
- 我们研究的大多数聚类算法使用所有属性来寻找簇。然而，数据可能只在某些属性的子集中表现出良好的聚类特性，而在其余属性上随机分布。
- CLIQUE (CLustering In QUEst) 是一种维度增长的子空间网格聚类算法。
- 它从一维子空间开始聚类，并增长到更高维的子空间。它寻找存在高密度簇的最高维度的子空间。
- 与基本的网格聚类一样，一个簇是一组相邻（接触）的密集单元。
- 在每个子空间中，数据被分割成矩形单元，并根据阈值识别出密集单元。
- 为了高效地在 k 维子空间中找到密集单元，CLIQUE 使用了关联规则挖掘中的 Apriori 特性（单调性原理）
- Apriori 原理: 如果一组点在 k 维空间中形成一个基于密度的簇，那么这组相同的点也属于这些维度所有可能的子集中的基于密度的簇。因此，如果一个 k 维单元是密集的，那么它在 (k-1) 维空间中的投影也是密集的。反之，如果一个 (k-1) 维单元不是密集的，那么其 k 维单元也不是密集的。
- CLIQUE 利用这一原理：为了生成 k 维空间中的候选密集单元，只需考虑 (k-1) 维空间中的密集单元即可。这减少了搜索空间。
- 与所有网格聚类算法一样，CLIQUE 的结果质量取决于参数选择（网格单元的数量和宽度以及密度阈值）。由于阈值是固定的，它对具有不同密度的簇效果不佳。
Apriori (monotonicity) principle
Apriori 原则（也称为单调性原则）
🧠 一句话通俗解释：
如果某个“高维区域”很密集，那它在“低维投影”里也一定很密集；反过来，如果低维就不密集，那再加维度也不会变密。
评估聚类结果
聚类算法即使在随机数据中也会找到簇。因此，评估聚类结果的质量非常重要，以确保不是在噪声中寻找模式。聚类结果的评估可以分为两种主要方法：
- 使用无监督度量评估聚类质量: 这些度量不使用外部信息（如真实标签），也称为内部度量。目标是评估簇内部的高相似性和簇之间的高分离性。
- 方法 1: 度量内聚性和分离性: 内聚性度量簇内点的相似性，分离性度量簇之间点的相似性。可以使用距离度量来计算。例如，SSE（簇内平方误差）和 BSE（簇间平方误差）可以用于度量。轮廓系数 (Silhouette coefficient) 结合了内聚性和分离性，用于评估单个点、簇或整个聚类的质量。轮廓系数的值介于 -1 和 1 之间，值越高越好。
- 方法 2: 评估两个相似度矩阵之间的相关性: 一个相似度矩阵来源于距离矩阵，另一个来源于聚类结果（同一簇中的点相似度为 1，不同簇中的点相似度为 0）。高相关性表明良好的聚类。
- 方法 3: 通过可视化检查排序的相似度矩阵: 根据簇对点进行排序，并绘制相似度矩阵。沿主对角线清晰定义的块表示良好的聚类。
- 使用有监督度量评估聚类质量: 这些度量使用外部信息，例如专家提供的真实簇标签（地面真值），也称为外部度量。目标是度量获得的聚类结果与地面真值之间的差异。
- 方法 1: 基于分类的度量: 例如，熵和纯度。它们度量每个簇相对于其真实类标签的同质性。熵越小，纯度越高，聚类质量越好。也可以使用准确率、精确率、召回率和 F1 度量。
- 方法 2: 基于相似度的度量: 例如，计算获得的簇相似度矩阵与理想簇相似度矩阵之间的相关性。由于这些矩阵是二进制的，也可以计算其他度量，如简单匹配系数 (Simple Matching Coefficient, SMC)，也称为兰德统计量 (Rand statistic)，或 Jaccard 系数。
cohesion 冲突 内聚度
✅ 总结：
这张图就是要说明：
Cohesion = 所有点到中心的距离总和，用来评价一个簇的内部紧密度。
它演示了如何在一维空间中（使用 Manhattan 距离）计算出两个简单簇的 cohesion，并最终求出整体聚类的总 cohesion 值（这里是 2）。
Separation 分离度
总中心概念
SSE与BSE
🧠 总结 & 对比：
指标 | 含义 | 越小越好 or 越大越好 | 作用 |
SSE | 簇内紧凑度 | 越小越好 | 越小表示簇内点更接近 |
BSE | 簇间分离度 | 越大越好 | 越大表示簇间更远、更清晰 |
Silhouette coefficient
✅ 什么是 Silhouette Coefficient？
它是一个综合了 内聚性（cohesion） 和 分离性（separation） 的评价指标，可以：
- 对每一个点进行评估
- 再扩展到每个簇、甚至整个聚类结果
👉 数值范围在 −1 到 +1 之间，越大越好。
Entropy
🧠 一句话解释：
熵越小，簇越“纯”（也就是说，大部分成员属于同一类）熵越大，簇越“杂”（混了很多种不同类别）
✅ 总结一句话：
熵衡量的是“每个簇中标签混得有多严重”
- 熵 = 0：完美纯簇（全是同一类）
- 熵 = 最大值（比如 log₂2 = 1）：完全混合（50%苹果 + 50%香蕉）
🧠 一句话解释：
纯度越高，簇越“干净”，也就是说，里面的样本越集中在一个类别里。
🔁 和熵的比较：
概念 | 纯度（Purity） | 熵（Entropy） |
衡量 | 最多类别所占比例 | 所有类别混杂的程度（越混越高） |
越大越好 | ✅ 是 | ❌ 否，熵越小越好（越纯） |
是否看多个类别 | ❌ 只看最多的那一个 | ✅ 所有类别都考虑 |
范围 | [0, 1]（1 表示完全纯） | [0, log₂ n]（0 表示完全纯） |
敏感性 | 不敏感于少数类别 | 对类别分布更敏感，更细腻 |
确定簇的数量
确定聚类中正确簇数量的一种常见方法是：
- 肘部法则 (Elbow method): 对不同的 k 值运行聚类算法，并绘制 SSE 或其他无监督度量与簇数量的关系图。寻找图中的明显“膝部”（下降）或峰值，这表明一个合适的簇数量。
确定聚类趋势
确定数据集是否具有聚类趋势（即数据是否随机分布或具有非随机结构）非常重要。
- 方法 1: 聚类数据并评估结果: 使用聚类质量度量评估聚类结果。如果评估表明质量差，数据可能没有明显的聚类趋势。
- 方法 2: 在聚类之前测量聚类趋势: 例如，使用霍普金斯统计量 (Hopkins statistic)。
霍普金斯统计量 (Hopkins statistic)
霍普金斯统计量用于估计聚类趋势（空间随机性）。它比较两组点到其最近邻居的距离：一组是原始数据集中的随机抽样点，另一组是随机生成的点。
霍普金斯统计量 H 的计算公式为： H = Σ(u_i) / (Σ(u_i) + Σ(w_i))，其中 u_i 是随机生成点到其最近邻居的距离，w_i 是原始数据集中随机抽样点到其最近邻居的距离。
霍普金斯统计量的解释：
- 接近 1: 数据高度聚类。随机点的邻居比实际点的邻居远（u 大于 w）。
- 接近 0.5: 两组点的最近邻距离大致相同，表明原始数据与随机数据相似，即数据集在空间上是随机的，聚类效果不佳。
- 接近 0: 数据既不聚类也不随机，而是均匀分布的。
通常，霍普金斯统计量会计算并对多次运行的结果取平均值。
如果聚集得很好，那么 W 的值就会很小在这里。越靠近 的话，就证明它们的数据越相关。
🧠 生动类比帮助你记住：
想象你有一堆人正在结伴聊天（聚类数据），你往人堆里扔几个新来的人（随机点）。这些人都插不进圈子，总是离别人远远的。这时候你就知道：“啊哈！原来这些人是分小圈子的！”
Hopkins 就是在量化这个“插不进去”的程度！
✅ 总结一句话：
Hopkins 越接近 1，说明数据越有聚类结构；越接近 0.5 或更低，越像是随机撒点，没什么簇可言。
- Author:盛溪
- URL:https://tangly1024.com/article/comp%205318%20week%2010%20new%20lec%20and%20tut
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
