高俊濤，閆駪藝

(東北石油大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，黑龍江 大慶 163318)

1 問題的提出

事件日志包括流程的活動(dòng)執(zhí)行情況和豐富的上下文信息，基于事件日志進(jìn)行過程挖掘不僅能夠發(fā)現(xiàn)過程的控制流模型，還能提供對業(yè)務(wù)流程的多維分析。然而，某些應(yīng)用場景下的事件日志包含高度敏感的隱私數(shù)據(jù)，無法直接應(yīng)用過程挖掘技術(shù)[1]。例如醫(yī)院患者的診療事件日志既蘊(yùn)藏著寶貴的醫(yī)療過程知識，又包含著患者的個(gè)人隱私，流程一旦涉及手動(dòng)處理，就可能暴露特定個(gè)人的隱私。表1所示為來自某醫(yī)院信息系統(tǒng)的事件日志，假設(shè)攻擊者僅知道某個(gè)患者進(jìn)行了活動(dòng)r和e，根據(jù)該日志數(shù)據(jù)很容易推斷出實(shí)例4記錄了該患者的診療過程，患者的診療活動(dòng)和敏感屬性值都將暴露。近幾年，隨著隱私相關(guān)法律法規(guī)的逐步健全，過程挖掘領(lǐng)域的隱私保護(hù)問題受到越來越廣泛的關(guān)注。

表1 事件日志

過程挖掘領(lǐng)域早期的隱私保護(hù)方法主要采用加密技術(shù)[2-4]實(shí)現(xiàn)。在給定少量背景知識的情況下，即使日志完全加密，仍可能導(dǎo)致隱私泄漏[5]。近年來，研究人員開始將數(shù)據(jù)失真技術(shù)和匿名化技術(shù)應(yīng)用在過程挖掘領(lǐng)域，以抵御常見的攻擊[6-7]。MANNHARDT等[1]將差分隱私概念應(yīng)用于事件數(shù)據(jù)，以確保攻擊者不能識別屬于特定個(gè)人的數(shù)據(jù)；FAHRENKROG-PETERSEN等[8]將傳統(tǒng)的隱私保護(hù)模型K-匿名和T-閉合組合，通過抑制的方式抵御鏈接攻擊。無論采用哪種隱私保護(hù)技術(shù)，事件日志的效用都不可避免地受到損失。因此，如何在給定隱私要求下盡可能高地保留日志效用，是目前過程挖掘中隱私保護(hù)的主要問題。

針對上述問題，ELKOUMY等[9]研究了差分隱私參數(shù)的優(yōu)化方法以獲取更高的效用，為過程挖掘的差分隱私保護(hù)技術(shù)提供了效用優(yōu)化方案；RAFIEI等[10]提出TLKC隱私保護(hù)模型，并采用貪心算法搜索符合隱私要求的活動(dòng)抑制集，然而該方法存在以下問題：

(1)貪婪算法每次選擇一個(gè)當(dāng)前貪婪分?jǐn)?shù)最高的活動(dòng)放入抑制集，忽略了活動(dòng)抑制的組合效應(yīng)，容易陷入局部最優(yōu)解。

(2)貪婪分?jǐn)?shù)的計(jì)算方式過于簡單，不能真實(shí)反映活動(dòng)抑制對日志效用的影響，而且分辨精度不夠，導(dǎo)致貪婪分?jǐn)?shù)相同的活動(dòng)大量存在，難以選擇抑制活動(dòng)。

(3)效用評價(jià)主要依靠匿名模型的質(zhì)量，如F1-分?jǐn)?shù)評估。然而模型質(zhì)量并不能說明日志效用的保留情況，正確的隱私保護(hù)目標(biāo)是得到與原始日志盡可能相似的結(jié)果。

本文提出一種基于遺傳算法的隱私保護(hù)方法搜索活動(dòng)抑制集，主要貢獻(xiàn)包括：

