回歸與矩陣分解的業(yè)務(wù)過程時間預測算法

李帥標,趙海燕,陳慶奎,曹 健

1(上海理工大學 光電信息與計算機工程學院 上海市現(xiàn)代光學系統(tǒng)重點實驗室 光學儀器與系統(tǒng)教育部工程研究中心,上海 200093) 2(上海交通大學 計算機科學與技術(shù)系,上海 200030)E-mail:2609215537@qq.com

1 引 言

為了在這個競爭激烈的社會環(huán)境中生存,企業(yè)必須實現(xiàn)高效的工作流程.時間作為業(yè)務(wù)流程中的重要因素,在近幾年得到了越來越多的關(guān)注,企業(yè)對時間方面的要求也越來越苛刻[1].幸運的是,在信息技術(shù)快速發(fā)展的前提下,越來越多的企業(yè)正在使用業(yè)務(wù)流程信息系統(tǒng)(Process-Aware Information Systems,PAISs)來支持他們的業(yè)務(wù)[2].系統(tǒng)將業(yè)務(wù)流程執(zhí)行的蹤跡和已執(zhí)行活動的信息或?qū)傩杂涗浽诜Q為事件日志的文件中,使企業(yè)積累大量數(shù)據(jù)信息.近些年來,很多學者開始研究如何對業(yè)務(wù)過程的執(zhí)行時間進行預測的問題.

對具有復雜性和靈活性的業(yè)務(wù)過程來說,準確的時間預測并不容易,因為其執(zhí)行方案和性能隨時間會發(fā)生變化,所以準確的預測結(jié)果取決于當前活動上下文環(huán)境[3].上下文環(huán)境對預測的結(jié)果和精確度有很大的影響,如時間、位置以及場景等信息.例如,對于快遞業(yè)務(wù)而言,即使運送的路線相同,也會因為不同的季節(jié)導致的交通狀況不同從而使得時間具有很大差別.因此考慮上下文環(huán)境對業(yè)務(wù)過程進行時間預測是極其重要的.

近年來,矩陣分解算法(Matrix Factorization,MF)的應用越來越廣泛,傳統(tǒng)矩陣分解技術(shù)主要包括奇異值分解(Singular Value Decomposition,SVD)[4]、非負矩陣分解(Non-negative Matrix Factorization,NMF)[5]和概率矩陣分解(Probabilistic Matrix Factorization,PMF)[6]等.上述模型的共同特性是將高維矩陣轉(zhuǎn)換為多個低維矩陣乘積來達到降維的目的,其中以概率矩陣分解應用最為廣泛[7].基于矩陣分解的算法是假設(shè)最終結(jié)果受到多個隱特征的影響,通過隱特征空間將用戶與物品聯(lián)系起來.又因存在的隱特征無法準確的歸納為某些具體特征,故矩陣分解模型也被稱為隱語義模型.因此,在假設(shè)結(jié)果受到隱特征或不可列舉因子影響的前提下,我們結(jié)合矩陣分解思想提出一種基于回歸與聯(lián)合概率矩陣分解(Regression and Collective Probabilistic Matrix Factorization,RCPMF)的算法用于業(yè)務(wù)過程時間的預測.在該算法中,對于可觀測的特征部分,我們使用回歸模型進行學習;對于不可觀測的特征部分(隱因子或潛在特征),我們使用聯(lián)合概率矩陣分解模型進行學習;最后將兩部分的結(jié)果相結(jié)合作為最終的預測結(jié)果.

2 相關(guān)工作

目前很多學者在對業(yè)務(wù)過程時間方面進行預測時都考慮了上下文環(huán)境因素,其實驗結(jié)果表明考慮上下文信息對預測效果有積極影響[12].

