algorithm - K-Medoid (PAM) 算法的缺点

Question

我研究过 K-medoid 算法 (PAM) 是一种基于分区的聚类算法，是 K-means 算法的变体。它解决了K-means产生空簇和对异常值/噪声敏感的问题。

但是，K-medoid 的时间复杂度是 O(n^2)，不像 K-means(劳埃德算法)的时间复杂度是 O(n)。请问K-medoid算法除了时间复杂度之外还有没有其他缺点。

Answer 1

K-Medoid 算法(PAM、CLARA 或 CLARANS)的主要缺点是它们不适合聚类非球形(任意形状)的对象组。这是因为它们依赖于最小化非中心点对象和中心点(聚类中心)之间的距离——简而言之，它们使用紧凑性而不是连通性作为聚类标准。

PAM 的另一个缺点是，它可能会在同一数据集上的不同运行中获得不同的结果，因为前 k 个中心点是随机选择的。

除了上述缺点外，您还必须提前指定k(簇数)的值。