基于坐标位置（Location）的聚类——特殊的kmeans

需求：
    在手机地图上，公交或者自驾，经常请求导航的起点终点。如何知道哪些是热点区域（特别是时间相关的热点区域）？

方法1：基于搜索的关键词 地名（用户输入的终点）进行文本聚类。然后将地名进行经纬度转换，即可找到热点区域。
方法2：基于用户终点的坐标。


方法1：对于做搜索的人来说，太熟悉不过，一个hash map就可以搞定了。但方法1的局限性很大，当用户不是输入关键词，而是gps导航等，是没有这些文本信息的。

方法2：
实际需求：给定很大的数据坐标集合（HDFS存储），如何按照自定义的聚类规则进行聚类？
采用geohash（实际是个四叉树过程，见另一篇博文写的内容），对坐标进行geohash后，然后mapreduce方式进行统计。reduce中进行聚合，实际上，最好不采用K个固定类聚合，而是依照类间距离来自适应聚类个数。



基于geohash方式的缺点：
（1）因为是类四叉树的hash，因此四叉树网格边界附近的点存在归类问题
（2）geohash有个精度问题（即最小网格），因此需要划分网格大小合适。如果网格划分太大，失去了聚类意义，太小，生成了太多网格，聚类性能降低。
优点：
（1）聚类复杂度 O(N),常见的kmeans 是O(N*K)，实际上，大数据量，这个完全不可接受

总之，对于大规模数据量的聚类算法，都需要预处理，来减小数据规模。而基于坐标数据的聚类，即采用geohash方式来减小聚类规模，这个是十分有效的方式。
而且，通常我们可以先用坐标将用户进行聚类，然后对某个聚类的所有用户，再采用普通的Kmeans来挖掘用户相关性，比如共同爱好。

————————————————————————————————————
重要的题外话：
我实际使用的聚类是按照geohash（四叉树）的层次聚类。
而且是自下而上的聚类方式。（四叉树的生成是自上而下）
即，开始网格大小 <dx,dy>,然后把聚类的结果，再次聚类(相当于四个叶子节点合并成一个节点）。
因此，最后形成了一个四叉树，每一层是该层的聚类结果。每一层的节点数，是在这个网格类的item数目。