自適應(yīng)窗口滑動(dòng)的物聯(lián)網(wǎng)數(shù)據(jù)流典型相關(guān)分析

馬帥營，陳志奎，劉 旸，張清辰，阿古達(dá)木

(1.大連民族學(xué)院網(wǎng)絡(luò)與信息技術(shù)中心遼寧大連116605;2.大連理工大學(xué)軟件學(xué)院遼寧大連116620)

物聯(lián)網(wǎng)數(shù)據(jù)通常表現(xiàn)為大量的、時(shí)變的、無法預(yù)測的數(shù)據(jù)流，其挖掘研究為學(xué)術(shù)界廣泛關(guān)注。其中，數(shù)據(jù)流典型相關(guān)分析(Canonical Correlation Analysis，CCA)屬于數(shù)據(jù)流挖掘的難點(diǎn)問題之一，對其研究能夠檢測數(shù)據(jù)流之間是否相關(guān)、相關(guān)模式是否發(fā)生變化，為關(guān)聯(lián)規(guī)則挖掘以及數(shù)據(jù)挖掘的后期處理提供參考。

數(shù)據(jù)流的典型相關(guān)分析屬于數(shù)據(jù)流挖掘的難點(diǎn)問題之一，相關(guān)文獻(xiàn)較少［1-4］。文獻(xiàn)［1］對多維數(shù)據(jù)流采用近似算法實(shí)現(xiàn)典型相關(guān)分析。文獻(xiàn)［2］采用不等概列采樣技術(shù)約減流元組的數(shù)量，形成概要矩陣，然后在概要矩陣的基礎(chǔ)上增量地計(jì)算多維數(shù)據(jù)流之間的前k個(gè)典型相關(guān)系數(shù)。文獻(xiàn)［3］為了提高相關(guān)性分析算法的計(jì)算效率，提出為樣本方差陣與協(xié)差陣組成的乘積陣降維的高效低價(jià)近似方法。但是，這些算法主要關(guān)注如何提高相關(guān)性分析的計(jì)算效率，并未考慮實(shí)際情況中，數(shù)據(jù)流速率變化這一復(fù)雜因素對相關(guān)性分析的實(shí)時(shí)性、準(zhǔn)確性和有效性的影響。其中，文獻(xiàn)［3］假定“無線傳感器網(wǎng)絡(luò)具有統(tǒng)一的采樣時(shí)鐘”，即各WSN數(shù)據(jù)流的速率是一致且保持不變。但是，事實(shí)上物聯(lián)網(wǎng)中各個(gè)WSN很難保證統(tǒng)一的采樣頻率，并且WSN數(shù)據(jù)采集包含多種模式:基于周期的數(shù)據(jù)采集;基于事件觸發(fā)的數(shù)據(jù)采集;基于查詢的數(shù)據(jù)采集WSN的這些特點(diǎn)決定了物聯(lián)網(wǎng)數(shù)據(jù)流具有變化和不一致的速率。因此，傳統(tǒng)的基于滑動(dòng)窗口的相關(guān)性分析算法不適用于實(shí)際的物聯(lián)網(wǎng)數(shù)據(jù)流相關(guān)性分析。

針對以上問題，提出一種基于自適應(yīng)窗口滑動(dòng)的物聯(lián)網(wǎng)數(shù)據(jù)流典型相關(guān)分析算法，根據(jù)數(shù)據(jù)流速率的變化，對滑動(dòng)窗口進(jìn)行自適應(yīng)設(shè)計(jì)、動(dòng)態(tài)調(diào)整窗口的滑動(dòng)策略，最后將其應(yīng)用在物聯(lián)網(wǎng)數(shù)據(jù)流之間的相關(guān)性分析之中。

1 相關(guān)理論

1.1 典型相關(guān)分析

相關(guān)關(guān)系是事物之間的一類常見關(guān)系。現(xiàn)實(shí)應(yīng)用中，數(shù)據(jù)流常常顯露出較強(qiáng)的相關(guān)性，典型相關(guān)分析是研究兩組變量之間相關(guān)關(guān)系的一種多元統(tǒng)計(jì)方法，能夠揭示出兩組變量之間的內(nèi)在聯(lián)系，最早由Hotelling于1936年提出［5］，不僅可直接用于相關(guān)性檢測，而且可用于特征融合［6］和數(shù)據(jù)降維［7-8］等領(lǐng)域。

1.2 物聯(lián)網(wǎng)數(shù)據(jù)流的典型相關(guān)分析

