流式數(shù)據(jù)挖掘的發(fā)展與統(tǒng)計學(xué)研究

1、流式數(shù)據(jù)挖掘的發(fā)展與統(tǒng)計學(xué)研究 朱建平 來升強(qiáng)廈門大學(xué)經(jīng)濟(jì)學(xué)院計劃統(tǒng)計系7/18/2022The Development and The Statistical Research for Streaming Data MiningZhu Jian-ping Lai Sheng-qiangDepartment of Planning and Statistics of the School of Economics of Xiamen University 7/18/2022報告目的 本報告對近年來在國內(nèi)外學(xué)界涌現(xiàn)出的流式數(shù)據(jù)挖掘的研究成果進(jìn)行較為全面的介紹，分析了

2、流式數(shù)據(jù)挖掘的研究現(xiàn)狀。提出了統(tǒng)計學(xué)在流式數(shù)據(jù)挖掘研究中的發(fā)展趨勢，以便更好讓大 家深入的認(rèn)識統(tǒng)計學(xué)和數(shù)據(jù)挖掘的結(jié)合， 拓展統(tǒng)計學(xué)方法的研究思路。7/18/2022報告的基本內(nèi)容一、流式數(shù)據(jù)挖掘的研究現(xiàn)狀 二、流式數(shù)據(jù)挖掘中統(tǒng)計學(xué)的研究趨勢 三、統(tǒng)計學(xué)研究的體會7/18/2022一、流式數(shù)據(jù)挖掘的研究現(xiàn)狀 經(jīng)過近二十年的發(fā)展，數(shù)據(jù)挖掘方法在眾多領(lǐng)域被廣泛研究和應(yīng)用。在學(xué)術(shù)界，美國計算機(jī)學(xué)會(ACM)有多個主題為數(shù)據(jù)挖掘的學(xué)術(shù)會議，例如SIGMOD（Conference on Management of Data）、DMKD（Data Mining and Knowledge Discovery

3、）和VLDB（VeryLargeDataBases）等。以數(shù)據(jù)挖掘為主題的國際期刊也有不少，其中影響較大的有超大數(shù)據(jù)庫期刊(VLDB Journal)、數(shù)據(jù)挖掘與知識發(fā)現(xiàn)（Data Mining and Knowledge Discovery)和美國計算機(jī)學(xué)會數(shù)據(jù)庫系統(tǒng)學(xué)報（ACM Transactions On Database Systems），并且一些系統(tǒng)科學(xué)、統(tǒng)計學(xué)、人工智能、臨床醫(yī)學(xué)等領(lǐng)域的重要刊物上也屢見數(shù)據(jù)挖掘理論及方法的應(yīng)用研究。7/18/2022 近年來，國內(nèi)外學(xué)界涌現(xiàn)了一大批針對流式數(shù)據(jù)挖掘的研究成果。所謂流式數(shù)據(jù)，指按照時間順序無限增加的數(shù)據(jù)觀測值向量所組成的數(shù)據(jù)序列，也

4、可以將流式數(shù)據(jù)看成歷史數(shù)據(jù)和不斷增加的更新數(shù)據(jù)的并集。從定義易知，流式數(shù)據(jù)挖掘是數(shù)據(jù)挖掘的更一般形式。 流式數(shù)據(jù)主要出現(xiàn)在大量實時監(jiān)測和控制系統(tǒng)中，例如航天水利設(shè)備傳感器組監(jiān)控、氣溫水流等環(huán)境氣象監(jiān)測、以及金融市場實時交易監(jiān)控等實時系統(tǒng)都會產(chǎn)生規(guī)模巨大的歷史數(shù)據(jù)，并能在數(shù)分鐘內(nèi)就生成一個相當(dāng)規(guī)模的更新數(shù)據(jù)集。 7/18/2022 數(shù)據(jù)對象的復(fù)雜化和動態(tài)化向研究者提出了新的挑戰(zhàn)。從總體上，國外在該領(lǐng)域的研究較為廣泛，我們從數(shù)據(jù)挖掘的技術(shù)和挖掘的知識看，在流式數(shù)據(jù)挖掘的研究方面取得了一些成效。 1. 流式數(shù)據(jù)聚類。 2. 流式數(shù)據(jù)分類。 3. 時變模式識別。 4. 流式數(shù)據(jù)壓縮。 5. 規(guī)則發(fā)現(xiàn)。

