你确定使用“聚类”是最好的方法吗?
在我看来,这听起来像是你正在进行“近似重复检测”,即你定义了一些阈值,只想找到是否存在任何其他对象在这个相似性阈值内。如果你使用DBSCAN并设置一个低的minPts值(比如minPts=2),那么你实际上并没有使用DBSCAN。
如果DBSCAN产生单元素簇,则实现有误。在DBSCAN中不能有单元素簇;它们应该被视为噪声对象。
我不知道RapidMiner中DBSCAN的质量。如果它基于Weka代码,那就太差了(即不要尝试Weka!)。而且非常缓慢。至少它的拼写是错误的:DBScan是错误的,它是一个缩写,应该拼写为DBSCAN...
当naively实现DBSCAN时,其复杂度为O(n^2)。如果你有一个良好的索引来支持查询,它可以运行在O(n log n)。如果你有一个真的很糟糕的实现,它可能会因为数据结构效率低下而降至O(n^3)。(从快速检查中,rapidminer应该在O(n^2)中,但可能由于使用LinkedList而浪费了大量内存,并且垃圾收集器可能会花费相当多的时间)
5000个对象实际上并不算太多。所以问题可能不是聚类算法的复杂度(我在单个CPU上使用ELKI在100000个对象上运行DBSCAN花费60秒),而是距离计算。从快速浏览RapidMiner,我无法看到它是否支持稀疏向量、稀疏向量上的有效余弦相似性,甚至是预先计算向量长度的技巧,以充分利用向量的稀疏性(以每个对象的预处理为代价,并存储一个额外的double)。现在显然,如果你有1%的稀疏向量,如文本向量,使用低效的非稀疏距离计算将需要比必要的时间长约100倍,计算大量的0。
我刚刚在类似文本的数据集上使用ELKI运行了DBSCAN。它不像你的那么大:只有3333个观察值和50个维度,稀疏度为13%。使用epsilon=0.001、minpts=3和余弦相似度,未启用索引加速,运行DBSCAN需要7秒钟。因此,显然问题不在于DBSCAN,而在于RapidMiner的实现。请注意,使用稀疏数据的ELKI有点棘手。你需要将数据放在正确的输入格式中,设置一些过滤器等——我现在不建议初学者使用它。这更多地是为了强调RapidMiner的相似度函数实现可能会导致运行时间过长。
我不想打击你对DBSCAN的信心。从聚类的角度来看,它是你可以找到的最合适的算法之一:它支持任意距离函数(k-means不支持),你不需要事先知道聚类的数量(显然你不知道),而且它还会放弃聚类所有东西(因为显然你有很多非聚类对象)。
然而,我认为你根本不想做聚类。你似乎对重复检测感兴趣,我认为如果你将文档加载到文本搜索引擎(如Lucene或Xapian)中,并查询专用的文本搜索引擎以查看是否有近似副本,则可以获得更好的性能和结果质量。这些文本搜索引擎在匹配文本方面非常出色,比RapidMiner要好得多,我推测。