基于关键词交集的匹配算法

假设我们有买卖双方试图在市场上找到对方。买家可以用关键字标记他们的需求;卖家可以为他们卖的东西做同样的事情。我感兴趣的是根据他们的两个关键字集合来找到按照与特定买家的相关性对卖家进行排序的算法。基于关键词交集的匹配算法

下面是一个例子：

buyer_keywords = {"furry", "four legs", "likes catnip", "has claws"}

，然后我们有我们需要他们的相关性方面的排名顺序的两个潜在卖家：

seller_keywords[1] = {"furry", "four legs", "arctic circle", "white"} 
seller_keywords[2] = {"likes catnip", "furry", 
         "hates mice", "yarn-lover", "whiskers"}

如果我们仅仅使用关键字的交集，我们没有得到太多的歧视：两个关键词相交。如果我们将交点数除以设定的联合的大小，则由于关键字的数量更多，卖家2实际上会变得更糟。这似乎会引入一个自动惩罚的方法，不纠正关键字集的大小（我们绝对不想惩罚添加关键字）。

为了把更多的结构上的问题，假设我们有关键字属性（其必须总和为1的每个卖家），例如，：

seller_keywords[1] = {"furry":.05, 
         "four legs":.05, 
         "arctic circle":.8, 
         "white":.1} 

seller_keywords[2] = {"likes catnip":.5, 
         "furry":.4, 
         "hates mice":.02, 
         "yarn-lover":.02, 
         "whiskers":.06}

强度的一些真实的措施现在我们可以总结点击的价值：所以现在卖家1只得到.1的得分，而卖家2得到0.9的得分。到目前为止，一切都很好，但现在我们可能会得到第三个卖家有非常有限的，非描述性的关键词组：

seller_keywords[3] = {"furry":1}

这弹射他们顶端关于他们的唯一关键字命中的，这是不好。

无论如何，我的猜测（和希望）是这是一个相当普遍的问题，并且存在着已知强度和局限性的不同算法解决方案。这可能是CS101涵盖的内容，所以我认为这个问题的一个很好的答案可能只是一个链接到相关的参考文献。

来源

2011-02-28 John Horton

我认为我们应该将有效分数乘以匹配关键字的数量。例如，在您的第二种情况下，例如，我们只有1个匹配，并且其得分为1，因此有效分数1 * 1 = 1。在这种情况下，如果找到两个匹配，我们将有效得分为2 * 1 = 2。因此，它被选中。您对这种方法有何看法。 – Algorithmist 2011-02-28 13:30:54

我认为你在寻找使用cosine similarity;这是一个基本的技术，可以让你成为第一个黑客。直观地说，你创建一个向量，每一个你知道的标签都有一个特定的索引：

terms[0] --> aardvark 
terms[1] --> anteater 
... 
terms[N] --> zuckerberg

然后你在这个空间里的每个人创造的载体：

person1[0] = 0  # this person doesn't care about aardvarks 
person1[1] = 0.05 # this person cares a bit about anteaters 
... 
person1[N] = 0

每个人现在在这个矢量N维空间。然后可以使用余弦相似度来计算它们之间的相似度。在计算上，这与要求两个向量之间的角度基本相同。你想要一个余弦接近1，这意味着向量大致共线 - 它们对于大多数维度具有相似的值。

要改进此度量标准，您可能需要对矢量中的元素使用加权tf-idf。 Tf-idf会淡化流行术语（如'iPhone'）的重要性，并提升这个人似乎特别与之相关的非流行术语的重要性。

结合tf-idf加权和余弦相似性对于这样的大多数应用程序来说效果很好。

来源

2011-02-28 14:00:12

余弦相似性不能解决'{“furry”：1}'的最后一个问题，但可能不是这样做（即采用两个归一化向量的点积），您可以使用实际的点积。未能规范买方并不重要，因为它将相同的比例因子应用于所有结果，并且它们的排名依然相同。未能规范卖家意味着您可以根据其他一些标准来衡量卖家，而不仅仅是关注他们的关键字列表。举一个简单的例子，你可以限制任何一个关键字的强度，所以只列出一个关键字的销售商的量级<1。 – 2011-02-28 16:02:00

你在找什么叫做分类学。标记内容并按相关顺序排序。

您可能找不到一些准备好的算法，但您可以从实际案例开始：Drupal documentation for taxonomy提供了一些准则，并检查search module的来源。

基本上，排名是根据这个词的频率。如果使用少量标签定义产品，则它们将具有更多的重量。仅在少数产品页面上出现的标签意味着它非常具体。你不应该用静态的方式来定义你的话语的强度;但在他们的上下文中检查它们。

问候

来源

2011-02-28 13:44:50 vaugham

这似乎更像是解决问题的特定库，而不是用于解决问题的算法或数学框架。 – templatetypedef 2011-02-28 20:43:36

基于关键词交集的匹配算法

回答

相关问题