張曉濱， 黃夢(mèng)瑩

(西安工程大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院， 西安 710048)

引言

隨著移動(dòng)智能設(shè)備的不斷普及與應(yīng)用， 使得越來(lái)越多的傳感器應(yīng)用到移動(dòng)智能設(shè)備里， 這樣就使得人們獲取數(shù)據(jù)的方式越來(lái)越多樣化， 群智感知服務(wù)的發(fā)展也越來(lái)越普及. 群智感知服務(wù)就類似于一種眾包服務(wù)， 是將原來(lái)分配給員工做的任務(wù)包給擁有移動(dòng)智能設(shè)備的群體進(jìn)行完成并上傳數(shù)據(jù)實(shí)現(xiàn)感知服務(wù). 當(dāng)某一項(xiàng)研究需要收集某些數(shù)據(jù)時(shí)， 就會(huì)發(fā)布一些感知任務(wù)， 收到任務(wù)的移動(dòng)感知節(jié)點(diǎn)根據(jù)需要完成該感知任務(wù)并上傳數(shù)據(jù)， 收集到這些數(shù)據(jù)的人員對(duì)數(shù)據(jù)進(jìn)行分析處理， 從而得到研究結(jié)果. 在現(xiàn)有的研究中， 有很多關(guān)于群智感知應(yīng)用， 感知問(wèn)題面臨的挑戰(zhàn)以及解決辦法等方面的研究.

Xu等[1]通過(guò)收集和研究現(xiàn)有移動(dòng)群智感知在社會(huì)感知上的應(yīng)用， 提出并分析了潛在的新應(yīng)用在未來(lái)方向上的一些可能. 當(dāng)然， 感知應(yīng)用也需要考慮到用戶成本、網(wǎng)絡(luò)壓力、云計(jì)算服務(wù)器架設(shè)、用戶隱私等問(wèn)題[2]. 在參與者的問(wèn)題上， 劉琰， 郭斌等[3]針對(duì)多感知任務(wù)并發(fā)的情況下對(duì)任務(wù)參與者的選擇問(wèn)題， 提出了三種任務(wù)參與者選擇的解決方法， 同時(shí)通過(guò)實(shí)驗(yàn)驗(yàn)證， 這三種方法針對(duì)不同的情景能夠?qū)崿F(xiàn)最優(yōu)的參與者選擇， 達(dá)到感知服務(wù)的目的. Wang等[4]通過(guò)對(duì)感知平臺(tái)數(shù)據(jù)傳遞的問(wèn)題的分析， 提出了端對(duì)端的參與者選擇模型， 來(lái)實(shí)現(xiàn)對(duì)參與者的選擇. 這兩者在不同程度上解決了參與者選擇上的問(wèn)題， 但是基于用戶隱私問(wèn)題的考慮， 大部分研究者的解決方法是對(duì)用戶采取激勵(lì)措施來(lái)降低用戶對(duì)隱私問(wèn)題的顧慮， 用戶基于激勵(lì)與隱私問(wèn)題的平衡來(lái)決定是否參與任務(wù). 因此， 激勵(lì)機(jī)制是群智感知研究的一個(gè)重要問(wèn)題[5]， 吳垚等[5]對(duì)群智感知服務(wù)做了分析， 同時(shí)介紹了4類主要的激勵(lì)機(jī)制及其核心研究問(wèn)題. 為了補(bǔ)償用戶參與感知任務(wù)的代價(jià)， 需要設(shè)計(jì)一種合理的激勵(lì)機(jī)制[6]， 從而使得能有更多的人能參與到感知任務(wù)中. 南文倩等[7]基于感知任務(wù)用戶參與度的問(wèn)題， 提出了基于跨空間的動(dòng)態(tài)激勵(lì)模型， 相比較傳統(tǒng)的方法來(lái)說(shuō)， 該方法有效地提高了用戶參與感知任務(wù)的積極性， 從而使得感知任務(wù)能順利的進(jìn)行. 為了讓更多的人自愿的參與感知任務(wù)， Cai等[8]提出了一種具有多項(xiàng)式時(shí)間計(jì)算復(fù)雜度的近最優(yōu)算法和一種關(guān)鍵的支付方案. 此方法能讓用戶在隱私與激勵(lì)上做出平衡， 從而決定參與感知任務(wù). 另外， 為了激勵(lì)更多的參與者完成感知任務(wù)， Zhang等[9]提出了三種在線反向拍賣的激勵(lì)機(jī)制， 并取得了很好的成效. 以及Micholia等[10]說(shuō)明了用戶最終參與和貢獻(xiàn)的不確定性， 同時(shí)提出了激勵(lì)分配問(wèn)題和迭代算法， 也取得了不錯(cuò)的效果.

