基于高斯混合模型的時(shí)空大數(shù)據(jù)挖掘算法

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

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

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

1?概述

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

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

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

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

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

2?算法

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

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

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

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

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

2.1?設(shè)置GMM參數(shù)

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

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

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

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

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

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

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

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

對(duì)于每個(gè)特征向量，如果gix在所有聚類標(biāo)簽中是最大的，我們就分配一個(gè)聚類標(biāo)簽i。

3?模型評(píng)估

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

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

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

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

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

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

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

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

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

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

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

結(jié)語(yǔ)

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

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

參考文獻(xiàn)：

［1］關(guān)雪峰，曾宇媚.時(shí)空大數(shù)據(jù)背景下并行數(shù)據(jù)處理分析挖掘的進(jìn)展及趨勢(shì)［J］.地理科學(xué)進(jìn)展，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í)空大數(shù)據(jù)處理的需求、應(yīng)用與挑戰(zhàn)［J］.測(cè)繪地理信息，2016，41（06）：14.

［6］吉根林，趙斌.面向大數(shù)據(jù)的時(shí)空數(shù)據(jù)挖掘綜述［J］.南京師大學(xué)報(bào)（自然科學(xué)版），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ù)、人工智能。