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

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

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

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

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