基于SimHash的數(shù)據(jù)流分層遺忘概要結(jié)構(gòu)

未春鳳　趙淑賢

摘要：數(shù)據(jù)流處理的關(guān)鍵是應(yīng)用高效的單趟掃描算法，創(chuàng)建數(shù)據(jù)流的概要結(jié)構(gòu)。現(xiàn)有的概要結(jié)構(gòu)存在著重構(gòu)誤差較大的缺點(diǎn)。作者針對這個問題，結(jié)合數(shù)據(jù)流分層遺忘概要結(jié)構(gòu)，采用simHash算法提取數(shù)據(jù)流中的概要信息，形成一種新的數(shù)據(jù)流分層遺忘概要結(jié)構(gòu)（simHash-Based Hierarchical Amnesic Synopsis，SH-HAS）。本文將SH-HAS結(jié)構(gòu)用在CUP99和Covertype數(shù)據(jù)集上，實(shí)驗(yàn)驗(yàn)證了該結(jié)構(gòu)的可靠性和穩(wěn)定性。

關(guān)鍵詞：數(shù)據(jù)流;概要結(jié)構(gòu);simHash;分層遺忘

中圖分類號：TP311 ? ? ? ?文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2019）15-0006-02

隨著計算機(jī)網(wǎng)絡(luò)和各類電子設(shè)備的應(yīng)用，越來越多的數(shù)據(jù)以流的形式出現(xiàn)，這種新的數(shù)據(jù)形式被稱為數(shù)據(jù)流[1]。數(shù)據(jù)流具有實(shí)時性、有序性、高速性、演化性、無限性等特性[2]。這使得傳統(tǒng)的數(shù)據(jù)挖掘方法不能直接應(yīng)用到數(shù)據(jù)流上。

因?yàn)閿?shù)據(jù)流具有無限到達(dá)的特性，導(dǎo)致現(xiàn)有的計算機(jī)系統(tǒng)不能存儲全部的數(shù)據(jù)流。針對這一問題，學(xué)者提出了建立數(shù)據(jù)流的概要結(jié)構(gòu)，以便保存數(shù)據(jù)流的概要信息和根據(jù)該結(jié)構(gòu)提供數(shù)據(jù)流的近似處理結(jié)果。數(shù)據(jù)流概要結(jié)構(gòu)是存儲數(shù)據(jù)流概要信息的一種結(jié)構(gòu)，旨在使用較小的數(shù)據(jù)規(guī)模代表全體數(shù)據(jù)，稱為概要結(jié)構(gòu)（synopsis structure）[3]?，F(xiàn)有的數(shù)據(jù)流概要結(jié)構(gòu)主要通過直方圖、抽樣、小波、隨機(jī)投影和散列方法獲取數(shù)據(jù)流的概要信息。

分層遺忘概要（Hierarchical Amnesic Synopsis，簡稱HAS）[4]，是陳華輝提出的一種基于數(shù)據(jù)流遺忘特性的概要結(jié)構(gòu)構(gòu)造框架。其他學(xué)者在這方面也進(jìn)行了許多的研究，例如文獻(xiàn)[5-7]。這些方法能有效地獲取數(shù)據(jù)流概要信息，但存在著重構(gòu)誤差較大的缺點(diǎn)。

simHash算法由Google的工程師于2007年提出，在文檔去重和文本相似度檢索等領(lǐng)域。學(xué)者將SimHash算法用于數(shù)據(jù)的相似性檢索[8-10]，并取得了較好的效果。

SimHash算法既可以高效地壓縮原始數(shù)據(jù)，又是一種降維方法。本文利用simHash算法在數(shù)據(jù)壓縮方面的高效性，結(jié)合數(shù)據(jù)流的HAS結(jié)構(gòu)，提出一種基于simHash的數(shù)據(jù)流分層遺忘概要結(jié)構(gòu)（simHash-Based Hierarchical Amnesic Synopsis，簡稱SH-HAS）。該算法的主要思想為：采用simHash算法提取數(shù)據(jù)流上新到的數(shù)據(jù)子序列的概要信息，創(chuàng)建對應(yīng)的數(shù)據(jù)節(jié)點(diǎn)并添加到SH-HAS結(jié)構(gòu)中;當(dāng)SH-HAS結(jié)構(gòu)中某層的數(shù)據(jù)節(jié)點(diǎn)個數(shù)達(dá)到上限，則將當(dāng)前層節(jié)點(diǎn)相加成K個節(jié)點(diǎn)并插入該結(jié)構(gòu)的上一層;隨著數(shù)據(jù)流的到來，動態(tài)調(diào)整該結(jié)構(gòu)。本文將該結(jié)構(gòu)用在CUP99和Covertype數(shù)據(jù)集上，實(shí)驗(yàn)驗(yàn)證了該結(jié)構(gòu)的可靠性和穩(wěn)定性。

1基于simHash的數(shù)據(jù)流分層概要結(jié)構(gòu)

simHash算法[9]屬于前述方法中的散列方法。它既是一種數(shù)據(jù)相似度計算方法，又是一種數(shù)據(jù)維度削減方法，用以解決數(shù)據(jù)流維度高和數(shù)據(jù)無限的問題。

1.1 分層概要結(jié)構(gòu)

數(shù)據(jù)流除了具有前述的特點(diǎn)外，其數(shù)據(jù)的影響是隨時間衰減的，表現(xiàn)為近期的數(shù)據(jù)價值更大。在分層概要結(jié)構(gòu)中，數(shù)據(jù)所處的層數(shù)越低，說明數(shù)據(jù)到達(dá)的時間較晚;層數(shù)越高說明數(shù)據(jù)到達(dá)的時間較早。

