帶興趣度的序列概念格的最大模式挖掘(圖文)

1、帶興趣度的序列概念格的最大模式挖掘(圖文)論文導(dǎo)讀：1.引言序列模式挖掘【1】是數(shù)據(jù)挖掘領(lǐng)域中重要的研究分支而頻繁工程集求解是序列模式挖掘的根底和前提。傳統(tǒng)的序列模式挖掘算法如AprioriAll算法【2】、GSP算法【3】、SPADE算法【4】、PrifixSpan算法等在挖掘序列模式時采取了一個多遍掃描候選子序列產(chǎn)生和測試的方法。由于概念格的完備性使其可以在不喪失有效信息的情況下。關(guān)鍵詞：數(shù)據(jù)挖掘，序列模式，概念格1.引言序列模式挖掘【1】是數(shù)據(jù)挖掘領(lǐng)域中重要的研究分支而頻繁工程集求解是序列模式挖掘的根底和前提。傳統(tǒng)的序列模式挖掘算法如AprioriAll算法【2】、GSP算法【3】、SP

2、ADE算法【4】、PrifixSpan算法等在挖掘序列模式時采取了一個多遍掃描候選子序列產(chǎn)生和測試的方法，有可能產(chǎn)生大量冗余候選序列，并需要屢次掃描數(shù)據(jù)庫，因而時間開銷較大。由于概念格的完備性使其可以在不喪失有效信息的情況下，基于概念格的頻繁工程集表示和求解，能有效地壓縮頻繁工程集的表示規(guī)模，這也為挖掘序列模式提供了有利條件，縮小了搜索空間，為序列模式的挖掘效率的提高提供了良好的根底。論文檢測。因此，作為序列模式挖掘的數(shù)學(xué)模型，將大規(guī)模數(shù)據(jù)庫中工程集映射到概念格中的概念內(nèi)涵,那么相應(yīng)地減小工程集的表示規(guī)模，因而有利于提高序列模式挖掘效率的。聶成林【7】首先提出了利用概念格進(jìn)行序列模式挖掘，從空

3、間上提高了挖掘效率。李云提出帶興趣度的序列概念格模型及其構(gòu)造算法把概念格的每個結(jié)點(diǎn)本質(zhì)上是一個最大工程集，非常有利于序列模式發(fā)現(xiàn)。通過掃描格節(jié)點(diǎn)就能能生成商家期望的感興趣序列，本文在帶興趣度的序列概念格模型上進(jìn)行最大序列模式挖掘。2.序列概念格模式相關(guān)概念給定一個由交易(Transaction)組成的交易數(shù)據(jù)庫DB。論文檢測。每個交易描述一位顧客在某時刻的一次買賣行為，內(nèi)容包含顧客號(Cid)、交易事件(Event)其中，每個交易序列中的事件具有唯一的標(biāo)識符Eid和交易的物品集合。規(guī)定同一個顧客在一個交易時間只能進(jìn)行一次交易，并且不考慮顧客在一次交易中所購置物品項(xiàng)的數(shù)量。定義 1 把每個商品稱

4、為一個數(shù)據(jù)項(xiàng)Item，簡稱項(xiàng)，令非空集合(i1,i2,im)，其中，ij(j=1,2, ,n)是不同的項(xiàng)，項(xiàng)的集合稱為工程集合item set,簡稱項(xiàng)集，其中每個k(1km)是一個項(xiàng)，長度為k的項(xiàng)集稱為k項(xiàng)集。如果把顧客的所有交易事件按交易時間進(jìn)行排列，將得到一個顧客序列,記作這里Eidi(1in)是某顧客的第i次交易標(biāo)識符，Event(Eidi)為該次交易中顧客購置的項(xiàng)集。由全部顧客序列組成的數(shù)據(jù)庫稱為顧客序列數(shù)據(jù)庫，記作SDB。通常，得到SDB需要對原交易數(shù)據(jù)庫重構(gòu)。定義 4 顧客支持序列S指序列S包含于該顧客序列中。序列S的支持度指顧客序列數(shù)據(jù)庫SDB中支持S的顧客數(shù)(也稱的支持?jǐn)?shù))與S