文獻[8]中,Polato等人使用了一種ε-SVR機器學習算法對業(yè)務(wù)過程進行剩余執(zhí)行時間的預測.該方法使用業(yè)務(wù)過程的歷史蹤跡活動屬性信息訓練ε-SVR模型,并通過編碼技術(shù)將部分蹤跡的特征轉(zhuǎn)換為適合模型輸入的格式,輸出的值即為估計的剩余執(zhí)行時間.文獻[9,10]中,Folino等人根據(jù)上下文特征對日志蹤跡進行聚類,然后,對于每個聚類創(chuàng)建剩余活動時間預測模型.為了對新的業(yè)務(wù)過程進行預測,首先根據(jù)其特征將其聚類,然后使用屬于特定集群的模型進行預測.在文獻[11]中,作者利用事件日志的上下文信息生成決策樹用來發(fā)現(xiàn)業(yè)務(wù)流程特征之間相關(guān)性.并在此基礎(chǔ)上想對業(yè)務(wù)過程剩余時間進行預測.由于決策樹需要將數(shù)值離散化,降低了方法準確性,故作者沒有提供相關(guān)的預測示例.在文獻[12]中,Polato等人考慮事件的附加屬性以改進時間預測質(zhì)量.該方法利用了在標記變遷系統(tǒng)(An Annotated Transition System)添加樸素貝葉斯分類器和支持向量回歸器的想法,實驗結(jié)果表明考慮附加屬性能夠?qū)︻A測結(jié)果產(chǎn)生積極影響.另外,Leitner 等人[13]根據(jù)記錄的歷史數(shù)據(jù),使用WEKA 機器學習框架來構(gòu)建回歸模型.對于正在運行的業(yè)務(wù)過程,將可用的特征信息輸入預測回歸模型,輸出服務(wù)水平協(xié)議(Service Level Agreement,SLA)值,即時間預測值.通過與規(guī)定的SLA值比較判斷該業(yè)務(wù)過程是否會超時.

以上是對業(yè)務(wù)過程活動時間方面的相關(guān)預測方法的介紹,上述方法雖然考慮活動的附加屬性,但沒有考慮業(yè)務(wù)過程受到了許多因素的影響,雖然有些因素是明確的,但是還有許多難以明確建模的隱因素對業(yè)務(wù)過程時間具有很大的影響.針對這一特點,我們將回歸模型與聯(lián)合概率矩陣分解模型應用于業(yè)務(wù)過程活動的時間預測.實驗結(jié)果表明,該算法考慮了更多的上下文環(huán)境特征,具有更高的預測精度.

3 基于回歸與聯(lián)合概率矩陣分解的業(yè)務(wù)過程時間預測算法

3.1 算法思想介紹

本文所提出的算法是為了解決在不同上下文環(huán)境下可觀測特征與不可觀測特征對結(jié)果有所影響的問題.該算法不只是局限于某種特定的上下文環(huán)境,其上下文環(huán)境可根據(jù)具體的業(yè)務(wù)過程背景有所不同,例如時間上下文或位置上下文等,故該算法在一定程度上滿足靈活性與通用性.

該算法假設(shè)結(jié)果受到可觀測特征與不可觀測特征的影響,在確定上下文環(huán)境類型后,對于可觀測特征部分,使用回歸模型進行學習,對于不可觀測特征部分,使用聯(lián)合概率矩陣分解進行學習.

3.2 問題的定義

為了方便進行形式化描述,本文所使用的符號標記如表1所示.

表1 符號表Table 1 Notations

表1中US表示不同隱特征矩陣所對應的用戶數(shù)目集合,E表示不同用戶隱特征矩陣與物品隱特征矩陣的時間偏差矩陣集合.

3.3 概率矩陣分解模型

目前,以概率方式預測用戶對物品的喜愛程度的矩陣分解模型被大部分的研究人員使用.在本文中,我們使用概率矩陣分解的思想預測業(yè)務(wù)活動的時間偏差.在假設(shè)用戶隱特征向量、物品隱特征向量以及活動時間偏差服從高斯分布的前提下,首先利用貝葉斯公式推導用戶隱特征向量與物品隱特征向量的后驗概率,然后利用隨機梯度下降法(Stochastic Gradient Descent,SGD)進行求導[14].

