一種時序數據間斷頻繁項挖掘算法

劉 昆 李穎芳 李紅林

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

0 引言

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

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

定義（時間序列數據）時間序列數據 S 是一個有限集{（t1，T1），（t2，T2），…，（tn，Tn）}，滿足 ti

本文將時間序列數據的頻繁序列挖掘過程分為以下五個步驟：時間序列數據符號化、對符號化后的序列生成互關聯后繼樹、生成互關聯線索樹、挖掘連續頻繁序、挖掘間斷頻繁序列。

1 針對股票數據應用的時間序列數據符號化表示

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

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

2 連續頻繁項和間斷頻繁項

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

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

如例abcdabaabcabddaadd#，如果當某序列個數大于2時，就認為它是頻繁序列，那么這個序列中b?d、b?a、a?d就是個間斷頻繁序列，d（Gfs（b?d））=|Gfs（b?d）|=3。

3 互關聯后繼樹與互關聯線索樹

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

定義 3.1 線索樹：以 Cm為樹根為 0 層，元模式類型{C1，C2，..，Cm}中的所有元素按順序構成葉子節點為1層，以后繼樹生產過程結合，將后繼樹的分支標記號按后繼歸類到作為下層的新葉子節點為2層，把此樹稱為Cm統計線索樹，此樹共有3層。

定義3.2互關線索數樹：把時間序列符號集S的所有線索樹組成的森林，叫做S的互關聯信息統計線索樹。

4 挖掘連續頻繁序與挖掘間斷頻繁序列

使用互關聯后繼樹挖掘多元連續頻繁序列在參考文獻[1-6]都有所涉獵，本文不過多描述。本文重點主要放在間斷頻繁項的挖掘上。

挖掘間斷頻繁序列分3步進行：

（1）構建可能的間斷頻繁序列。

（2）找出構成可能間斷頻繁序列的緊密連續非頻繁序列。

（3）查詢、檢驗、統計緊密連續非頻繁序列，統計非頻繁序列出現次數，如果出現次數大于最小支持閾值，則為間斷連續頻繁序列。

根據間斷頻繁序列的定義和性質，利用帶權有向圖找尋間斷頻繁項的思想。帶權有向圖建立的步驟如下：

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

（2）利用互關聯統計線索樹，將（1）所建圖進行加權和修枝；利用線索樹的第2層對有向弧進行賦值；例如在序列S中，CmCn子序列出現了w次，則有向弧CmCn的權值為w；刪除權值為0的有向弧。

（3）重復（2），直到加上所有的權和刪除所有的0弧，構成該序列的帶權有向圖。

利用帶權有向圖尋找間斷連續頻繁序列的步驟如下：

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

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

（3）統計V中路的總和，如果總和>=最小支持閾值，那么Cm*…*Cn可能是間斷連續頻繁序列，這些路就是構成可能間斷連續頻繁序列的連續非頻繁序列。

（4）利用互關聯統計線索樹，驗證、統計可能連續非頻繁序列，得到的總和>=最小支持閾值，則構成了間斷頻繁序列，否則，沒有構成間斷頻繁序列。

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

5 實驗分析

本文提出的挖掘算法經過試驗能夠從時間序列數據中有效的提取一些的時態關聯規則。由于實驗選取了1000日交易數據為樣本，本文算法算出的結果和實驗得到的結果完全一致，證明該算法是正確的；經與其他算法挖掘的效率分析比較，本文提出的算法是有效可行的。

［1］劉昆.基于時間序列數據的緊密連續頻繁序列挖掘算法[J].曲靖師范學院學報，2008，6：60-68.

［2］張忠平.基于三元互關聯后繼樹的Web日志挖掘[J].計算機應用與軟件，2011，10.

［3］霍林.二元互關聯后繼樹精簡索引模型研究[J].小型微型計算機系統，2011，2：286-290.

［4］顏文偉，胡運發.一個基于三元互關聯后繼樹的多功能全文檢索系統[J].計算機應用與軟件，2007，2：124-128.

［5］王政華，胡運發.基于后繼區間的互關聯后繼樹搜索算法[J].計算機工程，2007，5：84-86.

［6］楊茹.基于雙排序互關聯后繼樹的索引壓縮和原文生成算法[J].計算機應用與軟件，2010，9：1-4.