基于情景感知的Ngram改进预测模型研究.doc

基于情景感知的Ngram改进预测模型研究 第30卷第9期xx?9月微?计?算?机?应?用M ICROPUTER APPLICAT IONSVol?30No?9Sep?xx基于情景感知的N?gram改进预测模型研究张?芸?吕廷杰?李海强(?京邮电大学经济管?学院?京?100876)?摘要:情景感知服务(Context-Awareness Services)借助信息技术为用户提供自适应服务,卓著的个性化特性使其将成为下一代杀手级应用。 本文综合分析移动用户的位置、时间和业务信息,通过改进N-gram模型有效地预测用户?为趋势,以期通过最优化的方式使用户需求与其所处的环境资源相匹配,既期望能从用户视角获得?加丰富的信息体验,又期望能对运营商有所帮助,对?论研究及商业实践均具有积极意义。 关键词?情景感知?数据挖掘?预测算法?N?gram模型?序列模式ImprovedN?gram PredictionModelResearchBased onContext?AwareEnvironmentZHANG Yun,LV T ingjie,LI Haiqiang123(School ofEconomics andM anagem ent,Be ijingUniversityof PostsandTelemunications,Be ijing,100876,Ch ina)Abstract?Context-Awareness Servicesprovide self-adapting applicationsby usinginform ationhigh-technology?Its individuationmakes itconsidered tobe thenext killerapplication?W ithanalyz ingthe integratedlog filesof location,time andservice of users incontext-aware environm ent,we improve theN-gram modeland advancetwo prediction algorithm s,ai m ing formatching needsofus?ersw iththe currentresource inan optimized way?In orderto help m obileusers obtainm oresatisfying servicesand theoperators getmore profits,the articleai ms touse thecontext-aware dataeffectively andwe hopeit canplay apositive rolein bothacadem icre?search andbusiness practice?K eywords?Context-Aw are,datam ining,predictionalgorithm,N-gramm ode,l sequencepattern随着移动技术特别是传感器技术的进一步发展,信息技术对用户所处情景环境的捕获能?越来越强,这导致了基于情景感知的自适应服务的产生。 基于情景感知的移动商务服务在很多文献中被称为情景感1知服务,它是移动商务中提供个性化服务的关键因素。 由于用户情景是动态变化的,所以情景感知服务需要根据用户情景的变化自动调整所提供的服务,建立一种情景感知服务的自适应调整机制。 在这一环境中,如何实现预测移动用户的需求以?主动提供业务或信息就显得尤为重要。 近?来,情景感知已经成为一个研究热点。 目前,一些国际上的学术研究团队已经开始研究在移动网2络系统中的数据挖掘及预测,但他们大多是只侧重在与移动用户?为有关的一个或者两个属性来研究,比如:移动用户位置和相应的需求业务,而缺少对时间属性的综合考虑。 本文综合考虑移动用户基于情景感知环境的的位置、时间和业务信息,提出N-gram改进预测模型的两种算法,并比较二者的优劣势及适用范围,使基于情景感知环境中的预测?为有效,既期望能从用户视角获得?加丰富的信息体验,又期望能对运营商及其他厂商有所帮助。 本文于xx-05-14收到,xx-06-22收到修改稿。 *基金项目:信息产业部基金项目(xx-R-152)。 ?2?微?计?算?机?应?用?xx?1?基于情景感知的N?gram改进预测模型架构受自然语言中n元语言模型的启发,本文提出了一种基于情景感知环境的N-gram预测模型。 在这一部分,首先给出本文的预测模型架构(见图1),该架构通过对数据库中相关数据的分析,预测出移动用户在情景感知环境中可能的?为趋势,并基于此预测结果为终端用户提供与当前环境相匹配的服务。 近来,?少研究机构对基于位置和业务的预测方法进?了研究,但很少考虑时间维度的关联性。 本文提出的预测模型综合考虑了位置、时间和业务三种因素,其基本思想是:通过将位置Log信息、时间Log信息和业务Log信息组合后的数据库进?数据训练,构建出序列数据库,然后利用改进的N-gram模型对移动用户在情景感知环境中的趋势进?预测。 由此,运营商及其他相关服务厂商?可通过预测结果对移动用户进?具针对性的服务。 图1?基于情景感知的N-gram改进预测模型架构2?基于情景感知的N?gram改进预测算法在这一部分,本文首先介绍了传统N-gram算法的基本思想,随后对于情景感知环境中与预测相关的概念作出定义,而后通过对N-gram模型进?改进,得出适合于情景感知环境的预测算法,最后举例应用该算法并作出评价。 2?1?N?gram算法的基本思想介绍N-gram算法在自然语言和语音识别中有着广泛的应用,是一种非常重要的统计模型。 假定所研究的事件用序列P1,P2,?,P n来表示,其中P i(1i n)表示第i个事件。 为了估计序列的概率,运用贝叶斯规则改写概率公式,见公式 (1)。 Pr(P1,P2,?,P n)=p(P1)i?Pr(P=2ni P1,?,P3i-1) (1)运用统计语言模型来估计概率p(P i|P1,?,P i-1)时,广泛使用的统计模型就是所谓的N-gram模型。 N-gram语言模型假设序列中的每个单词由它的前n-1个单词决定,而与比这n-1个单词?往前的单词序列没有关系,也就是说p(P i|P1,?,P i-1)=p(P i|P1-n+1,?,P i-1),因此n长度的事件序列可以看成N-gram事件序列。 同?假设移动用户下一步将触发的事件取决于用户的前n-1次事件,见公式 (2)Pr(P i|P1,P2?,P i-1)=Pr(P i|,P i-n+1?,P i-1)=p(P i-n+1?P i-2,P i-1,P i)C(P i-n+1,?,P i-2,P i-1,P i)/C n=p(P i-n+1?P i-2,P i-1)C(P i-n+1,?,P i-2,P i-1)/C n-1C(P i-n+1,?,P i-2,P i-1,P i)*CC(P i-n+1,?,P i-2,P i-1) (2)C(P i-n+1,?,P i-2,P i-1,P i)表示N-gram序列(P i-n+1,?,P i-2,P i-1,P i)在样本序列中出现的次数,C n和C n?1分别表示N-gram和(N-1)-Gram序列总数,C、C n、C n?1都是常数,且C?C n?C n?1。 由此,Pr(P iP1,P2,?,P i-1)得以求解4。 使用时,n的取值越大表明可参照的历史信息越充分,可提高预测的准确性,但同时要求训练数据的样本?也越大,当n取1时,则N-gram模型退化为单M arkov模型。 2?2?相关概念的定义在组合数据库中存储着移动用户的各种数据,其中包含三个属性:位置、时间及业务5,它们分别对应?9期?张?芸等:基于情景感知的N-gram改进预测模型研究3位置集合L、时间集合T及业务集合S。 假设p?l?t?s?,其中p是用户情景环境数据集合P的元素,l是位置集合L的元素,t是时间集合T的元素,s是业务集合S的元素,则用户情景环境P可表示为:P?L!T!S?由此,用户情景环境序列可表示为M?刻的位置、时间及业务信息。 定义1:假设存在用户情景环境序列M=列,记为MM。 定义2:假设数据库D?序列M S的支持度定义为:sup Ms?M siMs Msi?1i NN (4)M S1?M S2?M Sn,其中M Si表示一种用户情景环境序列,则将用户情景环境p1,p2,p3,?,pm和M=p1,p2,p3,?,p n,其中m n,且存在一个严格递增序列i1,i2,?,i,2,?,m,都有p j#=p ij,则称M为M的一个子序m,使得对于所有的j=1l?t?s l?L andt?T ands?S (3)p1?p2?p3?p n,其中p i=(l i,t,i si)表示移动用户在某一时在组合数据库样本?足够大的情况下,我们可以就时间、位置及业务三个参数进?多种预测,结合情景感知应用实际意义的需求,本文选取其中三条预测规则(算法中表示为prule)进?研究: (1)已知时间和位置,预测业务。 根据用户情景环境历史数据,结合当前时间及位置,利用改进N-gram算法,预测业务。 可表示为:R?s?l m?n?1?t m?n?1?s m?n?1l m?n?2?t m?n?2?s m?n?2?l m?1?t m?1?s m?1l m?t m?s m? (2)已知时间和业务,预测位置。 根据用户情景环境历史数据,结合当前时间及业务,利用改进N-gram算法,预测位置。 可表示为:R(l m) (3)直接预测时间、位置及业务。 根据用户情景环境历史数据,利用改进N-gram算法,直接预测下一次事件的时间、位置及业务。 可表示为:R(l&t s)l)=l m-n+1,t m-n+1,s m-n+1l m-n+2,t m-n+2,s m-n+2?l m-1,t m-1,s m-1t m,s m?=l m-n,t m-n,s m-n l m-n+1,t m-n+1,s m-n+1?l m-1,t m-1,s m-)为rhs。 ?s m?1?(l m,t m,s m)?l m?n?2?t m?n?2?s m?n?2此处定义%?&左边的部分(例如R?s?中的?l m?n?1?t m?n?1?s m?n?1l m?1?t m?1?s m?1,定义%?&右边的部分(例如R?s?中的l m?t m?)为lhs2?3?基于情景感知的N?gram改进预测算法本文所提出的N-gram改进预测算法是基于对移动用户情景环境组合数据库中的历史数据进?统计训练,而后根据N-gram算法思想进?预测的算法。 根据上一节定义的预测规则,可以进?同组合、满足?同需求的预测。 本算法首先需要对历史数据进?统计训练,这是一个常见的挖掘关联规则的数据挖掘过程。 关于在大型数据库中挖掘关联规则,目前应用较为广泛的算法大多是基于Apriori或基于Fp-tree。 这一步骤的流程就是通过对情景环境组合数据库进?扫描,得出记录着强关联规则的训练表,此类算法很多,读者可自?参考,本文?做赘述。 特别指出的是,本文建议在情景感知环境中的挖掘关联规则这一步骤可以应用一种分布环境中的并?频繁模式挖掘算法76,该算法尽可能地让每个处?器独立地挖掘,每个处?器基于前缀树采用深度优先搜索的策略挖掘局部频繁模式集,并通过相关性质尽?减少候选全局频繁模式的规模,减少网络的通信?和同步次数以提高挖掘效率,较适用于情景感知环境分布式数据库的应用。 经过强关联规则的挖掘,得出包含支持度与频繁序列的训练表8,在该表的基础上,本文提出以下的N-gram改进预测模型。 基于对时间维度的?同处?方式,可分为两种应用模式(即两种算法): (1)将位置、时间、业务的组合,即(,l,t s),应用到N-gram预测算法中,具体算法如下:?4?微?计?算?机?应?用?xx?算法1:A lgorithmn-gram-a(cas:user?s current activity sequence;n:N-gram value;prule:Pred ictionrule)S tep1:if prule is set toR?s?,lhs(l m?1?t m?1?s m?1l m?1?t m?1?s m?1l m-1,t m-1,s ml m?t m?from caslhs(the lastn elements?l m?n?1?t m?n?1?s m?n?1,t m-n,s m-l ml m?n?2?t m?n?2?s m?n?2?,t m-,s m-?t m?s m?from cas&l t s)the lastn elements?l m?n?1?t m?n?1?s m?n?1l m?n?2?t m?n?2?s m?n?2?if pru le is set toR(l),if prule isset toR(-1,lhs(the lastn elem entsl m-n n-n+1n+1n+1from casS tep2:rhs(get thenex telement fromthe pre-created trainingtable aordingto thegiven pruleS tep3:if rhsis notempty,return rhsas the prediction results?O therwise,return NULL? (2)考虑到时间维度的特殊性9,如连续性和?分类等,先将(,l s)的组合应用到N-gram预测算法中,再对这一预测结果加入时间维度进?分析。 具体算法如下:算法2:A lgorithmn-gram-b(cas:user?s current activity sequence;n:N-gram value;prule:Pred ictionrule)S tep1:if prule isset toR?s?,l m?t m?from caslhs(the lastn elements?l m?n?1?t m?n?1?s m?n?1l m?n?s m?nl m?n?2?t m?n?2?s m?n?2?from cast m?s m?from casl&t s)lhs(the lastn elements?l m?n?1?t m?n?1?s m?n?1l m?n?2?t m?n?2?s m?n?2?lm?1?t m?1?s m?1lm?1?t m?1?s m?1if pruleissettoR(l),if pruleissettoR(,lhs(the lastn elementslm?n?1?s m?n?1?lm?1?s m?1S tep2:rhs(get thenex telement fromthepre-created trainingtable aordingto thegiven pruleS tep3:if rhsis empty,return NULL?O therwise,go onstep4?S tep4:b ihe lhsand rhsasP#,p#re-scan thedatabase,get allthe sequencesthat i?l#i?s#i?,containP#asM#,calculate theaverage value ofall?t#nM#,named ta?then gett m?1of cas,give t m?m?t#m?1?it a?t m?1as the prediction time?Step5:return rhsandt mas theprediction result?2?4?N?gram改进预测模型应用举例在这一部分,本文将举一个示例来展示如何应用本文所提出的两种预测算法。 首先给出组合Log信息,见表1:表1?情景感知环境log信息用户序号100101102情景感知环境序列用户序号103104105情景感知环境序列其中时间序号的具体时间戳见表2。 又给出当前某一用户A的情景感知环境序列为,以下将使用本文所提出的预测算法对用户的?为进?预测。 ?9期?张?芸等:基于情景感知的N-gram改进预测模型研究表2?时间序号的具体时间戳序号T1T2T3T4T5时间戳7:35:407:55:359:30:309:40:309:55:45序号T6T7T8T9T10时间戳10:20:3510:30:3511:25:3012:35:3512:45:45序号T11T12T13T14?时间戳13:10:2313:12:xx:10:xx:12:43?5对于n-gram-a算法,首先我们需要考虑时间维度,?简单的使用时间戳进?数据训练,可能会造成由于时间点与环境事件?匹配而造成训练?出频繁序列的情况,如:在09:30:30这一时刻发生的情景事件可能在数据库中仅有一次,而这一次情景事件事实上对频繁模式是有贡献的,但由于时间归类的划分问题导致了这一事件被过滤掉了。 因此,我们需要确定一个时间间隔阈值d以对时间戳进?归类,在本例中选定d=1小时,将24小时划分为0:00-1:00,1:00-2:00?,分别命名为t0,t1?t23。 则表1可改写为以时间聚合后的模型,见表3:表3?情景感知环境时间聚合模式log信息用户序号100101102情景感知环境序列用户序号103104105情景感知环境序列10选取最小支持度为30%,扫描一次数据库,得出下表4所示的数据训练表:表4?n?gram?a算法数据训练表数据训练序列支持度33%33%33%33%数据训练序列支持度33%33%50%选取N-gram的参数N=2,则用户A的情景感知环境序列末两个元素为(,f T2,2)(g,T10,5),以1小时为时间间隔聚合后表示为:(,f t7,2)(g,t12,5),扫描预测表,利用算法2:n-gram-a算法,设定prule为R(1?f t7,2)(g,t12,5)?,由此可以预测用户A下一个可能的?为是在t s),预测结果为(,t13的时域内在位置h使用业务编码为8的业务。 对于n-gram-b算法,首先我们将情景感知环境log信息中关于时间维度的数据去除,可得下表5:表5?情景感知环境时间去除模式log信息用户序号100101102情景感知环境序列用户序号103104105情景感知环境序列选取最小支持度为30%,扫描一次数据库,得出下表6所示的数据训练表:选取N-gram的参数N=2,则用户A的情景感知环境序列末两个元素为(,f T2,2)(g,T10,5),去除时间维度得:(,f2)(g,5)。 扫描预测表,利用算法2:n-gram-b算法,设定prule为R(1?f2)(g,5)ts),预测结果为?。 接下来预测时间,再次扫描数据库,提取情景感知环境log信息数据库中包含的记录,分别为:及,计算出ta=(T11-T9)+(T12-T10)/2=0:30:41,则tm?ta?tm?1=0:30:41+12:45:45=13:16:26,由此可以预测用户A下一个可能的?为是在13:16:26的时刻在位置h使用业务编码为8的业务。 2?5?基于情景感知的N?gram改进预测模型评价表6?n?gram?b算法数据训练表数据训练序列支持度33%33%33%33%数据训练序列支持度33%33%50%33%数据训练序列?支持度33%33%33%?在消费者?为预测领域被广泛应用的预测模型很多,如M arkov模型等。 而在网页浏览预测中,利用11N-gram模型进?预测已被证实是较为有效的预测方法,实验表明运用N-gram模型能够有效地缩减预测数据空间,大大降低程序运?的复杂程度,而且其在预测精度方面的表现也十分卓著,非常适合于用户数?众多、数据库信息庞杂的预测环境。 本文所研究的移动用户情景感知环境序列,是旨在研究当前全球范围内庞大的移动终端用户群的?为模式,分析由环境参数组合元素构成的海?数据,因此,使用改进后的N-gram模型进?预测是非常合适的。 比较?同元数(即N的取值)模型的预测精度和适用度,发现运用4元以上的预测模型可以得到最优预测结果,其在精度和适用度方面较其他元数均?为?想。 而与其他预测方法相比,本文所述方法无须过多地了解和分析用户的喜好信息,只需要分析服务器的Log数据库。 同时对于用户来说,也?需要增加任何额外的使用负担。 本文所提出的两种预测算法n-gram-a和n-gram-b各有?同的适用范围,以下将作出简要的利弊比较:对于n-gram-a算法: (1)采用时间间隔阈值对时间进?聚合分析,使用者可根据预测所需来设定阈值d的取值,从而使该算法具有较大的延展性。 而与此同时,阈值的取值精度直接影响数据训练的有效性,一般而言,时间阈值越小,数据训练序列越能保持其连贯性。 (2)将时间维度作为序列元素的属性进?分析,使得序列间匹配的难度加大,筛选出的可用数据训练序列数?较n-gram-b算法少,因此?适合应用于组合数据库中样本?较大的情况。 (3)在大型组合数据库中,在挖掘出的数据训练序列长度有保障的情况下,?N-gram中n值取值越大,预测准确性越高,但相应地也越难以找着匹配的训练序列,因此应该在准确性和可用性中寻求均衡。 特12别地,当N-gram中n值取1时,则该模型退化为单M arkov预测模型。 (4)仅扫描组合数据库一次,并且?有新的训练数据入库,可直接动态?新新数据即可,具有较高的应用效率。 对于n-gram-b算法: (1)采用先对位置和业务进?预测,再选训练数据库中相应的序列进?时间预测,所得的时间精度?高。 一般而言,组合数据库中的样本?越大,所预测的时间越精准。 (2)先将时间维度去除而进?序列分析,使得序列间匹配的难度降低,筛选出的可用数据训练序列数?较n-gram-a算法多。 较适用于组合数据库中样本?较小的情况。 (3)剔除时间因素之后,?能体现位置及业务之间的连贯性。 因此适合于对位置及业务关联度?为关注的情况。 (4)同样地,在大型组合数据库中,在挖掘出的数据训练序列长度有保障的情况下,?N-gram中n值取值越大,预测准确性越高,但相应地也越难以找着匹配的训练序列,因此应该在准确性和可用性中寻求均衡。 特别地,当N-gram中n值取1时,则该模型退化为单M arkov预测模型。 (5)扫描组合数据库两次,效率较n-gram-a有所降低,但?有新的训练数据入库,仍可直接动态?新新数据。 ?9期?张?芸等:基于情景感知的N-gram改进预测模型研究73?结束语本论文作为信息产业部基金项目的预研研究,通过系统地研究国内外研究文献,构建了基于情景感知的预测架构,将位置、时间和业务信息进?数据库的组合分析,而后对N-gram模型加以改进并提出两种预测算法(n-gram-a和n-gram-b算法),并比较了这两种算法的优劣势及各自的适用环境。 在这两个算法的使用中,可以通过设置预测规则、N-gram中n的长度及时间维度的划分等,灵活有效地预测出情景感知环境中的各种参数,以期通过最优化的方式使用户需求与所处的环境资源相匹配。 与其他预测算法相比,本文所提出的算法无须过多地了解和分析用户的喜好信息,只需要分析服务器的Log数据库,而对于移动用户而言,也?需要增加任何额外的使用负担。 该算法能够有效地缩小预测数据空间、简化预测复杂程度,同时有具有卓著的预测精度,将其运用在庞杂的移动数据库中是非常合适的。 同时我们也发现运用4元以上的预测模型(即N4)可以得到最优预测结果,其在精度和适用度方面较其他元数均?为?想。 本文的研究目标在于?加有效地处?情景感知环境下的数据信息,为在3G时代?好地为移动用户提供个性化服务提供一定的?论及实践研究,既期望能从用户视角获得?加丰富的信息体验,又期望能对运营商及其他厂商有所帮助,对?论研究及商业实践均具有积极意义。 参考文献1Gessler Stefan,M artinMique,l Weiss Stefan?ContextAw arenessin FutureL ifeScenarios:I mpact onService ProvisioningPlat?form s?xxSym posiumon Applicationsand theInterW orkshops,SA INTxx?Trento,Italy,xx?2V incentS?Tseng,KawuuW?L in?EfficientM iningand predictionofuser behavior patternsinm obileweb systems,Inform ationandsoftware technology,xx?3L iuZh ikun,W angW eiping?W ebPersonalization basedon AurateSequential Pattern,Computer systems andapplication