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

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

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

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

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

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

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

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

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

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