ITDS-聚类
Hierarchical，Similarity，DBSCAN，Validation
层次聚类
- Agglomerative
每次合并最近的两个点，直到合并成 k 个类 - Divisive
从一个包含所有数据点的类开始进行分裂，直到分裂成 k 个类
每次操作都只对一个聚类进行，聚类结果会形成一种嵌套关系，每个节点代表一个聚类，上层节点是由下层节点合并产生的，我们可以使用 dendrogram 树状图 来表示这种嵌套关系。它不需要预设聚类数量，通过在合适的层次切割树状图，就可以得到任意数量的聚类。
凝聚式算法：
- 计算 Proximity Matrix
邻近矩阵衡量各个数据点之间的距离 - 将每个数据点看作一个聚类
- 合并最近的两个聚类
- 更新邻近矩阵
- 重复 3-4 直到只剩下 k 个聚类
相似度
需要明确聚类间的相似性，以此判断哪些聚类应该合并或保持分离。计算两个簇之间的距离有不同的方法：
- Single Linkage (MIN)
计算两个簇之间最小距离，即最近两个点之间的距离。在簇之间形成链状连接，适用于发现非球形簇。 - Complete Linkage (MAX)
计算两个簇之间的最大距离，即最远两个点之间的距离。能创建更紧密，类似球形的簇，并减少噪声的影响。 - Average Linkage
计算两个簇之间所有点的平均距离，是 Single 和 Complete 的折中方案，对噪声敏感度底，偏向形成球形聚类。 - Centroid Linkage
计算两个簇之间质心（如几何中心）的距离。这种方法计算简单，处理复杂形状聚类时可能效果不佳。 - Ward’s Method
此方法选择 合并两个簇后，簇内平方和的增加量最小 的一对。这种方法对噪声敏感度低，适用于球形簇结构。
问题
- 层次聚类计算复杂度高，时间复杂度为 O(n^3)，空间复杂度为 O(n^2)
- 合并决策不可逆
- 无目标函数，无法直接优化
- 处理多种形状的簇效果不佳
DBSCAN
Density-Based Spatial Clustering of Applications with Noise 是一种基于密度的聚类算法，能够识别形状不规则的簇，并检测噪声点，不需要预设聚类数量。
它主要依赖两个参数：
- Eps：邻域半径，用于确定一个点的邻域范围，也就是多远才算是邻居
- MinPts：邻域内最少点数，也就是在一个区域类至少需要多少个点，才能算作一个簇
根据这两个参数，DBSCAN 将数据点分为三类：
- 核心点：在 Eps 范围内至少包含 MinPts 个点（包括自身）
- 边界点：不是核心点，但在某个核心点的 Eps 范围内
- 噪声点：既不是核心点也不是边界点
选择 Eps 和 MinPts
对于簇中的点，它们的第 k 近邻的距离应该相似，如第 2 与第 3 近邻的距离相差不大。我们可以通过 k-distance graph 来选择合适的 Eps 和 MinPts。
- 计算所有点到第 k 近邻的距离
- 对距离进行排序，画出随 k 变化的距离图
- 找到出现突然增长的点
- 这个点的横坐标就是 Eps，纵坐标就是 MinPts
Density Connectivity
Density Edge: 如果 p 和 q 都是核心点，且它们的距离小于等于 Eps，则能够在它们之间构建一条密度边，它的存在意味着两个核心点所在区域数据点密集，具备归为同一簇的条件，它用于构建核心点网络。
Density Connected: 如果某个点 p 可以通过一系列的密度边连接到另一个核心点 q，则 p 和 q 是密度相连的，它们可能不能直接相连，但是可以通过多个核心点传递连接。它是判断点是否属于同一簇的关键条件。
密度连接使 DBSCAN 能够形成任意形状的簇。
缺点
- 计算复杂度高
- 它假设所有簇的密度相近，对密度差异较大的数据集效果不佳
- 对参数敏感，需要调参
聚类有效性
在 Supervised Classification 中，我们使用 Accuracy，Precision，Recall 等评价结果的好坏。在聚类分析中，我们也需要评估聚类结果的好坏。由于聚类属于无监督学习，所以产生的结果会根据标准不同而变化。评估聚类的目的是防止噪声导致错误聚类，比较并选择最合适的算法。
我们可以评估整个聚类结果，也可以评估单个簇。我们可以：
- 判断数据集是否真的存在聚类，而不是随机噪声
- 将聚类结果与可能的已知结果比较，比如类别标签
- 使用数据本身来评估聚类的匹配度
- 对比不同聚类的结果
- 确定最佳的聚类数量
我们有以下衡量方法：
- 外部指标：如真实分类标签
- Entropy（聚类的不确定性，聚类结果与真实类别标签的一致性）
- Purity（簇内数据一致性，每个簇中占比最高的类别）
- 内部指标：
- 误差平方和 SSE（簇内数据点到簇中性距离，越小数据越紧密）
- 簇凝聚力（Cohesion，簇内数据点之间的相似度，或者距离）
- 簇分离度（Separation，不同簇之间的距离）
- 轮廓系数（Silhouette Coefficient）
- 相对指标：Rand Index
轮廓系数评估每个数据点在其所属簇中的合理性，它同时考虑 Cohesion 和 Separation。它最初计算单个数据点，然后可以扩展到簇和整个聚类结果，当用于簇时，计算的是平均系数，衡量该簇的质量，聚类同理。它的值在 [-1, 1] 之间，值越大，表示聚类效果越好，约等于 0 说明数据点在边界，负数说明可能被错误的分配到簇中。
Rand Index 比较数据点在真实类别和聚类的分配情况，来计算正确性。显而易见的，两个对象在同一簇中说明它们应该属于同一类。它的取值范围是 [0, 1]，值越大，说明聚类效果越好，接近 0.5 说明聚类接近于随机划分，而 0 是很差。如果某个类别的数据点较多，可能会使 Rand Index 偏高，使用 Adjusted Rand Index 来修正磁偏差。