已知時間偏差數(shù)據(jù)的條件概率分布函數(shù)如公式(1)所示.式中U表示n=1時,U的用戶隱特征矩陣集合,即U=U1;E表示n=1時,E的時間偏差矩陣集合,即E=E1:

(1)

(2)

(3)

根據(jù)貝葉斯推理,隱特征向量U和V的后驗概率分布函數(shù):

(4)

根據(jù)公式(4),通過用戶物品時間偏差矩陣,我們能夠?qū)W習用戶和物品的隱特征向量,相應的概率模型圖如圖1所示.

3.4 RCPMF模型框架

本文提出一種回歸與聯(lián)合概率矩陣分解的業(yè)務(wù)過程時間預測算法,該算法主要有以下幾個部分組成:

圖1 概率矩陣分解圖模型Fig.1 Graph model for probabilistic matrix factorization

1)獲取可觀測特征.根據(jù)已有的事件日志文件,通過數(shù)據(jù)預處理、特征篩選、特征提取等步驟獲取對時間有影響的活動特征.

2)求取時間偏差.根據(jù)可觀測特征,使用普通最小二乘法求取最優(yōu)的回歸系數(shù),通過回歸模型預測活動執(zhí)行時間,最后將預測時間與活動真實執(zhí)行時間之差作為回歸模型預測所產(chǎn)生的時間偏差.

3)學習隱特征矩陣.在假設(shè)時間偏差受到不同隱特征矩陣影響的前提下,將時間偏差矩陣集合E中不同的偏差矩陣融入到概率矩陣分解中,將最大化聯(lián)合后驗概率設(shè)定為目標函數(shù),通過隨機梯度下降算法學習最優(yōu)的用戶隱特征矩陣集合與物品隱特征矩陣集合.

4)預測時間偏差.根據(jù)不同部分的用戶隱特征矩陣和物品隱特征矩陣計算得到在其對應部分所預測的時間偏差.

5)業(yè)務(wù)活動持續(xù)時間預測結(jié)果.將回歸模型預測時間與聯(lián)合概率矩陣分解預測不同部分的時間偏差相結(jié)合作為最終的時間預測結(jié)果.

3.4.1 回歸模型

本文所使用的回歸模型為線性回歸模型,我們假設(shè)在回歸模型中所使用的上下文特征已經(jīng)消除特征多重共線性,線性回歸表示每個特征對整體預測結(jié)果所做的貢獻,通過加權(quán)求和的方式預測最終結(jié)果.假定輸人特征數(shù)據(jù)存放在矩陣Χ中,而回歸系數(shù)存放在向量w中,通過利用平方誤差求出向量w使得預測時間值和真實時間y值之間的差值最小.平方誤差公式如下:

(5)

圖2 聯(lián)合概率矩陣分解圖模型Fig.2 Graph model of collective probabilistic matrix factorization

通過對(5)式使用普通最小二乘法(ordinary least squares)即可求出最優(yōu)系數(shù)向量.

3.4.2 聯(lián)合概率矩陣分解模型

在不確定上下文環(huán)境時,我們不知道其結(jié)果受到多少種因素或場景的影響,因此將影響因素數(shù)目或場景數(shù)目設(shè)置為n,場景集合S={S1,S2,…,Sn},故所提出的聯(lián)合概率矩陣分解部分的圖模型如圖2所示.

根據(jù)模型得用戶數(shù)目集合US={US1,US2…USn},用戶隱特征矩陣集合U={U1,U2,…,Un},時間偏差矩陣集合E={E1,E2,…,En}.為了便于理解推導過程,在此處將影響結(jié)果的場景數(shù)目設(shè)置為2進行推導,即S={S1,S2}.

聯(lián)合概率矩陣分解圖模型基于以下假設(shè):

1)假設(shè)物品隱特征矩陣Vi,場景S1中用戶隱特征矩陣U1的先驗概率服從高斯分布且相互獨立,則滿足下列公式.

(6)

(7)