5、7/18/2022 1. 流式數(shù)據(jù)聚類 長期以來，數(shù)據(jù)挖掘的聚類分析都處在靜態(tài)數(shù)據(jù)的層次上。這一方面是維數(shù)災(zāi)問題(coarse of dimensionality)沒有得到很好的解決，常用的特征變換(feature transformation)和子空間選擇(subspace selection)方法實際上都是有損失的降維技術(shù)，許多研究都試圖提出新的降維方法，以盡可能地減少信息損失。另一方面是數(shù)據(jù)規(guī)模問題。由于計算機(jī)性能限制，大量的研究都在改進(jìn)算法和降低復(fù)雜度。7/18/2022 然而，流式數(shù)據(jù)是歷史數(shù)據(jù)與不斷增加的更新數(shù)據(jù)的并集，因此除了以上提到的兩個問題，流式數(shù)據(jù)聚類分析還應(yīng)考慮：(1)如

6、何反映流式數(shù)據(jù)在時間上的動態(tài)特征。現(xiàn)在基本是采用對時間窗內(nèi)不同時刻觀測值加權(quán)的辦法(有些文獻(xiàn)稱之為“傾斜時間窗(tilted time window)”)，例如Aggarwal C., et al.(2005)采用一個關(guān)于數(shù)據(jù)觀測值生存時間的指數(shù)衰減函數(shù)對歷史數(shù)據(jù)進(jìn)行加權(quán)；(2)如何處理更新數(shù)據(jù)對已有聚類的影響。顯然只有在(1)的基礎(chǔ)上，這個問題才有可能解決，目前這方面研究幾乎空白。7/18/20222. 流式數(shù)據(jù)分類 在流式數(shù)據(jù)條件下，分類過程不僅僅是建立一個判別模型就完成了，更重要的是保證分類模型對于更新數(shù)據(jù)的適應(yīng)性和分類穩(wěn)定性。例如Hulten G., et al.(2001)提出的動態(tài)

7、決策樹CVFDT，可以根據(jù)更新數(shù)據(jù)動態(tài)地建立新枝或刪除舊枝，有效的結(jié)合了歷史信息和更新信息。Hastie T., et al.(2001)的一種分類回歸樹(Categorical And Regression Tree)的改進(jìn)形式還可以完成對非數(shù)值型流式數(shù)據(jù)的分類任務(wù)。最近Lee S., et al.(2005)將廣義估計方程(GEE)應(yīng)用到?jīng)Q策樹分類中，較好解決了混合型流式數(shù)據(jù)的分類問題。Rousseeuw P., et al.(2006)改進(jìn)了穩(wěn)健統(tǒng)計分析中的最小截斷二乘法的估計方法(Least Trimmed Squares)，使LTS回歸能勝任大型流式數(shù)據(jù)的分類回歸任務(wù)。7/18/20

8、223. 時變模式識別 這一問題源于如何在包含空間位置信息的流式數(shù)據(jù)中進(jìn)行多目標(biāo)路徑相似性識別。從早期時空數(shù)據(jù)庫中的規(guī)則挖掘到現(xiàn)在的動態(tài)時間翹曲(Dynamic Time Warping)研究，時變模式識別已經(jīng)從尋找單一的、靜態(tài)的時空規(guī)則發(fā)展到可以分別挖掘出具有時間相似性(similarity in time)、路徑相似性(similarity in shape)、以及結(jié)構(gòu)相似性(structural similarity)等三種不同相似類型的時變模式。Cao H., et al.(2006)將回歸分析中的均方誤差和(Mean Square of Root Error)概念應(yīng)用到函數(shù)型數(shù)據(jù)中，

