不確定數(shù)據(jù)流中頻繁數(shù)據(jù)挖掘研究.pdf

1、隨著計算機技術與通信技術的快速發(fā)展，傳感器網(wǎng)絡、Web服務和RFID技術得到了廣泛應用，從而使得不確定性數(shù)據(jù)管理得到廣泛的重視.在許多現(xiàn)實的應用中，例如經(jīng)濟形勢預測、金融信息分析、生態(tài)環(huán)境監(jiān)測、網(wǎng)絡安全監(jiān)控、物流管理等等，不確定數(shù)據(jù)流扮演著關鍵角色.在這些應用中，傳統(tǒng)的數(shù)據(jù)管理技術卻無法有效地管理新型的不確定數(shù)據(jù)流，這就引發(fā)了學術界和工業(yè)界對研發(fā)新型的不確定數(shù)據(jù)流管理技術的興趣.因此，不確定數(shù)據(jù)流上的數(shù)據(jù)挖掘已經(jīng)成為當前數(shù)據(jù)挖掘領域的研

2、究熱點.
　　當前對于不確定數(shù)據(jù)流上的挖掘主要集中在不確定數(shù)據(jù)流上的聚類、不確定數(shù)據(jù)流上的頻繁模式挖掘、Skyline查詢、數(shù)據(jù)世系分析、異常分析等.本文在深入研究國內外的各種不確定數(shù)據(jù)流挖掘技術的基礎上，討論了目前國內外有關不確定數(shù)據(jù)流頻繁數(shù)據(jù)挖掘的研究現(xiàn)狀.由于不確定數(shù)據(jù)流上的頻繁數(shù)據(jù)挖掘是不確定數(shù)據(jù)流上的關聯(lián)規(guī)則、分類、聚類等挖掘的基礎，在不確定數(shù)據(jù)流挖掘中具有重要的地位.因此，本文在不確定數(shù)據(jù)流上頻繁數(shù)據(jù)挖掘方面進行了深入

3、的研究，提出了有效的頻繁數(shù)據(jù)挖掘算法.本文的主要工作有:
　　(1)提出了一種基于滑動窗口的不確定數(shù)據(jù)流中頻繁項查詢算法SWBUFIM.本文根據(jù)頻繁項的本質特性以及馬爾科夫不等式，給出了兩個裁剪規(guī)則，用于對不確定數(shù)據(jù)流進行預處理，裁剪掉不可能成為頻繁項的元組.在此基礎上我們:一方面利用動態(tài)規(guī)劃方法計算期望概率，保證在O(n2)時間內完成期望概率的計算;另一方面，根據(jù)不同數(shù)據(jù)項相互獨立性原理，針對不同數(shù)據(jù)項開辟子滑動窗口，并且根據(jù)數(shù)

4、據(jù)項的組合數(shù)目進行行列劃分來處理頻繁項挖掘問題，并在動態(tài)規(guī)劃方法的基礎上，進一步改進期望概率計算方法，只需要動態(tài)規(guī)劃滑動窗口中前玨1項即可保證在O(n)時間內有效地完成期望概率的計算.實驗結果表明，所提出的查詢算法SWBUFIM具有較快的處理速度，其空間復雜度隨著處理數(shù)據(jù)規(guī)模的增加成線性增長.
　　(2)提出了一種基于滑動窗口的不確定數(shù)據(jù)流中top-k查詢算法MPTopKTS.本文針對top-k查詢的定義，根據(jù)不確定數(shù)據(jù)流及其滑動

5、窗口的特性，研究基于滑動窗口top-k查詢問題，提出了所有可能世界中元組集成員相對得分值高并且具有最大出現(xiàn)概率的top-k元組集(MPTopKTS)的查詢算法.該算法基于滑動窗口建立概要表，然后在每一時刻對概要表進行修改，有效地減少了top-k查詢問題的復雜性;能夠在查詢準確性與查詢開銷之間取得平衡，較小的計算開銷獲得高質量的近似結果.實驗結果表明，所提出的查詢算法在時間與空間復雜性方面優(yōu)于其他類似的算法.
　　(3)提出一種基于

6、滑動窗口的不確定數(shù)據(jù)流中頻繁閉項集的采樣挖掘算法MFCIFUDS.本文針對不確定數(shù)據(jù)流頻繁閉項集的挖掘問題，首先使用采樣的方法，基于隨機采樣概率，把由不確定數(shù)據(jù)組成的事務轉換成由確定性數(shù)據(jù)組成的事務，再利用基于確定性數(shù)據(jù)模型的頻繁閉項集挖掘技術完成不確定數(shù)據(jù)流中頻繁閉項集的挖掘任務.本文不但從理論上證明了基于采樣技術利用確定性數(shù)據(jù)挖掘算法解決不確定數(shù)據(jù)挖掘問題的可行性，而且提出了一種改進頻繁模式樹生成與修改技術，有效地提高了基于FP-t

7、ree頻繁模式樹的頻繁閉項集挖掘速度.實驗結果表明，所提出的查詢算法MFCIFUDS有較高的挖掘精度和處理速度.
　　(4)提出了一種基于滑動窗口的不確定數(shù)據(jù)流中頻繁數(shù)量區(qū)間模式的挖掘算法MFIPatFUS.不同于處理常規(guī)二進制項集事務不確定數(shù)據(jù)流，數(shù)量區(qū)間事務不確定數(shù)據(jù)流使用數(shù)量區(qū)間來表示事務屬性，其不確定性在于屬性數(shù)量區(qū)間范圍的波動性，數(shù)量區(qū)間分布體現(xiàn)某種分布概率.本文借鑒常規(guī)的基于頻繁模式樹的不確定數(shù)據(jù)流頻繁模式挖掘算法，設

8、計一種頻繁數(shù)量區(qū)間模式生成樹FIPatTree，用于捕獲不確定數(shù)據(jù)流中所有事務的數(shù)量區(qū)間信息.我們把原始數(shù)量區(qū)間邊界值作為基元素，根據(jù)基元素的分布情況建立基數(shù)量區(qū)間，從而一方面基于基數(shù)量區(qū)間對原始數(shù)量區(qū)間進行重新劃分;另一方面根據(jù)基數(shù)量區(qū)間數(shù)值范圍在原始數(shù)量區(qū)間中所占比例決定其基數(shù)量區(qū)間概率.算法MFIPatFUS采用滑動窗口模型，使用FIPatTree樹作為概要數(shù)據(jù)結構，事務屬性以基數(shù)量區(qū)間結點保存在FIPatTree樹中.建立樹的過

9、程類似常規(guī)頻繁模式生成樹的建立過程，不同點在于當屬性基數(shù)量區(qū)間與出現(xiàn)概率均相同時，結點方可共享.對于共享結點設立頻次與局部概率統(tǒng)計數(shù)值，為了方便遍歷與修改，增設了與FIPatTree樹相關聯(lián)的屬性索引與基數(shù)量區(qū)間索引.基于頻繁數(shù)量區(qū)間模式生成樹FIPatTree的頻繁數(shù)量區(qū)間模式挖掘過程采用基于投影基與條件樹的遞歸挖掘方法.實驗結果表明，所提出滑動窗口模型的挖掘算法MFIPatFUS對處理數(shù)量區(qū)間事務組成的不確定數(shù)據(jù)流頻繁數(shù)量區(qū)間模式挖