具有多个参数的客户端预测搜索相关性计算

Question

我正在编写一个预测搜索,为了服务器性能要求(所有都是缓存的),必须在客户端浏览器上运行.这些项目是电视节目和电影,并由标题,演员和导演名称匹配.执行搜索后,它会返回一个匹配项列表,每个结果有两个值:

1. 匹配单词的数量(n):用户可以输入4个单词,但只有2个单词与一个项目匹配.越多越好.

2. 在莱文斯坦编辑距离增加(LD).用户可以输入3个单词,但其中有2个单词与索引的单词有拼写错误或其他小差异.我使用编辑距离来查找最近的索引字.所有Levenshtein距离的添加都作为接近指示符返回.越少越好.

要求

1. 客户端.没有Sphinx,Lucene或任何其他服务器端解决方案.

2. 速度超过准确性.该算法在每次击键时运行,我们不想让用户厌烦.保持大O不是那么大.

3. 非递归.每个项目相关性的计算不应该依赖于其他项目计算.我不想击败谷歌,只提供小套装的最佳效果.

4. 有界形式0到1,0到100或类似的东西.不是必需品,但能够显示"相关百分比"是一个加分.

5. 关于实施的想法.我正在寻找一种比特定实现更好的算法/公式.

我的aproach

基于指数衰减(如放射性半衰期分解),我编制了这个公式.

哪里:

• T 是用户提供的单词数.
• n 是匹配单词的数量.
• ld 是这个匹配单词的Levenshtein距离加法.

在伪代码中.

function lambda(n, ld) {
    lambda = (n/T) * e^(-ld * 1/n);
    return lambda;
}

一点解释:

• -ld * 1/n是相关性度量核心.如果ld是低并且n很大,它接近于零(-0侧)并且表明该结果更相关.

• n/T是准确率.匹配单词与所有单词.通过考虑总用户输入来优化先前的相关性.

对于负数幂,指数函数将结果限制在0和1之间.

最后,问题

我想要的不是基于具有额外编辑距离计算的响应来细化搜索算法,而是通过将相关值设置为每个来改进返回元素的相关性排序.如果可以使用除了n并且ld需要且易于计算的任何参数.在我的解决方案中,我添加T了用户提供的单词数.

Answer 1

一般来说,我相信你必须简化你的公式.事实上,像tf-idf这样的大多数基本相关公式都非常简单,只使用生产或参数的一部分,可能还有"加强"或"弱化"功能.例如,tf-idf只是术语频率的乘法和对数逆文档频率的"弱化".首先,我会快速分析您的公式,然后提出一些建议.

分析

让我们改写你的公式:

首先,请注意,这n/T是不归:可能会有更多的结果(n),然后搜索条目(T).考虑这样的例子:用户输入查询"John Malkovich",并且在您的数据库中有电影Being John Malkovich.用户输入了2个单词,即T = 2,但是电影在电影片名和演员阵容中都有这些术语,所以n = 2 * 2 = 4.鉴于此,最终的相关性将更加严重.缺乏正常化本身并不是问题,但在实践中,它可能会在未来导致许多错误.

现在让我们看一下公式的第二部分 - 1 / e^(ld/n).我们将其表示ld/n为x.在这种情况下,公式的第二部分将如下所示:

因此,对于高价值而言x,它将削弱最终的相关性.虽然我不明白为什么它必须是指数级的,但它仍然有意义.但x不是自变量,它本身就是2个变量的函数:x = x(ld, n).而且,ld也是一个函数:ld = ld(MAX_LD, T),所以x取决于3个不同的自变量/参数:x = x(MAX_LD, T, n).在这种情况下,很难预测x所有可能情况的行为(以及最终相关性).

建议

1.简化x().如果您希望公式的第二部分仅跟踪Levenshtein距离,则仅依赖于此距离,而不是所有3个独立变量.例如,您的公式可能如下所示:

甚至:

这里distance是实际的Levenshtein编辑距离,而不是功能T和MAX_LD.

2.使用词干.我知道,我知道,你说,你不能使用服务器端编程.但是你确定它无法在客户端执行吗？Steming似乎比它容易得多.大多数词干只是截断后缀和结尾,如"-s","-ing","-ment"等.这不是理想的,但我相信它会给出更好的结果,然后是Levenshtein距离.这里唯一强有力的限制是:必须使用词干 - 索引和搜索.

有关更精确的词干算法,请参阅Lucene来源的 PorterStemmer类.

3.使用反向记录频率.回想一下查询"John Malkovich"的例子.可能有很多电影用"约翰"这个词,但只有几部用"马尔科维奇".很自然地假设,第二项必须在搜索结果中具有更大的权重,然后是第一项.tf-idf在其idf(逆文档频率)部分中涉及这个事实.您可以通过计算逆记录频率来做同样的事情:

irf = number-of-all-found-records / number-of-records-with-current-term

并添加到您的相关性公式第三部分:

当然,请记住:在对真实数据进行测试之前,没有公式是好的.