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

摘要：提出一種建立在集群式高性能計(jì)算機(jī)上基于互關(guān)聯(lián)后繼樹的并行時(shí)序模式挖掘算法，將數(shù)據(jù)線段化、樹的建立及模式發(fā)現(xiàn)在多處理機(jī)上進(jìn)行并行處理，有效地改進(jìn)了算法的執(zhí)行效率。實(shí)驗(yàn)結(jié)果表明，此算法較之串行算法有較高的效率。

關(guān)鍵詞：互關(guān)聯(lián)后繼樹；時(shí)間序列；時(shí)序模式；并行計(jì)算

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)志碼：A

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

0引言

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

針對(duì)以上問題，本文提出一種并行數(shù)據(jù)挖掘算法——基于IRST的并行時(shí)序模式挖掘算法。該算法是以曾海泉等人^[2]提出的算法為基礎(chǔ)，首先將數(shù)據(jù)交疊進(jìn)行劃分，在各個(gè)節(jié)點(diǎn)上根據(jù)不同時(shí)間序列的特點(diǎn)選擇合適的序列劃分算法，將序列分段成線性變化的時(shí)序片斷，引入絕對(duì)斜率并結(jié)合領(lǐng)域知識(shí)將線性變化的時(shí)序片段符號(hào)化；然后去除各節(jié)點(diǎn)上的冗余片斷，在此基礎(chǔ)上對(duì)各節(jié)點(diǎn)上的時(shí)序片斷建立互關(guān)聯(lián)后繼樹；之后將各節(jié)點(diǎn)上的互關(guān)聯(lián)后繼樹合并，并將合并后的樹發(fā)到各個(gè)節(jié)點(diǎn)上，根據(jù)符號(hào)的種類個(gè)數(shù)在各節(jié)點(diǎn)分別發(fā)現(xiàn)以某些字符開頭的頻繁模式。

7結(jié)束語(yǔ)

如何在時(shí)序數(shù)據(jù)庫(kù)中高效地挖掘出具有實(shí)用價(jià)值的頻繁模式是一項(xiàng)重要的具有實(shí)際意義的課題，為此本文實(shí)現(xiàn)了一種并行的模式挖掘算法。與其他方法相比，其具有以下優(yōu)點(diǎn)：

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

b）提出了并行建立互關(guān)聯(lián)后繼樹的方法。

c）對(duì)挖掘任務(wù)進(jìn)行均等劃分，實(shí)現(xiàn)頻繁模式的并行挖掘，大大提高了挖掘效率。

通過實(shí)驗(yàn)對(duì)比，改進(jìn)后的算法大大提高了效率。然而，此算法在發(fā)現(xiàn)模式時(shí)，針對(duì)長(zhǎng)度差別不大而相似的序列卻無(wú)能為力，而這些模式的發(fā)現(xiàn)有時(shí)卻是非常重要的。今后筆者會(huì)在此算法基礎(chǔ)上對(duì)每種類型的線段按照其長(zhǎng)度進(jìn)行聚類，以期能發(fā)現(xiàn)代表某類相似序列的實(shí)用的頻繁模式。

參考文獻(xiàn)：

［1］胡運(yùn)發(fā)．互關(guān)聯(lián)后繼樹——一種新型全文數(shù)據(jù)庫(kù)數(shù)學(xué)模型，CIT-02-03[R]．上海：復(fù)旦大學(xué)，2002.

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

[3]申展，江寶林，唐磊，等.基于互關(guān)聯(lián)后繼樹的頻繁模式挖掘研究[J].計(jì)算機(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.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”