基于并發(fā)序列模式的偏序模式挖掘

逄玉俊， 劉 英， 陳未如

(沈陽(yáng)化工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，遼寧沈陽(yáng)110142)

判斷事務(wù)的偏序關(guān)系［1］在生活中應(yīng)用越來(lái)越廣泛，這個(gè)偏序關(guān)系是由一些相互關(guān)聯(lián)的事務(wù)及其上的序關(guān)系構(gòu)成，這里的序關(guān)系主要包括事務(wù)之間經(jīng)常順序出現(xiàn)的、經(jīng)常伴隨出現(xiàn)(無(wú)序)的及這2種關(guān)系的結(jié)合.這種相關(guān)事務(wù)集的劃分和序關(guān)系的判斷就是本文要研究的偏序關(guān)系模式，且利用并發(fā)事務(wù)與相關(guān)事務(wù)的聯(lián)系和并發(fā)關(guān)系中隱含的符合偏序性質(zhì)的關(guān)系，給出基于并發(fā)序列模式的偏序關(guān)系模式挖掘方法.偏序關(guān)系是對(duì)一組相關(guān)事務(wù)集及其上的序關(guān)系的描述，偏序關(guān)系模式挖掘是在事務(wù)序列數(shù)據(jù)庫(kù)上發(fā)現(xiàn)事務(wù)間偏序關(guān)系的挖掘任務(wù).并發(fā)序列模式［2］挖掘是一種在序列模式挖掘基礎(chǔ)上發(fā)現(xiàn)序列間并發(fā)關(guān)系的挖掘任務(wù)，而在它基礎(chǔ)上可以進(jìn)一步挖掘偏序關(guān)系模式.目前未見(jiàn)與本文提到的挖掘偏序模式方法相同的相關(guān)文獻(xiàn)報(bào)道.

1 并發(fā)序列模式

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

并發(fā)序列模式是結(jié)構(gòu)關(guān)系模式(Structural Relation Pattern)的一種，其含義可理解為，2個(gè)或多個(gè)序列模式在客戶序列數(shù)據(jù)庫(kù)中同時(shí)被足夠多的客戶序列所支持.詳細(xì)概念及挖掘方法見(jiàn)文獻(xiàn)［2］.

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

2 偏序關(guān)系和偏序關(guān)系模式

2.1 有序關(guān)系與偏序關(guān)系序列

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

有序［3］(Orders)可以看成是一個(gè)由有序?qū)M成的二元關(guān)系集合，可以應(yīng)用集合操作來(lái)處理有序關(guān)系.

如果一個(gè)二元關(guān)系P?A×A是自反、反對(duì)稱(chēng)和傳遞的，則P是集合A上的偏序［4］.即對(duì)于偏序關(guān)系P，有［3］

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

(2)反對(duì)稱(chēng)性:對(duì)于所有的t1，t2∈A，有(t1，t2)∈P和(t2，t1)∈P，當(dāng)且僅當(dāng)t1=t2時(shí).

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

如果對(duì)于任意2個(gè)元素t1，t2∈A，有(t1，t2)∈P，則P是一個(gè)全序關(guān)系.

定義2 有序關(guān)系序列.

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

單就一個(gè)序列來(lái)說(shuō)，如果其中沒(méi)有重復(fù)出現(xiàn)的元素，則將構(gòu)成一個(gè)全序關(guān)系，即所有元素之間都有序.可以通過(guò)消去序列模式中重復(fù)元素的方法得到全序關(guān)系.

定義3 元素間的序.

設(shè)事務(wù)集I上的有序關(guān)系序列集A={s1，s2，…，sn}，對(duì)于2個(gè)不相同的元素(事務(wù))α，β∈I:

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

如果不存在si∈A，使得α，β∈si，則稱(chēng)元素α，β相對(duì)于A是無(wú)序的;

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

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

定義4 序列對(duì)偏序關(guān)系的支持.

如果給定有序關(guān)系序列O和一個(gè)偏序關(guān)系P，O和P的元素即相同，而P的所有二元關(guān)系在O中都成立，則稱(chēng)有序關(guān)系序列O支持偏序關(guān)系P，或者說(shuō)，O是P的一種全序表現(xiàn)形式、P可產(chǎn)生O，表示為O|→P.

一般地，如果序列S存在一個(gè)子序列O，O是一個(gè)有序關(guān)系序列，且O支持P，則稱(chēng)S支持P，或者說(shuō)，S包含了P的一種全序表現(xiàn)形式、P可產(chǎn)生S的一個(gè)子序列，表示為S|→P.

2.2 偏序關(guān)系模式

構(gòu)成偏序關(guān)系的所有元素屬于一個(gè)集合，即它們之間有較強(qiáng)的關(guān)聯(lián)關(guān)系.為衡量這種關(guān)系的強(qiáng)弱，引入相關(guān)度的概念.

定義5 相關(guān)度:對(duì)于基于事務(wù)集I中的序列數(shù)據(jù)庫(kù)CSDB，元素α和β的相關(guān)度是指相對(duì)于α或β在CSDB的某一序列中出現(xiàn)，α和β同時(shí)出現(xiàn)的頻度，形式地表示為:

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