(1)以活動(dòng)抑制集為種群個(gè)體，將遺傳算法引入過程挖掘隱私保護(hù)，從而獲得高效用事件日志，同時(shí)通過改進(jìn)遺傳算子有效避免結(jié)果陷入局部最優(yōu)。

(2)證明活動(dòng)抑制集可行性的必要條件和約簡規(guī)則，縮小遺傳算法搜索空間。

(3)設(shè)計(jì)基于效用的適應(yīng)度函數(shù)，以效用引導(dǎo)種群進(jìn)化過程，為活動(dòng)抑制集的選擇提供合理的決策，保留更多的軌跡變體。

(4)將匿名模型與原模型的平均絕對誤差作為評價(jià)指標(biāo)，直觀反映匿名日志的效用。

2 相關(guān)工作

目前，在過程挖掘領(lǐng)域主要存在加密、差分隱私和匿名化3類隱私保護(hù)技術(shù)，本章對這3類隱私保護(hù)技術(shù)在過程挖掘領(lǐng)域的應(yīng)用及發(fā)展現(xiàn)狀進(jìn)行分析。

BURATTIN等[2]提出一種基于高級加密標(biāo)準(zhǔn)(Advanced Encryption Standard, AES)和Paillier密碼系統(tǒng)的加密方案，該方案允許過程挖掘外包，并確保數(shù)據(jù)集和過程的機(jī)密性；TILLEM等[11]提出一種應(yīng)用加密協(xié)議的Alpha算法進(jìn)行過程發(fā)現(xiàn)，該方法能夠同時(shí)保證用戶和軟件的隱私；RAFIEI等[5]提出一種受控的隱私保護(hù)方式，未經(jīng)授權(quán)的用戶不得訪問高級別的機(jī)密信息，同年又提出一個(gè)框架，為過程挖掘的機(jī)密性提供了通用的解決方案[4]，然而在攻擊者擁有少量背景知識的前提下，這些方案仍存在隱私泄漏的的風(fēng)險(xiǎn)。

對此，MANNHARDT等[1]提出基于(ε，δ)差分隱私的隱私保護(hù)引擎，作為事件日志的唯一訪問節(jié)點(diǎn)，過程挖掘算法只能利用受限的查詢操作獲取事件日志，該方法在理論上保證無論攻擊者是否掌握背景知識，都不能識別個(gè)人信息；FAHRENKROG-PETERSEN等[12]提出隱私保護(hù)的事件日志發(fā)布(PRIvacy-Preserving Event Log publishing, PRIPEL)框架,該框架遵循本地化差分隱私原則，在案例級別而不是整個(gè)日志提供差分隱私保障；ELKOUMY等[9]針對差分隱私帶來的效用損失提出基于效用損失估計(jì)差分隱私參數(shù)ε的優(yōu)化方法，因?yàn)榉墙Y(jié)構(gòu)化事件日志的差分隱私保護(hù)需要引入大量噪聲，使誤差不斷累積，進(jìn)而產(chǎn)生較高錯(cuò)誤率，所以差分隱私不適合非結(jié)構(gòu)化事件日志的隱私保護(hù)。

FAHRENKROG-PETERSEN等[8]提出基于t-閉合和前綴樹的事件日志清理算法(PREfix-Tree based event log Sanitization for t-closeness, PRETSA)，采用K-匿名和T-閉合作為隱私保護(hù)要求，對違反隱私保護(hù)要求的軌跡尋找相似軌跡并進(jìn)行合并，直到達(dá)到隱私保護(hù)要求，該算法通過細(xì)粒度的轉(zhuǎn)換保證了效用的適度損失，但是無法避免非頻繁軌跡的丟失，而這些非頻繁軌跡對過程挖掘至關(guān)重要；RAFIEI等[10]針對事件日志的高維稀疏性，從案例的視角提出一個(gè)TLKC隱私保護(hù)模型，并采用貪婪算法抑制事件獲得匿名日志，該方法比PRETSA算法能夠保留更多的軌跡變體，但是事件日志的匿名化過程容易陷入局部最優(yōu)。針對TLKC隱私保護(hù)模型存在的問題，本文將事件日志匿名化問題轉(zhuǎn)化為活動(dòng)抑制集的種群進(jìn)化問題，通過改進(jìn)遺傳算法、縮小可行解范圍降低匿名事件日志的效用損失。

