力搜索算法

A. 优化算法笔记（十七）万有引力算法

（以下描述，均不是学术用语，仅供大家快乐的阅读）
万有引力算法（Gravitational Search Algorithm）是受物体之间的万有引力启发而提出的算法。算法提出于2008（2009）年，时间不长，不过相关的文章和应用已经相对较多，也有不少的优化改进方案。
万有引力算法中，每一个物体的位置代表了一个可行解，而物体的质量则反映了该位置的好坏，位置越好的物体的质量越大，反之物体的质量越小（质量由适应度值计算出，不是直接相等）。物体在解空间中的运动方式由其他物体的引力决定，质量越大的物体，在同等引力作用下的加速度较小，所以单位时间内的速度也相对较小，位移距离较短，反之加速度和速度都较大，位移距离较长。故可以简单的认为， 位置越优的个体的移动速度越慢，位置越差的个体的移动速度越快 。

万物之间皆有万有引力，不过在我们谈到万有引力之时，对象大多是天体，否则万有引力太小可以忽略不计。所有这次我们的主角就是天体了。（总不可能是苹果吧）。

每一个天体都有个属性：位置X，质量M，加速度A，以及速度V，还有适应度值F。
在D维空间内有N个天体，其位置为

，加速度

，速度

，其适应度值为

。

第i个天体的质量则是根据其适应度值计算得出：

其中M为天体的质量在群体重质量中的占比， 分别表示全局最差天体的适应度值和全局最优个体的适应度值。
可以看出，处于最优位置的天体的质量m为1，最差位置的天体的质量m为0。当最优天体和最差天体重合时，所有的天体的质量m都为1。

由万有引力计算公式和加速度公式可以计算出当前天体收到另一个天体万有引力而产生的加速度：

其中R表示第i个天体和第j个天体之间的欧式距离，aij为天体i在第d维上受到天体j的万有引力而产生的加速度,ai为第i个天体受到的其他所有天体万有引力的合力产生的加速度。G为万有引力常量，可以根据一下公式计算：

其中G0为初始值，T为最大迭代次数。

计算出了天体的加速度，则可以根据当前速度计算出下一步天体的运行速度以及天体下一步的位置。

这一步比较简单与粒子群、蝙蝠等有速度的算法一致。

可以看出万有引力算法的流程异常的简单，与经典的粒子群差不多。万有引力算法也可以看做是一个优化改进版的粒子群，不过设计比较巧妙，引入的质量、加速度等概念，但实现仍然很简单。万有引力算法的效果如何，在下一节将会进行实验测试。

适应度函数 。
实验一：

从图像中可以看出，各个天体都在不停的运动，由于没有贪心算法（优于当前值才改变位置）的加入，所以个天体有可能运动到比原先位置更差的地方，而且其收敛速度也比较快。
从结果上看，似乎还不错，受到最差值的影响均值也相对较大，算法结果的稳定性不是太好。
直觉上感觉算法有点问题。根据物理得来的直觉告诉我，这些天体会相互靠近，所以，它们不会集中到它们所构成的凸包之外， 凸实心物体的质心不会跑到该物体的外部 。做个试验验证一下，将测试函数的最优解设置到一个极端的位置。
实验二 ： 适应度函数

这次最优解位置在（90,90）处，该点有很大概率出现在初始天体所围成的凸多边形外。

从图像中可以看出，在天体们还没有到达最优位置附近（右下角的红点）时，它们已经收敛于一个点，之后则很难再次向最优解靠经。看结果可以发现几乎每一次实验的结果都不太好，算法果然有点问题，不过问题不大。
万有引力出现这种现象可能有两个原因： 1.算法收敛的太快 ，还未对全局进行充分搜索之时就收敛到了一点，收敛到一点后无法再运到。 2.算法没有跳出局部最优的策略 ，万有引力作用下的天体慢慢聚集到奇点，形成黑洞，无法从中逃离。
那接下来，对万有引力算法的改进方向也比较明确了：1.减缓其收敛速度，2增加跳出局部最优操作，使之逃离黑洞。
看看万有引力常量G的函数图像

