1、帶興趣度的序列概念格的最大模式挖掘(圖文)論文導讀：1.引言序列模式挖掘1是數據挖掘領域中重要的研究分支而頻繁項目集求解是序列模式挖掘的基礎和前提。傳統的序列模式挖掘算法如AprioriAll算法2、GSP算法3、SPADE算法4、PrifixSpan算法5,6等在挖掘序列模式時采取了一個多遍掃描候選子序列產生和測試的方法。由于概念格的完備性使其可以在不丟失有效信息的情況下。關鍵詞：數據挖掘，序列模式，概念格 1.引言序列模式挖掘1是數據挖掘領域中重要的研究分支而頻繁項目集求解是序列模式挖掘的基礎和前提。傳統的序列模式挖掘算法如AprioriAll算法2、GSP算法3、SPADE算法

2、4、PrifixSpan算法5,6等在挖掘序列模式時采取了一個多遍掃描候選子序列產生和測試的方法，有可能產生大量冗余候選序列，并需要多次掃描數據庫，因而時間開銷較大。由于概念格的完備性使其可以在不丟失有效信息的情況下，基于概念格的頻繁項目集表示和求解，能有效地壓縮頻繁項目集的表示規模，這也為挖掘序列模式提供了有利條件，縮小了搜索空間，為序列模式的挖掘效率的提高提供了良好的基礎。論文檢測。因此，作為序列模式挖掘的數學模型，將大規模數據庫中項目集映射到概念格中的概念內涵,則相應地減小項目集的表示規模，因而有利于提高序列模式挖掘效率的。聶成林7首先提出了利用概念格進行序列模式挖掘，從空間上提高了挖掘

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

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

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

6、B=，如果存在一組整數使得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)|)上，若對于，一個三元組，則C必為一個興趣序列概念。則在其形式背景K上，由所有序列概念的超概念-子概念的偏序關系所誘導出的格結構稱為興趣序列概念格（這種偏序關系，使用符號“”表示），

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

8、數據庫中的位置為(Cidj,Eidj)，當Cidi=Cidj且Eidi，簡稱運算。例如：假設有項a和b，其中的位置信息為(10,1)(20,1)(20,2)，的位置信息為(10,2)(20,3)(30,2)，那么的位置信息(10,2)匹配的位置信息(10,1)，因為它們有相同的Cid=10，并且前者的Eid=2大于后者的Eid=1。同樣地，(20,3)匹配(20,1)，但是的位置信息(30,2)沒有與之匹配的位置信息，因為在的位置信息中，不存在位置這樣的位置信息使得Cid=30。因此，通過序列擴展可以生成序列，并且序列 的位置信息為(10,2)(20,3)。定義 9 給定一個序列S=(其中sk(k=1,2, m)是一個項目集)和一個項目，S的含義是S連接，S在數據庫中的位置為(Cidi,Eidi)，在數據庫中的位置為(Cidj , Eidj)，當Cidi=Cidj且Eidi=Eidj時稱為項擴展，新序列為S，把作為一個項目并入S的最后一個元素中，新序列S的位置為(Cidi,Eidj)。記為：S=，簡稱運算。例如：假設有項b和d，其中，的位置信息為(10,1)(20,2)(30,2)，的位置信息為(10,2)(20,2)