針對(duì)具有稀疏性的流式大數(shù)據(jù)卸載方法

王 順，李振星，連增申，曾國(guó)蓀，丁春玲

（1.同濟(jì)大學(xué)電子與信息工程學(xué)院，上海200092；2.北京捷軟世紀(jì)信息技術(shù)有限公司，北京100085；3.同濟(jì)大學(xué)國(guó)家高性能計(jì)算機(jī)工程技術(shù)中心同濟(jì)分中心，上海201804；4.同濟(jì)大學(xué)化學(xué)科學(xué)與工程學(xué)院，上海200092）

隨著大數(shù)據(jù)技術(shù)的深入發(fā)展，傳統(tǒng)的批量計(jì)算越來(lái)越難以滿足大數(shù)據(jù)處理的及時(shí)性要求。與此同時(shí)，以海量數(shù)據(jù)持續(xù)到達(dá)、在線計(jì)算、實(shí)時(shí)響應(yīng)為計(jì)算模式的應(yīng)用變得越來(lái)越廣泛。一般地，持續(xù)到達(dá)的數(shù)據(jù)稱(chēng)為流數(shù)據(jù)，對(duì)流數(shù)據(jù)的計(jì)算稱(chēng)為流式計(jì)算，簡(jiǎn)稱(chēng)流計(jì)算。在短時(shí)間內(nèi)產(chǎn)生海量的流數(shù)據(jù)，稱(chēng)為流式大數(shù)據(jù)，也稱(chēng)為流大數(shù)據(jù)。在網(wǎng)絡(luò)數(shù)據(jù)監(jiān)控、金融分析、社交網(wǎng)絡(luò)、互聯(lián)網(wǎng)用戶(hù)行為在線分析、交通監(jiān)控等領(lǐng)域中都需要對(duì)流大數(shù)據(jù)進(jìn)行實(shí)時(shí)處理和響應(yīng)。由于流大數(shù)據(jù)是在線到達(dá)，且到達(dá)速度和數(shù)據(jù)特征是不確定的，這就使得流大數(shù)據(jù)的實(shí)時(shí)流量往往不可預(yù)知，從而可能導(dǎo)致因瞬時(shí)流量增大，無(wú)法被系統(tǒng)及時(shí)處理的過(guò)載現(xiàn)象。一旦發(fā)生嚴(yán)重過(guò)載，會(huì)導(dǎo)致計(jì)算系統(tǒng)性能的急劇下降。因此，如何解決過(guò)載問(wèn)題，是流大數(shù)據(jù)處理的一個(gè)重要問(wèn)題。

為了加快流大數(shù)據(jù)的處理速度，解決其中的過(guò)載問(wèn)題，研究人員從計(jì)算任務(wù)、體系結(jié)構(gòu)、數(shù)據(jù)本身等多方面進(jìn)行了大量研究。在計(jì)算任務(wù)方面，在云計(jì)算環(huán)境中通過(guò)優(yōu)化任務(wù)調(diào)度提高資源利用效率。在體系結(jié)構(gòu)方面，通過(guò)對(duì)計(jì)算系統(tǒng)的橫向或者縱向擴(kuò)展，提高計(jì)算能力。在數(shù)據(jù)方面，主要是通過(guò)對(duì)數(shù)據(jù)本身進(jìn)行近似處理，以便減少不必要的計(jì)算，從而加快計(jì)算速度。盡管通過(guò)任務(wù)-資源優(yōu)化調(diào)度可以提高資源利用效率，從而加快計(jì)算速度，但硬件計(jì)算能力總會(huì)有極限，因此不能從根本上解決過(guò)載問(wèn)題。并行分布式計(jì)算技術(shù)的發(fā)展提高了大數(shù)據(jù)計(jì)算的處理速度，但隨著節(jié)點(diǎn)的增加通信開(kāi)銷(xiāo)也會(huì)相應(yīng)增加，所以并不一定能夠提高計(jì)算速度，且在實(shí)際應(yīng)用中增加計(jì)算資源不僅會(huì)帶來(lái)巨大的成本開(kāi)銷(xiāo)，而且會(huì)造成計(jì)算資源的浪費(fèi)。

卸載技術(shù)［1-3］是其中的典型方法，即當(dāng)系統(tǒng)的處理能力小于當(dāng)前的計(jì)算負(fù)載時(shí)，通過(guò)拋棄一部分?jǐn)?shù)據(jù)來(lái)降低系統(tǒng)負(fù)載。在實(shí)際應(yīng)用環(huán)境中，一方面因噪聲、異常、重復(fù)、冗余等因素存在，會(huì)產(chǎn)生大量無(wú)用數(shù)據(jù)。另一方面，在流計(jì)算中往往只有部分?jǐn)?shù)據(jù)是計(jì)算任務(wù)所需的數(shù)據(jù)，例如在物聯(lián)網(wǎng)監(jiān)測(cè)預(yù)警應(yīng)用中，較少出現(xiàn)的數(shù)據(jù)是重要數(shù)據(jù)，在正常范圍內(nèi)則可能產(chǎn)生大量重復(fù)或無(wú)用的數(shù)據(jù)。因此，通過(guò)丟棄部分無(wú)用數(shù)據(jù)，從而加快處理速度的卸載技術(shù)是解決資源有限條件下流大數(shù)據(jù)過(guò)載問(wèn)題的有效方法。

自流計(jì)算出現(xiàn)以來(lái)，研究人員已對(duì)卸載方法進(jìn)行大量研究，這些卸載方法主要分為2類(lèi)，分別是隨機(jī)卸載和語(yǔ)義卸載。

隨機(jī)卸載是以隨機(jī)的方式丟棄部分?jǐn)?shù)據(jù)來(lái)加快整個(gè)流大數(shù)據(jù)的處理速度。Babcock等［4］提出以置信度為前提的隨機(jī)卸載策略。Tatbul等［5］提出了向流大數(shù)據(jù)查詢(xún)?nèi)蝿?wù)中插入或移除隨機(jī)卸載操作符的方法來(lái)處理負(fù)載波動(dòng)。閆鶯等［6］提出改進(jìn)的隨機(jī)卸載方法：基于概率的均勻降載策略和小窗口準(zhǔn)確降載策略，并結(jié)合查詢(xún)?nèi)蝿?wù)調(diào)度和卸載提高流大數(shù)據(jù)處理效率。隨機(jī)卸載方法雖然提高了流計(jì)算系統(tǒng)的吞吐量，顯著加快了流大數(shù)據(jù)的整體處理速度，但是隨機(jī)卸載可能會(huì)降低計(jì)算精度和服務(wù)質(zhì)量。

