0 引言

随着网络的发展与普及,微博作为一种社交网络软件在人们的日常生活、工作、社会热点信息的传播中起着重要的作用。很多新词借助微博平台广泛的传播,被人们所了解和使用。新词识别在中文分词、信息检索等方面都有着重要的作用。如何从微博中快速、准确地识别新词,是自然语言处理学科中研究的重点。

目前,对于新词识别的研究方法主要分为三种:基于统计的方法、基于规则的方法和基于统计与规则相结合的方法^[1]。基于统计的方法^[2-5]通过利用各种统计策略来提取候选新词,找出相关度最大的各字串的组合。这类方法的适应性强,可移植性较好,但是需要大规模语料进行训练,且存在数据稀疏和准确率低的问题。陈飞等^[4]提出的基于条件随机场(Conditional Random Field,CRF)方法的开放领域新词发现方法,首先利用分词器对语料库进行分词,再计算这些词的统计特征,然后利用CRF进行训练,最终识别新词。该方法只是单纯地使用统计特征并没有采用相应的语言规则,且较依赖于分词器的性能。 李文坤等^[5]提出的基于词内部结合度和边界自由度的新词发现方法,首先利用NLPIR汉语分词系统对语料进行分词,然后再采用互信息(Mutual Information,MI)和左右信息熵对分词之后的语料进行过滤得到新词。该方法较依赖分词系统。基于规则的方法^[6]则首先由相关的领域专家利用构词学原理、词性及语义信息构造规则模板,然后对实验数据匹配这些模板及规则来发现新词^[1]。如李明^[6]利用改进后的Apriori算法对语料处理并生成关联规则,然后利用关联规则抽取新的专业词汇。基于规则方法的领域性很强,但是其可移植性较差,在规则的制定过程中需要消耗大量的人力、物力。基于统计和规则相结合的方法^[7-9]则融合了前两种方法的优点,以期提高新词发现的效果。林自芳等^[7]首先进行重复串查询,然后结合词内部模式的特征对位置成词概率和首尾单字成词概率进行加权和改进,最后统计互信息、邻接类别等统计量识别新词。霍帅等^[8]提出引入词关联性信息的迭代上下文熵算法,引入词法特征与统计特征相结合的方法,但是该方法依赖于使用的分词系统,且选取词频作为统计特征,容易忽视低频词。现在大多数研究者采用两者结合的方法,发挥各自的优势,提高新词发现的效果。

本文采用互信息、邻接熵等统计特征与停用字及词典过滤等规则相结合,提出了基于改进互信息和邻接熵的微博新词发现算法(MBN-Gram)。该算法首先使用N-Gram算法对语料进行分词得到候选新词,再利用频率和停用字等规则进行过滤,最后结合互信息以及邻近熵进行再过滤,识别出多字词,实现对微博内容的新词发现。

文献^[10]通过对大量的语料进行研究分析,发现新词主要是由2~4个汉字组成的,并总结出了11种构词模式,其中“1+1”“1+1+1”“1+1+1+1”单子模式占新词总数的61.4%,“2+1”“3+1”模式占新词总数的31.2%,所以本文主要针对这些构词模式进行新词发现。

1 相关技术 1.1 N-Gram算法

N-Gram算法的基本思想是:对于待处理的文本语料,设置滑动窗口的大小为N,对语料进行切分,切分后每个大小为N的字符串称为一个gram,并统计所有gram的频率,按照预先设定的阈值对其进行过滤,删除不满足条件的垃圾串,从而得到候选新词。

N-Gram算法不需要对文本语料进行语言学处理,具有语种无关性,对于书写错误有很强的容错性,不需要规则和专业词典。针对微博文本的创造性、随意性等特点,本文使用N-Gram算法对语料进行处理。

目前准确率较好的是二元递增Bigram算法和三元递增Trigram算法,本文使用这两种算法对微博语料进行处理。

1.2 内部统计量

常用的判断新词的成词概率的内部统计量有互信息(MI)、骰子系数(Dice coefficient,Dice)、对称条件概率(Symmetric Conditional Probability,SCP)等。通过实验对这三个统计量进行对比,如图 1所示,发现其中互信息相对于其他两种方法比较稳定,所以本文采用互信息来衡量词语的内部成词概率。

互信息^[11]的计算公式为:

$\text{MI}\left( \text{x},\text{y} \right)=\text{log}\frac{p(xy)}{p(x)p(y)}$

(1)

