GeoMesa-HBase索引篇——理论准备
目录
1. 数据标准化方法
1.1 数据标准化的背景
数据的标准化(normalization)是将数据按比例缩放，使之落入一个小的特定区间。在某些比较和评价的指标处理中经常会用到，去除数据的单位限制，将其转化为无量纲的纯数值，便于不同单位或量级的指标能够进行比较和加权。
假设对3名新生婴儿体重（5，6，7）和3名成年人的体重（150，151，152）差异的大小进行对比分析，从表面上看，两组人员的平均差异均为1斤，由此便得出两组人员的体重差异程度相同显然是不合适，因为两者的体重水平不在同一等级上，即量纲不同。
对多个指标进行综合分析，假设对商品的运营指标销售量、销售额、浏览量进行综合评价或聚类分析，由于各指标间的水平相差很大，如果直接进行分析会突出数值较高的指标在综合分析中的作用，从而使各个指标以不等权参与运算。
因此，常常需要先对数据进行标准化，对各统计指标进行无量纲化处理，消除量纲影响和变量自身变异大小和数值大小的影响。
而对于时空数据，同样存在这样的量纲不统一的问题。例如时 间上，其单位为秒、分钟、小时，而在空间上，其单位又根据坐标系的不同，会选择不同的量度体系。如果选择大地坐标系，这个量度的标准就是度，如果选择空间直角坐标系，这个量度就变成了米、千米。因此这个矛盾同样是非常突出的，需要通过数据标准化的方式来解决。
在GeoMesa当中，在进行数据的预处理的过程当中，就用到了数据标准化的方法，使得时空数据可操作。而数据标准化的方法在统计学中非常多，其中比较有代表性的方法就是Max-Min标准化方法和Z-score标准化方法。
1.2 Max-Min标准化/极差标准化
该方法将某个变量的观察值减去该变量的最小值，然后除以该变量的离差，其标准化的数值落到[0,1]区间，转换函数为：x’=(x-min)/(max-min)，其中max为样本的最大值，min为样本的最小值。其过程可以表达如下
对序列x1，x2，…，xn进行变换：
则新序列y1，y2，…，yn ∈ [0,1] 无量纲。
该方法对原始数据进行线性变换，保持原始数据之间的联系，其缺陷是当有新数据加入时，可能导致max或min的变化，转换函数需要重新定义。GeoMesa当中采用的数据标准化方法就是这种方法。
1.3 Z-score标准化/标准差标准化/零均值标准化
该方法将某变量中的观察值减去该变量的平均数，然后除以该变量的标准差，标准化后的数据符合标准正态分布。转化为数学表达式如下：
上式中，x是原始数值，u是样本均值，σ是样本标准差。回顾下正态分布的基本性质，若x～N(u,σ2),则有
其中，N（0,1）表示标准正态分布。
可以看出，z-score标准化方法试图将原始数据集标准化成均值为0，方差为1且接近于标准正态分布的数据集。然而，一旦原始数据的分布 不 接近于一般正态分布，则标准化的效果会不好。该方法比较适合数据量大的场景(即样本足够多，现在都流行大数据，因此可以比较放心地用)。此外，相对于min-max归一化方法，该方法不仅能够去除量纲，还能够把所有维度的变量一视同仁(因为每个维度都服从均值为0、方差1的正态分布)，在最后计算距离时各个维度数据发挥了相同的作用，避免了不同量纲的选取对距离计算产生的巨大影响。所以，涉及到计算点与点之间的距离，如利用距离度量来计算相似度、PCA、LDA，聚类分析等，并且数据量大(近似正态分布)，可考虑该方法。相反地，如果想保留原始数据中由标准差所反映的潜在权重关系应该选择min-max归一化，
2. GeoHash算法
2.1 GeoHash概述
Geohash是将整个地图或者某个分割所得的区域进行一次划分，由于采用的是base32编码方式。即Geohash中的每一个字母或者数字（如wx4g0e中的w）都是由5bits组成（2^5 = 32，base32），这5bits可以有32中不同的组合（0~31），这样我们可以将整个地图区域分为32个区域，通过00000 ~ 11111来标识这32个区域。第一次对地图划分后的情况如下图所示（每个区域中的编号对应于该区域所对应的编码）：
Geohash的0、1串序列是经度0、1序列和纬度0、1序列中的数字交替进行排列的，偶数位对应的序列为经度序列，奇数位对应的序列为纬度序列，在进行第一次划分时，Geohash0、1序列中的前5个bits（11100），那么这5bits中有3bits是表示经度，2bits表示纬度，所以第一次划分时，是将经度划分成8个区段（2^3 = 8），将纬度划分为4个区段（2^2 = 4），这样就形成了32个区域。如下图：
2.2 GeoHash实现流程
2.2.1 将经纬度转化为二进制编码
以经纬度值：（116.389550， 39.928167）进行算法说明，对纬度39.928167进行逼近编码 (地球纬度区间是[-90,90]）
- 区间[-90,90]进行二分为[-90,0),[0,90]，称为左右区间，可以确定39.928167属于右区间[0,90]，给标记为1
- 接着将区间[0,90]进行二分为 [0,45),[45,90]，可以确定39.928167属于左区间 [0,45)，给标记为0
- 递归上述过程39.928167总是属于某个区间[a,b]。随着每次迭代区间[a,b]总在缩小，并越来越逼近39.928167
- 如果给定的纬度x（39.928167）属于左区间，则记录0，如果属于右区间则记录1，序列的长度跟给定的区间划分次数有关
2.2.2 合并经纬度数据为一个数据（生成莫顿码）
偶数位放经度，奇数位放纬度，把2串编码组合生成新串如下图：
2.2.3 按照base32编码集进行编码
首先将11100 11101 00100 01111 0000 01101转成十进制，对应着28、29、4、15，0，13 十进制对应的base32编码就是wx4g0e,如下图
2.3 GeoHash算法的问题
现在大多数采用GeoHash算法的软件采用的都是Peano曲线（Z曲线），这种曲线最大的问题就是容易出现空间的突变问题。例如在下面右图当中，虽然编码为0111的点和编码为1000的点虽然在编码上是非常接近的，但是实际上，两个点的空间位置是非常远的。
所以在实际操作当中，往往在计算空间距离时，会对每个点周围的点进行计算，这算是对于这种索引机制的一种补充。
2.4 GeoHash算法的展望
在现有的空间填充曲线理论当中，已经有了一些方案，如下图。可以看出，这些填充曲线都是为了能够将空间当中所有的数据利用一定的规律来进行排序，实现降维的操作。结合前面GeoHash算法面临的问题，可以看出，在众多的空间填充曲线的解决方案当中，希尔伯特曲线（Hilbert）的突变性是最低的，同样这个方案也是很多空间数据开发者推荐的一个方案。但是这种方案的计算开销比较大，而且算法实现是比较困难的，尤其是如果延伸到三维数据，这样的编码往往会更加复杂。所以大多数现有的利用GeoHash算法的软件采用的也都是peano曲线，不过在以后，随着空间数据库的发展，这个方案是一个非常不错的发展方向。