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

1、2022-3-181流式數(shù)據(jù)挖掘的發(fā)展流式數(shù)據(jù)挖掘的發(fā)展與統(tǒng)計(jì)學(xué)研究與統(tǒng)計(jì)學(xué)研究 朱建平朱建平 來升強(qiáng)來升強(qiáng)2022-3-182The 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 2022-3-183報(bào)告目的 本報(bào)告對(duì)近年來在國(guó)內(nèi)外學(xué)界涌現(xiàn)出的流式數(shù)據(jù)挖掘的研究成果進(jìn)行較為全面的介

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

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

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

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

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

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

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

9、Error)概念應(yīng)用到函數(shù)型數(shù)據(jù)中，其實(shí)例分析的結(jié)果也很有說服力。2022-3-18124. 流式數(shù)據(jù)壓縮 流式數(shù)據(jù)壓縮是指在給定的誤差設(shè)定下，把歷史數(shù)據(jù)壓縮為一個(gè)相對(duì)較小的概要數(shù)據(jù)集(synopsis data structure)，同時(shí)保證概要數(shù)據(jù)集對(duì)歷史數(shù)據(jù)的代表性。流式數(shù)據(jù)壓縮方法和統(tǒng)計(jì)模型結(jié)合較為緊密，例如線性擬合，多項(xiàng)式擬合，獨(dú)立成分分析等統(tǒng)計(jì)和數(shù)學(xué)模型。Bagnall A., et al.(2004)還證明如果流式數(shù)據(jù)是寬平穩(wěn)的ARMA過程，則其0/1離散化的序列也將漸進(jìn)地服從寬平穩(wěn)的ARMA過程，并利用小波變換對(duì)離散化的0/1序列進(jìn)行壓縮。2022-3-1813 相對(duì)于其他挖掘

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

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

12、改進(jìn)為主，如利用Chernoff不等式改進(jìn)流式數(shù)據(jù)的頻繁模式挖掘算法；對(duì)FP-Growth算法的改進(jìn)，使之適應(yīng)流式數(shù)據(jù)的頻繁模式挖掘任務(wù)等。在應(yīng)用方面，國(guó)內(nèi)有關(guān)研究機(jī)構(gòu)也開發(fā)了不少應(yīng)用級(jí)的數(shù)據(jù)挖掘軟件。其中，Markway軟件是功能較全面的軟件之一，該軟件已經(jīng)被國(guó)內(nèi)高校和研究機(jī)構(gòu)大量使用，并取得一致好評(píng)。2022-3-1816二、流式數(shù)據(jù)挖掘中統(tǒng)計(jì)學(xué)的研究趨勢(shì) 流式數(shù)據(jù)挖掘雖然是數(shù)據(jù)挖掘的高級(jí)形式，但仍然依托于數(shù)據(jù)庫(kù)、流式數(shù)據(jù)挖掘雖然是數(shù)據(jù)挖掘的高級(jí)形式，但仍然依托于數(shù)據(jù)庫(kù)、統(tǒng)計(jì)學(xué)、人工智能、計(jì)算機(jī)科學(xué)、以及信息科學(xué)等眾多交叉學(xué)科。統(tǒng)計(jì)學(xué)、人工智能、計(jì)算機(jī)科學(xué)、以及信息科學(xué)等眾多交叉學(xué)科。其其

13、中，各種統(tǒng)計(jì)方法也被廣泛使用，中，各種統(tǒng)計(jì)方法也被廣泛使用，例如決策樹分類、近鄰聚類、核估例如決策樹分類、近鄰聚類、核估計(jì)、計(jì)、BayesBayes分析、廣義估計(jì)、抽樣理論、時(shí)序分析等等分析、廣義估計(jì)、抽樣理論、時(shí)序分析等等。 但是，在流式數(shù)據(jù)挖掘應(yīng)用過程中，統(tǒng)計(jì)學(xué)也遇到了不少難題，但是，在流式數(shù)據(jù)挖掘應(yīng)用過程中，統(tǒng)計(jì)學(xué)也遇到了不少難題，例例如高維流式數(shù)據(jù)的降維問題、流式數(shù)據(jù)的壓縮問題和抽樣問題、函數(shù)如高維流式數(shù)據(jù)的降維問題、流式數(shù)據(jù)的壓縮問題和抽樣問題、函數(shù)數(shù)據(jù)和高頻數(shù)據(jù)的統(tǒng)計(jì)分析問題、數(shù)據(jù)丟失和異常發(fā)現(xiàn)問題、流式知數(shù)據(jù)和高頻數(shù)據(jù)的統(tǒng)計(jì)分析問題、數(shù)據(jù)丟失和異常發(fā)現(xiàn)問題、流式知識(shí)的穩(wěn)定性與可靠