以物聯(lián)網(wǎng)感知層中無線傳感器網(wǎng)絡(luò)為例，如圖1。區(qū)域X和Y中分別部署了p個(gè)和q個(gè)傳感器，分別感知區(qū)域中的不同事件源信息，這些傳感器所采集的數(shù)據(jù)以流的形式達(dá)到物聯(lián)網(wǎng)數(shù)據(jù)處理中心，表示為p維和q維數(shù)據(jù)流。物聯(lián)網(wǎng)數(shù)據(jù)流的典型相關(guān)分析主要實(shí)現(xiàn)隨著時(shí)間l的增加，實(shí)時(shí)計(jì)算物聯(lián)網(wǎng)數(shù)據(jù)流X(l)和Y(l)之間的典型相關(guān)系數(shù)及典型相關(guān)變量，以此來判斷區(qū)域X和Y中事件是否相關(guān);如果相關(guān)，又是哪些傳感器感知的信息占有主導(dǎo)作用;以及如何實(shí)現(xiàn)實(shí)時(shí)監(jiān)測物聯(lián)網(wǎng)數(shù)據(jù)流之間的相關(guān)性。

圖1 物聯(lián)網(wǎng)中無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)流

2 基于自適應(yīng)窗口滑動(dòng)的物聯(lián)網(wǎng)數(shù)據(jù)流CCA算法

2.1 CCA計(jì)算有效性和實(shí)時(shí)性問題

物聯(lián)網(wǎng)數(shù)據(jù)流的典型相關(guān)分析，有兩個(gè)關(guān)鍵問題。第一，數(shù)據(jù)流處理的實(shí)時(shí)性需要考慮數(shù)據(jù)流的速率。如果數(shù)據(jù)流速率較低，不應(yīng)當(dāng)一直等待數(shù)據(jù)到達(dá)，而應(yīng)當(dāng)設(shè)定最大等待時(shí)間，以滿足CCA計(jì)算實(shí)時(shí)性要求。第二，CCA算法的執(zhí)行時(shí)間與待處理數(shù)據(jù)的規(guī)模相關(guān)，也就是和滑動(dòng)窗口內(nèi)數(shù)據(jù)所構(gòu)成的矩陣規(guī)模相關(guān)。在數(shù)據(jù)流維數(shù)一定的前提下，如果滑動(dòng)窗口內(nèi)包含的數(shù)據(jù)元組數(shù)過多，則CCA處理時(shí)間過長，無法滿足數(shù)據(jù)流處理的實(shí)時(shí)性要求;相反，如果元組數(shù)過少，則統(tǒng)計(jì)樣本少，會(huì)造成相關(guān)性不顯著、計(jì)算精度低，因而不足以驗(yàn)證數(shù)據(jù)流的相關(guān)性。這就需要依據(jù)數(shù)據(jù)流的速率特性，設(shè)計(jì)適當(dāng)?shù)幕瑒?dòng)窗口模型和窗口滑動(dòng)方法，以保證物聯(lián)網(wǎng)數(shù)據(jù)流典型相關(guān)分析的實(shí)時(shí)性、準(zhǔn)確性和高效性。針對此問題，提出了基于自適應(yīng)窗口滑動(dòng)的物聯(lián)網(wǎng)數(shù)據(jù)流典型相關(guān)分析算法。

2.2 符號(hào)及定義

定義1(數(shù)據(jù)流) 數(shù)據(jù)流可以被看作是一個(gè)允許元素重復(fù)出現(xiàn)的無限集合:

定義2(滑動(dòng)窗口) 設(shè)數(shù)據(jù)流按照時(shí)間戳的先后順序進(jìn)入滑動(dòng)窗口。任意時(shí)刻每個(gè)滑動(dòng)窗口中的數(shù)據(jù)可以表示成序列:

滑動(dòng)窗口分為兩類［9］，一類是基于元組個(gè)數(shù)定義的滑動(dòng)窗口，此時(shí)窗口內(nèi)保存最近到來的K個(gè)元組，即在任意時(shí)刻序列W滿足條件u-l=K;另一類是基于時(shí)間定義的滑動(dòng)窗口，此時(shí)存儲(chǔ)最近T時(shí)間內(nèi)到達(dá)的元組，即在任意時(shí)刻序列W滿足條件tu-tl=T。

本文使用基于時(shí)間定義的滑動(dòng)窗口模型。

定義3(窗口寬度) ?w∈W，滑動(dòng)窗口w如定義1所示，tu-tl定義為 w的寬度，記作 Wid(w)。