其中N(x|μ,σ2)表示均值為μ,方差為σ2的高斯分布概率密度函數(shù),I為單位矩陣.同理可得場景S2中用戶隱特征矩陣U2滿足公式(8).

成分不同，安全劑量不同。對乙酰氨基酚的日常最大用量為每4小時1次，每次15mg/kg，如孩子體重超過44千克，可參考成人劑量1000mg/次或4000mg/日。布洛芬的日常最大用量為每6小時1次，每次10mg/kg，如孩子體重超過44千克，可參考成人劑量600mg/次或2400mg/日。

(8)

(9)

(10)

用戶與物品之間存在的時間偏差受不同場景的影響,所以聯(lián)合概率矩陣分解部分將不同場景中用戶與物品的關(guān)系矩陣的分解結(jié)合起來.由圖2可以推出U1,U2,V的后驗概率分布函數(shù).后驗分布函數(shù)的對數(shù)函數(shù)滿足公式(11):

(11)

其中,C是一個獨立于參數(shù)的常量.最大化方程(11)等價于最小化方程(12):

(12)

根據(jù)隨機梯度下降法,如下所示:

(13)

(14)

(15)

公式(13)-公式(15)在算法中用于更新各個隱特征向量值.

4 實驗和結(jié)果分析

4.1 實驗數(shù)據(jù)

為了驗證模型,本文使用兩種不同業(yè)務(wù)過程的數(shù)據(jù)集.第一個實驗數(shù)據(jù)集來自國內(nèi)某服裝企業(yè)2015年1月-2018年4月在面料采購環(huán)節(jié)所記錄的真實數(shù)據(jù),該數(shù)據(jù)集反應了不同面料供應商在生產(chǎn)不同類型的面料時所花費時間的真實情況.原始數(shù)據(jù)集包括133個供應商,7337種面料類型,11219條供應商生產(chǎn)面料所需時間的記錄.第二個實驗數(shù)據(jù)集來自福特GoBike自行車2017年6月-2018年6月所記錄騎行時間的真實數(shù)據(jù),該數(shù)據(jù)集反應不同年齡的用戶在行駛不同路徑所需時間的真實情況.原始數(shù)據(jù)集包括53種用戶年齡等級,10895條行駛路徑,35658條不同年齡等級用戶騎行不同路徑所需時間的記錄.

4.2 場景分析

對數(shù)據(jù)集1與數(shù)據(jù)集2中過程持續(xù)時間分析如圖3所示.

圖3 業(yè)務(wù)過程活動持續(xù)時間分析Fig.3 Business process activity duration analysis

圖3(a)表示企業(yè)在不同季節(jié)采購面料的時間分布,圖3(b)圖表示用戶在不同季節(jié)騎行的時間分布.從圖中可粗略估計,數(shù)據(jù)集1中,冬季訂購面料所需要的時間比夏季要多;數(shù)據(jù)集2中,秋季騎行時間比冬季要長.通過對數(shù)據(jù)集的分析與探索,我們發(fā)現(xiàn)活動時間隨著不同季節(jié)呈現(xiàn)出季節(jié)性變動規(guī)律;另一方面,根據(jù)經(jīng)驗所得,在不同季節(jié)中,這兩種活動時間都會受到一定影響.因此在本文中考慮上下文場景為時間因素,且主要研究季節(jié)因素的影響.

根據(jù)季節(jié)效應的特性,我們將n取值為4,得US={US1,US2,US3,US4},U={U1,U2,U3,U4},E={E1,E2,E3,E4},令A=U1,B=U2,C=U3,D=U4,E=E1,F=E2,G=E3,H=E4,σE=σE1,σF=σE2,σG=σE3,σH=σE4,其中ABCD表示四季所對應的用戶隱特征矩陣,EFGH表示四季所對應的時間偏差矩陣.