将万有引力常量的值修改为随着迭代次数线性下降，从图像中可以看出，效果还是比较明显的，天体在不断的运动，最后才收敛、聚集于一起。从实验结果也可以看出，算法相对稳定。结合图像可以知道，改进后，算法的收敛性下降，但全局搜索能力有较大的提升，算法的结果不会很差但是精度较低。

将万有引力常量的下降趋势放缓为原来的1/4，从图像中可以看出，算法的收敛速度非常快，也得到了较好的结果，相比线性下降，算法有着更好的精度，不足之处则是没有跳出局部最优的操作，收敛过快也容易陷入局部最优。
不知道原文为什么让万有引力常量G的如此快的降到0，明明降的更慢能有更好的全局搜索能力，但精度可能较差。猜测如果精度较差则在测试函数结果和曲线上比不赢对比的其他算法，论文没法发了。其使用的测试函数的最优解大多处于解空间的中心位置附近，即很少出现最优解在天体所围成的凸多面体之外的情况，而实际问题中我们是无法预知最优解在个位置的。
接下来，将试着为万有引力算法加入一点跳出局部最优的操作。

实验四 ：改进,新增以下规则及操作
在实验二的条件下
1 . 处于最优位置的天体保持自己的位置不动.
2 . 如果某一个天体的运动后的位置优于当前全局最优个体的位置则将当前的最优个体初始化到解空间的随机位置.(将被自己干掉的大哥流放)。
3 . 如果触发了规则2，将所有的个体的以迭代次数重置为0，即计算G=G0*e^(-20t/T)中的t置为0，重新计算万有引力常量，若未触发条件2则t=t+1。

从图像上看，算法的全局搜索能力有大幅的增强，并且已经集中到了最优解的附近，而且由于加入了“流放”这一跳出局部最优的操作，可以看出，不断的有新的个体出现在距最优位置较远的位置。不过收敛速度有所下降，因此局部搜索能力有一定减弱。
看结果，好像没有实验三那么好，但与实验二相比，已经有了很大的提升，而且有了跳出局部最优的操作，结果也相对稳定。
上述的实验仅仅是对直观猜想的实现，如果想以此为改进点，还要对其进行大量的调优，相信会有不错的结果。

万有引力算法根据万有引力提出，结合了牛顿第二定律，可以说其操作步骤与真实的物理规律非常的贴切。不过就像前文说过，受物理现象启发而来的优化算法其性能是未知的，因为它们不具备智能，只有着规律，有规律就会存在弱点，就会有搜索盲区。宇宙那么大，肯定存在没有任何天体到达过的空间。
不过由于万有引力算法流程简单，理解方便，其优化方案和能改进的地方相对较多。万有引力算法的收敛速度过快，导致其全局搜索能力较弱而局部搜索能力很强，容易陷入局部最优。根据其特点，我们可以降低其收敛速度或者增加跳出局部最优操作，来平衡算法的各个性能。

参考文献
Rashedi E , Nezamabadi-Pour H , Saryazdi S . GSA: A Gravitational Search Algorithm[J]. Information Sciences, 2009, 179(13):2232-2248. 提取码：xhpa

以下指标纯属个人yy,仅供参考

目录
上一篇 优化算法笔记（十六）混合蛙跳算法
下一篇 优化算法笔记（十八）灰狼算法

优化算法matlab实现（十七）万有引力算法matlab实现

B. 论淘宝搜索推荐算法排序机制及2021年搜索的方向。

