時序關聯規則的挖掘算法研究

摘 要：基于概念格理論，本文研究了對時間序列的波動情況進行周期關聯規則的挖掘。首先對時間序列進行了反季節化預處理，然后給出了生成周期關聯規則的算法，在算法內部對生成的概念進行了剪枝處理，有效的提高了挖掘速度。并用所給出的高精度模型對不滿足移動平均法反季節化預處理條件的時間序列進行了反季節化計算。

關鍵詞：數據挖掘；時間序列；關聯規則；形式概念分析

1 引言

目前，關于時間序列中的周期分析正在受到數據挖掘領域的重視，如序列的周期模式和周期規則的發現。針對周期模式的挖掘，即在時序數據庫中挖掘重復出現的模式。周期模式挖掘可以看成是以一組分片序列為持續時間的序列模式挖掘，例如，在每年春節銷售這一事件出現前后的每一天的銷售等。周期模式可以應用于許多重要的領域，例如，季節、潮汐、行星軌道、每日能量消耗、每日交通模式以及每周特定時間的所有TV節目。

2 時間序列

時間序列是指按時間順序排列的隨時間變化的數據集合。這些數據通常是等時間間隔測得的數值，在經濟、技術的很多領域都廣泛存在[1]，如股票每日波動，科學實驗，醫療等等。隨著信息技術的廣泛使用，人類所擁有的時間序列信息量急劇增加。針對這些海量歷史時序數據，如何利用新的技術方法，將其轉化為可靠的知識信息，提高人類對未來的預測能力以及對未來事件的提前控制能力，一直受到人們的密切關注。

關于時間序列的分析，可以用很多直觀的方法檢測時間序列中存在的變化。實際的時間序列數據有時要作某種形式的變換。這樣做不但可以穩定時間序列的變化，而且可以解決數據的維度災難問題。平滑就是一種去除時間序列中非系統化行為的方法。

3 時序關聯規則挖掘的預處理

當一個時段內序列出現某一波動后，得到其后續時段內，序列將要發生的波動情況即對時間序列的波動情況進行周期關聯規則的挖掘。在此過程中，首先應用移動平均法對時間序列進行了反季節化預處理，得到了基于平均趨勢水平的波動序列；然后對該波動序列進行了周期關聯規則的挖掘；最后，通過分析新時段內出現的波動情況和挖掘所得規則的比較，得到了未來時段內將要發生的波動情況。這里將概念格理論和時序波動算法相結合，提出了對片段多值背景生成周期關聯規則的新并行算法。在計算新時段內發生序列的波動情況時，給出了一個對新發生序列反季節化的預測模型，預測了新發生序列反季節化處理后的序列值，并且達到了很高的精度。最終實現了對未來序列波動情況的提前發現。

由于原移動平均法計算趨勢時，丟棄了時間序列尾端中不足一個步長內的序列項，出現了與預測值關聯最大的近期因素被人為忽略，不但使所得結論產生了被掩蓋的誤差，而且使該方法缺乏即時使用性。為了修正原移動平均法的不足，并且為傳統預測方法與關聯規則挖掘方法的結合搭起橋梁，給出了一個當 時，計算 值的模型，

在式（1）中

上述模型在不同時段內記述的不同經濟活動數據中進行了仿真試驗，實驗結果表明，所給模型實驗結果的平均絕對百分比誤差（MAPE）都明顯低于公認界值10，表明該模型可以使用。

平均絕對百分比誤差MAPE：即若有N個樣本數據，預測對象的第m個實際值記作Ym，由模型得到的相應值為 ，則

一般認為，若MAPE小于10，則模型精度較高。

利用模型對實際 的時間數據進行計算，得到新時段內（ ）出現的波動序列 ，將其各波動值劃分到導出背景的閾值區間中后，得到新序列 ，用該序列逐個匹配挖掘所得到的全部規則前驅，如果 ，則序列 具有該條規則，該規則前驅的后續時間可能出現的波動，便如其規則后繼所表示。

3 時序關聯規則的挖掘

