移動群智感知中基于空間時間序列的真值發現算法研究

焦嘉　吳宇飛

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

關鍵詞：真值發現;時間序列分析

中圖分類號：TP311? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2022）08-0067-02

1研究概述

由于網絡拓撲的高度密集，空間上相近的節點觀測值之間具備高度的相關性，而且節點之間距離越近，這種相關度越高。這種與空間距離有關的相關性被稱為空間相關性。

空間自相關下群智感知應用系統一般包含3個組成：云平臺（即系統），任務請求者和任務完成者。任務請求者隨時向云平臺發布感知任務（下文簡稱任務）需求，并從云平臺接收任務結果;云平臺主要負責任務發布、任務分配、感知數據收集和任務質量評估;任務完成者即眾多移動用戶（下文簡稱用戶），從云平臺接收所分配的任務并負責數據感知和收集，并將感知數據發送給云平臺。群智感知任務的完成依賴于大量感知用戶的參與，這些感知用戶會返回海量的感知數據。為了對這個“大數據”進行真值發現的研究，我們希望利用云計算技術來并行處理大規模的數據。

在并行處理模型中，MapReduce [1-3]被廣泛應用在關于大規模數據的許多數據挖掘任務中，本文在Hadoop平臺上描述了基于并行的MapReduce模型的算法。在能夠解決海量數據的基礎上，提出的基于空間自相關的真值發現算法能夠對數據進行篩選，空間自相關是指一些變量在同一個分布區域內的觀測數據之間潛在的相互依賴性。

2系統模型

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

3問題建模

3.1 問題陳述

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

實體分組：

空間相關性是現實世界中廣泛存在的另一種類型的相關性。例如，加油站之間的汽油價格和某些地理區域內的天氣狀況通常非常相似。具體來說，可以將分布在網格地圖上的實體分為四個不相交的獨立集合。令[e（i，j）]為網格圖的第i行和第j列上的實體，令[p=1，2…P]和[q={1，2…Q}]作為指標。可以構造四個獨立的集合，如下所示：

這四個獨立的集合形成的方式是：奇數行和奇數列中的實體形成獨立集[I1]，奇數行和偶數列中的實體形成[I2]，偶數行和奇數列中的實體形成[I3]，偶數行和偶數列中的實體形成[I4]。可以看出，每個集合中的實體與同一集合中的其他實體不相關。

4結束語

本文提出了一種基于空間自相關的真值發現算法，與其他工作不同，將重點放在解決由在相關變量上添加正則項引起的困難。為了解決這個問題，文章提出了將變量劃分為不相交的獨立集合，并進行塊坐標下降以迭代地更新真值和權重的方法，證明了該方法的收斂性。為了進一步加快流程，提出了在Hadoop集群上實現的算法的MapReduce版本。

參考文獻：

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

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

[3] 張元鳴，蔣建波，陸佳煒，等.面向MapReduce的迭代式數據均衡分區策略[J].計算機學報，2019，42（8）：1873-1885.

【通聯編輯：代影】