[写在前面]淘宝搜索引擎至今反复多次，搜索顺序也从最初的统计模型升级到机械学习模型，到2010年为止没有标签没有基础标签，随着计算能力的提高，2010年后开始挖掘用户的基础标签，从3年到2013年开始使用大规模的机械学习和实时特征
但你有没有想过为什么2016-2017年的两年是各种各样的黑搜索盛行的一年，为什么今天几乎消失了？
最根本的原因是从统计算法模型到机械学习模型的转型期。
说白了，这时不收割就没有收割的机会。因为统计模型即将退出历史舞台。
因此，各路大神各自扩大了统计模型算法中的影响因素。统计算法无论在哪里，点击率和坑产都很容易搜索。
那两年成了中小卖家的狂欢盛宴，很多大神的烟火也是旺盛的。
今天推荐算法的第三代使用后，加上疫情的影响进行了鲜明的比较，真的很感慨。
淘宝真的没有流量了吗？电器商务真的做不到吗？还是大家的思维没有改变，停留在2016-2017年的黑搜宴会上不想醒来？
2017年、2018年、2019年是淘宝推荐算法反复最快的3年，每年的算法升级都不同，整体上到2019年9月为止统计算法模型的影响因素还很大，从2019年下半年开始第三代推荐算法后，全面的真正意义进入了以机械学习模型为中心的推荐算法时代。
各路大神也无法验证，加上百年疫情的影响，很多大神的隐蔽布也泄露了。
基本上以统计模型为主，训练基本上没有声音，典型的是坑产游戏。
如果现在还能看到的话，基本上可以判断他不是在训练，而是在制作印刷用纸，一定会推荐使用资源，资源是多么安全。
刷子的生产增加真的没有效果吗？不是我以前的文章说:不是不行，而是从坑产的角度思考，而是从改变竞争环境的角度思考，用补充书改变竞争环境，改变场地，有新的天地，任何手段都要为商业本质服务。
正文
概述统计算法模型时代。
统计模型时代搜索引擎的排名是最原始的排名思考，如果你的类别不错，关键词比较正确，就能得到很大的流量，当时产品需求少，只要上下架的优化就能使产品上升。
到2016年为止没有坑产游戏吗？黑色搜索的效果不好吗？其实，什么时候坑产是最核心的机密，谁来教大家，什么时候教的最多的是类别优化，关键词优化，大部分优化都围绕关键词，电器商的老人想起了你什么时候得到关键词的人得到了世界。
有人告诉我做坑产，关键词找到生意也来了。什么时候知道坑产也没有人给你刷子，大规模的补充书也出现在黑色搜索盛行的时期。
为什么关键词者得天下？
搜索关键词是用户目前意图最直观的表达，也是用户表达意图最直接的方式。
搜索的用户购物意图最强，成交意愿也最强，现在搜索也是转化率最高的流量来源。
统计时代关键词背后直接依赖的是类别商品，只要制作类别和关键词分词即可，哪个时代最出现的黑马通常是类别机会、关键词机会、黑科学技术机会。
最基本的是商业本质，什么时候产品需求少，没有很多现在的类别，自己找类别，现在想想什么概念。
记得什么时候类别错了，搜索也可以来。如果你的商品点击反馈好的话，错误的类别没有什么影响，现在试试吧
搜索类是搜索的基础。
什么时候能称霸，背后有商业逻辑，用户行为数据好就行了。
但无论如何发展检索都离不开关键词。例如，上述关键词是用户表达意图的最直接的方法，是当前消费者的检索行为和购买行为发生了根本性的变化。
检索依然根据消费者的行为数据和关键词来判断需求，这就是机械学习模型时代。
机器学习模式时代-推荐搜索算法。
现在的商品体积和消费者购物行为的丰富性，统计算法不能满足检索的本质要求。
所以现在搜索引擎开始发展深度学习模式更精细的建模-推荐搜索算法，搜索排名更智能。
在此重点讨论推荐检索算法，
2017、2018、2019是推荐检索算法真正意义发展的3年，3年3个系统版本每年更换一次，很多电器商人都不知道头脑。
推荐检索算法和统计算法模型的最大区别在于，Query的处理能力和算法有召回机制
简单表示推荐算法的程序:
1:对检索关键词进行分词、重写的处理进行类别预判
2:根据用户信息，即用户以前的行为数据记录和预测的性别、年龄、购买力、店铺喜好、品牌喜好、实时行动作等信息存档
3:根据检索用户信息，根据检索用户以前的行为数据检索引擎和预测的性别、年龄、购买力、店铺喜好、品牌喜好、实时行动作为等信息存档3:根据检索用户信息的检索用户信息
也就是说，在第一关召回阶段基本上与统计模型时代的最佳化途径相同，核心是标题分词和类别，现在最大的区别是根据用户信息推荐最佳化，这是标签和正确人群标签图像最佳化的基本意义。
为什么现在一直在谈论标签，谈论人标签图像？入池实际上是为了匹配真正的消费者用户信息，通过直通车测试来判断人群也是为了通过性别、年龄和购买力来优化匹配真正的消费者。
召回机制:
通过构建子单元索引方式加快商品检索，不必经历平台上亿级的所有商品。该索引是搜索引擎中的倒置索引，利用倒置索引初始筛选商品的过程是召回阶段。
在这个阶段，不会进行复杂的计算，主要是根据现在的搜索条件进行商品候选集的快速圈定。
之后再进行粗排和精排，计算的复杂程度越来越高，计算的商品集合逐渐减少，最后完成整个排序过程。
主要召回路径分为
1:语言召回
2:向量召回
这些都是商业秘密不方便的说明，有兴趣的是学习我们的在线会员课程标签重叠游戏6是基于语言和向量召回的基础逻辑实战落地的课程。
下一阶段进入粗行列，粗行列受这些因素的影响:
粗行列作为召回后的第一个门槛，希望用户体验以时间低的模型快速排序和筛选商品，第一关系将过滤到不适合本次检索词要求的商品
为了实现这个目的，首先要明确影响粗排名得分的因素
1:类别匹配得分和文本匹配得分，
2:商品信息质量(商品发布时间、商品等级、商品等级)
3:商品组合得分
点击得分
交易得分卖方服务商业得分
在粗排列框架下，系统粗排列算法根据商品类别的预测得分进行得分
点击得分交易得分
交易得分卖方服务商业得分粗排列框架下，系统粗排列的大排列
最后是精排，检索顺序的主要目标是高相关性、高个性化的正确性。
每个用户的喜好不同，系统会根据每个用户的Query结合用户信息进行召回。然后通过粗排后，商品数量从万级下降到千级。
千级商品经排后直接向用户展示，搜索过程中商品集合的思考和具体变化如下图

