1、第十一章 序列模式挖掘一、序列模式的概念及定義舉例說(shuō)明，比如有顧客租借錄像帶，典型的順序是先租“星球大戰(zhàn)”，然后是“帝國(guó)反擊戰(zhàn)”，再是“杰達(dá)武士歸來(lái)”(這三部影片是以故事發(fā)生的時(shí)間先后而情節(jié)連續(xù)的)。值得注意的是租借這三部電影的行為并不一定需要是連續(xù)的。在任意兩部之間隨便插租了什么電影，仍然還是滿足了這個(gè)序列模式，并且擴(kuò)展一下，序列模式的元素也可以不只是一個(gè)元素(如一部電影)，它也可以是一個(gè)項(xiàng)集(item set)。項(xiàng)集，指的是多個(gè)物品組成的集合，內(nèi)部元素不分排列順序，比如“枕頭和枕頭套”就可以看作是由兩個(gè)項(xiàng)(item)組成的項(xiàng)集，它也可以作為某一個(gè)序列模式的元素。相關(guān)概念及定義 以商品交易為

2、例子，數(shù)據(jù)源是一個(gè)給定的由客戶交易組成的大型數(shù)據(jù)庫(kù)，每個(gè)交易由客戶號(hào)(customer-id)，交易時(shí)間以及在交易中購(gòu)買(mǎi)的項(xiàng)組成。項(xiàng)集(itemset):由項(xiàng)(item)組成的一個(gè)非空集合。序列(sequence):是一列排好序的項(xiàng)集。不失一般性假定項(xiàng)集中的項(xiàng)由一些連續(xù)整數(shù)代替，這樣一個(gè)項(xiàng)集i可以表示為(i1,i2im)，而這里的ij代表了一個(gè)項(xiàng)。一個(gè)序列s可以表示為，這里的sj代表的是一個(gè)項(xiàng)集。相關(guān)概念及定義最大序列 兩個(gè)序列A= 和B= ，如果存在整數(shù)i1i2in且a1包含于bi1，a2包含于bi2，an包含于bin，則稱序列a包含于序列b。在一個(gè)序列集中如果序列s不包含于任何其它序列中，

3、則稱序列s為最大的。 比如序列包含于序列，因?yàn)?3)包含于(3,8)，(4,5)包含于(4,5,6)以及(8)包含于(8)。但是序列不包含于，反之亦然。前者表示項(xiàng)3和項(xiàng)5是先后購(gòu)買(mǎi)的，而后者則表示項(xiàng)3和項(xiàng)5是同時(shí)購(gòu)買(mǎi)的，這就是區(qū)別所在。相關(guān)概念及定義客戶序列一個(gè)數(shù)據(jù)庫(kù)中的交易記錄可以表示成上表 一個(gè)客戶所有的事務(wù)可以綜合的看成是一個(gè)序列，每一個(gè)事務(wù)都由相應(yīng)的一個(gè)項(xiàng)集來(lái)表示。事務(wù)按交易時(shí)間序排列成一個(gè)序列。稱這樣的序列為客戶序列。通常，將一個(gè)客戶的交易按交易時(shí)間排序成T1 ，T2 ，Tn。Ti中的項(xiàng)集定義成itemset(Ti)。這樣，這個(gè)客戶的客戶序列成了這樣的一個(gè)序列：itemset(T1)

4、 itemset(T2) itemset(Tn)。 客戶號(hào)物品(Item)時(shí)間1309002.10.2502.10.30210,203040,60,7002.10.1002.10.1502.10.20330,50,7002.10.2559002.10.1243040,709002.10.1102.10.2502.10.30交易號(hào)客戶購(gòu)物序列1(30),(90)2(10,20),(30),(40,60,70)3(30,50,70)4(30)(40,70)(90)5(90)相關(guān)概念及定義序列模式如果一個(gè)序列s包含于一個(gè)客戶序列中，則稱該客戶支持序列s。一個(gè)序列的支持度定義為支持該序列的客戶總數(shù)。給

