數(shù)據(jù)流概要數(shù)據(jù)結(jié)構(gòu)在大型零售商業(yè)管理信息系統(tǒng)中的應(yīng)用

[摘要] 本文首先介紹了數(shù)據(jù)流概要數(shù)據(jù)結(jié)構(gòu)構(gòu)建技術(shù)及其發(fā)展現(xiàn)狀，說(shuō)明了數(shù)據(jù)流概要構(gòu)建技術(shù)應(yīng)用于大型零售商業(yè)管理信息系統(tǒng)中的必要性，分析了如何將數(shù)據(jù)流概要構(gòu)建技術(shù)應(yīng)用于大型零售商業(yè)管理信息系統(tǒng)中。

[關(guān)鍵詞] 數(shù)據(jù)流 概要數(shù)據(jù)結(jié)構(gòu) 零售商業(yè) 管理信息系統(tǒng)

一、引言

近年來(lái)在很多應(yīng)用領(lǐng)域中出現(xiàn)了一種新的數(shù)據(jù)模式，其數(shù)據(jù)不是以傳統(tǒng)的有限數(shù)據(jù)集形式，而是連續(xù)的數(shù)據(jù)流形式出現(xiàn)。這些應(yīng)用領(lǐng)域包括金融數(shù)據(jù)在線分析、商業(yè)交易數(shù)據(jù)處理、傳感器網(wǎng)絡(luò)、電信數(shù)據(jù)管理和網(wǎng)絡(luò)安全等。數(shù)據(jù)流中的數(shù)據(jù)基本元素仍然可能是關(guān)系元組，但數(shù)據(jù)的到達(dá)是快速、時(shí)變、不可預(yù)測(cè)和無(wú)限的數(shù)據(jù)流形式，不可能完全存儲(chǔ)原始數(shù)據(jù)。但是，對(duì)于很多應(yīng)用來(lái)說(shuō)，查詢歷史數(shù)據(jù)卻是很重要的。從而需要利用高效的近似處理算法，在有限的存儲(chǔ)空間中，建立和維護(hù)一個(gè)數(shù)據(jù)量遠(yuǎn)遠(yuǎn)小于其原始數(shù)據(jù)規(guī)模的概要數(shù)據(jù)結(jié)構(gòu)（Synopsis Data Structure）。數(shù)據(jù)流概要構(gòu)建技術(shù)的研究當(dāng)前數(shù)據(jù)流領(lǐng)域的研究熱點(diǎn)之一，已經(jīng)取得了一些研究成果。

二、數(shù)據(jù)流概要數(shù)據(jù)結(jié)構(gòu)

根據(jù)所處理數(shù)據(jù)的時(shí)序范圍，數(shù)據(jù)流處理模型可分為界標(biāo)窗口模型模型（Landmark Window Model）、滑動(dòng)窗口模型（Sliding Window Model）和快照模型（Snapshot Model）等多種子模。其中最常用的處理子模型是界標(biāo)窗口模型模型和滑動(dòng)窗口模型。界標(biāo)窗口模型是指在內(nèi)存中開(kāi)辟一個(gè)內(nèi)存空間，用來(lái)保存自某個(gè)初始時(shí)間點(diǎn)到當(dāng)前時(shí)間點(diǎn)范圍內(nèi)到達(dá)的數(shù)據(jù)元組。滑動(dòng)窗口模型是指在內(nèi)存中開(kāi)辟一個(gè)內(nèi)存空間，用來(lái)保存最近到達(dá)的數(shù)據(jù)，隨著新數(shù)據(jù)的不斷到達(dá)，滑動(dòng)窗口中的數(shù)據(jù)不斷被更新。滑動(dòng)窗口分為兩類(lèi)，一類(lèi)是基于數(shù)據(jù)元組個(gè)數(shù)定義的滑動(dòng)窗口，即在內(nèi)存中保存數(shù)據(jù)流中數(shù)量為常數(shù)m的最新到達(dá)的數(shù)據(jù)；另一類(lèi)是基于時(shí)間定義的滑動(dòng)窗口，即在內(nèi)存中保存數(shù)據(jù)流在最近Δt時(shí)間范圍內(nèi)到達(dá)的數(shù)據(jù)。基于不同數(shù)據(jù)流處理子模型構(gòu)建概要數(shù)據(jù)結(jié)構(gòu)有不同的近似處理算法和技術(shù)，下面簡(jiǎn)單介紹幾種常用的數(shù)據(jù)流概要數(shù)據(jù)結(jié)構(gòu)構(gòu)建方法和技術(shù)。

