Geohash應用——附近鄉鎮資訊挖掘（提升檢索召回與準確）
摘要
Geohash在LBS領域的應用開發很常見，常常應用於查詢附近的人或門店等應用程式中。這裏不再介紹Geohash的原理，其原理詳見：GeoHash核心原理解析。 這裏主要講一個Geohash的另一種應用：挖掘熱點地名/地址資訊，補充實體POI（Point Of interest)資訊，輔助擴大檢索召回。
目錄
一、背景介紹
在LBS檢索中，使用者檢索query往往是where+what的檢索，例如：q=桂平市西山鎮長安小學。爲了提高檢索準確率，必然是會想辦法解析出where，桂平市、西山鎮，然後給使用者查詢what=長安小學。如果提供給檢索的數據（這裏指POI點）資訊很全，比如：數據的地址欄位（addr）含有「西山鎮」，又或者名字欄位（name）包含西山鎮，例如：長安小學（西山鎮分校），又或者有其他地址資訊中包含「西山鎮」，都可以輔助引擎檢索召回，同時，當長安小學有很多時，數據欄位越豐富，越準確，還能進一步提升排序的合理性。
但現實世界往往是極其殘酷的，說的不誇張一點，提供給檢索引擎的數據，幾乎都是東拼西湊的，數據製作工藝參差不齊。數據資訊除了錯，最大的問題之一就是資訊不全，不夠精細。特別是對於那些多源數據融合的檢索數據，往往都存在類似問題。僅對LBS領域來說，一些小作坊的POI數據，往往存在缺失「省/市/區」三級以下的「地理資訊」，即鄉/鎮/村/道路/道路門牌等。在這樣的情況下，如何能夠給那些「地理」資訊不全的POI進行資訊補全呢？ 從而提高檢索的召回率與準確率。 此文，正是要討論解決的這一難題，它的解決方案，恰恰是Geohash的一個典型應用案例。
二、解決方案
思路：針對一個POI點，查詢它附近點的地理資訊。將附近點的地域資訊經過一定的篩選和過濾，然後賦值給該POI點上的某個欄位，從而補全該POI點的地理資訊。
不難發現，一提及「附近」，這就很容易想到Geohash。這裏提出一個極其簡單的解決方案，在實際應用中，各位還需結合自己的業務進行完善。
前提條件：
<1> 已有「地名地址資訊;行政區劃」類目的POI數據，此類數據爲：省、市、區、街道/鄉/鎮、村等行政區劃的POI數據;
<2> 每個POI數據均具有名稱、地址、省、市、區、經緯度、行政區劃編碼、類別等基礎欄位。
任務需求：利用以上「地名地址資訊;行政區劃」類目的POI數據，爲其他POI點補充「地理資訊」 ，新增hot_place欄位存放。
【注】 僅補充區級以下，不用補充省、市、區一級的地理資訊，因爲它們已經是基礎欄位資訊了。預設是必備的。
具體解決方案與步驟
<1> 利用Geohash演算法，對已有「地名地址資訊;行政區劃」類目的POI數據進行編碼，構建詞表，存放在
town_geohash.map檔案中。
<2> 遍歷目標POI數據，利用經緯度欄位計算出自身的Geohash值，再由該值查詢出其附近8個格子的Geohash值。
（類似9宮格，自身與其周邊的8個方格，具體如圖）；
<3> 利用步驟2得到的9個格子的Geohash值，查詢構建的行政區劃詞表（town_geohash.map），找出每個格子對應的行
政區劃數據（名稱和經緯度），並計算每個行政區劃數據與目標POI點的距離。
<4> 設定一個距離閾值r。目標POI點與要新增的行政區劃數據的距離必須小於r，才能 纔能成爲候選集。在候選集中，取距離
最近的行政區劃資訊，補充至目標POI上，並存入hot_place欄位。這裏的篩選條件，是最簡單的距離限制條件，並取
最小值。
以上4個步驟，就完成了任務需求。需要注意的是，步驟4中設定的距離閾值r，其實是影響到Geohash精度的選取的，即Geohash值的長度。這裏，需要注意；因爲步驟<1>構建詞表與步驟<2>計算每個目標POI點的Geohash，需保持相同的Geohash精度值（即長度）。
三、拓展與思考
上一節，在實現步驟<4>提到，篩選條件僅用了距離因子進行了限制。並最終選取距離最小的一個。篩選條件，是一個值得思考和深究的地方。它極大影響了新增「地理資訊」的準確率。
此文的任務需求是：增添行政區劃數據，一個POI在一個級別也就只有一個行政區劃資訊。所以，找距離最小的一個，在這個任務場景下，僅靠距離因素限制，一般問題也不大，往往準確率也能達標。 但如果增加的是「熱點地名，商圈」等地理資訊。比如，王府井，理想國大廈，望京，中關村等。僅利用距離因子作爲限制條件，現實情況下，準確率常常是不達標的。那麼，應該怎麼做呢？
如果是熱點地名與商圈的地理資訊補充，可以考慮，利用目標POI點與其周邊格子所處位置，進行限制。比如，必須呈包含目標POI點的態勢時，才能 纔能新增。怎麼定義包含態勢呢？這個讀者可以自行定義與實現。這裏舉2個範例：
a、目標點處於中心位，其餘8個格子都包含「望京」這樣一個商圈地理資訊。這是典型的包含態勢，目標POI點可增加商圈「望京」；
b、目標點上/下（南北），左/右（東西），對角線格子均具有相同的地理資訊，這種也可視爲呈包含態勢（ 大致如圖2-1所呈現的樣子）。
圖2-1，展示了目標POI點以及周邊8個格子的示意圖。可以想象每個Geohash的格子都包含了一些地理資訊。
爲了提高新增的「地理資訊」的準確度。總結一下，本人能想到的限制條件主要有以下3方面：
1、距離條件是基礎，必須有距離限制；
2、目標POI點所處格子與欲新增地理資訊所處格子的位置態勢進行限制；
3、爲目標POI點增加某一個地理資訊，該地理資訊在單個格子出現的次數，以及它被距離條件篩選後，總體出現的次數。
【注】某個地理資訊出現的次數：可理解爲有多少個POI具有該地理資訊。
四、程式碼實現
程式碼實現，使用的是scala語言。Scala可以方便的呼叫Java語言的jar包。因此，你也可以理解爲是Java實現的。這裏有利用了Java的兩個重要的jar包。
利用Spatial4j包計算兩個經緯度之間的球面距離；利用ch.hsr.geohash包獲取一個geohash周邊8個網格（geohash）的方法
<dependency>
<groupId>org.locationtech.spatial4j</groupId>
<artifactId>spatial4j</artifactId>
<version>0.7</version>
</dependency>
<dependency>
<groupId>ch.hsr</groupId>
<artifactId>geohash</artifactId>
<version>1.3</version>
</dependency>
以上兩個包都能計算Geohash值。Geohash的長度對應了不同的精度。長度與精度對照表如下（最長爲12）：
| geohash碼長度 | 寬度 |
高度 |
|---|---|---|
| 1 | 5,009.4km |
4,992.6km |
| 2 | 1,252.3km |
624.1km |
| 3 | 156.5km |
156km |
| 4 | 39.1km |
19.5km |
| 5 | 4.9km |
4.9km |
| 6 | 1.2km |
609.4m |
| 7 | 152.9m |
152.4m |
| 8 | 38.2m |
19m |
| 9 | 4.8m |
4.8m |
| 10 | 1.2m |
59.5cm |
| 11 | 14.9cm |
14.9cm |
| 12 | 3.7cm |
1.9cm |
按照第二章解決方案的1~4的步驟實現。這裏先要敲定距離閾值r，假定r=2公裡，則Geohash的長度應選5（即4.9km,4.9km的格子）。由對照表可知如果選擇Geohash長度爲6（對應1.2km，0.6km），構造出的9宮格，是不滿足需求的，會有漏掉滿足距離目標POI點爲2公裡的行政區劃POI點的。這是爲什麼，請大家自己思考吧。
先把行政區劃數據和結果詞表geohash_map詞表檔案的樣例貼出：
//這裏對行政區劃POI做了資訊抽取，直接是town-name city 經緯度，存放到town.txt檔案中，具體格式如下：
舒莊鄉 周口市 114.454095,33.509907
幸福鄉 樂山市 103.89755,28.939625
張家塬鎮 寶雞市 107.117532,34.699135
大林鄉 忻州市 112.723693,38.856616
穆店鄉 淮安市 118.605614,32.917239
//由town.txt構建的Geohash詞表，存放在geohash_map詞表中，第一列是5位的Geohash值，後面是城鎮資訊，具體格式如下：
wscey: 萬福鎮|吉安市|114.885236,27.419279
ws4wq: 新亨鎮|揭陽市|116.289072,23.624153
wqry3: 和川鎮|臨汾市|112.23623,36.264385
wt45m: 石鼻鎮|南昌市|115.573624,28.726617
ybe87: 鐵林街道|伊春市|128.833531,47.864312
wq3d9: 免古池鄉|臨夏回族自治州|103.42043,35.619691
步驟1： 利用行政區劃POI構建geohash_map詞表
/**
* @define 利用原始詞表town.txt構建geohash_map詞表.
* @param fpath
* @param output
* @param len
*/
def init_town_map(fpath: String, output: String, len: Int = 5): Unit = {
val geohash_map = scala.collection.mutable.Map[String, List[String]]()
Source.fromFile(fpath,"UTF-8").getLines().toList.filter(_.trim != "").foreach(line =>
{
val split_line = line.split("\t", -1)
if (split_line.size == 3) {
val town = split_line(0)
val city = split_line(1)
val loc = split_line(2).split(",", -1)
val geohash_code = get_geohash_code(split_line(2))
val tmplist = List[String](town + "|" + city + "|" + loc.mkString(","))
if (geohash_map.contains(geohash_code)) {
geohash_map(geohash_code) = geohash_map(geohash_code) ++ tmplist
} else {
geohash_map += (geohash_code -> tmplist)
}
}
})
val out = new PrintWriter(output)
for((k,v) <- geohash_map){
out.println(k+": " + v.mkString("\t"))
}
out.close()
}
/**
* @define 依據經緯度以及指定長度,計算Geohash值.預設長度指定爲5.
* @param loc_str
* @param len
* @return
*/
def get_geohash_code(loc_str:String,len:Int = 5):String = {
val loc = loc_str.split(",",-1)
val lon = loc(0).toDouble
val lat = loc(1).toDouble
val geohash_code = GeohashUtils.encodeLatLon(lat, lon, len)
geohash_code
}
步驟2：這裏給出瞭如何找出9宮格的Geohash值。程式碼實現時，不僅找到了9個方格的geohash，還給每個方案設定了標記值，標註方向。標記值與格子位置的對應關係如下圖所示。有了格子相對目標POI點的方向標註，後續纔可能實現第三節所說的依據「位置態勢」進行限制。其中，目標POI所處的格子，方向標註是MY。
import ch.hsr.geohash.GeoHash
import org.locationtech.spatial4j.context.SpatialContext
import org.locationtech.spatial4j.distance.DistanceUtils
import org.locationtech.spatial4j.io.GeohashUtils
/**
* @define 包括自己一共會找到9個格子(涵蓋自己和相鄰的8個格子),分別用標
* 記"MY,N,NE,E,SE,S,SW,W,NW"標記出格子的方位,其中MS,是該點自己所處格子的標記.
* @param lon
* @param lat
* @return
*/
def find_nearby_geohash(lon:Double,lat:Double):Array[Tuple2[GeoHash,String]] = {
val nearby_town_array = ArrayBuffer[Tuple2[GeoHash,String]]()
try{
val geohash:GeoHash = GeoHash.withCharacterPrecision(lat,lon,5)
nearby_town_array += Tuple2(geohash,"MY")
val nearby_town = geohash.getAdjacent
//N, NE, E, SE, S, SW, W, NW
val direct_flag_list = "N,NE,E,SE,S,SW,W,NW".split(",",-1)
for(i <- 0 until nearby_town.size){
val geohash_item = nearby_town(i)
val direct_flag = direct_flag_list(i)
nearby_town_array += Tuple2(geohash_item,direct_flag)
}
}catch {
case e:Exception => {}
}
nearby_town_array.toArray
}
步驟3：利用步驟2得到的9個格子的Geohash值，查詢構建的行政區劃詞表（town_geohash.map），找出每個格子對應的行政區劃數據（名稱和經緯度），並計算每個行政區劃數據與目標POI點的距離。
//存放所有找到的行政區劃數據（行政區劃的一些資訊值，存放爲String型別，與目標POI的距離，Double型別）
val all_nearby_towns = ListBuffer[Tuple2[String,Double]]()
//9個格子的geohash值和方向標註均被儲存在一個存放爲Tuple2型別的陣列中。遍歷這個陣列，獲取每個格子中的行政區劃數據（名稱，城市，經緯度）。
val nearby_town:Array[Tuple2[GeoHash,String]] = find_nearby_geohash(lon,lat) //find_nearby_geohash 在上面步驟2實現了該方法
if(nearby_town.size > 0){
nearby_town.foreach(geohash_item => {
val geohash_code = geohash_item._1.toBase32
val direct_flag = geohash_item._2
if(geohash_map.contains(geohash_code)){
val nearby_town_list = geohash_map(geohash_code).map(town_item => {
var item = Tuple2[String,Double](town_item,10000.0)
val tmparr = town_item.split("\\|",-1)
if(tmparr.size == 3){
val town = tmparr(0)
val gcity = tmparr(1)
val loc2 = tmparr(2).split(",",-1)
if(city == "" ){
val distance = get_distance(Tuple2(lon,lat),Tuple2(loc2(0).toDouble,loc2(1).toDouble))
item = (town_item+"|"+nearby_geohash,distance)
}else{
if(city.startsWith(gcity) || gcity.startsWith(city)){
val distance = get_distance(Tuple2(lon,lat),Tuple2(loc2(0).toDouble,loc2(1).toDouble))
item = (town_item+"|"+nearby_geohash,distance)
}
}
}
item
}).filter(_._2 <= 2.0 ) //此處，直接將距離大於2公裡的行政資訊都已剔除了
if(nearby_town_list.size > 0){
all_nearby_towns ++= nearby_town_list
}
}
})
}
/**
* @define 提供一對經緯度座標,計算兩個點的球面距離
* @param loc1
* @param loc2
* @return
*/
def get_distance(loc1:Tuple2[Double,Double], loc2:Tuple2[Double,Double]):Double = {
val geo:SpatialContext = SpatialContext.GEO
val geo_shape = geo.getShapeFactory
val p1 = geo_shape.pointXY(loc1._1,loc1._2)
val p2 = geo_shape.pointXY(loc2._1,loc2._2)
val distance:Double = geo.calcDistance(p1,p2) * DistanceUtils.DEG_TO_KM
get_litpoint_level(distance,2) //單位:km，該函數僅是設定獲取小數點後幾位。
}
def get_litpoint_level(num:Double,level:Int):Double = {
val bg:BigDecimal = new BigDecimal(num)
bg.setScale(level, BigDecimal.ROUND_HALF_UP).doubleValue()
}
步驟4：取距離最小的作爲新增的行政區劃資訊。這裏的程式碼實現方式是：將所有存放行政區化資訊的List，按照距離排序（升序）。然後，取第一個元素，即距離最小的那個行政區劃資訊。
//all_nearby_towns按照距離進行升序排序，步驟3的程式碼中已經限定了存放的元素都必須小於2公裡。
//所以，這裏沒有重複限定2公裡。都必定是<=2公裡的元素
val sort_nearby_towns = all_nearby_towns.sortWith(_._2 < _._2)
val nearest_town = sort_nearby_towns.head //取第1個元素，作爲新增的行政區劃資訊。
另外，這裏認爲，不存在同時有1個以上的行政區劃的點，與目標POI點的距離一樣。預設，最小值僅存在一個。因此，程式碼實現沒有考慮上述極端情況。
寫到這裏，4個步驟均以實現完成了。拓展一節中提到的更多篩選限制的條件。其實，在步驟3或步驟4中均可增加程式碼實現。比如，上述步驟3中的程式碼實現，如果認真閱讀，可以發現，程式碼實現中，多了一個城市的限定比較。行政區劃的數據資訊，它所歸屬的城市必須與目標POI所屬城市相同，才能 纔能進入候選集。否則，無論遠近，均不能作爲候選集。