語(yǔ)義卸載是在一定條件下根據(jù)數(shù)據(jù)在應(yīng)用中的重要程度來(lái)選擇要卸載數(shù)據(jù)的方法。由于流大數(shù)據(jù)產(chǎn)生方式不同，數(shù)據(jù)結(jié)構(gòu)多樣，應(yīng)用場(chǎng)景各異，因此出現(xiàn)許多具體方法。文獻(xiàn)［7］針對(duì)固定結(jié)構(gòu)的元組流大數(shù)據(jù)，提出基于頻率的卸載方法，該方法根據(jù)數(shù)據(jù)出現(xiàn)的頻率判斷數(shù)據(jù)重要程度，通過(guò)在內(nèi)存中維護(hù)一個(gè)T-tree數(shù)據(jù)字典，卸載出現(xiàn)頻率較低的數(shù)據(jù)，實(shí)驗(yàn)結(jié)果表明該方法能支持高速率到達(dá)的流大數(shù)據(jù)卸載。Zhang等［8］提出一種基于反饋控制的自適應(yīng)卸載策略，首先對(duì)流大數(shù)據(jù)建立一個(gè)包括負(fù)載監(jiān)視器、反饋控制器、卸載器等模塊的卸載系統(tǒng)，然后使用根軌跡法設(shè)計(jì)反饋控制器，以便接收來(lái)自監(jiān)視器的反饋信息，進(jìn)行動(dòng)態(tài)自適應(yīng)卸載。文獻(xiàn)［9］提出基于執(zhí)行開(kāi)銷(xiāo)和數(shù)值分布優(yōu)先級(jí)的卸載算法，首先將數(shù)據(jù)在其值域上劃分成若干區(qū)域，然后根據(jù)不同區(qū)域數(shù)據(jù)在多個(gè)串聯(lián)或并聯(lián)操作符上的執(zhí)行路徑計(jì)算出執(zhí)行開(kāi)銷(xiāo)，在內(nèi)存中維護(hù)數(shù)值和開(kāi)銷(xiāo)二維表，根據(jù)數(shù)據(jù)優(yōu)先級(jí)進(jìn)行卸載。Maison等［10］提出基于預(yù)測(cè)的流大數(shù)據(jù)卸載框架，通過(guò)對(duì)高斯分布的流大數(shù)據(jù)進(jìn)行流量和數(shù)值分布的預(yù)測(cè)，結(jié)合不同的查詢(xún)操作符，給出相應(yīng)丟棄最大、最小等的不同的卸載策略，實(shí)驗(yàn)表明該方法能有效提高服從高斯分布數(shù)據(jù)源的卸載精度和數(shù)據(jù)吞吐量。文獻(xiàn)［11］提出基于直方圖的卸載方法，該方法針對(duì)緩存的數(shù)據(jù)構(gòu)建一種塔形矩陣的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，每桶提取一個(gè)代表數(shù)據(jù)并刪除該桶中其余數(shù)據(jù)，將每桶的代表數(shù)據(jù)組成新的數(shù)據(jù)參與任務(wù)處理，該方法在一定程度上提高卸載精度，但海量數(shù)據(jù)處理時(shí)存在性能不高的問(wèn)題。文獻(xiàn)［12］針對(duì)一段時(shí)間內(nèi)接收的以資源描述框架（RDF）表示的流大數(shù)據(jù)，根據(jù)數(shù)據(jù)間的圖結(jié)構(gòu)關(guān)聯(lián)關(guān)系，分析其語(yǔ)義信息從而卸載語(yǔ)義上的無(wú)效數(shù)據(jù)，但該方法僅適用于數(shù)據(jù)間關(guān)聯(lián)關(guān)系已知的流大數(shù)據(jù)卸載。

目前，學(xué)者們針對(duì)多種場(chǎng)景對(duì)流大數(shù)據(jù)卸載技術(shù)進(jìn)行了大量的研究工作，包括基于數(shù)據(jù)出現(xiàn)頻率［7］、任務(wù)反饋控制［8，13］、維護(hù)優(yōu)先級(jí)表或樹(shù)［9，14］、流大數(shù)據(jù)到達(dá)規(guī)律預(yù)測(cè)［10］、數(shù)據(jù)關(guān)聯(lián)圖［12］等方面。盡管有些學(xué)者已提出基于離群點(diǎn)和基于任務(wù)內(nèi)容的語(yǔ)義卸載方法，然而尚未發(fā)現(xiàn)對(duì)數(shù)據(jù)距離進(jìn)行動(dòng)態(tài)彈性度量的研究工作，也未發(fā)現(xiàn)對(duì)數(shù)據(jù)處理行為等價(jià)度量的深入研究工作。為此，本文針對(duì)2種典型的應(yīng)用場(chǎng)景進(jìn)行分析和建模，使用彈性距離機(jī)制提出基于離心率的卸載方法，使用數(shù)據(jù)處理行為相似性提出基于等價(jià)類(lèi)劃分的卸載方法。

1 流大數(shù)據(jù)及其稀疏性

1.1 流大數(shù)據(jù)處理的一般過(guò)程

根據(jù)流大數(shù)據(jù)的處理過(guò)程，一般可以將流大數(shù)據(jù)的生命周期分為數(shù)據(jù)到達(dá)、數(shù)據(jù)預(yù)處理、任務(wù)計(jì)算、應(yīng)用挖掘、事后存儲(chǔ)等多個(gè)階段，如圖1所示。

圖1 流大數(shù)據(jù)處理的一般過(guò)程Fig.1 The general process of big data stream processing

在數(shù)據(jù)到達(dá)階段，數(shù)據(jù)源可分為單源、多源。從數(shù)據(jù)結(jié)構(gòu)上來(lái)講，可分為固定結(jié)構(gòu)和可變結(jié)構(gòu)流大數(shù)據(jù)。從數(shù)據(jù)之間的關(guān)聯(lián)關(guān)系上來(lái)講，可分為無(wú)關(guān)聯(lián)流大數(shù)據(jù)和有關(guān)聯(lián)流大數(shù)據(jù)，例如社交網(wǎng)絡(luò)流是圖結(jié)構(gòu)流大數(shù)據(jù)，而定點(diǎn)監(jiān)測(cè)流大數(shù)據(jù)則是無(wú)關(guān)聯(lián)的。從流大數(shù)據(jù)的到達(dá)方式上來(lái)講，可分為穩(wěn)定到達(dá)、不確定到達(dá)。目前，流計(jì)算尚無(wú)對(duì)所有形態(tài)流大數(shù)據(jù)的統(tǒng)一計(jì)算模型。因此，不同的數(shù)據(jù)到達(dá)方式，決定著流大數(shù)據(jù)的不同形態(tài)，后續(xù)數(shù)據(jù)預(yù)處理、任務(wù)計(jì)算、應(yīng)用挖掘等方法也各不相同。本文假設(shè)所討論的流大數(shù)據(jù)，以元組為數(shù)據(jù)的最小單位，它是相互無(wú)關(guān)聯(lián)的、結(jié)構(gòu)相同的數(shù)據(jù)實(shí)體，由現(xiàn)實(shí)應(yīng)用場(chǎng)合源源不斷地產(chǎn)生，并依次交由流大數(shù)據(jù)計(jì)算系統(tǒng)處理。

