時(shí)間約束序列模式的有效生成候選項(xiàng)的方法
摘 要: 針對(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)。直到