面向不確定數(shù)據(jù)流的聚類和模式挖掘技術研究.pdf

1、在網(wǎng)絡流量管理、金融數(shù)據(jù)分析、網(wǎng)站日志管理、視頻流版權保護等數(shù)據(jù)流應用中，由于設備精度、噪音、干擾和隱私保護等問題，數(shù)據(jù)流中往往包含著大量不確定性數(shù)據(jù)，而這些不確定性對數(shù)據(jù)流的管理和挖掘帶來了挑戰(zhàn)。通過分析數(shù)據(jù)流的不確定性，可以降低不確定性對挖掘結果的影響，進而提升數(shù)據(jù)流挖掘的質量。
　　在針對不確定數(shù)據(jù)流的挖掘中，分析數(shù)據(jù)的不確定性特征對控制挖掘質量尤為重要。在交通監(jiān)控、金融數(shù)據(jù)分析、網(wǎng)站監(jiān)控等包含大量對象的應用中，數(shù)據(jù)對象的不

2、確定性，對計算對象間的相似度和對象聚類的質量產(chǎn)生了很大的影響。而在對環(huán)境監(jiān)控、氣象監(jiān)測等數(shù)據(jù)流的在線聚類過程中，需要考慮數(shù)據(jù)元組的不確定性對微簇質量的影響。在針對不確定數(shù)據(jù)流的頻繁模式挖掘中，需要根據(jù)不確定項集的概率頻繁程度和概率分布，反映不確定頻繁項集的頻次分布情況。在針對不確定數(shù)據(jù)的序列模式挖掘中，需要基于概率模型度量序列模式的概率頻繁程度，這就需要對現(xiàn)有的序列模式挖掘方法進行擴展，并提高概率序列模式的挖掘效率。
　　本論文旨

3、在通過對不確定數(shù)據(jù)概率特征進行分析，以提高針對不確定數(shù)據(jù)流的聚類和模式挖掘的質量。論文圍繞著基礎科研業(yè)務費項目“基于概要模型的海量復雜時序數(shù)據(jù)分析方法研究”、自然基金項目“多核系統(tǒng)下調控模式識別的MapReduce模型及算法研究”和基礎科研業(yè)務費項目“基于Sketch的不確定流數(shù)據(jù)管理關鍵技術研究”等課題，研究不確定數(shù)據(jù)流的挖掘。本文的研究內容主要針對不確定對象聚類、不確定數(shù)據(jù)流聚類、概率頻繁模式挖掘和概率頻繁序列模式挖掘四個方面，概括

4、為以下四個部分：
　　第一部分研究基于概要結構的不確定對象聚類方法。針對現(xiàn)有的不確定聚類方法未考慮不確定對象的概率分布的問題，分別在離散域和連續(xù)域上對不確定對象的概率分布進行建模。為了使概率分布的提取更適合數(shù)據(jù)流環(huán)境，通過構建概要數(shù)據(jù)模型以降低海量對象數(shù)據(jù)的規(guī)模。針對概要數(shù)據(jù)，采用Kullback-Leibler散度計算不確定對象的相似度，并使用改進的快速高斯變換提高了計算相似度的效率。在此基礎上，本文采用改進的KL-散度作為相似

5、性度量，對現(xiàn)有的基于劃分的聚類算法分別進行了擴展，提出了基于概率分布相似性的KM-KL聚類算法。最后通過仿真實驗驗證了該算法對聚類的質量和效率的提升。
　　第二部分研究基于質量度量的不確定數(shù)據(jù)流聚類方法。針對現(xiàn)有不確定數(shù)據(jù)流在線聚類方法，基于概率分布給出了微簇的質量度量模型，并基于質量度量構建了描述微簇不確定性質量的直方圖模型。在此基礎上，提出了一種基于質量度量和時間劃分的在線微簇維護策略，通過將緩沖區(qū)按照質量和時間區(qū)間進行劃分，

6、根據(jù)微簇的質量特征調整緩沖區(qū)，以達到對微簇的質量和成長時間進行細粒度控制的目的。并基于微簇維護策略，提出了一種基于質量度量的不確定數(shù)據(jù)流聚類算法。同時，針對高維不確定數(shù)據(jù)流，基于質量度量和投影映射方法，將高維全空間投影到微簇相關的子空間中。在此基礎上，給出了在微簇相關子空間中的相似度計算公式，提出了一種基于子空間的高維空間中不確定數(shù)據(jù)流的聚類算法。最后通過分別與現(xiàn)有算法進行實驗比較，說明了低維和高維聚類算法的準確性和高效性。
　　

7、第三部分研究基于Sketch的不確定數(shù)據(jù)流頻繁模式挖掘方法。基于可能世界模型描述頻繁模式的概率特征，通過將后綴支持度與Sketch相結合以優(yōu)化概率頻繁模式的挖掘方法。將概率頻繁模式挖掘分為兩個部分：面向支持度的頻繁模式挖掘和頻繁項的概率分布統(tǒng)計。基于后綴支持度，優(yōu)化了頻繁模式樹的構建，提出了一種基于后綴支持度的頻繁模式挖掘算法。同時，基于Sketch和滑動窗口，統(tǒng)計項集的概率分布信息，并提出了一種面向不確定數(shù)據(jù)流的概率頻繁模式的挖掘策略

8、。同時，基于概率分布信息，設計了頻繁模式的預測模型，提出了基于預測模型的剪枝算法。最后通過實驗表明基于后綴支持度和預測剪枝的挖掘算法，能提高不確定數(shù)據(jù)流頻繁模式挖掘的效率和準確性。
　　第四部分研究基于增長模式的不確定序列模式挖掘方法。在分析序列級不確定數(shù)據(jù)模型特點的基礎上，闡述了概率序列模式的頻度測定方法。分析了現(xiàn)有的序列模式挖掘算法中的樹形存儲結構的冗余性，通過對相同后綴進行合并，基于有向無環(huán)圖提出了一種概率序列的存儲結構PG