9、其實例分析的結(jié)果也很有說服力。7/18/20224. 流式數(shù)據(jù)壓縮 流式數(shù)據(jù)壓縮是指在給定的誤差設(shè)定下，把歷史數(shù)據(jù)壓縮為一個相對較小的概要數(shù)據(jù)集(synopsis data structure)，同時保證概要數(shù)據(jù)集對歷史數(shù)據(jù)的代表性。流式數(shù)據(jù)壓縮方法和統(tǒng)計模型結(jié)合較為緊密，例如線性擬合，多項式擬合，獨立成分分析等統(tǒng)計和數(shù)學(xué)模型。Bagnall A., et al.(2004)還證明如果流式數(shù)據(jù)是寬平穩(wěn)的ARMA過程，則其0/1離散化的序列也將漸進(jìn)地服從寬平穩(wěn)的ARMA過程，并利用小波變換對離散化的0/1序列進(jìn)行壓縮。7/18/2022 相對于其他挖掘方法，規(guī)則發(fā)現(xiàn)更適合用于非標(biāo)準(zhǔn)流式數(shù)據(jù)的探索

10、性分析。例如分析諸如DNA序列等字符型流式數(shù)據(jù)時，可以采用小波變換；而在分析點擊流數(shù)據(jù)時，可將點擊流數(shù)據(jù)映射為以所有互異鏈接為基本項的事務(wù)數(shù)據(jù)集，進(jìn)而采用時態(tài)規(guī)則進(jìn)行網(wǎng)頁內(nèi)容優(yōu)化和個性化網(wǎng)頁訪問服務(wù)。由于規(guī)則的具體形式是非常依賴數(shù)據(jù)的，在更新數(shù)據(jù)不斷獲取的情況下，規(guī)則的有效性和穩(wěn)定性問題也是一個值得深入研究的方面。方法之一是利用抽樣誤差公式進(jìn)行抽樣并根據(jù)抽樣頻數(shù)進(jìn)行頻數(shù)估計，另外一種方法稱為top-k有損頻數(shù)估計。5. 規(guī)則發(fā)現(xiàn)7/18/2022 在應(yīng)用方面，由于意識到數(shù)據(jù)挖掘的巨大商機(jī)，各大數(shù)據(jù)庫系統(tǒng)公司也不斷更新和完善自己的數(shù)據(jù)挖掘軟件，其中應(yīng)用最廣泛的軟件有SAS公司Enterprise

11、 Miner，IBM公司的Intelligent Miner，和SPSS公司的Clementine。最近Microsoft公司新推出的中小型數(shù)據(jù)庫系統(tǒng)SQL2005也極大地改進(jìn)和增強(qiáng)了數(shù)據(jù)挖掘功能。這些軟件中基本都包括：決策樹、聚類分析、規(guī)則挖掘、自組織圖、神經(jīng)網(wǎng)絡(luò)、特征提取和可視化等功能。另外，有些軟件還包括：遺傳算法、EM算法、Monte Carlo模擬、記憶推理和文檔挖掘等高級統(tǒng)計計算方法。7/18/2022 與國外相比，國內(nèi)學(xué)術(shù)界對流式數(shù)據(jù)挖掘的研究剛剛開始，除了一些回顧性的研究外，其研究方向較為單一，且以流式數(shù)據(jù)下頻繁模式挖掘的算法改進(jìn)為主，如利用Chernoff不等式改進(jìn)流式數(shù)據(jù)的

12、頻繁模式挖掘算法；對FP-Growth算法的改進(jìn)，使之適應(yīng)流式數(shù)據(jù)的頻繁模式挖掘任務(wù)等。在應(yīng)用方面，國內(nèi)有關(guān)研究機(jī)構(gòu)也開發(fā)了不少應(yīng)用級的數(shù)據(jù)挖掘軟件。其中，Markway軟件是功能較全面的軟件之一，該軟件已經(jīng)被國內(nèi)高校和研究機(jī)構(gòu)大量使用，并取得一致好評。7/18/2022二、流式數(shù)據(jù)挖掘中統(tǒng)計學(xué)的研究趨勢 流式數(shù)據(jù)挖掘雖然是數(shù)據(jù)挖掘的高級形式，但仍然依托于數(shù)據(jù)庫、統(tǒng)計學(xué)、人工智能、計算機(jī)科學(xué)、以及信息科學(xué)等眾多交叉學(xué)科。其中，各種統(tǒng)計方法也被廣泛使用，例如決策樹分類、近鄰聚類、核估計、Bayes分析、廣義估計、抽樣理論、時序分析等等。 但是，在流式數(shù)據(jù)挖掘應(yīng)用過程中，統(tǒng)計學(xué)也遇到了不少難題，例

