基于并發序列模式的偏序模式挖掘

逄玉俊， 劉 英， 陳未如

(沈陽化工大學計算機科學與技術學院，遼寧沈陽110142)

判斷事務的偏序關系［1］在生活中應用越來越廣泛，這個偏序關系是由一些相互關聯的事務及其上的序關系構成，這里的序關系主要包括事務之間經常順序出現的、經常伴隨出現(無序)的及這2種關系的結合.這種相關事務集的劃分和序關系的判斷就是本文要研究的偏序關系模式，且利用并發事務與相關事務的聯系和并發關系中隱含的符合偏序性質的關系，給出基于并發序列模式的偏序關系模式挖掘方法.偏序關系是對一組相關事務集及其上的序關系的描述，偏序關系模式挖掘是在事務序列數據庫上發現事務間偏序關系的挖掘任務.并發序列模式［2］挖掘是一種在序列模式挖掘基礎上發現序列間并發關系的挖掘任務，而在它基礎上可以進一步挖掘偏序關系模式.目前未見與本文提到的挖掘偏序模式方法相同的相關文獻報道.

1 并發序列模式

序列(Sequence)是由一組元素組成的有序表，即不同元素的有序排列，記作S=＜s1，s2，…，sn＞，其中sk(1≤k≤n)是一個元素.序列模式挖掘是挖掘頻繁出現的有序事件或子序列［1］.序列模式挖掘的側重點在于分析數據間的前后序列關系.

并發序列模式是結構關系模式(Structural Relation Pattern)的一種，其含義可理解為，2個或多個序列模式在客戶序列數據庫中同時被足夠多的客戶序列所支持.詳細概念及挖掘方法見文獻［2］.

并發序列模式包含2種關系，一是各序列內部的順序關系，二是序列之間的并發關系.對并發序列模式中的任2個元素，如果它們同屬于一個序列模式，則它們之間存在順序關系;如果它們分別出現在不同的序列模式中，則它們之間存在并發關系.并發序列模式的這種特性使得可以基于并發序列模式進行偏序模式的挖掘.

2 偏序關系和偏序關系模式

2.1 有序關系與偏序關系序列

定義1 有序、偏序和全序.

有序［3］(Orders)可以看成是一個由有序對組成的二元關系集合，可以應用集合操作來處理有序關系.

如果一個二元關系P?A×A是自反、反對稱和傳遞的，則P是集合A上的偏序［4］.即對于偏序關系P，有［3］

(1)自反性:對于所有的t∈A，有(t，t)∈P;

(2)反對稱性:對于所有的t1，t2∈A，有(t1，t2)∈P和(t2，t1)∈P，當且僅當t1=t2時.

(3)傳遞性:對于所有的t1，t2，t3∈A，如果有(t1，t2)∈P且(t2，t3)∈P則有(t1，t3)∈P.

如果對于任意2個元素t1，t2∈A，有(t1，t2)∈P，則P是一個全序關系.

定義2 有序關系序列.

如果序列c是由互不相同的元素α1，α2，…，αn組成，且所處的位置分別是1，2，…，n，則所有元素之間都是有序的，稱它們相對于c有序，表示為＜α1，α2，…，αn＞c，稱c是一個有序關系序列.特別地，對于元素α和β，若它們相對于序列c有序，且出現次序是α在前β在后，則表示為＜α，β＞c或 ＜α，β＞∠c，也可以省略表示為＜αβ＞.

單就一個序列來說，如果其中沒有重復出現的元素，則將構成一個全序關系，即所有元素之間都有序.可以通過消去序列模式中重復元素的方法得到全序關系.

定義3 元素間的序.

設事務集I上的有序關系序列集A={s1，s2，…，sn}，對于2個不相同的元素(事務)α，β∈I:

如果存在si∈A，使得＜α，β＞∠si，且對于任何sj∈A，或者＜α，β＞∠sj，或者α?sj且β?sj，稱元素α，β相對于A是有序的;

如果不存在si∈A，使得α，β∈si，則稱元素α，β相對于A是無序的;

如果存在si，sj∈A，且si≠sj，有＜α，β＞∠si和＜β，α＞∠sj，稱元素α，β相對于A是次序矛盾的;

對于元素β∈I，如果存在α，γ∈I，si，sj∈A，且si≠sj，有＜α，β＞∠si，＜α，β＞＜sj和 ＜β，γ＞＜si，＜β，γ＞∠sj，稱元素β相對于A是次序不完全的.