3 預(yù)備知識

為敘述方便，首先定義過程挖掘隱私保護(hù)相關(guān)的基本概念與表示符號。

給定一個(gè)活動(dòng)集合A，σ∈A*為集合A上的一條活動(dòng)軌跡。σ1σ2,σ1,σ2∈A*，表示σ1是σ2的子軌跡。σ′=(a1,t1),(a2,t2),…,(an,tn)表示簡單軌跡，其中a1,a2,…,an∈A，t1,t2,…,tn∈T為事件的時(shí)間戳，?(ai,ti)inσ′表示σ′中的一個(gè)活動(dòng)時(shí)間對。|σ′|表示軌跡的長度，πk(η)=πk(x)|x∈η為投影到第k個(gè)屬性上的投影序列，其中η是一個(gè)n元組,n≥k。

定義1帶敏感屬性的過程實(shí)例。P=C×(A×T)*×S為過程實(shí)例的域。c∈C為案例ID，s∈S為案例的敏感屬性，σ′為案例的簡單軌跡，P=(c,σ′,s)∈P表示一個(gè)帶敏感屬性的過程實(shí)例。

表2所示為由帶敏感屬性的過程實(shí)例表示的事件日志。

表2 一個(gè)簡單事件日志

定義2TLKC隱私[10]。EL為一個(gè)事件日志，L為背景知識的最大長度，時(shí)間戳精度T∈{seconds,minutes,hours,days}，背景知識的類型type∈{set,mult,seq,rel}，EL(T)為時(shí)間戳精度為T的事件日志。EL(T)滿足TLKC隱私，當(dāng)且僅當(dāng)?σσ′，(c,σ′,s)∈EL，0<|σ|≤L滿足且s∈S，0

定義3違規(guī)軌跡(Violating Trave, VT)[10]。EL為一個(gè)事件日志，σσ′，(c,σ′,s)∈EL，L為背景知識的最大長度，背景知識的類型type∈{set,mult,seq,rel}。如果或則σ是一個(gè)違反TLKC隱私的違規(guī)軌跡。

定義4最小違規(guī)軌跡(Minimal Violating Trace, MVT)[10]。EL為一個(gè)事件日志，違規(guī)軌跡σσ′，(c,σ′,s)∈EL，如果違規(guī)軌跡σ的任何子軌跡都不是事件日志EL的違規(guī)軌跡，則其為一個(gè)最小違規(guī)軌跡。

定義5最大頻繁軌跡(Maximal Frequent Trace, MFT)[10]。EL為一個(gè)事件日志，給定最小支持度閾值Θ，一個(gè)非空軌跡σσ′，(c,σ′,s)∈EL。如果軌跡σ是頻繁的，即σ出現(xiàn)的頻率大于等于Θ，且σ的任意一個(gè)超集都不是頻繁的，則σ是一個(gè)最大頻繁軌跡。

4 基于遺傳算法的隱私保護(hù)方法

遺傳算法是一種基于自然選擇和群體遺傳機(jī)理的搜索算法,其模擬了遺傳過程中的繁殖、雜交和突變現(xiàn)象[13]?；具z傳算法(Simple Genetic Algorithm, SGA)采用經(jīng)典遺傳算子——比例選擇算子、單點(diǎn)交叉算子和基本位變異算子進(jìn)行遺傳[14]。因?yàn)槭录罩緮?shù)據(jù)具有高維稀疏的特點(diǎn)，所以SGA搜索TLKC隱私保護(hù)方案時(shí)往往無法得到高效用的數(shù)據(jù)集。

