cluster-analysis - 适用于非常小的集群的聚类算法

Question

我试图在大约 5000 条记录的列表中查找重复项。每条记录都是一个人的姓名和地址，但都不一致地输入到一个字段中，所以我正在尝试一种模糊匹配方法。我的方法(使用rapidminer)是对文本进行一些预处理(即标记化，删除常见和不相关的词，例如“先生”等)，生成TF-IDF并使用DBSCAN对匹配记录进行聚类。这有效，并给出了非常好的结果，但是当我尝试运行完整数据集时需要很长时间。也导致很多簇只有一个元素，不知道这对DBSCAN的计算时间有什么影响。

是否有一种聚类算法可以更快地处理此类数据，或者是否有更好的方法来解决这个问题？

Answer 1

您确定聚类是最好的方法吗？

对我来说，这听起来好像你在做 近似重复检测 ，即您定义了某个阈值，只想查找此相似性阈值内是否还有其他对象。
如果您使用的 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% 的稀疏性)。以epsilon=0.001、minpts=3和余弦相似度运行DBSCAN需要7秒；没有启用索引加速。因此，问题显然不在于 DBSCAN，而在于 RapidMiner 的实现。请注意，ELKI 与稀疏数据一起使用有点棘手。您需要以正确的输入格式获取数据，正确设置许多过滤器等 - 我现在不建议初学者使用它。这更要强调可能是 RapidMiner 的相似函数实现杀死了您的运行时。

我不想阻止您使用 DBSCAN。从聚类的角度来看，它是你能找到的最合适的算法之一:它支持任意距离函数(k-means 不支持)，你不需要事先知道聚类的数量(你显然不知道) 't) 并且它也会选择退出对所有内容进行聚类(显然您有很多非聚类对象)。

然而，我相信你根本不想做聚类 .您似乎对重复检测感兴趣，我认为您可以通过例如获得更好的性能和结果质量将您的文档加载到文本搜索引擎中，例如 Lucene 或 Xapian，以及 查询专用文本搜索引擎，查看您是否有近乎重复的内容。
这些文本搜索引擎非常擅长:匹配文本。我认为比 Rapidminer 好得多。