在頻繁序列模式中挖掘并發(fā)序列模式

張 洋， 陳未如， 張立忠

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

序列模式挖掘是數(shù)據(jù)挖掘的一個重要研究內(nèi)容，能夠發(fā)現(xiàn)隱藏在大規(guī)模數(shù)據(jù)中的具有順序關(guān)系的模式.結(jié)構(gòu)關(guān)系模式挖掘是一種建立在序列模式挖掘基礎(chǔ)上的新的挖掘任務(wù)，旨在尋找隱藏在序列模式后面的新的結(jié)構(gòu)關(guān)系模式.結(jié)構(gòu)關(guān)系模式［1－2］和序列模式一樣在實際應(yīng)用中也有重要的研究價值.結(jié)構(gòu)關(guān)系模式和序列模式之間的關(guān)系如圖1所示.

圖1 結(jié)構(gòu)關(guān)系模式和序列模式之間的關(guān)系Fig.1 The relationship between structural relation patterns and sequential patterns

圖挖掘［3－5］、樹挖掘［6－8］和偏序挖掘［9－11］與結(jié)構(gòu)關(guān)系模式挖掘相似.從挖掘的對象上看，偏序挖掘和結(jié)構(gòu)關(guān)系模式挖掘更為相似，結(jié)構(gòu)關(guān)系可以看作是偏序關(guān)系的限定和擴(kuò)展.結(jié)構(gòu)關(guān)系中的并發(fā)關(guān)系、互斥關(guān)系和順序關(guān)系可以看作是偏序關(guān)系的限定，他們簡化了挖掘過程和挖掘結(jié)果.而結(jié)構(gòu)關(guān)系中的重復(fù)關(guān)系、關(guān)聯(lián)關(guān)系則不屬于偏序關(guān)系，這使得結(jié)構(gòu)關(guān)系模式挖掘在實際應(yīng)用中更有價值.

經(jīng)過幾年的研究，本課題組建立了相對完整的結(jié)構(gòu)關(guān)系模式挖掘理論體系，獲得了一系列的研究成果.其中文獻(xiàn)［12－13］分別從序列間相對關(guān)系角度和整個序列數(shù)據(jù)庫的角度考慮序列模式之間的并發(fā)特性，提出了并發(fā)序列模式的定義、基本性質(zhì)以及挖掘并發(fā)序列模式的算法.文獻(xiàn)［14－15］提出了互斥關(guān)系模式的定義、性質(zhì)和挖掘方法.文獻(xiàn)［16］提出了重復(fù)關(guān)系模式的定義、性質(zhì)和挖掘方法.本文依然從序列間的相對關(guān)系出發(fā)考慮序列模式間的并發(fā)性，對并發(fā)序列模式的性質(zhì)進(jìn)行描述，并利用并發(fā)序列模式的反單調(diào)特性及挖掘的非平凡特性，在文獻(xiàn)［12］算法基礎(chǔ)上對算法進(jìn)行優(yōu)化.通過實驗對比可知:該算法在文獻(xiàn)［12］算法基礎(chǔ)上對挖掘結(jié)果進(jìn)行了大幅精簡，算法正確、有效.

1 基本概念

1.1 定義

設(shè)SDB={S1，S2，S3，…，Sn}是一個序列數(shù)據(jù)庫，α與β為在某一最小支持度minsup下序列模式挖掘結(jié)果，且α與β互不包含.

定義1 若(α∠S)∧(β∠S)，則在序列s中α和β構(gòu)成并發(fā)關(guān)系，表示為［α+β］S.一般地，如果(α1∠S)∧(α2∠S)∧…(αn∠S)，則相對于序列s，序列α1，α2，…，αn構(gòu)成并發(fā)關(guān)系，表示為［α1+α2+…+αn］S，其中符號“∠”表示包含于.

定義2 序列α和β的并發(fā)度

序列模式α1，α2，…，αn的并發(fā)度可以定義為