假設(shè)用戶與物品之間存在的時間偏差受不同季節(jié)的影響,通過3.4.2小節(jié)中聯(lián)合概率矩陣分解模型推導過程將不同季節(jié)的用戶與物品的關(guān)系矩陣的分解、夏季用戶與物品的關(guān)系矩陣的分解、秋季用戶與物品的關(guān)系矩陣的分解以及冬季用戶與物品的關(guān)系矩陣的分解結(jié)合起來,取后驗分布函數(shù)的對數(shù)函數(shù)滿足公式(16).

(16)

最大化方程(16)并根據(jù)SGD得各部分隱特征向量迭代公式:

(17)

(18)

(19)

(20)

(21)

4.3 評價指標

本文使用均方根誤差(Root Mean Squared Error,RMSE)作為評測指標.RMSE計算實際觀測值與預測值之間的標準差,其值越小表示模型預測的結(jié)果要好.計算公式如下:

(22)

4.4 方法比較

為了驗證RCPMF方法的預測精度,將該方法與一些時間預測方法進行比較.在本文中使用歷史平均值(Mean Value,MV)方法、移動平均(Moving Average,MA)方法、指數(shù)平滑(Exponential Smoothing,ES)方法、K近鄰(k-Nearest Neighbour,KNN)方法、線性回歸(Linear Regression,LR)以及支持向量回歸(Support Vector Regression,SVR)方法與所提出RCPMF模型進行比較.為了驗證模型的效果,我們將訓練集與測試集分別按照8:2、6:4、4:6以及2:8進行劃分[15].另外,實驗過程部分放置在GitHub(1)https://github.com/woyaogithub/Collective-probabilistic-matrix-factorization.git.

4.5 迭代次數(shù)分析

圖4 不同迭代次數(shù)的RMSE值(數(shù)據(jù)集1)Fig.4 RMSE values for different iterations(data set 1)

圖5 不同迭代次數(shù)的RMSE值(數(shù)據(jù)集2)Fig.5 RMSE values for different iterations(data set 2)

圖6 不同正則化參數(shù)值的RMSE值(數(shù)據(jù)集1)Fig.6 RMSE values for different regularization parameter values(data set 1)

圖7 不同正則化參數(shù)值的RMSE值(數(shù)據(jù)集2)Fig.7 RMSE values for different regularization parameter values(data set 2)

在聯(lián)合概率矩陣分解部分,本文使用SGD對目標函數(shù)進行求解,因此在本節(jié)分析迭代次數(shù)對RCPMF模型的影響.為了實驗方便,在后續(xù)實驗中設(shè)置λF、λG、λH、λA、λB、λC、λD與λ值相同.

在數(shù)據(jù)集1中,我們將訓練集與測試集按照8:2進行劃分.通過多次實驗,設(shè)置學習速率α=0.001,潛在特征向量維數(shù)d=5,參數(shù)λ設(shè)置為由4.5小節(jié)得到的實驗結(jié)果.迭代次數(shù)對預測精度的影響如圖4所示.

如圖4所示,橫坐標表示算法迭代的次數(shù),縱坐標表示RMSE值.由圖可知,隨著迭代次數(shù)的增加,算法的RMSR值下降并趨于平穩(wěn),說明我們的算法達到了收斂狀態(tài).故在后面的實驗,我們均選擇迭代次數(shù)的值為50.

在數(shù)據(jù)集2中,我們同樣將訓練集與測試集按照8:2進行劃分.通過多次實驗,設(shè)置學習速率α=0.0005,潛在特征向量維數(shù)d=5,參數(shù)λ設(shè)置為由4.5小節(jié)得到的實驗結(jié)果.迭代次數(shù)對預測精度的影響如圖5所示.

如圖5所示,橫坐標表示算法迭代的次數(shù),縱坐標表示RMSE值.由圖可知,隨著迭代次數(shù)的增加,算法的RMSE值下降并趨于平穩(wěn),說明我們的算法達到了收斂狀態(tài).同樣,我們也選擇50作為后面實驗的迭代次數(shù)值.

4.6 正則化參數(shù)分析

