年企业管理学术研讨会暨

2003年企業管理學術研討會暨2003年電子商務經營管理研討會快速序列拆解演算法(FastSequenceDecompositionAlgorithm)黃仁鵬南台科技大學資訊管理所副教授[e-mail]許耀文南台科技大學資訊管理所研究生[e-mail]郭煌政國立嘉義大學資訊工程學系助理教授[e-mail]摘要序列型樣(SequentialPattern)的挖掘在資料探勘(Datamining)中是逐漸受到重視的研究領域，最主要原因是它能挖掘出在不同時間下，各個序列出現的重複性，以預測出未來當該序列中的前幾個元素出現時，可以預先得知後面接著出現的元素。而這樣的特性就可以應用在很多方面，以買賣業的交易分析中來說，把序列中的元素表示成不同商品，接著依每個顧客購買商品時間先後所形成的交易序列來做探勘，結果所得之資訊可說是非常有用的，因為這樣即可預先得知顧客消費行為，並對該顧客做「目標行銷」，這樣一來，也可進一步的先為未來的產品開發方向做一規畫，以成為市場中的領先者。而本論文即是提出一新的「快速序列拆解(FastSequenceDecomposition)」演算法(以下皆以FSD簡稱)，其優點如下：1.只需掃描資料庫一次。2.減少大量候選序列的產生，藉著以上這些特點，讓使用者能快速得到序列型樣，以獲得最大的經濟效益，達到使用者和消費者雙贏的局面。關鍵字：序列型樣、資料探勘、目標行銷1.緒論資料探勘[1][2][3][6]（DataMining）是一個從資料庫中挖掘出先前未知、或是隱藏的有用資訊的過程[7]。這個領域的研究主要可區分為描述與辨別(CharacterizationandDiscrimination)、關聯法則(AssociationAnalysis)、預測與分類(ClassificationandPrediction)、叢集分析(ClusterAnalysis)、異常分析(OutlierAnalysis)及趨勢分析(EvolutionAnalysis)等六類。由於現行的資料庫普遍都存有大量的交易資料，如何以自動化的方式從中找出有用的資訊，就成為一個相當重要的課題，也因此，資料探勘即成為一個愈來愈重要的研究領域。而資料探勘中以「關聯法則(AssociationRule)」為比較為人所知的研究，它主要是探勘出資料之間的關聯性，例如，如果A出現然後B也會跟著出現這樣的一個關係，且都只有資料庫中具有足夠代表性的那些規則才會被產生，但在各種不同來源的資料中，有些資料卻是有循序(Sequential)的特性存在，例如，買A商品後，過一段時間後會在買B商品的這樣一個有時間先後關係存在，而一樣地，如果其序列在資料庫中出現的頻繁很高，也就是大於等於所設定的最小支持度，那就可稱之為一個「序列型樣(SequentialPattern)」。但在做關聯法則時，並不會有如序列型樣的這樣資訊產生，如此一來，可能會失去一些有用的資訊，所以近年來，對於這方面的研究也引起了大家的興趣，而積極地的投入相關研究。而本研究即是以趨勢分析中的「序列型樣」為研究的主題，序列型樣的挖掘，最初是由Agrawal&Srikant等人在1995所提出[8]，主要的目的是要從順序性的資料中找出樣式，像「顧客在購買房子後，會再購買傢俱，且之後也會再買電視」即是一個典型的序列樣式。在此一類型的資料挖掘中，其資料的每個項目（item）都具有一個順序性；也就是以一個用以決定項目順序的衡量方式，如交易時間，將所有的項目呈順序性的排列。而序列型樣的挖掘，也就是從一群序列紀錄中，去找出一些出現頻率超過某一設定比率的子序列，而這些尋出的子序列，即是所謂的序列型樣。而透過這些尋出的序列型樣，我們即可以對顧客的購2003年企業管理學術研討會暨2003年電子商務經營管理研討會買行為、或是使用者對網站的瀏覽模式進行分析，以進行促銷或是網站調整等活動。目前以序列型樣所發展出來的有AproiriAll[8]、AprioriSome[8]、DynamicSome[8]、FreeSpan[4]、PrefixSpan[5]等演算法。而本論文架構則為如下所示述，第二章相關文獻探討，是提出問題的定義和相關的演算法；第三章研究架構，說明本論文的研究架構；第四章研究方法，則是提出新的演算法-FSD，並闡述拆解的方式，以求得序列型樣；第五章演算法實例分析，提出FSD演算法的實例拆解過程與結果；最後第六章提出結論。2.相關文獻探討在這一章，除了介紹序列型樣的問題定義之外，接者也描述相關性的演算法，藉此了解本文所提出演算法的一些參考依據。2.1問題定義[9]Agrawal&Srikant等人在1995年即最早將此類問題作出定義，首先I={i1,i2,…,in}為所有項目(Items)的集合，項目組X便是I的子集，即XI。一個序列(Sequence)則是項目組的有序序列(OrderedList)，即是將項目組按照時間先後順序排列。假設一個序列s可表示成s1s2....sn的形式，則其中sj代表一個項目組，其中對於每一個j(1jn)而言，sjI，是為項目的實例(Instanceofitem)，另外sj也可稱為是序列的一個元素(Element)，可表示成x1x2....xm，其中xk為一個項目，xkI，而且1km。換言之，一個序列可含有許多的元素，而一個元素就是項目的集合。舉例來說，(be)c(bdf)即代表為一個序列，(be)、c、(bdf)分別為三個「元素一」的項目組，其中(be)元素含有b、e兩個項目，(bdf)元素含有b、d、f三個項目，c元素因為只有一個項目c，在這裡可將()號省略，而如序列中的(be)c、c(bdf)或(be)(bdf)等則稱為「元素二」的項目組，依此類推。另外，一個項目最多只能在一個元素裡出現一次，但是卻可以重複出現在許多不同的元素中。以上例來說，b項目在第一及第三個元素中分別只會出現一次。序列的長度是指在序列裡所包含的項目個數，若長度為l的序列則稱之為l-序列(l-sequence)，如(be)c(bdf)共包含有6個項目，因此此序列為6-序列。假設兩序列A=a1,a2,…,al和B=b1,b2,…,bh，若存在著一個整數(i1,i2,…ih)，且i1＜i2＜…＜ih，使得對所有j(1jh)而言，bj=aij，則B為A的子序列(Sub-sequence)，相對地，A就為B的超序列(Super-sequence)，例如，序列(3)(4,5)(8)為(7)(3,8)(9)(4,5,6)(8)的子序列，因為(3)(3,8)，(4,5)(4,5,6)，(8)(8)，所以序列(3)(4,5)(8)包含於(7)(3,8)(9)(4,5,6)(8)的序列中。一個序列資料庫(SequenceDatabase,S)的綱要可以表示(sid,s)，其中sid表示其序列的識別代碼，而s則是代表其序列本身。各個(sid,s)的集合，構成了序列資料庫S，至於在序列資料庫中包含序列的數量，即稱為該序列的支持度，其式子為support_countS()={(sid,s)(sid,s)Siscontainedins}，如果的支持度大於或等於所定義的最小支持度時，則是一個大序列(LargeSequence)，或稱頻繁序列(FrequentSequence)，，而若某個大序列不被包含在其他序列中，則稱為最大的大序列(MaximalLargeSequence)，也就是一個序列型樣(SequentialPattern)。2.2相關演算法AprioriAll演算法[8]此演算法在概念上和探勘關聯規則的Apriori演算法類似，皆是逐層式產生候選序列，接著逐一計算每個候選序列的支持度，如果符合，就產生頻繁序列(FrequentSequence)，如此重覆以上動作，直到不能產生候選序列為止，但此演算法也同樣延續Apriori的缺點，即是多次掃描資料庫且產生大量的候選序列，因此，此演算法是相當花費時間和空間的。QDT演算法[10]此演算法只需掃描資料庫一次，主要利用拆解(Decomposition)方式來分解交易紀錄，將結果存入分解表(DecomposeTable;DT)中，每次拆解完一筆交易紀錄之後，予以紀錄每個項目集合之支持度，最後透過所拆解出的頻繁項目集之支持度總2003年企業管理學術研討會暨2003年電子商務經營管理研討會合，檢測是否通過最小信賴度門檻值來產生關聯規則。QDT演算法執行速度平均比Apriori演算法約快15倍，大幅地提升執行效能。所以本論文所提出的一新的演算法-FSD，即是為了改善AprioriAll缺點，並加上QDT演算法拆解方式的概念而發展出來的，期能加速處理的效能，以產生最後的序列型樣。3.研究架構圖1演算法流程圖FSD演算法的流程圖說明如下：Step1：讀取序列資料庫中顧客購買商品的交易序列。Step2：針對此序列進行“拆解”動作，也就是先把序列中有同時購買的項目集做拆解並分別放入原來此項目集的位置上，接著再做這些候選序列的拆解。Step3：先將拆解出來的候選序列做一處理，也就是如遇有重複的情形發生時，還是只計算一次，因為都是來自於相同的原始序列。Step4：判斷拆解出來的這些候選序列是否存在於拆解表格中，“沒有”就執行第五步驟，“有”就執行第六步驟。Step5：將該候選序列新增於拆解表格中，並給予初值1。Step6：將拆解表格中該候選序列的值加1。Step7：判斷資料庫中是否還有交易序列，“有”的話就重覆第一步驟，“沒有”的話，則執行第八步驟。Step8：從拆解表格中，取出符合最小支持度的所有頻繁序列。Step9：從Step8所得之結果中產生序列型樣。4.研究方法FSD演算法的特性在於只要掃描資料庫一次即可拆解出所有的候選序列，進一步得到頻繁序列以求得序列型樣。如此，就可以加速執行的效率。在拆解過程先對序列中同時購買商品的項目組做拆解，並將這些子項目視為單一個元素且分別放入當初此項目組所在的位置上做結合，之後，再拆解出所有的候選序列。假設結合後的候選序列有k個元素，於是先拆解出由左至右(序列有時間先後上的排列順序)且相同的項目不可出現在同一元素中，但可以出現在不同元素中的k-1個元素的候選序列，然後再從這些k-1個元素中依照相同方法做拆解，一直做到k-(k-1)個元素才結束該序列的拆解動作。但在做拆解時，如有同一個候選序列的產生，則此候選序列因為出自相同的序列，所以在計算上還是只算一次，最後把這些拆解出來的候選序列全部在拆解表格中記錄下來，並給予初始值1，再把其他所有的序列給拆解完成以求得所有候選序列的支持度，則可求得最後的序列型樣。以「元素四」的序列214(21)為例，先把(21)項目組，也就是同時購買商品2和商品1的這個項目組做拆解，所以得到1、2、21等三種子項目，接著把這三種組合視為三個單一元素，並分別放入當初該項目組所在位置上做結合，結果形成了三個「元素四」的候選序列：2141、2142、214(21)，再分別把這三個候選序列做拆解，從2003年企業管理學術研討會暨2003年電子商務經營管理研討會2141開始拆解，結果得到214、211、241、141等四個「元素三」的候選序列，然後再把這四個繼續往下做拆解。214經拆解得到表1的三個「元素二」的候選序列：表1212414211經拆解得到二個「元素二」的候選序列：表22111241經拆解得到三個「元素二」的候選序列：表3242141141經拆解得到二個元素二的候選序列：表41411而因為這些候選序列皆出自同一個原始序列214(21)，所以，拆解後會產生重複的候選序列，例如表1與表2中的24、21重複，皆只計算一次，依此類推。「元素二」的候選序