以上研究中在參與者的選擇問(wèn)題上做了許多改進(jìn)，使更多的參與者能夠參與到感知任務(wù)中并完成感知任務(wù)， 但是對(duì)于任務(wù)完成的質(zhì)量卻沒(méi)有保證. Luo等[11]針對(duì)激勵(lì)用戶參與感知任務(wù)以及感知數(shù)據(jù)的真實(shí)性問(wèn)題，采用協(xié)同的方式解決了這兩個(gè)問(wèn)題. 在數(shù)據(jù)傳輸成本問(wèn)題上， 徐哲等[12]利用感知節(jié)點(diǎn)的社會(huì)屬性提出了多任務(wù)分發(fā)算法， 降低了數(shù)據(jù)傳輸?shù)臅r(shí)間消耗成本， 實(shí)現(xiàn)了節(jié)點(diǎn)之間的高效感知與通信. Ma等[13]基于感知角度探討了如何利用人類移動(dòng)的機(jī)會(huì)主義特征來(lái)高效、有效地收集數(shù)據(jù). 這三者雖然在數(shù)據(jù)的可靠性和數(shù)據(jù)的傳輸收集效率上做了改進(jìn)， 但并未對(duì)數(shù)據(jù)做出有效的篩選， 因此在后續(xù)的數(shù)據(jù)處理效率上并沒(méi)有有效的提高.

另外， 在群智感知的研究中可以利用群智感知收集的數(shù)據(jù)進(jìn)行分析與研究， 找到某些數(shù)據(jù)直接的關(guān)聯(lián)，從而實(shí)現(xiàn)對(duì)具體事件的分析. 張佳凡等[14]基于新浪微博進(jìn)行研究， 根據(jù)詞頻變化特征以及熱詞上下文語(yǔ)境能有效的對(duì)熱點(diǎn)事件進(jìn)行區(qū)分， 達(dá)到事件的感知效果.李靜林等[15]分析了車聯(lián)網(wǎng)群智感知服務(wù)的三種感知模型， 從而提出了一種有效的感知方法解決了車聯(lián)網(wǎng)的高效性與時(shí)效性之間的沖突. 以上的大部分研究都是對(duì)群智感知的整體問(wèn)題與挑戰(zhàn)進(jìn)行的研究與分析， 很少有對(duì)于局部的數(shù)據(jù)的篩選問(wèn)題進(jìn)行解決的具體解決方法. 同時(shí)， 在傳統(tǒng)的數(shù)據(jù)篩選問(wèn)題上都是對(duì)基礎(chǔ)數(shù)據(jù)，如數(shù)值數(shù)據(jù)、統(tǒng)計(jì)數(shù)據(jù)的篩選.

本文主要是針對(duì)群智感知環(huán)境下的情感文本數(shù)據(jù)的篩選來(lái)進(jìn)行感知節(jié)點(diǎn)的選擇. 首先進(jìn)行感知網(wǎng)絡(luò)模型的構(gòu)建， 結(jié)合遺傳算法， 根據(jù)節(jié)點(diǎn)攜帶的數(shù)據(jù)進(jìn)行分類， 從而根據(jù)適應(yīng)度函數(shù)得到節(jié)點(diǎn)最終值選擇節(jié)點(diǎn)迭代. 同時(shí)， 對(duì)遺傳算法的復(fù)雜度進(jìn)行了分析. 一般感知服務(wù)收集到的數(shù)據(jù)包含有時(shí)間、地理位置以及用戶上傳的文本等信息， 而本文主要是通過(guò)篩選出帶有情感詞的文本數(shù)據(jù)的節(jié)點(diǎn)， 對(duì)節(jié)點(diǎn)所含情感文本數(shù)據(jù)進(jìn)行處理， 從而實(shí)現(xiàn)后續(xù)的情感分析處理. 本文提出的方法在一定程度上減少了不必要的數(shù)據(jù)獲取以及避免了較大數(shù)據(jù)量的篩選， 從而實(shí)現(xiàn)了數(shù)據(jù)處理效率的提高.