定義4(窗口元組數(shù)) ?w∈W，滑動(dòng)窗口w如定義1所示，當(dāng)Wid(w)=tu-ti時(shí)，u-l定義為w的窗口元組數(shù)，記為Size(w)。

定義5(數(shù)據(jù)流速率) ?s∈S，t時(shí)刻數(shù)據(jù)流s的速率記為R(t)，代表單位時(shí)間內(nèi)到達(dá)的數(shù)據(jù)元組個(gè)數(shù)。

由定義3和5可得，滑動(dòng)窗口w的元組數(shù)Size(w)與數(shù)據(jù)流速率R(t)滿足關(guān)系:Size(w)=R(t)dt。此公式是處理數(shù)據(jù)流速率變化、以及不同速率數(shù)據(jù)流的重要基礎(chǔ)。

樣本含量對典型相關(guān)系數(shù)的顯著性有較大影響［10］，所以下面給出有效窗口寬度的定義。

定義6(有效窗口寬度) 有效窗口寬度定義了w中元組數(shù)Size(w)的最小值，記為EffWin。對于滑動(dòng)窗口w，當(dāng)滿足:Size(w)=R(t)dt≥Eff-Win時(shí)，CCA的計(jì)算才有效。反之，當(dāng)Size(w)=R(t)dt＜EffWin時(shí)，窗口w內(nèi)包含的元組數(shù)過少，會(huì)造成相關(guān)性不顯著、計(jì)算精度低，因而不足以驗(yàn)證數(shù)據(jù)流的相關(guān)性。依據(jù)物聯(lián)網(wǎng)數(shù)據(jù)流的維度數(shù)、數(shù)據(jù)統(tǒng)計(jì)特性，選取適當(dāng)?shù)挠行Т翱趯挾菶ffWin值，對于保證數(shù)據(jù)流典型相關(guān)分析的實(shí)時(shí)性、準(zhǔn)確性和高效性有重要意義。

定義7(最大等待時(shí)間) 定義最大等待時(shí)間Δt，使得在 Δt時(shí)間內(nèi)至少對數(shù)據(jù)流計(jì)算一次CCA，以滿足物聯(lián)網(wǎng)數(shù)據(jù)流典型相關(guān)分析的實(shí)時(shí)性要求。

定義8(有效窗口所需時(shí)間) 定義有效窗口所需時(shí)間為 TEffWin，滿足R(t)dt=EffWin。TEffWin表示，若以有效窗口寬度EffWin為步長進(jìn)行窗口的滑動(dòng)，則下一滑動(dòng)窗口w達(dá)到EffWin所需的時(shí)間。其中，TEffWin是和數(shù)據(jù)流速率R(t)相關(guān)的一個(gè)變值，在本文中滿足TEffWin≤Δt。

定義9(CCA計(jì)算時(shí)間)。TCCA表示對數(shù)據(jù)規(guī)模為(EffWin×(p+q))的數(shù)據(jù)流計(jì)算一次CCA所需要的時(shí)間。在本文中滿足TCCA≤TEffWin。

2.3 臨界速率計(jì)算及自適應(yīng)窗口滑動(dòng)

數(shù)據(jù)流的處理以自適應(yīng)的、近似查詢?yōu)槠浜诵募夹g(shù)［11］。因此首先計(jì)算數(shù)據(jù)流的兩個(gè)臨界速率，并以此為基礎(chǔ)設(shè)計(jì)不同的窗口滑動(dòng)策略，以保證數(shù)據(jù)流典型相關(guān)分析的實(shí)時(shí)性、準(zhǔn)確性和高效性。

依據(jù)數(shù)據(jù)流處理實(shí)時(shí)性和有效性的要求，由定義6和7可知，當(dāng)滿足公式R(t)dt=Eff-Win時(shí)，可以得到臨界速率R1。當(dāng)數(shù)據(jù)流的速率R(t)≤R1時(shí)，R(t)dt≤EffWin，則每隔 Δt對數(shù)據(jù)流計(jì)算一次CCA，滑動(dòng)窗口以Δt為步長進(jìn)行滑動(dòng)。同時(shí)，下一滑動(dòng)窗口w的結(jié)束時(shí)間為tu+1=tu+Δt，w 的開始時(shí)間tl+1由公式 Size(w)=R(t)dt=R(t)dt=EffWin計(jì)算得到。此時(shí)，既滿足了數(shù)據(jù)流處理的實(shí)時(shí)性，又保證了CCA計(jì)算的有效性。

由于數(shù)據(jù)流速率在短時(shí)間內(nèi)變化較小，所以，對于以上兩個(gè)臨界速率可以采用估算的方式獲得，即 R1=EffWin/Δt和 R2=EffWin/TCCA。

