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

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

>匹配单词的数量(n):用户可以键入4个单词,但只有2个单词与一个项目匹配.越多越好.
> Levenshtein Edit Distance加法(ld).用户可以键入3个单词,但其中2个单词与索引的单词有拼写错误或其他小差异.我使用编辑距离来查找最近的索引字.所有Levenshtein距离的加法作为接近指标返回.越少越好.

要求

>客户端.没有Sphinx,Lucene或任何其他服务器端解决方案.
>速度超过准确性.该算法在每次击键时运行,我们不想让用户厌烦.保持大O不是那么大.
>非递归.每个项目相关性的计算不应该依赖于其他项目计算.我不想击败谷歌,只提供小套装的最佳效果.
>有界形式0到1,0到100或类似的东西.不是必需品,但能够显示“相关百分比”是一个加分.
>关于实施的想法.我正在寻找一种比特定实现更好的算法/公式.

我的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之间.

最后,问题

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

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

分析

让我们改写你的公式:

首先,请注意,n / T未规范化:可能会有更多结果(n),然后是搜索项(T).考虑这样的例子:用户输入查询“John Malkovich”,数据库中有电影Being John Malkovich.用户输入了2个单词,即T = 2,但是电影在电影片名和演员表中都有这些术语,因此n = 2 * 2 = 4.鉴于此,最终相关性将更加严格,然后是1.缺乏规范化不是问题本身,但实际上可能会导致将来出现一些错误.

现在让我们看看公式的第二部分 – 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个独立变量.例如,您的公式可能如下所示:

甚至:

其中距离是Levenshtein的实际编辑距离,而不是T和MAX_LD的函数.

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

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

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

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

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

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

相关文章
相关标签/搜索