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

焦 嘉,吳宇飛

(湖南信息職業(yè)技術(shù)學(xué)院,湖南 長(zhǎng)沙 410203)

1 系統(tǒng)模型

觀察者對(duì)幾個(gè)實(shí)體進(jìn)行觀察,生成概率時(shí)間序列。基于GARCH模型,從原始數(shù)據(jù)生成一個(gè)概率時(shí)間序列并將其上傳到服務(wù)器。在服務(wù)器端,將執(zhí)行本研究提出的真值發(fā)現(xiàn)框架。系統(tǒng)框架如圖1所示。

圖1 GARCH模型架構(gòu)

2 問(wèn)題陳述

假設(shè)研究K個(gè)用戶和N個(gè)實(shí)體,從所有K個(gè)用戶收集的時(shí)間序列S1{ ,S2,...,SN}作為輸入;用i索引每個(gè)實(shí)體,ei表示第i個(gè)實(shí)體。以k索引每個(gè)觀察者,時(shí)間序列表示為Si(k),表示觀察者k在實(shí)體ei上觀察到的時(shí)間序列。D=S1,{S2,…,Sn}是一組時(shí)間序列。觀測(cè)者k在j時(shí)刻收集到的一個(gè)讀數(shù)被標(biāo)記為∈Si。

由于每個(gè)觀察者的可靠性在之前是未知的,所以它提供的原始數(shù)據(jù)可能不正確。用si(*)來(lái)表示實(shí)體ei的真值,用D(*)來(lái)表示所有實(shí)體的真值。

通過(guò)最小化約束下的目標(biāo)函數(shù)f(D(*),W),設(shè)置了兩組變量,其中一組是真值D(*),另一組是感知用戶權(quán)重W。面對(duì)這兩個(gè)變量,塊坐標(biāo)下降法可以解決求約束條件下的最優(yōu)值問(wèn)題。

在這一部分中,假設(shè)已經(jīng)使用KNN算法,并且獲得了獨(dú)立的集合。將m表示為獨(dú)立集的索引,包含所有實(shí)體的集合表示為I=,而Im表示第m個(gè)子集。所以,可以將問(wèn)題定義如下:

2.1 實(shí)體分組

由于數(shù)據(jù)在應(yīng)用程序中順序產(chǎn)生,因此實(shí)體真值之間存在時(shí)間相關(guān)性。例如,鄰近地區(qū)的空氣質(zhì)量可能相同,因此實(shí)體的值在短時(shí)間內(nèi)相似。時(shí)間相關(guān)性也可以合并到模型中以推測(cè)真值。此屬性能夠使用KNN算法對(duì)實(shí)體進(jìn)行分類[1]。先在現(xiàn)有實(shí)體類別中找到最相似的集合,再根據(jù)KNN的類別決定要分類的實(shí)體屬于的組別。KNN是最簡(jiǎn)單有效的分類算法之一,其分類有效性在很大程度上取決于K值(最近鄰居數(shù)的好壞選擇)。根據(jù)經(jīng)驗(yàn),本文確定的K是不超過(guò)觀測(cè)樣本數(shù)平方根的最大整數(shù)[2]。

2.2 時(shí)間序列分析算法詳述

本文的原始數(shù)據(jù)利用GARCH模型進(jìn)行處理,隨后輸出一個(gè)概率時(shí)間序列。該模型包含的兩個(gè)參數(shù),分別如下:期望真值和方差。

預(yù)測(cè)期望真值:給定時(shí)間序列S,可以使用ARMA模型將時(shí)間戳j的讀數(shù)建模為根據(jù)其過(guò)去的值,可以在時(shí)間j處計(jì)算期望的真實(shí)值。

方差推測(cè):根據(jù)在時(shí)間j的的讀為可以給定直到時(shí)間j-1的所有可用信息來(lái)定義條件方差[3]。具體的算法如表2所示。

表2 算法1

2.3 真值發(fā)現(xiàn)算法詳述

2.3.1 更新感知者權(quán)重

所有的真值集合都是固定的,根據(jù)真值和感知者的觀測(cè)數(shù)據(jù)的差異來(lái)計(jì)算出每個(gè)觀察者權(quán)重的更新規(guī)則。

公式(2)中k′表示觀察者的索引。該公式表明,用戶報(bào)告的觀察值與真值實(shí)況越接近,感知用戶擁有的權(quán)重越高。

2.3.2 更新時(shí)間序列真值分布

在這種情況下,觀察者權(quán)重W是固定的,除了以外,其余真值集也固定。通過(guò)最小化目標(biāo)函數(shù)來(lái)更新中每個(gè)實(shí)體的真值分布。

3 結(jié)語(yǔ)

本文提出了一種新的移動(dòng)群智感知真值發(fā)現(xiàn)算法,與其他工作不同,將重點(diǎn)放每個(gè)關(guān)聯(lián)實(shí)體一段時(shí)間內(nèi)的真值分布情況。考慮到現(xiàn)實(shí)生活中的實(shí)際情況,利用K近鄰算法將相關(guān)聯(lián)的實(shí)體進(jìn)行分組規(guī)劃,并利用GARCH算法來(lái)預(yù)測(cè)每個(gè)實(shí)體的概率時(shí)間序列分布,提高數(shù)據(jù)質(zhì)量。基本思路是利用關(guān)聯(lián)實(shí)體一段時(shí)間內(nèi)的真值分布具有相似性,通過(guò)塊坐標(biāo)下降算法計(jì)算出感知用戶的權(quán)重以及實(shí)體的真值分布集合。