基于实例的无监督机器学习方法计算信息间的上下文相关度,主要思想是利用历史信息中相邻的信息往往更可能属于同一个会话这一性质,从历史信息中分别找出与待判定相关度的两条信息相似的信息集合,一方面作为待判定信息的特征扩展数据,另一方面进一步从相似信息集合找出前导信息集合,计算待判定信息与前导信息集合的相似度.最后,综合待判定信息间的相似度和与前导信息集合间的相似度,计算出最终的相关度.

　　定义7(会话上下文相关度).信息Mi和Mk间的相关度ρ表示这两条信息构成会话上下文关系的可能性,用二元函数ρ(Mi,Mk)表示,值越大表示可能性越大.

　　通过大量观察我们发现,网络聊天记录中时间顺序上紧临的两条信息,在大部分情况下,时间晚的信息是对时间早的信息的回复.并且,时间顺序上不紧邻的两条信息,如果它们产生的时间间隔较小,也有可能构成对话.

　　性质2.同一个短文本信息流中的两条信息Mi和Mk相距越近,这两条信息的会话上下文相关度越大.即1(,)||MiMkik∝ρ(5)

　　自然语言难以直接进行相似度的度量,通常做法是把文档分解成语法成分、词和长度等特征项,用特征项的权重构成的向量来表示文档.为便于表述,我们采用类似于文档向量的方法,不同之处在于我们忽略了权重为0的特征项.一条信息可以看作一个集合,其元素是权重不为0的特征项.

　　定义8(邻接共现频率).特征项w和w′相继在相邻的两条信息出现,称w和w′邻接共现.给定信息流片段S,二元函数χ(w,w′)表示w和w′在S中邻接共现的频率,其定义如下:(,)|{|1}|||wwiwMiwMiMiSSχ+∈∧′∈∧∈′=(6)

　　定理1.任意特征项w,w′和信息M,M′,若w∈M且w′∈M′,则χ(w,w′)∝ρ(M,M′)成立.

　　证明:由性质2可知,文本信息流中时序上紧邻的两条信息较有可能构成会话上下文关系.换言之,文本信息流中,大部分紧邻的信息之间构成会话上下文关系.而信息是特征项的集合,如果特征项w和w′在信息流中经常邻接共现,说明w和w′较有可能在同一个会话的上下文里同时出现.因此,若w∈M且w′∈M′,那么信息M,M′构成会话关系的可能性也就越大,即χ(w,w′)和ρ(M,M′)成正比.□大部分情况下,单个特征项只是信息某个维度的特征,不是任意特征项都能决定信息间的上下文关系.比如,“感谢你们的帮助”与“不用客气”这两条信息,起决定作用的是“感谢”、“帮助”和“客气”这3个特征项.因此,特征项集合W,W′在信息流中邻接共现的次数越多,W,W′的基数越大,就越能决定信息间是否有上下文关系,如推论1所示.

　　推论1.给定信息流片段S,对任意特征项集合W,W′,若W.M且W′.M′,则有如下公式成立:|{i|W.Mi∧W′.Mi+1∧Mi∈S}|×|W|×|W′|∝ρ(M,M′)(7)根据定理1和推论1,针对某个信息流,可指定某个历史片段为训练语料,计算出各个特征项的IDF值、所有特征项的各种组合间的邻接共现率,从而计算信息间的相关度.但是,这种方法的时间开销巨大.并且,由于网络聊天语言的动态性,我们必须经常地更新训练语料.因此,采用基于实例的机器学习方法,实时地从历史信息流中学习出信息间的相关度更为合适.

　　首先,为作为训练语料的信息流片段S构建特征项到信息的倒排索引.当信息M到达时,根据M的特征项,在倒排索引中搜索出最相似的前μ条信息,组成信息集合α.然后,构建如公式(8)所示的前导信息集合β:{|,}ijMikjiMSαβ∈=∪.<<∈(8)其中,β表示集合α中的每条信息在S中的k条前导信息组成的集合.以特征项为维度,以特征项的TF-IDF值为维度的值构成信息的特征向量.集合的中心向量为集合中所有信息向量的和的正规化向量.由定理1和推论1可知,信息M′中权重不为0的特征项在β的中心向量β..中的权重越高,M′与M的相关度就越高.另外,讨论同一主题的信息经常出现相同的关键词,两条信息的相似度越高,相关度也越高.因此,定义M′与M的相关度为M′的特征向量M′与β的角余弦相似度,以及M′与M的相似度的综合值,如公式(9)所示:ρ(M,M′)=cos(M′,β)×(1.cos(M′,α))+cos(M′,α)..............................(9)其中,α表示将α作为信息M的特征扩展后得到的向量,即{M}∪α的中心向量.

　　3.3在线会话抽取算法SPFC