1 感知網(wǎng)絡(luò)模型

本文是利用混合群智感知服務(wù)對(duì)基于情感文本數(shù)據(jù)篩選的感知服務(wù)節(jié)點(diǎn)選取機(jī)制進(jìn)行的研究.

圖1是混合群智感知服務(wù)的模型圖， 任務(wù)發(fā)布機(jī)構(gòu)進(jìn)行感知任務(wù)的發(fā)布， 任務(wù)發(fā)布之后由感知中心進(jìn)行任務(wù)的分解發(fā)布給各個(gè)感知節(jié)點(diǎn)， 感知節(jié)點(diǎn)需要在感知中心進(jìn)行注冊(cè)才能進(jìn)行感知任務(wù)的參與和完成.感知節(jié)點(diǎn)完成感知任務(wù)上傳感知數(shù)據(jù)， 感知中心是對(duì)在感知中心進(jìn)行注冊(cè)的感知節(jié)點(diǎn)上傳的數(shù)據(jù)進(jìn)行處理，將數(shù)據(jù)進(jìn)行集成并將數(shù)據(jù)報(bào)告上傳至任務(wù)發(fā)布機(jī)構(gòu).由于該機(jī)制是混合式的群智感知服務(wù)， 所以每個(gè)感知節(jié)點(diǎn)也是服務(wù)節(jié)點(diǎn)， 也有對(duì)數(shù)據(jù)的處理能力， 當(dāng)處理能力不夠就需要在感知中心進(jìn)行注冊(cè)讓感知中心進(jìn)行處理. 在進(jìn)行感知任務(wù)時(shí)都需要對(duì)感知節(jié)點(diǎn)進(jìn)行選取， 本文主要是采用遺傳算法對(duì)感知節(jié)點(diǎn)進(jìn)行選擇， 實(shí)現(xiàn)對(duì)特定情感文本數(shù)據(jù)的高效處理.

圖1 混合群智感知服務(wù)模型圖

2 感知節(jié)點(diǎn)集選擇

2.1 基于遺傳算法的編碼機(jī)制

在參與感知的服務(wù)節(jié)點(diǎn)集中選取符合條件的節(jié)點(diǎn)進(jìn)行感知服務(wù)， 首先對(duì)節(jié)點(diǎn)進(jìn)行編碼， 本文采用遺傳算法的編碼機(jī)制， 采用常用的二進(jìn)制編碼. 現(xiàn)有服務(wù)節(jié)點(diǎn)集里面包含m個(gè)服務(wù)節(jié)點(diǎn)， 即每個(gè)節(jié)點(diǎn)攜帶m個(gè)數(shù)據(jù)信息， 即， 當(dāng)節(jié)點(diǎn)被選取就將其歸到服務(wù)節(jié)點(diǎn)集 中， 同時(shí)將對(duì)應(yīng)位置的數(shù)據(jù)信息標(biāo)記為1， 否則標(biāo)記為0，即:

2.2 適應(yīng)度函數(shù)

在遺傳算法中需要采取適應(yīng)度函數(shù)對(duì)群體中的個(gè)體進(jìn)行定量篩選， 然后根據(jù)適應(yīng)度函數(shù)值的大小決定該個(gè)體是否淘汰. 本文是基于情感文本的數(shù)據(jù)篩選， 所以在節(jié)點(diǎn)信息攜帶的過(guò)程中本文主要考慮以下幾個(gè)方面:

(1)節(jié)點(diǎn)攜帶的信息數(shù)據(jù)類型. 定義數(shù)據(jù)類型t， 取值為1和0. 當(dāng)t=1時(shí)表示數(shù)據(jù)類型為文本類型， 當(dāng)t=0時(shí)表示數(shù)據(jù)類型是非文本類型.