其中: p(x)、p(y)表示x、y单独出现在语料中的概率； p(xy)表示x、y共同出现在语料中的概率。若MI(x,y)>0,表示x、y是密切相关的,其值越大说明关联程度越大,越可能成为新词;若MI(x,y)=0,表示x、y是相互独立分布的,它们之间是偶然的;若MI(x,y)<0,表示x、y是不相关的。

互信息对于二元词组的计算有很好的效果,但是对大于两个字的多字词如何划分成两部分是比较困难的,针对这个问题对其进行改进,公式为:

$MMI({{w}_{1}}...{{w}_{n}})=\log (\frac{p({{w}_{1}}...{{w}_{n}})}{Avg({{w}_{1}}...{{w}_{n}})})$

(2)

$p({{w}_{1}}...{{w}_{n}})=\frac{f({{w}_{1}}...{{w}_{n}})}{N}$

(3)

$Avg({{w}_{1}}...{{w}_{n}})=\frac{1}{n-1}\sum\limits_{i=1}^{n-1}{p({{w}_{1}}...{{w}_{i}})p({{w}_{i}}...{{w}_{n}})}$

(4)

其中:w₁…w_n为多字串； p(w₁…w_n)是字串w₁…w_n在语料库中出现的概率； f(w₁…w_n)表示字串在语料库中的频率；N表示语料库的总字数；Avg(w₁…w_n)是多字串不同组合的平均概率。改进后的公式能够计算多字词之间的互信息。本文算法中所使用的是改进后的互信息。

多字串互信息公式有效性证明:

对于互信息的计算公式(1)利用数学知识对其进行恒等变换：

$\begin{align} & \text{MI}\left( \text{x},\text{y} \right)=\text{log}\frac{p(xy)}{p(x)p(y)}\text{=}\log \frac{p({x}/{y}\;)}{p(x)} \\ & =\log \frac{p({y}/{x}\;)}{p(y)}=\frac{1}{2}[\log \frac{p({x}/{y}\;)}{p(x)}+\log \frac{p({y}/{x}\;)}{p(y)}] \\ \end{align}$

在新词发现中互信息衡量的是两个部分组合在一起的成词概率。对于二字词可以很容易的将其分成两部分,但是对于多字词(本文指三字词和四字词)如何拆分成两部分是一个难题,本文根据互信息公式变形的启发,取多字词的不同组合形式的均值作为公式的分母值。

如三字词(w₁w₂w₃)将其分成A、B两部分,则其互信息

$\begin{align} & \text{MI}\left( A,B \right) \\ & =\text{log}\frac{p(AB)}{p(A)p(B)}=\frac{1}{2}[\log \frac{p({A}/{B}\;)}{p(A)}+\log \frac{p({B}/{A}\;)}{p(B)}] \\ \end{align}$

其中:A、B的划分有两种形式,对于新词,并不能确定如何划分是有效的,所以对于公式分母p(A)p(B),取其两种划分的均值作为其值。如“高富帅”,可以分成“高”和“富帅”和“高富”“帅”两种形式,分别计算p(高)p(富帅)及p(高富)p(帅)的值并取平均作为分母值。

对于多字词(w₁…w_n),同理可得其互信息分母计算公式为$Avg({{w}_{1}}...{{w}_{n}})=\frac{1}{n-1}\sum\limits_{i=1}^{n-1}{p({{w}_{1}}...{{w}_{i}})p({{w}_{i}}...{{w}_{n}})}$。

理论上这种方法是可行的,本文实验结果也表明这种划分方法是有效可行的。

融合互信息的一种改进N-Gram算法是在Bigram算法进行分词的基础上对其进行扩展以得到多元词语。首先对预处理之后的相关语料采用Bigram算法进行切分得到多个gram;然后对每一个gram构建相邻的关联矩阵,相邻的两个gram构成矩阵M,相邻的三个gram构成矩阵N,并统计出现的频率,移除频率小于阈值且含有停用字的矩阵;接着计算gram之间的互信息筛选出满足要求的词作为候选词；最后利用常用词词典对其进行过滤,得出新词。

1.3 外部统计量

现在常用的外部统计量包括邻接熵(Branch Entropy,BE)和邻接类别(Accessor Variety,AV)。通过实验对这两个统计量进行对比,如图 2所示,发现邻接熵比邻接类别的准确率要高,所以本文采用邻接熵作为外部统计量来衡量词串成词概率。

邻接熵是Huang等^[12]提出的衡量词串成词概率的一个重要外部统计量,它利用信息熵来计算候选词左右邻接串的不确定性,其不确定性越大,说明其邻接的字符串包含信息越多,其成词的概率就越高。