隨機(jī)抽樣方法從整個(gè)數(shù)據(jù)集中隨機(jī)抽取一部分?jǐn)?shù)據(jù)形成樣本集來(lái)描述數(shù)據(jù)的總體分布，根據(jù)該樣本集獲得對(duì)數(shù)據(jù)總體的近似查詢結(jié)果，是常用的基于界標(biāo)窗口模型和滑動(dòng)窗口模型概要數(shù)據(jù)結(jié)構(gòu)構(gòu)造方法。水庫(kù)抽樣（Reservoir Sampling）是一種經(jīng)典的在線均勻抽樣算法，可用于數(shù)據(jù)流的在線處理，可以適用于界標(biāo)窗口模型，但不能有效地處理數(shù)據(jù)的過(guò)期刪除，不適用于數(shù)據(jù)流滑動(dòng)窗口處理子模型。鏈?zhǔn)匠闃樱–hain-Sample）算法針對(duì)水庫(kù)抽樣進(jìn)行了改進(jìn)，是一種適用于基于數(shù)據(jù)元組個(gè)數(shù)的滑動(dòng)窗口的隨機(jī)抽樣算法。鏈?zhǔn)匠闃臃椒ɡ枚鄠€(gè)數(shù)據(jù)元組的“鏈”來(lái)處理過(guò)期數(shù)據(jù)問(wèn)題，能夠獲得整個(gè)滑動(dòng)窗口上的一個(gè)樣本集。優(yōu)先級(jí)抽樣（Priority-Sample）算法對(duì)每個(gè)數(shù)據(jù)元素隨機(jī)賦給一個(gè)0到1之間的優(yōu)先級(jí)數(shù)值，然后根據(jù)數(shù)據(jù)元組的優(yōu)先級(jí)數(shù)值和到達(dá)的時(shí)間先后來(lái)進(jìn)行排序，根據(jù)其順序來(lái)對(duì)樣本集進(jìn)行插入和刪除的維護(hù)。上述兩種抽樣算法屬于均勻抽樣，以相同的概率對(duì)數(shù)據(jù)流中到達(dá)的數(shù)據(jù)元組進(jìn)行隨機(jī)抽樣，文獻(xiàn)通過(guò)對(duì)水庫(kù)抽樣算法的改進(jìn)，給出了加權(quán)抽樣算法，該算法只需單遍掃描整個(gè)數(shù)據(jù)集就能實(shí)現(xiàn)對(duì)帶權(quán)值數(shù)據(jù)流中數(shù)據(jù)元組的隨機(jī)抽樣，是一種偏倚抽樣算法。

直方圖方法是根據(jù)實(shí)際數(shù)據(jù)的分布將數(shù)據(jù)劃分到一系列的區(qū)間（直方或桶）中，以桶為單位估算數(shù)據(jù)的分布。根據(jù)桶內(nèi)數(shù)據(jù)的分布情況，直方圖一般可分為等寬、變寬、偏向兩端等各種類(lèi)型。其中變寬直方圖又有等深（或等高）、V-最優(yōu)、壓縮、最大差異直方圖等各種類(lèi)型。直方圖可以簡(jiǎn)潔地表達(dá)一個(gè)數(shù)據(jù)集中數(shù)據(jù)值的分布情況，在傳統(tǒng)數(shù)據(jù)領(lǐng)域有著廣泛的應(yīng)用，有很多最優(yōu)直方圖和逼近最優(yōu)直方圖的構(gòu)造算法。但這些算法不能適用于數(shù)據(jù)流的處理。Guha等中把面向數(shù)據(jù)流的直方圖算法按照估算數(shù)據(jù)的不同范圍分為兩類(lèi)：Agglomerative類(lèi)算法和Fixed Window類(lèi)算法，并且通過(guò)改進(jìn)V-最優(yōu)直方圖維護(hù)算法，降低算法的空間和時(shí)間復(fù)雜度以適應(yīng)數(shù)據(jù)流的處理，提出了一種Fixed Window類(lèi)直方圖增量維護(hù)算法，在文獻(xiàn)提出了一種Agglomerative類(lèi)直方圖維護(hù)算法，構(gòu)造V-最優(yōu)直方圖的1＋ε逼近，但該算法僅僅適用于經(jīng)過(guò)數(shù)據(jù)排序的流數(shù)據(jù)處理，并且不能對(duì)直方圖進(jìn)行增量維護(hù)；Datar等提出了一種統(tǒng)計(jì)直方圖，稱(chēng)為指數(shù)直方圖（EM， Exponential Histogram），EM按照數(shù)據(jù)元組到達(dá)的順序構(gòu)建桶，可用于建立和維護(hù)基于滑動(dòng)窗口模型的概要數(shù)據(jù)結(jié)構(gòu)。