定義4 序列對偏序關系的支持.

如果給定有序關系序列O和一個偏序關系P，O和P的元素即相同，而P的所有二元關系在O中都成立，則稱有序關系序列O支持偏序關系P，或者說，O是P的一種全序表現形式、P可產生O，表示為O|→P.

一般地，如果序列S存在一個子序列O，O是一個有序關系序列，且O支持P，則稱S支持P，或者說，S包含了P的一種全序表現形式、P可產生S的一個子序列，表示為S|→P.

2.2 偏序關系模式

構成偏序關系的所有元素屬于一個集合，即它們之間有較強的關聯關系.為衡量這種關系的強弱，引入相關度的概念.

定義5 相關度:對于基于事務集I中的序列數據庫CSDB，元素α和β的相關度是指相對于α或β在CSDB的某一序列中出現，α和β同時出現的頻度，形式地表示為:

一般地，對于元素α1，α2，…，αn的相關度可定義為所有包含α1，α2，…，或αn的客戶序列中同時包含所有α1，α2，…，和αn的客戶序列數的比例.即:

定義6 相關元素:對于基于事務集I中的序列數據庫CSDB，如果元素α1，α2，…，αn的相關度足夠大，即達到或超過了某一設定值minrel，即:Relative(α1，α2，…，αn)≥minrel，則稱這些元素相對于序列數據庫CSDB是相關的.特別地，如果對于元素 α和 β有Relative(α，β)≥minrel，則稱α和β是相關的，表示為α||β.一般的，符號“||”表示前后兩項之間是相關的.

上述提到的相關元素對和有序元素概念中涉及的minrel叫做最小相關度.

定義7 有序度:對于基于事務集I中的序列數據庫CSDB，元素α和β的有序度是指相對于α或β在CSDB的某一序列中出現，α和β以＜α，β＞的次序同時出現的頻度，形式地表示為:

定義8 有序元素:對于基于事務集I中的序列數據庫CSDB，如果元素α和β的有序度足夠大，即達到或超過了某一設定值minrel，即: Order(α，β)≥minrel，則稱元素α和β相對于序列數據庫CSDB是有序的，它們構成一對有序元素，表示為α＜β.一般的，符號“＜”表示前后兩項之間是有序的.

定義9 偏序關系模式.

對于基于事務集I中的序列數據庫CSDB，一個偏序關系模式是指其上的一個相關元素集R以及該集合上的二元關系P，P是一個偏序關系，而每個二元關系中的兩個元素都是CSDB的有序元素，且P在CSDB的序列中頻繁地出現，即有足夠多的序列支持P，稱P是一個偏序關系模式.即:設用戶給定的最小相關度為minrel，則

Relative(R)≥minrel;

P={＜α，β＞|Order(α，β)≥minrel，and α，β∈R};

P是偏序關系，且

其中:sup(P)表示偏序關系P的支持度，minsup是用戶指定最小支持度，表示P是頻繁出現的，是一個模式.

3 偏序關系模式與并發序列模式

3.1 偏序關系模式的性質

對于序列數據庫CSDB上相關元素集R的偏序關系P，α、β、γ是R的元素:

性質1 反單調性:R的子集R'上的二元關系P'仍是一個偏序關系模式，如果:

P'={＜α，β＞|α，β∈R'，＜α，β＞∈P，R'?R}即:偏序關系模式的子模式仍是偏序關系.

性質2 相關性:R上的所有元素之間都是相關的.

性質3 交換律:α||β=β||α，即元素間的相關關系是相互的、對稱的.

性質4 分配律:(α＜β)||(α＜γ)=α＜ (β||γ)，(α＜γ)||(β＜γ)=(α||β)＜γ，即:兩個具有相同前驅(后繼)的相關有序對，可以提取共同的前驅(后繼).

分配律將在對偏序關系模式進行整理、組合、求精、優化過程中起到重要作用.

3.2 并發序列模式與偏序模式的聯系

根據并發序列模式的定義和性質［2，5］與上述偏序關系模式的定義和性質，設最小相關度、最小并發度值相同，如果兩個序列模式s1和s2是并發的，則可得到以下推論:

推論1 s1和s2的所有序列中的所有元素構成相關元素集;

推論2 分屬s1和s2上的任意兩個元素是相關的;

推論3 同屬s1或s2上的任意兩個元素之間是有序的;

推論4 如果s1或s2中無重復元素，那么s1或s2是有序關系序列.

定理1 有序關系序列集上的偏序關系.