前面的召回、粗排主要解决主题相关性，通过主题相关性的限制，首先缩小商品集合和我们的在线会员课程标签
精排阶段系是真正系统推荐算法发挥真正威力时，应根据用户行为反馈迅速进行机械学习建模，判断用户真实性、准确性和可持续控制性。
为什么现在的游戏和黑色技术暂时出现，核心是系统算法模型机械学习模型，系统分析用户有问题，不正确，不稳定，维持性差，可以迅速调整。
也就是说，即使发现脆弱性，研究快速有效的方法，系统也会根据你精排阶段的用户行为迅速分析学习建模，发现模型有问题，你的玩法就结束了。
猜机器学习建模的速度有多快？
想玩黑色的东西早点死去吧。
现在使用的检索顺序模型主要是
CTR模型和CVR模型，具体模型过于复杂也不需要深入，但影响这两种模型的最基本因素是用户行为数据
真的不能假的，假的也不能假的算法模型越来越智能化，算法越来越强，只有回归商业本质才能真正解决算法模型背后真正想解决的问题，算法基于商业逻辑。
2021年搜索向哪个方向发生变化:
2020年电器商人和蚂蚁是不平凡的一年。2020年也是蚂蚁从神坛上拉下来的元年，现在蚂蚁有各种各样的黑色。
基于中小卖家的走势无疑是阿里必须正面面对的现实。
如何让中小卖家回流或留在平台上，搜索该怎么做？
检索一定是基于三方的考虑，买方、卖方和平台本身，现在市场上又开始提倡坑产搜索逻辑，坑产妖风又开始，根据推荐搜索算法逻辑来谈这个问题。
为什么坑产思维是不死的小强，每次危机都会跳出来。
以统计模型为中心的坑产时代是淘宝从2003年到2015年一直使用的搜索算法模型长达13年。
同时也是淘宝和中国网分红的野蛮生长期，统计算法模式让太多电商赚钱。除了
之外，十年的奴役思维已经习惯了，在电器商圈，坑产游戏一定有人相信，其他人不一定被认可。所以，我们夹着尾巴发展的原因，时间真的可以证明一切，不用多说，做自己。
习惯性思维加上特殊时期的赚钱蝴蝶效应，使许多电器商人活在历史的长梦中。正确地说，统计算法模型的真正废除是在2019年下半年。
同学说坑产永远有效，我也这么想。
永远有效的是起爆模型坑产权重驱动和统计算法模型中的坑产排名不同。
起爆模型的坑产要素永远有效，这永远不会改变。
但是，如何有效地加上这个起爆模型的坑产权重，并不像模仿购物的意图那么简单。
坑产游戏在2021年绝对不行。淘宝不会把现在的算法系统换成15年前的。
基于三方利益:
购买者体验
卖方利益
平台的发展
搜索肯定会向高精度和高控制性发展。以标签为中心的用户标签图像仍然是影响流量精度的基本因素。
必须从标签的角度考虑和优化种子组的图像。
通过种子组的图像向相似人扩展到叶类人，业界喜好人最后向相关人扩展也是扩大流量的过程渠道。
基于推荐搜索算法逻辑:
精密排列阶段算法更强，精度更高，转化率更高，持续稳定性更强。
基于中小卖方流通的现状，优化精排阶段并非中小卖方能够简单接触。
推荐算法从搜索排名阶段出现在哪个阶段？
个人判断
一是召回阶段
二是粗排阶段
上述提到召回阶段的算法简单复盖商品为万级，排序规则也比较简单，中小卖方在召回阶段提高精度尤为重要。
在这个万级商品库中，如上下架的权重上升，中小卖方有机会上升到主页，从子单元的索引召回中寻找机会。
或者根据中小卖方的新产品和中小卖方的店铺水平进行特别优先搜索推荐，使中小卖方的新产品在低销售状态下显示，可以实现锦囊算法。
中小卖方有机会搜索主页，不调用用户信息直接打开主页的展示权可能是中小卖方最大的支持。
根据召回阶段的用户行为数据，在粗排阶段以比例融入用户信息，即标签的影响。
在初始召回阶段，类别和分词权重，看业者主图场景反应背后的人们反馈，用系统引导，给中小卖方真正参考的流量方向和成交方向。
谁疯狂地印刷用纸直接关闭黑屋，理解印刷用纸优化竞争场景，从优化人群的角度出发，适当放宽处罚。
通过召回阶段，得到的用户信息会影响粗体结果。在这个阶段，用户信息的权重比例不应该太大，流量卡也不应该太死。
在各检索顺序阶段用户信息，即用户标签对检索的影响权重的问题。
这个方向我的个人观点是可能的。

