移动群智感知中基于顺序时间序列的真值发现算法研究

焦 嘉,吴宇飞

(湖南信息职业技术学院,湖南 长沙 410203)

1 系统模型

观察者对几个实体进行观察,生成概率时间序列。基于GARCH模型,从原始数据生成一个概率时间序列并将其上传到服务器。在服务器端,将执行本研究提出的真值发现框架。系统框架如图1所示。

图1 GARCH模型架构

2 问题陈述

假设研究K个用户和N个实体,从所有K个用户收集的时间序列S1{ ,S2,...,SN}作为输入;用i索引每个实体,ei表示第i个实体。以k索引每个观察者,时间序列表示为Si(k),表示观察者k在实体ei上观察到的时间序列。D=S1,{S2,…,Sn}是一组时间序列。观测者k在j时刻收集到的一个读数被标记为∈Si。

由于每个观察者的可靠性在之前是未知的,所以它提供的原始数据可能不正确。用si(*)来表示实体ei的真值,用D(*)来表示所有实体的真值。

通过最小化约束下的目标函数f(D(*),W),设置了两组变量,其中一组是真值D(*),另一组是感知用户权重W。面对这两个变量,块坐标下降法可以解决求约束条件下的最优值问题。

在这一部分中,假设已经使用KNN算法,并且获得了独立的集合。将m表示为独立集的索引,包含所有实体的集合表示为I=,而Im表示第m个子集。所以,可以将问题定义如下:

2.1 实体分组

由于数据在应用程序中顺序产生,因此实体真值之间存在时间相关性。例如,邻近地区的空气质量可能相同,因此实体的值在短时间内相似。时间相关性也可以合并到模型中以推测真值。此属性能够使用KNN算法对实体进行分类[1]。先在现有实体类别中找到最相似的集合,再根据KNN的类别决定要分类的实体属于的组别。KNN是最简单有效的分类算法之一,其分类有效性在很大程度上取决于K值(最近邻居数的好坏选择)。根据经验,本文确定的K是不超过观测样本数平方根的最大整数[2]。

2.2 时间序列分析算法详述

本文的原始数据利用GARCH模型进行处理,随后输出一个概率时间序列。该模型包含的两个参数,分别如下:期望真值和方差。

预测期望真值:给定时间序列S,可以使用ARMA模型将时间戳j的读数建模为根据其过去的值,可以在时间j处计算期望的真实值。

方差推测:根据在时间j的的读为可以给定直到时间j-1的所有可用信息来定义条件方差[3]。具体的算法如表2所示。

表2 算法1

2.3 真值发现算法详述

2.3.1 更新感知者权重

所有的真值集合都是固定的,根据真值和感知者的观测数据的差异来计算出每个观察者权重的更新规则。

公式(2)中k′表示观察者的索引。该公式表明,用户报告的观察值与真值实况越接近,感知用户拥有的权重越高。

2.3.2 更新时间序列真值分布

在这种情况下,观察者权重W是固定的,除了以外,其余真值集也固定。通过最小化目标函数来更新中每个实体的真值分布。

3 结语

本文提出了一种新的移动群智感知真值发现算法,与其他工作不同,将重点放每个关联实体一段时间内的真值分布情况。考虑到现实生活中的实际情况,利用K近邻算法将相关联的实体进行分组规划,并利用GARCH算法来预测每个实体的概率时间序列分布,提高数据质量。基本思路是利用关联实体一段时间内的真值分布具有相似性,通过块坐标下降算法计算出感知用户的权重以及实体的真值分布集合。