基于軟定時自動機(jī)的用戶行為建模

許小媛　紀(jì)河　黃黎　李從明

摘 要： 提出一種軟定時轉(zhuǎn)變自動機(jī)，識別更大范圍的用戶行為歷史。該軟建模的框架用戶模型可以在類似網(wǎng)絡(luò)學(xué)習(xí)的虛擬平臺中實時地評估用戶的動態(tài)行為，通過評估觀察到的行為中的時間偏差、額外的或省去的行為量來評估用戶行為。當(dāng)觀察到的行為只部分滿足給定的行為模型約束時，該模型也可以用于用戶歷史行為的部分識別。相對于標(biāo)準(zhǔn)的布爾模型的識別，當(dāng)多個用戶模型存在偏差量時，該方法通過預(yù)測、投影和其他已知的技術(shù)更適用于用戶實時支持系統(tǒng)，引導(dǎo)生成系統(tǒng)支持。基于日志的網(wǎng)絡(luò)學(xué)習(xí)平臺和軟時間自動機(jī)的規(guī)劃實驗證明了該模型的表現(xiàn)力和有效性。

關(guān)鍵詞： 用戶行為； 時變自動機(jī)； 自動規(guī)劃； 建模； 軟定時； 匹配

中圖分類號： TN98?34； G231.5 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2018）15?0165?04

User behavior modeling based on soft timed automata

XU Xiaoyuan1， JI He1， HUANG Li1， 2， LI Congming1

（1. College of Information and Mechanical Engineering， Jiangsu Open University， Nanjing 210017， China；

2. College of Computer Science and Technology， Nanjing University of Aeronautics and Astronautics， Nanjing 210016， China）

Abstract： A soft timed transition automata （TTA） is proposed to recognize the user history behavior in a wider range. The user behavior model constructed with soft modeling can evaluate the dynamic behavior of users in real time in the virtual platform similar to network learning. The time deviation， additional or omitted behavior amount observed in estimation are used to evaluate the user behavior. When the observed behavior partially satisfies the given constraint of behavior model， the model can be used to the part recognition of user history behavior. In comparison with the standard Boole model recognition， the proposed method is more suitable for the user real?time support system by means of prediction， projection and other know techniques while the deviation exists in a large number of user model， and can be used to generate the system support. The expressivity and validity of the model were verified with planning experiment of network learning platform based on logs and soft timed automata.

Keywords： user behavior； time varying automaton； automated planning； modeling； soft timing； matching

0 引 言

目前，在有關(guān)用戶行為建模的研究中，一些方法側(cè)重通過正式的“用戶會話”[1?3]和“用戶行為”的生成措施，分析用戶的行為歷史[4]或行程歷史[1]。多數(shù)現(xiàn)有的方法側(cè)重于用戶歷史的后驗分析，從而描述網(wǎng)站的使用模式，更好地實現(xiàn)目標(biāo)用戶類型尋址。

在自適應(yīng)的Web系統(tǒng)領(lǐng)域，文獻(xiàn)[5?6]提出實時監(jiān)測和用戶建模/分析是為了實現(xiàn)即時適應(yīng)。文獻(xiàn)[7?9]提出一些基于自動機(jī)的模型，其中用戶歷史的定義是“動作序列”，并由代表行為模式的有限狀態(tài)的自動機(jī)進(jìn)行解析，作為用戶行為模型。這種方法的缺點是把符合行為模型及偏離約束條件的用戶明顯分開了。實際上，在這種情況下，行為模型只是一種“最小必要行為模式”，并且不允許任何偏離。因此，所能給用戶的信息是他/她的歷史行為被模型自動機(jī)接受或拒絕，而并不能表明他/她的行為接近或偏離行為模型的程度。

本文簡要介紹基于自動機(jī)的用戶行為模型，并且說明在學(xué)習(xí)平臺中如何將其用于域和行為建模。在前文模型的基礎(chǔ)上，本文介紹在一般動態(tài)虛擬系統(tǒng)的軟用戶建模方法。通過案例定量比較這兩個模型，并討論行為識別的實驗結(jié)果。

