基于高斯混合模型的時空大數據挖掘算法

郭慶豐 黨鵬飛 劉亞明 任建吉

摘?要：時空大數據在各領域中得到了持續的運用，推動著新研究模式的產生。但是，傳統數據存取中、分析與挖掘方法則很難支持新研究模式的形成。時空數據的探索性增長以及社交媒體和位置傳感技術的出現，使得為分析大數據而開發新的、高效的計算方法十分必要。傳統的數據挖掘算法大多是基于小型數據集開展的研究，通常忽略了計算效率，而是更側重于識別能力的研究。針對傳統算法的不足，本文介紹了基于高斯混合模型（GMM）的時空大數據挖掘算法，在GPU上并行了GMM聚類算法，結果顯示，模型具有較高的可擴展性和較低的計算成本，但仍需要新的方法來有效地模擬空間和節奏的限制。

關鍵詞：高斯模型；時空大數據；聚類算法；數據挖掘

1?概述

在過去的十年中，時空大數據領域的論文數量不斷上升，如下圖所示，時空大數據的出現，推動并促成了信息系統各方面的創新，已成為數據挖掘領域的研究熱點，在國內外贏得了廣泛關注。從硬件、算法、軟件到應用，它促進了不同傳統學科的融合，從而實現了新的研究方向。與常規數據分析不同，大時空數據分析對信息屬性提出了更高的要求，要求具有全新的構架，為了找出各領域趨勢與規律的同時，能夠更加高效地取得成果，其中包括人的動態、交通擁堵、智慧城市、行業演變、醫療與健康問題、大腦科學及其他。隨著信息技術和網絡技術的飛速發展，大時空數據以驚人速度增長，對其進行挖掘和利用已成為學術界與工業界關注的焦點。

過去十年時空大數據相關論文的發表數量趨勢圖

時空數據挖掘作為新的研究方向，正在努力發展并應用正在出現的計算技術，以對海量進行分析、高維時空數據，挖掘時空數據中蘊含的寶貴信息。

然而在具體研究應用中，傳統數據處理和分析方法已無法滿足時空大數據高效存取、實時處理、智能挖掘的性能需求。一方面，時空數據量大，種類多，填補了資料匱乏的空白，能最大限度地滿足各種研究需要，并進一步促進交叉研究深化；另一方面，結合時空大數據的特征，探究時空對象、事件及其他元素的關聯關系也是當前存在的巨大挑戰。

自20世紀末開始，隨著計算機應用能力的大幅度提升，數據挖掘技術逐漸成為一項成熟的技術，在分類、預測、數據挖掘方面的優勢尤為明顯［1］。在算法性能方面，由于傳統數據挖掘算法往往是基于常規數據集進行挖掘計算的，隨著級別的升高，算法的效率明顯降低，尤其是在推廣到TB級別甚至是PB級別。本文介紹了基于高斯混合模型（GMM）的時空大數據挖掘算法，有效地解決了傳統算法的不足。

2?算法

由于時空大數據具有復雜性和目標的多樣性，產生了許多分析方法，包括但不限于聚類、預測和變化檢測。作為最重要的方法之一，聚類已被廣泛用于許多應用［2］，如醫學和交通領域的圖像分割問題。

時空數據聚類通常是基于空間和時間相似度，把具有相似行為的數據集進行時空對象劃分，在進行劃分時，應該保持劃分后的數據集組與組的差別應盡量大，為同一組內的數據集差異應盡可能的小。

在本節中，我們選用了一種基于高斯混合模型（GaussIan?Mixture?Models，GMM）的聚類算法［3］，因為它的數學形式簡單，其參數的表達也是封閉式的，可以在復雜的多模態數據中取得較好的聚類性能，有效地解決了多模態數據聚類性能不佳的問題。

該算法的核心思想是：GMM由幾個高斯分布組成，原始數據由這些分布生成，服從相同的獨立高斯分布的數據被認為屬于同一個聚類。它的優點在于，能夠更真實地給出歸屬的概率，通過改變分布、集群的數量等，具有相對較高的可擴展性，并得到發達的統計學的支持［4］。而缺點在于，涉及許多對聚類結果有很大影響的參數，時間復雜度相對較高。

基于GMM的聚類算法由兩個子問題組成。首先，我們必須估計模型參數。其次，我們需要確定GMM中的成分數量。

