地理空间距离计算优化 - 美团点评技术团队
##4.2 简化距离计算公式方法
1)基本思路
我们的业务场景仅仅是在一个城市范围内进行距离计算,也就是说两个点之间的距离一般不会超过200多千米。由于范围小,可以认为经线和纬线是垂直的,如图所示,要求A(116.8,39,78)和B(116.9,39.68)两点的距离,我们可以先求出南北方向距离AM,然后求出东西方向距离BM,最后求矩形对角线距离,即sqrt(AMAM + BMBM)。

南北方向AM = R纬度差Math.PI/180.0;
东西方向BM = R经度差Cos<当地纬度数* Math.PI/180.0>
这种方式仅仅需要计算一次cos函数。
public static double distanceSimplify(double lat1, double lng1, double lat2, double lng2, double[] a) { double dx = lng1 - lng2; // 经度差值 double dy = lat1 - lat2; // 纬度差值 double b = (lat1 + lat2) / 2.0; // 平均纬度 double Lx = toRadians(dx) * 6367000.0* Math.cos(toRadians(b)); // 东西距离 double Ly = 6367000.0 * toRadians(dy); // 南北距离 return Math.sqrt(Lx * Lx + Ly * Ly); // 用平面的矩形对角距离公式计算总距离 } }
我们对这个方法的有效性和性能进行验证。
1.1)有效性验证
我们首先检验这种简化是否能满足我们应用的精度,如果精度较差将不能用于实际生产环境。
我们的方法叫distanceSimplify,lucene的方法叫distHaversineRAD。下表是在不同尺度下两个方法的相差情况。
| 测试点对 | distanceSimplify(米) | distHaversineRAD(米) | 差别(米) |
|---|---|---|---|
| (39.941,116.45)(39.94, 116.451) | 140.0285167225230 | 140.02851671981400 | 0.0 |
| (39.96, 116.45)(39.94, 116.40) | 4804.421262839180 | 4804.421153907680 | 0.0 |
| (39.96, 116.45)(39.94, 117.30) | 72444.81551882200 | 72444.54071519510 | 0.3 |
| (39.26, 115.25)(41.04, 117.30) | 263525.6167839860 | 263508.55921886700 | 17.1 |
可以看到两者在百米、千米尺度上几乎没有差别,在万米尺度上也仅有分米的差别,此外由于我们的业务是在一个城市范围内进行筛选排序,所以我们选择了北京左下角和右上角两点进行比较,两点相距有260多千米,两个方法差别17m。从精度上看该优化方法能满足我们应用需求。
1.2)性能验证
| POI数目 | 耗时(ms) |
|---|---|
| 5w | 0.5 |
| 10w | 1.1 |
| 100w | 11 |
2)进一步优化
我们看到这里计算了一次cos这一三角函数,如果我们能消除此三角函数,那么将进一步提高计算效率。
如何消除cos三角函数呢?
采用多项式来拟合cos三角函数,这样不就可以将三角函数转换为加减乘除了嘛!
首先决定多项式的最高次数,次数为1和2显然都无法很好拟合cos函数,那么我们选择3先尝试吧,注:最高次数不是越多越好,次数越高会产生过拟合问题。
使用org.apache.commons.math3这一数学工具包来进行拟合。中国的纬度范围在10~60之间,即我们将此区间离散成Length份作为我们的训练集。
public static double[] trainPolyFit(int degree, int Length){ PolynomialCurveFitter polynomialCurveFitter = PolynomialCurveFitter.create(degree); double minLat = 10.0; //中国最低纬度 double maxLat = 60.0; //中国最高纬度 double interv = (maxLat - minLat) / (double)Length; List<WeightedObservedPoint> weightedObservedPoints = new ArrayList<WeightedObservedPoint>(); for(int i = 0; i < Length; i++) { WeightedObservedPoint weightedObservedPoint = new WeightedObservedPoint(1, minLat + (double)i*interv, Math.cos(toRadians(x[i]))); weightedObservedPoints.add(weightedObservedPoint); } return polynomialCurveFitter.fit(weightedObservedPoints); } public static double distanceSimplifyMore(double lat1, double lng1, double lat2, double lng2, double[] a) { //1) 计算三个参数 double dx = lng1 - lng2; // 经度差值 double dy = lat1 - lat2; // 纬度差值 double b = (lat1 + lat2) / 2.0; // 平均纬度 //2) 计算东西方向距离和南北方向距离(单位:米),东西距离采用三阶多项式 double Lx = (a[3] * b*b*b + a[2]* b*b +a[1] * b + a[0] ) * toRadians(dx) * 6367000.0; // 东西距离 double Ly = 6367000.0 * toRadians(dy); // 南北距离 //3) 用平面的矩形对角距离公式计算总距离 return Math.sqrt(Lx * Lx + Ly * Ly); }
我们对此优化方法进行有效性和性能验证。
2.1)有效性验证
我们的优化方法叫distanceSimplifyMore,lucene的方法叫distHaversineRAD,下表是在不同尺度下两个方法的相差情况。
| 测试点对 | distanceSimplifyMore(米) | distHaversineRAD(米) | 差别(米) |
|---|---|---|---|
| (39.941,116.45)(39.94, 116.451) | 140.0242769266660 | 140.02851671981400 | 0.0 |
| (39.96, 116.45)(39.94, 116.40) | 4804.113098854450 | 4804.421153907680 | 0.3 |
| (39.96, 116.45)(39.94, 117.30) | 72438.90919479560 | 72444.54071519510 | 5.6 |
| (39.26, 115.25)(41.04, 117.30) | 263516.676171262 | 263508.55921886700 | 8.1 |
可以看到在百米尺度上两者几乎未有差别,在千米尺度上仅有分米的区别,在更高尺度上如72千米仅有5.6m米别,在264千米也仅有8.1米区别,因此该优化方法的精度能满足我们的应用需求。
2.2)性能验证
| POI数目 | 耗时(ms) |
|---|---|
| 5w | 0.1 |
| 10w | 0.3 |
| 100w | 4 |
#5 实际应用
坐标转换方法和简化距离公式方法性能都非常高,相比lucene使用的Haversine算法大大提高了计算效率,然而坐标转换方法存在一些缺点:
a)坐标转换后的数据不能被直接用于空间索引。lucene可以直接对经纬度进行geohash空间索引,而通过空间转换变成三维数据后不能直接使用。我们的应用有附近范围筛选功能(例如附近5km的团购单子),通过geohash空间索引可以提高范围筛选的效率;
b)坐标转换方法增大内存开销。我们会将坐标写入倒排索引中,之前坐标是2列(经度和纬度),现在变成3列(x,y,z),在使用中我们往往会将这数据放入到cache中,因此会增大内存开销;
c)坐标转换方法增大建索引开销。此方法本质上是将计算从查询阶段放至到索引阶段,因此提高了建索引的开销。
基于上述原因我们在实际应用中采用简化距离公式方法(通过三次多项式来拟合cos三角函数),此方法在团购筛选和商家筛选的距离排序、智能排序中已经开始使用,与之前相比,筛选团购时北京全城美食品类距离排序响应时间从40ms下降为20ms。
搜索引擎利用机器学习排序 - August_1989 - 博客频道 - CSDN.NET
首先,由人工标注训练数据。也就是说,对于某个查询Q,人工标出哪些文档是和这个査询相关的,同时标出相关程度,相关程度有时候可以用数值序列来表示,比如从1分 到5分为3个档次,1代表微弱相关,5代表最相关,其他数值代表相关性在两者之间。对于某个查询,可能相关文档众多,同时用户査询也五花八门,所以全部靠人工标注有时候 不太可能。此时,可以利用用户点击记录来模拟这种人工打分机制。
对于机器学习来说,输入是用户查询和一系列标注好的文档,机器学习系统需要学习打分函数,然后按照打分函数输出搜索结果,但是在其内部,每个文档由若干特征构成的,即每个文档进入机器学习系统之前,首先需要将其转换我饿滴特征向量,比较常用的特征包括:
• 查询词在文档中的词频信息
• 查询词的IDF信息
• 文档长度:
• 网页的入链数量:
• 网页的出链数量:
• 网页的pageRank值;
• 网页的URL松度:
• 査询词的Proximity值:即在文档中多大的窗口内可以出现所有査询词。
以上所列只是影响排序的一部分特征,实际上还有很多类似的特征可以作为特征向量中的一维加入。在确定了特征数量后,即可将文档转換为特征向量X,前面说过每个文档会人工标出其相关性得分y.这样每个文档会转換为<X,Y>的形式,即特征向量及其对应的相关性得分,这样就形成了一个具体的训练实例。
通过多个调练实例,就可以采用机器学习技术来对系统进行训练,训练的结果往在是 ―个分类函数或者回归函数,在之后的用户搜索中,就可以用这个分类函数对文档进行打分,形成搜索结果
从目前的研究方法来说,可以将机器学习揉序方法分为以下3种:单文档方法、文档对方法和文档列表方法。
3. 单文档方法(PointWise Approach》
单文档方法的处理对象是单独的一篇文档,将文档转换为特征向量后,机器学习系统根据从训练数据中学习到的分类或者回归函数对文档打分,打分结果即是搜索结果。下面我们用一个简单的例子说明这种方法。
图2是人工标注的训练集合,在这个例子中,我们对于每个文档采用了3个特征: 査询与文档的Cosme相似性分值、査询词的Proximity值及页面的PageRank数值,而相关性判断是二元的,即要么相关要么不相关,当然,这里的相关性判断完全可以按照相关程度扩展为多元的,本例为了方便说明做了简化。

图2 训练数据
例子中提供了5个训练实例,每个训练实例分别标出来其对应的查询,3个特征的得分情况及相关性判断。对于机器学习系统来说,根据训练数据,需要如下的线性打分函数:
Score(Q, D)=a x CS+ b x PM+cx PR+ d
这个公式中,cs代表Cosine相似度变徽,PM代表Proximity值变量,PR代表pageRank, 而a、 b、 c、 d则是变量对应的参数。
如果得分大于一设定阀值,则叫以认为是相关的, 如果小于设定闽值则可以认为不相关。通过训练实例,可以获得最优的a、 b,、c、d参数组合,当这些参数确定后,机器学习系统就算学习完毕,之后即可利用这个打分函数进行相关性判断。对于某个新的查询Q和文档D,系统首先获得其文档D对应的3个特 I特征值,之后利用学习到的参数组合计算两者得分,当得分大于设定的闽值,即可判断文档是相关文档,否则判断为不相关文档。
4. 文档对方法(PairWise Approach)
对于搜索系统来说,系统接收到用户査询后,返回相关文档列表,所以问题的关键是确定文档之间的先后顺序关系。单文档方法完全从单个文档的分类得分角度计算,没有考虑文档之间的顺序关系。文档对方法则将重点转向量对文档顺序关系是否合理进行判断。
之所以被称为文档对方法,是因为这种机器学习方法的训练过程和训练目标,是判断任意两个文档组成的文档对<D0C1,D0C2>是否满足顺序关系,即判断是否D0C1应该排在DOC2的前面。图3展示了一个训练实例:査询Q1对应的搜索结果列表如何转换为文档对的形式,因为从人工标注的相关性得分可以看出,D0C2得分最高,D0C3次之,D0C1得分最低,于是我们可以按照得分大小顺序关系得到3个如图3所示的文档对,将每个文档对的文档转换为特征向量后,就形成了一个具体的训练实例。

图3 文档对的方法训练实例
根据转换后的训练实例,就可以利用机器学习方法进行分类函数的学习,具体的学习方法有很多,比如SVM. Boosts、神经网络等都可以作为具体的学习方法,但是不论具体方法是什么,其学习目标都是一致的,即输入- 个査询和文档对<Docl,DOC2>, 机器学习排序能够判断这种顺序关系是否成立,如果成立,那么在搜索结果中D0C1应该排在D0C2 前面,否则Doe2应该摔在Docl前面,通过这种方式,就完成搜索结果的排序任务。
尽管文档对方法相对单文档方法做出了改进,但是这种方法也存在两个明显的问题:
一个问题是:文档对方法只考虑了两个文档对的相对先后顺序,却没有考虑文档出现在搜索列表中的位置,排在搜索站果前列的文档更为重要,如果前列文档出现判断错误,代价明显高于排在后面的文档。针对这个问题的改进思路是引入代价敏感因素,即每个文档对根据其在列表中的顺序具有不同的权重,越是排在前列的权重越大,即在搜索列表前列如 果排错顺序的话其付出的代价更高•
另外一个问题是:不同的査询,其相关文档数量差异很大,所以转换为文档对之后, 有的查询对能有几百个对应的文档对,而有的查询只有十几个对应的文档对,这对机器学习系统的效果评价造成困难 •我们设想有两个查询,査询Q1对应500个文文档对,查询Q2 对应10个文档对,假设学习系统对于査询Ql的文档对能够判断正确480个,对于査询 Q2的义格对能够判新正确2个,如果从总的文档对数量来看,这个学习系统的准确率是 (480+2)/(500+10)=0.95.即95%的准确率,但是从査询的角度,两个査询对应的准确率 分别为:96%和20%,两者平均为58%,与纯粹从文档对判断的准确率相差甚远,这对如何继续调优机器学习系统会带来困扰。
4. 文档列表方法(ListWise Approach)
单文档方法将训练集里每一个文档当做一个训练实例,文档对方法将同一个査询的搜索结果里任意两个文档对作为一个训练实例,文档列表方法与上述两种表示方式不同,是将每一个查询对应的所有搜索结果列表整体作为一个训练实例,这也是为何称之为文档列表方法的原因。
文档列表方法根据K个训练实例(一个査询及其对应的所有搜索结果评分作为一个实 例)训练得到最优评分函数F, 对于一个新的用户査询,函数F 对每一个文档打分,之后按照得分顺序由高到低排序,就是对应的搜索结果。 所以关键问题是:拿到训练数据,如何才能训练得到最优的打分函数?
这里介绍一种训练方法,它是基于搜索结果排列组合的概率分布情况来训练的,图4是这种方式训练过程的图解示意。

图4 不同评分函数的KL距离
首先解释下什么是搜索结果排列组合的概率分布,我们知道,对于搜索 引擎来说,用户输入査询Q, 搜索引擎返回搜索结果,我们假设搜索结果集合包含A. B 和C 3个文档,搜索引擎要对搜索结果排序,而这3个文档的顺序共有6种排列组合方式:
ABC, ACB, BAG, BCA, CAB和CBA,
而每种排列组合都是一种可能的搜索结果排序方法。
对于某个评分函数F来说,对3个搜索结果文档的相关性打分,得到3个不同的相关度得分F(A)、 F(B)和F(C), 根据这3个得分就可以计算6种排列组合情况各自的概率值。 不同的评分函数,其6种搜索结果排列组合的概率分布是不一样的。
了解了什么是搜索结果排列组合的概率分布,我们介绍如何根据训练实例找到最优的 评分函数。图4展示了一个具体的训练实例,即査询Q1及其对应的3个文档的得分情况,这个得分是由人工打上去的,所以可以看做是标准答案。可以设想存在一个最优的评分函数g,对查询Q1来说,其打分结果是:A文档得6分,B文档得4分,C文档得3分, 因为得分是人工打的,所以具体这个函数g是怎样的我们不清楚,我们的任务就是找到一 个函数,使得函数对Ql的搜索结果打分顺序和人工打分顺序尽可能相同。既然人工打分 (虚拟的函数g) 已知,那么我们可以计算函数g对应的搜索结果排列组合概率分布,其具体分布情况如图4中间的概率分布所示。假设存在两个其他函数h和f,它们的计算方法已知,对应的对3个搜索结果的打分在图上可以看到,由打分结果也可以推出每个函数对应的搜索结果排列组合概率分布,那么h与f哪个与虚拟的最优评分函数g更接近呢?一般可以用两个分布概率之间的距离远近来度量相似性,KL距离就是一种衡量概率分布差异大小的计算工具,通过分别计算h与g的差异大小及f与g的差异大小,可以看出f比h更接近的最优函数g,那么在这个函数中,我们应该优先选f作为将来搜索可用的评分函数,训练过程就是在可能的函数中寻找最接近虚拟最优函数g的那个函数作为训练结果,将来作为在搜索时的评分函数。
上述例子只是描述了对于单个训练实例如何通过训练找到最优函数,事实上我们有K 个训练实例,虽然如此,其训练过程与上述说明是类似的,可以认为存在一个虚拟的最优 评分函数g (实际上是人工打分),训练过程就是在所有训练实例基础上,探寻所有可能的 候选函数,从中选择那个KL距离最接近于函数g的,以此作为实际使用的评分函数。 经验结果表明,基于文档列表方法
的机器学习排序效果要好于前述两种方法。
(3)搜索与机器学习_李航博士_新浪博客
机器学习在互联网搜索中的应用
下面介绍一些基于统计机器学习的最前沿的互联网搜索技术。
排序学习
对给定的查询语句,将检索到的网页进行排序是排序学习的任务。排序学习将此问题形式化为监督学习的问题,将网页表示为特征向量,其中特征表示网页与查询语句的匹配程度或网页的重要度,基于标注数据学习一个排序模型。现在最常用的方法是LambdaMART [1]。该方法将排序问题转换为二类分类问题,利用Boosting算法优化学习目标函数。其最大特点是不显示地定义损失函数,而定义损失函数的梯度函数,以解决排序损失函数不易优化的问题。其他代表的排序学习方法还有Rank SVM [5]、 IR SVM [2]、AdaRank [10]等。
网页重要度学习
网页重要度学习旨在计算出每个网页的重要度,排序时将重要的网页尽量排在前面。传统的网页重要度计算基于超链接与PageRank算法。直观上,有许多链接指向的网页重要,网页的重要度可以通过链接在网上传播;PageRank用马尔可夫模型实现这一直观。可以认为最近提出的BrowseRank算法 [6]是PageRank算法的扩展与补充。BrowseRank首先根据用户行为数据构建用户浏览图。然后再在用户浏览图上定义连续时间马尔可夫过程,用其平稳分布表示网页的重要度。直观上,用户在网页上平均停留时间越长,网页就越重要;转移到网页的次数越高,网页就越重要。基于用户的互联网使用行为数据,BrowseRank能够更好地计算网页重要度。
匹配学习
查询语句与网页的相关性靠两者的匹配程度决定,匹配结果直接影响搜索结果。比如,查询“ny times”应与含有“new york times”的网页匹配。理想的匹配应该是语义上的匹配,而不是关键字上的匹配。匹配学习的目的在于将字面上并不相同,但语义相同的查询语句与网页匹配上,将语义相关的网页排在搜索结果的前面。代表的方法有翻译模型 [3]与隐空间模型 [9]。日志数据中记录了用户点击。比如用户搜索“ny”,因为既含有“ny”又含有“new york”的网页会被搜到,所以两者通过用户搜索中的点击得以联系。隐空间模型方法基于点击数据将查询语句与网页投影到隐空间,在隐空间中学习到查询语句与网页之间的相似度,也就是匹配关系,进而能对新的查询语句与网页的匹配程度作出判断。比如,学到“ny”与“new york”的相似度,判断“ny times”与“new york times”是可以匹配的。
话题模型学习
查询语句与网页应该在话题上也能匹配,比如,查询语句是“jaguar car”,那么关于jaguar汽车的网页是与查询相关的,而关于动物jaguar的网页即使含有jaguar与car这两个字,往往也是不相关的。话题模型学习旨在自动从索引网页中抽出所有可能的话题,以及每个网页的话题,以便在搜索时,进行查询语句与网页在话题上的匹配。话题模型学习的方法很多,有概率方法,如PLSI、LDA,也有非概率方法,如LSI、NMF、RLSI。互联网搜索需要处理大规模网页数据,最近提出的RLSI [7] 方法有很好的扩展性、能够在大规模网页数据上进行高效的话题模型学习。
查询语句转换学习
10-15%的英文查询语句含有拼写错误;中文查询语句中含有许多拼音汉字转换错误,如“新浪”被误转换为“新郎”。除此之外,查询语句中还有许多不规范、不准确的表述。搜索引擎一般能够自动纠正拼写等错误,将不正确的查询语句转换为正确的查询语句。代表的方法有CRF-QF [3]、LogLinear [8]等。例如,LogLinear方法从日志数据中收集大量的含有拼写错误的查询语句,以及相应的正确的查询语句,从中提取转换规则,自动学习拼写转换的对数线形模型。搜索时,对新的查询语句试用各种转换规则,根据对数线形模型,找出最有可能的转换,即纠正,如果转换的概率足够大,就对查询语句实施转换。
3.互联网搜索的挑战与机遇
帮助用户尽快、尽准、尽全地找到信息,从本质上需要对用户需求(查询语句),以及互联网上的文本、图像、视频等多种数据的内容进行“理解”。也就是要解决人工智能的挑战。这种意义上,互联网搜索永远需要面对且克服这一挑战。
互联网搜索遵循幂率分布,有头部查询(高频查询)与尾部查询(低频查询)。人工智能挑战在尾部与头部体现出不同的特点。
回到图灵测试。也许经过几轮测试,图灵就会发现互联网搜索对头部的查询能给出很好的结果,但是对尾部的查询结果常常不很理想。互联网搜索主要还是基于关键字匹配。因为尾部查询没有足够多的信号,比如点击数据,有时查询语句与网页不能有很好的匹配,搜索引擎无法做出正确的相关度判断。匹配学习能解决一部分问题,但是还有很长的路要走。
十大最热门的大数据技术
-
预测分析:随着现在硬件和软件解决方案的成熟,许多公司利用大数据技术来收集海量数据、训练模型、优化模型,并发布预测模型来提高业务水平或者避免风险;
-
NoSQL数据库:非关系型数据库包括Key-value型(Redis)数据库、文档型(MonogoDB)数据库、图型(Neo4j)数据库;
-
搜索和知识发现:支持信息的自动抽取,可以从多数据源洞察结构化数据和非结构化数据;
-
流式分析:软件可以对多个高吞吐量的数据源进行实时的清洗、聚合和分析;
-
内存数据结构:通过动态随机内存访问(DRAM)、Flash和SSD等分布式存储系统提供海量数据的低延时访问和处理;
-
分布式存储系统:分布式存储是指存储节点大于一个、数据保存多副本以及高性能的计算网络;
-
数据可视化:数据可视化技术是指对各类型数据源(包括Hadoop上的海量数据以及实时和接近实时的分布式数据)进行显示;
-
数据整合:通过亚马逊弹性MR(EMR)、Hive、Pig、Spark、MapReduce、Couchbase、Hadoop和MongoDB等软件进行业务数据整合;
-
数据预处理:数据整合是指对数据源进行清洗、裁剪,并共享多样化数据来加快数据分析;
-
数据校验:对分布式存储系统和数据库上的海量、高频率数据集进行数据校验,去除非法数据,补全缺失。