(2)節(jié)點(diǎn)攜帶的文本信息的內(nèi)容是否包含情感詞.定義文本標(biāo)記s， 取值為1和0. 當(dāng)s=1時(shí)表示文本包含情感詞， 當(dāng)s=0時(shí)表示文本不包含情感詞.

(3)節(jié)點(diǎn)攜帶信息內(nèi)容中包含情感詞的多少. 用c表示表示包含情感詞的數(shù)量.

結(jié)合以上三個(gè)方面的考慮， 對(duì)適應(yīng)度函數(shù)的設(shè)計(jì)如下:

(1)節(jié)點(diǎn)聯(lián)合攜帶文本數(shù)據(jù)概率. 節(jié)點(diǎn)聯(lián)合攜帶文本數(shù)據(jù)概率是指節(jié)點(diǎn)服務(wù)集中被選定的節(jié)點(diǎn)攜帶的信息數(shù)據(jù)中至少有一個(gè)是文本數(shù)據(jù)， 用T表示.

(2)聯(lián)合包含情感詞概率. 聯(lián)合包含情感詞概率是指節(jié)點(diǎn)服務(wù)集中被選定的節(jié)點(diǎn)攜帶的文本信息中至少有一個(gè)文本信息中包含情感詞， 用表示.

其中，

(3)節(jié)點(diǎn)聯(lián)合情感詞數(shù). 節(jié)點(diǎn)聯(lián)合情感詞數(shù)指節(jié)點(diǎn)服務(wù)集中被選定的節(jié)點(diǎn)攜帶的文本信息中包含情感詞數(shù)量的平均值， 用表示.

3 遺傳算法分析

3.1 遺傳算法優(yōu)化過(guò)程

根據(jù)第二節(jié)提到的編碼機(jī)制和適應(yīng)度函數(shù)， 基于遺傳算子操作設(shè)計(jì)的遺傳算法及其優(yōu)化過(guò)程如下:

1)隨機(jī)產(chǎn)生M個(gè)初始個(gè)體；

2)根據(jù)式(2)-式(5)計(jì)算種群中各個(gè)個(gè)體的適應(yīng)度函數(shù)值， 并判斷是否達(dá)到最大迭代次數(shù)， 若滿足終止條件， 則輸出結(jié)果， 否則， 執(zhí)行步驟 3)；

3)根據(jù)種群中各個(gè)個(gè)體的適應(yīng)度函數(shù)值， 依此執(zhí)行選擇， 交叉， 變異遺傳算子， 產(chǎn)生新的種群， 并執(zhí)行步驟2).

具體的算子選擇如下:

1)在進(jìn)行選擇操作時(shí)采用比例選擇算子， 該算子是指?jìng)€(gè)體被選中的概率與適應(yīng)度函數(shù)值是成正比的，即在輪盤選擇的時(shí)候， 適應(yīng)度函數(shù)值越大的， 在盤面上的刻度越長(zhǎng).

2)交叉算子是通過(guò)交換個(gè)體之間某個(gè)基因從而產(chǎn)生新個(gè)體的過(guò)程. 在對(duì)父?jìng)€(gè)體進(jìn)行的重組操作采用的是單點(diǎn)交叉算子， 從而使得選取的節(jié)點(diǎn)冗余比較少.

3)變異運(yùn)算采用基本位變異算子， 該算子是最簡(jiǎn)單的變異算子， 即是在某一個(gè)基因位上取反操作. 在變異的操作過(guò)程中需要選擇合適的迭代次數(shù)， 從而得到最優(yōu)解.

3.2 遺傳算法復(fù)雜度分析

復(fù)雜度分析包括時(shí)間復(fù)雜度分析和空間復(fù)雜度分析， 在這里忽略空間復(fù)雜度的分析， 只分析時(shí)間復(fù)雜度.遺傳算法的時(shí)間復(fù)雜度可以認(rèn)為是算法的平均計(jì)算時(shí)間， 即是求適應(yīng)度函數(shù)最優(yōu)值的平均計(jì)算時(shí)間.