2.1?設置GMM參數

首先，我們通過假設訓練數據集Dj是一個由M個成分組成的有限高斯混合模型產生的，來解決模型參數估計的問題。如果這些成分的標簽都是已知的，那么問題就會簡化為通常的參數估計問題，我們可以使用最大似然估計法（Maximum?Likelihood?Estimation，MLE）。

基于GMM的聚類方法使用MLE找出每個數據點的最大對數相似性概率，該值代表此數據點被劃分至該聚類的概率最大，被劃分至其他聚類的概率最小。在這種方法中，數據元素的每一個組成部分都與一些概率能力相關聯，因此它們的總和將等于1。

假設每個樣本xj來自一個超級種群D，它是由有限數量（M）的集群D1，…，DM按一定比例α1，…，αm分別組成的混合體，其中∑Mj=1αi=1，αi0i=1，…，M?，F在，我們可以將數據D=xini=1建模為獨立產生于以下的混合密度：

pxi|Θ=∑Mj=1αjpjxi|θj（1）

LΘ=∑ni=1ln∑Mj=1αjpjxi|θj（2）

這里pixi|θi對應于混合物j，并以θj為參數，Θ=α1，…，αm，θ1，…，θm表示與M成分混合物密度有關的所有未知參數。一般來說，式（2）很難優化，因為它含有對數函數ln。然而，當存在未觀察到的（或不完整的）樣本時，這個方程被大大簡化了。

現在我們簡單介紹一下最大似然估計法，算法第一步是使用當前的參數，并以觀察到的樣本為條件，使對數似然函數進行期望最大化。算法第二步，重新計算參數值。EM算法在這兩步中不斷迭代，直到達到收斂。對于多變量正態分布，期望值E.，用pij表示，是高斯混合物j產生數據點i的概率，其公式為：

pij=Σ^j－1/2e－12xi－μ^jtΣ^j－1xi－μ^j∑Ml=1Σ^l－1/2e－12xi－μ^ltΣ^l－1xi－μ^l（3）

α^kj=1n∑ni=1pij（4）

μ^kj=∑ni=1xipij∑ni=1pij（5）

Σ^kj=∑ni=1pijxi－μ^kjxi－μ^kjt∑ni=1pij（6）

2.2?聚類

一旦GMM被擬合到訓練數據上，我們就可以使用該模型來預測每個群組的標簽。標簽的分配是使用最大似然（MLE）程序進行的。由MLE原理給出的判別函數g（.）如下所示：

gi（x）=-ln｜∑i｜-（x-μi）t｜∑i｜-1（x-μi）（7）

對于每個特征向量，如果gix在所有聚類標簽中是最大的，我們就分配一個聚類標簽i。

3?模型評估

GMM模型擬合的計算復雜度取決于計算期望值（E）和最大化（M）步驟的迭代次數和時間。

假設訓練數據集的大小為N，成分數為M，維度為d，那么E和M步驟的計算成本在每次迭代中分別為ONMD+NM和O2NMD。另外，空間前張力會產生額外的迭代條件模式（ICM），從而增加成本。我們為基于GMM的空間半監督學習開發了一個有效的解決方案，即在GPU上并行了GMM聚類算法。實驗環境為具有240個CUDA核心和1GB內存的GTX285，初步結果顯示，在學習部分有160倍的出色可擴展性。學習部分通常計算成本高，I/O密集度低，因為我們必須處理小的訓練數據，通常是總數據的3%～5%。然而，對于聚類，即為數據中的每個特征向量分配標簽。聚類算法的性能受到I/O的影響，其主要原因是，與學習相比，計算聚類要求適度。因此，我們需要高效的I/O方案來擴大大數據集的聚類規模。

4?應用與挑戰

4.1?時空大數據挖掘的應用

時空數據挖掘被廣泛應用，如交通運輸、地質災害監測和預防、氣象研究、競技體育、犯罪分析、公共衛生以及醫療和社會網絡應用。例如，為了解決智能交通中人們在道路上的出行問題，分析和挖掘車輛的運行狀況和人流的運動規律，可以實現對交通狀況的跟蹤和實時預測［5］。

此外，從經濟角度來看，時空大數據分析報告可用于工業信貸風險控制。還可以根據客戶的消費習慣、地理位置、消費時間等因素，達到精準營銷的目的，更精準地投放廣告。大數據分析技術用于加速內部數據的處理、使用全球數據、找出業務運營的薄弱環節等。

