根据互联网，k-means 聚类在数据对象的数量上是线性的，即 O(n)，其中 n 是数据对象的数量。大多数层次聚类算法的时间复杂度是二次的，即O(n2)。
我正在努力直观地理解导致这种情况的两种聚类方法之间的区别。
问题：是什么导致了时间复杂度的差异？
为什么层次聚类是二次的，k-means是线性的？
数据挖掘
聚类
k-均值
2022-02-15 11:54:26
1个回答
我认为这些时间复杂度是乐观的情况，但除此之外，我认为原因是在层次聚类中，您考虑了许多（如果不是全部）数据点对之间的距离。对数与点数成二次方关系。
对于 k 均值，您通过查看每个数据点与 k 均值之间的距离来在考虑所有对时有点作弊。这在 k 和数据点的数量上都是线性缩放的。
所以我认为加速是由于使用与手段的距离作为所有点之间的距离的代理。
其它你可能感兴趣的问题