左邻接熵:

$HL(x)=-\sum\limits_{a}{p(a|x)\log p(a|x)}$

(5)

右邻接熵:

$HR(x)=-\sum\limits_{b}{p(b|x)\log p(b|x)}$

(6)

其中: p(a|x)表示a为候选词x的左邻接字符的概率; p(b|x)表示b为候选词x的右邻接字符的概率。

2 本文MBN-Gram算法 2.1 改进思路

在对微博数据进行新词发现的过程中,传统的规则与统计方法不能解决微博数据存在的数据稀疏的问题,且单纯的基于规则的方法可移植性较差,使得新词发现的效果并不理想。而N-Gram算法可以有效地解决微博数据的稀疏性问题,不必考虑分词过程中出现的错分、误分的问题。传统的N-Gram算法只是针对数据中的二元词语进行新词发现,并没有对数据中的多元词语(三元、四元)进行识别。基于N-Gram算法与互信息相结合的算法则考虑了词语之间的内部成词概率,对识别的二元词语进行扩展,从而可以识别出多元词语,但是该方法并没有考虑到词语的外部成词概率。文献^[5]提出的方法较依赖分词系统,分词系统的好坏直接影响最后的结果。

针对以上问题,本文提出一种融合互信息和邻接熵改进N-Gram算法的MBN-Gram算法。具体步骤如下：

首先使用N-Gram算法对语料进行切分并统计其频率,使用频率和停用字等相关规则对其进行初步筛选,过滤掉频率小于阈值或者包含停用字的词语;

其次对于筛选出来的词语利用互信息计算其内部成词概率来进行再次的筛选;

最后采用邻接熵对上面筛选出来的词进行外部成词概率的筛选,由于新词是不包含在常用词词典中的,所以最后使用常用词词典对其进行最后过滤,从而得到新词集合。

本文方法可以有效地解决微博数据稀疏及多元词语的识别的问题，同时由于N-Gram算法不需要对文本进行语言学处理,具有语种无关性,所以其有很好的可移植性。

本文提出的MBN-Gram方法如图 3所示。

2.2 算法流程

本文是针对微博语料的新词发现算法,由于微博语料中包含了大量的噪声数据,所以先要对语料进行预处理,然后对预处理之后的数据采用N-Gram算法进行分词,获得初始候选新词集合,在利用内外统计量及相应过滤规则进行过滤,最后在使用已有旧词典进行过滤,从而得到新词。算法流程如图 4所示。

2.3 算法实现

由于获取的微博语料中包含了大量的噪声数据,所以在进行分词之前要先对微博语料进行预处理操作。

1) 微博语料预处理操作。把微博语料中包含的链接、表情符号、用户名、特殊字符、英文单词等噪声数据过滤掉,得到预处理之后的语料集合。

微博语料过滤算法Tfilter(T)步骤如下:

输入微博语料T。

输出 语料预处理之后的结果T1。

①初始化

②T=removeALLSymbol(T);   //删除语料中的符号

③T=removeALLAlpha(T);  //删除语料中的英文字母

④T=removeALLUrls(T); //删除语料中包含的Url链接

⑤T=removeALLDigit(T);    //删除数字

⑥RETURN T1;    //预处理之后的语料

2)使用N-Gram算法(Bigram和Trigram算法)对预处理之后的语料进行分词,并统计其频率。

3)预过滤。过滤掉频率小于阈值且含有停用字的词,把满足条件的词加入到候选新词集合。

4)对上步的候选新词集合利用改进的互信息进行统计,剔除互信息小于阈值的词,形成新的候选新词集合。

5)如果候选词为二元组,对词的左右邻接熵进行统计,将左右邻接熵都大于阈值的词加入候选新词集;如果候选词为三元组,计算该词的左邻接熵,若大于阈值则左边界确定;否则向左扩展一个字,再次计算其左邻接熵,对于左邻接熵大于阈值的词,同理进行右邻接熵计算。把左右邻接熵都大于阈值的词加入候选新词集。

MBN-Gram算法MBN-Gram(T1,N3)步骤如下:

输入 微博语料预处理之后的结果T1。

输出 候选新词N3。

①Tfilter(T);//文本过滤

②分词：

FOR length=minn:maxn

 FOR str: ngrams(n,T1)

  FOR (int i=0; i < words.length - n+1; i++)

 ngrams.add(concat(words,i,i+n));// 将切好的字组合成词

 FOR (int i=start; i < end; i++)

   sb.append((i > start ? " " : "")+words[i]);// 切字

   return sb.toString();

  END FOR

 END FOR

 END FOR

