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

1、隨著云計(jì)算、大數(shù)據(jù)以及物聯(lián)網(wǎng)等技術(shù)的迅速發(fā)展，數(shù)據(jù)的存在形式發(fā)生了變化。在許多實(shí)際應(yīng)用中，產(chǎn)生的數(shù)據(jù)大多數(shù)以數(shù)據(jù)流的形式存在，如網(wǎng)頁搜索日志數(shù)據(jù)、傳感器網(wǎng)絡(luò)數(shù)據(jù)、氣候環(huán)境監(jiān)測數(shù)據(jù)、金融交易數(shù)據(jù)以及通信記錄數(shù)據(jù)等等。此外，由于數(shù)據(jù)采集技術(shù)不斷進(jìn)步，數(shù)據(jù)流中采集到的數(shù)據(jù)往往呈現(xiàn)出不確定性，即數(shù)據(jù)的出現(xiàn)通常伴隨一定的概率。傳統(tǒng)的頻繁模式挖掘算法大多數(shù)都是針對(duì)確定性數(shù)據(jù)，包括確定性的靜態(tài)數(shù)據(jù)和確定性的動(dòng)態(tài)數(shù)據(jù)流,而針對(duì)不確定性數(shù)據(jù)流的頻繁模式挖

2、掘算法還尚未成熟。除了具有傳統(tǒng)數(shù)據(jù)流的無限性、快速性、實(shí)時(shí)性等特點(diǎn)，不確定性數(shù)據(jù)流還有數(shù)據(jù)的不確定性問題需要迫切解決，這導(dǎo)致難以在不確定性數(shù)據(jù)流上直接使用傳統(tǒng)的確定性數(shù)據(jù)流頻繁模式挖掘算法，并且傳統(tǒng)的概要數(shù)據(jù)結(jié)構(gòu)不能夠?qū)Σ淮_定性數(shù)據(jù)進(jìn)行高效的存儲(chǔ)。因此，有必要設(shè)計(jì)優(yōu)化的適合不確定性數(shù)據(jù)流的概要數(shù)據(jù)結(jié)構(gòu)，并且在此基礎(chǔ)上提出有效的不確定性數(shù)據(jù)流頻繁模式挖掘算法。
　　本文對(duì)不確定性數(shù)據(jù)流頻繁模式挖掘中存在的問題進(jìn)行了詳細(xì)介紹，分析了當(dāng)

3、前該領(lǐng)域一些經(jīng)典算法的優(yōu)缺點(diǎn)，提出了一種基于滑動(dòng)窗口的不確定性數(shù)據(jù)流頻繁模式挖掘算法BSUF-mine。該算法設(shè)計(jì)了一種符合不確定性數(shù)據(jù)流特點(diǎn)的概要數(shù)據(jù)結(jié)構(gòu)，該結(jié)構(gòu)能夠高效的對(duì)不確定性數(shù)據(jù)流的概要數(shù)據(jù)信息進(jìn)行存儲(chǔ)，并且能夠有效的提高頻繁模式挖掘的時(shí)空效率。此外，針對(duì)項(xiàng)集期望支持度計(jì)算中存在的問題，本文加入了數(shù)據(jù)項(xiàng)權(quán)重因素的考慮，在BSUF-mine算法的基礎(chǔ)上，提出了一種改進(jìn)的頻繁模式挖掘算法WBSUF-mine。該算法能夠有效的挖掘出

4、長度較長的頻繁模式，保證頻繁模式挖掘結(jié)果的完整性。本文的主要工作包括：
　　(1)本文詳細(xì)介紹了不確定性數(shù)據(jù)的相關(guān)理論，包括不確定性數(shù)據(jù)的產(chǎn)生原因、表現(xiàn)形式及處理模型；并且對(duì)頻繁模式挖掘領(lǐng)域的經(jīng)典算法的優(yōu)缺點(diǎn)進(jìn)行了分析和討論，包括不確定性數(shù)據(jù)頻繁模式挖掘算法、確定性數(shù)據(jù)流頻繁模式挖掘算法、不確定性數(shù)據(jù)流頻繁模式挖掘算法。
　　(2)針對(duì)不確定性數(shù)據(jù)流頻繁模式挖掘算法SUF-growth存在的概要數(shù)據(jù)結(jié)構(gòu)壓縮程度低，在內(nèi)存中會(huì)

5、產(chǎn)生大量冗余節(jié)點(diǎn)的問題，設(shè)計(jì)了一種高壓縮程度的概要數(shù)據(jù)結(jié)構(gòu)BSUF-stream，并提出了一種有效的不確定性數(shù)據(jù)流頻繁模式挖掘算法BSUF-mine，詳細(xì)介紹了該算法的主要思想和所釆用的概要數(shù)據(jù)結(jié)構(gòu)BSUF-stream，并且從內(nèi)存消耗、時(shí)間消耗和可擴(kuò)展性三個(gè)方面與SUF-growth算法進(jìn)行了對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，BSUF-mine算法能夠有效的減少內(nèi)存中冗余節(jié)點(diǎn)的數(shù)量，獲得較高的內(nèi)存利用率和時(shí)間效率。
　　(3)針對(duì)在計(jì)算項(xiàng)

6、集的期望支持度時(shí)采用對(duì)數(shù)據(jù)項(xiàng)概率進(jìn)行簡單相乘的方式，沒有充分考慮數(shù)據(jù)項(xiàng)的權(quán)重因素而丟失長度較長的頻繁項(xiàng)集的問題，結(jié)合BSUF-mine算法，提出了一種有效的不確定性數(shù)據(jù)流頻繁模式挖掘算法 WBSUF-mine，詳細(xì)介紹了該算法的主要思想和所采用的概要數(shù)據(jù)結(jié)構(gòu)WBSUF-stream，并且從內(nèi)存消耗、時(shí)間消耗和頻繁模式的分布情況三個(gè)方面與BSUF-mine算法進(jìn)行了對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，WBSUF-mine算法能在保證合理的內(nèi)存開銷和運(yùn)