例如，表2的活動(dòng)可以有不同長度的組合，每種組合都是一個(gè)候選的活動(dòng)抑制集，但不是每個(gè)候選活動(dòng)抑制集都是可行解，即滿足隱私保護(hù)要求。在初始化階段，可能得到全部個(gè)體均不可行的初始種群，導(dǎo)致直接應(yīng)用SGA無法通過選擇個(gè)體進(jìn)行遺傳。

即使隨機(jī)生成的初始種群中有可行解，也不能避免在進(jìn)化過程中再次出現(xiàn)種群大量個(gè)體不可行的情況。這是由于事件日志初始化的抑制集種群中可行解比較稀疏，導(dǎo)致選擇后的種群有很多重復(fù)個(gè)體，種群多樣性變差，即使選擇的種群多樣性好，使用基礎(chǔ)遺傳算子交叉變異后仍會(huì)產(chǎn)生大量不可行解，甚至出現(xiàn)整個(gè)種群都不可行的極端情況。

針對上述問題，本文提出一種遺傳隱私保護(hù)算法。首先分析可行解的必要條件及約簡規(guī)則，縮小遺傳算法搜索空間，提高種群進(jìn)化效率；然后基于日志相似性、軌跡變體和最大頻繁軌跡集合設(shè)計(jì)適應(yīng)度函數(shù)，引導(dǎo)種群向高效用進(jìn)化；最后改進(jìn)遺傳算子與遺傳過程，增加種群的多樣性。

4.1 活動(dòng)抑制集

定義6活動(dòng)抑制集。v_set={mvt1,mvt2,…,mvtn}為事件日志EL的最小違規(guī)軌跡集合，v_a={v|vinmvt?v_set}為v_set中所有活動(dòng)構(gòu)成的集合。supp_set∈2va為EL的一個(gè)活動(dòng)抑制集，簡稱抑制集。

給定隱私要求T=hours，L=3，C=0.5，k=2，背景知識類型multiset，根據(jù)表2可得如表3所示的最小違規(guī)軌跡集合v_set，其活動(dòng)抑制全集v_a={(m,1),(d,3),(r,2),(v,2),(r,3),(c,3),(b,1),(r,1),(e,1)(v,1),(d,2),(c,2)}。對?v∈v_a，權(quán)重w(v)表示抑制包含v的活動(dòng)后原日志軌跡變體的減少量，根據(jù)定義7可知一個(gè)可行活動(dòng)抑制集能移除日志中所有MVT，使日志滿足隱私要求，據(jù)此可以分析出可行抑制集的必要條件和約簡規(guī)則。

表3 最小違規(guī)軌跡

證明假設(shè)?mvt?v_set∧|mvt|=1，抑制集supp_set為可行解，且v∈mvt∧v?supp_set，則通過抑制supp_set不可能移除最小違規(guī)軌跡mvt。匿名日志不可能達(dá)到TLKC隱私要求，與當(dāng)前抑制集是可行解的假設(shè)條件矛盾。證畢。

例如表3中5號最小違規(guī)軌跡僅包含一個(gè)活動(dòng)(r,3)，只有抑制(r,3)才能消除5號最小違規(guī)軌跡，因此(r,3)一定在抑制集中。

定理2抑制集約簡。?v1,v2∈v_a，若f(v2)?f(v1),且w(v1)≤w(v2),則抑制集中v2可由v1替代。

證明因?yàn)橐种苬1較抑制v2可以消除更多的mvt，而且損失的軌跡變體更少，所以v1可以完全替代v2在抑制集中的作用。

例如表3中的(e,1)和(r,1)，抑制前者可以移除4條最小違規(guī)軌跡，抑制后者可以消除1條最小違規(guī)軌跡，且前者的權(quán)重等于后者的權(quán)重，因此活動(dòng)(e,1)可以完全替代活動(dòng)(r,1)。

