自適應窗口滑動的物聯網數據流典型相關分析

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

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

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

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

針對以上問題，提出一種基于自適應窗口滑動的物聯網數據流典型相關分析算法，根據數據流速率的變化，對滑動窗口進行自適應設計、動態調整窗口的滑動策略，最后將其應用在物聯網數據流之間的相關性分析之中。

1 相關理論

1.1 典型相關分析

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

1.2 物聯網數據流的典型相關分析

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

圖1 物聯網中無線傳感器網絡的數據流

2 基于自適應窗口滑動的物聯網數據流CCA算法

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

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

2.2 符號及定義

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

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

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

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

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

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

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

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

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

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

定義7(最大等待時間) 定義最大等待時間Δt，使得在 Δt時間內至少對數據流計算一次CCA，以滿足物聯網數據流典型相關分析的實時性要求。

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

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

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

數據流的處理以自適應的、近似查詢為其核心技術［11］。因此首先計算數據流的兩個臨界速率，并以此為基礎設計不同的窗口滑動策略，以保證數據流典型相關分析的實時性、準確性和高效性。

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

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

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

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

2.4 算法流程

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

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

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

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

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

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

步驟4 數據流速率與臨街速率對比及策略選擇:

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

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

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

步驟6 計算CCA;

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

3 實驗

利用提出的算法模擬物聯網數據流的實驗，說明算法的執行流程及效果。

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

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

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

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

圖2數據流速率和自適應窗口滑動

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

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

表1 數據流X和Y的典型相關分析部分結果

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

4 結論

傳統的數據流典型相關分析分析算法沒有考慮數據流速率的動態特性，不適用于物聯網的實際情況。針對物聯網數據流具有變化和不一致的速率問題，依據典型相關分析理論，研究物聯網數據流之間的相關性，提出基于自適應窗口滑動的數據流典型相關分析算法。實驗結果表明，算法可以保證物聯網數據流典型相關分析的實時性、準確性和高效性。

［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］楊學梅，董逸生，徐宏炳，等.高維數據流的在線相關分析［J］.計算機研究與發展，2006，43(10):1744-1750.

［3］王永利，徐宏炳，董逸生，等.基于低階近似的多維數據流相關性分析［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］孫權森，曾生根，王平安，等.典型相關分析的理論及其在特征融合中的應用［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］黃樹成，曲亞輝.數據流分類技術研究綜述［J］.計算機應用研究，2009，(10):3604-3609.

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

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

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