5、定一個(gè)由客戶交易組成的數(shù)據(jù)庫(kù)D，挖掘序列模式的問(wèn)題是：在那些具有客戶指定最小支持度的序列中找出最大序列。而這樣的最大序列就代表了一個(gè)序列模式。示例對(duì)于最小支持?jǐn)?shù)為2的情況，有兩個(gè)序列： 和 在那些滿足支持度約束的序列中是最大的，也是我們所需的序列模式。交易號(hào)客戶購(gòu)物序列1(30),(90)2(10,20),(30),(40,60,70)3(30,50,70)4(30)(40,70)(90)5(90)序列挖掘算法步驟 1) 排序階段。數(shù)據(jù)庫(kù)D以客戶號(hào)為主鍵，交易時(shí)間為次鍵進(jìn)行排序。這個(gè)階段將原來(lái)的事務(wù)數(shù)據(jù)庫(kù)轉(zhuǎn)換成由客戶序列組成的數(shù)據(jù)庫(kù)。 2) 頻繁項(xiàng)集階段。找出所有頻繁項(xiàng)集組成的集合L。也同步得

6、到所有頻繁1-序列組成的集合。 3) 轉(zhuǎn)換階段。在找序列模式的過(guò)程中，要不斷地進(jìn)行檢測(cè)一個(gè)給定的頻繁集是否包含于一個(gè)客戶序列中。 4) 序列階段利用已知的頻繁集的集合來(lái)找到所需的序列。類(lèi)似于關(guān)聯(lián)的Apriori算法。算法示例1) 在給出的數(shù)據(jù)庫(kù)中，找出所有頻繁1-序列組成的集合： 和 2) 給一個(gè)可行的映射。交易號(hào)客戶購(gòu)物序列1(30),(90)2(10,20),(30),(40,60,70)3(30,50,70)4(30)(40,70)(90)5(90)頻繁項(xiàng)集映射成（30）1（40）2（70）3（40,70）4（90）5好處：將頻繁集按一個(gè)實(shí)體的形式進(jìn)行處理，可以帶來(lái)比較和處理上的方便和高

7、效，提供了一個(gè)統(tǒng)一的格式。(30)(40)(70)(90)(40,70)算法示例3)轉(zhuǎn)換。為了使這個(gè)過(guò)程盡量的快，用另一種形式來(lái)替換每一個(gè)客戶序列。在轉(zhuǎn)換完成的客戶序列中，每條交易被其所包含的所有頻繁項(xiàng)集所取代。如果一條交易不包含任何頻繁集，在轉(zhuǎn)換完成的序列中它將不被保留。如果一個(gè)客戶序列不包含任何的頻繁項(xiàng)集，在轉(zhuǎn)換好的數(shù)據(jù)庫(kù)中這個(gè)序列也將不復(fù)存在。一個(gè)客戶序列被一列由頻繁集組成的集合所取代，每個(gè)頻繁集的集合表示為l1,l2,ln，l i表示一個(gè)頻繁集。交易號(hào)客戶購(gòu)物序列1(30),(90)2(10,20),(30),(40,60,70)3(30,50,70)4(30)(40,70)(90)5

8、(90)頻繁項(xiàng)集映射成（30）1（40）2（70）3（40，70）4（90）5交易號(hào)客戶購(gòu)物序列1(30),(90)2(10,20),(30),(40,60,70)3(30,50,70)4(30)(40,70)(90)5(90)頻繁項(xiàng)集映射成(30)(90)1,5(30)(40)(70)(40,70)1,2,3,4(30)(70)1,3(30)(40)(70)(40,70)(90)12,3,45(90)5算法示例算法示例例：考察右圖所示的一個(gè)客戶序列組成的數(shù)據(jù)庫(kù)，假定客戶序列已經(jīng)以轉(zhuǎn)換的形式出現(xiàn)了，每一條交易都被包含其中的頻繁項(xiàng)集取代，頻繁項(xiàng)集則由整數(shù)代替。最小支持?jǐn)?shù)據(jù)定義為2。算法示例1_項(xiàng)集支持度142234445422_項(xiàng)集支持度243323223_項(xiàng)集支持度223224_項(xiàng)集支持度4下次遍歷不好會(huì)產(chǎn)生候選，最大序列是以下三個(gè)：,和。結(jié)束語(yǔ)數(shù)據(jù)挖掘涉及的是多學(xué)科的領(lǐng)域，涉及數(shù)據(jù)庫(kù)技術(shù)、人工智能、機(jī)器