一種時(shí)序數(shù)據(jù)間斷頻繁項(xiàng)挖掘算法

劉 昆 李穎芳 李紅林

（1.曲靖師范學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院，云南 曲靖 655011；2.紅河學(xué)院 工學(xué)院，云南 蒙自 661100）

0 引言

在人類社會和自然界的變遷中，都存在時(shí)間的因素。例如，金融證券市場中每天的股票交易中價(jià)格波動；零售行業(yè)中，某項(xiàng)商品每天的銷售額；氣象預(yù)報(bào)研究中，某一地區(qū)的每天氣溫與氣壓的讀數(shù)以及在生物醫(yī)學(xué)中，某一癥狀病人在每個(gè)時(shí)刻的心跳變化，課堂作業(yè)中學(xué)生交作業(yè)的先后順序等；這些事件中都有時(shí)間的先后順序，把這些信息稱為數(shù)據(jù)，它們是有時(shí)間先后性質(zhì)的數(shù)據(jù)，是時(shí)間序列數(shù)據(jù)。所謂時(shí)間序列數(shù)據(jù)就是在一個(gè)確定時(shí)間區(qū)間，以確定的時(shí)間量子或者時(shí)刻為單位對研究對象進(jìn)行連續(xù)觀測得到的一組記錄，這組記錄是按時(shí)間順序排列的。

不同研究者對時(shí)間序列的定義是不一樣的。根據(jù)所查文獻(xiàn)和收據(jù)的資料，對時(shí)間序列數(shù)據(jù)給出如下形式化定義：

定義（時(shí)間序列數(shù)據(jù)）時(shí)間序列數(shù)據(jù) S 是一個(gè)有限集{（t1，T1），（t2，T2），…，（tn，Tn）}，滿足 ti

本文將時(shí)間序列數(shù)據(jù)的頻繁序列挖掘過程分為以下五個(gè)步驟：時(shí)間序列數(shù)據(jù)符號化、對符號化后的序列生成互關(guān)聯(lián)后繼樹、生成互關(guān)聯(lián)線索樹、挖掘連續(xù)頻繁序、挖掘間斷頻繁序列。

1 針對股票數(shù)據(jù)應(yīng)用的時(shí)間序列數(shù)據(jù)符號化表示

針對某股市交易數(shù)據(jù)中，pi=（第i天收盤價(jià)-第i-1天收盤價(jià)）/第i天收盤價(jià) *100%，當(dāng) pi為 0%～2%時(shí)，視為第 i天為“小漲”；pi大于5%時(shí)記為第 i天“大漲”，pi在 2%～5%之間，第 i天為“上漲”，同理，當(dāng)pi為 0%～-2%時(shí)，第 i天為“小跌”；pi小于 5%時(shí)記為第 i天“大跌”，pi在-2%～-5%之間，記為第i天為“下跌”。把“小漲”用A表示，“上漲”用B表示，“大漲”用C表示，“小跌”用D表示，“下跌”用 E表示，“大跌”用F表示，則此只股票收盤價(jià)數(shù)據(jù)變化規(guī)律就可以轉(zhuǎn)化為包含符號{A，B，C，D，E，F(xiàn)}的字符串。

利用該算法就可以把一只股票的變化規(guī)律轉(zhuǎn)化成一串字符序列S，S=S1S2…Sn，Si∈String（A，B，C，D，E，F(xiàn)），i=1，2，…，n。

2 連續(xù)頻繁項(xiàng)和間斷頻繁項(xiàng)

把某股票交易日收盤價(jià)的時(shí)間序列數(shù)據(jù)符號化后得到字符串，子序列相等的定義、連續(xù)頻繁系列的定義、k元連續(xù)頻繁序列集的定義參考論文[1]。

間斷頻繁序列是不連續(xù)的、有間斷的頻繁序列，其定義如下：在S序列中，有子序列 Cm*…*Cn（m=1，2，…，k-2 ； n>=m+2），當(dāng) *…* 對應(yīng)任意某個(gè)固定長度子序列時(shí)，與序列Ci*…*Cj相等的子序列數(shù)小于最小支持閾值（也就是說形如Ci∞固定長度序列∞Cj的序列是連續(xù)非頻繁序列）；但是，如果把幾個(gè)這樣的不相等的緊密連續(xù)非頻繁序列計(jì)數(shù)相加，所得和值大于最小支持閾值，那么就稱Ci*…*Cj為間斷連續(xù)頻繁序列。

如例abcdabaabcabddaadd#，如果當(dāng)某序列個(gè)數(shù)大于2時(shí)，就認(rèn)為它是頻繁序列，那么這個(gè)序列中b?d、b?a、a?d就是個(gè)間斷頻繁序列，d（Gfs（b?d））=|Gfs（b?d）|=3。

3 互關(guān)聯(lián)后繼樹與互關(guān)聯(lián)線索樹

復(fù)旦大學(xué)的胡運(yùn)發(fā)教授和申展、曾海泉等人幾年來，對互關(guān)聯(lián)后繼樹做了深入的研究工作，并獲得大量的好的結(jié)果[1-6]。互關(guān)聯(lián)后繼樹模型是一種應(yīng)用在文本索引中的模型，對連續(xù)、有序的字符建立索引，它的任意可進(jìn)入性給查詢序列型數(shù)據(jù)帶來很大的方便[1-6]，本文對互關(guān)聯(lián)后繼樹就不再論述。

定義 3.1 線索樹：以 Cm為樹根為 0 層，元模式類型{C1，C2，..，Cm}中的所有元素按順序構(gòu)成葉子節(jié)點(diǎn)為1層，以后繼樹生產(chǎn)過程結(jié)合，將后繼樹的分支標(biāo)記號按后繼歸類到作為下層的新葉子節(jié)點(diǎn)為2層，把此樹稱為Cm統(tǒng)計(jì)線索樹，此樹共有3層。

