1

我必须根据他们的名字将一些酒店归为同一类别。我正在使用 levenshtein 进行分组，但是我尝试了多少，一些酒店被留在了他们应该属于的类别之外，或者在另一个类别中。

例如：所有这些酒店都应该属于同一类别：

==============================

贝西贝西左岸酒店

贝斯特韦斯特体育馆

最佳西方勃艮第公爵酒店

最佳西方福克斯通歌剧院

最佳西方法国欧洲

悉尼歌剧院贝斯特韦斯特酒店

最佳西方巴黎卢浮宫歌剧院

德诺伊维尔贝斯特韦斯特酒店

==============================

我有一个包含所有酒店名称的列表（比如 1000 行）。我也有他们应该如何分组。知道如何优化 levenshtein，使其更适合我的情况吗？

$inserted = false;
foreach($hotelList as $key => $value){
    if (levenshtein($key, $hotelName, 2, 5, 1) <= abs(strlen($key) - strlen($hotelName))){
        array_push($hotelList[$key], trim($line));
        $inserted = true;
    }
}
// if no match was found add another entry
if (!$inserted){
    $hotelList[$hotelName] = array(
            trim($line)
        );
}
4

3 回答 3

2

我会带着我的想法涉水。首先，像这样对数据进行分组或“聚类”是一个相当大的话题，我不会特别深入探讨它，但也许可以将事情指向一个理想的方向。

您通过在比较字符串的长度上标准化 Levenshtein 做了一件了不起的事情——这完全正确，因为您避免了字符串长度在许多情况下会过度确定相似性的问题。

但是算法并没有解决问题。首先，我们想比较单词。“Bent Eastern French Hotels”显然与“Best Western French Hotels”有很大不同，但它比“Best Western Paris Bed and Breakfasts”得分更高。这里要掌握的直觉是，您的标记不应该是字符，而是单词。

我喜欢@saury 的回答，但我不确定一开始的假设。相反，让我们从通常被称为“词袋”的好东西开始。然后，我们实现了一个散列技巧，它允许您根据最少使用的单词包含最多信息的直觉来识别关键短语。

如果您同意酒店品牌名称靠近开头的想法，那么您也总是可以将它们与字符串开头的距离倾斜。问题是，您的团队最终可能会成为“法国”和“最佳”/“西方”（但不是“酒店”——为什么？）。

您希望您的结果更准确吗？

从这里开始，我们将不得不采取一些严肃的算法 - 享受浏览许多堆栈溢出主题。我的直觉是，我敢打赌，许多酒店名称根本没有品牌，因此您也需要为它们设置不同的类别。我的直觉也是，酒店名称中重复单词的数量将相对较少——一些单词将成为酒店名称的频繁成员。这些事实将成为上述问题。在这种情况下，有一种非常流行的（如果对 SO 来说是陈词滥调）技术，称为 k-means，一个有趣的介绍是扩展这样的算法（非常勇敢地用 php 编写）以将您选择的n 个关键短语作为n集群的维度，然后将集群中心点的大多数组件作为您的分类标签。（例如，这将消除“France”，因为“France”的命中将非常均匀地分布在 n 维空间中）。

对于看起来像一个小问题的事情，这可能有点多 - 但我想强调的是，如果您的数据不是结构化的，那么正确地做事真的没有任何捷径。

于 2013-07-04T10:38:11.233 回答
0

您将什么 levenshtein 距离值作为要被视为同一组的一部分的单词之间的增量？似乎您倾向于根据最初的几个词对酒店进行分组，这将需要完全不同的方法（例如进行字典排序，将当前字符串与下一个字符串进行比较等）。但是，如果您的用例仍然需要计算 levenshtein 距离，那么我建议您根据字符串的长度对字符串进行排序，然后开始将每个字符串与其他类似长度的字符串进行比较（将您自己的启发式应用于您认为“相似”的内容就像你可能会说的 isSimilar = Math.abs(str1.length - str2.length) < SOME_LOWEST_DELTA_VALUE 或类似的东西）

于 2013-07-04T09:56:31.950 回答
0

一般来说，您可能想阅读http://en.wikipedia.org/wiki/K-means_clustering和http://en.wikipedia.org/wiki/Cluster_analysis。

于 2013-07-04T10:52:32.890 回答