基于ＩＲＳＴ的并行時序模式挖掘算法

摘要：提出一種建立在集群式高性能計算機上基于互關聯后繼樹的并行時序模式挖掘算法，將數據線段化、樹的建立及模式發現在多處理機上進行并行處理，有效地改進了算法的執行效率。實驗結果表明，此算法較之串行算法有較高的效率。

關鍵詞：互關聯后繼樹；時間序列；時序模式；并行計算

中圖分類號：TP391文獻標志碼：A

文章編號：1001-3695(2007)12-0137-04

0引言

在數據挖掘中，時序模式挖掘是近年來研究的熱門課題之一。時序模式挖掘就是利用數據挖掘技術從大量時序數據中發現頻繁出現的有用模式(簡稱時序模式)的一種時間序列分析方法。IRST模型^[1]是胡運發提出的一種全文檢索模型。基于這種模型的時序模式挖掘算法^[2，3]避免了Apriori算法的缺陷，避免了在挖掘過程中產生大量的候選模式，有效地提高了挖掘效率。但是，在對海量數據進行挖掘時，隨著內存支持和I/O開銷的增長，算法的效率也受到嚴重影響，單機處理遠遠滿足不了需要。

針對以上問題，本文提出一種并行數據挖掘算法——基于IRST的并行時序模式挖掘算法。該算法是以曾海泉等人^[2]提出的算法為基礎，首先將數據交疊進行劃分，在各個節點上根據不同時間序列的特點選擇合適的序列劃分算法，將序列分段成線性變化的時序片斷，引入絕對斜率并結合領域知識將線性變化的時序片段符號化；然后去除各節點上的冗余片斷，在此基礎上對各節點上的時序片斷建立互關聯后繼樹；之后將各節點上的互關聯后繼樹合并，并將合并后的樹發到各個節點上，根據符號的種類個數在各節點分別發現以某些字符開頭的頻繁模式。

7結束語

如何在時序數據庫中高效地挖掘出具有實用價值的頻繁模式是一項重要的具有實際意義的課題，為此本文實現了一種并行的模式挖掘算法。與其他方法相比，其具有以下優點：

a）采取了基于交疊數據分區的并行數據分割方法，既保留了時間序列的特征，又提高了劃分效率。

b）提出了并行建立互關聯后繼樹的方法。

c）對挖掘任務進行均等劃分，實現頻繁模式的并行挖掘，大大提高了挖掘效率。

通過實驗對比，改進后的算法大大提高了效率。然而，此算法在發現模式時，針對長度差別不大而相似的序列卻無能為力，而這些模式的發現有時卻是非常重要的。今后筆者會在此算法基礎上對每種類型的線段按照其長度進行聚類，以期能發現代表某類相似序列的實用的頻繁模式。

參考文獻：

［1］胡運發．互關聯后繼樹——一種新型全文數據庫數學模型，CIT-02-03[R]．上海：復旦大學，2002.

[2]曾海泉，胡勤友，周水庚，等.基于互關聯后繼樹的時序模式挖掘[J].模式識別與人工智能，2003，16(3):934-940.

[3]申展，江寶林，唐磊，等.基于互關聯后繼樹的頻繁模式挖掘研究[J].計算機工程，2004，30(21):30-32.

[4]STOLORZ P，MUSICK R. Scalable high performance computing forknowledge discovery and data mining[M].[S.l.]:Kluwer Academic Publishers， 1997.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”