1.2 數(shù)據(jù)定義

在SH-HAS結(jié)構(gòu)中數(shù)據(jù)節(jié)點(diǎn)[P（D）]=[ts，n，X，Γ]，其中[ts]為該數(shù)據(jù)節(jié)點(diǎn)的時間戳，記錄D中最后一個數(shù)據(jù)的到達(dá)時刻;n為D中數(shù)據(jù)個數(shù)[D];[X]為D中數(shù)據(jù)的均值;[Γ]表示采用simHash算法計算出的數(shù)據(jù)概要信息。

1.2.3 SH-HAS結(jié)構(gòu)的動態(tài)維護(hù)

隨著數(shù)據(jù)的到達(dá)，為了使SH-HAS結(jié)構(gòu)中保存的信息能無限接近真實(shí)的數(shù)據(jù)流，需要對此結(jié)構(gòu)進(jìn)行動態(tài)更新維護(hù)。數(shù)據(jù)流上的SH-HAS結(jié)構(gòu)的動態(tài)維護(hù)算法如圖1所示。算法的空間和時間復(fù)雜性在文獻(xiàn)[4]中已經(jīng)被證明，在此不再贅述。

2 實(shí)驗(yàn)及分析

2.1 數(shù)據(jù)集及評價標(biāo)準(zhǔn)

本文使用UCI（University of California Irvine）[11]的機(jī)器學(xué)習(xí)庫中的KDDCUP99和Covertype數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)集，并使用相對重構(gòu)誤差來評價實(shí)驗(yàn)結(jié)果。

設(shè)有數(shù)據(jù)序列[D=（X1，X2，...，Xn）]，設(shè)[D']為重構(gòu)得到的重構(gòu)數(shù)據(jù)集，其相對重構(gòu)誤差定義為式（1）：

其中符號[∥x∥]表示向量x的2范數(shù)。

2.2 實(shí)驗(yàn)及結(jié)果分析

2.2.1實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)中修改MOA系統(tǒng)lancher文件模擬數(shù)據(jù)流的到達(dá)，將數(shù)據(jù)流上每2000條數(shù)據(jù)劃分為一個子序列。本文實(shí)驗(yàn)比較了Sampling、Histogram和SH-HAS方法在數(shù)據(jù)流上的相對重構(gòu)誤差。

2.2.2實(shí)驗(yàn)結(jié)果及分析

因?yàn)槠邢?，在此僅列出數(shù)據(jù)集Covertype上的部分實(shí)驗(yàn)結(jié)果。圖2分別截取了一部分實(shí)驗(yàn)數(shù)據(jù)，記載了將Sampling、Histogram、SH-HAS方法應(yīng)用在Covertype數(shù)據(jù)集的相對重構(gòu)誤差。從圖2中可以看出， SH-HAS方法較Sampling、Histogram方法相對重構(gòu)誤差明顯降低。

3結(jié)語

本文針對現(xiàn)有數(shù)據(jù)流概要結(jié)構(gòu)存在著重構(gòu)誤差較大的缺點(diǎn)，采用simHash算法提取數(shù)據(jù)流中的概要信息，形成一種新的數(shù)據(jù)流分層遺忘概要結(jié)構(gòu)（SH-HAS）。該結(jié)構(gòu)采用simHash算法提取數(shù)據(jù)流上新到的數(shù)據(jù)子序列的概要信息，創(chuàng)建對應(yīng)的數(shù)據(jù)節(jié)點(diǎn)并添加到SH-HAS結(jié)構(gòu)中;當(dāng)SH-HAS結(jié)構(gòu)中某層的數(shù)據(jù)節(jié)點(diǎn)個數(shù)達(dá)到上限，則將當(dāng)前層節(jié)點(diǎn)相加成K個節(jié)點(diǎn)并插入該結(jié)構(gòu)的上一層;隨著數(shù)據(jù)流的到來，動態(tài)調(diào)整該結(jié)構(gòu)。實(shí)驗(yàn)結(jié)果表明SH-HAS結(jié)構(gòu)可以大大減小相對重構(gòu)誤差。下一步可開展基于SH-HAS結(jié)構(gòu)的數(shù)據(jù)流相似性判斷和分類等處理方法的研究。

參考文獻(xiàn)：

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

[2] 李南.概念漂移數(shù)據(jù)流分類算法及應(yīng)用[D].福建師范大學(xué)，2013.

[3] 龍門，夏靖波，張子陽.基于概要數(shù)據(jù)結(jié)構(gòu)的網(wǎng)絡(luò)異常檢測方法[J].計算機(jī)應(yīng)用與軟件，2011，04：186-188.

[4] 陳華輝.基于遺忘特性的數(shù)據(jù)流概要結(jié)構(gòu)及其應(yīng)用研究[D].復(fù)旦大學(xué)，2008.

[5] Pang C，Zhang Q，Zhou X，et al.Computing unrestricted synopses under maximum error bound[J].Algorithmica，2013，65（1）：1-42.

[6] Pham D S，Venkatesh S，Lazarescu M，et al.Anomaly detection in large-scale data stream networks[J]. Data Mining and Knowledge Discovery，2014，28（1）：145-189.

[8] Graham Cormode;S.Muthukrishnan.An Improved Data Stream Summary：The Count-Min Sketch and Its Applications[A].2004

[10] Xu X，Gao C，Pei J，et al.Continuous similarity search for evolving queries[J].Knowledge and Information Systems，2014：1-30.

[11] http：//www.ics.uci

【通聯(lián)編輯：唐一東】