正則化參數(shù)用來防止模型過擬合,所以正則化參數(shù)值的選擇對模型預測的精度具有很大影響.在數(shù)據(jù)集一中,我們選擇與4.4小節(jié)中相同的的數(shù)據(jù)集與參數(shù)值.正則化參數(shù)λ的對預測精度的影響,如圖6所示.

根據(jù)圖6觀察可知,正則化參數(shù)λ的值對預測時間的精度有著一定的影響.在[0.9,1.8]范圍內(nèi),隨著λ值的增加,模型預測的RMSE值呈下降趨勢,但是,當λ的值超過1.8以后,模型預測時間的RMSE值開始增加.因此,在第一個數(shù)據(jù)集中,我們將正則化參數(shù)λ設(shè)置為1.8.

同樣,在第二個數(shù)據(jù)集中,我們選擇與4.4小節(jié)中相同的的數(shù)據(jù)集與參數(shù)值.正則化參數(shù)λ的對預測精度的影響,如圖7所示.

根據(jù)圖7觀察可知,正則化參數(shù)λ的值對預測時間的精度有著一定的影響.在[1.48,1.5]范圍內(nèi),隨著λ值的增加,模型預測的RMSE值呈下降趨勢,但是,當λ的值超過1.5以后,模型預測時間的RMSE值呈上升趨勢.因此,在第二個數(shù)據(jù)集中,我們將正則化參數(shù)λ設(shè)置為1.5.

4.7 對比實驗分析

本節(jié)主要比較本文所提出的RCPMF算法與對比算法的預測效果,從實驗數(shù)據(jù)隨機抽取20%、40%、60%以及80%的訓練集對算法進行實驗.數(shù)據(jù)集1實驗結(jié)果如表2所示,數(shù)據(jù)集2實驗結(jié)果如表3所示.

表2 不同預測方法的RMSE值(數(shù)據(jù)集1)Table 2 RMSE values for different prediction methods(data set 1)

由表2和表3所示,隨著訓練集的增大,本文所提出的方法在兩個數(shù)據(jù)集中均比其對比算法的的精度高.另外,隨著訓練集的數(shù)目增大,訓練模型預測的效果的精度呈上升趨勢.其中,在數(shù)據(jù)集1中,模型預測最好的情況下,其RMSE值比其他方法降低了1.032～10.654;在數(shù)據(jù)集2中,模型預測最好的情況下,其RMSE值比其他方法降低了4.305～13.336.通過上述分析,模型在數(shù)據(jù)集1中所取的最好結(jié)果參數(shù)組合為:訓練集與測試集比例為8:2,迭代次數(shù)值為50,學習速率值為0.001,正則化參數(shù)值為1.8;模型在數(shù)據(jù)集2中所取的最好結(jié)果參數(shù)組合為:訓練集與測試集比例為8:2,迭代次數(shù)值為50,學習速率值為0.0005,正則化參數(shù)值為1.5.

表3 不同預測方法的RMSE值(數(shù)據(jù)集2)Table 3 RMSE values for different prediction methods(data set 2)

5 總結(jié)與展望

本文結(jié)合回歸技術(shù)與聯(lián)合概率矩陣分解模型提出了一種應用于不同上下文場景下的時間預測方法.在考慮上下文場景為時間因素且分析季節(jié)因素影響的條件下,結(jié)合業(yè)務(wù)過程活動在執(zhí)行過程中可觀測特征部分與不可觀測特征部分進行時間預測.通過對數(shù)據(jù)集不同程度的劃分并將本文提出的算法與相關(guān)業(yè)務(wù)活動時間預測方法進行比較,在以RMSE作為評價指標的前提下,發(fā)現(xiàn)該算法具有更高的預測精度.本文所提出的模型為預測活動的執(zhí)行時間,所以下一步我們會考慮以該模型為基礎(chǔ),將當前預測的活動時間及其自身屬性添加到特征信息列表中,在此基礎(chǔ)上對該業(yè)務(wù)過程的下一個活動執(zhí)行時間進行預測,通過此方法以達到預測業(yè)務(wù)過程的剩余執(zhí)行時間的目的.