14、性問題等。識(shí)的穩(wěn)定性與可靠性問題等。這些跨學(xué)科的研究問題既是挑戰(zhàn)，更是這些跨學(xué)科的研究問題既是挑戰(zhàn)，更是推動(dòng)統(tǒng)計(jì)科學(xué)發(fā)展的大好機(jī)遇。我們應(yīng)該明確統(tǒng)計(jì)學(xué)在流式數(shù)據(jù)挖掘推動(dòng)統(tǒng)計(jì)科學(xué)發(fā)展的大好機(jī)遇。我們應(yīng)該明確統(tǒng)計(jì)學(xué)在流式數(shù)據(jù)挖掘研究中的趨勢(shì)，以便更好地促進(jìn)統(tǒng)計(jì)學(xué)和數(shù)據(jù)挖掘的結(jié)合，解決在實(shí)研究中的趨勢(shì)，以便更好地促進(jìn)統(tǒng)計(jì)學(xué)和數(shù)據(jù)挖掘的結(jié)合，解決在實(shí)際問題及理論研究中遇到難題。際問題及理論研究中遇到難題。2022-3-1817 我們從統(tǒng)計(jì)學(xué)理論和方法的角度來審視流式數(shù)據(jù)挖掘的內(nèi)容和方法，一方面有利于明確統(tǒng)計(jì)方法的應(yīng)用現(xiàn)狀和所面臨的困難；另一方面可以引起統(tǒng)計(jì)學(xué)界對(duì)流式數(shù)據(jù)挖掘的廣泛關(guān)注，也有利于統(tǒng)計(jì)學(xué)方

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

16、任務(wù)；(3)選擇適當(dāng)?shù)幕瘮?shù)對(duì)流式數(shù)據(jù)進(jìn)行擬合。在這些方法研究中，重點(diǎn)是如何設(shè)計(jì)具有時(shí)變特征的權(quán)重因子。1. 高維數(shù)據(jù)降維2022-3-18192. 2. 流式數(shù)據(jù)壓縮流式數(shù)據(jù)壓縮 結(jié)合統(tǒng)計(jì)理論中時(shí)序分析的基本思想，結(jié)合統(tǒng)計(jì)理論中時(shí)序分析的基本思想，對(duì)流式數(shù)據(jù)對(duì)流式數(shù)據(jù)中包含的不同性質(zhì)、不同程度、不同周期的規(guī)律性特征進(jìn)中包含的不同性質(zhì)、不同程度、不同周期的規(guī)律性特征進(jìn)行分離，用適當(dāng)?shù)膹V義可加模型進(jìn)行描述，并采用時(shí)變參行分離，用適當(dāng)?shù)膹V義可加模型進(jìn)行描述，并采用時(shí)變參數(shù)反映流式數(shù)據(jù)的動(dòng)態(tài)特征。另外，還可以數(shù)反映流式數(shù)據(jù)的動(dòng)態(tài)特征。另外，還可以利用粗糙集利用粗糙集等等知識(shí)推理方法進(jìn)行約簡(jiǎn)，將大量不

17、必要的細(xì)節(jié)信息泛化為知識(shí)推理方法進(jìn)行約簡(jiǎn)，將大量不必要的細(xì)節(jié)信息泛化為若干代表性知識(shí)，實(shí)現(xiàn)知識(shí)泛化。若干代表性知識(shí)，實(shí)現(xiàn)知識(shí)泛化。2022-3-18203. 流式數(shù)據(jù)的統(tǒng)計(jì)描述 借助現(xiàn)在統(tǒng)計(jì)理論函數(shù)型數(shù)據(jù)的觀點(diǎn)，對(duì)流式數(shù)據(jù)進(jìn)行函數(shù)數(shù)據(jù)判別分析、函數(shù)數(shù)據(jù)主成分分析、函數(shù)數(shù)據(jù)的聚類分析、以及函數(shù)數(shù)據(jù)回歸分析等。此外，還可以采用高頻數(shù)據(jù)的觀點(diǎn)，對(duì)流式數(shù)據(jù)進(jìn)行類似的分析。2022-3-1821 傳統(tǒng)多元統(tǒng)計(jì)分析都假設(shè)觀測(cè)值都是一次獲取的，很少考慮到重復(fù)觀測(cè)記錄的情形。在傳統(tǒng)多元統(tǒng)計(jì)分析的基礎(chǔ)上，針對(duì)流式數(shù)據(jù)可以對(duì)判別分析、主成分分析、相應(yīng)分析等經(jīng)典方法加以推廣，使之適用于諸如流式數(shù)據(jù)等重復(fù)觀測(cè)數(shù)據(jù)的情

