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

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

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

1?概述

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

過去十年時空大數(shù)據(jù)相關論文的發(fā)表數(shù)量趨勢圖

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

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

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

2?算法

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

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

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

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

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

2.1?設置GMM參數(shù)

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

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

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

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

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

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

現(xiàn)在我們簡單介紹一下最大似然估計法，算法第一步是使用當前的參數(shù)，并以觀察到的樣本為條件，使對數(shù)似然函數(shù)進行期望最大化。算法第二步，重新計算參數(shù)值。EM算法在這兩步中不斷迭代，直到達到收斂。對于多變量正態(tài)分布，期望值E.，用pij表示，是高斯混合物j產(chǎn)生數(shù)據(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被擬合到訓練數(shù)據(jù)上，我們就可以使用該模型來預測每個群組的標簽。標簽的分配是使用最大似然（MLE）程序進行的。由MLE原理給出的判別函數(shù)g（.）如下所示：

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

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

3?模型評估

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

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

4?應用與挑戰(zhàn)

4.1?時空大數(shù)據(jù)挖掘的應用

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

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

在科技方面，以數(shù)據(jù)挖掘為基礎開展智能化分析，能夠提高規(guī)劃方案制訂效率及準確度，從而優(yōu)化資源配置，節(jié)約成本。

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

4.2?時空大數(shù)據(jù)挖掘面臨的挑戰(zhàn)

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

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

結語

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

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

參考文獻：

［1］關雪峰，曾宇媚.時空大數(shù)據(jù)背景下并行數(shù)據(jù)處理分析挖掘的進展及趨勢［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］邊馥苓，杜江毅，孟小亮.時空大數(shù)據(jù)處理的需求、應用與挑戰(zhàn)［J］.測繪地理信息，2016，41（06）：14.

［6］吉根林，趙斌.面向大數(shù)據(jù)的時空數(shù)據(jù)挖掘綜述［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—?），男，漢族，河南焦作人，博士，副教授，研究方向：工業(yè)大數(shù)據(jù)、人工智能。