移動(dòng)群智感知中基于空間時(shí)間序列的真值發(fā)現(xiàn)算法研究

焦嘉　吳宇飛

摘要：隨著智能移動(dòng)設(shè)備的日益增多，移動(dòng)群智感知（MCS）在現(xiàn)實(shí)生活中被廣泛普及。人們使用自己的移動(dòng)設(shè)備作為傳感器來(lái)報(bào)告關(guān)于實(shí)體的真實(shí)信息。因此，如何從人們上傳的海量數(shù)據(jù)中找到真實(shí)的信息是一個(gè)關(guān)鍵問(wèn)題。文章提出了一種新的基于關(guān)聯(lián)實(shí)體的實(shí)值感測(cè)數(shù)據(jù)的概率模型。該模型利用了時(shí)間序列分析來(lái)預(yù)測(cè)實(shí)體在一段時(shí)間內(nèi)的概率時(shí)間分布，這樣可以提高真值發(fā)現(xiàn)的效率。此外，還考慮了實(shí)體之間的相關(guān)性以確保準(zhǔn)確性。

關(guān)鍵詞：真值發(fā)現(xiàn);時(shí)間序列分析

中圖分類號(hào)：TP311? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2022）08-0067-02

1研究概述

由于網(wǎng)絡(luò)拓?fù)涞母叨让芗?，空間上相近的節(jié)點(diǎn)觀測(cè)值之間具備高度的相關(guān)性，而且節(jié)點(diǎn)之間距離越近，這種相關(guān)度越高。這種與空間距離有關(guān)的相關(guān)性被稱為空間相關(guān)性。

空間自相關(guān)下群智感知應(yīng)用系統(tǒng)一般包含3個(gè)組成：云平臺(tái)（即系統(tǒng)），任務(wù)請(qǐng)求者和任務(wù)完成者。任務(wù)請(qǐng)求者隨時(shí)向云平臺(tái)發(fā)布感知任務(wù)（下文簡(jiǎn)稱任務(wù)）需求，并從云平臺(tái)接收任務(wù)結(jié)果;云平臺(tái)主要負(fù)責(zé)任務(wù)發(fā)布、任務(wù)分配、感知數(shù)據(jù)收集和任務(wù)質(zhì)量評(píng)估;任務(wù)完成者即眾多移動(dòng)用戶（下文簡(jiǎn)稱用戶），從云平臺(tái)接收所分配的任務(wù)并負(fù)責(zé)數(shù)據(jù)感知和收集，并將感知數(shù)據(jù)發(fā)送給云平臺(tái)。群智感知任務(wù)的完成依賴于大量感知用戶的參與，這些感知用戶會(huì)返回海量的感知數(shù)據(jù)。為了對(duì)這個(gè)“大數(shù)據(jù)”進(jìn)行真值發(fā)現(xiàn)的研究，我們希望利用云計(jì)算技術(shù)來(lái)并行處理大規(guī)模的數(shù)據(jù)。

在并行處理模型中，MapReduce [1-3]被廣泛應(yīng)用在關(guān)于大規(guī)模數(shù)據(jù)的許多數(shù)據(jù)挖掘任務(wù)中，本文在Hadoop平臺(tái)上描述了基于并行的MapReduce模型的算法。在能夠解決海量數(shù)據(jù)的基礎(chǔ)上，提出的基于空間自相關(guān)的真值發(fā)現(xiàn)算法能夠?qū)?shù)據(jù)進(jìn)行篩選，空間自相關(guān)是指一些變量在同一個(gè)分布區(qū)域內(nèi)的觀測(cè)數(shù)據(jù)之間潛在的相互依賴性。

2系統(tǒng)模型

