數(shù)據(jù)挖掘中的序列模式

數(shù)據(jù)挖掘的任務(wù)是從數(shù)據(jù)中發(fā)現(xiàn)模式，模式時(shí)空一個(gè)用語言L來表示的一個(gè)表達(dá)式E，它可用來描述數(shù)據(jù)集F中數(shù)據(jù)的特性，E所描述的數(shù)據(jù)時(shí)機(jī)和F的一個(gè)子集FE。E作為一個(gè)模式要求它比數(shù)據(jù)子集FE中所有元素的描述方法簡單，在實(shí)際應(yīng)用中，往往根據(jù)模式的實(shí)際作用細(xì)分為分類模式、回歸模式、時(shí)間序列模式、聚類模式、關(guān)聯(lián)模式和序列模式6種。給定一個(gè)由客戶交易之城的數(shù)據(jù)庫DB，挖掘序列模式的問題就是在那些具有客戶指定最小支持度（minimum support）的序列中找出最大序列（maximal sequence），而每個(gè)這樣的最大序列就代表了一個(gè)序列模式（sequence pattern）

一、序列模式挖掘參數(shù)

1.時(shí)間序列T的時(shí)間長度

可以講數(shù)據(jù)庫中的整個(gè)序列或用戶所選擇的序列（如2003你那）作為時(shí)間序列的長度，序列模式（挖掘）將僅限于在之一序列長度之內(nèi)進(jìn)行。

2.時(shí)間窗口W

一系列在時(shí)間內(nèi)發(fā)生的事件在特定的分析中可以看成是一起發(fā)生的。如果一個(gè)時(shí)間窗口W唄設(shè)置為同序列T一樣長，那就會(huì)發(fā)現(xiàn)對時(shí)間不敏感的頻繁模式，也就是基本關(guān)聯(lián)模式。如：“2000年，一個(gè)購買電腦的顧客也買了數(shù)碼相機(jī)”其中不再關(guān)系哪個(gè)先買哪個(gè)后買）；若一個(gè)事件窗口W被設(shè)置為0，那就會(huì)發(fā)現(xiàn)一個(gè)序列事件是作為單個(gè)時(shí)間發(fā)生（來處理的）如：“一個(gè)顧客購買了電腦，然后又購買了內(nèi)存，最后悔購買CD-ROM”。若一個(gè)事件窗口W被設(shè)置為上述兩者之間的某個(gè)值（即0與T總長度之間），如：若W設(shè)為一個(gè)月，那么在同一月發(fā)生的交易事務(wù)，將被認(rèn)為是同一時(shí)間發(fā)生的，而被合在一起進(jìn)行分析。

3.發(fā)現(xiàn)模式中事件發(fā)生的時(shí)間間隔int。

若將int設(shè)為0，就意味著沒有間隔，也就是發(fā)現(xiàn)嚴(yán)格連續(xù)時(shí)間序列。這里也可以將參數(shù)W考慮進(jìn)來。若W設(shè)為一周，也就是要發(fā)現(xiàn)連續(xù)各周頻繁模式。DNA分析經(jīng)常需要發(fā)現(xiàn)無間隔的連續(xù)序列。而min_interval int大多挖掘頻繁序列模式的研究都是針對不同的參數(shù)設(shè)置，以及采用Aprior啟發(fā)知識(shí)和與Apriori類似。但做了相應(yīng)改動(dòng)的挖掘方法。

二、序列模式發(fā)現(xiàn)算法

1.基于Apriori性質(zhì)的逐層發(fā)現(xiàn)方法

Apriori性質(zhì)是指頻繁項(xiàng)集的所有非空子集必須也是頻繁的。即在交易數(shù)據(jù)庫中，如果某一長度為K的序列不是頻繁的，那么它的任何長度為k+1的超序列也不可能是頻繁的。這種基于Apriori[8]性質(zhì)的逐層搜索的迭代方法，主要包括AprioriAll算法和GSP算法等。此類算法的思想是在已經(jīng)生成頻繁序列中搜尋更長的頻繁序列，并在此過程中對待檢查的序列集進(jìn)行有效的修建。