C. 谈谈几种接触搜索算法的比较麻烦告诉我

接触分析计算主要是接触界面的搜寻方法和法向接触力的计算问题.
常见的有主从面法、级域法和一体化算法 是接触点的搜索算法，这三种算法中，最早的是主从面法，主从面法中从节点不允许穿透主动面，但主动面上的接触点可以穿透从动面。故主从面法只需搜寻与主动面接触的节点。主从面法的一个缺陷是——不能处理同一个接触面内发生的情况，比如子接触问题。与其他两种方法相比，主从面法只考虑接触体中一半的接触点，所以其计算工作量是比较小的。级域法在相互靠近的接触块中寻找接触对；一体化算法总是在所有的接触块中寻找。由于计算方法的不同，这三种方法计算时间依赖于接触面的大小。另一方面主从法之所以被广泛采用，是他的算法很成熟，编程也容易，而级域法需要从高到低逐级进行，编程就很困难，而且其矢量化运算能力也不行。
所以总体来说，一体化算法是最优越的。
除了这三种算法，还有一些别的算法：比如 BCM，边界搜索，近些年一些智能算法也被广泛引入进来！
除了接触点的搜寻算法，常用的接触力算法为：拉格朗日乘子法和罚函数法。拉格朗日乘子法不允许接触边界的互相穿透，能准确描述几何约束条件，是一种精确的接触力算法，但它与显式算法不相容，要求特殊的数值处理。但该方法在每个接触点处要求引入乘子，导致系统自由度的增加，使计算效率降低。而罚函数法允许接触面之间的互相穿透，并通过罚子将接触力大小和接触边界的穿透量联系起来，接触力正比于边界穿透量。此方法比较简单单也适合于显式算法，能在系统自由度不增加的情况下进行数值求解。但它影响显式算法中的临界时间步长。罚因子的好坏还影响计算结果的可靠性。

