數(shù)據(jù)流頻繁項挖掘與聚類分析的研究.pdf

1、隨著科學(xué)技術(shù)的高速發(fā)展和信息技術(shù)的廣泛應(yīng)用引發(fā)了一類新型應(yīng)用,包括計算機網(wǎng)絡(luò)流量控制、網(wǎng)絡(luò)安全監(jiān)控、金融應(yīng)用、環(huán)境監(jiān)測和日志分析等。在這些新型的應(yīng)用中,數(shù)據(jù)以流的形式產(chǎn)生,它實時、持續(xù)、有序地到達。這種由一系列連續(xù)且有序的數(shù)據(jù)組成的序列被稱為數(shù)據(jù)流。與傳統(tǒng)數(shù)據(jù)庫不同,數(shù)據(jù)流具有如下特點:無限性;不可再現(xiàn)性;數(shù)據(jù)到達速率極快;數(shù)據(jù)的到達次序不受應(yīng)用約束。分析和挖掘數(shù)據(jù)流已成為熱點研究問題。
　　 數(shù)據(jù)流挖掘即在流式數(shù)據(jù)上提取隱含在

2、其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程。數(shù)據(jù)流挖掘主要是通過挖掘頻繁項(集)、分類分析、聚類分析、異常分析等知識發(fā)現(xiàn)活動,以尋找數(shù)據(jù)流中的關(guān)聯(lián)規(guī)則、分類規(guī)則、聚類模式、異常模式等類型的知識。如挖掘數(shù)據(jù)流中的頻繁項可應(yīng)用于基于流量的網(wǎng)絡(luò)計費、網(wǎng)絡(luò)交通阻塞控制、網(wǎng)絡(luò)安全監(jiān)控等。對數(shù)據(jù)流進行聚類分析可應(yīng)用于監(jiān)測網(wǎng)絡(luò)入侵、在線新聞組過濾、話題識別與跟蹤、對交通擁塞與地理環(huán)境等進行實時監(jiān)控、對大型公司中不同顧客群進行劃分、檢測

3、金融欺詐等。
　　 由于存儲空間的有限性與數(shù)據(jù)流的無限性,使得薦儲數(shù)據(jù)流中的全部數(shù)據(jù)以提供精確的挖掘結(jié)果是不實際的。因此,在數(shù)據(jù)流處理模型中,數(shù)據(jù)流處理算法只存儲數(shù)據(jù)流的概要信息,并隨著流中數(shù)據(jù)不斷到來,不斷更新流概要,同時根據(jù)用戶的查詢要求,利用所維護的數(shù)據(jù)流概要信息,為用戶提供近似的查詢結(jié)果。
　　 由于頻繁項挖掘與聚類分析在網(wǎng)絡(luò)數(shù)據(jù)流分析中有著重要的應(yīng)用,我們主要進行數(shù)據(jù)流環(huán)境下的頻繁項挖掘與聚類分析方法的研究。在

4、網(wǎng)絡(luò)數(shù)據(jù)流及大量的其它應(yīng)用領(lǐng)域中,數(shù)據(jù)類型多種多樣,它們不僅包括數(shù)值型數(shù)據(jù),而且包括非數(shù)值型數(shù)據(jù),且這些數(shù)據(jù)經(jīng)常會有幾十甚至幾百個屬性,使得研究混合屬性數(shù)據(jù)流的聚類及高維屬性數(shù)據(jù)流聚類均具有重要的理論價值與實際意義。以生物系統(tǒng)的機理為基礎(chǔ)設(shè)計算法和系統(tǒng)是近代研究的熱點,并已取得了矚目成效。而人工免疫系統(tǒng)(AIS)結(jié)合了分類器、神經(jīng)網(wǎng)絡(luò)和機器推理等系統(tǒng)的一些優(yōu)點,具有提供新穎的問題解決方法的潛力。同時AIS在數(shù)據(jù)流聚類中也已有了初步研究,