（1）AprioriAll算法。AprioriAll算法將序列模式發(fā)現(xiàn)的過程分為以下五個(gè)階段：排序階段：數(shù)據(jù)庫中的元組按照“顧客號(hào)”為主鍵，“交易時(shí)間”為次主鍵排序。頻繁項(xiàng)集發(fā)現(xiàn)階段：用頻繁集合發(fā)現(xiàn)算法，求出所有頻繁項(xiàng)集，以滅個(gè)頻繁項(xiàng)集為唯一元素的序列即為頻繁1-序列。轉(zhuǎn)化階段：每個(gè)事務(wù)被該事務(wù)中所有頻繁項(xiàng)集所替代，經(jīng)過轉(zhuǎn)化，事務(wù)序列唄表示成由頻繁項(xiàng)集的集合構(gòu)成的有序表。序列階段：這是算法的主要階段。在算法執(zhí)行中，需要多趟掃描原序列數(shù)據(jù)庫。最大序列階段：從頻繁序列中找出最大序列，在實(shí)現(xiàn)上，這一階段可以與上一階段合并。

（2）GSP算法?；镜男蛄心Ｊ侥Ｐ脱芯康氖窃谕蛔侄紊系男蛄心Ｊ郊磫尉S的序列模式。實(shí)踐應(yīng)用中的數(shù)據(jù)集是一個(gè)多維的空間?；拘蛄心Ｐ痛嬖谌鄙贂r(shí)間約束、對交易的定義死板、缺少分類層次等局限，因此為客服上述局限文獻(xiàn)7的作者將序列模式的基本模型進(jìn)行了擴(kuò)展，加入了時(shí)間約束、滑動(dòng)窗口和分類層次，提出了泛化序列模式發(fā)現(xiàn)問題并給出了相應(yīng)的GSP算法。GSP算法是一個(gè)迭代的過程，在每一次迭代中，首先生成候選序列，然后掃描序列數(shù)據(jù)庫計(jì)算候選序列的支持度以確定頻繁徐立。其中候選序列的生成階段包括連接階段和修剪階段。

2.基于序列模式增長的發(fā)現(xiàn)方法

基于序列模式增長（sequential patterns growth）方法，包括FreeSpan，PrefixSpan算法等。這類方法采取了一種分而治之（devide-and-conquer）的思想，挖掘過程中無需生成候選序列。其主要特征有：算法不生成大量的候選序列，而是以某種壓縮的形式保留了原數(shù)據(jù)庫的基本的數(shù)據(jù)分組。隨后的分析可以聚焦于計(jì)算相關(guān)數(shù)據(jù)集而非候選序列的頻率。算法的每一次迭代不是掃描完整的原數(shù)據(jù)庫來匹配相應(yīng)的全部候選序列，而是通過數(shù)據(jù)庫投影來對將要檢查的數(shù)據(jù)集和序列模式進(jìn)行劃分，這樣分而治之的方法將減小搜索空間，提高算法性能。FreeSpan算法是在基于任何頻繁子序列對數(shù)據(jù)庫投影，并在子序列的任何位置上增長；而PrefixSpan算法僅僅基于頻繁前綴子序列投影并通過在其后添加后綴來實(shí)現(xiàn)序列的增長。PrefixSpan算法因包含更少的投影庫和子序列連接而比FreeSpan算法性能更優(yōu)。

本文主要講述了序列模式的挖掘問題，并對序列模式挖掘的經(jīng)典算法進(jìn)行描述。肅立惡魔是與管理模式相仿，只不過把數(shù)據(jù)之間的關(guān)聯(lián)性與時(shí)間聯(lián)系起來。為了發(fā)現(xiàn)序列模式，不僅需要知道事件是否發(fā)生，而且需要確定事件發(fā)生的時(shí)間。由此看出，序列模式挖掘是很有價(jià)值的，他在網(wǎng)絡(luò)通信、氣象分析、商業(yè)零售、金融證劵等領(lǐng)域有廣闊的應(yīng)用前景。同時(shí)對于一般的大型數(shù)據(jù)庫，序列模式挖掘算法的時(shí)空開銷往往都很大，這就要求我們在經(jīng)典算法的基礎(chǔ)上設(shè)計(jì)出高校挖掘算法。

作者簡介：

孫冬梅（（1978—），女，長春市房產(chǎn)檔案館，學(xué)士，研究方向：人工智能。

（作者單位：長春市房產(chǎn)檔案館）