定義1流數(shù)據(jù)。指隨時(shí)間變化，持續(xù)產(chǎn)生的大量無(wú)關(guān)聯(lián)、固定結(jié)構(gòu)的元組數(shù)據(jù)序列。假設(shè)一條流數(shù)據(jù)記為D=｛d1，d2，…，dn｝，其中di表示第i個(gè)元組，每個(gè)元組都有k個(gè)屬性組成，di帶屬性的記法為di（ai,1，ai,2，…，ai,k），其中ai,j表示第i個(gè)數(shù)據(jù)的第j個(gè)屬性，1≤j≤k。當(dāng)流數(shù)據(jù)在短時(shí)內(nèi)海量到達(dá)時(shí)稱(chēng)為流大數(shù)據(jù)。

如圖1所示，在流大數(shù)據(jù)處理的整個(gè)過(guò)程中，數(shù)據(jù)預(yù)處理階段主要任務(wù)是對(duì)實(shí)時(shí)到達(dá)的流大數(shù)據(jù)進(jìn)行在線檢測(cè)、清洗、去噪、補(bǔ)全和卸載等預(yù)處理，以便保證流計(jì)算系統(tǒng)的正常運(yùn)行，并且為后續(xù)流大數(shù)據(jù)的處理做準(zhǔn)備工作。本文就是在該階段找出使用價(jià)值較低的數(shù)據(jù)并卸載。任務(wù)計(jì)算和應(yīng)用挖掘階段則是對(duì)上一階段輸出的數(shù)據(jù)進(jìn)行流計(jì)算任務(wù)處理。根據(jù)不同的應(yīng)用場(chǎng)景，流大數(shù)據(jù)系統(tǒng)所執(zhí)行的計(jì)算任務(wù)也各不相同。為不失一般性，如圖1所示，用無(wú)環(huán)有向圖（directed acyclic graph，DAG）來(lái)描述流大數(shù)據(jù)挖掘處理的計(jì)算任務(wù)。海量流大數(shù)據(jù)在DAG任務(wù)處理下，任務(wù)程序的動(dòng)態(tài)執(zhí)行路徑可能十分復(fù)雜，不同的執(zhí)行路徑其開(kāi)銷(xiāo)也可能不同，因此數(shù)據(jù)的功能行為也是對(duì)數(shù)據(jù)進(jìn)行分類(lèi)的一個(gè)有效方法。為此研究基于預(yù)處理自動(dòng)機(jī)的行為相似性度量方法。

本文流大數(shù)據(jù)處理模式為每隔一個(gè)固定的時(shí)間周期T0對(duì)到達(dá)的數(shù)據(jù)實(shí)施集中卸載，這似乎和流大數(shù)據(jù)的實(shí)時(shí)處理的要求不相符，但事實(shí)上實(shí)時(shí)處理是相對(duì)的，只要T0設(shè)置足夠小，應(yīng)該能夠達(dá)到流大數(shù)據(jù)及時(shí)處理的目標(biāo)。假設(shè)計(jì)算負(fù)載和數(shù)據(jù)量正相關(guān)，數(shù)據(jù)量越大，則計(jì)算負(fù)載也越大。如果過(guò)載，要求在數(shù)據(jù)處理前卸載一定數(shù)量的數(shù)據(jù)即可。

1.2 流大數(shù)據(jù)的稀疏性

定義2流大數(shù)據(jù)的稀疏性。流大數(shù)據(jù)的稀疏性指流大數(shù)據(jù)具有2個(gè)方面的特性，一是數(shù)據(jù)的各個(gè)屬性值呈現(xiàn)出稠密不均的非均勻分布的特性；二是流大數(shù)據(jù)的流量隨時(shí)間不斷變化。

2 流大數(shù)據(jù)卸載方法

流大數(shù)據(jù)分布稀疏性的現(xiàn)象是客觀存在的，這也造成每個(gè)數(shù)據(jù)的價(jià)值各不相同。顯然，低價(jià)值數(shù)據(jù)的處理將占用不必要的計(jì)算資源。為了應(yīng)對(duì)流大數(shù)據(jù)稀疏性中的流量波動(dòng)特征導(dǎo)致的過(guò)載問(wèn)題，針對(duì)2種應(yīng)用場(chǎng)景進(jìn)行分析和建模，并針對(duì)這2種場(chǎng)景提出相應(yīng)的卸載算法，旨在保證計(jì)算系統(tǒng)實(shí)時(shí)性前提下提高卸載準(zhǔn)確性，提高服務(wù)質(zhì)量。

2.1 普通均勻業(yè)務(wù)流大數(shù)據(jù)分析應(yīng)用場(chǎng)景

在許多普通應(yīng)用中，數(shù)據(jù)源產(chǎn)生的數(shù)據(jù)呈現(xiàn)高斯分布，即數(shù)據(jù)在靠近聚集中心的周?chē)霈F(xiàn)概率較大，分布較密集；離聚集中心遠(yuǎn)的數(shù)據(jù)出現(xiàn)概率較小，分布較稀疏。如電子商務(wù)交易中，希望在線分析用戶(hù)購(gòu)買(mǎi)偏好，大部分正常業(yè)務(wù)數(shù)據(jù)的消費(fèi)金額、購(gòu)買(mǎi)數(shù)量等數(shù)據(jù)都在某個(gè)區(qū)間內(nèi)，但也有一小部分客戶(hù)會(huì)購(gòu)買(mǎi)金額、數(shù)量、種類(lèi)等極大或者極小的情況存在。在這類(lèi)應(yīng)用中，那些分布集中的數(shù)據(jù)是重要的數(shù)據(jù)，那些稀疏的離群數(shù)據(jù)往往被認(rèn)為是無(wú)用數(shù)據(jù)。因此，流計(jì)算時(shí)，卸載應(yīng)該丟棄掉那些離群數(shù)據(jù)。

據(jù)定義5，計(jì)算離心率的關(guān)鍵是度量2個(gè)點(diǎn)之間的距離，不同的距離計(jì)算方法對(duì)離心率計(jì)算的準(zhǔn)確性有直接影響，其中最典型的是歐氏距離計(jì)算方法。由于數(shù)據(jù)處于臨界邊緣時(shí)，使用傳統(tǒng)的距離計(jì)算方法無(wú)法明顯區(qū)分異常的離群點(diǎn)和正常的聚集點(diǎn)。為此提出彈性距離的計(jì)算方法：對(duì)于那些距離中心點(diǎn)越近的數(shù)據(jù)，縮小它們的差異，使它們具有更明顯的聚集特征；而對(duì)于那些距離中心點(diǎn)越遠(yuǎn)的數(shù)據(jù)，放大它們的差異，使它們具有更明顯的稀疏和離群特征，從而更有利于對(duì)異常的離群點(diǎn)進(jìn)行甄別。

