| 标题 | 基于软定时自动机的用户行为建模 |
| 范文 | 许小媛 纪河 黄黎 李从明 摘 要： 提出一种软定时转变自动机，识别更大范围的用户行为历史。该软建模的框架用户模型可以在类似网络学习的虚拟平台中实时地评估用户的动态行为，通过评估观察到的行为中的时间偏差、额外的或省去的行为量来评估用户行为。当观察到的行为只部分满足给定的行为模型约束时，该模型也可以用于用户历史行为的部分识别。相对于标准的布尔模型的识别，当多个用户模型存在偏差量时，该方法通过预测、投影和其他已知的技术更适用于用户实时支持系统，引导生成系统支持。基于日志的网络学习平台和软时间自动机的规划实验证明了该模型的表现力和有效性。 关键词： 用户行为； 时变自动机； 自动规划； 建模； 软定时； 匹配 中图分类号： 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； matching0 引 言 目前，在有关用户行为建模的研究中，一些方法侧重通过正式的“用户会话”[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. |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。