我想将ROCK聚类算法与基于距离的算法进行比较。假设我们有(m)个训练样本和(n)个特征

ROCK:

据我所知，ROCK所做的是

1. 它使用Jaccard系数计算一个(m*m)的相似性矩阵。2. 然后用户提供一个阈值。3. 根据阈值，它连接数据点，具有更多共同邻居的数据点被认为在同一个聚类中。例如，让我们看下面的png文件，

   上图显示了相似性矩阵，并假设阈值为0.2。4. 算法然后计算点之间的链接，如下所示。   对于A- A   （只有A超过阈值）     B- BCD （因为bb, bc和bd超过阈值）    C- BCD    D- BCD现在由于B, C和D每个都有3个共同的邻居，它们被分组到同一个聚类中。因此我们得到两个聚类{A}, {BCD}

基于距离的方法:

1. 我采取了一种不同的方法，但像ROCK一样，我也创建了相似性矩阵。2. 我也计算了初始链接，如下所示，   对于A- A   （只有A超过阈值）        B- BCD （因为bb, bc和bd超过阈值）       C- BCD       D- BCD3. 现在不是寻找邻居，我进行了一些操作并找到最佳的中心点。4. 找到中心点后，我在相似性矩阵(m*m)上运行k-means聚类算法。5. 由于我事先找到了中心点，算法所需的时间减少了，因为不需要多次运行k-means算法来选择随机的中心点。

问题陈述:

我看到的问题是空间复杂度，因为相似性矩阵是一个(m*m)矩阵，如果m的值太大，比如100万，存储这么大的矩阵会很困难，而且由于矩阵的大小，欧几里得距离计算需要时间。

然而，我认为在ROCK中，完全没有必要存储矩阵，因为当计算数据集之间的Jaccard系数时，可以即时构建链接。

我对蘑菇数据集（可在uci.org获得）使用了基于距离的算法方法，输出结果与ROCK非常相似，对于其他一些数据集甚至更好。

问题:

1. 我对ROCK的理解是否正确。2. 是否值得考虑创建如此大的相似性矩阵并存储在磁盘上，然后稍后使用它来计算距离。3. 如果有人能提供基于距离方法的大O复杂度，我将不胜感激。

谢谢:)

回答：

据我所知，随着数据规模的增加，聚类变得非常耗费内存，你需要想办法降低数据的维度。

我不熟悉ROCK，但我之前处理过聚类问题，其中我需要对数百万份文档进行聚类。

距离计算度量：levenshtein距离聚类算法：DBSCAN

回到你的问题

问题2：是否值得考虑创建如此大的相似性矩阵并存储在磁盘上，然后稍后使用它来计算距离。

我从不建议构建大型矩阵。例如，构建100万个单词的距离矩阵将需要4TB的空间。你需要使用某种分块技术来将相似文档分组，然后在其上应用聚类算法。

3. 如果有人能提供基于距离方法的大O复杂度，我将不胜感激。

通常，计算两个单词之间的距离的时间复杂度是微不足道的，因为单词不是太长。你的复杂度将是比较的数量，所以如果你有n个单词，那么时间复杂度将是O(n*n)