D. 有赞搜索引擎实践(算法篇)

注：转自于 有赞

在上篇文章(工程篇)中, 我们介绍了有赞搜索引擎的基本框架. 搜索引擎主要3个部件构成. 第一, hadoop集群, 用于生成大规模搜索和实时索引; 第二, ElasticSearch集群, 提供分布式搜索方案; 第三, 高级搜索集群, 用于提供商业搜索的特殊功能.

商业电商搜索由于搜索的特殊性, 独立的ElasticSearch集群是无法满足多样的算法需求的, 我们在搜索的各个部件上都有相应的算法插件, 用于构建商业电商搜索引擎的算法体系.

创建索引过程从原始数据创建倒排索引的过程. 这个过程中我们对商品(doc)进行分析, 计算商品静态分, 并对商品进行相似度计算. 商品的静态分对于提升搜索引擎质量起到至关重要的作用, 相当于网页搜索的pagerank, 想象一下如果没有pagerank算法, 网页搜索的质量会有多么差. 在电商搜索中, 最常见的问题是相似商品太多, 必须在建立索引过程中就对商品间的相似度进行预计算, 以便在检索过程中进行有效去重.

创建索引的过程如下.

step 1. 计算每个doc的静态分
step 2. 计算两两doc的相似度
step 3. 根据相似度和其他信息对数据进行分库
step 4. 建立ES索引

检索过程是搜索引擎接收用户的query进行一系列处理并返回相关结果的过程. 商业搜索引擎在检索过程中需要考虑2个因素: 1) 相关性 2) 重要性.

相关性是指返回结果和输入query是否相关, 这是搜索引擎基本问题之一, 目前常用的算法有BM25和空间向量模型. 这个两个算法ElasticSearch都支持, 一般商业搜索引擎都用BM25算法. BM25算法会计算每个doc和query的相关性分, 我们使用Dscore表示.

重要性是指商品被信赖的程度, 我们应该吧最被消费之信赖的商品返回给消费者, 而不是让消费之自己鉴别. 尤其是在商品充分竞争的电商搜索, 我们必须赋予商品合理的重要性分数, 才能保证搜索结果的优质. 重要性分, 又叫做静态分, 使用Tscore表示.

搜索引擎最终的排序依据是:

Score = Dscore * Tscore

即综合考虑静态分和动态分, 给用户相关且重要的商品.

检索的过程大致抽象为如下几个步骤.

step 1. 对原始query进行query分析
step 2. 在as中根据query分析结果进行query重写
step 3. 在as中使用重写后的query检索es
step 4. 在es查询过程中根据静态分和动态分综合排序
step 5. 在as中吧es返回的结果进行重排
step 6. 返回结果

下面几章阐述几个重点技术.