5、DB中顧客總數(shù)量之比。大于最小支持度(minimum support，由用戶指定的閾值，記為S)的序列稱為SDB上的頻繁序列。定義 5 項(xiàng)集的支持度(support)定義為在某次交易中購置了該項(xiàng)集所含物品的顧客數(shù)與總顧客數(shù)之比。支持度大于最小支持度的項(xiàng)集稱為頻繁項(xiàng)集。給定交易數(shù)據(jù)DB和用戶指定的最小支持度S，序列模式挖掘的問題就是發(fā)現(xiàn)DB中所有滿足S的子序列，每一個這樣的子序列代表了一個序列模式(a sequential pattern)序列模式挖掘的任務(wù)就是找出數(shù)據(jù)庫中所有的序列模式，即那些在序列集合中出現(xiàn)頻率超過最小支持度(用戶指定最小支持度閾值)的子序列。定義 6 給定兩個序列A=和B=

6、，如果存在一組整數(shù)使得a1bi1，a2bi2，ambim，那么稱序列A被序列B包含。不包含在任何其它序列中的序列稱為最大序列(Maximal Sequence)。定義7 在形式背景K(Cid,Eid),Event,SIM|(Event)|)中，t(Cid,Eid)，eEvent，在(Cid,Eid)和Event之間可定義兩個映射f和g：定理 1 在形式背景K(Cid,Eid),Event,SIM|(Event)|)上，假設(shè)對于，一個三元組，那么C必為一個興趣序列概念。那么在其形式背景K上，由所有序列概念的超概念-子概念的偏序關(guān)系所誘導(dǎo)出的格結(jié)構(gòu)稱為興趣序列概念格這種偏序關(guān)系，使用符號;表示，記

7、為IFL(K)。3.帶興趣度的序列概念格的最大模式算法研究對于任意的序列數(shù)據(jù)庫SDB，一旦按照算法SCLI構(gòu)造好了對應(yīng)于交易數(shù)據(jù)庫的序列概念格，就可以直接從格中得到所有的用戶感興趣的1-興趣序列，這個過程對應(yīng)于AprioriAll算法的第一步，但是對數(shù)據(jù)庫的掃描次數(shù)卻大大減少了。將得到的1-興趣序列最為種子集合進(jìn)行迭代以求得全部的序列模式。然后按照定義8定義9進(jìn)行k-序列的擴(kuò)展即可，并不需要屢次掃描原始數(shù)據(jù)庫而只需要掃描候選興趣序列的位置集合即可。定義 8 給定一個序列S=(其中sk(k=1,2, m)是一個工程集)和一個工程，S的含義是S連接，S在數(shù)據(jù)庫中的位置為(Cidi,Eidi)，在數(shù)

8、據(jù)庫中的位置為(Cidj,Eidj)，當(dāng)Cidi=Cidj且Eidi，簡稱運(yùn)算。例如：假設(shè)有項(xiàng)a和b，其中的位置信息為(10,1)(20,1)(20,2)，的位置信息為(10,2)(20,3)(30,2)，那么的位置信息(10,2)匹配的位置信息(10,1)，因?yàn)樗鼈冇邢嗤腃id=10，并且前者的Eid=2大于后者的Eid=1。同樣地，(20,3)匹配(20,1)，但是的位置信息(30,2)沒有與之匹配的位置信息，因?yàn)樵诘奈恢眯畔⒅校淮嬖谖恢眠@樣的位置信息使得Cid=30。因此，通過序列擴(kuò)展可以生成序列，并且序列 的位置信息為(10,2)(20,3)。定義 9 給定一個序列S=(其中sk(

9、k=1,2, m)是一個工程集)和一個工程，S的含義是S連接，S在數(shù)據(jù)庫中的位置為(Cidi,Eidi)，在數(shù)據(jù)庫中的位置為(Cidj , Eidj)，當(dāng)Cidi=Cidj且Eidi=Eidj時稱為項(xiàng)擴(kuò)展，新序列為S，把作為一個工程并入S的最后一個元素中，新序列S的位置為(Cidi,Eidj)。記為：S=，簡稱運(yùn)算。例如：假設(shè)有項(xiàng)b和d，其中，的位置信息為(10,1)(20,2)(30,2)，的位置信息為(10,2)(20,2)(30,2)，那么的位置信息(10,2)(30,2)與的位置信息(10,2)(30,2)相匹配，因?yàn)樗鼈冇邢嗤腃id及相同的Eid，但是的位置信息(20,2)沒有與之