13、如高維流式數(shù)據(jù)的降維問題、流式數(shù)據(jù)的壓縮問題和抽樣問題、函數(shù)數(shù)據(jù)和高頻數(shù)據(jù)的統(tǒng)計分析問題、數(shù)據(jù)丟失和異常發(fā)現(xiàn)問題、流式知識的穩(wěn)定性與可靠性問題等。這些跨學(xué)科的研究問題既是挑戰(zhàn)，更是推動統(tǒng)計科學(xué)發(fā)展的大好機(jī)遇。我們應(yīng)該明確統(tǒng)計學(xué)在流式數(shù)據(jù)挖掘研究中的趨勢，以便更好地促進(jìn)統(tǒng)計學(xué)和數(shù)據(jù)挖掘的結(jié)合，解決在實際問題及理論研究中遇到難題。7/18/2022 我們從統(tǒng)計學(xué)理論和方法的角度來審視流式數(shù)據(jù)挖掘的內(nèi)容和方法，一方面有利于明確統(tǒng)計方法的應(yīng)用現(xiàn)狀和所面臨的困難；另一方面可以引起統(tǒng)計學(xué)界對流式數(shù)據(jù)挖掘的廣泛關(guān)注，也有利于統(tǒng)計學(xué)方法研究的拓展和深入。 1. 高維數(shù)據(jù)降維 2. 流式數(shù)據(jù)壓縮 3. 流式數(shù)據(jù)

14、的統(tǒng)計描述 4. 重復(fù)觀測數(shù)據(jù)分析 5. 可視化分析7/18/2022 現(xiàn)代統(tǒng)計理論與方法研究的重要領(lǐng)域之一是高維數(shù)據(jù)的降維問題，它也是流式數(shù)據(jù)挖掘研究的主要內(nèi)容：(1)在K-NN聚類的基礎(chǔ)上，設(shè)計出合適的權(quán)重函數(shù)，使其既能滿足降維的需要，又能充分反映時間變化的影響；(2)借鑒投影尋蹤方法(pursue projection)的思想，在流式數(shù)據(jù)的高維空間中找出最優(yōu)線性基向量并將其作為降維子空間，同時把相應(yīng)的線性變換矩陣作為原維度的權(quán)重矩陣。進(jìn)一步地，還可以研究如何將這一思想推廣到非線性情形，使之適合更一般的數(shù)據(jù)降維任務(wù)；(3)選擇適當(dāng)?shù)幕瘮?shù)對流式數(shù)據(jù)進(jìn)行擬合。在這些方法研究中，重點是如何設(shè)計

15、具有時變特征的權(quán)重因子。1. 高維數(shù)據(jù)降維7/18/20222. 流式數(shù)據(jù)壓縮 結(jié)合統(tǒng)計理論中時序分析的基本思想，對流式數(shù)據(jù)中包含的不同性質(zhì)、不同程度、不同周期的規(guī)律性特征進(jìn)行分離，用適當(dāng)?shù)膹V義可加模型進(jìn)行描述，并采用時變參數(shù)反映流式數(shù)據(jù)的動態(tài)特征。另外，還可以利用粗糙集等知識推理方法進(jìn)行約簡，將大量不必要的細(xì)節(jié)信息泛化為若干代表性知識，實現(xiàn)知識泛化。7/18/20223. 流式數(shù)據(jù)的統(tǒng)計描述 借助現(xiàn)在統(tǒng)計理論函數(shù)型數(shù)據(jù)的觀點，對流式數(shù)據(jù)進(jìn)行函數(shù)數(shù)據(jù)判別分析、函數(shù)數(shù)據(jù)主成分分析、函數(shù)數(shù)據(jù)的聚類分析、以及函數(shù)數(shù)據(jù)回歸分析等。此外，還可以采用高頻數(shù)據(jù)的觀點，對流式數(shù)據(jù)進(jìn)行類似的分析。7/18/20