　　本节综合第3.1节和第3.2节的两种方法,基于Single-Pass聚类模型设计了在线会话抽取算法SPFC.单独使用第3.1节或第3.2节的方法都不能达到较好的效果.基于信息产生频率的会话边界检测利用文本信息流的时序特性有效地将一个文本信息流切分成多个会话片段.但是,它不能处理交错性问题.如果切分粒度较粗,那么交错在一起的多个会话无法被正确地区分开来;如果粒度较细,则会将原本属于同一会话的信息切成多个片黄九鸣等:短文本信息流的无监督会话抽取技术741段,导致召回率降低.另一方面,虽然基于实例的上下文相关度计算方法利用历史信息,有效地将属于不同会话却交错出现的信息正确地分检到其所属队列,但却没有考虑信息出现的时序特性,受短文本特征稀疏性影响很大.相关度方法虽然比相似度方法具有更高的准确率,但仍难以区分一些应用过于广泛的日常用语(如“是”、“好的”)与上下文的关系.此外,相关度计算过程需要搜索历史记录,计算开销也远大于其他计算方法.

　　因此,为了较好地处理交错性问题,有效利用会话的时间特性,并面向海量数据实现高效处理,我们提出SPFC算法(如算法1所示):对文本信息流,先采用基于信息产生频率的边界检测方法将其切分为多个较细粒度的会话片段;再用基于实例的上下文相关度计算方法计算各个细粒度的会话片段间的相关度,采用Single-Pass聚类模型,聚合细粒度的会话片段得到最终的文本会话.

　　由于会话的数量很多,SPFC算法的实现采用了双时间窗口机制:只检测最新的tW个会话,每个会话只检测最新的dW条信息.SPFC算法定义了一个大小可配置的会话队列TW.TW队列采用先进先出的原则,其大小称为会话窗口tW.每到达一条信息,算法先使用公式(4)检测该信息是否为会话边界:若不是,则加入到最近的一个会话中;若是,则计算其与TW中每个会话的相关度,若大于阈值ζ,则将该起始信息加入到相关度最大的会话,否则创建新的会话.会话相关度以输入的训练语料G为学习实例,采用下面第4.2节所述方法计算.训练语料G为当前文本信息流的某个历史片断的倒排索引.实际应用中,训练语料可动态更新以解决动态性问题.

　　假设每条信息的产生频率检测时间复杂度为CF,上下文相关度计算的复杂度为CR.最坏情况下,信息产生频率频繁波动,每隔一条信息就要计算一次相关度,此时,SPFC算法的时间复杂度为O(|S|×(CF+CR)/2).

　　4、实验

　　SPFC去掉上下文相关度计算部分,即为基于信息产生频率的会话抽取算法SPF;去掉信息产生频率检测的部分,即为基于上下文相关度的会话抽取算法SPC.我们使用ICTCLAS对文本信息进行分词,使用Lucene构建训练语料的倒排索引并提供检索,实现上述提出的3种算法及基准算法.实验结果以SPWC,SPNN,SPWNN为基准算法,以F度量值为评价指标,对比验证SPF,SPC和SPFC的性能与时间开销.此外,本节还测试参数变化对算法的影响,并分析参数对算法性能产生影响的原因.

　　3种基准算法是目前比较有效的基于文本相似度进行改进的文本信息流会话抽取算法.其中,SPWC采用中心向量法,根据信息出现的时间顺序对特征向量进行加权计算得到各会话的中心向量后与待判定的信息一起计算相似度;SPNN用待判定信息与各会话的k个最近邻信息的相似度作为其与会话的相似度;SPWNN与SPNN相似,但在计算待判定信息与会话的k个最近邻信息的相似度时,根据信息的时间顺序对特征向量进行加权.

　　4.1实验数据

　　实验数据采集自我们的QQ群聊天记录.我们人工标注出一个名为Linux技术交流的群的部分聊天记录文本会话,形成实验数据集D.其余未标注的聊天记录(来自多个QQ群)组成训练集G,作为SPC和SPFC的训练语料.D的起始时间为2009年10月5日,结束时间为2009年11月5日;G的所有信息流的结束时间都早于D的起始时间.数据的语言大部分为中文,夹杂着一些英文和网络非正规语言.过滤掉一些只包含杂乱符号的信息后,D剩下44991条信息,G剩下126027条信息.

　　为验证各种算法的通用性,我们将D拆分成如表1所示的D1和D2两个子数据集,分别测试各种算法在D1和D2这两个不同数据集上的性能,以及D1和D2的并集,即数据集D上的性能.3个数据集的信息平均长度都在13个字符左右,是一个典型的短文本信息流.

　　4.2评测方法

　　评测方法采用与文献相似的准确率、召回率和F度量值.首先,对于算法抽取出的每个文本会话,我们计算其与人工标注的各个文本会话之间的准确率、召回率以及F度量的值.具体来说,对于算法抽取出的会话j和人工标注的真实会话i,准确率Precision、召回率Recall和F度量的值由以下3个公式给出:FijPrecisionijRecallijPrecisionijRecallij×=+(12)其中,nij是指真实会话i和算法抽取的文本会话j之间相同的信息的条数,ni是指真实会话i的信息条数,nj是指算法抽取的会话j的信息条数.F(i,j)是指真实会话i和算法抽取的会话j之间的F度量值.

　　算法会话抽取结果总的F度量值由下式算出:imax((,))ijFnFijn=Σ(13)其中,max函数扫描所有检测结果,查找与真实会话i有最大F度量值的会话j;n是指信息的总条数.

　　4.3实验结果