我试图解决一个问题，包括比较大量的单词集，每个单词集包含一组单词（大约600，非常高维度！）的大量有序数量的单词，用于相似性，然后将它们聚类成不同的分组 . 解决方案需要尽可能无人监督 .
数据看起来像
[Apple，Banana，Orange ......]
[Apple，Banana，Grape ......]
[果冻，茴香，橘子......]
[草莓，香蕉，橙...]
...等等
每组中单词的顺序很重要（[Apple，Banana，Orange]与[Apple，Orange，Banana]截然不同
到目前为止我一直使用的方法是使用Levenshtein距离（受距离阈值限制）作为在Python脚本中计算的度量，每个单词都是唯一标识符，从距离生成相似度矩阵，并将该矩阵投入KNIME中的k-Mediods用于分组 .
我的问题是：
-
Levenshtein是最适合此问题的距离指标吗？
-
平均/ medoid原型聚类是进行分组的最佳方式吗？
-
我在群集中没有't yet put much thought into validating the choice for ' k' . 评估聚类的SSE曲线是最好的方法吗？
-
我的方法有什么缺陷吗？
-
作为未来解决方案的扩展，在给定培训数据的情况下，是否有人会碰巧有关于为群集分配分配概率的想法？例如，集合1有80％的机会进入集群1等 .
我希望我的问题看起来不是太愚蠢或答案非常明显，我对数据挖掘相对较新 .
谢谢！
2 回答
是的，Levenshtein是一个非常合适的方法 . 但是如果序列的大小变化很大，那么这些距离除以序列长度的总和可能会更好 - 否则你会发现观察到的距离往往会增加成对的长序列"average distance"（在某种意义上）对于一些小的k），相应的k长度子串之间的平均距离是恒定的 .
示例：对
([Apple, Banana], [Carrot, Banana])可以说与([Apple, Banana, Widget, Xylophone], [Carrot, Banana, Yam, Xylophone])具有相同的"average"距离，因为每个第二项都匹配，但后者对的原始Levenshtein距离将是两倍 .另外请记住，Levenshtein没有为 "block moves" 做特殊限制：如果你取一个字符串，并将其中一个子串移动得足够远，那么得到的对（原始和修改过的字符串）将具有相同的Levenshtein分数，就好像第二个字符串在子字符串移动到的位置具有完全不同的元素 . 如果您想考虑这一点，请考虑使用compression-based distance . （虽然我在那里说它对于计算距离而不考虑顺序是有用的，但它当然有利于有序相似性与无序相似性 . ）
在sourceforge上查看SimMetrics，了解支持各种指标的平台，这些指标可用作评估任务最佳的方法 .
有关商业有效版本，请查看K-Now.co.uk的K-Similarity .