摘 要： 針對(duì)序列模式的幾個(gè)經(jīng)典的算法的缺點(diǎn)，提出了一種基于時(shí)間約束序列模式的快速產(chǎn)生候選項(xiàng)的方法（TFEGC）。此算法不但避免了頻繁的掃描數(shù)據(jù)庫(kù)，還考慮了時(shí)間限制因素，避免了無(wú)用的候選序列的產(chǎn)生，提高了算法運(yùn)行的時(shí)間效率。
關(guān)鍵詞： 序列模式挖掘；時(shí)間約束；候選項(xiàng);快速產(chǎn)生

序列模式挖掘在很多領(lǐng)域都具有十分重要的意義，比如它可以根據(jù)分析顧客購(gòu)買行為來(lái)決定商品的擺放位置，從而制定商場(chǎng)的營(yíng)銷策劃。所以，近年來(lái)出現(xiàn)了很多序列模式挖掘的改進(jìn)算法，目前提出算法中，有兩類比較典型：GSP[1]算法和采用分治策略來(lái)進(jìn)行模式增長(zhǎng)的PrefixSpan[2]算法。但是這兩種算法都存在一定的缺點(diǎn)。參考文獻(xiàn)[3]中提出的快速有效的產(chǎn)生候選項(xiàng)的FEGC算法，不需要多次掃描數(shù)據(jù)庫(kù)，且不需要在前一次迭代的基礎(chǔ)上來(lái)產(chǎn)生候選項(xiàng)，也不需對(duì)非頻繁項(xiàng)進(jìn)行剪枝或修剪，能夠達(dá)到快速產(chǎn)生候選項(xiàng)的效果。但是，F(xiàn)EGC算法是針對(duì)數(shù)據(jù)庫(kù)總體的序列來(lái)產(chǎn)生候選項(xiàng)的，有些并不是有效的和用戶感興趣的序列，這在實(shí)際應(yīng)用中就耗費(fèi)了大量的時(shí)間和空間，如分析顧客的購(gòu)買行為，就不需要將其一月份購(gòu)買的產(chǎn)品和十二月份購(gòu)買的產(chǎn)品放在一起進(jìn)行研究比較。所以本文在FEGC算法的基礎(chǔ)上將時(shí)間限制因素加了進(jìn)去，可稱之為TFEGC算法，本算法繼承了FEGC算法的優(yōu)點(diǎn)，而且避免了不必要的、無(wú)用的一些候選項(xiàng)的產(chǎn)生，提高了算法的運(yùn)行效率，且在序列結(jié)合的過(guò)程中，只需檢查uid、fid(t)以及s(t)的值，便可知道與哪些項(xiàng)進(jìn)行結(jié)合，無(wú)須再進(jìn)行檢驗(yàn)。
1 相關(guān)算法介紹
GSP算法，即廣義序列模式算法，使用序列模式的向下封閉性，并采用多次掃描的候選產(chǎn)生-測(cè)試方法，它是由Srikant和Agrawal于1996年提出的。它的主要思想是利用序列模式的種子集，即前次掃描得來(lái)的序列模式來(lái)產(chǎn)生潛在的頻繁序列，即候選序列，每個(gè)候選序列都會(huì)比產(chǎn)生它的種子序列模式多包含一個(gè)項(xiàng)。直到