除隨機(jī)抽樣和直方圖外，Sketches技術(shù)、基本窗口和小波變換等也是構(gòu)建數(shù)據(jù)流概要結(jié)構(gòu)的常用方法和技術(shù)[6]。

三、概要數(shù)據(jù)結(jié)構(gòu)在大型零售商業(yè)管理信息系統(tǒng)中的應(yīng)用

零售商業(yè)企業(yè)的信息化建設(shè)的主要目標(biāo)是使商品數(shù)據(jù)流轉(zhuǎn)迅速通暢，經(jīng)營(yíng)管理信息準(zhǔn)確可靠，提高員工的辦事效率和有效支持經(jīng)營(yíng)管理決策等。一般來(lái)說(shuō)，大型零售商業(yè)企業(yè)具有組織機(jī)構(gòu)龐大，管理模式復(fù)雜，經(jīng)營(yíng)商品品種多，進(jìn)貨和銷(xiāo)售量大和職工人數(shù)眾多等特點(diǎn)，有著大量的商品銷(xiāo)售、顧客購(gòu)買(mǎi)和貨物進(jìn)出數(shù)據(jù)。當(dāng)前各個(gè)大型零售商業(yè)企業(yè)都有著用于執(zhí)行聯(lián)機(jī)事務(wù)和查詢處理的聯(lián)機(jī)操作數(shù)據(jù)庫(kù)和用于數(shù)據(jù)分析和決策支持的數(shù)據(jù)倉(cāng)庫(kù)和數(shù)據(jù)挖掘系統(tǒng)。其主要的數(shù)據(jù)處理方式是將聯(lián)機(jī)操作數(shù)據(jù)庫(kù)系統(tǒng)中的數(shù)據(jù)經(jīng)過(guò)清理、變換和集成裝入一個(gè)定時(shí)更新的數(shù)據(jù)倉(cāng)庫(kù)，然后在數(shù)據(jù)倉(cāng)庫(kù)系統(tǒng)上進(jìn)行數(shù)據(jù)分析，為經(jīng)營(yíng)管理者提供決策支持（如圖1）。

目前，大型零售商業(yè)企業(yè)的交易數(shù)據(jù)量都十分龐大，而且隨著時(shí)間的增長(zhǎng)急劇膨脹。這使得傳統(tǒng)數(shù)據(jù)庫(kù)和數(shù)據(jù)挖掘技術(shù)無(wú)法及時(shí)地對(duì)數(shù)據(jù)進(jìn)行有效管理和查詢處理。如沃爾瑪連鎖超市的日交易次數(shù)可達(dá)數(shù)十萬(wàn)，面對(duì)如此巨大數(shù)量的數(shù)據(jù)，處理或挖掘一天數(shù)據(jù)可能會(huì)花費(fèi)多于一天的時(shí)間，數(shù)據(jù)積累的速度要快于數(shù)據(jù)處理和挖掘的速度。即使能夠?qū)?jīng)過(guò)清理和集成后的數(shù)據(jù)進(jìn)行處理和挖掘，一般也需要一個(gè)很長(zhǎng)的周期，并且不能直接利用當(dāng)前最新的交易數(shù)據(jù)。從而不能快速響應(yīng)市場(chǎng)的變化，及時(shí)提高經(jīng)營(yíng)效率和服務(wù)質(zhì)量，在日趨激烈的市場(chǎng)競(jìng)爭(zhēng)中獲得先機(jī)。