1 用戶行為的時間自動機(jī)

用戶在結(jié)構(gòu)化界面環(huán)境中操作的行為域（如網(wǎng)絡(luò)學(xué)習(xí)平臺、郵件客戶端、內(nèi)容管理平臺）可以很容易地由一個隨著時間約束擴(kuò)展的狀態(tài)轉(zhuǎn)變圖描述。由狀態(tài)轉(zhuǎn)變圖表示用戶可以執(zhí)行的動作。

定時轉(zhuǎn)變自動機(jī)（TTA）[10]是一種有限狀態(tài)機(jī)，能夠識別定時的口令，即由給定的字母集[Σ]和時間值符號構(gòu)成的序列對?？梢园研蛄袑醋鳂?biāo)注著發(fā)生時間的、記錄用戶事件或行為的日志記錄序列。

在TTA中，只有滿足某些時間條件時（如在給定的時間間隔內(nèi)提交在線作業(yè)），才可以限制某個行為的執(zhí)行，即某個轉(zhuǎn)變的發(fā)生，那么域名自動機(jī)被定義為合法轉(zhuǎn)變或相當(dāng)于在系統(tǒng)可以進(jìn)行的行為的合法程序。

用戶行為可以由時間自動機(jī)描述，其接受的語言是域自動機(jī)的一個子語言。即如果用戶行為的序列由自動機(jī)解析，相應(yīng)的用戶行為就被確認(rèn)。文獻(xiàn)[7?8]提出了描述用戶行為的TTA的應(yīng)用。

2 算法

定義（軟定時轉(zhuǎn)變自動機(jī)）：軟定時轉(zhuǎn)變自動機(jī)（STTA）是一個數(shù)組[As=（A，?，π，σ，θ）]，其中：[A]表示定時轉(zhuǎn)變自動機(jī)；[?]表示軟匹配的度量；[π]表示額外輸入符號的度量；[σ]表示狀態(tài)跳過的度量；[θ]表示時限違背的度量。

定義（軟定時語言）：軟定時轉(zhuǎn)變自動機(jī)的語言[L（As）]，[As=（A，?，π，σ，θ）]是通過由定時口令形成的成組的集合，對應(yīng)于自動機(jī)的從[S0]開始的持續(xù)運行，及其軟運行的最小行為偏差?？梢钥闯觯琔BM中定義的滿足時間約束的所有時間口令是一定程度的行為偏差的“軟接受”。自動機(jī)接受的所有時間口令也都是[γ=0]時軟接受的。雖然不是所有的時間口令被自動機(jī)所接受，但滿足時間約束的所有軟接受[γ>0]。

設(shè)一個軟時間轉(zhuǎn)變自動機(jī)[2，9][As]，其中[s]表示當(dāng)前狀態(tài)，[w]表示當(dāng)前時間口令，[γ]表示行為偏差測度的現(xiàn)狀評價，本文建立一個算法SoftParse（[s，w，γ]），對應(yīng)于給定時間口令評價中可能出現(xiàn)的不同偏差，返回一組解析偏差的評估值。一個口令的整體偏差度量是：

[γ（w，As）=min{SoftParse（s0，w，0）}]

如果[w]由相應(yīng)的時間轉(zhuǎn)變自動機(jī)[A]接受，那么[γ（w，As）=0]。或者，等價于[L（A）∈L（As）]。

3 實驗

表1～表3表示軟性偏差的三個案例。

1） 采用軟匹配[4][?（a，b）]的量度和時間約束違背的量度[θ（δ，τ）]，γ是更新的：

[γ：=γ+?（a，b）+θ（δ，τ）]

輸入口令中的符號a在連接的[si]和[sj]的邊緣與符號b對應(yīng)。

2） 采用額外的輸入符號的度量[11][π（a，si）]，γ是更新的：

[γ：=γ+π（a，si）]

在輸入口令中的解析符號a時，狀態(tài)[si]記作目前狀態(tài)。

3） 采用狀態(tài)跳過的度量[σ（si，sj）]，γ是更新的：