定義6 相關(guān)元素:對(duì)于基于事務(wù)集I中的序列數(shù)據(jù)庫(kù)CSDB，如果元素α1，α2，…，αn的相關(guān)度足夠大，即達(dá)到或超過(guò)了某一設(shè)定值minrel，即:Relative(α1，α2，…，αn)≥minrel，則稱(chēng)這些元素相對(duì)于序列數(shù)據(jù)庫(kù)CSDB是相關(guān)的.特別地，如果對(duì)于元素 α和 β有Relative(α，β)≥minrel，則稱(chēng)α和β是相關(guān)的，表示為α||β.一般的，符號(hào)“||”表示前后兩項(xiàng)之間是相關(guān)的.

上述提到的相關(guān)元素對(duì)和有序元素概念中涉及的minrel叫做最小相關(guān)度.

定義7 有序度:對(duì)于基于事務(wù)集I中的序列數(shù)據(jù)庫(kù)CSDB，元素α和β的有序度是指相對(duì)于α或β在CSDB的某一序列中出現(xiàn)，α和β以＜α，β＞的次序同時(shí)出現(xiàn)的頻度，形式地表示為:

定義8 有序元素:對(duì)于基于事務(wù)集I中的序列數(shù)據(jù)庫(kù)CSDB，如果元素α和β的有序度足夠大，即達(dá)到或超過(guò)了某一設(shè)定值minrel，即: Order(α，β)≥minrel，則稱(chēng)元素α和β相對(duì)于序列數(shù)據(jù)庫(kù)CSDB是有序的，它們構(gòu)成一對(duì)有序元素，表示為α＜β.一般的，符號(hào)“＜”表示前后兩項(xiàng)之間是有序的.

定義9 偏序關(guān)系模式.

對(duì)于基于事務(wù)集I中的序列數(shù)據(jù)庫(kù)CSDB，一個(gè)偏序關(guān)系模式是指其上的一個(gè)相關(guān)元素集R以及該集合上的二元關(guān)系P，P是一個(gè)偏序關(guān)系，而每個(gè)二元關(guān)系中的兩個(gè)元素都是CSDB的有序元素，且P在CSDB的序列中頻繁地出現(xiàn)，即有足夠多的序列支持P，稱(chēng)P是一個(gè)偏序關(guān)系模式.即:設(shè)用戶給定的最小相關(guān)度為minrel，則

Relative(R)≥minrel;

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

P是偏序關(guān)系，且

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

3 偏序關(guān)系模式與并發(fā)序列模式

3.1 偏序關(guān)系模式的性質(zhì)

對(duì)于序列數(shù)據(jù)庫(kù)CSDB上相關(guān)元素集R的偏序關(guān)系P，α、β、γ是R的元素:

性質(zhì)1 反單調(diào)性:R的子集R'上的二元關(guān)系P'仍是一個(gè)偏序關(guān)系模式，如果:

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

性質(zhì)2 相關(guān)性:R上的所有元素之間都是相關(guān)的.

性質(zhì)3 交換律:α||β=β||α，即元素間的相關(guān)關(guān)系是相互的、對(duì)稱(chēng)的.

性質(zhì)4 分配律:(α＜β)||(α＜γ)=α＜ (β||γ)，(α＜γ)||(β＜γ)=(α||β)＜γ，即:兩個(gè)具有相同前驅(qū)(后繼)的相關(guān)有序?qū)?，可以提取共同的前?qū)(后繼).

分配律將在對(duì)偏序關(guān)系模式進(jìn)行整理、組合、求精、優(yōu)化過(guò)程中起到重要作用.

3.2 并發(fā)序列模式與偏序模式的聯(lián)系

根據(jù)并發(fā)序列模式的定義和性質(zhì)［2，5］與上述偏序關(guān)系模式的定義和性質(zhì)，設(shè)最小相關(guān)度、最小并發(fā)度值相同，如果兩個(gè)序列模式s1和s2是并發(fā)的，則可得到以下推論:

推論1 s1和s2的所有序列中的所有元素構(gòu)成相關(guān)元素集;

推論2 分屬s1和s2上的任意兩個(gè)元素是相關(guān)的;

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

推論4 如果s1或s2中無(wú)重復(fù)元素，那么s1或s2是有序關(guān)系序列.

定理1 有序關(guān)系序列集上的偏序關(guān)系.

對(duì)于事務(wù)集I上的有序關(guān)系序列集A={s1，s2，…，sn}，如果A中不包含任何次序矛盾的元素對(duì)和次序不完全的元素，則A可構(gòu)成一個(gè)偏序關(guān)系.

簡(jiǎn)要證明:A中不包含任何次序矛盾的元素對(duì)保證了反對(duì)稱(chēng)性;A中內(nèi)部不包括次序不完全的元素保證了傳遞性.所以A可構(gòu)成一個(gè)偏序關(guān)系.