END FOR

RETURN ngrams;//返回候选新词

③规则过滤：

IF 频率<阈值 or 含有停用词

 N1=remove(ngrams);     //过滤频率小于阈值或含有停用词的ngrams

END IF

④内部统计量过滤：

MMI(w₁…w_n)=logp(w₁…w_n)Avg(w₁…w_n);     //计算互信息

IF MMI < b

remove(N1);     //删除MMI小于阈值的词

END IF

RETURN N2;     //候选新词集合

⑤外部统计量过滤：

HL(x)=-∑ap(a|x) log p(a|x)

HR(x)=-∑bp(b|x) log p(b|x) //计算左右邻接熵

FOR num=2

IF HL(x)>c and HR(x)>d

N3=add(x);     //将左右邻接熵都大于阈值的词加入新词集合

 END IF

END FOR

FOR num=3

 IF HL(x)>e 左边界确定

 ELSE 向左扩展一个字形成y,计算HL(y)

 END IF

 FOR HL>阈值

  IF HR>阈值

   N3=add(x或者y):

  ELSE

   Remove(x或者y);

  END IF

 END FOR

END FOR

RETURN N3     //候选新词

6) 再过滤。由于候选新词集中含有大量的常用词,利用常用词典对其进行过滤。本文使用第六届中文信息测评提供的常用词典,共包含77 457个常用词。在该词典中出现的词都将过滤掉,最终得到微博新词集合N。

3 实验与分析

本实验采用的实验数据是COAE2014提供的数据,约1 000万条微博数据,大小约为1.5GB,从其中随机地抽取10万条数据作为本文的实验数据,对其进行新词发现研究。使用中文测评委员会提供的原始词典作为判断词语是否是新词的依据。

对于新词发现,一般采用正确率(P)、召回率(R)和F值来衡量系统的性能,其计算公式如下:

$P=\frac{AN}{N}\times 100%$

(7)

$R=\frac{AN}{M}\times 100%$

(8)

$F=\frac{2PR}{P+R}\times 100%$

(9)

其中:AN表示算法正确识别出的新词个数;N表示识别出的总的词串的个数;M表示重复串N-Gram中新词数目。

为了验证本文算法的有效性,使用传统的基于N-Gram的算法、基于N-Gram算法与互信息相结合的算法与本文算法MHN-Gram进行比较，其中频率阈值设为4，互信息阈值设为8，左右邻接熵阈值分别设为3和4。结果如表 1所示。

由表 1可知,本文提出的融合内外部统计量的微博新词发现方法在微博新词发现中取得了不错的效果,其准确率、召回率和F值相对于其他算法都有提高。传统N-Gram方法对于多字词的识别率较低,所以其准确率相对来说较低;文献^[5]提出的方法受分词工具对文本分词的影响,部分新词可能被错分、误分;基于N-Gram算法与互信息相结合的算法相对于传统N-Gram方法解决了多字词识别的问题,所以其准确率有了提高,但是该方法没有考虑词语的外部成词概率;而本文方法采用N-Gram方法对文本进行分词,在能识别多字词的基础上,同时考虑了词语的内部成词概率和外部成词概率,所以其效果有了提高。

为了进一步验证本文方法的效果,本文采用P@N值方法与霍帅等^[8]提出的基于微博内容的新词发现方法(记为MTND)进行对比。其中N值取500,即选取前500个词进行比较,结果如图 5所示。

由图 5可知,本文方法较MTND方法在准确率上有了相应的提高,由于MTND方法在分词步骤采用ICTCLAS作为分词工具,对一些新词容易错分。如“矮矬穷”,分词为“矮”“矬”“穷”。且MTND使用的是词频特征,对于一些语料中出现较少的新词,不能有效地识别。

4 结语

在自然语言处理过程中,仅仅依靠统计或者是规则方法来发现新词难以满足要求，所以本文采用统计与规则相结合的方法来发现新词。由于微博数据的文本一般较短,对其进行新词发现会存在数据稀疏的问题，而N-Gram算法能够较好地解决微博数据稀疏的问题,所以本文在N-Gram算法基础上,融合词语的互信息和邻接熵的统计量方法,以及词频和停用字等过滤规则相结合进行微博新词发现。实验结果表明,本文方法对微博新词的发现效果有所提高。但是,由于微博数据量的庞大,采用N-Gram算法对其进行分词会产生大量的词串,在实验的过程中发现其耗费的时间较长。今后将针对这个问题对其进行相应的改进,使其效率提高。