在电商搜索引擎里面商品的静态分是有网页搜索里面的pagerank同等的价值和重要性, 他们都是doc固有的和查询query无关的价值度量. pagerank通过doc之间的投票关系进行运算, 相对而言商品的静态分的因素会更多一些. 商品静态计算过程和pagerank一样需要解决如下2个问题: 1. 稳定性. pagerank可以保证一个网站不会因为简单链接堆砌可以线性提升网站的排名. 同样, 商品静态分的计算不可以让商品可以通过增加单一指标线性增加分值(比如刷单对搜索引擎的质量的影响).
2. 区分度. 在保证稳定性的基础上商品静态分要有足够的区分度可以保证同样搜索的条件下, 排在前面的商品的质量比排在后面的商品的质量高.

我们假设商品的静态分有3个决定性因素, 1.下单数, 2. 好评率 3. 发货速度

静态分我们使用Tsocre表示, Tscore可以写成如下形式:

Tscore = a * f(下单数) + b * g(好评率) + c * h(发货速度)

a,b,c是权重参数, 用于平衡各个指标的影响程度. f,g,h是代表函数用于把原始的指标转化成合理的度量.

首先, 我们需要寻找合理的代表函数.

z-score 标准化方法

这种方法非常不稳定, 假设一个奇异点是第二大的值的1000倍, 会让大部分的值都集中在0~0.01, 同样失去了归一化的目的.

(图三: log-zscore归一化)

最后, 选择合适的权重 经过log-zscore归一化以后, 我们基本上吧f,g,h的表示的代表函数说明清楚. Tscore = a f(下单数) + b g(好评率) + c*h(发货速度), 下一步就是确定a,b,c的参数. 一般有两个方法:

a) 专家法. 根据我们的日常经验动态调整权重参数;
b) 实验法. 首先在专家的帮助下赋一个初始值, 然后改变单一变量的方法根据abtest的结果来动态调整参数.

商品标题去重在电商搜索中起到重要作用, 根据数据, 用户通过搜索页购买商品80%选择搜索的前4页. 商品标题的重复会导致重要的页面没有含金量, 极大降低了搜索的购买率.

举个例子:

Title1:美味/香蕉/包邮/广东/高州/香蕉/banana//无/催熟剂/

Title2:美味/香蕉/广东/高州/香蕉//非/粉蕉/包邮/

首先, 进行特征向量化

这里用到 "bag of word" 技术, 将词汇表作为空间向量的维度, 标题的每个term的词频作为这个feature的值. 以这个例子来说. 这个词汇的维度为: 美味(0), 香蕉(1), 包邮(2), 广东(3), 高州(4), banana(5),无(6), 催熟剂(7),非(8),粉蕉(9) 位置: 0,1,2,3,4,5,6,7,8,9

Title1: 1,2,1,1,1,1,1,1,0,0
Title2: 1,2,1,1,1,0,0,0,1,1

这个每个title都用一个固定长度的向量表示.

再次, 计算两两相似度

相似度一般是通过计算两个向量的距离实现的, 不失一般性, 在这里我们使用1-cosine(x,y)来表示两个向量的距离. 这是一个"All Pair Similarity"的问题, 即需要两两比较, 复杂度在O(n^2). 在商品量巨大的时候单机很难处理. 我们给出两种方法用于实现"All Pair Similarity".

方法一: spark的矩阵运算.

方法二: map-rece 线性方法. 这个方法参考论文"Pairwise Document Similarity in Large Collections with MapRece". 可以实现几乎线性的时间复杂度. 相对于矩阵运算在大规模(10亿以上)pair similarity 运算上面有优势. 这个方法简单的描述如下: 首先, 按照倒排索引的计算方式计算每个term到doc的映射. 比如3个doc:

转化为倒排格式, 这个需要一次mapper rece

然后, 对于value只有一个元素的过滤掉, 对于value大于2个doc的两两组合:

最后, 对于输出进行聚合,value为重复次数和两个doc乘积开根号的比.

