3

我正在尝试解决一个涉及比较大量单词集的问题，每个单词集都包含来自一组单词的大量有序单词（总计约 600+，非常高的维度！）以进行相似性，然后将它们聚类成不同的分组。解决方案需要尽可能不受监督。

数据看起来像

[苹果、香蕉、橙子...]
[苹果、香蕉、葡萄...]
[果冻、茴香、橙子...]
[草莓、香蕉、橙子...]
...等

每组单词的顺序很重要（[Apple, Banana, Orange] 与 [Apple, Orange, Banana] 不同

到目前为止，我一直使用的方法是使用 Levenshtein 距离（受距离阈值限制）作为在 Python 脚本中计算的度量，每个单词都是唯一标识符，从距离生成相似度矩阵，然后将该矩阵放入用于分组的 KNIME 中的 k-Mediods。

我的问题是：

  • Levenshtein 是解决这个问题的最合适的距离度量吗？
  • 均值/中心点原型聚类是进行分组的最佳方式吗？
  • 我还没有花太多心思来验证集群中“k”的选择。评估聚类的 SSE 曲线是否是解决此问题的最佳方法？
  • 我的方法有什么缺陷吗？
  • 作为未来解决方案的扩展，在给定训练数据的情况下，是否有人碰巧对将概率分配给集群分配有任何想法？例如，集合 1 有 80% 的机会位于集群 1 中，等等。

我希望我的问题不会显得太愚蠢或答案很明显，我对数据挖掘还比较陌生。

谢谢！

4

2 回答 2

3

是的，Levenshtein 是一种非常合适的方式来做到这一点。但是如果序列的大小变化很大，最好通过除以序列长度的总和来归一化这些距离 - 否则你会发现观察到的距离往往会增加对于“平均距离”的长序列对（在对于一些小的 k)，对应的 k 长度子串之间的平均距离的意义是恒定的。

示例：([Apple, Banana], [Carrot, Banana])可以说这对具有相同的“平均”距离，([Apple, Banana, Widget, Xylophone], [Carrot, Banana, Yam, Xylophone])因为每个第二个项目都匹配，但后一对的原始 Levenshtein 距离将是两倍大。

还要记住，Levenshtein 对“块移动”没有特别考虑：如果你拿一个字符串，并将它的一个子字符串移动足够远，那么结果对（原始和修改的字符串）将具有相同的 Levenshtein 分数好像第二个字符串在子字符串移动到的位置具有完全不同的元素。如果您想考虑到这一点，请考虑改用基于压缩的距离。（虽然我在那里说它对于计算距离而不考虑顺序很有用，但它当然有利于有序相似性而不是无序相似性。）

于 2010-12-02T07:05:06.920 回答
0

查看 sourceforge 上的 SimMetrics 以了解支持各种指标的平台，这些指标可以用作评估任务最佳表现的方法。

如需商业上有效的版本，请查看 K-Now.co.uk 的 K-Similarity。

于 2010-12-01T23:19:51.650 回答