18、形。4. 重復(fù)觀測(cè)數(shù)據(jù)分析2022-3-1822 可視化是反映統(tǒng)計(jì)分析結(jié)果的重要環(huán)節(jié)，在流式數(shù)據(jù)研究的過程中，對(duì)于復(fù)雜現(xiàn)象的統(tǒng)計(jì)分析結(jié)果，我們還可以通過計(jì)算機(jī)軟件實(shí) 現(xiàn)流式數(shù)據(jù)挖掘結(jié)果的可視化，并 實(shí)現(xiàn)人機(jī)交互式的數(shù)據(jù)挖掘過程， 使得分析結(jié)果更能體現(xiàn)使用價(jià)值。5. 可視化分析2022-3-1823 流式數(shù)據(jù)挖掘技術(shù)和方法研究的主要目的在于應(yīng)用，其研究的成果可以對(duì)移動(dòng)通信通話記錄進(jìn)行客戶流失分析；對(duì)股市分鐘交易數(shù)據(jù)的投機(jī)交易行為進(jìn)行探測(cè)；通過網(wǎng)站的訪問日志數(shù)據(jù)分析來優(yōu)化網(wǎng)頁(yè)內(nèi)容，提高網(wǎng)站平均訪問率和瀏覽時(shí)間等等。 通過理論分析和實(shí)際應(yīng)用研究，我們體會(huì)到，統(tǒng)計(jì)學(xué)應(yīng)該隨時(shí)地關(guān)注數(shù)據(jù)分析。哪里有數(shù)據(jù)，

19、哪里就應(yīng)該有統(tǒng)計(jì)分析。統(tǒng)計(jì)學(xué)方法一直就是數(shù)據(jù)挖掘研究的主要方法，在流式數(shù)據(jù)挖掘領(lǐng)域中必將發(fā)揮越來越重要的作用。統(tǒng)計(jì)學(xué)和數(shù)據(jù)挖掘的關(guān)系是相輔相成的，在流式數(shù)據(jù)挖掘中適當(dāng)運(yùn)用統(tǒng)計(jì)方法會(huì)顯著提高挖掘的效率和效果。同時(shí)，流式數(shù)據(jù)挖掘中所出現(xiàn)的問題也將促進(jìn)統(tǒng)計(jì)科學(xué)的進(jìn)一步發(fā)展。 三、統(tǒng)計(jì)學(xué)研究的體會(huì)2022-3-1824參考文獻(xiàn)n1 Aggarwal C., Han J., Wang C. and Wu P., On high dimensional projected clustering of data streamsJ, Data Mining and Knowledge Discovery, 1

20、0, 2005, p251-273.n2 Hulten G., Spencer P. and Domingos P., Mining time-changing data streamsJ/OL, , 2001.n3 Hastie T., Tibshirani R. and Friedman J., The elements of statistical learning: data mining, inference, and predictionM, Springer-Verlag, 2001, p55-80.n4 Lee S., Kang H., Han S. and Kim K., U

21、sing generalized estimating equations to learn decision trees with multivariate responsesJ, Data Mining and Knowledge Discovery, 11, 2005, p273-393.n5 Rousseeuw P. and Driessen K., Computing LTS regression for large data setsJ, Data Mining and Knowledge Discovery, 12, 2006, p29-45.n6 Tan P., Steinba

22、ch M. and Kumar V., Finding spatio-temporal patterns in earth science dataA, KDD workshop on temporal data mining, 2001, p1-12.n7 Bagnall A., Ratanamahatana C., Keogh E., et al., A bit level representation for time series data mining with shape based similarityJ, Data Mining and Knowledge Discovery,

23、 13, 2006, p11-40.n8 Cao H., Wolfson O. and Trajcevski G., Spatio-temporal data reduction with deterministic error boundsJ, The VLDB Journal, 15 (3), 2006, p211-228.n9 Cai Y. and Ng R., Indexing spatio-temporal trajectories with chebyshev polynomialsA, In proc. of ACM SIGMOD, 2004, p599-610.n10 Basak J., Sudarshan A., Trivedi D. and Santhan