N個(gè)個(gè)體的初始化種群， 記為， 經(jīng)過(guò)重組后產(chǎn)生的新種群記為，中的每個(gè)個(gè)體每一位以概率p取反， 產(chǎn)生新個(gè)體， 得到種群， 最后從中選取N個(gè)最好的個(gè)體組成下一代種群， 重復(fù)以上重組和變異操作， 直到選出滿足條件的個(gè)體結(jié)束.

4 實(shí)驗(yàn)驗(yàn)證

4.1 實(shí)驗(yàn)準(zhǔn)備與操作

實(shí)驗(yàn)選取100個(gè)愿意上傳移動(dòng)應(yīng)用數(shù)據(jù)的志愿者進(jìn)行實(shí)驗(yàn)， 使用Matlab實(shí)現(xiàn). 志愿者的年齡范圍在20～50之間， 男女比例1:1. 每個(gè)志愿者相當(dāng)于一個(gè)個(gè)體， 代表著感知節(jié)點(diǎn)， 每個(gè)個(gè)體在100×100區(qū)域內(nèi)隨機(jī)分布. 計(jì)算每個(gè)個(gè)體中每個(gè)基因是文本數(shù)據(jù)的概率， 包含情感詞的概率 和包含情感詞的數(shù)量 的值. 根據(jù)這些值算出每個(gè)個(gè)體的適應(yīng)度函數(shù)值， 并將函數(shù)值降序排列， 選出前N個(gè)個(gè)體作為候選感知節(jié)點(diǎn).

設(shè)置遺傳算法程序運(yùn)行的參數(shù)， 初始化的種群個(gè)體數(shù)M=20， 終止進(jìn)化迭代次數(shù)G=500， 交叉操作的交叉概率Pc=0.3， 變異操作的變異概率Pm=0.06， 運(yùn)行程序得到實(shí)驗(yàn)程序選出的個(gè)體. 再將選出的個(gè)體中的包含的文本信息數(shù)據(jù)整理出來(lái)， 同時(shí)記錄實(shí)驗(yàn)所需的時(shí)間和數(shù)據(jù)量， 最后將實(shí)驗(yàn)中單位時(shí)間內(nèi)處理的數(shù)據(jù)量進(jìn)行歸一化， 即是實(shí)驗(yàn)中的數(shù)據(jù)處理效率指標(biāo). 因此實(shí)驗(yàn)分為兩部分: 一是對(duì)節(jié)點(diǎn)的選取， 二是對(duì)選取的節(jié)點(diǎn)攜帶的數(shù)據(jù)進(jìn)行處理. 所以， 實(shí)驗(yàn)的總時(shí)間就是這兩部分時(shí)間的總和. 數(shù)據(jù)處理效率指標(biāo)也就是整個(gè)實(shí)驗(yàn)的處理效率指標(biāo). 另外， 算出選擇出的節(jié)點(diǎn)攜帶的有效數(shù)據(jù)占比， 即是文本類型又包含情感詞的數(shù)據(jù)占比.

對(duì)于傳統(tǒng)方法本文采用隨機(jī)選擇算法進(jìn)行實(shí)驗(yàn)，對(duì)于節(jié)點(diǎn)的選取是直到選擇符合數(shù)量的感知節(jié)點(diǎn)為止.后面的對(duì)數(shù)據(jù)處理的方法和本文中所用的數(shù)據(jù)處理方法一致.

4.2 實(shí)驗(yàn)結(jié)果與分析

圖2是在迭代次數(shù)、交叉概率和變異概率相同，初始化種群個(gè)體數(shù)不同的情況下， 傳統(tǒng)的數(shù)據(jù)處理與使用本文提出的算法進(jìn)行的數(shù)據(jù)處理的對(duì)比. 圖2(a)節(jié)點(diǎn)選取時(shí)間的倒數(shù)與初始種群個(gè)體數(shù)關(guān)系， 由圖可以看到隨著初始化種群個(gè)體數(shù)的增加， 兩種方法在節(jié)點(diǎn)選取所需時(shí)間上的差距越來(lái)越小， 雖然在節(jié)點(diǎn)選取上本文方法在時(shí)間上會(huì)有一點(diǎn)延時(shí)， 但是由圖2(b)可以看出， 兩者的整體處理效率上本文方法相對(duì)較好， 并且隨著初始化種群個(gè)體數(shù)的增加， 兩者的整體處理效率相差越來(lái)越明顯， 在初始化種群個(gè)體數(shù)達(dá)到90時(shí)， 差距達(dá)到最大， 相差27.6%. 因此， 該方法能夠有效的節(jié)省數(shù)據(jù)的處理時(shí)間.

