文本检测（共4篇）
文本检测 篇1
0 引言
计算机高级语言系统只能对一维文本型的数学表达式进行识别和运算, 一些被采集的二维数学表达式最终都要被转化成一维文本型的数学表达式来让计算机对其进行后续处理[1,2]。按照计算机定义的表达规则将数学表达式以一维文本的形式输入至计算机中极有利于提高计算机对该表达式的识别与运算效率。对于初等数学表达式来说, 它们基本上都能够根据这种表达规则用一维文本的形式表达出来[3], 基于此, 一些用于对一维文本型的初等数学表达式自动处理的系统也已开发出来[4,5,6]。虽然文本型的数学表达式符合计算机的表达规则且方便了计算机的处理, 但它与人工读写的习惯还是有些偏离的, 人工对其的读写错误在所难免。随着数学表达式的运算层次、运算内容的增加, 这种文本型的数学表达形式的复杂程度也会变得越来越高, 这对于文本型数学表达式的人工准确输入与检测的效率会造成一定的影响, 用计算机来检测人工输入的文本型数学表达式的有效性十分必要, 同时这种检测对于表达式的后续自动处理也具有十分重要的意义。
针对算术、三角函数、指数、对数等初等数学表达式中的文本句法错误, 根据数学表达式的文本规则, 采用模式匹配的方法, 通过扫描表达式来检测表达式中的这些句法错误。实验结果表明, 检测方法简单, 算法设计容易, 仅用一次扫描即可完成对表达式的文本句法检测, 且检测速度快, 正确检测率为100%。
1 初等数学表达式的文本表达规则
文本是计算机键盘能够直接输入的一维字符串表达形式, 文本句法是数学表达式的表达规则所规范的文本语句表达格式。文本型数学表达式的输入格式应尽量便于人工读写, 同时兼顾计算机对其的表示方法, 以便于计算机识别。算术、三角、指数、对数等的文本句法表达规则定义如下:
(1) 算术操作符的表示形式
加、减、乘、除、幂的文本形式分别是“+”、“-”、“*”、“/”、“^”, 如“ (x-y) * (x^2+x*y+y^2) ”中的操作符所示。其中, “*”有利于对变量个数的区分[3], 如:“x*y”中有两变量, 而将“MN”看成一个变量。
(2) 三角函数、对数操作符的表示形式
三角函数操作符有“sin”、“cos”、“tan”, 自然对数操作符为“ln”。
(3) 因子式的乘积
带括号或带绝对值符号的因子式与其它因子相乘时, 它们之间用乘号“*”来连接。如:“2*|-1+x|* (x-y) ”为有效表达式, “3|x-y|u”看成为无效表达式。
(4) 操作符与操作数相间排列
如:“2*x^2+3*x+4”为有效表达式, 而“x**^2”为无效表达式。
(5) 括号或绝对值符号成对出现
成对的括号或绝对值符号之间是变量或数或表达式。如:“ (-4) * (x-y) /|-x-y|”为有效表达式, 而“x* (x+y^2|”为无效表达式。
(6) 三角函数、对数的操作对象用括号包围
“sin (x) ”、“ln (x) ”为三角函数和对数的表示形式, 而“tanxy”被当成是一个变量。
(7) 操作符、括号、绝对值的分布关系
算术操作符、三角函数操作符、对数操作符一般与括号或绝对值符号的外部相邻, 而正负号还可与左括号或左绝对值符号的内部相邻, 左括号和左绝对值符号可以相邻, 右括号和右绝对值符号可以相邻。
如:“|-x- (y-a) |*x/ (|-x+y|^2-b) ”、“sin (x) ”、“ln (x) ”为有效表达式, 而“ (^2+x*) ”为无效表达式。
2 初等数学表达式中的错误文本句法模式
根据初等数学表达式的文本句法表达规则, 文本句法错误模式可分为2类。
(1) 表达式基元的相邻排列句法错误
数学表达式的基元即为表达式中的操作符和操作数。在文本型的数学表达式中, 相邻基元的文本排列规则构成了表达式的文本句法基础。文本型的初等数学表达式中相邻基元的错误句法模式如表1所示。
(2) 左右括号或绝对值符号的排列顺序错误
在数学表达式中, 除了有左右括号或绝对值符号成对的句法规则外, 还存在这些符号排列次序的规则, 即左括号或左绝对值符号排在左边 (或前面) , 右括号或右绝对值符号排在右边 (或后面) , 若次序排反, 则存在句法错误。如在“=a) +x-y*z- (x/y”中, 右括号排在了前面, 而左括号却排在了后面, 则其为无效表达式。
3 初等数学表达式的文本句法检测原理
从表达式左边的第一个字符开始, 往右扫描并识别表达式中的每一个字符。在扫描搜索的过程中, 根据2类错误句法模式, 分别采用模板匹配[7]和左右括号或绝对值符号相抵消的方法来检测表达式中的文本句法错误。
(1) 单字符操作符的句法检测
文本型算术表达式中的操作符基本上都是由单个字符组成。若检测到的单个字符为“=”、“+”、“-”、“*”、“/”、“^”、“ (”、“) ”、“|”, 则以第1类错误句法模式为模板, 检测与其前或后相邻的1个字符, 通过模板匹配的方法来检测这些操作符的句法错误。
(2) 操作数的提取
当检测到的1个字符不是“=”、“+”、“-”、“*”、“/”、“^”、“ (”、“) ”、“|”, 则其可能属于操作数。一个操作数可能由多个字符组成, 这时, 必须将其作为一个基元整体地提取出来。将表达式中任意1个字符用dn表示, 用p表示1个操作数基元, 并设p=Trim ("") , 其中Trim ("") 表示空字符[3]。多字符操作数基元的提取算法如下:
①令n=1。
②判别扫描搜索到的1个字符dn是否为“=”、“+”、“-”、“*”、“/”、“^”、“ (”、“) ”、“|”。
③若不是, 则p=p+dn, 并令n=n+1, 返回②;若是, 则p即为搜索到的1个操作数基元。
算法流程如图1所示。
(3) 三角函数、对数操作符的检测
当检测到有非操作符基元与左括号相邻时, 则以“sin”、“cos”、“tan”、“ln”为模板, 通过模板匹配的方法识别该非操作符, 若不为“sin”、“cos”、“tan”、“ln”, 则存在句法错误, 否则为三角函数、对数操作符。若为三角函数、对数操作符, 则与其相邻的左括号后面至一右括号之间的内容即为相应的操作对象。
(4) 左右括号或绝对值符号的检测
左右括号由字符“ (”、“) ”来识别, 对于只有一个字符形式“|”的左右绝对值符号的识别必须借助句法规则来进行。
①左右绝对值符号的识别
采用绝对值符号和其相邻的字符来判别其左右性。左右绝对值符号的有效句法模式如表2所示。表中的操作数为变量或数字。例如:由“|y-x|”中的“y”、“|-5+y|”中的“-”以及“|+x-y|”中的“+”都可判别与它们相邻的绝对值符号为左绝对值符号。当“+”或“-”号出现在“|”的右边时, “|”既可判别为左绝对值符号, 也可判别为右绝对值符号, 此时, 只能由与其左边相邻的基元来判别其左右性。例如:若左邻基元为“=”或“+”或“-”或“*”或“/”或“^”或“ (”, 则其为左绝对值符号;若左邻基元为操作数“) ”, 则其为右绝对值符号。
②绝对值符号的排列句法检测
根据表2中的句法模式来判别左右绝对值符号时, 若同一个绝对值符号既被判别为左绝对值符号, 又被判别为右绝对值符号, 则其排列句法存在错误。例如, 在“+|*x-y|”中, 由相邻两字符“+|”可判别此处的绝对值符号为左绝对值符号, 而由两相邻字符“|*”却可判别其为右绝对值符号, 则“+|*”就为错误句法。
若有两个或多个绝对值符号相邻, 则这些相邻的绝对值符号的性质相同, 即要么都是左绝对值符号, 要么都是右绝对值符号。它们可由与其最左边和最右边绝对值符号相邻的基元来判别, 若两边判别的结果不一致, 则该处绝对值就存在句法错误。例如:在“=||x-y|-R|”中, 由“=|”和“|x”都可判别“||”为两个相邻的左绝对值符号。而在“+t|||x-y|-R”中, 由“t|”和“|x”分别将“|||”判别为右和左绝对值符号, 则“t|||x”处绝对值的排列句法存在错误。
采用左右括号或绝对值符号个数相抵消的方法来识别左右括号或绝对值符号的排列次序, 算法为:当搜索到一个左括号或左绝对值符号时, 则括号或绝对值符号数加1;当搜索到一个右括号或右绝对值符号时, 则括号或绝对值符号数减1。若在搜索前将括号或绝对值符号数设为0时, 则当某次加减的结果出现负数时, 其排列次序就存在句法错误。如在“=a) +x-y*z- (x/y”中, 当搜索到右括号“) ”时, 得括号数为负1, 因此, “a) ”处存在句法错误。
(5) 角度、弧度的检测
角度表示的错误句法有:分在前、度在后、度分符号相邻, 如“32'40°”、“23'°”。对于弧度检测, 要先识别并提取出三角函数中的操作对象, 再检测之。
(6) 真数的检测
对数中的操作对象即为真数, 它不能为负数。如“ln (-8) ”为错误句法。先识别并提取出操作对象, 操作对象还不能带有“°”、“'”、“π”等符号。
设由基元相邻排列而成的文本型的初等数学表达式的形式为p1p2…pL, 其中pn (n=1, 2, …, L) 为表达式中的一个基元, L为表达式中基元的个数。对该表达式的数学文本句法检测的算法如下:
首先提取两相邻基元p1p2, 并以第1类句法错误模式为检测模板检测该基元串的排列句法。若存在第1类句法错误, 则显示句法错误;若不存在第1类句法错误, 则检测其第2类句法错误, 若存在第2类句法错误, 则显示句法错误;若不存在句法错误, 则继续扫描搜索并检测表达式中后续相邻两基元的排列句法, 即检测p2p3、p3p4、…、pnpn+1、…, 直到整个表达式基元串的搜索检测完毕。表达式的文本句法检测流程如图2所示。
4 实验及其结果
为验证检测方法, 用VB6.0设计了一个表达式输入及检测的实验系统, 系统界面如图3所示。在文本框中输入数学表达式, 按“确定”按钮则得出检测结果。图中输入了一个错误句法表达式“x- (a*b/) d^2- (e^x+sin (x+y) ) ) ^3”, 计算机则检测出表达式中的错误并显示“第7、8个字符“/) ”表达不正确!”, 可看出计算机检测结果的正确性。
运用该实验系统对大量的错误句法表达式进行了检测实验, 如表3所示。表中的“实例”栏给出的是几个具有代表性的错误表达式, “检测结果”栏为计算机对错误句法的检测结果。从表中可看出系统检测结果与人工检测结果一致, 正确检测率为100%。
5 结语
(1) 本文方法可有效地检测初等数学表达式中的文本句法错误, 该检测方法简单, 算法设计容易, 检测速度快, 仅用一次扫描即可检测出表达式中的错误。
(2) 定义的初等数学表达式的文本书写格式全部可由计算机键盘输入实现, 并符合数学表达式的句法规则。如:“=”、“+”、“-”、“*”、“/”、“^”、“sin”、“cos”、“tan”、“ln”、“|”、“ (”、“) ”、数字、变量等都可用键盘输入, 其中的绝对值符号“|”在一些高级语言中是少见的 (高级语言基本上都是用函数的形式来表示绝对值) , 因此, 定义的文本形式相对比较符合人的读写习惯。
(3) 用左右括号或绝对值符号相抵消的方法来检测括号或绝对值符号, 即可检测出它们的成对性又可检测出它们的排序性。当符号个数加减的结果不为零, 则符号不成对, 当加减的结果为负数时, 则符号排序有误。
(4) 无论是采用模式匹配法还是抵消法, 均离不开对相邻两基元排列句法的检测。相邻两基元的排列规则构成了正确表达式的文本句法基础, 对其的检测是对数学表达式文本句法检测的根本。由于数学表达式中相邻两基元排列规则的单一性, 十分适合采用模板匹配的方法来检测数学表达式中文本句法的正确性。
参考文献
[1]KamFai Chan, DitYan Yeung.Error detection, error correction and performance evaluation in on-line mathematical expression recognition[J].Pattern Recognition, 2001, 34 (8) :1671-1684.
[2]KamFai Chan, DitYan Yeung.An efficient syntactic approach to structural analysis of on-line handwritten mathematical expressions[J].Pattern Recognition, 2000, 33 (3) :375-384.
[3]陈庆章.Visual Basic程序设计基础[M].杭州:浙江科学技术出版社, 2007.
[4]Kostas Zotos.Performance comparison of Maple and Mathematica[J].Applied Mathematics and Computation, 2007, 188 (2) :1426-1429.
[5]田延安, 王建文, 杨莉.智能化工程计算器的设计与实现[J].计算机工程与设计, 2009, 30 (17) :4095-4096, 4137.
[6]李士雨, 秦汇川.公式输入技术及其应用[J].天津大学学报, 2000, 33 (6) :776-780.
[7]徐珊, 袁小坊, 王东, 等.Sunday字符串匹配算法的效率改进[J].计算机工程与应用, 2011, 47 (29) :96-98, 160.
文本检测 篇2
在这个海量信息充斥的时代,信息的重复也随之增多,而其中一些相似文本的出现不仅不能丰富信息的价值,反而造成资源的浪费。因此,如何在大规模数据中快速检测出这些相似的文档是一项十分重要的技术。目前,国内、外在该领域的检测手段普遍都采用将文本哈希成数字指纹的技术。特别是Simhash算法,由于其检测准确率高,“降维”的思想使得检测速度快,同时还可以根据指纹距离反映文本内容的差异程度,因此受到广泛的应用。但由于中文语义的复杂性,包括同义词,一词多义等问题,现有Simhash算法对于不同文档采用同义词作为关键字的相似检测性能并不是很理想。例如,两篇文档的关键词分别为:大规模、文档、去重、技术和海量、文本、查重、算法。
基于上述原因,本文在现有Simhash算法的基础上,通过对其进行改进,提出一种基于同义词扩展编码的语义指纹生成方法,实现海量文本的快速相似检测。该方法利用基于同义词词典的语义扩展编码,通过Simhash函数映射生成固定长度的语义指纹,解决了其中普通哈希函数无法进行语义表达的问题,扩展了指纹的表达能力,提升了检测准确率。再根据指纹信息进行分段索引建立,减少了比对过程中的冗余操作,提高整体检测效率。通过实验验证,该算法在海量文本相似检测过程中性能良好,其快速匹配机制也满足了大数据环境下的检测需求。
2 相关工作
2.1 Simhash算法
Simhash算法在2002年由Charikar[1]提出,后由Manku对其进行扩展研究,被认为是当前文本相似检测处理中最有效的算法之一[2]。Simhash算法实质上是一种具有局部敏感特征的哈希算法,它能够将文本内容特征向量映射到一个指定维度的二进制比特向量上,并由这个二进制哈希值来表示文本内容的数字指纹(Digital Fingerprint)。区别于其他哈希算法,Simhash不仅在保证低碰撞率的条件下通过哈希映射将原本不同的文本内容映射到不同的哈希空间中,同时还能通过比特位数的不同体现两个比较文本的相似性,这也正是其局部敏感特性的体现。根据局部敏感哈希算法(Local Sensitive Hashing,LSH)的基本思想[3],两篇文本p,q相似的可能性与其距离呈负相关关系,即它们之间的距离越小,相似的可能性就越高,反之,则相似的可能性就越低。这里我们定义Simhash函数h,则映射后h(p),h(q)与其距离的关系满足以下两个局部敏感性质(公式1):
这里参数c>1,概率P1>P2,p与q的距离也就是我们所需计算的文本相似度,h(p),h(q)的距离由二者的汉明距离来确定。两篇文档的相似性计算经过哈希映射后,转化为两篇文本的指纹值汉明距离计算。
基于Simhash的相似文本检测需要经过文本特征提取、指纹生成和指纹索引匹配三个数据处理过程。首先,算法以经过分词的文档词项作为文档的特征,其对应的频率作为每个特征的权值wi。通过普通的hash函数计算得到每个分词的一个f位的二进制哈希值,再将所有特征的哈希值加权累加,得到一个同样为f位的总向量V,根据V中各位的符号生成文档的数字指纹F。最后根据指纹的索引值指纹库中进行比对,找到满足一定条件的其他指纹作为相似比对结果。
2.2 同义词词林
在信息检索领域,将关键词进行同义词扩展实现模糊检索,这类方案目前已有一定研究[4,5,6]一般地,通过同义词挖掘算法事先建立同义词词库,再运用该词库对检索关键词进行语义扩展,生成一个扩展关键词集合。在检索时,根据集合内的关键词生成索引,依据索引进行查询比对。在本文中,需要对关键词的语义进行同义词概念的扩展,把从属于某一概念下的同义词和关联词均划归到该概念下的集合中,并以该集合的编码作为语义编码返回处理。
同义词的扩展是以同义词词典作为基础进行操作,而“同义词词林”作为其中一个具有代表性的中文词典,在中文自然语言处理领域受到广泛关注。在词林中,将所有词汇按照树状结构分层地组织到其中,树中的每个结点代表一个概念域。自顶向下整个词林树共有5层,依次对应1到2个编码进行标识,将各个标识排列后就形成词元的编码。词林的层次与其分类相对应,而分类的原则是依据汉语语言特点,以词义为主,兼顾词类,充分体现词义的聚集。
同义词词林依据“词义为主,兼顾词类”的原则,结合汉语语言本身的特点及其使用规则将收录的所有词语划分为三个等级:其中大类共12个,中类94个,小类多达1428个。再向下根据词义集中的原则划分成3925个词群并排列,每个词群对应一个标题词。最后按照以下三个原则划分成最小的子群:一、词义的细微差别;二、修辞色彩与使用范围的不同;三、词语结构的差异。其中第一个是主要的。
3 基于语义指纹的快速相似检测算法
本文提出的文本相似检测算法主要是基于经典的Simhash算法,而其主体思想是“降维”,通过将高维的文本特征向量映射成一个唯一的二进制指纹值,从而达到减少文本表示空间的作用。不同于其他指纹生成算法,Simhash算法可以将两篇相似的文本映射到一个距离相对较近的低维特征空间中,通过在该空间中距离的大小判别两个文本向量的相似程度。但由于中文语义的复杂性,包括同义词,一词多义等问题,现有Simhash算法对于不同文档采用同义词作为关键字的相似检测性能并不是很理想。例如,两篇文档的关键词分别为:大规模、文档、去重、技术和海量、文本、查重、算法。基于上述原因,本课题在现有Simhash指纹生成算法的基础上,通过对其进行改进,提出一种基于同义词扩展编码的语义指纹生成方法。语义指纹的生成流程如图1所示。
文本最终的语义指纹值是基于离散化的文本特征提取的结果,数据指纹间的汉明距离越接近,则代表文本的语义越相似。根据同义词词林在词语组织上的层次架构,对待文本中的关键词进行定位标识,在词林层级结构树中找到该关键词所有义项所属的层次,考虑到一词多义的情况,一个词的不同义项间可能差距较大,因此根据其上下文信息进行筛选,取最大概率的词项所属词群编码进行扩展。概率判定的指标主要基于该词与其上下文词汇的互信息。
一般地,在应用Simhash算法时,将划分出的词语作为文本的基本特征,再结合每一个词语的词频作为其权重。考虑到本课题算法中,文本块的划分以句子为单位,而各个单词在一句话中出现的频率区分度并不会很大,因此在本课题中特征的权值采用另一个指标——单词的词性。从词性角度来说,名词表征着文档更多的特征,因此其权重应该最高,动词次之,形容词再次之,其余词权重最低。
根据文本的特征向量信息生成文本语义指纹的算法如下:
输入:一个64维特征向量V={w1,w2…,wn},其中w1,w2,…,wn分别是文本关键词特征,其对应相对值分别为we1,we2,……wen;
输出:一个64位的二进制语义指纹F={f1,f2,…,fb};
1)初始化一组64位的二进制向量,其中一个向量F作为文本的语义指纹,其他向量用来存储关键词对应的同义词扩展词群编码;
2)将各个关键词在同义词词林中找到对应多个词项,并根据与前一个词以及后一个词互信息(公式2),计算该词汇对应的词群编码,并转换成64位二进制hash值;
3)根据关键词各位的hash值以及其标注词性的权重进行调整。如果第i位为1,则将该词hash值的第i位置为权值,如果为0,则将该位置为负权值;
4)将所有词向量的对应位进行求和运算,结果向量记为F’;
5)按照向量F’各个位的正负确定语义指纹F的数值:如果F’第i位为正,则指纹F的第i位置为1,反之,则置对应位为0。
这样,就得到了经过同义词扩展后的文本特征hash值的加权综合结果。
4 实验验证
4.1 实验数据及工具
由于汉语中没有句子相似度检索用的标准测试数据集,因此本实验的数据是通过从搜狗语料库网页数据中进行处理得到。实验所用语料为标准中文数据集SOGOU-T,从中选取800篇文档作为基础数据集,经过本课题语义指纹生成算法处理后形成指纹存入数据库中,作为相似检测依据。测试文档集中,其中一部分从基础数据集中选取200篇,并作不同种类的修改,构成论文相似目标数据集。通过将本文算法和其他算法,包括经典的词频统计算法,未改进的simhash算法进行比较。
文本处理过程中,采用ICTALAS中文分词系统实现,该系统采用层叠隐马模型,该工具具有160万字/秒的高速处理能力,同时支持外文字母以及数字等的分词处理和用户自定义词典的扩展,目前共收录有392755个词汇。
4.2 评价标准
本文采用传统的准确率、召回率两个关键指标来对本文提出的算法进行性能评价。假设在进行文本相似性检测的实验结果如表1所列,则其各参数的定义如下:
准确率:被检测相似句子中实际相似句子所占的比例,衡量的是查准率;
召回率:实际相似句子中被检测出的比例,衡量的是查全率;
4.3 实验结果分析
通过上述流程介绍,下面进行实验,对本文提出的相似度检测算法进行验证。实验运行环境是CPU为Intel(R)i53210.2.50GHz,内存4GB,操作系统为windows8.1 64bit,采用Java语言实现算法,并在My Eclipse上运行。
首先对算法运行情况进行分析。从整体流程上看,本文采用的相似检测方法可以分为个主要步骤:文本的语句划分及分词处理、构建特征向量、文本语义指纹生成、指纹对比计算四个过程。
如图2、图3所示,本文算法的经过加入同义词替换等处理的测试文本,文本的准确率和召回率都达到80%以上。而相比之下,传统simhash算法和词频统计算法的两项指标都只有70%左右,通过图2曲线的比较可以很直观地发现本文算法在语义识别上准确率有很大提升。同时,由于简化传统simhash算法根据Tfidf来计算关键词相对值的过程,本文算法在计算速度上也有一定提高,这与理论预期结果相一致。
5 结束语
针对传统的Simhash算法无法处理中文文本信息中一词多义、同义词等语义问题,本文提出一种基于同义词扩展词群编码的语义指纹改进算法,利用同义词词林中的语义项层次结构关系,对检测文本中关键词进行语义词群的扩展,利用词群中的关系信息来融合不同的同义词,再通过基于词性对关键词权值的确定,生成具有语义信息的语义指纹。经过与Simhash算法以及词频统计算法进行比对研究,实验表明,本文中的算法能对相似文本实现快速去重,而且能够保持较高的准确率、召回率以及F1值,弥补了其他算法在文本语义表达方面的不足,特别针对同义词替换的情况。同时,在时间效率上,本文提出的算法相比原始simhash算法,节省了大量无意义的比较计算处理,总体上提高了检测效率。
今后的研究目标是完善语料库,不断改进文本相似检测算法,不仅考虑到词汇对相似度计算的影响,同时挖掘更复杂情况如词汇组合、语句结构修改等方面的检测算法,力求在文本相似度计算中达到更高的准确度。
参考文献
[1]Moses S.Charikar.Similarity Estimation Techniques fromRoundings Algorithms[R].ACM STOC`02.May,2002:19-21.
[2]Sadowski C,Levin G.Simhash:Hash-based similarity detec-tion[R].Technical report,Google,2007.
[3]Datar M,Immorlica N,Indyk P,et al.Locality sensitive hash-ing scheme based on p-stable distributions[R].In Proceedingsof the ACM Symposium on Computational Geometry.2004.23-36.
[4]田久乐,赵蔚.基于同义词词林的词语相似度计算方法[J].吉林大学学报:信息科学版,2012,28(6):602-608.
[5]张继东,刘萍.基于语料库同义词辨析的一般方法[J].解放军外国语学院学报,2005,28(6):49-52.
文本检测 篇3
自然场景文本检测方法主要分为两类:基于连通区域的方法[1[1,2]和基于纹理的方法[3,4]]。基于连通区域的方法通常是提取出连通域后根据几何规则或其他文本特征检测文本区域,这类方法时间复杂度低,在背景简单时能取得较好的检测效果;基于纹理的方法通常利用纹理分析技术,如小波变换、离散余弦变换、Gabor滤波器等[5]。这类方法受文本大小、字体的影响较小,通用性较强。为了提高复杂背景下文本检测的鲁棒性,将这两类方法相结合已成为一种研究趋势。
鉴于此,文章提出一种基于小波变换和BTC编码的纹理特征提取方法,并结合SVM实现候选文本区域的精确分类。算法首先利用sobel边缘检测和几何规则得到候选文本区域,对候选文本区域进行小波分解和BTC编码,所提取的WT-BTC特征能反映水平、垂直和对角方向的纹理信息,运用所得的纹理特征训练对应不同方向的SVM分类器,并将其组合以实现候选文本区域的分类。由于结合了连通区域方法和纹理方法的优点,所提算法在复杂背景下对场景文本有更好的检测效果。
1 候选文本区域
由于文本字符具有丰富的边缘信息。为强化边缘效应,采用sobel算子[6]分别对图像RGB三个颜色分量进行梯度遍历,结果如图1(b)所示。为了避免对低对比度和低照度文字的漏检,采用自适应二值化方法对边缘图像进行二值化[7],如图1(c)。因为场景文本通常为单独的连通域,其大小形状和排列方式都有一定的规则,所以采用如下规则去除一些明显的非文字区域。
1.1 字符大小
自然场景中的文本字符大小占整个图像的面积有限,通常不超过图像面积的1/2。为能准确识别,其尺度大小不能低于10像素。即
式(1)中:A_CCi为连通分量CCi的面积;W,H分别为原图像宽度和高度。
1.2 字符区域宽高比
场景文本通常符合一定的宽高比。即
式(2)中,W_CCi、H_CCi分别为连通分量CCi的宽度和高度。此处比值阈值若选取过小,则会错误去除部分文本区域;若选取过大,则会将非文字区域保留,增加后续处理时间。通过测试阈值为10时效果最佳。
1.3 字符边缘密度
文本区域的边缘通常比较密集。采用边缘密度来确定候选文本区域,即
式(3)中,N_CCi为连通区域的边缘像素数。
将满足上述约束条件的连通域判定为候选文本区域,如图1所示。从图1(e)中可看出候选文本区域中还有部分非文本区域,所以有必要对候选文本区域进一步筛选。
2 WT-BTC特征
对候选文本区域先进行二维离散小波变换,对水平、垂直、对角的三个高频分量图像进行BTC编码,提取WT-BTC特征,用于SVM训练与分类。
2.1 小波变换
小波变换[8]是近些年被广泛应用在图像处理领域的数学工具。二维图像经小波分解后的高频分量能反映水平、垂直、对角不同方向上变化明显的纹理信息,而文本字符,特别是中文字符,因笔画结构在这三个方向上的纹理较于背景更为突出,所以采用小波变换进行特征提取。小波函数类型很多,其中Haar小波[9]简单便捷,且滤波器更短,更易刻画小的纹理基元,因此本文选用Haar小波对文字图像进行一层小波分解。将M×N大小的候选文本区域表示为I(m,n),m=1,…,M,n=1,…,N。对I(m,n)进行二维离散小波变换,在尺度j上可分解为:
式(4)中,I2j+1(m,n)是低频子图像,是对原图的近似逼近;wH2j+1(m,n)、wV2j+1(m,n)、wD2j+1(m,n)分别是图像水平、垂直、对角方向上的高频细节分量,其能很好地描述文本区域在各个方向上的纹理信息,如图2所示。
2.2 BTC编码
为了获得更细致的纹理特征,需要对上述子带图像进一步处理。方块编码算法是一种有效、快速的有损数字图像的压缩技术[10],利用模板对图像分块后根据设定的阈值进行像素颜色值量化,构成位映射矩阵代替子块图像达到图像压缩的目的。BTC压缩编码是要以尽可能紧凑的特征码值来表征原图像,而图像中的文本区域相比于背景区域,因笔画丰富其纹理特征更为明显,因此采用BTC编码能进一步区分文本区域与非文本区域。具体步骤如下。
(1)对于候选文本区域小波变换后得到的水平、垂直、对角方向上的高频子带图像wH(m,n)、wV(m,n)、wD(m,n),大小为M×N,为方便标记分别记为H、V、D。设置L×L的模板,每个模板包含L×L个像素,将此模板分别遍历三个高频子带图像将其划分成互不重叠的子块。
(2)以水平方向子带图像H为例,对其中每个子块图像分别计算均值,设为阈值Tk。
式(5)中,k={1,2,…,(M/L)×(N/L)},Hk(i,j)表示第k个子块图像中点(i,j)的像素值。
(3)按照下列公式对子块内像素进行编码。
式(6)中BHk(i,j)表示编码形成的二值位图中第k个图像块点(i,j)的值。
2.3 WT-BTC特征提取
因为均值(μ)、方差(σ2)具有旋转不变性,适合不同方向文本字符的检测;度量数据分布的统计学参数偏度(e)能反映图像区域块内像素值的密集程度,这可以很好地区分文本区域与背景区域,所以提取这三种统计量作为纹理特征。根据两类像素计算第k个子块图像的两个均值、两个方差及两个偏度。计算公式如下。
式中H1u,k、H1σ2,k、He1,k分别表示第k个子块图像中编码为“1”对应像素点的均值、方差、偏度;H0u,k,H0σ2,k,He0,k分别表示第k个子块图像中编码为“0”对应像素点的均值、方差、偏度。
将所有k个子块的6个特征值求均值得到Hu1、Hu0、H1σ2、H0σ2、He1、He0并构成H子带的纹理特征矢量φ(H)。
同样方法求出垂直、对角子带图像的纹理特征矢量φ(V)、φ(D)。
3 SVM组合分类器设计
SVM机器学习方法在特征表示方面能力很强,适用于字符大小、尺寸不一致,排列方式不固定的复杂场景图像中的文本检测问题。文本字符尤其是中文字符,其笔画主要是由“横”、“竖”、“撇”及“捺”四种笔画组成,由于“撇”、“捺”特征相对较弱,所以将两者合并,这正好与小波分解的三个高频方向契合。因此,文本字符在水平、垂直、对角方向上的纹理特征较于背景区域更强。为了更好地利用SVM分类思想并提高复杂背景下候选文本区域的分类精度,运用所得的水平、垂直、对角方向的纹理特征训练对应不同方向的SVM分类器,并将其组合对候选文本区域精确检测。三个SVM核函数统一选取复杂性最小、置信范围也较小的径向基函数,即
式(14)中,径向基函数的核σ通过交叉验证的方法确定。实验中所采用的SVM分类器工具来源于Chang C.C.等人研究开发的支持向量机工具包LIBSVM软件包[11]。从实验图片中分割1 000个文本块作为正样本,随机分割2 000个非文本块作为负样本,组成样本集。样本示例如图3所示。
在训练过程执行前,首先将样本集均分成训练样本集和验证样本集,各包含500个正样本和1 000个负样本。在训练过程中采用循环验证的方法对SVM分类器进行多次训练,提高分类精度。
3.1 SVM模型训练
图4(a)表示SVM的训练过程结构图。其中,H、V、D分别是小波变换后水平方向、垂直方向和对角方向文本区域样本,B是小波变换后输出的背景区域样本。φ(x)表示样本图像关于均值μ、方差σ2和偏度e的特征提取函数。分类器用分类函数G(Z)表示:
式(15)中,Z表示样本,yj=±1表示输入样本向量的类标,αj是拉格朗日系数,b是分类面方程的常数。GH(Z)、GV(Z)、GD(Z)分别对应水平、垂直、对角三个方向的分类器。ωi是三个方向分类器的权值。因为大部分文本水平、垂直方向的信息较多,对角方向偏少,所以选取ωi=[0.35,0.35,0.3]作为权重计算函数,所生成的分类网络输出为三个分类器输出的权重和σ(ωi,G(Z))。对每一个SVM分类器,使用交叉验证的方法进行样本训练。整个训练过程反复迭代直到验证样本的准确率大于一个给定的阈值T。为保证检测性能,T设为98%。
3.2 SVM组合分类
生成SVM组合分类模型后对候选文本区域分类。图4(b)表示SVM组合分类过程结构图。具体步骤:
(1)对输入的候选文本区域进行一层小波分解和BTC编码;
(2)提取三个高频分量的纹理特征矢量φ(H)、φ(V)、φ(D)。使用横向分类器GH(Z)预测水平分量H的分类结果GH。当为文本块时GH=1;当为非文本块时GH=0。依次计算分量图像V、D的分类结果GV,GD。
(3)使用权值矩阵ωi构造最终的识别函数B
若输出B=1,则判定为文本区域,保留;若输出B≠1,则判定文非文本区域,舍弃。
4 实验结果与分析
实验采用两种数据库对算法的性能进行测试,一种是ICDAR2003和MSRA-TD500公开数据库,其中MSRA-TD500数据集包含中文文本;另一种是自建的用于场景文本检测实验的数据库,其中包含不同字体、不同大小、不同光照条件和复杂背景等文本图像,共计1 000幅。为量化检测算法的有效性,性能指标采用常用的准确率(P)、召回率(R)、F指数(F)[12],定义如下。
式中,c表示场景图像中检测到的文本域的个数,f表示被错误检测的场景图像中非文本区域个数,即误检数,d表示场景图像中未被检测到的文本区域个数。
4.1 算法综合性能测试
为检验算法综合性能,从两个数据库中选取500张具有代表性的文本图像作为测试数据集,其中包含不同字体、排列方式、光照条件的复杂场景文本图像。图5给出了部分文本定位结果。
从图5可以看出,所提算法能够对不同字体、尺寸大小、排列方式以及复杂背景下的文本进行检测,鲁棒性较强。原因分析:(1)在粗检测阶段,分析文本边缘特征定位文本块,采用自适应的二值化方法避免了不同光照的影响;(2)提取的WT-BTC特征能很好地表征图像块的纹理信息;(3)在SVM分类时,针对不同方向的纹理特征单独训练和分类,降低了文本定位的虚警率。
4.2 与其他算法的比较
将关于场景文本检测的文献[5]、文献[7]、文献[13]、文献[14]、文献[15]中的算法与本文所提算法,采用相同的数据库且在相同实验环境下进行性能对比,实验结果如表1所示。从表中可以看出,本文算法的综合性能更加优越。
5 结束语
文本检测 篇4
微博客,又称微博,作为一种新的传播载体,包含了大量用户针对人物、事件等的评论信息,因此在网络舆情发起和传播中起着重要作用,并成为网络舆情浏览和分析的重要数据源之一。
但是,在微博空间,便捷的“转发”操作以及快速增长的“网络水军”,使得大量相同或相似的数据在微博空间内迅速传播。同时,噪音微博作为一种宣传手段也迅猛蔓延到微博空间的各个角落。对于网络舆情分析而言,噪音微博通常没有意义,相同或相似的微博也只具有一定的统计意义。对于微博用户的浏览而言,用户会发现自己看到的微博数据很多,但真正得到的有意义的信息量却很有限,浪费了时间和精力。同时,这类微博的存在也严重影响到了信息检索的准确性,大大降低了分析的可信性。因此,对微博客文本信息进行过滤提纯,对于减轻用户浏览理解和系统存储的负担,提高文本内容检索、网络舆情分析的效率等都具有十分重要的意义。
基于此,本文分析了微博客文本流中噪音微博和相似微博的特点,提出一种针对微博文本流的噪音判别和内容相似性双重检测的过滤方法。通过URL、字符率、高频词等特征判别,过滤噪音微博。通过分段过滤和索引过滤的双重内容过滤,检测和剔除相似微博。实验表明了这些方法能有效的对海量中文微博数据进行提纯,准确地过滤掉其中的噪音微博和相似微博。
1 相关工作
微博客近年来已经成为相关领域的研究热点。Sakaki等利用微博数据的实时性特征,将Twitter[1]中的用户看作“社会信息传感器”,并以此来对地震、台风等自然灾害信息进行跟踪与预警[2]。Weng等研究微博空间中关键用户发现问题,考虑用户间的话题相似性和链接结构,设计新的排序算法Twitter Rank来发现Twitter中有影响力的用户[3]。在文献[4]中,作者利用Twitter中蕴含的情感信息来对竞选结果进行预测。除此之外,在热点话题发现[5]、短文本分类[6]、虚拟社群挖掘[7]都是微博研究中的热点问题。
文本过滤是指依据一定的标准和运用一定的工具从大量的文本数据流中选取用户需要的信息或剔除用户不需要的信息的方法[8]。在微博文本过滤的研究方面,文献[9]对微博数据进行训练,利用半监督的机器学习支持向量机的方法发现微博上的噪音制造者。文献[10]提出了统计字符种类和最短编辑距离计算方法来判定Twitter中近似重复的消息。
虽然微博的研究目前已成为一个热点,但总体上,针对微博的文本过滤技术还处于起步阶段。中文微博考虑到“微博文本流”这一特点,以上过滤方法并不适用。因此,本文在分析了中文微博文本流中噪音微博和相似微博特点的基础上,提出了针对微博文本流的噪音判别和内容相似性双重检测的过滤方法,通过对微博数据实时抓取后再进行过滤,实现了保留高质量微博数据的目标。
2 中文微博客噪音文本、相似文本的特点
2.1 噪音微博文本的特点
目前针对微博的工作主要为舆情分析、观点挖掘等,因此我们将微博中对这类应用没有实际意义的微博数据定义为噪音微博,本文将其分为以下两类:广告型噪音微博和字符型噪音微博。
(1)广告型噪音微博
广告型噪音微博是指为达到宣传、增加点击率的目的而在微博客中有意加入的URL链接。为了分析该类噪音微博的特征,我们取不同时间段随机下载了1000条微博数据,并进行人工标注,统计发现其中噪音微博的覆盖率高达29.9%。进一步分析发现噪音微博中含有URL链接的信息约占85%,说明广告型噪音微博占有相当高的比例,同时说明了链接特征是广告型噪音微博最根本特点。噪音散布者通常利用链接的特性,人为地发表指向其他网站的链接,旨在宣传产品或者提升网站权威性。表1给出一些广告型噪音微博例子,其中都含有链接。
(2)字符型噪音微博
字符型噪音微博包括纯数字、纯英文等对中文微博分析和舆情分析无意义的字符型消息,以及用户分享视频、图片的文本保存形式,例如“分享图片”代表了用户在微博上分享的图片格式的文本保存信息。表2给出一些字符型噪音微博的例子。
我们分别统计了500条噪音微博和500条正常微博的文本字数,平均值为66和44,噪音文本的字数大于正常微博。图1显示了正常微博和噪音微博不同字数所占有的比率,噪音微博字数较为平均,长消息和短消息覆盖率相差不大,而普通用户发表的微博主要以少于40字的短消息为主,这是因为微博用户通常用简短的文字发表自己的观点和心情。图2显示了不同字数的正常微博和噪音微博消息中非汉字字符所占比率,发现噪音微博中所含有的无意义字符占有非常高的比率,例如在小于20字的噪音消息中,90%是非汉字字符,在这样的微博中通常只有URL链接的信息。同时我们统计了10万条微博信息的平均非汉字字符率,约为30%,而这500条噪音微博的平均字符率约为50%,因此本文将微博的字符率作为噪音微博判定的依据之一。
(3)噪音微博中的高频词
本文在人工标注的过程中发现噪音微博中大多含有URL,而在含有URL的噪音微博中用词相对集中,普通微博用词分散。这样,利用大量的含有URL的微博,可以找到噪音微博中的常用词。我们利用这一特点,从大量微博中提取出含有URL的微博消息作为训练集,对微博进行分词,去除停用词后作为噪音微博高频词的词库。统计发现词库中词的出现频率范围较大,本文保留了高于某一合适频率的词语作为高频词匹配词典。含有高频词的微博实例如表3所示。通过构建噪音微博高频词词典,累加高频词的频率计算权值,作为噪音微博判定的参考。同时,本文采用人工分析的方法修正了普通微博也会出现的高频词语,例如“微博”。
综上分析可见,噪音微博的3个主要特点是:(1)字符率较高;(2)URL较多;(3)噪音微博的高频词。其中(1)、(2)是显著特点,而(3)的检测则需要对内容进行分析,第3节将基于这3个特点检测噪音微博。
2.2 相似微博文本的特点
本文在对新浪微博平台的观察中发现,用户在发送消息时经常会复制别人的消息,或者直接转发好友的消息,或者经过少量的添加、删除、修改部分原始微博后作为新的消息再发送。同时,微博客空间内存在一定数量的“网络水军”,不断发布重复的微博数据。这些都是相似微博产生的原因,表4给出了一些例子。
可见,相同或相似微博本身并非噪音微博那样具有明显特点,只有通过内容相似性分析予以检测。
3 微博文本流中噪音微博和相似微博的过滤
我们利用API对微博进行实时抓取,首先基于噪音微博特征的判定方法,通过URL链接、字符率、高频词特征判别,过滤噪音微博。对文本进行预处理工作后,去掉微博本身特有的符号特征,然后基于VSM模型描述微博并采用向量夹角的余弦计算两微博间相似度,通过分段过滤和索引过滤的双重内容过滤,检测和剔除相似微博。第一重过滤基于时间分段,段内的微博之间进行相似度比较。第二重过滤时,考虑“微博文本流”的特点,将第一重过滤输出的微博集在缓冲池中构建索引,以提高搜索和比较的性能。微博文本流的过滤方法如图3所示。
3.1 基于特征判别的噪音微博检测与过滤
结合2.1节介绍的三个典型的噪音微博特征,即字符率较高、URL较多、以及噪音微博的高频词,首先以微博的字符率作为基础权值,对含有URL这种最为典型的噪音微博文本加上较高的权值,最后匹配高频词,本文对高频词的频率扩大了5倍。基于此,本文提出了算法1计算出微博的噪音权值,若大于所设定的阈值则过滤掉该条微博。
算法1 Spam microblog filter based on feature judgment
Input:microblogs mbs,spam weightβ,high frequency word lexicon HF,total thresholdθ;
Output:result without spam microblog result Set;
Method:
算法1中,第2)行是对字符率的处理,第3)行是对URL链接的处理,第6)~7)行是借助于2.1.3中所述的高频词典HF对高频词的处理。这三个特征的判别均以对β加权的形式统一到一个权重上,最后在第8)~9)行,判断该权重是否满足阈值θ,满足则视为噪音微博予以剔除。
3.2 特殊类型微博文本的预处理
微博中转发回复以及提到某一用户都有一定特征,系统会给消息加上一些固定模式的特殊字符(如//@),这类字符对转发回复消息的识别提供了可靠条件。微博中还包括“@”加上用户名,表示该微博是针对这一用户。由于本文仅考虑“原始消息”,在进行相似文本判断前对这类消息进行预处理,把特殊字符过滤掉。经过基于微博特殊规则的字符串匹配算法,使微博消息缩短,利于进一步的相似文本判断。预处理前后的微博文本对比如表5所示。
3.3 基于内容计算的相似微博双重检测与过滤
微博数据流属于海量数据,如果在整个数据集中去重,需要花费很多时间,也不能及时的得到处理结果,难以应用到实际中。而且,研究发现大量的转发微博更多地出现在相近时间里,重复率随着发表时间差距的增大而减小。为了证明这一规律,本文对各个时间段的总共800条话题微博计算重复率,利用VSM模型表达、向量夹角的余弦计算两条微博的相似值,该值高于所设阈值则定义为重复,重复率即为重复微博占段内总微博数的比例。如图4所示,在短时间内微博的重复率较高,随着相隔时间的加大,微博重复率迅速减少到很小值。
为了在尽量不降低召回率的前提下提高准确率,改善文本过滤性能,本文根据微博重复率随时间递减的特性,提出基于内容相似性计算的双重过滤法:首先对抓取的一个时间段内微博进行第一重过滤———分段过滤,再对相近时间发表的微博进行第二重过滤———索引过滤,达到微博文本流整体上的过滤,这样对发表时间相隔较短的微博去重,即能保证准确率,同时极大地减少处理时间,提高可用性。
(1)第一重内容过滤———分段过滤
首先,对噪音微博过滤以及文本预处理后的微博集分词,过滤停用词。然后构建向量空间模型,将每一条微博转换为一个文本向量,通过计算每两个文本向量的余弦值作为相似度,将相似度存在矩阵中,最后得到一个上三角相似度矩阵。遍历矩阵,查找相似的微博,如果相似值大于设定的阈值,则将其中一条过滤掉,如算法2所示。
算法2 Subsection-based similar microblogs filter
Input:microblogs subsection mbs,thresholdγ;
Output:result with less similar microblog in the subsection result Set;
Method:
(2)第二重内容过滤———索引过滤
经过算法2对微博进行一重过滤后,这里再对输出结果进行第二重过滤。本文使用索引查找相似微博的算法。首先构建一个微博缓冲池,存放最近发表的微博。由于微博的重复率随发表时间的递增而递减,因此本文只对最新一批微博构建索引。算法的基本原理如图5所示。图中的数据集经过了噪音微博过滤、微博预处理以及相似微博的一重过滤。图中(a)表示data5尚未加入缓冲池的状态,(b)表示data1数据集从缓冲池中移除后,data5加入缓冲池的状态。
算法3说明了将一重过滤后的微博集进行二重过滤的过程。首先对该微博集中的每一条进行分词处理,去除停用词。然后使用该条微博的分词结果集作为检索关键词,即可在构建的缓冲池索引中检索出最相关的一条微博。同样VSM模型表达、向量夹角的余弦计算两条微博的相似值。如果相似度值大于设定的阈值,则表示该微博与检索出的微博相似,过滤掉该微博。这样循环,对第一重过滤后的每一条微博再过滤后,将剩余微博集加入缓冲池进行更新,同时对缓冲池里的微博重新构建索引,该索引将作为下一批微博集进行二重过滤时所使用的新索引。
算法3 Index-based similar microblogs filter
Input:microblogs from first-level filter mbs,thresholdγ;
Output:result without similar microblog result Set;Method:
4 实验
4.1 实验数据与评价标准
目前在微博客过滤领域,尚无国际公认的标准测试语料库,本文从国内用户最多的新浪微博下载了公共大厅微博和话题微博作为实验数据源。本文的评价指标采用正确率(Precision)、召回率(Recall)及微F测度(F-score)来衡量算法性能的高低[11]。计算如式(1)、式(2)和式(3)所示。对于噪音微博分类,其中S为噪音微博分类算法检测为噪音微博结果中判断正确的数量,C是分类算法检测为噪音微博的数量,R是人工标注测试数据集中噪音微博的总数量。同样,对于相似微博过滤方法,其中S为相似微博检测算法检测为相似微博结果中判断正确的数量,C是算法检测为相似微博的数量,R是人工标注测试数据集中相似微博的总数量。实验中,程序找出的相似微博与人工标注的这组相似微博完全相同则为正确。
4.2 数据集大小对噪音微博过滤效果的影响
由于不同的数据集大小产生不同的噪音微博高频词,进而会影响到噪音微博过滤的效果,本文在阈值β为1的情况下,增加数据集的大小做了多组实验。首先从3000万微博中提取出含有URL的微博共700万作为总的噪音微博高频词训练集,然后取10万、50万、100万、200万、300万、400万、500万7组不同大小的数据集提取高频词,实验结果如图6所示,当数据量较小时,噪音高频词的覆盖面太窄,过滤效率不理想。随着数据量的增加,过滤的效率得到提升。但是当数据量足够大时,过滤的效率趋于平缓。当数据集选取100万时F值达到了峰值,本文选取这100万含有URL的数据集提取高频词,最终保留了含有5000词的噪音微博高频词词典。
4.3 噪音微博阈值β对判别性能的影响
在噪音微博判别算法中,判断是否为噪音微博的阈值β是一个很重要的参数,它会影响分类器的性能。本文标注了1000篇公共大厅微博作为检测噪音微博分类的数据集,利用上文确定的高频词词典,对该参数进行了多组实验。为了平衡准确率和召回率,以F值作为分类算法的评判标准,同时作为参数选取的标准。实验结果如图7所示,当β取值范围在0.8-1.0时,都取得了较好的分类效果;其中β在取值为0.9时,分类器具有最好的性能,此时F值达到峰值0.90,准确率P为0.84,召回率R为0.97。说明本文的判定方法能够较准确地过滤掉噪音微博,简单实用高效。由于阈值β的大小决定了分类效果,因此,若β取值过小,分类器则会过度拟合为噪音微博,从而导致分类准确率下降;若β取值过大,会导致分类的召回率下降。当β取0.9时,最好地平衡了准确率和召回率。
4.4 阈值γ和双重过滤对相似微博判断算法性能影响
在相似微博判断算法中,阈值γ也是一个很重要的参数,γ的取值将会影响过滤的性能。本文将经过了噪音微博过滤后人工发现的相似微博进行标注,其中含有大于或等于2个的多种相似微博,将标注的600多条相似微博加入不含相似微博的普通微博中,约2000条微博作为检测实验效果的数据集,针对不同参数进行了多组实验,同样以F值的大小作为算法的评判标准和参数选取标准。实验如图8所示,三条曲线分别表示进行双重过滤和仅第一重过滤、仅第二重过滤时F值的对比,其中双重过滤的算法性能明显较高,充分说明了本文提出的双重过滤法的必要性、准确性和实用性。双重过滤在γ等于0.5时F值取得最高值0.72,召回率为0.78,准确率为0.66,说明该算法判断较为准确、性能较高;当γ大于0.5的时候,F值开始出现下降现象。这是因为,随着γ的增加,被归类到相似微博的条件越高,被判为相似的文本越少,因此导致召回率大大下降。
4.5 相似微博双重过滤的时间性能
本文设计双重过滤法主要考虑到微博数据流属于海量数据,如果在整个数据集中进行去重,时间效率较低,难以达到实时应用的目的。因此本文首先对抓取的一个时间段内微博进行一重过滤,然后再对相近时间发表的微博进行二重过滤,达到微博文本流整体上的过滤目的。本文下载了2000条公共大厅微博,仅使用一重过滤处理的时间为90秒,使用二重过滤时处理时间仅为44秒,同时过滤掉了约20%的相似微博。实验说明本文提出的双重过滤法即能保证有效地过滤掉相似微博,同时极大地减少了处理时间,增加了处理效率。
5 结语
本文分析了中文微博数据的特点,针对其中的相似消息和噪音消息提出了一种面向微博客文本流的噪音判别与内容相似性双重检测的过滤方法。本方法实现效率较高,效果理想,实验证明了该方法能有效的对海量中文微博数据进行提纯,高效准确地过滤掉其中的噪音微博和相似微博,较好地保留下了高质量数据。同时该数据也可用于今后对微博数据的进一步分析,包括话题检测、情感倾向性分析等方面。
然而,这些工作尚需进一步深入和完善,主要包括以下几个方面:随着噪音微博的种类特征变化,还需根据新规则新特点进行过滤;在微博相似性计算方面可以选择其他更合理的方法进行比较。
参考文献
[1]Twitter[EB/OL].2011-3-16.http://twitter.com.
[2]Sakaki T,Okazaki M,Matsuo Y.Earthquake shakes Twitter users:real-time event detection by social sensors[C]//Proceedings of the 19th International Conference on World Wide Web,WWW2010,Ra-leigh,North Carolina,USA,April26-30,2010.ACM2010,2010:851-860.
[3]Weng J,Lim E,Jiang J,et al.TwitterRank:finding topic-sensitive influential twitterers[C]//Proceedings of the Third International Con-ference on Web Search and Web Data Mining,WSDM2010,New York,USA,February4-6,2010.ACM2010,2010:261-270.
[4]Tumasjan A,Sprenger T,Sandner P,et al.Predicting elections with Twitter:what140characters reveal about political sentiment[C]//Proceedings of the Fourth International Conference on Weblogs and So-cial Media,ICWSM2010,Washington,DC,USA,May23-26,2010.The AAAI Press2010,2010:178-185.
[5]Goorha S,Ungar L.Discovery of significant emerging trends[C]//Proceedings of the16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Washington,DC,USA,July 25-28,2010.ACM2010,2010:57-64.
[6]Sriram B,Fuhry D,Demirbas M.Short text classification in Twitter to improve information filtering[C]//Proceeding of the33rd Interna-tional ACM SIGIR Conference on Research and Development in Infor-mation Retrieval,SIGIR2010,Geneva,Switzerland,July19-23,2010.ACM2010,2010:841-842.
[7]Kamath K,Caverlee J.Identifying hotspots on the real-time web[C]//Proceedings of the19th ACM Conference on Information and Knowl-edge Management,CIKM2010,Toronto,Ontario,Canada,October 26-30,2010.ACM2010,2010:1837-1840.
[8]黄晓斌.网络信息过滤原理与应用[M].北京:北京大学出版社,2005.
[9]Benevenuto F,Magno G.Detecting spammers on Twitter[EB/OL].http://ceas.cc/2010/papers/Paper%2021.pdf.
[10]曹鹏,李静远.Twitter中近似重复的消息的判定方法研究[J].中文信息学报,2011,25(1):20-27.