面向地理标签数据的高效聚类算法研究

With the development of GPS devices and telecommunication techniques, geo-tagged data has been commonly seen in our daily life. Cluster analysis is an important and useful tool for mining the information behind the data. Since the geo-tagged data usually has a large size and is related to different areas, applying the existing clustering algorithms directly on the geo-tagged data brings problems such as low efficiency, low accuracy, difficulty of interpretting results, or even unacceptable time or space complexity and unreusable results. Therefore, the project is going to work on the clustering algorithms with high efficiency and effectiveness for geo-tagged data. We will perform the study and propose new algorithms from two aspects: one is to improve the existing algorithms and the other is to study and merge knowledge from other areas. In order to obtain high efficiency, a new cluster-based validity method is going to be proposed and studied. Without increasing the time complexity of the original algorithm, the new validity method can be employed into the design of a new algorithm by well merging into an existing algorithm. Besides, a new grid-based clustering algorithm is to be proposed by considering the geographical feature of the geo-tagged data especially. When other features, which are related to different areas, are involved, a dual/multiple clustering algorithm can be considered.

随着GPS设备和通讯技术的发展，日常生活中出现了大量的地理标签数据。聚类分析是用以挖掘这类数据中所包含信息的一个有用的工具。但是，地理标签数据属性涉及领域较广且通常数据量较大。因此，直接简单地应用现有聚类方法，会产生效率低下、准确度降低、可理解程度差甚至时间或空间复杂度不可接受、聚类结果不可用等一系列问题。因此，本课题拟开展面向地理标签数据的高效聚类算法的研究，提出复杂度低、实时性高和效果好的聚类算法。我们拟从两方面进行研究：一是改进传统聚类算法，形成新算法；二是融入领域知识，设计新算法。为了达到高效的目的，我们拟提出一种新的、基于类级别的有效性方法。在不增加原有算法的计算负担下，可以将它与传统聚类算法有效地结合起来以改进算法的缺陷。另外，考虑到地理标签数据的地理属性和特定领域属性，我们提出新的基于网格的聚类算法。在网格算法基础上，当融合其它领域属性时，我们还可设计双/多属性的聚类方法。

随着带位置信息的数据的大量出现和增加，基于地理标签数据的收集和分析是各种应用领域里需要涉及的，比如城市规划，交通治理，用户画像等。带地理位置的数据可以包括GPS数据（经纬度，时间戳）、文本和图像等，分析角度可以从位置出发，也可以从用户出发，或者图像出发。.聚类分析作为数据挖掘中一个主要的工具，传统的方法很难完全适应到现有的数据中，比如，带地理标签的用户，如果要对用户根据地理位置信息进行自动分类，kmeans这种流行的聚类算法很难直接应用到该数据上。原因在于，kmeans需要定义距离来定义两个数据之间的相似度，而两个用户之间的相似度很难直接用欧氏空间中的距离（e.g., 欧氏距离）来进行衡量。.本项目就带地理信息的数据的高效聚类算法进行研究，侧重在一是将传统聚类算法改进以适应不同的数据类型，二是融入领域知识来设计聚类算法，最终减少算法复杂度，提高实时性。具体而言：.（1）.GPS数据的收集与分析，包括设计与实现了一个手机APP用以数据收集。并从基于聚类算法的出租车起停点感兴趣区域生成，GPS轨迹数据的查询和搜索，电信基站数据进行位置预测，及可视化展现平台的设计等多方面开展了工作。.（2）.带位置信息的多媒体数据，如yelp，大众点评数据的分析。针对网站中商家的地理信息，来对用户进行自动分类。在这部分工作中，需要定义两个用户间的相似度，我们利用树结构来将原有的非结构化数据转成结构化数据。为增加算法效率，以cover tree的数据结构来设计聚类算法，该算法比DBSCAN，Spectral clustering，层次聚类等均效率高。.本课题所开展的研究为多种不同带地理标签的数据（包括出租车GPS点数据，轨迹数据，电信基站数据，生活服务类数据）的分析提供了解决方案。