圖3是在初始化種群個(gè)體數(shù)為20、交叉概率為0.03和變異概率為0.06， 迭代次數(shù)不同的情況下， 傳統(tǒng)的數(shù)據(jù)處理與使用本文提出的算法進(jìn)行的數(shù)據(jù)處理的對(duì)比. 圖3(a)是選取的感知節(jié)點(diǎn)個(gè)數(shù)與迭代次數(shù)之間的關(guān)系圖， 圖3(b)是數(shù)據(jù)處理效率與迭代次數(shù)對(duì)應(yīng)選出的感知節(jié)點(diǎn)數(shù)之間的關(guān)系圖. 由圖3(a)可以看出， 隨著迭代次數(shù)的增加， 節(jié)點(diǎn)選取的數(shù)量逐漸趨于穩(wěn)定， 即在迭代次數(shù)達(dá)到700時(shí)， 最優(yōu)的感知節(jié)點(diǎn)個(gè)數(shù)一定. 當(dāng)最優(yōu)感知節(jié)點(diǎn)個(gè)數(shù)達(dá)到一定時(shí)， 需要處理的數(shù)據(jù)量就是最優(yōu)感知節(jié)點(diǎn)攜帶的數(shù)據(jù)量， 所以由圖3(b)可以看出， 在迭代次數(shù)達(dá)到700時(shí)， 數(shù)據(jù)處理的效率時(shí)趨于穩(wěn)定的. 同時(shí)圖3(b)可以看出， 使用本文提出的方法， 數(shù)據(jù)處理的效率優(yōu)于傳統(tǒng)的數(shù)據(jù)處理的效率. 圖4是在迭代次數(shù)、交叉概率和變異概率相同， 初始化種群個(gè)體數(shù)不同的情況下， 傳統(tǒng)的數(shù)據(jù)處理的有效數(shù)據(jù)占比與使用本文提出的算法進(jìn)行的數(shù)據(jù)處理的有戲數(shù)據(jù)占比的對(duì)比. 由圖4可以看出， 隨著初始化種群個(gè)體數(shù)的增加， 兩種方法的有效數(shù)據(jù)占比相差越來(lái)越明顯， 在初始化種群個(gè)體數(shù)達(dá)到90時(shí)， 差距達(dá)到最大， 相差21%. 實(shí)驗(yàn)表明， 該方法能夠有效的提高獲取的數(shù)據(jù)的有效性.

圖2 感知節(jié)點(diǎn)評(píng)價(jià)指標(biāo)與初始種群個(gè)體數(shù)關(guān)系

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

本文通過(guò)對(duì)感知環(huán)境下節(jié)點(diǎn)數(shù)據(jù)的獲取方法的分析， 提出了一種新的針對(duì)基于特定的情感文本數(shù)據(jù)篩選的節(jié)點(diǎn)選擇機(jī)制. 基于遺傳算法的優(yōu)化選擇過(guò)程， 得到所有節(jié)點(diǎn)集中符合優(yōu)化條件的節(jié)點(diǎn)集， 從而實(shí)現(xiàn)感知服務(wù)對(duì)數(shù)據(jù)的獲取. 實(shí)驗(yàn)結(jié)果表明， 本文提出的方法減少了對(duì)不必要數(shù)據(jù)的獲取， 從而減少了在后續(xù)的數(shù)據(jù)處理的工作量， 能夠提高對(duì)整體數(shù)據(jù)進(jìn)行分析的效率. 在后續(xù)的研究中， 還需要根據(jù)實(shí)際情況考慮到遺傳算法中遺傳算子的選擇問(wèn)題， 實(shí)現(xiàn)對(duì)算法的進(jìn)一步優(yōu)化.

圖3 感知節(jié)點(diǎn)評(píng)價(jià)指標(biāo)與迭代次數(shù)關(guān)系

圖4 有效數(shù)據(jù)占比與初始種群個(gè)體數(shù)關(guān)系