<< 搜索引擎利用机器学习排序 - August_1989 - 博客频道 - CSDN.NET | 首页 | 使用Spark-MLlib进行内容推荐 >>

地理空间距离计算优化 - 美团点评技术团队

##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。

阅读全文……

标签 : ,



发表评论 发送引用通报