另一個(gè)問題是:物聯(lián)網(wǎng)數(shù)據(jù)流之間可能存在速率差異，從而造成相同時(shí)間內(nèi)滑動(dòng)窗口中的數(shù)據(jù)元組數(shù)的差異。由于CCA計(jì)算需要兩數(shù)據(jù)流的滑動(dòng)窗口具有相同的元組數(shù)，所以對于數(shù)據(jù)流速率不一致的情況，首先需要保證兩數(shù)據(jù)流滑動(dòng)窗口都達(dá)到有效窗口寬度EffWin的要求:

而對于超出EffWin的元組，則可以通過采樣的方式將數(shù)據(jù)元組數(shù)降低到有效元組個(gè)數(shù)。

2.4 算法流程

依據(jù)所計(jì)算的臨界速率及自適應(yīng)窗口滑動(dòng)策略，算法具體流程如下:

也許與王羲之喜鵝有關(guān)，華堂村的白鵝養(yǎng)殖歷史悠久，遠(yuǎn)近聞名.華堂村的白鵝養(yǎng)殖一直是一家一戶主要利用天然雜草、采用傳統(tǒng)的放牧方式養(yǎng)殖，在本地集市上出售，收益很低.隨著放牧地減少，現(xiàn)在幾乎沒有農(nóng)戶飼養(yǎng)了.

輸入:tu時(shí)刻數(shù)據(jù)流X和Y，其維數(shù)分別為p和q，速率分別為RX(t)和RY(t);

步驟1 初始化參數(shù)最大等待時(shí)間Δt、有效窗口寬度EffWin和CCA計(jì)算時(shí)間TCCA;

步驟2 計(jì)算臨界速率R1和R2;

步驟 3R(t)=MIN(RX(t)，RY(t));

步驟4 數(shù)據(jù)流速率與臨街速率對比及策略選擇:

如果R(t)≤R1，則以Δt為步長進(jìn)行窗口滑動(dòng);

如果R1＜R(t)≤R2，則以 EffWin為步長進(jìn)行窗口滑動(dòng);

如果R(t)＞R2，則以TCCA為步長進(jìn)行窗口滑動(dòng);

步驟6 計(jì)算CCA;

輸出:tu時(shí)刻數(shù)據(jù)流X和Y之間的典型相關(guān)系數(shù) ρk和對應(yīng)的投影向量 αk和 βk(k=1，2，…，p)。

3 實(shí)驗(yàn)

利用提出的算法模擬物聯(lián)網(wǎng)數(shù)據(jù)流的實(shí)驗(yàn)，說明算法的執(zhí)行流程及效果。

實(shí)驗(yàn)選取UCI標(biāo)準(zhǔn)數(shù)據(jù)集:臭氧含量檢測數(shù)據(jù)集 (Ozone Level Detection Data Set，ODS)［12］。該數(shù)據(jù)集包括兩組數(shù)據(jù)，分別記錄了1小時(shí)和8小時(shí)的觀測值，樣本容量為2536，有效維數(shù)為71維。另外，對該數(shù)據(jù)集缺失值進(jìn)行填充處理，為滿足數(shù)據(jù)流模擬實(shí)驗(yàn)要求，采用對ODS數(shù)據(jù)集進(jìn)行復(fù)制接續(xù)的方式解決。

ODS數(shù)據(jù)集為靜態(tài)采樣，本實(shí)驗(yàn)給定仿真速率函數(shù)R(t)=MIN(RX(t)，RY(t))模擬數(shù)據(jù)流速率的不同情況。

R(t)=5×(10+humps(0.01×(-0.7×t+160)))

并給定 Δt=10s，EffWin=500，TCCA=1s(Matlab中CCA計(jì)算矩陣規(guī)模為500×(71+71)的實(shí)際時(shí)間為0.935 502)，得到臨界速率值為R1=50和R2=500。實(shí)驗(yàn)結(jié)果如圖2。

圖2數(shù)據(jù)流速率和自適應(yīng)窗口滑動(dòng)

