我最近完成了一个项目，我使用 scikit-learn 的DBSCAN模块在相对较短的文本字符串中查找集群。我使用了自定义字符串相似度度量来允许向量化计算相似矩阵。
我知道可以将 DBSCAN 的时间复杂度降低到通过使用适当的 (查找时间）用于查找给定数据点的邻居的索引结构。DBSCAN 时间复杂度
当我的数据是长度为 1296 的二进制特征向量时，我该如何做到这一点？是否有一种有效的方法来索引具有任意维数的点的查找？如果是这样，这个功能是内置在 scikit-learn 中还是我需要推出自己的解决方案？
倒排列表非常适合稀疏数据。这就是例如 Lucene 所使用的。
我不知道 scikit-learn 的可扩展性如何。其中的很多代码似乎是用 Cython 编写的，因此它是通过 C 编译的类似 Python 的代码。这将使其更难扩展。
ELKI是我贡献良多的数据挖掘工具，它有一个尚未发布和未记录的Lucene 插件。这可能对你有用。我希望在某个时候在 ELKI main 中也有一个稀疏向量的倒排索引（由于 Lucene 依赖，我计划保持这个插件分开）。
我们还有（非集成的）用于加速 Levenshtein 距离的前缀树索引的代码。但这需要更多的工作来整合它，也许还需要一些分析。
大多数时候，索引只适用于特定的距离。没有可以同时支持任意距离的通用索引。有一些索引（例如 M-tree 和 iDistance，两者都在 ELKI 中可用）可以处理任意距离，但一次只能处理一个距离。但是它们对您的数据和距离的工作情况差异很大。通常，您需要对相似性进行良好的数值对比。
您需要问自己的问题是：有没有办法找到半径范围内的所有对象（或相似度大于)而不将每个对象与其他所有对象进行比较。
请注意，对于 DBSCAN，您可以使用假距离。不使用实际距离；只需要二元决策（）。这被形式化为GeneralizedDBSCAN。因此，如果您可以实现一个“距离函数”，返回 0 表示“相似”，返回 1 表示“不相似”，并将其插入 scikit-learn 的 DBSCAN，你应该没问题。根据 scikit-learn 的架构，您也许可以插入伪装成距离函数的自定义索引。倒排列表是二进制数据的良好候选者。