定理3抑制集約簡。?v1,v2∈v_a，若f(v2)?f(v1),且w(v1)>w(v2)，則兩個(gè)活動(dòng)互斥，即不同時(shí)存在于抑制集中。

證明因?yàn)閒(v1v2)=max(f(v1),f(v2))，且w(v1v2)≥w(v1)>w(v2)，即同時(shí)抑制v1,v2不會(huì)移除更多的MVT，但是可能改變更多的軌跡變體，損失更多的日志信息，所以v1,v2不應(yīng)同時(shí)出現(xiàn)在抑制集中。

例如表3中的(e,1)和(v,1)，兩個(gè)活動(dòng)不應(yīng)該同時(shí)被抑制，其存在互斥關(guān)系。

4.2 日志相似性度量

大部分過程發(fā)現(xiàn)算法通過挖掘活動(dòng)的常見關(guān)系模式(如直接跟隨關(guān)系、互斥關(guān)系、并行關(guān)系)來構(gòu)建業(yè)務(wù)過程模型。因此，根據(jù)過程模型相似性度量[15]，給出基于日志次序關(guān)系的日志相似性度量公式，作為數(shù)據(jù)效用度量的一部分。

定義8基于日志的次序關(guān)系[16]。EL表示一個(gè)基于A的事件日志，令a,b∈A,則：

(1)a>ELb(直接跟隨關(guān)系)，當(dāng)且僅當(dāng)存在一個(gè)軌跡σ=e1,e2,…,en，i∈{1,…,n-1}，使得σ∈EL，ei=a，并且ei+1=b。

(2)a→ELb(因果關(guān)系)，當(dāng)且僅當(dāng)a>ELb，b≯ELa。

(3)a#ELb(互斥關(guān)系)，當(dāng)且僅當(dāng)a≯ELb，b≯ELa。

(4)a‖ELb(并行關(guān)系)，當(dāng)且僅當(dāng)a>ELb，b>ELa。

給定事件日志EL和匿名日志EL′，EL→，EL#，EL‖分別為EL的因果關(guān)系、互斥關(guān)系、并行關(guān)系集合，匿名日志EL′也有同樣的關(guān)系集合，通過這些集合計(jì)算日志的相似性。

w‖為并行關(guān)系的權(quán)重，

(1)

w#為互斥關(guān)系的權(quán)重，

(2)

w→為因果關(guān)系的權(quán)重，

(3)

并行關(guān)系的相似性是用日志EL和EL′所有并行關(guān)系的交集元素?cái)?shù)除以日志EL和EL′所有并行關(guān)系的并集元素?cái)?shù)，即

(4)

對于互斥關(guān)系的相似性，用日志EL和EL′所有互斥關(guān)系的交集元素?cái)?shù)除以日志EL和EL′所有互斥關(guān)系的并集元素?cái)?shù)，即

(5)

對于因果關(guān)系的相似性，用日志EL和EL′所有因果關(guān)系的交集元素?cái)?shù)除以日志EL和EL′所有因果關(guān)系的并集元素?cái)?shù)，即

(6)

兩個(gè)日志EL，EL′的相似性為并行關(guān)系的權(quán)重乘以并行關(guān)系的相似性、互斥關(guān)系的權(quán)重乘以互斥關(guān)系的相似性、因果關(guān)系的權(quán)重乘以因果關(guān)系的相似性這三者的累加和，即

sim(EL,EL′)=w‖×sim‖(EL,EL′)+

w#×sim#(EL,EL′)+w→×sim→(EL,EL′)。

(7)

4.3 遺傳隱私保護(hù)算法

基于活動(dòng)抑制集和日志相似性，本文設(shè)計(jì)的遺傳隱私保護(hù)算法(Genetic Privacy Preserving Algorithm, GPPA)分為初始化、個(gè)體評價(jià)和遺傳操作3個(gè)階段。圖1所示為算法的工作流程。