定理2 由并發(fā)序列模式可得出偏序關(guān)系模式.

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

定理3 所有偏序關(guān)系模式可由并發(fā)序列模式導(dǎo)出.

證明:由于偏序關(guān)系模式要求在序列數(shù)據(jù)庫(kù)中有足夠多的客戶序列支持P，而每個(gè)這樣的客戶序列將對(duì)應(yīng)一個(gè)有序關(guān)系序列支持P.由于P是頻繁的，則這些有序關(guān)系序列將構(gòu)成一個(gè)并發(fā)序列模式.反過(guò)來(lái)說(shuō)，這樣的一個(gè)并發(fā)序列模式可產(chǎn)生給定的偏序關(guān)系模式.

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

3.3 主要算法描述

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

(2)對(duì)并發(fā)序列模式集CSPSet的每一個(gè)并發(fā)序列模式CSP;

(A)并發(fā)序列模式CSP中包含的所有元素構(gòu)成關(guān)聯(lián)元素集R;

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

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

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

算法1 拆分序列模式 //將含有重復(fù)元素的序列拆分成若干個(gè)無(wú)重復(fù)元素的有序關(guān)系序列.

輸入:并發(fā)序列模式CSP

輸出:有序關(guān)系序列集COP方法:

(1)令COP為空

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

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

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

(3)輸出COP

算法2 構(gòu)建偏序關(guān)系模式(POP_Graph).

輸入:并發(fā)有序關(guān)系序列集COP={βi|βi∈SP，1≤i≤n，n是COP中有序關(guān)系序列個(gè)數(shù)}.

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

方法:

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

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

(3)Call RefinePOP_Graph(POP_Graph).//求精構(gòu)建最終的偏序關(guān)系模式圖POP_Graph.

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

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

輸出:(the refined POPG)經(jīng)組合后構(gòu)成的偏序關(guān)系模式(POP_Graph).

方法:

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

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

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

算法4 Combine將2個(gè)并發(fā)有序關(guān)系模式組合偏序關(guān)系模式.

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

輸出:偏序關(guān)系模式.

方法:

(1)令POBG'為空

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

(3)如果(βi和βj包含次序相矛盾的元素對(duì))或(β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)對(duì) elemSi和 elemSj進(jìn)行進(jìn)一步求精(遞歸調(diào)用算法3);

(8)用有向邊連接各部分構(gòu)成偏序關(guān)系模式.

4 舉例

在給定的序列數(shù)據(jù)庫(kù)上挖掘偏序模式，且給定最小相關(guān)度minrel.步驟是先按最小并發(fā)度等于最小相關(guān)度進(jìn)行并發(fā)序列模式挖掘，然后對(duì)每個(gè)并發(fā)序列模式應(yīng)用算法得到偏序模式.

假設(shè)挖掘得到的一個(gè)并發(fā)序列模式為［＜ebcb＞+＜eacb＞+＜efcb＞+＜fcbc＞］，以此為基礎(chǔ)挖掘偏序模式，過(guò)程描述如下:

(1)首先，應(yīng)用算法1對(duì)有重復(fù)元素的序列進(jìn)行分解使之成為無(wú)重復(fù)元素的有序關(guān)系序列，則序列＜ebcb＞分解成2個(gè)序列＜ebc＞和＜ecb＞，＜fcbc＞分解成2個(gè)序列 ＜fcb＞和＜fbc＞.原并發(fā)序列模式變成并發(fā)的有序模式［＜ebc＞+＜ecb＞+＜eacb＞+＜efcb＞+＜fbc＞+＜fcb＞］.

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

(3)應(yīng)用算法2～算法4可得到2個(gè)偏序關(guān)系模式，如圖1所示.

其中相關(guān)元素:{a，b，c，e，f}相關(guān)關(guān)系如下:

①相關(guān)關(guān)系{＜eb＞，＜ec＞，＜bc＞，＜fb＞，＜fc＞}

②相關(guān)關(guān)系{＜ea＞，＜eb＞，＜ec＞，＜ef＞，＜ac＞，＜ab＞，＜fb＞}.

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

5 結(jié)束語(yǔ)

主要描述了基于元素間偏序關(guān)系的理論體系，分析偏序和并發(fā)的概念，給出有關(guān)偏序的定義，引入相關(guān)度、相關(guān)元素和偏序關(guān)系模式的定義，通過(guò)性質(zhì)、定理推導(dǎo)出偏序與并發(fā)之間有著緊密的聯(lián)系，在此基礎(chǔ)上得出基于并發(fā)序列模式的偏序模式挖掘方法，并應(yīng)用實(shí)例說(shuō)明此方法的挖掘過(guò)程.本課題是把每個(gè)項(xiàng)集看作一個(gè)元素進(jìn)行討論.偏序關(guān)系模式挖掘具有實(shí)際的應(yīng)用價(jià)值，這將是今后工作的重點(diǎn)研究方向.

［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］ 但紅衛(wèi).基于偏序的頻繁序列模式壓縮算法研究［D］.浙江:浙江大學(xué)，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.