對于事務集I上的有序關系序列集A={s1，s2，…，sn}，如果A中不包含任何次序矛盾的元素對和次序不完全的元素，則A可構成一個偏序關系.

簡要證明:A中不包含任何次序矛盾的元素對保證了反對稱性;A中內部不包括次序不完全的元素保證了傳遞性.所以A可構成一個偏序關系.

定理2 由并發序列模式可得出偏序關系模式.

證明:首先根據推論1，并發序列模式的所有序列中的所有元素構成相關元素集，而偏序關系模式的基礎是相關元素集;其次，根據推論4，如果并發序列模式的某個序列中無重復元素，那么這個序列是有序關系序列，即:若將所有并發序列模式的各序列中的重復元素去掉，可得到一組有序關系序列集;根據定理1，如果從前面得到的有序關系序列集中去掉那些包含次序矛盾元素對和包含次序不完全元素的序列，可得到一個偏序關系模式.

定理3 所有偏序關系模式可由并發序列模式導出.

證明:由于偏序關系模式要求在序列數據庫中有足夠多的客戶序列支持P，而每個這樣的客戶序列將對應一個有序關系序列支持P.由于P是頻繁的，則這些有序關系序列將構成一個并發序列模式.反過來說，這樣的一個并發序列模式可產生給定的偏序關系模式.

由定理3可知所有偏序關系模式可由并發序列模式導出，定理2給出了由并發序列模式得出偏序關系模式的方法:首先，對并發序列模式的每個序列進行拆分，使之成為有序關系序列，得到有序關系序列集，詳見算法1;其次，在有序關系序列集上消除包括次序相矛盾的元素對和次序不完全的元素的序列，詳見算法2至4.

3.3 主要算法描述

(1)設定以偏序模式的最小支持度(minsup)為最小并發度進行并發序列模式挖掘，得到最大并發序列模式集CSPSet;

(2)對并發序列模式集CSPSet的每一個并發序列模式CSP;

(A)并發序列模式CSP中包含的所有元素構成關聯元素集R;

(B)通過消除重復元素的辦法拆分并發序列模式CSP的每個序列sp，得到一組有序關系序列opg，拆分過程見算法1，拆分后去掉有包含關系的序列.根據并發序列模式的性質，這些有序關系序列也是并發的.對CSP的所有序列拆分后得到一個并發的有序關系序列集COP;

(C)對COP進行重組，得到若干個新的有序關系序列集POP，使得每個POP中不包含次序相矛盾的元素對和次序不完全的元素，為已得到的每個偏序關系模式構造偏序關系圖.過程見算法2～算法4;

(D)根據定理2，這些POP都是偏序關系模式.

算法1 拆分序列模式 //將含有重復元素的序列拆分成若干個無重復元素的有序關系序列.

輸入:并發序列模式CSP

輸出:有序關系序列集COP方法:

(1)令COP為空

(2)對于CSP中每一序列模式s做如下處理，直至CSP為空:

若s中存在某一重復出現的元素a，記錄a重復出現的位置a1、a2、…、an和次數n，將s復制成n個序列s1、s2、…、sn，使該元素a在每個序列si中只出現在ai位置一次(i=1，2，…，n)，其他元素不變，并存到CSP中;

否則，令 COP=COP∪{s}，CSP=CSP－{s}.

(3)輸出COP

算法2 構建偏序關系模式(POP_Graph).

輸入:并發有序關系序列集COP={βi|βi∈SP，1≤i≤n，n是COP中有序關系序列個數}.

輸出:偏序關系模式圖(POP_Graph).

方法:

(1)為每一個有序序列(βi∈COP)構建序列模式圖(SPG).每個SPG叫做一個偏序分支圖(POBG)，則有序序列βi的偏序分支表示為POBG(βi).

(2)POP_Graph=POBG(β1)∪POBG(β2)∪…∪POBG(βn).

(3)Call RefinePOP_Graph(POP_Graph).//求精構建最終的偏序關系模式圖POP_Graph.

算法3 RefinePOP_Graph(POP_Graph)//對POP_Graph的求精.

輸入:未求精的POP_Graph，用POPG表示.

輸出:(the refined POPG)經組合后構成的偏序關系模式(POP_Graph).

方法:

(1)Call Combine(POBG(βi)，POBG(βj)).對于任兩個POBG(βi)，POBG(βj)∈POPG，i≠j組合，得到一個新偏序分支圖 POBG'，如果POBG'不為空就存到POPG中.

