K-Means 和 Mean-Shift 使用原始样本描述符（无需预先计算亲和矩阵）。

否则，对于谱聚类或幂迭代聚类，您可以使用 k-最近邻亲和矩阵的稀疏矩阵表示（例如压缩稀疏行）（对于某些距离或亲和度量）。如果 k 很小（比如说 5 或 10）。您将获得一个非常节省空间的表示（2 * n_samples * k * 8 字节用于双精度浮点值）。

一些聚类算法可以使用空间索引结构。这允许例如 DBSCAN 和 OPTICS 在时间内运行（只要索引允许查询）。$O(n\log n)$$O(\log n)$

显然，以这种复杂度运行的算法不会构建距离矩阵。$O(n^2)$

对于一些算法，例如具有单链接和完全链接的层次聚类，有可用的优化算法（SLINK，CLINK）。只是大多数人使用他们能得到的任何东西，任何容易实现的东西。并且层次聚类很容易天真地实现，次迭代（导致算法......）。$n$$n^2$$O(n^3)$

我不知道比较聚类算法的完整列表。毕竟，可能有 100 多种聚类算法。例如，至少有十几个 k-means 变体。此外，还有运行时复杂性和内存复杂性；有平均情况和最坏情况。存在巨大的实现差异（例如上面提到的单链接；以及不使用索引的 DBSCAN 实现，因此在中，虽然它们不需要存储完整的距离矩阵，然后他们仍然需要计算所有成对距离）。另外还有很多参数。对于 k 均值，$O(n^2)$$n\times n$$k$很关键。对于几乎任何算法，距离函数都会产生巨大的差异（任何许多实现都只允许欧几里得距离......）。一旦你得到昂贵的距离函数（除了像欧几里得这样的琐碎的东西），距离计算的数量可能很快就会成为主要部分。因此，您需要区分操作的总数和所需的距离计算次数。因此，当距离函数非常昂贵距离函数本身是 )。$O(n^2)$$O(n)$$O(n \log n)$$O(n)$

好问题。说 3 个最近邻居的稻草人方法是对每个数据点的 Nsample 邻居进行采样，保持最近的 3 个。虽然微不足道，但对 Nsample 的几个值运行此操作将使您对信噪比、近邻/背景噪声有所了解，为您的数据轻松绘制。另一个技巧是检查邻居的邻居，看看是否有比直接邻居更近的邻居。此外，如果输入数据已经很好地混洗，则以块为单位进行采样，否则缓存将崩溃。

（已添加）：请参阅R 中的fastcluster ，我相信 SciPy v0.11。
有关文本，请参阅 google-all-pairs-similarity-search。

重复一遍，“适当的相异性度量对于获得成功的聚类比选择聚类算法更重要”—— 选择聚类方法。