定義3.2互關(guān)線索數(shù)樹：把時(shí)間序列符號集S的所有線索樹組成的森林，叫做S的互關(guān)聯(lián)信息統(tǒng)計(jì)線索樹。

4 挖掘連續(xù)頻繁序與挖掘間斷頻繁序列

使用互關(guān)聯(lián)后繼樹挖掘多元連續(xù)頻繁序列在參考文獻(xiàn)[1-6]都有所涉獵，本文不過多描述。本文重點(diǎn)主要放在間斷頻繁項(xiàng)的挖掘上。

挖掘間斷頻繁序列分3步進(jìn)行：

（1）構(gòu)建可能的間斷頻繁序列。

（2）找出構(gòu)成可能間斷頻繁序列的緊密連續(xù)非頻繁序列。

（3）查詢、檢驗(yàn)、統(tǒng)計(jì)緊密連續(xù)非頻繁序列，統(tǒng)計(jì)非頻繁序列出現(xiàn)次數(shù)，如果出現(xiàn)次數(shù)大于最小支持閾值，則為間斷連續(xù)頻繁序列。

根據(jù)間斷頻繁序列的定義和性質(zhì)，利用帶權(quán)有向圖找尋間斷頻繁項(xiàng)的思想。帶權(quán)有向圖建立的步驟如下：

（1）建立以 C={C1，C2，…，Cm}頂點(diǎn)集的有向完全圖。

（2）利用互關(guān)聯(lián)統(tǒng)計(jì)線索樹，將（1）所建圖進(jìn)行加權(quán)和修枝；利用線索樹的第2層對有向弧進(jìn)行賦值；例如在序列S中，CmCn子序列出現(xiàn)了w次，則有向弧CmCn的權(quán)值為w；刪除權(quán)值為0的有向弧。

（3）重復(fù)（2），直到加上所有的權(quán)和刪除所有的0弧，構(gòu)成該序列的帶權(quán)有向圖。

利用帶權(quán)有向圖尋找間斷連續(xù)頻繁序列的步驟如下：

（1）根據(jù)間斷頻繁序列的性質(zhì)，如果CmCn∈{2元頻繁序列}，那么Cm、Cn一定∈{1元頻繁項(xiàng)}；根據(jù)緊密連續(xù)頻繁序列與間斷連續(xù)頻繁序列間的關(guān)系，刪除長度為d（Gfs（Cm*…*Cn））連續(xù)頻繁序列集中所有的開始字符和結(jié)束字符對，并在加權(quán)有向圖中減去這些緊密頻繁序列所經(jīng)過的路的權(quán)值，達(dá)到修正加權(quán)有向圖權(quán)值的目的；根據(jù)剩下的加權(quán)圖，找到可能產(chǎn)生間斷連續(xù)頻繁序列Cm、Cn；從帶權(quán)有向圖中提取，以Cm為出度，Cn為入度的有向子圖。

（2）根據(jù)（1）中提取的子圖，找出從 Cm到 Cn所有長度為 d（Gfs（Ci*…*Cj））有向路，放在 V 中。

（3）統(tǒng)計(jì)V中路的總和，如果總和>=最小支持閾值，那么Cm*…*Cn可能是間斷連續(xù)頻繁序列，這些路就是構(gòu)成可能間斷連續(xù)頻繁序列的連續(xù)非頻繁序列。

（4）利用互關(guān)聯(lián)統(tǒng)計(jì)線索樹，驗(yàn)證、統(tǒng)計(jì)可能連續(xù)非頻繁序列，得到的總和>=最小支持閾值，則構(gòu)成了間斷頻繁序列，否則，沒有構(gòu)成間斷頻繁序列。

（5）利用上面的步驟找出所有的間斷頻繁序列。

5 實(shí)驗(yàn)分析

本文提出的挖掘算法經(jīng)過試驗(yàn)?zāi)軌驈臅r(shí)間序列數(shù)據(jù)中有效的提取一些的時(shí)態(tài)關(guān)聯(lián)規(guī)則。由于實(shí)驗(yàn)選取了1000日交易數(shù)據(jù)為樣本，本文算法算出的結(jié)果和實(shí)驗(yàn)得到的結(jié)果完全一致，證明該算法是正確的；經(jīng)與其他算法挖掘的效率分析比較，本文提出的算法是有效可行的。

［1］劉昆.基于時(shí)間序列數(shù)據(jù)的緊密連續(xù)頻繁序列挖掘算法[J].曲靖師范學(xué)院學(xué)報(bào)，2008，6：60-68.

［2］張忠平.基于三元互關(guān)聯(lián)后繼樹的Web日志挖掘[J].計(jì)算機(jī)應(yīng)用與軟件，2011，10.

［3］霍林.二元互關(guān)聯(lián)后繼樹精簡索引模型研究[J].小型微型計(jì)算機(jī)系統(tǒng)，2011，2：286-290.

［4］顏文偉，胡運(yùn)發(fā).一個(gè)基于三元互關(guān)聯(lián)后繼樹的多功能全文檢索系統(tǒng)[J].計(jì)算機(jī)應(yīng)用與軟件，2007，2：124-128.

［5］王政華，胡運(yùn)發(fā).基于后繼區(qū)間的互關(guān)聯(lián)后繼樹搜索算法[J].計(jì)算機(jī)工程，2007，5：84-86.

［6］楊茹.基于雙排序互關(guān)聯(lián)后繼樹的索引壓縮和原文生成算法[J].計(jì)算機(jī)應(yīng)用與軟件，2010，9：1-4.