典型的MapReduce模型包含兩個(gè)階段：（1）map 階段讀取輸入數(shù)據(jù)，并將其轉(zhuǎn)換為鍵值對(duì);（2）reduce階段采用鍵值對(duì)從map階段生成作為輸入，并執(zhí)行需要對(duì)其進(jìn)行的操作。對(duì)于提出的真值發(fā)現(xiàn)任務(wù)，目標(biāo)是使得算法2適應(yīng)并行版本。為了解決這個(gè)問(wèn)題，文章設(shè)計(jì)了基于異步并行坐標(biāo)下降的MapReduce算法，所提出的方法迭代計(jì)算用戶權(quán)重和真值集。在每次迭代期間，輸入數(shù)據(jù)包括來(lái)自所有K個(gè)用戶的觀測(cè)值[xkKk=1]，從上次迭代（在迭代t）中產(chǎn)生的真值集[xt（*）]=[xi（t）Ni=1]和用戶權(quán)重[w（t）]=[wktKk=1]。輸出是在當(dāng)前迭代（在迭代t+1） 中計(jì)算出的真值集和用戶權(quán)重。以上提出的方法將在算法1中詳細(xì)描述，下面將詳細(xì)描述MapReduce真值發(fā)現(xiàn)算法中使用的功能。

3問(wèn)題建模

3.1 問(wèn)題陳述

本章節(jié)中依舊假設(shè)有K個(gè)用戶和N個(gè)實(shí)體。從所有K個(gè)用戶收集的時(shí)間序列[S1，S2，...，SN]作為輸入。 [C（i）]表示與實(shí)體[ei]有關(guān)的所有實(shí)體的集合。預(yù)期的輸出真值用[D（*）]表示和觀察者權(quán)重用[W]表示。

實(shí)體分組：

空間相關(guān)性是現(xiàn)實(shí)世界中廣泛存在的另一種類型的相關(guān)性。例如，加油站之間的汽油價(jià)格和某些地理區(qū)域內(nèi)的天氣狀況通常非常相似。具體來(lái)說(shuō)，可以將分布在網(wǎng)格地圖上的實(shí)體分為四個(gè)不相交的獨(dú)立集合。令[e（i，j）]為網(wǎng)格圖的第i行和第j列上的實(shí)體，令[p=1，2…P]和[q={1，2…Q}]作為指標(biāo)?？梢詷?gòu)造四個(gè)獨(dú)立的集合，如下所示：

這四個(gè)獨(dú)立的集合形成的方式是：奇數(shù)行和奇數(shù)列中的實(shí)體形成獨(dú)立集[I1]，奇數(shù)行和偶數(shù)列中的實(shí)體形成[I2]，偶數(shù)行和奇數(shù)列中的實(shí)體形成[I3]，偶數(shù)行和偶數(shù)列中的實(shí)體形成[I4]?？梢钥闯觯總€(gè)集合中的實(shí)體與同一集合中的其他實(shí)體不相關(guān)。

4結(jié)束語(yǔ)

本文提出了一種基于空間自相關(guān)的真值發(fā)現(xiàn)算法，與其他工作不同，將重點(diǎn)放在解決由在相關(guān)變量上添加正則項(xiàng)引起的困難。為了解決這個(gè)問(wèn)題，文章提出了將變量劃分為不相交的獨(dú)立集合，并進(jìn)行塊坐標(biāo)下降以迭代地更新真值和權(quán)重的方法，證明了該方法的收斂性。為了進(jìn)一步加快流程，提出了在Hadoop集群上實(shí)現(xiàn)的算法的MapReduce版本。

參考文獻(xiàn)：

[1] Dean J，Ghemawat S.Mapreduce： simplifieddata processing on large clusters[J].Communications ofthe ACM，2008，51（1）：107-113.

[2] 陳軍曉，李中升，劉逸敏，等.基于MapReduce的時(shí)間序列索引與批量查詢技術(shù)[J].計(jì)算機(jī)工程，2019，45（11）：47-53.

[3] 張?jiān)Q，蔣建波，陸佳煒，等.面向MapReduce的迭代式數(shù)據(jù)均衡分區(qū)策略[J].計(jì)算機(jī)學(xué)報(bào)，2019，42（8）：1873-1885.

【通聯(lián)編輯：代影】