定義7彈性距離。指數(shù)據(jù)點(diǎn)到中心點(diǎn)的距離進(jìn)行縮放后的距離。假設(shè)數(shù)據(jù)集的中心為dc（ac，1，ac，2，…，ac，k），對(duì)任意數(shù)據(jù)點(diǎn)di（ai，1，ai，2，…，ai，k）與dc的距離進(jìn)行彈性度量，記di與dc的彈性距離為L(zhǎng)（di，dc），則L（di，dc）=f（di，dc）×l（di，dc）。其中，f（di，dc）表示以dc為中心點(diǎn)的彈性系數(shù)，令f（di，dc）=eα(l(di，dc))+β，它是以歐氏距離為自變量的指數(shù)函數(shù)。由于指數(shù)函數(shù)的單調(diào)遞增特性，當(dāng)di與dc的距離越近時(shí)，彈性系數(shù)f（di，dc）越小。當(dāng)di與dc的距離越遠(yuǎn)時(shí)，彈性系數(shù)越大。通過(guò)將彈性系數(shù)與歐氏距離相乘，對(duì)點(diǎn)di與dc的距離進(jìn)行彈性度量，用于對(duì)實(shí)時(shí)到達(dá)流大數(shù)據(jù)的離心率進(jìn)行計(jì)算，從而對(duì)遠(yuǎn)偏離的數(shù)據(jù)進(jìn)行卸載，顯然更具有合理性。

根據(jù)普通均勻業(yè)務(wù)的流大數(shù)據(jù)分析應(yīng)用場(chǎng)景的數(shù)據(jù)特點(diǎn)可知，在固定時(shí)間周期T0內(nèi)，到達(dá)的數(shù)據(jù)為內(nèi)部稠密、外部稀疏的“超球”分布，卸載時(shí)應(yīng)丟棄偏離中心點(diǎn)較遠(yuǎn)的數(shù)據(jù)。根據(jù)定義5，以T0周期內(nèi)到達(dá)的所有數(shù)據(jù)為點(diǎn)集、以該點(diǎn)集的平均值作為中心點(diǎn)、以所有點(diǎn)到中心的平均距離為半徑計(jì)算每個(gè)數(shù)據(jù)的離心率，并根據(jù)離心率預(yù)先設(shè)定的閾值決定該數(shù)據(jù)是否被卸載。但是，由于流大數(shù)據(jù)的海量性，可能有大量數(shù)據(jù)的離心率處于閾值邊緣。為了更好地區(qū)分稀疏和稠密數(shù)據(jù)，尤其是在閾值附近的數(shù)據(jù)，使用彈性距離計(jì)算每個(gè)數(shù)據(jù)的離心率。

定義8彈性離心率。指以彈性距離為數(shù)據(jù)間測(cè)度的離心率。已知在T0內(nèi)到達(dá)的流數(shù)據(jù)為D=｛d1，d2，…dn｝，di表示D中第i個(gè)數(shù)據(jù)，dc（ac，1，ac，2，…，ac，k）為D的中心點(diǎn)，L（di，dc）表示di與中心點(diǎn)的彈性距離，記di的彈性離心率為ψ（di，dc），則

由定義8可知，離心率值域?yàn)椋?，1），彈性系數(shù)f（di，dc）=eα(l(di，dc))+β值域?yàn)椋?+β，eα+β），當(dāng)l（di，dc）=1/α×ln（1-β）為彈性縮放的分界點(diǎn)，其中參數(shù)α、β由實(shí)際應(yīng)用需求確定。同時(shí)，根據(jù)實(shí)驗(yàn)和歷史經(jīng)驗(yàn)，給定該T0時(shí)間周期內(nèi)的離心率分割閾值ε0，那么離心率大于閾值ε0視為無(wú)用點(diǎn)全部拋棄。根據(jù)上述過(guò)程，基于離心率卸載算法的偽代碼如下。

算法1基于離心率的卸載算法（CBLS），輸入：D=｛d1，d2，…dn｝，ε0，其中D為預(yù)定周期T0到達(dá)的流大數(shù)據(jù)，ε0為卸載閾值；輸出：D′，其中D′為D中要卸載的數(shù)據(jù)。

其中1、2行是初始化并計(jì)算中心點(diǎn)，3～8行是計(jì)算半徑r，第12行是計(jì)算每個(gè)數(shù)據(jù)的彈性離心率。13～14行根據(jù)彈性離心率的大小判斷是否需要卸載。其中，時(shí)間復(fù)雜度的關(guān)鍵在于彈性離心率的計(jì)算。D中數(shù)據(jù)點(diǎn)的個(gè)數(shù)為n，整個(gè)算法求中心點(diǎn)和半徑分別需要n次計(jì)算，之后每個(gè)數(shù)據(jù)都只需根據(jù)公式計(jì)算一次彈性離心率，因此算法1的時(shí)間復(fù)雜度為O（n）。

該算法是對(duì)一個(gè)T0時(shí)間周期到達(dá)的數(shù)據(jù)進(jìn)行卸載處理。對(duì)于持續(xù)到達(dá)的流大數(shù)據(jù)，可以通過(guò)計(jì)時(shí)，每隔T0周期，循環(huán)調(diào)用該算法，即可實(shí)現(xiàn)對(duì)該應(yīng)用場(chǎng)景下流大數(shù)據(jù)的持續(xù)卸載處理。

2.2 異常檢測(cè)業(yè)務(wù)流大數(shù)據(jù)應(yīng)用場(chǎng)景

在異常檢測(cè)類(lèi)應(yīng)用場(chǎng)景中，用戶(hù)主要對(duì)那些較少出現(xiàn)的數(shù)據(jù)特別關(guān)注，而對(duì)經(jīng)常出現(xiàn)的數(shù)據(jù)則不太關(guān)心。例如，公安犯罪監(jiān)測(cè)、海關(guān)信息監(jiān)測(cè)等應(yīng)用中，違法信息往往在數(shù)額、數(shù)量、頻率等屬性上與通常數(shù)據(jù)明顯不同，因此這些數(shù)據(jù)屬于重要數(shù)據(jù)。又如，在有些物聯(lián)網(wǎng)應(yīng)用中，一旦檢測(cè)到不常見(jiàn)的溫度、濕度或者異常的化學(xué)物質(zhì)等信息，應(yīng)及時(shí)作出反應(yīng)。因此，在這類(lèi)應(yīng)用中，當(dāng)流數(shù)據(jù)新到達(dá)時(shí)，應(yīng)該特別關(guān)注異常數(shù)據(jù)。

2.2.1 流大數(shù)據(jù)的處理過(guò)程和行為

