面向地理標籤數據的高效聚類算法研究

《面向地理標籤數據的高效聚類算法研究》是依託同濟大學，由趙欽佩擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：面向地理標籤數據的高效聚類算法研究
• 項目類別：青年科學基金項目
• 項目負責人：趙欽佩
• 依託單位：同濟大學

中文摘要

隨著GPS設備和通訊技術的發展，日常生活中出現了大量的地理標籤數據。聚類分析是用以挖掘這類數據中所包含信息的一個有用的工具。但是，地理標籤數據屬性涉及領域較廣且通常數據量較大。因此，直接簡單地套用現有聚類方法，會產生效率低下、準確度降低、可理解程度差甚至時間或空間複雜度不可接受、聚類結果不可用等一系列問題。因此，本課題擬開展面向地理標籤數據的高效聚類算法的研究，提出複雜度低、實時性高和效果好的聚類算法。我們擬從兩方面進行研究：一是改進傳統聚類算法，形成新算法；二是融入領域知識，設計新算法。為了達到高效的目的，我們擬提出一種新的、基於類級別的有效性方法。在不增加原有算法的計算負擔下，可以將它與傳統聚類算法有效地結合起來以改進算法的缺陷。另外，考慮到地理標籤數據的地理屬性和特定領域屬性，我們提出新的基於格線的聚類算法。在格線算法基礎上，當融合其它領域屬性時，我們還可設計雙/多屬性的聚類方法。

結題摘要

隨著帶位置信息的數據的大量出現和增加，基於地理標籤數據的收集和分析是各種套用領域裡需要涉及的，比如城市規劃，交通治理，用戶畫像等。帶地理位置的數據可以包括GPS數據（經緯度，時間戳）、文本和圖像等，分析角度可以從位置出發，也可以從用戶出發，或者圖像出發。 聚類分析作為數據挖掘中一個主要的工具，傳統的方法很難完全適應到現有的數據中，比如，帶地理標籤的用戶，如果要對用戶根據地理位置信息進行自動分類，kmeans這種流行的聚類算法很難直接套用到該數據上。原因在於，kmeans需要定義距離來定義兩個數據之間的相似度，而兩個用戶之間的相似度很難直接用歐氏空間中的距離（e.g., 歐氏距離）來進行衡量。 本項目就帶地理信息的數據的高效聚類算法進行研究，側重在一是將傳統聚類算法改進以適應不同的數據類型，二是融入領域知識來設計聚類算法，最終減少算法複雜度，提高實時性。具體而言： （1） GPS數據的收集與分析，包括設計與實現了一個手機APP用以數據收集。並從基於聚類算法的計程車起停點感興趣區域生成，GPS軌跡數據的查詢和搜尋，電信基站數據進行位置預測，及可視化展現平台的設計等多方面開展了工作。 （2） 帶位置信息的多媒體數據，如yelp，大眾點評數據的分析。針對網站中商家的地理信息，來對用戶進行自動分類。在這部分工作中，需要定義兩個用戶間的相似度，我們利用樹結構來將原有的非結構化數據轉成結構化數據。為增加算法效率，以cover tree的數據結構來設計聚類算法，該算法比DBSCAN，Spectral clustering，層次聚類等均效率高。 本課題所開展的研究為多種不同帶地理標籤的數據（包括計程車GPS點數據，軌跡數據，電信基站數據，生活服務類數據）的分析提供了解決方案。