对于2个title1, title2, 如果X(title1, title2) > 0.7 则认为title1和title2相似, 对于相似的两个doc, 静态分大的定义为主doc, 静态分小的定义为辅doc. 主doc和辅doc分别建库.

区别于网页搜索(网页搜索直接将辅doc删除), 我们将主doc和辅doc分别建库. 每一次搜索按比例分别搜主库和辅库, 并将结果融合返回. 这样可以保证结果的多样性.

店铺去重和商品标题去重有点不同. 由于电商特定场景的需要, 不希望搜索结果一家独大, 这样会引发强烈的马太效应. 店铺去重不能使用如上的方法进行. 因为上面的方法的主要依据是文本相似, 在结果都相关的前提下, 进行适当的取舍. 但是店铺去重不是这样的特性.

设想一下, 如果我们根据店铺是否相同, 把同一店铺的商品分到主库和从库中, 如下图所示.

A和B代表不同的店铺.

在搜索香蕉的时候, 的确可以控制A店铺结果的数量, 但是在搜索"梨"的时候就错误的吧B店铺的梨排在前面了(假设A:梨比B:梨静态分高).

搜索的过程每个桶平均分摊搜索任务的25%, 并根据静态分合并成一页的结果. 这样同一保证结果的相对顺序, 又达到了店铺去重的目的.

如上图所示, 搜索"香蕉", 虽然A店铺有10个满足需求的结果, 但是每页搜索醉倒只有5个结果可以展示.

上面介绍了几个建立索引过程中几项技术, 检索过程中的关键技术有很多. 其中最着名的是query分析技术. 我们使用的query分析技术主要包括核心词识别, 同义词拓展, 品牌词识别等等. query分析技术大部分都是NLP研究范围, 本文就不详细阐述很多理论知识. 我们重点介绍同义词拓展技术. 这个技术一般都需要根据自己的商品和和用户日志特定训练, 无法像分词技术和品牌词识别一样有标准的库可以适用.

同义词拓展一般是通过分析用户session日志获取. 如果一个用户输入"苹果手机"没有得到想要的结果, 他接着输入"iphone", 我们在"苹果手机"和"iphone"之间创建一个转移关系. 基于统计, 我们可以把用户query创建一个相互联系的权重图.

用户输入query "苹果手机", 根据query分析, "苹果手机"有 "iphone" 0.8, "iphone 6" 0.5 两个同义词. 0.8和0.5分别表示同义的程度. 我们想要"苹果手机", "iphone", "iphone 6" 3个query同时输入, 并且按照同义的程度对不同的query赋予不同的权重. ElasticSearch提供的BoostingQuery可以支持这个需求. 参考: https://www.elastic.co/guide/en/elasticsearch/guide/current/ boosting query_clauses.html

原始query:

改写后的Query

其他比如核心词识别, 歧义词纠正等方法差不多, 本文不做详细阐述.

商业电商搜索算法另外两个重要技术, 一个是类目体系建立和应用,另一个是个性化技术. 这个两项技术我们还处在探索阶段. 类目体系我们主要使用机器学习的方法进行训练, 个性化主要通过用户画像进行Query改写来实现. 等我们上线有效果在与大家分享.

搜索算法是一个非常值得一个电商产品持续投入的技术. 一方面我们技术人员要有良好的技术背景, 可以借鉴很多成熟的技术, 避免重复造轮子; 另一方面, 每个产品的搜索都有自身的特点, 需要深入研究产品的特性给出合理的解决方案. 本文给出的案例都具有代表性, 灵活的运用搜索的各方面的技术. 另外, 商业搜索非常看重投入产出比, 我们也需要在众多方案中寻找捷径. 比如我们在做类目体系时候, 没有投入大量的人力资源用于标注数据, 而是通过爬虫爬取其他电商的数据进行参考, 从而节省了80%的人力资源. 由于笔者能力有限, 文中的方案不保证是问题的最优解, 如果有指正, 请联系笔者( [email protected] ).