焦嘉　吴宇飞

摘要：随着智能移动设备的日益增多，移动群智感知（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.

【通联编辑：代影】