5、本文針對現(xiàn)有基于AIS的數(shù)據(jù)流聚類存在的不足,研究新的基于AIS的數(shù)據(jù)流聚類算法。本文的研究內(nèi)容和創(chuàng)新工作可概括為以下四個方面。
　　 (1)數(shù)據(jù)流頻繁項挖掘算法的研究
　　 本文在BloomFilter的基礎(chǔ)上,提出空間效率高、可支持表達龐大數(shù)據(jù)集及較高查找效率的數(shù)據(jù)結(jié)構(gòu)—可擴展BloomFilter,并基于該數(shù)據(jù)結(jié)構(gòu)提出基于界標(biāo)窗口模型的數(shù)據(jù)流頻繁項挖掘算法(FI-ESBFL),同時通過理論證明只需比同類算法中更少的

6、計數(shù)器數(shù)目即可達到相同的精度與置信度要求。FI-ESBFL可以根據(jù)數(shù)據(jù)流中數(shù)據(jù)的不同分布及不同的數(shù)據(jù)項的多少動態(tài)調(diào)整所使用的內(nèi)存空間,從而大大減少了內(nèi)存空間的浪費。實驗證明FI-ESBFL具有更高的空間效率與較高的時間效率。本文在H-EBFSL的基礎(chǔ)上還提出了基于衰減窗口模型的數(shù)據(jù)流頻繁項挖掘算法—FI-ESBFD及基于滑動窗口模型的數(shù)據(jù)流頻繁項挖掘算法-FIS-EBFS。FIS-EBFSD具有在一般情況下比同類算法有更高的時間與空間效

7、率。FIS-EBFS具有高效的時間性能。
　　 (2)混合屬性數(shù)據(jù)流聚類分析算法的研究
　　 本文提出兩種不同的基于熵的混合屬性數(shù)據(jù)對象間相似性度量,并在此基礎(chǔ)上提出兩類混合屬性數(shù)據(jù)流聚類算法——CNCE-Stream與CNCDE-Stream。其中CNCDE-Stream同時利用歐式距離與熵來定義混合屬性數(shù)據(jù)對象間的相似性。在算法CNCE-Stream中,利用單一的量——熵度量混合屬性數(shù)據(jù)對象間的相似性,提出數(shù)據(jù)流環(huán)境

8、下概率密度函數(shù)的估計方法-S核方法和帶混合屬性的類的期望熵計算方法。實驗結(jié)果表明,CNCDE-Stream與CNCE-Stream均具有較高的聚類質(zhì)量,且CNCDE-Stream具有很高的時間效率。
　　 (3)高維數(shù)據(jù)流子空間聚類分析算法的研究v
　　 針對大部分現(xiàn)有的數(shù)據(jù)流聚類算法只適合于待聚類的數(shù)據(jù)含有的維度較低的情況及現(xiàn)有數(shù)據(jù)流子空間聚類算法的不足,本文提出基于網(wǎng)格與密度的高維數(shù)據(jù)流子空間聚類算法-SOStrea

9、m。SOStream在線維護一個所有密集網(wǎng)格單元的超集,并提出延遲插入潛在密集網(wǎng)格單元與定期修剪非密集(稀疏)網(wǎng)格單元策略,提高了算法的時間與空間效率。當(dāng)用戶請求時,利用在線維護的密集網(wǎng)格單元生成最終類結(jié)構(gòu)。我們通過實驗證明了本算法的有效性。
　　 (4)基于人工免疫原理的數(shù)據(jù)流聚類分析算法的研究
　　 本文根據(jù)人工免疫系統(tǒng)可動態(tài)適應(yīng)外部環(huán)境的變化,提出一種新的基于人工免疫網(wǎng)絡(luò)的數(shù)據(jù)流聚類算法-AIN-Stream。AI

10、N-Stream利用外部抗原(流數(shù)據(jù))對B細胞的激勵作用定義B細胞的激勵度,并通過為B細胞創(chuàng)建特征向量,利用統(tǒng)計分析的方法自動確定基于人工免疫聚類算法的關(guān)鍵參數(shù)-B細胞識別區(qū)域,保證了聚類結(jié)果的穩(wěn)定性。同時,AIN-Stream利用B細胞特征向量中的統(tǒng)計信息更有效地去除冗余B細胞,進一步提高了算法效率。在生成聚類結(jié)果時,AIN-Stream無需指定類數(shù),可真正實現(xiàn)無監(jiān)督聚類。實驗表明,AIN-Stream能夠動態(tài)適應(yīng)數(shù)據(jù)流的變化,并具較