php - Levenshtein - 分组酒店名称

Question

我必须根据名称将一些酒店归入同一类别。我正在使用 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)
        );
}

Answer 1

我会深入思考。首先，像这样对数据进行分组或“聚类”是一个很大的话题，我不会真正深入探讨它，但也许会指出一个理想的方向。

您通过根据所比较的字符串的长度对 Levenshtein 进行归一化来做了一件绝妙的事情 - 这是完全正确的，因为您避免了字符串长度在许多情况下过度确定相似性的问题。

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

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

如果您同意酒店品牌名称位于开头附近的想法，您也可以始终歪曲它们与字符串开头的接近程度。问题是，您的团队很可能最终会成为“法国”而不是“最佳”/“西方”(但不是“酒店”- 为什么？)。

您想让您的结果更准确吗？

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

对于看似小问题的事情来说，这可能有点繁重 - 但我想强调的是，如果您的数据不是结构化的，那么正确处理事情确实没有任何捷径.