aqu*_*tae 5 text-processing cluster-analysis data-mining rapidminer dbscan
我正在尝试在大约 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 个对象实际上并不算多。因此，问题很可能不在于聚类算法的复杂性（我已经在使用 ELKI 的单个 CPU 上在 60 秒内对 100000 个对象运行了 DBSCAN），而在于距离计算。快速浏览一下rapidminer，我看不出它是否支持稀疏向量、稀疏向量上的高效余弦相似性，甚至不知道预先计算向量长度以充分利用向量稀疏性的技巧（以预处理每个对象并存储额外的双）。显然，如果向量的稀疏度为 1%（与文本向量一样），则使用低效的非稀疏距离计算将需要大约 100 倍的时间，计算大量 0。
我刚刚在类似文本的数据集上使用 ELKI 运行 DBSCAN。它没有你的那么大：只有 3333 个观测值和 50 个维度，稀疏度为 13%）。在epsilon=0.001、minpts=3、Cosine相似度下运行DBSCAN需要7秒；没有启用索引加速。因此，显然问题不在于 DBSCAN，而在于 RapidMiner 的实现。请注意，ELKI 在处理稀疏数据时有点棘手。您需要以正确的输入格式提供数据，设置一些正确的过滤器等 - 我现在不会向初学者推荐它。这更要强调的是，它可能是 RapidMiner 的相似函数实现杀死了你的运行时间。
我不想阻止您使用 DBSCAN。从聚类的角度来看，它是您能找到的最合适的算法之一：它支持任意距离函数（k-means 不支持），您不需要事先知道聚类的数量（您显然不知道） 't）并且它还会选择退出对所有内容进行聚类（显然您有很多非聚类对象）。
但是，我相信您根本不想进行聚类。您似乎对重复检测感兴趣，我假设您可以通过将文档加载到文本搜索引擎（例如 Lucene 或 Xapian）中，并查询专用文本搜索引擎来查看是否有更好的性能和结果质量。接近重复。这些文本搜索引擎非常擅长这一点：匹配文本。我认为比rapidminer 好得多。