[γ：=γ+σ（si，sj）]

自動機(jī)由[si]狀態(tài)轉(zhuǎn)變到[sj]時，沒有解析輸入口令中的任何符號。

通過ILOG CPLEX[3，12]求解，在英特爾奔騰IV 3.00 GHz 1 GB RAM運行，Linux操作系統(tǒng)上進(jìn)行測試。在下面的一些例子中，詳細(xì)顯示提出的方法來計算給定的軟運行的偏差γ。n和a函數(shù)的值在表4～表6中定義。

測試分為三類[13?14]：

1） 當(dāng)完全識別時，最后的γ函數(shù)等于零；

2） 描述用戶行為的活動序列定時口令至少有一個活動少于容許序列的情況；

3） 在2）的情況下，動作序列反而形成一個額外的沒有列在用戶模型ubl中的輸入動作。

系統(tǒng)完全接受表4，表5中描述的Seql和Seq2序列。用于研究STTA算法與TTA的相同點。

系統(tǒng)完全接受表4，表5中描述的Seql和Seq2序列。用于研究STTA算法與TTA的相同點。

序列Seq6=[（0，登錄），（10，作業(yè)），（12，主菜單），（40，測驗），（50，提交），（70，注銷）]，取而代之的是一個序列，其中至少一個行為（上課）相對于一個容許序列缺失。在該案例中[15]，進(jìn)行了前三個行為（登錄，作業(yè)，主菜單）之后，適用于從[s1]狀態(tài)到[s2]狀態(tài)過渡的[a]函數(shù)，不解析任何符號，并增加懲罰[γ1=σ（s1，s2）=30]，?函數(shù)是為了以ub1模型中的上課行為替代用戶行為序列中的測驗行為，增加一項懲罰[γ2=?]（測驗，上課）=20。在算法的這一步驟中，方法二優(yōu)于方法一（[γ2<γ1]）。然而，在需要持續(xù)處理行為序列時，方法二必須通過測驗和注銷來編輯[?]，總體上[γ2=130]。方法一可以直接轉(zhuǎn)去繼續(xù)處理行為序列，最后可得[γ1=30]。

序列Seq7=[（0，登錄），（10，作業(yè)），（12，主菜單），（15，評論），（20，主菜單），（25，上課），（55，測驗），（60，提交）， （70，注銷）]已被用于第三類的測試[16]。在這種情況下，對于ub1接受的合法行為序列，有一個額外的輸入行為（評論）。該算法經(jīng)過處理前三個行為后，既適用于通過函數(shù)n（view，[si]）添加一個gap到自動機(jī)，而不改變狀態(tài) （[γ1=]π（view，[s1]）=70），通過函數(shù)?（view，assignment），用assignment（作業(yè)）代替用戶行為view（評論）（[γ2=]?（view，assignment=10）。當(dāng)STTA違背時間約束[17?18]，?（view，lesson）=5的替代不適用。當(dāng)[γ2<γ1]時，算法繼續(xù)在該分支處理剩余的行為序列，直到最后，[γ2=]10，所以第一分支是經(jīng)過精簡的一個過程。

4 結(jié) 論

本文引入一個原始的用戶行為模型，當(dāng)部分違背約束條件時，允許用戶行為的軟識別；多個用戶模型存在偏差時，可以量化評估違背的程度，更適用于用戶實時支持系統(tǒng)，引導(dǎo)生成系統(tǒng)支持。將來的工作可以考慮高效的軟解析算法的生成，以及對記錄歷史的自動提取模型技術(shù)的研究。

參考文獻(xiàn)

[1] BERENDT B， SPILIOPOULOU M. Analysis of navigation behavior in websites integrating multiple information systems [J]. Journal of the VLDB， 2000， 9（1）： 56?75.

[2] MASSEGLIA F， PONCELET P， TEISSEIRE M， et al. Web usage mining： extracting unexpected periods from weblogs [C]// Proceedings of 2005 the 5th IEEE International Conference on Data Mining. Houston： IEEE， 2005： 39?65.