在科技方面，以數據挖掘為基礎開展智能化分析，能夠提高規劃方案制訂效率及準確度，從而優化資源配置，節約成本。

就社會管理而言，大數據作為數據資源的典型代表，其來源非常廣，數據粒度較小時記錄單元零碎，結構多元化使人文知識在獲得、標注、對比和采樣等方面發生根本性變化、闡釋和表現方式。同時，大數據具有豐富的語義表達能力、多維空間感知能力、時空關聯表達能力及復雜系統自適應學習能力，能夠有效提高人類認知水平和智能程度。通過地理、氣象等交通運輸及其他自然信息與經濟、社會、文化的關系，發掘人口和其他人文社會信息，可為城市規劃提供有力決策支持，增強城市管理服務的科學性、前瞻性。其中最重要的就是數據挖掘技術在智慧城市中的應用，它能夠幫助我們快速地發現問題和解決問題，從而提高政府的辦事效率，改善民生，推動經濟社會發展。

4.2?時空大數據挖掘面臨的挑戰

時空數據實質上為非結構化數據，不但包括時序數據模型，還有圖模型。在傳統存儲模式下，由于空間、計算資源以及內存需求的限制，大量復雜而龐大的時空數據檢索與查詢變得非常困難，甚至不能進行。在圖模型基礎上，算法一般具有較大的時間復雜度，針對海量數據，甚至連O（N）復雜度都不能忍受［6］。此外，由于空間位置信息在地理空間信息中具有重要作用，對時空數據進行存儲與檢索時將直接影響到后續分析處理。

已有時空數據多來自GPS、遙感與傳感器及其他裝置，每一種裝置所產生的數據格式與數據形式都是不一樣的。因此，在時空數據預處理的過程中，實現時空數據的高效融合、清洗、轉換與提取是一個重要課題。

結語

時空大數據雖然開辟了新的應用，但也帶來了一些挑戰。我們不僅需要新的方法來克服這些挑戰，還需要新的模型來明確、有效地模擬空間和節奏的限制［7］，在壓縮和采樣領域需要進一步研究，特別是需要將空間數據挖掘工作流程與云計算、原地、數據空間等現代計算基礎設施相結合。

而現在，人工智能算法的開發為大數據挖掘算法的研究提供了一種全新的模式與手段。本文在對大數據分析研究基礎上提出一種基于人工智能算法的數據挖掘技術，通過該技術可以解決數據稀疏性問題，同時還能夠有效地減少人工參與程度。人工智能算法更多的是一種“黑箱”模式，隱藏了底層數據挖掘的過程，使得大數據挖掘變得更加便捷。

參考文獻：

［1］關雪峰，曾宇媚.時空大數據背景下并行數據處理分析挖掘的進展及趨勢［J］.地理科學進展，2018，37（10）：13141327.

［2］Shi?Z，PunCheng?L?S?C.Spatiotemporal?data?clustering：a?survey?of?methods［J］.ISPRS?international?journal?of?geoinformation，2019，8（3）：112.

［3］Vatsavai?R?R，Ganguly?A，Chandola?V，et?al.Spatiotemporal?data?mining?in?the?era?of?big?spatial?data：algorithms?and?applications［C］//Proceedings?of?the?1st?ACM?SIGSPATIAL?international?workshop?on?analytics?for?big?geospatial?data.2012：110.

［4］Xu?D，Tian?Y.A?comprehensive?survey?of?clustering?algorithms［J］.Annals?of?Data?Science，2015，2（2）：165193.

［5］邊馥苓，杜江毅，孟小亮.時空大數據處理的需求、應用與挑戰［J］.測繪地理信息，2016，41（06）：14.

［6］吉根林，趙斌.面向大數據的時空數據挖掘綜述［J］.南京師大學報（自然科學版），2014，37（01）：17.

［7］Yang?C，Clarke?K，Shekhar?S，et?al.Big?Spatiotemporal?Data?Analytics：A?research?and?innovation?frontier［J］.International?Journal?of?Geographical?Information?Science，2020，34（6）：10751088.

*通訊作者：任建吉（1982—?），男，漢族，河南焦作人，博士，副教授，研究方向：工業大數據、人工智能。