我正在尝试在大约 5000 条记录的列表中查找重复项。每条记录都是一个人的姓名和地址，但都在一个字段中输入不一致，所以我正在尝试一种模糊匹配方法。我的方法（使用rapidminer）是对文本进行一些预处理（即标记化，删除常见和不相关的单词，例如“先生”等），生成TF-IDF并使用DBSCAN对匹配记录进行聚类。这很有效，并给出了很好的结果，但是当我尝试运行完整的数据集时需要很长时间。这也会导致很多只有一个元素的簇，我不知道这会如何影响 DBSCAN 的计算时间。
是否有一种聚类算法可以更快地处理此类数据，或者是否有更好的方法来解决这个问题？
你确定集群是最好的方法吗？
对我来说，这听起来好像你在做近乎重复的检测，即你定义了一些阈值，只是想找出在这个相似性阈值内是否有任何其他对象。如果您使用的 DBSCAN 具有较低的 minPts 值（例如 minPts=2），那么您实际上并没有在使用 DBSCAN。
如果 DBSCAN 生成单元素簇，则它的实现不正确。DBSCAN 中不能有单元素簇；这些是噪声对象，应该这样对待。
我不知道 RapidMiner 中 DBSCAN 的质量。如果它是基于 Weka 代码的，那就是垃圾（即，甚至都不要费心去尝试 Weka！）。而且真的很慢。它至少拼写错误：DBScan 不正确，它是一个缩写，应该拼写为 DBSCAN...
天真地实施 DBSCAN 是复杂的O(n^2)。如果你有一个好的索引来支持查询，它可以在O(n log n). 如果你有一个非常糟糕的实现，它可能会因为数据结构效率低下而下降O(n^3)......（从快速检查来看，rapidminer 应该在O(n^2)，但由于使用 可能会浪费大量内存LinkedList<Integer>，并且垃圾收集器会可能要花很多钱）
5000 个对象实际上并没有那么多。所以很可能问题不在于聚类算法的复杂性（我已经在 60 秒内使用 ELKI 在单个 CPU 上对 100000 个对象运行了 DBSCAN），而是距离计算。快速浏览一下 rapidminer，我看不出它是否支持稀疏向量、稀疏向量上的有效余弦相似度，甚至没有预计算向量长度以充分利用向量稀疏性的技巧（以预处理每个对象和存储为代价）一个额外的双）。现在显然，如果您的向量与文本向量一样具有 1% 的稀疏度，那么使用低效的非稀疏距离计算将花费大约 100 倍的时间，计算大量的 0。
我刚刚在类似文本的数据集上使用 ELKI 运行 DBSCAN。它没有你的那么大：只有 3333 个观测值和 50 个维度，以及 13% 的稀疏性）。运行 DBSCAN 需要 7 秒，epsilon=0.001，minpts=3，余弦相似度；未启用索引加速。所以很明显，问题似乎不在于 DBSCAN，而在于 RapidMiner 实现。请注意，ELKI 与稀疏数据一起使用有点棘手。您需要以正确的输入格式输入数据，正确设置一些过滤器等 - 我现在不推荐给初学者。这更要强调它可能是 RapidMiner 的相似函数实现杀死了你的运行时。
我不想阻止您使用 DBSCAN。从聚类的角度来看，它是你能找到的最合适的算法之一：它支持任意距离函数（k-means 不支持），你不需要事先知道聚类的数量（显然你不需要't) 并且它也会选择不将所有内容聚类（显然你有很多非聚类对象）。
但是，我相信您根本不想进行聚类。您似乎对重复检测感兴趣，我假设您可以通过例如将文档加载到 Lucene 或 Xapian 等文本搜索引擎中并查询专用文本搜索引擎来查看您是否有更好的性能和结果质量附近重复。而这些文本搜索引擎真的很擅长：匹配文本。我认为比 rapidminer 好得多。
您的问题不是聚类，而是近似字符串匹配。
您可能需要查看Levenshtein 编辑距离或使用几个 现有选项之一。