數(shù)據(jù)的作用和價(jià)值往往通過(guò)分析和處理來(lái)獲得。數(shù)據(jù)分析和處理往往具有復(fù)雜的計(jì)算過(guò)程，一般包含多個(gè)計(jì)算子任務(wù)，它們互為因果，交互作用，它們的動(dòng)態(tài)行為可抽象為有限狀態(tài)自動(dòng)機(jī)［15］。不同的輸入數(shù)據(jù)，在檢測(cè)預(yù)處理任務(wù)程序中可能產(chǎn)生不同的狀態(tài)轉(zhuǎn)移過(guò)程，即不同類(lèi)別的輸入數(shù)據(jù)在分析處理時(shí)，對(duì)應(yīng)的任務(wù)程序有不同處理過(guò)程或者行為。每個(gè)數(shù)據(jù)的處理過(guò)程或者行為體現(xiàn)了數(shù)據(jù)的價(jià)值和功能，因而記錄并比較每個(gè)數(shù)據(jù)的動(dòng)態(tài)處理行為，可以判斷出每個(gè)數(shù)據(jù)在該任務(wù)下的功能相似度。首先使用行為自動(dòng)機(jī)對(duì)流大數(shù)據(jù)的檢測(cè)預(yù)處理過(guò)程進(jìn)行建模，并根據(jù)數(shù)據(jù)預(yù)處理的行為進(jìn)行等價(jià)類(lèi)劃分，為流大數(shù)據(jù)卸載提供決策依據(jù)。將流大數(shù)據(jù)檢測(cè)預(yù)處理任務(wù)的計(jì)算過(guò)程抽象為一個(gè)5元組，即行為自動(dòng)機(jī)M=＜S，S0，C，E，F(xiàn)＞，其中S是有窮狀態(tài)集合；S0是初始狀態(tài)集；C是狀態(tài)轉(zhuǎn)移約束和開(kāi)銷(xiāo)權(quán)重的集合，用＜ci，wi＞表示；E=S×（Φ（C）×2C×S）是狀態(tài)轉(zhuǎn)換關(guān)系的集合，邊e=＜s，a，δ，s′，w＞表示當(dāng)輸入為a時(shí)從狀態(tài)s到s′的轉(zhuǎn)換，δ表示一個(gè)條件約束，w表示權(quán)重；F是終止?fàn)顟B(tài)集合。如圖2所示給出了一個(gè)舉例。

圖2 任務(wù)預(yù)處理自動(dòng)機(jī)Fig.2 Task automata machine

定義9數(shù)據(jù)處理行為。假設(shè)流大數(shù)據(jù)處理的過(guò)程用自動(dòng)機(jī)M=＜S，S0，C，E，F(xiàn)＞描述，那么數(shù)據(jù)di的處理行為是指di在自動(dòng)機(jī)M中的狀態(tài)轉(zhuǎn)移路徑，由狀態(tài)節(jié)點(diǎn)和邊的交替序組成，記為Pi=s0ex…svey…ezsif，其中s0為初始狀態(tài)，s0∈S0，sif為結(jié)束狀態(tài)且sif∈F，sv和ey為Pi的中間狀態(tài)，且sv∈S，ey∈E。

例如，如圖2所示，該自動(dòng)機(jī)有9個(gè)狀態(tài)，數(shù)據(jù)處理的初始狀態(tài)為s0，結(jié)束狀態(tài)為s8，s2～s7為中間狀態(tài)，s0到s8之間的不同路徑對(duì)應(yīng)不同數(shù)據(jù)的處理行為。特別地，假設(shè)圖2箭頭路徑為數(shù)據(jù)d1的處理過(guò)程，則d1的處理行為P1=s0e1s1e2s2e4s4e7s1e2s2e3s3e8s5e11s8。

為了得到數(shù)據(jù)處理行為序列，構(gòu)建預(yù)處理自動(dòng)機(jī)程序。首先，對(duì)數(shù)據(jù)任務(wù)進(jìn)行抽象，將一個(gè)流大數(shù)據(jù)處理任務(wù)劃分成多個(gè)子任務(wù)，根據(jù)子任務(wù)之間的相互關(guān)系構(gòu)建任務(wù)DAG圖。然后，根據(jù)DAG任務(wù)每個(gè)節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)移條件編寫(xiě)預(yù)處理自動(dòng)機(jī)，記錄每個(gè)數(shù)據(jù)到達(dá)時(shí)的狀態(tài)轉(zhuǎn)移路徑，此即為通過(guò)預(yù)處理獲取數(shù)據(jù)處理行為的基本方法。

2.2.2 流大數(shù)據(jù)處理行為相似性度量

一般地，如果2個(gè)處理行為的開(kāi)始狀態(tài)和結(jié)束狀態(tài)相同，且中間處理過(guò)程也存在一定程度的相同，那么我們認(rèn)為這2個(gè)處理行為具有相似性。

定義10行為相似。設(shè)數(shù)據(jù)di的處理行為Pi=si0eiu…exsx…eivsif，數(shù)據(jù)dj的處理行為Pj=sj0eju…eysy…ejvsjf，其中si0和sj0分別為Pi和Pj的起始節(jié)點(diǎn)，sif和sjf分別為Pi和Pj的終止節(jié)點(diǎn)。如果有si0=sj0，si=sjf，且Pi的邊集Ei與Pj的邊集Ej有Ei∩Ej≠?，或Pi的狀態(tài)集Si與Pj的狀態(tài)集Sj有Si∩Sj≠?，則稱(chēng)數(shù)據(jù)di與數(shù)據(jù)dj處理行為相似。

如果2個(gè)數(shù)據(jù)存在處理行為相似，那么它們處理過(guò)程的狀態(tài)轉(zhuǎn)移路徑有3種情形：①完全相同；②有若干交點(diǎn)，但不存在循環(huán)；③有若干交點(diǎn)，且存在循環(huán)。如果將每次循環(huán)的邊都看作不同的邊，那么無(wú)論在某個(gè)節(jié)點(diǎn)或多個(gè)節(jié)點(diǎn)之間是否存在循環(huán)，它們可以統(tǒng)一歸納為情形②。例如，假設(shè)2個(gè)數(shù)據(jù)處理行為分別為Pi=s0e1s1e3s3e5s4e6s5e8s8和Pj=s0e2s2e4s3e5s4e7s6e9s7e10s8，如圖3所示，除了初始節(jié)點(diǎn)s0和結(jié)束節(jié)點(diǎn)s8之外有2個(gè)交點(diǎn)s3、s4。由于Pi與Pj節(jié)點(diǎn)和邊個(gè)數(shù)可能不同，無(wú)法一一對(duì)應(yīng)比較，因此根據(jù)處理行為交點(diǎn)的個(gè)數(shù)將Pi與Pj分為若干個(gè)相似階段，分別從節(jié)點(diǎn)和邊的相似程度來(lái)度量。

圖3 數(shù)據(jù)處理行為相似的情況Fig.3 Similarity of data processing behavior

設(shè)Si∩Sj=Sc，且|Sc|=m，則Pi與Pj可分為m+1個(gè)相似階段。設(shè)Pi的第p個(gè)相似階段有Mi，p個(gè)節(jié)點(diǎn)。Pi的任意節(jié)點(diǎn)sr的后繼節(jié)點(diǎn)記為V（Pi，sr），若V（Pi，sr）?Pj，令V（Pi，sr）=1；如果V（Pi，sr）∈Pj，令V（Pi，sr）=0；路徑Pi中Sr節(jié)點(diǎn)的后繼邊記為E（Pi，sr），且令E（Pi，sr）=wr，其中wr為E（Pi，sr）的開(kāi)銷(xiāo)權(quán)重。記數(shù)據(jù)di、dj處理行為Pi與Pj相似度為B（di，dj），則