10、匹配的的位置信息，所以，通過項(xiàng)擴(kuò)展可以生成序列，并且序列的位置信息為(10,2)(30,2)。在基于興趣的序列概念格的根底上，可以快速地發(fā)現(xiàn)最大的序列模式以及用戶需求的頻繁序列。算法思想如下：(1) 利用算法SCLI生成基于興趣度的序列概念格IMSL。(2) 把格IMSL節(jié)點(diǎn)中各序列的位置信息保存到位置信息表中。格IMSL 中的各序列就是1-興趣序列。(3) 掃描位置信息表，對位置信息表中的各序列利用運(yùn)算與運(yùn)算進(jìn)行2-序列的擴(kuò)展，同時判斷候選序列S在SDB中的支持興趣度值SIM|(S)| = SIM(S)*Support(S)是否大于Min-Sim，假設(shè)大于那么把生成的2-序列中各序列的位置信

11、息更新到位置信息表中。(4) 掃描2-序列中的位置信息表，對位置信息表中的各序列利用運(yùn)算與運(yùn)算進(jìn)行3-序列的擴(kuò)展，并把生成的3-序列中各序列的位置信息更新到位置信息表中。同理生成k-序列，直到?jīng)]有生成新的序列擴(kuò)展或項(xiàng)擴(kuò)展為止。(5) 按照定義6掃描位置信息表，生成最大興趣序列模式。算法IMLSP(Interest Measure LatticeSequence Pattern)實(shí)現(xiàn)了挖掘滿足用戶需求的最大序列模式，具體算法描述如下： 算法 Procedure IMLSP (IMSL (K), IMV,) 輸入：序列模糊格IMSL (K)，興趣序列閾值Min-Sim 輸出：滿足用戶需求的興趣序列

12、模式集MaxIMseq 1: Begin 2: Maxseq:= 3: For each node of IMSL(K) do 4: Mark:= Eventi 5: Tab(S). Si:= Eventi 6: Tab(S). Eposi := (Cid , Eid) i 7: Tab(S). SIMi := SIMi |( Event)| 8: For two Event of Tab(S) do 9: IF Cidi= Cidj and Eidi針對表1中的序列數(shù)據(jù)庫中構(gòu)建的基于興趣度的序列概念格模型進(jìn)行最大序列模式的挖掘，其中，Min-Sim =0.6。 表1 交易數(shù)據(jù)庫 Cid Se

13、quence 10 20 30 40 (1) 按照算法SCLI生成相應(yīng)的序列概念格的Hasse圖如圖1。圖1 序列概念格的Hasse圖(2) 把圖1節(jié)點(diǎn)中各序列的位置信息保存到位置信息表中如下表2表2 圖1中1-序列的位置信息 1-序列 位置信息 Sim (10,1)(10,2) (20,1) (30,2)(40,1) 1.0 (10,1)(20,1)(30,3)(40,1)(40,3) 2.0 (10,1)(10,2)(10,4)(40,2) 2.0 (10,3)(20,2)(40,2) 1.8 (10,4)(20,2)(30,2) 0.9 (30,1)(40,3) 1.6 (40,4) 1