步驟1初始化。隨機(jī)生成規(guī)模為N的初始群體P0。初始化步驟持續(xù)至搜索到至少一個(gè)滿足TLKC隱私的解為止，編碼方式為multi-hot。

步驟3遺傳操作。多點(diǎn)交叉隨機(jī)生成交叉點(diǎn)會(huì)導(dǎo)致一些無意義的遺傳操作或產(chǎn)生無用個(gè)體，例如交叉點(diǎn)處兩個(gè)體基因型相同、交叉后未產(chǎn)生新個(gè)體或交叉產(chǎn)生的個(gè)體包含的活動(dòng)數(shù)為0。為了減少這些無意義的操作并增加種群多樣性，交叉算子采用改進(jìn)的多點(diǎn)交叉機(jī)制。先確定每對父代個(gè)體基因型中基因不同的位置，在這些位置中生成多個(gè)交叉點(diǎn)，交叉點(diǎn)的個(gè)數(shù)應(yīng)小于不同基因數(shù)的一半，以確保產(chǎn)生新的個(gè)體。如果基因型中的活動(dòng)數(shù)小于1，則對個(gè)體使用變異算子，變異算子采用改進(jìn)的單點(diǎn)變異和多點(diǎn)變異。若變異前，個(gè)體基因型中的活動(dòng)數(shù)小于1，則隨機(jī)生成一個(gè)其他活動(dòng)，其余部分與經(jīng)典的單點(diǎn)變異和多點(diǎn)變異相同。該步驟同時(shí)進(jìn)行交叉與變異，每次迭代比較一對父個(gè)體的適應(yīng)度值，以及多點(diǎn)交叉、單點(diǎn)變異和多點(diǎn)變異后子代個(gè)體的適應(yīng)度值，選取適應(yīng)度值最高的兩個(gè)個(gè)體遺傳到下一代，此處設(shè)計(jì)的最佳保留策略能夠?qū)⒚看淖顑?yōu)解保留在子代中，保證了遺傳算法的收斂性，而交叉和變異算子混合使用的方式顯著提高了種群多樣性，避免了結(jié)果陷入局部最優(yōu)。

步驟4終止條件判斷。達(dá)到迭代次數(shù)后停止迭代，算法結(jié)束。

算法1基于遺傳算法的隱私保護(hù)方法GPPA。

輸入：原始的事件日志EL，L，K，C；敏感屬性S；種群大小N；迭代次數(shù)NG；交叉率Pc；背景知識類型bk_type；頻繁閾值?。

輸出：滿足TLKC隱私的匿名事件日志EL′.

1.生成EL的最大頻繁軌跡集f_set和最小違規(guī)軌跡集v_set

2.for each mvt?v_set do

3. if mvt滿足定理1，then將v∈mvt加入抑制集sup_set，從v_set中移除mvt

5.根據(jù)v_set生成v_a

6.for each v?v_a do

7. if 活動(dòng)v∈mvt滿足定理2，then從v_a中移除v，從v_set中移除mvt

8.if 最小違規(guī)軌跡數(shù)全部移除，returnsup_set

9.else 根據(jù)v_a：

10. 隨機(jī)生成種群大小為N的初始種群P0

11. for eachi∈P0 do

12. if i滿足定理3 ,then對個(gè)體i使用罰函數(shù)

13. else 計(jì)算i的適應(yīng)度值fit

14. while 迭代次數(shù)

15. 對P中個(gè)體進(jìn)行交叉與變異，產(chǎn)生下一代大小為N的種群Q

16. P = Q

17. 計(jì)算P中個(gè)體的適應(yīng)度最大值，對應(yīng)的個(gè)體加入sup_set

18.for each v∈v_set do

19. 抑制事件日志所有實(shí)例中包含活動(dòng)v的事件

20.return EL′