[3] 劉嘯濱，郭兵，沈艷，等.嵌入式軟件體系結(jié)構(gòu)級能耗建模方法[J].軟件學(xué)報，2012，23（2）：230?239.

LIU Xiaobin， GUO Bing， SHEN Yan， et al. Embedded software architecture level energy consumption modeling method [J]. Software journal， 2012， 23（2）： 230?239.

[4] 陳碧歡.基于需求和體系結(jié)構(gòu)的軟件系統(tǒng)自適應(yīng)方法[D].上海：復(fù)旦大學(xué)，2014.

CHEN Bihuan. Software system adaptive method based on requirement and architecture [D]. Shanghai： Fudan University， 2014.

[5] BRUSILOVSKY P， KOBSA A， NEJDL W. The adaptive Web： methods and strategies of Web personalization [J]. Lecture notes in computer science， 2007（5）： 377?408.

[6] BRUSILOVSKY P， MILLAN E. User models for adaptive hypermedia and adaptive educational systems [EB/OL]. [2007?11?21]. https：//www.scss.tcd.ie/Owen.Conlan/CS7IS5/10.1.1.87.5703.pdf.

[7] CERI S， DANIEL， DEMALDE V， et al. An approach to user?behavior?aware web applications [C]// Proceedings of 2005 LNCS. [S.l.]： Springer， 2005： 417?428.

[8] CERI S， DANIEL F， FACCA F M. Modeling Web applications reacting to user behaviors [J]. Computer networks， 2006， 50（10）： 1533?1546.

[9] MILANI A， SURIANI S. Modeling user behaviour by planning [J]. Proceedings of World Academy of Science Engineering & Technology， 2008， 40： 237?241.

[10] ALUR R， DILL D L. A theory of timed automata [J]. Theoretical computer science， 1994， 126（2）： 183?235.

[11] 王晶，戎玫，張廣泉，等.基于概率模型檢測的Web服務(wù)組合驗證[J].計算機(jī)科學(xué)，2012，39（1）：120?123.

WANG Jing， RONG Mei， ZHANG Guangquan， et al. Web service composition verification based on probabilistic model detection [J]. Computer science， 2012， 39（1）： 120?123.

[12] 李力行，金芝，李戈.基于時間自動機(jī)的物聯(lián)網(wǎng)服務(wù)建模和驗證[J].計算機(jī)學(xué)報，2011，34（8）：1365?1377.

LI Lixing， JIN Zhi， LI Ge. Modeling and verification of internet services based on time automata [J]. Computer journal， 2011， 34（8）： 1365?1377.

[13] 范貴生，虞慧群，陳麗瓊，等.策略驅(qū)動的可靠嵌入式系統(tǒng)建模及分析方法[J].軟件學(xué)報，2011，22（6）：1123?1139.

FAN Guisheng， YU Huiqun， CHEN Liqiong， et al. Modeling and analysis method of reliable embedded system driven by policy [J]. Software journal， 2011， 22（6）： 1123?1139.

[14] ZHOU Y， BARESI L， ROSSI M. Towards a formal semantics for UML/MARTE state machines based on hierarchical timed automata [J]. Journal of computer science and technology， 2013， 28（1）： 188?202.

[15] HAYDEN CM， MAGILL S， HICKS M， et al. Specifying and verifying the correctness of dynamic software updates [C]// Proceedings of 2012 the 4th International Conference on Verified Software： Theories， Tools， Experiments. [S.l.]： Springer， 2012： 278?293.

[16] BARESI L， GHEZZI C， MOTTOLA L. Loupe： verifying publish?subscribe architectures with a magnifying lens [J]. IEEE transactions on software engineering， 2011， 37（2）： 228?246.

[17] CHEN H B， YU J， HANG C Q， et al. Dynamic software updating using a relaxed consistency model [J]. IEEE transactions on software engineering， 2011， 27（5）： 679?694.

[18] DIMITAR P， DANG H. Reasoning about QoS contracts in the probabilistic duration calculus [J]. Electronic notes in theoretical computer science， 2010， 238（6）： 41?62.