這里Sk∈SDB，1≤k≤n，公式(1)中分子為同時包含α和β的序列的個數(shù)，分子為包含α或β的序列的個數(shù);公式(2)同上.

定義3 設(shè)mincon為用戶所給最小并發(fā)度閾值，如果concurrence(α，β)≥mincon［12］，那么α、β構(gòu)成并發(fā)序列模式，表示成［α+β］.

示例:表1中因為〈ac〉和〈af〉都包含于S3=〈babfaec〉，所以，有［〈ac〉+〈af〉］〈babfaec〉.設(shè)客戶給定最小并發(fā)度mincon為50%，在S3和S4中afac和bafc都滿足并發(fā)關(guān)系，并且包含afac或bafc的序列個數(shù)為2，即 concurrence(〈afac〉，〈bafc〉)=100%≥mincon，所以，〈afac〉和〈bafc〉構(gòu)成并發(fā)序列模式，表示為［〈afac〉+〈bafc〉］.

表1 示例序列數(shù)據(jù)庫SDB和每個序列所支持的序列模式Table 1 A sample SDB and supported sequential patterns by each sequence

1.2 基本性質(zhì)

性質(zhì)1 ［x+y］=［y+x］

即并發(fā)序列模式滿足交換律.

性質(zhì)2 ［x+y+z］=［［x+y］+z］=

［x+［y+z］］.

性質(zhì)2說明并發(fā)的各個序列之間滿足可結(jié)合性.性質(zhì)1和性質(zhì)2保證了在挖掘并發(fā)序列模式過程中，任意挖掘次序都將會得到相同的結(jié)果.

性質(zhì)3 并發(fā)關(guān)系與頻繁項集、序列模式之間存在包含關(guān)系.在minsup≥mincon的情況下，一個頻繁項集中的各個頻繁項之間可構(gòu)成并發(fā)模式，一個序列模式的各個元素之間以及各個子序列模式之間可構(gòu)成并發(fā)模式.

例如，頻繁項集(a，b)可以構(gòu)成并發(fā)模式［a+b］，序列模式〈abc〉可以構(gòu)成并發(fā)模式［a+ b+c］、［ab+ac+bc］等.由本性質(zhì)所得到的并發(fā)模式并不是挖掘的目標(biāo).并發(fā)模式挖掘的結(jié)果應(yīng)該是不包含在頻繁項集或序列模式中的并發(fā)模式，即并發(fā)序列模式挖掘結(jié)果應(yīng)具有非平凡特性.

性質(zhì)4 多分支并發(fā)序列模式中去掉任意分支后仍構(gòu)成并發(fā)序列模式，稱為原并發(fā)序列模式的子模式.

性質(zhì)4為并發(fā)序列模式的反單調(diào)特性，該性質(zhì)可以用來指導(dǎo)采用自下向上的方法挖掘并發(fā)序列模式，在進(jìn)行并發(fā)序列模式挖掘過程中將起到重要作用.

上述性質(zhì)定理均可從定義出發(fā)進(jìn)行推導(dǎo)證明，由于篇幅有限，此處略.

2 并發(fā)序列模式挖掘改進(jìn)算法

任意序列模式之間的并發(fā)關(guān)系可以按定義1進(jìn)行判斷，利用定義2和定義3還可以判斷滿足并發(fā)關(guān)系的序列模式是否構(gòu)成并發(fā)序列模式.但是對于一個序列數(shù)據(jù)庫SDB，找到所有滿足最小并發(fā)度的并發(fā)序列模式仍然是一個具有挑戰(zhàn)的任務(wù).

2.1 序列模式支持向量

每個序列模式spi(1≤i≤m)的支持向量如下:

這里當(dāng)spi(1≤i≤m)包含于Sk(1≤k≤n)，即spi∠Sk時，vk=1(1≤k≤n)，否則vk=0.