16、22 傳統(tǒng)多元統(tǒng)計分析都假設(shè)觀測值都是一次獲取的，很少考慮到重復(fù)觀測記錄的情形。在傳統(tǒng)多元統(tǒng)計分析的基礎(chǔ)上，針對流式數(shù)據(jù)可以對判別分析、主成分分析、相應(yīng)分析等經(jīng)典方法加以推廣，使之適用于諸如流式數(shù)據(jù)等重復(fù)觀測數(shù)據(jù)的情形。4. 重復(fù)觀測數(shù)據(jù)分析7/18/2022 可視化是反映統(tǒng)計分析結(jié)果的重要環(huán)節(jié)，在流式數(shù)據(jù)研究的過程中，對于復(fù)雜現(xiàn)象的統(tǒng)計分析結(jié)果，我們還可以通過計算機(jī)軟件實 現(xiàn)流式數(shù)據(jù)挖掘結(jié)果的可視化，并 實現(xiàn)人機(jī)交互式的數(shù)據(jù)挖掘過程， 使得分析結(jié)果更能體現(xiàn)使用價值。5. 可視化分析7/18/2022 流式數(shù)據(jù)挖掘技術(shù)和方法研究的主要目的在于應(yīng)用，其研究的成果可以對移動通信通話記錄進(jìn)行客戶流失

17、分析；對股市分鐘交易數(shù)據(jù)的投機(jī)交易行為進(jìn)行探測；通過網(wǎng)站的訪問日志數(shù)據(jù)分析來優(yōu)化網(wǎng)頁內(nèi)容，提高網(wǎng)站平均訪問率和瀏覽時間等等。 通過理論分析和實際應(yīng)用研究，我們體會到，統(tǒng)計學(xué)應(yīng)該隨時地關(guān)注數(shù)據(jù)分析。哪里有數(shù)據(jù)，哪里就應(yīng)該有統(tǒng)計分析。統(tǒng)計學(xué)方法一直就是數(shù)據(jù)挖掘研究的主要方法，在流式數(shù)據(jù)挖掘領(lǐng)域中必將發(fā)揮越來越重要的作用。統(tǒng)計學(xué)和數(shù)據(jù)挖掘的關(guān)系是相輔相成的，在流式數(shù)據(jù)挖掘中適當(dāng)運用統(tǒng)計方法會顯著提高挖掘的效率和效果。同時，流式數(shù)據(jù)挖掘中所出現(xiàn)的問題也將促進(jìn)統(tǒng)計科學(xué)的進(jìn)一步發(fā)展。 三、統(tǒng)計學(xué)研究的體會7/18/2022參考文獻(xiàn)1 Aggarwal C., Han J., Wang C. and Wu

18、P., On high dimensional projected clustering of data streamsJ, Data Mining and Knowledge Discovery, 10, 2005, p251-273.2 Hulten G., Spencer P. and Domingos P., Mining time-changing data streamsJ/OL, :/, 2001.3 Hastie T., Tibshirani R. and Friedman J., The elements of statistical learni

19、ng: data mining, inference, and predictionM, Springer-Verlag, 2001, p55-80.4 Lee S., Kang H., Han S. and Kim K., Using generalized estimating equations to learn decision trees with multivariate responsesJ, Data Mining and Knowledge Discovery, 11, 2005, p273-393.5 Rousseeuw P. and Driessen K., Comput

20、ing LTS regression for large data setsJ, Data Mining and Knowledge Discovery, 12, 2006, p29-45.6 Tan P., Steinbach M. and Kumar V., Finding spatio-temporal patterns in earth science dataA, KDD workshop on temporal data mining, 2001, p1-12.7 Bagnall A., Ratanamahatana C., Keogh E., et al., A bit leve

21、l representation for time series data mining with shape based similarityJ, Data Mining and Knowledge Discovery, 13, 2006, p11-40.8 Cao H., Wolfson O. and Trajcevski G., Spatio-temporal data reduction with deterministic error boundsJ, The VLDB Journal, 15 (3), 2006, p211-228.9 Cai Y. and Ng R., Indexing spatio-temporal trajectories with chebyshev polynomialsA, In proc. of ACM SIGMOD, 2004, p599-610.10 Basak J., Sudarshan A., Trivedi D. and Santhanam M., Weather data mining using independent component analysisJ