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

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

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

中圖分類(lèi)號(hào)： TN98?34； G231.5 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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)用戶(hù)行為建模的研究中，一些方法側(cè)重通過(guò)正式的“用戶(hù)會(huì)話(huà)”[1?3]和“用戶(hù)行為”的生成措施，分析用戶(hù)的行為歷史[4]或行程歷史[1]。多數(shù)現(xiàn)有的方法側(cè)重于用戶(hù)歷史的后驗(yàn)分析，從而描述網(wǎng)站的使用模式，更好地實(shí)現(xiàn)目標(biāo)用戶(hù)類(lèi)型尋址。

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

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

1 用戶(hù)行為的時(shí)間自動(dòng)機(jī)

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

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

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

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

2 算法

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

定義（軟定時(shí)語(yǔ)言）：軟定時(shí)轉(zhuǎn)變自動(dòng)機(jī)的語(yǔ)言[L（As）]，[As=（A，?，π，σ，θ）]是通過(guò)由定時(shí)口令形成的成組的集合，對(duì)應(yīng)于自動(dòng)機(jī)的從[S0]開(kāi)始的持續(xù)運(yùn)行，及其軟運(yùn)行的最小行為偏差。可以看出，UBM中定義的滿(mǎn)足時(shí)間約束的所有時(shí)間口令是一定程度的行為偏差的“軟接受”。自動(dòng)機(jī)接受的所有時(shí)間口令也都是[γ=0]時(shí)軟接受的。雖然不是所有的時(shí)間口令被自動(dòng)機(jī)所接受，但滿(mǎn)足時(shí)間約束的所有軟接受[γ>0]。

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

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

如果[w]由相應(yīng)的時(shí)間轉(zhuǎn)變自動(dòng)機(jī)[A]接受，那么[γ（w，As）=0]?；蛘?，等價(jià)于[L（A）∈L（As）]。

3 實(shí)驗(yàn)

表1～表3表示軟性偏差的三個(gè)案例。

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

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

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

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

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

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

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

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

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

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

測(cè)試分為三類(lèi)[13?14]：

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

2） 描述用戶(hù)行為的活動(dòng)序列定時(shí)口令至少有一個(gè)活動(dòng)少于容許序列的情況；

3） 在2）的情況下，動(dòng)作序列反而形成一個(gè)額外的沒(méi)有列在用戶(hù)模型ubl中的輸入動(dòng)作。

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

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

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

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

4 結(jié) 論

本文引入一個(gè)原始的用戶(hù)行為模型，當(dāng)部分違背約束條件時(shí)，允許用戶(hù)行為的軟識(shí)別；多個(gè)用戶(hù)模型存在偏差時(shí)，可以量化評(píng)估違背的程度，更適用于用戶(hù)實(shí)時(shí)支持系統(tǒng)，引導(dǎo)生成系統(tǒng)支持。將來(lái)的工作可以考慮高效的軟解析算法的生成，以及對(duì)記錄歷史的自動(dò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í)能耗建模方法[J].軟件學(xué)報(bào)，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] 王晶，戎玫，張廣泉，等.基于概率模型檢測(cè)的Web服務(wù)組合驗(yàn)證[J].計(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] 李力行，金芝，李戈.基于時(shí)間自動(dòng)機(jī)的物聯(lián)網(wǎng)服務(wù)建模和驗(yàn)證[J].計(jì)算機(jī)學(xué)報(bào)，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ū)動(dòng)的可靠嵌入式系統(tǒng)建模及分析方法[J].軟件學(xué)報(bào)，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.