所有支持向量的集合構(gòu)成支持矩陣Supp［SDB，SP］，矩陣中Sk(1≤k≤n)作為行，序列模式spi(1≤i≤m)作為列:

sp1 … spi … spm S1…Sk…Sn v11 … v1i … v1m·····vk1 … vki … v km·····vn1 … vni … v nm

當(dāng)spi∠Sk(1≤k≤n，1≤i≤m)，即序列模式spi(1≤i≤m)包含于 Sk(1≤k≤n)時，Supp［Sk，spi］=vki=1;否則Supp［Sk，spi］=vki=0.

表1中序列數(shù)據(jù)庫SDB對應(yīng)的支持矩陣大致表示如下:

a b c e … abcc abfc afac bafc S1 S2 S3 S4 1000…00001111·10001111…01111110· 1111

同理［sp1，sp2，…，spk］表示k分支序列模式，它對應(yīng)的支持向量可以表示為:

r1表示向量中值為“k”的元素個數(shù)，r2表示向量中不為零的元素的個數(shù).

2.2 并發(fā)序列模式挖掘改進(jìn)算法

INPUT:最小支持度 minsup，最小并發(fā)度mincon，序列數(shù)據(jù)庫SDB.

OUTPUT:并發(fā)序列模式集Concurrent Sequential Patterns(CSPs).

METHOD:

(1)在用戶指定的最小支持度minsup下對序列數(shù)據(jù)庫SDB進(jìn)行序列模式挖掘，SP={sp1，sp2，…，spm}為序列模式挖掘結(jié)果;

(2)對于任意spk∈SP and spk.length＞1 //spk.length表示spk中items的個數(shù)

{對于任意 spj∈SP and spj.length=spk.length-1

{如果spj∠spk將spj加入到spk.SubSeqs中}}

(3)按照2.1節(jié)支持矩陣的定義，求SP中每個序列模式的支持向量Supp(spi)，得到支持矩陣Supp［SDB，SP］;

(4)基于支持矩陣Supp［SDB，SP］，根據(jù)

2.1 節(jié)相關(guān)定義

對于任意spi∈SP

對于任意spj∈SP

如果┐(spi∈SubSeq(spj))∧┐(spj∈Sub-Seq(spi))值為真//spi和spj不互相包含

計算spi和spj的相對并發(fā)度

如果concurrence(spi，spj)≥mincon

CSPs=CSPs∪［spi+spj］

(5)根據(jù)并發(fā)序列模式的反單調(diào)特性，循環(huán)通過spi(1≤i≤m)及(k－1)-分支并發(fā)序列模式構(gòu)造k-分支并發(fā)序列模式(k≥3)，找出滿足mincon的并發(fā)序列模式，將其加入CSPs中，具體方法如下:

對于任意spi∈SP

對于任意(k－1)-CSP∈CSPs//(k－1)-CSP表示任意(k－1)-分支并發(fā)序列模式