14、.1 (10,1) (20,1)(40,1) 0.9 (10,1) (10,2) 0.7 (40,3) 1.2 (30,1) 0.8 (3) 對表2中的每個1-序列利用運(yùn)算與運(yùn)算進(jìn)行2-序列的擴(kuò)展，同時判斷候選序列S在SDB中的支持興趣度值SIM|(S)| = SIM(S)*Support(S)是否大于Min-Sim，本例中Min-Sim=0.6，假設(shè)大于那么把生成的2-序列中各序列的位置信息更新到位置信息表中表3。表3 2-序列的位置信息 2-序列 位置信息 Sim (30,3)(40,3) 0.6 (10,2)(10,4)(40,2) 1.05 (10,3)(20,2)(40,2) 1.2

15、 (10,4)(20,2) 0.5 (10,2)(10,4)(40,2) 1.35 (10,3)(20,2)(40,2) 1.5 (10,4)(20,2) 0.7 (10,2)(10,4)(40,2) 1.1 (10,4)(20,2) 0.6 (4) 由2-序列沒有生成3-序列，故，最長的序列模式長度為2。(5) 最后生成的最大興趣序列模式：、，其序列模式的興趣度值分別為1.1、0.6、1.05、1.2、1.5、1.2、0.75、1.1、0.6。4.結(jié)果分析將本文研究的基于序列概念格的挖掘算法與傳統(tǒng)的挖掘算法相比擬，我們可以得出以下結(jié)論：(1) 由于序列概念格的漸進(jìn)式構(gòu)造算法的優(yōu)點(diǎn)在于可以實(shí)現(xiàn)

16、概念格的維護(hù)和更新，因此，帶興趣度的序列概念格的挖掘完全適應(yīng)于增量式挖掘序列模式，當(dāng)有新數(shù)據(jù)參加，即數(shù)據(jù)庫規(guī)模增大時，不需要重新掃描整個新數(shù)據(jù)庫，只需要在原始序列概念格上進(jìn)行更新操作，得到新的序列概念格，然后按挖掘過程獲取新的序列模式，實(shí)現(xiàn)對序列模式發(fā)現(xiàn)的增量挖掘。(2) 另外一個問題是由于概念格的節(jié)點(diǎn)數(shù)量在最壞的情況下是呈指數(shù)增長的，因此內(nèi)存的消耗量有時會到達(dá)難以承受的程度，因此可以考慮利用外部存儲器和分解格或者采取并行的方法來構(gòu)格。5.結(jié)語基于興趣度的序列概念格的最大序列模式挖掘完全適應(yīng)于增量式挖掘序列模式。論文檢測。序列概念格構(gòu)造是建立在序列數(shù)據(jù)庫形式背景的根底上，序列形式背景的復(fù)雜性很

17、大程度上制約后續(xù)處理的性能，因此如何將序列數(shù)據(jù)庫轉(zhuǎn)化成序列形式背景，并滿足用戶支持度和置信度的情況下，使序列形式背景進(jìn)一步優(yōu)化是一個重要的預(yù)處理研究方向。所以，下一步的研究那么需要考慮并行處理以提高挖掘的效率。參考文獻(xiàn)【1】 AGRAWAL R，IMIELINSKI T，SWAMI AMining association rulesbetweensets of items in large databasesProceedings of the ACM SIGMOD Conference on Management of DataWashington，DC：ACM Press，1993：207

18、216【2】 Agrawal R ,Srikant R. Mining Sequential Patterns . Proc 1995 Int Conf Data Engineering( ICDE95) .Taipei : IEEE Computer Society ,1995. 3141【3】 Agrawal R ,Srikant R. Mining Sequential Patterns : Generalizationgs and PerformanceImprovments . Proc 5th Int Conf Extending Database Technology ( EDBT) .Avignon : Lecture Notes in Computer Science , 1996. 317.【4】 M. Zaki. SPADE:An Efficient Algorithm for Mining Frequent Sequences. Machine Learning, 2001，411 / 2:31 - 60 .【5】 Han J，Pei J，MortazaviAsl B，et a1Prefixspan：Mining Sequential PatternsEficiently by P