定義1：當 ，則形式背景（O，A1，R），（O，A2，R），...，（O，Al，R）為（O，A，R）的片段形式背景，各背景所對應的概念格L（O，A1，R），L（O，A2，R），...，L（O，Al，R）為L（O，A，R）的片段概念格，其中|A1|，|A2|，...，|Al|對應為各片段的長度 。

兩個片段概念格L（O，Ai，R），L（O，Aj，R）所對應的概念集分別為Li，Lj。若Li中的任一概念為（Xi，Yi）；Lj中的任一概念為（Xj，Yj），則概念內涵關聯規則 的支持度的定義為 為支持度計數，置信度定義為

對某一長度為n的序列按前面給出的預處理方法進行處理后，將其進一步做分段處理，即將波動序列{ }按照步長L進行分段，時間分段區間定義為 ，其中 為分段號的集合。以分段號K為對象集合；每個分段內各個序列項所對應的{1，2，...，L}順序時間位置作為多值屬性集合；各序列項值作為屬性值集合，建立多值形式背景。對其屬性按波動幅度進行標準化劃分后，給出每個屬性劃分對應的閾值區間，將屬性的屬性值影射到各自的閾值區間中，得到導出背景，根據現實不同時間序列的實際特性（如小時、季度等）和人們的實際需要來定義各片段的長度 ，最后得到各片段的導出背景，表1為某個時間序列的片段導出背景的舉例。例中的屬性集{1，2，3}為整體屬性集{1，2，...，L}的一個子集。其片段長度為3，{1991，1992，...，2006}為該例整體的對象集。

在各片段導出背景間進行關聯規則挖掘時，對每個片段上進行概念格的建立以及片段內的剪枝處理，這樣減少了對數據的挖掘時間。片段內的剪枝處理是指依照最小支持度，將各片段概念格所對應的概念集合中小于最小支持度計數的概念刪除，即刪除概念外延包含的屬性個數小于最小支持度計數的概念，這樣做有效的減少了后續挖掘的數據量。

算法描述如下：

輸入：導出背景（O，A，R），最小支持計數Z，各片段的長度

輸出：格間關聯規則集合

⑴按各片段長度將（O，A，R）劃分為有序的片段背景（O，A1，R），（O，A2，R），（O，Al，R）；

⑵對片段個數進行計數，

⑶對每個片段背景執行4到5；

⑷建立概念格，生成各自的概念集合H；

⑸for（g=1；g<=count（H）；g++）

{對于處理器上概念集中第g個概念H（X，Y）g的外延與內涵H（X）g與H（Y）g

if（count（H（X）g）

刪除該概念H（X，Y）g}

⑹在任意兩個處理器Pi，Pj（i

c=count（Hi）；d=count（Hj）；

for（k=1；k<=c；k++）

for（r=1；r<=d；r++）

{對于概念集合Hi中第k個概念Hi（Xi，Yi）k的外延與內涵Hi（Xi）k、Hi（Yi）k以及概念集合Hj中第r個概念Hj（Xj，Yj）r的外延與內涵

if（count（Hi（Xi）k∩Hj（Xj）r）>=Z）

輸出Hi（Yi）k=>Hj（Yj）r；}

因為規則中“ ”兩端出現的是有序的短周期，所以這里將“ ”左端項稱為該規則的前驅，右端項稱為該規則的后繼。

文中在計算新時段內發生序列的波動時，給出了一個具有較高精度的模型，該模型可以提高了預測質量；隨后在挖掘序列波動規則的過程中，提出了對片段多值背景生成時序關聯規則的算法。最后借助規則匹配，完成了對未來序列波動情況的精確預知。

[參考文獻]

[1]Like Gao，and Xiaoyang Sean Wang.Continuous Similarity-Based Queries on Streaming Time Series，IEEE Transactions on Knowledge and Data Engineering.2005，17（10），1320-1332.

[2]簡宋全，胡學鋼，蔣美華.擴展概念格的漸進式構造.計算機工程與應用.2001，15：132-134.

[3]趙文兵，簡宋全，王浩，等.約簡概念格的縱向維護算法.計算機工程與應用.2002，7：209-211.

[4]張意德，簡宋全，趙文兵，等.相對約簡格及其構造.計算機工程與應用.2002，6：196-197，239.