5 實(shí)驗(yàn)設(shè)計(jì)與分析

為驗(yàn)證GPPA的有效性，從所得模型的誤差和匿名日志有效信息的角度，將GPPA和TLKC算法與基線算法進(jìn)行對比。其中，基線算法包括SGA和簡單的K-匿名算法(Simple K-anonymity, SK)，SK算法通過刪除日志中所有出現(xiàn)次數(shù)少于k次的軌跡實(shí)現(xiàn)事件日志匿名；SGA在實(shí)驗(yàn)中不能保證得到可行解，因此對SGA進(jìn)行少量修改以得到可比較的結(jié)果。首先，針對SGA不收斂的問題加入最佳保留策略，將每代的最優(yōu)解保留到下一代，然后用GPPA中的初始種群生成策略搜索到可行解?；?種背景知識、3種隱私強(qiáng)度，本文共進(jìn)行了120組實(shí)驗(yàn)。

過程發(fā)現(xiàn)算法采用主流的inductive miner infrequent[17]，以保證研究結(jié)果的普適性。實(shí)驗(yàn)采用的敗血癥病例日志[18](sepsiscases)是典型的衛(wèi)生保健領(lǐng)域的醫(yī)療事件日志，存在許多罕見的變體，每個(gè)案例代表患者接受治療的過程。該日志包括16個(gè)活動(dòng)、1 050個(gè)實(shí)例、15 214個(gè)事件、846個(gè)變體，即80%的實(shí)例軌跡是唯一的；軌跡的最短長度為3，最大長度為185；最頻繁的軌跡變體出現(xiàn)了35次，每種變體平均出現(xiàn)1.2次。

5.1 實(shí)驗(yàn)參數(shù)設(shè)置

遺傳隱私保護(hù)算法的參數(shù)調(diào)優(yōu)結(jié)果如表4所示。表4確定了遺傳算法的3個(gè)參數(shù)，即種群大小為50，迭代次數(shù)為200，頻繁閾值和交叉率均為0.8。其余實(shí)驗(yàn)參數(shù)設(shè)置如下：敏感屬性設(shè)置為“診斷”；置信值C的上限設(shè)置為0.5，即一個(gè)實(shí)例至少有兩個(gè)不同的敏感值。實(shí)驗(yàn)設(shè)置了3種隱私強(qiáng)度，其中弱隱私參數(shù)為L=2，K=10，C=0.5，中度隱私參數(shù)為L=4，K=40，C=0.4，強(qiáng)隱私參數(shù)為L=6，K=80，C=0.3。適應(yīng)度函數(shù)取法見4.3節(jié)。

表4 參數(shù)調(diào)優(yōu)

5.2 模型誤差實(shí)驗(yàn)分析

圖2所示為日志匿名后所得模型M′與原日志所得模型M的3個(gè)指標(biāo)fitness，precision，F(xiàn)1-score[19]之間的平均絕對誤差MAE的平均值。MAE表征M′與M的偏離程度，其值越大，M′與M的差別越大。從圖2可見所提方法的3個(gè)指標(biāo)與原模型的差別最小，原因在于GPPA采用改進(jìn)遺傳算子有效增加了種群的多樣性，從而增強(qiáng)了算法的全局搜索能力，提高了解的質(zhì)量。由120次實(shí)驗(yàn)結(jié)果分析可知，采用GPPA得到的M′與M的precision誤差縮小3%～7%，原因是新方法著眼于保留日志的次序關(guān)系，而模型precision[20]的計(jì)算與日志中的直接跟隨關(guān)系強(qiáng)相關(guān)，因此包含基于日志的次序關(guān)系的適應(yīng)度函數(shù)可以搜索到精度更高的結(jié)果。另外，4個(gè)方法中SK方法的誤差最大，原因是該方法刪除了大量軌跡變體，使得強(qiáng)隱私下的整個(gè)日志都被刪空，日志信息損失較多。