其中σ、ρ分別表示頂點(diǎn)和邊在實(shí)際應(yīng)用中開(kāi)銷(xiāo)的重要程度，且σ+ρ=1。由B（di，dj）的計(jì)算式可知其取值范圍為［0，1］。當(dāng)Pi和Pj完全相同時(shí)，B（di，dj）=1，當(dāng)di和dj不存在行為相似即Ei∩Ej=?，或者Si∩Sj=?時(shí)，B（di，dj）=0。

2.2.3 流大數(shù)據(jù)綜合相似度計(jì)算

2個(gè)數(shù)據(jù)處理行為的相似度反映了2個(gè)數(shù)據(jù)的價(jià)值的相似程度。但是，即使具有相同的處理行為，因數(shù)據(jù)本身的差異，在進(jìn)行異常數(shù)據(jù)分析檢測(cè)時(shí)，不同數(shù)據(jù)應(yīng)該區(qū)別對(duì)待。為此，在行為相似的基礎(chǔ)上，結(jié)合純數(shù)據(jù)的相似性，進(jìn)行綜合相似性度量。根據(jù)文獻(xiàn)［16］的相似性定義，2個(gè)數(shù)據(jù)d1、d2的純數(shù)據(jù)相似度表示F（d1，d2）=1/（1+l（d1，d2）），其中l(wèi)（d1，d2）為數(shù)據(jù)d1、d2間的距離，參見(jiàn)定義 3。數(shù)據(jù)d1、d2的綜合相似度用純數(shù)據(jù)相似度與數(shù)據(jù)處理行為相似度的積表示，記為H（d1，d2），則

顯然，H（d1，d2）是取值為［0，1］內(nèi)的實(shí)數(shù)，取值越大，表示數(shù)據(jù)d1和d2在處理過(guò)程和數(shù)值上具有越高的相似程度。反之，表示d1和d2在處理過(guò)程和數(shù)值上差異越大。當(dāng)H（d1，d2）=1時(shí)表示這2個(gè)數(shù)據(jù)完全相同。該公式綜合考慮了數(shù)據(jù)的純數(shù)據(jù)相似性與功能相似性，分別從靜態(tài)和動(dòng)態(tài)2個(gè)方面來(lái)度量數(shù)據(jù)間的相似性，為后文等價(jià)類(lèi)劃分提供了依據(jù)。

定義11數(shù)據(jù)等價(jià)類(lèi)。在一個(gè)大數(shù)據(jù)集合中，如果2個(gè)數(shù)據(jù)的綜合相似度大于某個(gè)給定的閾值，則稱(chēng)它們之間具有等價(jià)關(guān)系。滿足上述等價(jià)關(guān)系的數(shù)據(jù)構(gòu)成的子集稱(chēng)為一個(gè)數(shù)據(jù)等價(jià)類(lèi)。

2.2.4 基于等價(jià)類(lèi)劃分的卸載算法

基于等價(jià)類(lèi)劃分的卸載方法的主要思想是：在時(shí)間周期T0內(nèi)到達(dá)的數(shù)據(jù)中，找出差異度最大的那個(gè)數(shù)據(jù)，以此作為基點(diǎn)，并且根據(jù)數(shù)據(jù)綜合相似度劃分成2個(gè)等價(jià)類(lèi)，一個(gè)是異常等價(jià)類(lèi)，另一個(gè)是正常等價(jià)類(lèi)。在異常檢測(cè)業(yè)務(wù)流大數(shù)據(jù)應(yīng)用場(chǎng)景下，特別需要關(guān)注異常數(shù)據(jù)，理應(yīng)保留異常等價(jià)類(lèi)，因此可以卸載正常等價(jià)類(lèi)。同時(shí)，根據(jù)實(shí)驗(yàn)和歷史經(jīng)驗(yàn)，可以設(shè)定一個(gè)綜合相似度的閾值η0，那么當(dāng)流大數(shù)據(jù)中的單個(gè)數(shù)據(jù)的綜合相似度大于閾值η0時(shí)，歸為異常等價(jià)類(lèi)。反之，歸為正常等價(jià)類(lèi)。根據(jù)上述算法思想，下面給出基于等價(jià)類(lèi)劃分卸載算法的偽代碼。

算法2基于等價(jià)類(lèi)劃分的卸載算法（equivalence based load shedding，EBLS）輸入：D=｛d1，d2，…，dn｝，η0，其中D為流大數(shù)據(jù)，η0為綜合相似度閾值。輸出：D′，D′。其中D′為異常等價(jià)類(lèi)，D′為正常等價(jià)類(lèi)，即要卸載的數(shù)據(jù)。

//計(jì)算每個(gè)數(shù)據(jù)的差異度

//求數(shù)據(jù)差異度

//求d*為差異度最大的數(shù)據(jù)

5.d*←argdimax｛φ（d1），φ（d2），...，φ（dn）｝；

//計(jì)算每個(gè)數(shù)據(jù)與d*的綜合相似度

6.while（D≠?）

7.｛di←get_one_data（D）；//逐個(gè)取D中數(shù)據(jù)

8.D←D-｛dj｝；

9.H（dj，d*）←calculate_simulation（di，dj）；//根據(jù)式（2）計(jì)算dj與d*的綜合相似度

10.if（H（dj，d*）＞η0）

11.D′←D′+｛dj｝；

//異常等價(jià)類(lèi)

12.else

13.D′←D′+｛dj｝；

//正常等價(jià)類(lèi)

14.｝

15.returnD′，D′；

16.｝

其中，第1行是初始化，第2～4行是計(jì)算每個(gè)數(shù)據(jù)的差異度，第5行是求有最大差異度的數(shù)據(jù)d*，第7～13行是計(jì)算每個(gè)數(shù)據(jù)與d*的相似度，并根據(jù)閾值η0判斷等價(jià)類(lèi)。第2、4、5行均需要計(jì)算n次，6～14行為一層循環(huán)，也為n次，因此算法的時(shí)間復(fù)雜度為O（n）。

EBLS算法是對(duì)單個(gè)T0時(shí)間周期到達(dá)的數(shù)據(jù)進(jìn)行的處理，應(yīng)將正常等價(jià)類(lèi)D′卸載。對(duì)于持續(xù)到達(dá)的流大數(shù)據(jù)，通過(guò)計(jì)時(shí)，每隔T0周期循環(huán)調(diào)用該算法，即可實(shí)現(xiàn)對(duì)異常監(jiān)測(cè)應(yīng)用場(chǎng)景下流大數(shù)據(jù)持續(xù)的卸載處理。

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

為了分析所提出的卸載算法的有效性，設(shè)計(jì)了一系列對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)使用的計(jì)算機(jī)為Dell T330，內(nèi)含 Intel Xeon E3-1220 V5CPU@3.0GHz，16.00 GB內(nèi)存，2TB主硬盤(pán)，CentOS 6.5（64位）操作系統(tǒng)。算法CBLS、EBLS以及其他傳統(tǒng)卸載算法均采用Storm框架+JavaSE8.0編程實(shí)現(xiàn)。由于算法在重復(fù)執(zhí)行時(shí)，每次結(jié)果可能會(huì)有微小差異，因此每組實(shí)驗(yàn)重復(fù)進(jìn)行5次，結(jié)果取其平均值分別進(jìn)行算法有效性評(píng)價(jià)。