(2)所有的可組合成新偏序分支圖(新圖不為空)的POBG'從POBGs中刪除.

(3)重復步驟(1)，(2)直到無新的偏序分支圖要組合.

算法4 Combine將2個并發有序關系模式組合偏序關系模式.

輸入:任意兩個并發的有序模式圖POBG (βi)，POBG(βj).

輸出:偏序關系模式.

方法:

(1)令POBG'為空

(2)如果(βi包含 βj)或(βj包含 βi)，返回;

(3)如果(βi和βj包含次序相矛盾的元素對)或(βj和βi包含次序不完全的元素)，返回;

(4)找出POBG(βi)和POBG(βj)的公共前綴，定義為preS.

(5)找出POBG(βi)和POBG(βj)的公共后綴，定義為postS.

(6)如果preS或postS不為空，令elemSi= (βi－preS－postS)和 elemSj=(βi－preS－postS);

(7)對 elemSi和 elemSj進行進一步求精(遞歸調用算法3);

(8)用有向邊連接各部分構成偏序關系模式.

4 舉例

在給定的序列數據庫上挖掘偏序模式，且給定最小相關度minrel.步驟是先按最小并發度等于最小相關度進行并發序列模式挖掘，然后對每個并發序列模式應用算法得到偏序模式.

假設挖掘得到的一個并發序列模式為［＜ebcb＞+＜eacb＞+＜efcb＞+＜fcbc＞］，以此為基礎挖掘偏序模式，過程描述如下:

(1)首先，應用算法1對有重復元素的序列進行分解使之成為無重復元素的有序關系序列，則序列＜ebcb＞分解成2個序列＜ebc＞和＜ecb＞，＜fcbc＞分解成2個序列 ＜fcb＞和＜fbc＞.原并發序列模式變成并發的有序模式［＜ebc＞+＜ecb＞+＜eacb＞+＜efcb＞+＜fbc＞+＜fcb＞］.

(2)其次，去掉有包含關系的序列，由于序列＜eacb＞包含序列＜ecb＞，序列＜efcb＞包含序列＜fcb＞，則消除后，原并發的有序模式替換成［＜ebc＞+＜eacb＞+＜efcb＞+＜fbc＞］.

(3)應用算法2～算法4可得到2個偏序關系模式，如圖1所示.

其中相關元素:{a，b，c，e，f}相關關系如下:

①相關關系{＜eb＞，＜ec＞，＜bc＞，＜fb＞，＜fc＞}

②相關關系{＜ea＞，＜eb＞，＜ec＞，＜ef＞，＜ac＞，＜ab＞，＜fb＞}.

圖1 從并發關系模式［＜ebcb＞+＜eacb＞+＜efcb＞+＜fcbc＞］生成偏序關系模式Fig.1 From concurrent pattem［＜ebcb＞+＜eacb＞+＜efcb＞+＜fcbc＞］to partial pattem

5 結束語

主要描述了基于元素間偏序關系的理論體系，分析偏序和并發的概念，給出有關偏序的定義，引入相關度、相關元素和偏序關系模式的定義，通過性質、定理推導出偏序與并發之間有著緊密的聯系，在此基礎上得出基于并發序列模式的偏序模式挖掘方法，并應用實例說明此方法的挖掘過程.本課題是把每個項集看作一個元素進行討論.偏序關系模式挖掘具有實際的應用價值，這將是今后工作的重點研究方向.

［1］ Gemma Gasas-Garriga.Summarizing Sequential Date with Closed Partial Orders［J］.SIAM Conf，2005: 380－391.

［2］ Chen Weiru，Zhang Yang，Chen Shanshan，et al.From Sequential Patterns to Structural Relation Patterns［C］//2009 International Conference on Scalable Computing and Communications;Eighth International Conference on Embedded Computing，Washington:IEEE Computer Society，2009:148－153.

［3］ Antti Ukkonen.Data Mining Techniques for Discovering Partial Orders［EB/OL］.(2004－10－31)［2010－12－17］.http://users.ics.tkk.fi/aukkonen/pdf/aukkonen_thesis.pdf.

［4］ 但紅衛.基于偏序的頻繁序列模式壓縮算法研究［D］.浙江:浙江大學，2007:37－65.

［5］ Lu Jing，Chen Weiru，Osei Adjei，et al.Sequential Patterns Postprocessing for Structural Relation Patterns Mining［J］.International Journal of Data Warehousing and Mining(IJDWM)，2008，4(3):71－89.