當(dāng)數(shù)據(jù)流速率低于50時(shí)，則以最大等待時(shí)間Δt=10 s為步長進(jìn)行窗口的滑動(dòng);當(dāng)數(shù)據(jù)流速率在50和500之間時(shí)，則以EffWin=500為步長進(jìn)行窗口滑動(dòng)，相應(yīng)的滑動(dòng)時(shí)間隨數(shù)據(jù)流速率而變化;當(dāng)數(shù)據(jù)流速率高于500時(shí)，則以TCCA=1 s為步長進(jìn)行窗口滑動(dòng)，并對到達(dá)的數(shù)據(jù)進(jìn)行采樣將數(shù)據(jù)量縮減到EffWin=500。實(shí)驗(yàn)結(jié)果驗(yàn)證了自適應(yīng)窗口滑動(dòng)策略和動(dòng)態(tài)調(diào)整滑動(dòng)窗口寬度的思想，從而保證了數(shù)據(jù)流典型相關(guān)分析的實(shí)時(shí)性、準(zhǔn)確性和高效性。

對以上的滑動(dòng)窗口計(jì)算CCA所得部分結(jié)果如表1。

表1 數(shù)據(jù)流X和Y的典型相關(guān)分析部分結(jié)果

實(shí)驗(yàn)結(jié)果表明，針對物聯(lián)網(wǎng)數(shù)據(jù)流的典型相關(guān)分析，可以用來判斷事件源X和Y的相關(guān)性，同時(shí)可以定量判斷具體是哪些傳感器感知的信息占主導(dǎo)作用，以及相關(guān)模式的性質(zhì)，進(jìn)而為物聯(lián)網(wǎng)數(shù)據(jù)流的關(guān)聯(lián)規(guī)則挖掘以及數(shù)據(jù)挖掘的后期處理提供參考。

4 結(jié)論

傳統(tǒng)的數(shù)據(jù)流典型相關(guān)分析分析算法沒有考慮數(shù)據(jù)流速率的動(dòng)態(tài)特性，不適用于物聯(lián)網(wǎng)的實(shí)際情況。針對物聯(lián)網(wǎng)數(shù)據(jù)流具有變化和不一致的速率問題，依據(jù)典型相關(guān)分析理論，研究物聯(lián)網(wǎng)數(shù)據(jù)流之間的相關(guān)性，提出基于自適應(yīng)窗口滑動(dòng)的數(shù)據(jù)流典型相關(guān)分析算法。實(shí)驗(yàn)結(jié)果表明，算法可以保證物聯(lián)網(wǎng)數(shù)據(jù)流典型相關(guān)分析的實(shí)時(shí)性、準(zhǔn)確性和高效性。

［1］WANG Yongli，ZHANG Gongxuan，QIAN Jiangbo.ApproxCCA:an approximate correlation analysis algorithm for multidimensional data streams［J］.Knowledge-Based Systems，2011，24(7):952-962.

［2］楊學(xué)梅，董逸生，徐宏炳，等.高維數(shù)據(jù)流的在線相關(guān)分析［J］.計(jì)算機(jī)研究與發(fā)展，2006，43(10):1744-1750.

［3］王永利，徐宏炳，董逸生，等.基于低階近似的多維數(shù)據(jù)流相關(guān)性分析［J］.電子學(xué)報(bào)，2006，34(2):293-300.

［4］STUDIPTO G，GUNOPULOS D，NICK K.Correlating synchronous and asynchronous data streams［C］.Acm SIGKDD，USA，2003:529-534.

［5］HAROLD H.Relations between two sets of variates［J］.Biometrika，1936，28(3/4):321-377.

［6］孫權(quán)森，曾生根，王平安，等.典型相關(guān)分析的理論及其在特征融合中的應(yīng)用［J］.計(jì)算機(jī)學(xué)報(bào)，2005，28(9):1524-1533.

［7］KAMALIKA C，SHAM M K，KAREN L，et al.Multiview clustering via canonical correlation analysis［C］.ICML＇09 Proceedings of the 26th Annual International Conference on Machine Learning，New York，USA，2009:129-136.

［8］OLCAY K，ETHEM A，OLEG V F.Canonical correlation analysis using within-class coupling［J］.Pattern Recognition Letters，2011，32(2):134-144.

［9］黃樹成，曲亞輝.數(shù)據(jù)流分類技術(shù)研究綜述［J］.計(jì)算機(jī)應(yīng)用研究，2009，(10):3604-3609.

［10］張路.典型相關(guān)分析應(yīng)用常見問題分析及處理［J］.沈陽體育學(xué)院學(xué)報(bào).2011，30(5)，125-127.

［11］楊穎，韓忠明，楊磊.數(shù)據(jù)流的核心技術(shù)與應(yīng)用發(fā)展研究綜述［J］.計(jì)算機(jī)應(yīng)用研究，2005，(11):4-7.

［12］UCI氧含量檢測數(shù)據(jù)集［EB/OL］.［2013-10-05］.http:∥archive.ics.uci.edu/ml/datasets/Ozone+Level+Detection.