實(shí)驗(yàn)采用Storm流大數(shù)據(jù)處理框架，實(shí)現(xiàn)流大數(shù)據(jù)的產(chǎn)生、到達(dá)、卸載處理。通過(guò)編寫(xiě)讀取程序，實(shí)現(xiàn)將靜態(tài)數(shù)據(jù)集轉(zhuǎn)換為不確定方式到達(dá)的動(dòng)態(tài)流大數(shù)據(jù)，經(jīng)標(biāo)準(zhǔn)化后將數(shù)據(jù)發(fā)送到卸載處理程序。實(shí)驗(yàn)共分為2組，分別利用算法CBLS和算法EBLS，與傳統(tǒng)的直接卸載、隨機(jī)卸載、基于頻率的卸載［7］方法進(jìn)行比較。所謂直接卸載，是指當(dāng)?shù)竭_(dá)的數(shù)據(jù)個(gè)數(shù)超過(guò)系統(tǒng)所能處理的極限時(shí)直接卸載后續(xù)新到達(dá)的過(guò)載數(shù)據(jù)。所謂隨機(jī)卸載，是指當(dāng)?shù)竭_(dá)的流大數(shù)據(jù)個(gè)數(shù)超過(guò)系統(tǒng)所能處理的極限時(shí)隨機(jī)選擇一批數(shù)據(jù)丟棄的卸載方法。基于頻率的卸載方法的關(guān)鍵在于它構(gòu)造了基于內(nèi)存的T-tree數(shù)據(jù)結(jié)構(gòu)記錄數(shù)據(jù)的頻率，根據(jù)數(shù)據(jù)出現(xiàn)的頻率選擇卸載數(shù)據(jù)的方法。對(duì)其加以改造，與本文其他對(duì)比算法相同，每個(gè)固定時(shí)間T0進(jìn)行一次卸載。實(shí)驗(yàn)算法均通過(guò)對(duì)Storm框架中任務(wù)節(jié)點(diǎn)過(guò)載處理邏輯改造實(shí)現(xiàn)。為了評(píng)估數(shù)據(jù)卸載效果，最常用的數(shù)據(jù)質(zhì)量的評(píng)價(jià)標(biāo)準(zhǔn)是平方距離和（SSQ），為了便于比較，這里把平均平方距離和作為數(shù)據(jù)卸載質(zhì)量的度量指標(biāo)。

3.1 普通均勻業(yè)務(wù)分析流大數(shù)據(jù)應(yīng)用實(shí)驗(yàn)

實(shí)驗(yàn)使用Yahoo時(shí)間序列數(shù)據(jù)集［17］以及人工合成數(shù)據(jù)，2種數(shù)據(jù)按1：1混合作為實(shí)驗(yàn)數(shù)據(jù)。人工合成數(shù)據(jù)按照文獻(xiàn)［18］生成服從高斯分布的數(shù)據(jù)。獲取了672 000條數(shù)據(jù)，經(jīng)過(guò)處理后每個(gè)元數(shù)據(jù)含8個(gè)屬性，經(jīng)過(guò)極差標(biāo)準(zhǔn)化方法對(duì)數(shù)據(jù)進(jìn)行規(guī)范化處理后，所有屬性取值映射到［0，1］區(qū)間。根據(jù)應(yīng)用場(chǎng)景的要求，模擬該數(shù)據(jù)集大部分?jǐn)?shù)據(jù)相對(duì)均勻集中，小部分?jǐn)?shù)據(jù)較為稀疏，符合普通均勻業(yè)務(wù)應(yīng)用場(chǎng)景。

為了對(duì)比4種算法的卸載效果，實(shí)驗(yàn)利用4種卸載算法都處理同一個(gè)數(shù)據(jù)集，分別卸載不同比例的數(shù)據(jù)，統(tǒng)計(jì)卸載后數(shù)據(jù)的平均SSQ。實(shí)驗(yàn)中，卸載比例從5%個(gè)增加到25%。其中，直接卸載算法選擇最后到達(dá)的那部分?jǐn)?shù)據(jù)卸載；隨機(jī)卸載算法從數(shù)據(jù)集中隨機(jī)選擇相應(yīng)比例數(shù)據(jù)卸載；基于頻率的卸載算法根據(jù)比例卸載T-tree上頻率較低的數(shù)據(jù)；本文CBLS算法根據(jù)經(jīng)驗(yàn)確定相應(yīng)卸載比例下的離心率閾值，從而進(jìn)行卸載處理。利用統(tǒng)計(jì)程序分別計(jì)算在使用每個(gè)算法處理后的平均SSQ。

為了直觀體現(xiàn)4種算法的卸載效果，特意選取當(dāng)卸載比例為5%時(shí)采用4種方法處理后的數(shù)據(jù)，取前2維作數(shù)據(jù)分布示意圖。如圖4所示，其中灰色星號(hào)點(diǎn)為要卸載的點(diǎn)，黑色點(diǎn)為保留點(diǎn)。圖4為直接卸載、隨機(jī)卸載、基于頻率卸載和CBLS算法的卸載示意圖。其中，圖4a、圖4b灰色點(diǎn)和黑色點(diǎn)混在一起，說(shuō)明這2個(gè)算法無(wú)法區(qū)分哪些是離群點(diǎn)。圖4c的周?chē)鸀榛疑?，而中間為黑色，說(shuō)明基于頻率卸載能夠較好理離群數(shù)據(jù)，但邊界不清。圖4d CBLS算法能夠比直接卸載和隨機(jī)卸載算法更明顯區(qū)分離心點(diǎn)。這從直觀上說(shuō)明CBLS算法有更高的卸載準(zhǔn)確性。

圖4 CBLS和傳統(tǒng)方法卸載質(zhì)量對(duì)比Fig.4 Quality comparison of load shedding between CBLS and traditional methods

為了更加客觀地對(duì)比4種算法在卸載準(zhǔn)確性上的差異，表1展示了4種卸載算法在卸載比例從5%到25%時(shí)相應(yīng)的平均SSQ值，并據(jù)此繪制成如圖5所示的數(shù)據(jù)質(zhì)量對(duì)比折線圖。在該場(chǎng)景下平均SSQ值越小，表示越能識(shí)別出無(wú)用數(shù)據(jù)，算法效果越好。

由圖5可以看出，在不同的卸載比例下，采用隨機(jī)卸載算法處理后的數(shù)據(jù)的平均SSQ值較為平穩(wěn)，采用直接卸載算法處理的平均SSQ值上下有波動(dòng)，且始終保持較高。而基于頻率的卸載方法和CBLS算法的平均SSQ值隨著卸載比例的增大卸載后不斷減小，但CBLS算法減小更快。這說(shuō)明在該場(chǎng)景下，隨著卸載比例的增大，CBLS算法卸載了更多的無(wú)用數(shù)據(jù)，相比其他算法具有更高的卸載準(zhǔn)確性。

