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

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

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

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

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

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

1 相關(guān)理論

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

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

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

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

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

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

2.1 CCA計算有效性和實時性問題

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

2.2 符號及定義

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

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

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

本文使用基于時間定義的滑動窗口模型。

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

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

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

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

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

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

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

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

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

2.3 臨界速率計算及自適應窗口滑動

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

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

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

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

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

2.4 算法流程

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

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

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

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

步驟2 計算臨界速率R1和R2;

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

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

如果R(t)≤R1，則以Δt為步長進行窗口滑動;

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

如果R(t)＞R2，則以TCCA為步長進行窗口滑動;

步驟6 計算CCA;

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

3 實驗

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

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

ODS數(shù)據(jù)集為靜態(tài)采樣，本實驗給定仿真速率函數(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計算矩陣規(guī)模為500×(71+71)的實際時間為0.935 502)，得到臨界速率值為R1=50和R2=500。實驗結(jié)果如圖2。

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

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

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

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

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

4 結(jié)論

傳統(tǒng)的數(shù)據(jù)流典型相關(guān)分析分析算法沒有考慮數(shù)據(jù)流速率的動態(tài)特性，不適用于物聯(lián)網(wǎng)的實際情況。針對物聯(lián)網(wǎng)數(shù)據(jù)流具有變化和不一致的速率問題，依據(jù)典型相關(guān)分析理論，研究物聯(lián)網(wǎng)數(shù)據(jù)流之間的相關(guān)性，提出基于自適應窗口滑動的數(shù)據(jù)流典型相關(guān)分析算法。實驗結(jié)果表明，算法可以保證物聯(lián)網(wǎng)數(shù)據(jù)流典型相關(guā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］楊學梅，董逸生，徐宏炳，等.高維數(shù)據(jù)流的在線相關(guān)分析［J］.計算機研究與發(fā)展，2006，43(10):1744-1750.

［3］王永利，徐宏炳，董逸生，等.基于低階近似的多維數(shù)據(jù)流相關(guān)性分析［J］.電子學報，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)分析的理論及其在特征融合中的應用［J］.計算機學報，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］.計算機應用研究，2009，(10):3604-3609.

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

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

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