大型零售商業(yè)企業(yè)的海量交易數(shù)據(jù)具有數(shù)據(jù)流的典型特征，是數(shù)據(jù)流處理和挖掘研究的主要應(yīng)用領(lǐng)域之一。我們可以將數(shù)據(jù)流概要數(shù)據(jù)結(jié)構(gòu)構(gòu)造技術(shù)應(yīng)用于大型零售商業(yè)企業(yè)的數(shù)據(jù)管理，在引入數(shù)據(jù)流概要數(shù)據(jù)結(jié)構(gòu)的大型零售商業(yè)管理系統(tǒng)中（如圖2），在實(shí)時(shí)更新聯(lián)機(jī)操作數(shù)據(jù)庫(kù)的同時(shí)，及時(shí)用最新的交易數(shù)據(jù)更新概要數(shù)據(jù)結(jié)構(gòu)。由于不同類(lèi)型查詢的需求不同，可能需要多個(gè)概要數(shù)據(jù)結(jié)構(gòu)同時(shí)存在。但相對(duì)于原始數(shù)據(jù)來(lái)說(shuō)，每個(gè)概要數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)量很少，所需存儲(chǔ)空間小于原始數(shù)據(jù)所需存儲(chǔ)空間幾個(gè)甚至幾十個(gè)數(shù)量級(jí)。綜合利用概要數(shù)據(jù)結(jié)構(gòu)和聯(lián)機(jī)操作數(shù)據(jù)庫(kù)系統(tǒng)既可以利用當(dāng)前最新的交易數(shù)據(jù)，又能利用歷史數(shù)據(jù)進(jìn)行查詢處理和數(shù)據(jù)分析，而且能比較快甚至實(shí)時(shí)地分析一些重要的商品銷(xiāo)售和顧客購(gòu)買(mǎi)數(shù)據(jù)，迅速獲得部分查詢和分析的結(jié)果，為經(jīng)營(yíng)管理者及時(shí)提供數(shù)據(jù)分析和決策支持信息。

最后需要說(shuō)明的是，利用概要數(shù)據(jù)進(jìn)行查詢和分析的優(yōu)點(diǎn)是其響應(yīng)很快，缺點(diǎn)是僅僅能獲得一些近似的查詢和數(shù)據(jù)分析結(jié)果，大量的數(shù)據(jù)分析和決策支持功能仍然需要數(shù)據(jù)倉(cāng)庫(kù)和數(shù)據(jù)挖掘系統(tǒng)完成。所以，概要數(shù)據(jù)結(jié)構(gòu)只能作為聯(lián)機(jī)操作數(shù)據(jù)庫(kù)和數(shù)據(jù)倉(cāng)庫(kù)系統(tǒng)的有益補(bǔ)充和輔助工具，而不能替代原有的數(shù)據(jù)倉(cāng)庫(kù)和數(shù)據(jù)挖掘系統(tǒng)。

四、結(jié)束語(yǔ)

本文介紹了數(shù)據(jù)流概要數(shù)據(jù)結(jié)構(gòu)構(gòu)建技術(shù)及其發(fā)展現(xiàn)狀，給出了一個(gè)將數(shù)據(jù)流概要數(shù)據(jù)結(jié)構(gòu)構(gòu)建技術(shù)應(yīng)用于大型零售商業(yè)管理信息系統(tǒng)的框架結(jié)構(gòu)，希望能夠?yàn)榇笮土闶凵虡I(yè)管理信息系統(tǒng)的分析設(shè)計(jì)提供有益的參考。

參考文獻(xiàn)：

[1]Babcock B， Datar M， Motwani R. Sampling from a moving window over streaming data[C]. Proceedings of the 13th Annual ACM-SIAM Symp. on Discrete Algorithms. San Francisco， ACM/SIAM， 2002: 633-634

[2]P. S. Efraimidis， P. G. Spirakis. Weighted random sampling with a reservoir[J]. Information Processing Letters， Vol. 97， Issue 5， March 2006: 181～185

[3]S. Guha， N. Koudas and K. Shim. Approximating a Data Stream for Querying and Estimation: Algorithm Performance Evaluation[C]. Proceeding of ICDE’02. 2002

[4]S. Guha， N. Koudas， K. Shim. Data Streams and Histograms[C]. Proceedings of Symposiumon the Theory of Computing (STOC)， 2001

[5]Datar M， Gionis A， Indyk P， Motwani R. Maintaining stream statistics over sliding windows[C]. Proceedings of the 13th Annual ACM-SIAM Symp. on Discrete Algorithms. 635～644. San Francisco， ACM/SIAM， 2002

[6]B. Babcock， S. Babu， M. Datar， R. Motwani， and J. Widom. Models and issues in data stream systems[C]. In Proceedings of 21st ACM SIGACT-SIGMODSIGART Symp. on Principles of Database Systems， Madison， Wisconsin， May 2002: 1～16

[7]劉夕炎王田等:商業(yè)MIS系統(tǒng)研究（一）[J]. 重慶商學(xué)院學(xué)報(bào). 2000(1): 51～54

[8]李旭東:零售業(yè)信息系統(tǒng)的設(shè)計(jì)(J). 計(jì)算機(jī)與網(wǎng)絡(luò). 2003(1): 56～58

注:本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文