5.3 日志信息實(shí)驗(yàn)分析

圖3所示為GPPA與對比方法在日志數(shù)據(jù)效用(見4.2節(jié))保留方面的對比結(jié)果，圖4所示為日志剩余軌跡變體數(shù)量的對比結(jié)果。可見，TLKC，SGA，GPPA 3個(gè)使用TLKC隱私要求的方法在set背景知識下的結(jié)果非常相似，均高于使用K-匿名隱私模型的SK方法，原因是這3種方法只需抑制少量活動(dòng)即可抵御具有弱背景知識的隱私攻擊，而SK方法需要抑制的是整條軌跡，因此數(shù)據(jù)效用損失更大。在multiset和sequence這樣較強(qiáng)的背景知識下，GPPA明顯較對比算法保留了更多的數(shù)據(jù)效用和軌跡變體，原因是TLKC方法僅考慮活動(dòng)出現(xiàn)在頻繁軌跡中的次數(shù)這一因素，無法精確區(qū)分不同活動(dòng)的效用，GPPA則在此基礎(chǔ)上加入基于日志的次序關(guān)系和軌跡變體數(shù)量共同引導(dǎo)種群進(jìn)化，容易搜索到高數(shù)據(jù)效用的解。3種方法在relative這種強(qiáng)背景知識下的數(shù)據(jù)效用均較低，這是容易理解的，因?yàn)楣粽哒莆樟藭r(shí)間這樣精確的信息，所以進(jìn)行隱私保護(hù)就需要付出更大的代價(jià)。

由圖3和圖4可見，SK方法在數(shù)據(jù)效用和軌跡變體數(shù)量上獲得的結(jié)果均最差，原因是該方法采用簡單粗暴的方式對日志進(jìn)行粗粒度轉(zhuǎn)換，刪除了大量日志軌跡。值得注意的是，SK方法采用K-匿名隱私模型，不考慮攻擊者是否掌握時(shí)間戳和敏感屬性的概率信息，無法抵御鏈接攻擊，在relative這樣強(qiáng)的背景知識下，不能提供所需的隱私保護(hù)，相比使用TLKC隱私模型的3種方法，只能提供較弱的隱私保障。日志效用和軌跡變體兩組對比實(shí)驗(yàn)結(jié)果顯示，GPPA生成的事件日志保留了更多的軌跡變體和基于日志的次序關(guān)系，表明所設(shè)計(jì)的適應(yīng)度函數(shù)具有較強(qiáng)的篩選能力。

表5所示為兩種遺傳算法方案SGA和GPPA空間規(guī)模的對數(shù)值(log2)對比?？梢姡珿PPA的方案空間較未使用定理的SGA的方案空間有大幅縮減，relative背景知識下的縮減最明顯，原因是relative背景知識會(huì)產(chǎn)生大量長度為1的最小違規(guī)軌跡，利用定理1可顯著縮小方案空間規(guī)模。

表5 兩種遺傳算法方案空間規(guī)模的對數(shù)值(log2)對比

6 結(jié)束語

本文提出一種基于遺傳算法的過程挖掘匿名化算法，將過程挖掘的隱私保護(hù)與效用權(quán)衡問題規(guī)約為活動(dòng)抑制集優(yōu)化問題，并通過研究活動(dòng)抑制集可行性的必要條件和約簡定理，顯著壓縮了抑制集求解空間。根據(jù)主流過程發(fā)現(xiàn)算法的共性，設(shè)計(jì)了綜合效用函數(shù)引導(dǎo)遺傳算法的進(jìn)化過程，并采用最佳個(gè)體保留策略加速算法收斂。最后在真實(shí)的事件日志上與TLKC和基線算法進(jìn)行了對比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，該方法得到的模型精度誤差比TLKC算法縮小3%～7%。未來將研究更高效的優(yōu)化算法，以進(jìn)一步提高匿名化事件日志的可用性。