ITDS-聚类
Hierarchical，Similarity，DBSCAN
层次聚类
- 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 能够形成任意形状的簇。
缺点
- 计算复杂度高
- 它假设所有簇的密度相近，对密度差异较大的数据集效果不佳
- 对参数敏感，需要调参