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

1、近年來，不確定數(shù)據(jù)(Uncerta in Data)得到了越來越廣泛的重視。數(shù)據(jù)的不確定性本身存在于許多真實世界的應用，例如傳感器數(shù)據(jù)監(jiān)測、環(huán)境監(jiān)視、移動軌跡、定位服務，歸因于環(huán)境因素、設備缺陷、人為問題等。數(shù)據(jù)不確定性普遍存在的同時，且不確定性數(shù)據(jù)往往扮演著關鍵角色。不確定數(shù)據(jù)挖掘也成為數(shù)據(jù)挖掘領域中一個非常重要的研究課題。本文以不確定性數(shù)據(jù)的頻繁序列模式挖掘算法作為研宄對象。相比于確定序列數(shù)據(jù)庫，不確定序列數(shù)據(jù)庫中挖掘序列模式更加復

2、雜，其通常有著更大的搜索空間。由于數(shù)據(jù)的不同，已知的目前被廣泛應用的基于確定數(shù)據(jù)的序列模式挖掘方法也不能夠直接用來解決不確定序列模式挖掘問題。
　　本文分析了在確定的數(shù)據(jù)中挖掘序列模式的方法，分別基于候選集生成-測試框架與基于模式增長框架，介紹了幾個經(jīng)典的序列模式挖掘算法。通過對序列模式挖掘算法的分析，得知模式增長框架相比候選集生成-測試框架更具有擴展性。然后，闡述了不確定數(shù)據(jù)挖掘的一些基礎理論。給出了可能世界數(shù)據(jù)模型，包括源頭水

3、平不確定數(shù)據(jù)模型與事件水平不確定數(shù)據(jù)模型。對本文所研究的一般不確定序列數(shù)據(jù)，需要序列模式進行判斷是否為可能頻繁序列模式，有兩種常采用的斷定方式：期望支持度和概率頻繁。綜述了不確定數(shù)據(jù)中頻繁序列模式挖掘算法，給出了不確定數(shù)據(jù)中挖掘頻繁序列模式的一般思路與方法。通過不確定序列模式挖掘算法的比較分析，聯(lián)系到經(jīng)典的序列模式挖掘理論框架，得知模式增長框架比候選集生成框架更具擴展性。其中在對不確定數(shù)據(jù)序列頻繁性的判斷上概率頻繁性優(yōu)于期望支持度，同時

4、在計算概率頻繁上分而治之策略相對動態(tài)規(guī)劃策略開銷少些。
　　對于不確定數(shù)據(jù)的頻繁序列模式挖掘，會導致可能頻繁模式數(shù)量的指數(shù)級出現(xiàn)，其中有些無用的挖掘結果，引起頻繁序列的冗余。針對上述不足，提出了可能頻繁閉序列模式(pfcsp)的定義，以及一種基于不確定數(shù)據(jù)的可能頻繁閉序列挖掘算法 U-F CS M。此算法中，基于一種元組不確定數(shù)據(jù)模型，采取分而治之的策略去計算序列的概率頻繁性，應用BIDE算法的閉序列思想判斷可能頻繁序列是否是可能