{對于構(gòu)成(k－1)-CSP的任意序列模式spj如果┐(spi∈SubSeq(spj))∧┐(spj∈SubSeq(spi))為真

計算spi和(k－1)-CSP的相對并發(fā)度

如果 concurrence(spi，(k－1)-CSP)≥mincon

CSPs=CSPs∪［spi+(k－1)-CSP］//新得到的k分支并發(fā)序列加入結(jié)果集

(6)重復(fù)步驟(4)，直到不能產(chǎn)生新的模式為止;

(7)輸出結(jié)果集CSPs.

算法中步驟(2)求得每個spk∈SP對應(yīng)的直接子序列集，從而得到所有序列模式的直接子序列集SubSeqs.步驟(4)、步驟(5)中條件┐(spi∈SubSeq(spj))∧┐(spj∈SubSeq(spi))是為了確保spi、spi的直接子序列集SubSeq(spi)及Sub-Seq(spi)中每個元素的直接子序列集 SubSeq (SubSeq(spi))不包含spj;同理spj、spj的直接子序列集SubSeq(spj)及SubSeq(spj)中每個元素的直接子序列集SubSeq(SubSeq(spj))不包含spi，在算法實現(xiàn)時此處應(yīng)用遞歸調(diào)用來完成.

現(xiàn)有算法通過序列模式的支持向量產(chǎn)生了所有可能的k(k≥2)分支并發(fā)序列模式，沒有考慮到構(gòu)成并發(fā)序列的各序列模式之間的相互包含關(guān)系，導(dǎo)致挖掘結(jié)果中存在大量冗余的平凡并發(fā)模式.本算法求得序列模式挖掘結(jié)果集中每個序列對應(yīng)的直接子序列SubSeqs，遞歸利用Sub-Seqs及SubSeqs中每個序列的直接子序列集檢測序列之間的包含關(guān)系，對挖掘結(jié)果進(jìn)行了大幅精簡.現(xiàn)有算法通過產(chǎn)生(k－1)分支序列模式的支持向量生成k分支并發(fā)序列，產(chǎn)生了大量的中間數(shù)據(jù).本算法直接利用支持矩陣產(chǎn)生k分支序列模式的支持向量來計算并發(fā)度，生成k分支并發(fā)序列模式，避免了大規(guī)模中間數(shù)據(jù)的產(chǎn)生，提高了算法執(zhí)行效率.

3 實驗驗證

對本算法進(jìn)行實驗驗證.最小支持度minsup=50%，最小并發(fā)度mincon=90%.SDB如表2所示，本算法與現(xiàn)有算法挖掘結(jié)果對比如圖2所示.

表2 實驗SDBTable 2 SDB in experiment

圖2 挖掘結(jié)果對比圖Fig.2 Mining results contrast diagram

從圖2可以看出:本算法和現(xiàn)有算法挖掘得到的曲線圖數(shù)據(jù)走勢相似，挖得的并發(fā)序列模式的數(shù)目隨著并發(fā)分支數(shù)的增大都呈現(xiàn)數(shù)倍增大，當(dāng)分支數(shù)到達(dá)某一數(shù)值后，并發(fā)序列模式數(shù)又呈現(xiàn)數(shù)倍減少現(xiàn)象.從圖2還可以看出:根據(jù)并發(fā)序列模式的反單調(diào)特性，本文算法利用(k－1)-分支并發(fā)序列模式和頻繁序列模式spi生成k-分支并發(fā)序列模式，避免了冗余k-分支序列的產(chǎn)生;另外在計算并發(fā)度之前，遞歸利用直接子序列集Subseqs判斷序列模式之間是否存在包含關(guān)系，從而對挖掘結(jié)果又進(jìn)行了大幅精簡，避免了存在相互包含關(guān)系的序列構(gòu)成的并發(fā)序列在挖掘結(jié)果中的出現(xiàn)，也因此使得本文算法挖掘得到的并發(fā)分支數(shù)及其對應(yīng)的并發(fā)序列模式數(shù)都比現(xiàn)有算法有了大幅的減少，從而使挖掘結(jié)果更有實際意義.

4 結(jié)論

結(jié)構(gòu)關(guān)系模式挖掘是本課題組新提出的一種數(shù)據(jù)挖掘理論，并發(fā)序列模式挖掘是結(jié)構(gòu)關(guān)系模式挖掘的一個重要分支.本文從并發(fā)關(guān)系、并發(fā)度角度給出了并發(fā)序列模式的定義、性質(zhì)，并提出了并發(fā)序列模式挖掘的改進(jìn)算法，實驗證明算法正確、有效.在生物信息領(lǐng)域研究中，DNA序列之間關(guān)系的確定主要靠實驗方法，實驗方法費(fèi)時、費(fèi)力、成本高，另外實驗方法還受生物體本身的限制.將結(jié)構(gòu)關(guān)系模式挖掘理論應(yīng)用于DNA序列間關(guān)系的分析，對開拓新的生物信息分析方法，降低生物實驗成本將有重要的意義，這將是本課題組下一步的研究工作.

［1］ CHEN Weiru，ZHANG Yang，CHEN Shanshan，et al.From Sequential Pattterns to Structural Relation Patterns［C］//Li Keqiu，Min Geyong，Zhu Yongxin et al.Proceedings of IEEE International Conference on Scalable Computing and Communications-The 8th Internation Conference on Embedded Computing，ScalCom-EmbeddedCom 2009.Dalian:IEEE Computer Society，2009:148－153.

［2］ CHEN Weiru，CHEN Shanshan，ZHANG Yang.Structural Relation Sequential Pattern Mining［C］// TIAN Xianzhi，ZHU Egui.Proceedings of ICRCCS 2009-2009 International Conference on Research Challenges in Computer Science.Shanghai:IEEE Computer Society，2009:41－44.

［3］ Kuramochi M，Karypis G.GREW:A Scalable Frequent Subgraph Discovery Algorithm［C］//Proceedings of the 2004 IEEE International Conference on Mining(ICDM'04).Brighton:ICDM，2004: 439－442.

［4］ Vanetik N，Gudes E，Shimony S E.Computing Frequent Graph Patterns from Semi-structured Data［C］//ICDM'02 Proceedings of the 2002 IEEE International Conference on Data Mining.Washington:IEEE Computer Society，2002:458－563.

［5］ Huan J，Wang W，Prins J，et al.SPIN:Mining Maximal Frequent Subgraphs from Graph Databases［C］//KDD'04 Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM， 2004:581－586.

［6］ Asai T，Abe K，Kawasoe S，et al.Efficient Substructure Discovery from Large Semi-structured Data［C］//Proceedings of the 2nd SIAM International Conference on Data Mining.Arlington:SIAM，2002:158－174.

［7］ Zaki M J.Efficiently Mining Frequent Trees in a Forest［C］//Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM，2002:71－80.

［8］ Ruckert U，Kramer S.Frequent Free Tree Discovery in Graph Data［C］//Proceedings of 2004 ACM Symposium on Applied Computing.Nicosia:ACM，2004:564－570.

［9］ PEI Jian，LIU Jian，WANG Haixun，et al.Efficiently Mining Frequent Closed Partial Orders［C］//ICDM'05 Proceedings of the fifth IEEE International Conference on Data Mining.Washington:［s.n.］，2005:753－756.

［10］Casas-Garriga G.Summarizing Sequential Data with Closed Partial Orders［C］//Proceedings of the Fifth SIAM International Conference on Data Mining.Newport Beach:SIAM，2005:380－391.

［11］DONG Guozhu，PEI Jian.Mining Partial Orders from Sequences［J］.SEQUENCE DATA MINING Advances in Database Systems，2007，33(10):89－112.

［12］張洋，陳未如，陳姍姍.并發(fā)序列模式挖掘算法研究［J］.計算機(jī)應(yīng)用，2009，29(11):3096－3099.

［13］LU Jing，Osei Adjei，CHEN Weiru，et al.An Apriori-based Algorithm for Mining Concurrent Branch Pattern［C］//Proceeding of the 4th RoEduNet International Conference:Education/Training and Information/Communication Technologies-RoEduNet 2005.Romania:RoEduNet，2005:183－189.

［14］張洋，陳未如，紀(jì)元.互斥關(guān)系模式挖掘算法研究［J］.計算機(jī)工程與設(shè)計，2008，29(22):5776－5779.

［15］CHEN Weiru，LU Jing，Malcolm Keech.Discovering Exclusive Patterns in Frequent Sequences［J］.Int.J.Data Mining，Modeling and Management，2010，2 (3):252－267.

［16］彭弗楠，陳未如，黃寧.結(jié)構(gòu)關(guān)系模式挖掘中的重復(fù)序列模式挖掘［J］.甘肅科技，2008，24(8):20－22.