序列模式挖掘中的增量式更新算法研究.pdf

1、序列模式挖掘是指挖掘相對于時間或其他模式出現(xiàn)頻率高的模式，是數(shù)據(jù)挖掘的一個重要分支。在交易數(shù)據(jù)分析，病癥分析，Web日志分析，天氣預(yù)報等領(lǐng)域具有廣泛的應(yīng)用前景。 本文選擇序列模式作為研究對象，系統(tǒng)的分析了當前序列模式挖掘的現(xiàn)狀；針對一般序列模式算法、交互式序列模式、增量式序列模式三個方面展開研究和實驗。主要研究工作和成果有： 1、分析了序列模式國內(nèi)外的研究現(xiàn)狀。從序列模式挖掘的基本方法和序列模式挖掘現(xiàn)有的模型兩個角度對相

2、關(guān)文獻進行歸類分析。 2、提出了一種基于CTID的改進算法SPM(Sequential Patterns Mining)。該算法利用時序連接，將時序情況分為時序前綴和時序后綴兩種情況進行計算，可以得到更多有效序列；并且在剪枝過程中充分利用CTID表的特點，簡化了剪枝步驟，從而提高了算法效率。 3、提出了一種基于投影數(shù)據(jù)庫的交互式序列模式挖掘算法FISP (Fast Interactive Sequential Patte

3、rns Mining )。在實際挖掘的過程中，用戶通常會指定不同的最小支持度，以得到滿意的序列模式。所以整個挖掘過程是一個迭代和交互的過程。如果支持度改變時，重新挖掘顯然是低效的。FISP利用前次挖掘得到的序列，來縮減本次挖掘的投影數(shù)據(jù)庫；并設(shè)置了一個全局閾值來減少整個交互過程的時間和空間消耗。 4、 提出了基于投影數(shù)據(jù)庫的增量式更新算法ISMP (Incremental Sequential Patterns Mining B

4、ased on Projected Database)。數(shù)據(jù)庫往往是隨時間動態(tài)更新的。更新后，一部分舊的序列模式可能會不再滿足最小支持度，并且會有新的序列模式出現(xiàn)。在處理具有大量數(shù)據(jù)的大型數(shù)據(jù)庫時，對整個數(shù)據(jù)庫重新執(zhí)行一般的序列模式挖掘算法顯然是低效的，因此需要有效的算法來更新、維護和管理已經(jīng)發(fā)現(xiàn)的知識，以反映這種交易數(shù)據(jù)庫的動態(tài)更新。ISMP用間接拼接更新已經(jīng)得到序列，用增量數(shù)據(jù)庫來減小投影數(shù)據(jù)庫，提高了算法效率。并且考慮了數(shù)據(jù)庫減小