表1 不同卸載方法的平均SSQTab.1 Average SSQ ofCBLS and traditional shedding methods

圖5 CBLS和傳統(tǒng)方法卸載不同比例質(zhì)量對(duì)比Fig.5 Quality comparison between CBLS and traditional methods when shedding different proportion

3.2 異常檢測(cè)業(yè)務(wù)流大數(shù)據(jù)應(yīng)用實(shí)驗(yàn)

在實(shí)驗(yàn)中，根據(jù)該應(yīng)用場(chǎng)景下數(shù)據(jù)分布特點(diǎn)，人工合成實(shí)驗(yàn)所需數(shù)據(jù)集。使用文獻(xiàn)［19］中的方法共生成613 450條數(shù)據(jù)，每個(gè)元數(shù)據(jù)包含10個(gè)數(shù)值屬性，經(jīng)規(guī)范化后所有屬性的取值均在［0，1］區(qū)間。根據(jù)應(yīng)用場(chǎng)景的要求，模擬的該數(shù)據(jù)集大部分?jǐn)?shù)據(jù)在較小的取值區(qū)間范圍均勻分布，部分異常數(shù)據(jù)則較為分散，符合異常檢測(cè)業(yè)務(wù)流大數(shù)據(jù)應(yīng)用場(chǎng)景。

同樣地，為了分析EBLS算法在異常檢測(cè)應(yīng)用場(chǎng)景下的卸載效果，實(shí)驗(yàn)對(duì)比了該算法與直接卸載、隨機(jī)卸載和基于頻率的卸載算法，在不同卸載比例下處理同一個(gè)數(shù)據(jù)集的平均SSQ值。其中，基于頻率的卸載算法根據(jù)比例卸載T-tree上頻率較高的數(shù)據(jù)。實(shí)驗(yàn)中，卸載比例從5%個(gè)增加到25%。其中，EBLS算法在不同卸載比例下的綜合相似度閾值η0通過(guò)經(jīng)驗(yàn)確定。在每個(gè)卸載算法處理后，都通過(guò)統(tǒng)計(jì)程序計(jì)算平均SSQ判斷卸載的有效性。

選取當(dāng)卸載比例為5%時(shí)，對(duì)采用4種方法處理后的數(shù)據(jù)取前2維作數(shù)據(jù)分布示意圖，如圖6所示，其中灰色星號(hào)點(diǎn)為要卸載的點(diǎn)，黑色點(diǎn)為保留點(diǎn)。圖6為直接卸載、隨機(jī)卸載和基于頻率的卸載和EBLS算法卸載效果示意圖，其中圖6a和圖6b灰色點(diǎn)分布在整個(gè)數(shù)據(jù)集，這顯示出這2種卸載算法會(huì)丟棄一部分異常數(shù)據(jù)。圖6c在中心部分能夠卸載更多的重復(fù)數(shù)據(jù)，但仍會(huì)卸載分布在邊緣的異常數(shù)據(jù)。圖6d能更多保留邊緣的異常數(shù)據(jù)，卸載正常數(shù)據(jù)。這4張圖從直觀上體現(xiàn)了EBLS卸載算法有較好的卸載準(zhǔn)確性。

圖6 EBLS和傳統(tǒng)方法卸載質(zhì)量對(duì)比Fig.6 Quality comparison of load shedding between EBLS and traditional methods

為了客觀對(duì)比4種算法的卸載效果，表2展示了4種卸載算法在卸載比例從5%到25%時(shí)，4種算法卸載處理后的平均SSQ值，并據(jù)此繪制成如圖7所示的數(shù)據(jù)質(zhì)量對(duì)比折線圖。在這種場(chǎng)景下平均SSQ值越大，表示越能識(shí)別出異常數(shù)據(jù)，也就是說(shuō)算法效果越好。

由圖7可見(jiàn)，利用4種卸載算法處理數(shù)據(jù)時(shí)，隨著卸載比例的增加直接卸載算法的平均SSQ值有一定的波動(dòng)，而隨機(jī)卸載算法總體較為平穩(wěn)，且直接卸載和隨機(jī)卸載算法的平均SSQ值明顯低于基于頻率的卸載算法和EBLS算法。但隨著卸載比例的增加，EBLS算法的平均SSQ值增長(zhǎng)明顯快于基于頻率的卸載算法，說(shuō)明在該場(chǎng)景下EBLS算法更具有效性。

表2 EBLS和傳統(tǒng)卸載方法的平均SSQTab.2 Average SSQ of EBLS and traditional shedding methods

圖7 EBLS和傳統(tǒng)方法卸載不同比例質(zhì)量對(duì)比Fig.7 Quality comparison between EBLS and traditional methods when shedding different proportion

綜上可知，在發(fā)生過(guò)載時(shí)使用了算法CBLS和算法EBLS卸載的準(zhǔn)確性明顯高于直接卸載和隨機(jī)卸載，能夠有效提高卸載準(zhǔn)確性。

4 結(jié)語(yǔ)

針對(duì)普通均勻業(yè)務(wù)流大數(shù)據(jù)應(yīng)用場(chǎng)景進(jìn)行分析，把數(shù)據(jù)看成空間中的點(diǎn)，將該場(chǎng)景下無(wú)效數(shù)據(jù)視為離群點(diǎn)，給出了數(shù)據(jù)間彈性距離度量方法對(duì)不同價(jià)值的數(shù)據(jù)進(jìn)行縮放，結(jié)合該應(yīng)用場(chǎng)景下流大數(shù)據(jù)的超球分布特點(diǎn)，提出了以數(shù)據(jù)離心率為依據(jù)的CBLS卸載算法。針對(duì)異常檢測(cè)業(yè)務(wù)流大數(shù)據(jù)應(yīng)用場(chǎng)景下，希望卸載行為相似差異度不大的數(shù)據(jù)的要求，采用預(yù)處理自動(dòng)機(jī)對(duì)數(shù)據(jù)處理過(guò)程進(jìn)行建模，給出了數(shù)據(jù)處理行為相似性度量方法，結(jié)合數(shù)據(jù)差異度給出了綜合相似性度量方法，并以此提出了基于等價(jià)類(lèi)劃分的EBLS卸載算法。最后，開(kāi)展了實(shí)驗(yàn)測(cè)試，分別在2種應(yīng)用場(chǎng)景的數(shù)據(jù)分布條件下，使用直接卸載、隨機(jī)卸載和本文提出的2種卸載算法，在處理過(guò)載流大數(shù)據(jù)時(shí)進(jìn)行對(duì)比實(shí)驗(yàn)，結(jié)果表明使用本文算法明顯提高了流大數(shù)據(jù)卸載的準(zhǔn)確性。

本文不足之處是未考慮流大數(shù)據(jù)之間有關(guān)聯(lián)的情況，也未考慮概念漂移情況下的數(shù)據(jù)卸載。為此，下一步工作將研究在多源流大數(shù)據(jù)之間存在相互關(guān)聯(lián)的情況下，如何有效地進(jìn)行流大數(shù)據(jù)的卸載處理。