基于軟定時自動機的用戶行為建模

許小媛　紀河　黃黎　李從明

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

關鍵詞： 用戶行為； 時變自動機； 自動規劃； 建模； 軟定時； 匹配

中圖分類號： TN98?34； G231.5 文獻標識碼： 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 引 言

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

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

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

1 用戶行為的時間自動機

用戶在結構化界面環境中操作的行為域（如網絡學習平臺、郵件客戶端、內容管理平臺）可以很容易地由一個隨著時間約束擴展的狀態轉變圖描述。由狀態轉變圖表示用戶可以執行的動作。

定時轉變自動機（TTA）[10]是一種有限狀態機，能夠識別定時的口令，即由給定的字母集[Σ]和時間值符號構成的序列對。可以把序列對看作標注著發生時間的、記錄用戶事件或行為的日志記錄序列。

在TTA中，只有滿足某些時間條件時（如在給定的時間間隔內提交在線作業），才可以限制某個行為的執行，即某個轉變的發生，那么域名自動機被定義為合法轉變或相當于在系統可以進行的行為的合法程序。

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

2 算法

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

定義（軟定時語言）：軟定時轉變自動機的語言[L（As）]，[As=（A，?，π，σ，θ）]是通過由定時口令形成的成組的集合，對應于自動機的從[S0]開始的持續運行，及其軟運行的最小行為偏差。可以看出，UBM中定義的滿足時間約束的所有時間口令是一定程度的行為偏差的“軟接受”。自動機接受的所有時間口令也都是[γ=0]時軟接受的。雖然不是所有的時間口令被自動機所接受，但滿足時間約束的所有軟接受[γ>0]。

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

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

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

3 實驗

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

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

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

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

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

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

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

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

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

自動機由[si]狀態轉變到[sj]時，沒有解析輸入口令中的任何符號。

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

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

1） 當完全識別時，最后的γ函數等于零；

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

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

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

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

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

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

4 結 論

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

參考文獻

[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] 劉嘯濱，郭兵，沈艷，等.嵌入式軟件體系結構級能耗建模方法[J].軟件學報，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] 陳碧歡.基于需求和體系結構的軟件系統自適應方法[D].上海：復旦大學，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服務組合驗證[J].計算機科學，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].計算機學報，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] 范貴生，虞慧群，陳麗瓊，等.策略驅動的可靠嵌入式系統建模及分析方法[J].軟件學報，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.