CN104375982A - 一种确定文本视觉相似度的方法 - Google Patents

Abstract

本发明涉及一种确定文本视觉相似度的方法，实现步骤如下：(1)计算两个字符串直接的视觉距离；(2)计算两个字符串直接相似度；(3)将以前发邮件记录中的邮件记录最大值与当前电子邮件的最大值作为分类器的特征，来检测特定字符串即电子邮件地址的相似度；(4)将利用随机森林分类器对误发送邮件进行分类训练和检测，以用于检测误发邮件。本发明达到了比传统的检测技术更高的准确率和召回率。

Description

一种确定文本视觉相似度的方法

技术领域

本发明涉及一种确定文本视觉相似度的方法，属于互联网技术领域。 

背景技术

随着互联网的蓬勃发展，互联网中承载着各式各样的海量信息，并且规模在快速增长。这其中包含着大量视觉相似度非常高的文本。文本视觉相似度是指对两个给定文本，从人的视觉感官角度衡量两个文本的相似度。对一个合法或正常的文本A来说，如果某个文本B与其具有非常高的视觉相似度，那么就非常可能引起人的视觉错误，从而错把文本B当作文本A使用。这样就会给使用者带来不必要的风险和麻烦。例如，如果文本A是一个银行网站的URL，不法分子可能伪造该银行网站，在其中挂载恶意木马等攻击脚本，并使用一个看上去与文本A非常相似的文本B作为伪造站点的URL。一旦用户被迷惑，错误地把文本B当作文本A点击，那么就会发生用户帐号窃取甚至是资金被套走，导致一系列恶劣的经济后果。如果用户被两个非常相似的邮件地址迷惑，错把收件人人的地址写错，就会发生邮件误发事件。如果误发邮件中包含个人信息、财务数据甚至涉密信息等敏感数据，就会导致严重的社会和经济问题。现在的邮件客户端基本上都具有邮件地址自动补齐功能，即用户输入收件人邮箱地址的若干个字符，客户端会根据用户的发送邮件历史，向用户推荐一些邮箱地址供用户选择，这些邮箱地址以用户输入的字符为前缀。自动补齐功能使用户可以不输入完整的收件人邮件地址，带来了一些便利，但引入的一个问题是由于人们误选择备选项而导致邮件误发的情况更容易发生。因此，需要一种确定文本视觉相似度的方法，以期避免由于人的视觉疏忽导致误发邮件事件的发生。 

目前传统的确定字符串相似度的方法是Levenshtein相似度计算方法，也就是字符串之间的编辑距离，在字符串直接不同位置的字符被赋予相同的权重。这种方式无法合理的准确的反映和理解用户阅读和书写特定字符串(例如email地址、URL)的习惯。针对两个字符串，根据人们实际阅读的习惯，对字符串的不同位置赋予不同的权重，以防止人们误读而造成列斯URL钓鱼攻击或者由于用户的写错收件人地址而造成发错收件人，从而造成个人隐私，甚至是国家机密的泄漏。 

所以迫切需要一种新型的字符串相似度确定方法，以弥补上述不足。 

发明内容

本发明的技术解决问题：克服现有技术的不足，提供一种确定特定文本视觉相似度的方法,一种特定字符串(通常以电子邮件为例)文本相似度的方法，达到了比传统的检测技术更高的准确率和召回率。 

本发明技术解决方案：一种确定文本视觉相似度的方法，实现步骤如下： 

(1)计算两个字符串直接的视觉距离，计算公式如下： 

$\mathrm{VD}({\mathrm{\α}}_{[t+1,l\left(a\right)]},{\mathrm{\β}}_{[t+1,l\left(\mathrm{\β}\right)]})=\mathrm{\θ}\×\min (x,y,z)+\left\{\begin{array}{ccc}0& \mathrm{if}& {\mathrm{\α}}_{l\left(a\right)}={\mathrm{\β}}_{l\left(\mathrm{\β}\right)}\\ 1& \mathrm{if}& {\mathrm{\α\β}}_{l\left(a\right)}\≠{\mathrm{\β}}_{l\left(\mathrm{\β}\right)}\end{array}\right.$

其中 $\left\{\begin{array}{c}x=\mathrm{VD}({\mathrm{\α}}_{[t+1,l\left(\mathrm{\α}\right)-1]},{\mathrm{\β}}_{[t+1,l\left(\mathrm{\β}\right)]})\\ y=\mathrm{VD}({\mathrm{\α}}_{[t+1,l\left(\mathrm{\α}\right)]},{\mathrm{\β}}_{[t+1,l\left(\mathrm{\β}\right)]})\\ z=\mathrm{VD}({\mathrm{\α}}_{[t+1,l\left(\mathrm{\α}\right)-1]},{\mathrm{\β}}_{[t+1,l\left(\mathrm{\β}\right)-1]})\end{array}\right.$

计算两个字符串之间可能的视觉距离最大值： 

$\begin{array}{c}\mathrm{MVD}({\mathrm{\α}}_{[t+1,l\left(\mathrm{\α}\right)]},{\mathrm{\β}}_{[t+1,l\left(\mathrm{\β}\right)]})=\underset{k=0}{\overset{\max (l\left(\mathrm{\α}\right),l\left(\mathrm{\β}\right)-t-1)}{\mathrm{\Σ}}}{\mathrm{\θ}}^k\\ =\frac{{1-\mathrm{\θ}}^{\max (l\left(\mathrm{\α}\right),l\left(\mathrm{\β}\right)-t)}}{1-\mathrm{\θ}}\end{array}$

其中α、β表示两个字符串，l(·)表示字符串的长度，θ表示每个相邻字符之间的权重因子的比值。 

(2)根据步骤(1)中的两个字符串直接的视觉距离计算两个字符串直接相似度，计算公式如下： 

$\mathrm{VS}(A,B)=\left\{\begin{array}{cc}0& {\mathrm{if\α}}_{[1,t]}\≠{\mathrm{\β}}_{[1,t]}\\ 1-\frac{\mathrm{VD}({\mathrm{\α}}_{(t+1,l\left(a\right))},{\mathrm{\β}}_{(t+1),l\left(\mathrm{\β}\right)})}{\mathrm{MVD}({\mathrm{\α}}_{(t+1,l\left(a\right))},{\mathrm{\β}}_{(t+1),l\left(\mathrm{\β}\right)})}& \mathrm{otherwise}\end{array}\right.$

VD表示上文中计算出来的字符串之间的视觉距离，其中VD表示计算出的视觉相似度的，MVD表示上面提到的字符串α、β之间理论上视觉相似度的最大值。 

(3)将该邮件的收件人地址与用户历史发件记录的联系人列表的邮件地址计算得到的视觉相似度作为分类器中的VESA(Visual Similarity between Email Addresses)特征，来检测特定字符串如形式类似于电子邮件地址的视觉相似度； 

(4)每一封邮件计算得到对应的VESA特征，将VESA特征作为分类器的一个特征，利用随机森林分类器对安然数据集中所有发送邮件进行分类训练和测试，以用于检测误发邮件。 

(5)将每一封邮件的发件人的邮件地址与该发件人以前发邮件记录中的邮件记录最大值与当前电子邮件的最大值作为分类器的特征，来检测特定字符串即电子邮件地址的相似度； 

所述步骤(4)中采用安然数据集进行性能训练和测试时，将安然数据集分成三份，第一份统计所有邮件用户的发件人列表，第二份用作训练集，以用户生成随机森林分类器、第三份用作测试集，以用于测试分类器的性能；对训练集中每一封邮件，计算该发件人与其历史收件人所有的字符串视觉相似度，取其中的最大值作为该封邮件的VESA特征；然后再针对测试集中的每一封邮件，利用随机森林进行分类，得到邮件是否误发的分类结果。 

本发明与现有技术相比的优点在于：本发明充分考虑了人阅读URL或Email时时优先关注字符串前缀，而很容易忽略掉后缀的习惯，与传统的计算字符串文本的相似度相比，更精确的衡量了两个字符串的易混淆程度。 

附图说明

图1为本发明方法的实现流程图； 

图2为实验效果对比图。 

具体实施方式

如图1所示，本发明提出的一种确定文本视觉相似度的方法具体如下。 

定义：对文本A＝α₁…α_l(α)(简写为α_[1，l(α)])和B＝β[_1，(β)]，l(·)表示文本的长度，二者的视觉相似度定义为： 

$\mathrm{VS}(A,B)=\left\{\begin{array}{cc}0& {\mathrm{if\α}}_{[1,t]}\≠{\mathrm{\β}}_{[1,t]}\\ 1-\frac{\mathrm{VD}({\mathrm{\α}}_{(t+1,l\left(a\right))},{\mathrm{\β}}_{(t+1),l\left(\mathrm{\β}\right)})}{\mathrm{MVD}({\mathrm{\α}}_{(t+1,l\left(a\right))},{\mathrm{\β}}_{(t+1),l\left(\mathrm{\β}\right)})}& \mathrm{otherwise}\end{array}\right.$

视觉相似度的取值范围是[0，1]。如果两个文本的前t个字符不相同，则认为两个文本的视觉相似度为0，以邮件客户端为例，用户会在地址框中输入地址的前几个字母，然后从提示的备选项中选择回车敲入。由前面所述，这一个过程有可能由于用户的粗心而导致选择了错误的收件人进而导致错发邮件。 

VD函数给出的是两个文本的视觉距离，其计算公式如下： 

$\mathrm{VD}({\mathrm{\α}}_{[t+1,l\left(a\right)]},{\mathrm{\β}}_{[t+1,l\left(\mathrm{\β}\right)]})=\mathrm{\θ}\×\min (x,y,z)+\left\{\begin{array}{ccc}0& \mathrm{if}& {\mathrm{\α}}_{l\left(a\right)}={\mathrm{\β}}_{l\left(\mathrm{\β}\right)}\\ 1& \mathrm{if}& {\mathrm{\α\β}}_{l\left(a\right)}\≠{\mathrm{\β}}_{l\left(\mathrm{\β}\right)}\end{array}\right.$

其中， 

$\left\{\begin{array}{c}x=\mathrm{VD}({\mathrm{\α}}_{[t+1,l\left(\mathrm{\α}\right)-1]},{\mathrm{\β}}_{[t+1,l\left(\mathrm{\β}\right)]})\\ y=\mathrm{VD}({\mathrm{\α}}_{[t+1,l\left(\mathrm{\α}\right)]},{\mathrm{\β}}_{[t+1,l\left(\mathrm{\β}\right)]})\\ z=\mathrm{VD}({\mathrm{\α}}_{[t+1,l\left(\mathrm{\α}\right)-1]},{\mathrm{\β}}_{[t+1,l\left(\mathrm{\β}\right)-1]})\end{array}\right.$

θ代表两个相邻字符之间的权重差别，其取值范围为[0，1]。值越小表示后面的字符权重越高。当θ等于1时，视觉距离即为Levenshtein距离。 

Levenshtein距离，也称为编辑距离，是指对两个给定文本，把一个转变为另一个所需的最少编辑操作次数。编辑操作是指插入字符操作、删除字符操作、替换字符操作。如果两个文本的Levenshtein距离越大，则两个文本的差异性越大，他们的相似度越低。 

例如，将kitten转成sitting至少需要如下三步操作： 

1、替换操作：sitten    (k→s) 

2、替换操作：sittin    (e→i) 

3、插入操作：sitting    (→g) 

因此，文本kitten和文本sitting的Levenshtein距离为3。 

Levenshtein距离赋予不同位置的编辑操作相同的权重。例如，Levenshtein距离认为在首字符的替换操作和在中间字符的替换操作是一样的。即认为levenshtein和nevenshtein的编辑距离是1，levenshtein和levemshtein的编辑距离都是1，他们的相似度都相同，但显然后两个文本更容易被相互认错。这是因为人在短时间内判定两个文本是否相同时，不会逐字符地进行比较，而是更关注特殊位置的字符是否相同，例如开始的若干字符、结尾的若干个字符、特殊字符附近的若干字符。很多钓鱼URL就是利用人的这种判定心理构造的。 

MVD函数给出的是两个文本的视觉距离的最大值。根据VD函数的计算公式，可以得到： 

$\begin{array}{c}\mathrm{MVD}({\mathrm{\α}}_{[t+1,l\left(\mathrm{\α}\right)]},{\mathrm{\β}}_{[t+1,l\left(\mathrm{\β}\right)]})=\underset{k=0}{\overset{\max (l\left(\mathrm{\α}\right),l\left(\mathrm{\β}\right)-t-1)}{\mathrm{\Σ}}}{\mathrm{\θ}}^k\\ =\frac{{1-\mathrm{\θ}}^{\max (l\left(\mathrm{\α}\right),l\left(\mathrm{\β}\right)-t)}}{1-\mathrm{\θ}}\end{array}$

当θ＝1即相邻字符之间的权重因子的比值为1时，令MVD(α_{[t+1，l(α)]}，β_{[t+1，l(β)]})＝max(l(α)，l(β))-t，θ＝1下，两个字符串视觉距离的最大值； 

以邮件误发检测实验来评价本发明的方法。给定一则消息M，消息内容为c，消息的 发送者为s，消息的接收者共有n个：R＝{r₁，r₂，…，r_n}。那么消息M实际上包含了n封邮件：M＝{E₁，E₂，…，E_n}，其中E_i是个三元组：E_i＝(s，r_i，c)。邮件误发检测实际上是一个二元分类问题，即判定每封邮件E_i是否为误发。对邮件E_i，可以以发件人s的历史收件人列表中与当前收件人r_i的视觉相似度的作为一个重要特征，记为VSEA(Visual Similarity of Email Address)，则： 

$\mathrm{VSEA}\left(E_i\right)=\underset{u\∈\mathrm{EAB}\left(s\right)}{\max }\mathrm{VS}(r_i,u)$

其中，EAB代表该某邮件地址所有发送过邮件的接收地址集合，其中VS为前面所述的两个邮件地址字符串之间的视觉相似度，此公式表示该封邮件的发件人对应的历史收件人的地址中视觉相似度的最大值。 

在邮件误发检测中所用的其余20个特征如下表所示。 

表1 

以VSEA作为第21个特征。实验用的数据集是安然公司邮件记录数据集。该数据集为安然公司的工作人员真实的大规模的邮件信息。该数据集由美国联邦能源管理委员会公布以作公开研究用途。实验采用了十折交叉验证得到最终检测结果，使用的安然数据集中从2010年1月份到2010年10月份的邮件记录。实验结果如图2所示。 

误发邮件的数据集采用人工生成的方法。数据集中误发邮件包括两个子集：1、随机生成的收件人地址。2、超过一定时间再也没有邮件联系的收件人地址。图2显示了使用不同特征对邮件误发检测结果的影响。由图可见，只采取前10个特征的分类器的召回率和准确率只有不到10％，使用前20个特征，召回率和准确率可以达到80％以上。在添加了VESA特征后，邮件误发检测的准确率和召回率可以进一步地提高了2％-5％。其中图2中的β表示所有误发邮件集合中发件人与收件人从未有过联系记录的邮件占所有误发邮件的百分比。 

实施例子 

首先以两个邮箱地址α＝“chenxiaojuniie.ac.cn”和β＝“chengxiuyuniie.ac.cn”为例， 

利用文本视觉相似度计算两个字符串的相似性： 

这里设置参数t＝3，θ＝1/2： 

$\begin{array}{c}\mathrm{VS}(\mathrm{\α},\mathrm{\β})=1-\frac{\mathrm{VD}(\′\′\mathrm{nxiaojun}\′\′,\′\′\mathrm{ngxiuyun}\′\′)}{\mathrm{MVD}(\′\′\mathrm{nxiaojun}\′\′,\′\′\mathrm{ngxiuyun}\′\′)}\\ =1-\frac{1/512+1/64+1/32+1/16+1/4}{{1-(1/2)}^8}\\ \≈0.82\end{array}$

VD为字符串之间的视觉相似度，MVD是两个字符串假定直接所有字符都不相同的情况的取值。 

由此可见，基于文本视觉相似度能得到更加精细的度量结果。 

而利用Levenshtein计算两个字符串的距离为3，这里将Levenshtein距离的倒数，作为 字符串的相似度为0.33，显然，基于本发明提出确定文本视觉相似度方法更能反映刻画人们阅读字符串习惯的本质。 

提供以上实施例仅仅是为了描述本发明的目的，而并非要限制本发明的范围。本发明的范围由所附权利要求限定。不脱离本发明的精神和原理而做出的各种等同替换和修改，均应涵盖在本发明的范围之内。 

Claims (2)

1.一种确定文本视觉相似度的方法，其特征在于实现步骤如下：

(1)计算两个字符串直接的视觉距离，计算公式如下：

$\mathrm{VD}\left({\mathrm{\α}}_{[t+1,l\left(a\right)],}{\mathrm{\β}}_{[t+1,l\left(\mathrm{\β}\right)]}\right)=\mathrm{\θ}\×\min (x,y,z)+\left\{\begin{array}{ccc}0& \mathrm{if}& {\mathrm{\α}}_{1\left(a\right)}={\mathrm{\β}}_{l\left(\mathrm{\β}\right)}\\ 1& \mathrm{if}& {\mathrm{\α}}_{1\left(a\right)}\≠{\mathrm{\β}}_{l\left(\mathrm{\β}\right)}\end{array}\right.$

其中 $\left\{\begin{array}{c}x=\mathrm{VD}({\mathrm{\α}}_{[t+1,l\left(\mathrm{\α}\right)-1]},{\mathrm{\β}}_{[t+1,l\left(\mathrm{\β}\right)]})\\ y=\mathrm{VD}({\mathrm{\α}}_{[t+1,l\left(\mathrm{\α}\right)]},{\mathrm{\β}}_{[t+1,l\left(\mathrm{\β}\right)]})\\ z=\mathrm{VD}({\mathrm{\α}}_{[t+1,l\left(\mathrm{\α}\right)-1]},{\mathrm{\β}}_{[t+1,l\left(\mathrm{\β}\right)-1})\end{array}\right.$

计算两个字符串之间可能的视觉距离最大值：

$\begin{array}{c}\mathrm{MVD}({\mathrm{\α}}_{[t+1,l\left(\mathrm{\α}\right)]},{\mathrm{\β}}_{[t+1,l\left(\mathrm{\β}\right)]})=\underset{k=0}{\overset{\max (l\left(\mathrm{\α}\right),l\left(\mathrm{\β}\right)-t-1)}{\mathrm{\Σ}}}{\mathrm{\θ}}^k\\ =\frac{1-{\mathrm{\θ}}^{\max (l\left(\mathrm{\α}\right),l\left(\mathrm{\β}\right)-t)}}{1-\mathrm{\θ}}\end{array}$

其中α、β表示两个字符串，l(·)表示字符串的长度，θ表示每个相邻字符之间的权重因子的比值；

(2)根据步骤(1)中的两个字符串直接的视觉距离计算两个字符串视觉相似度，计算公式如下：

$\mathrm{VS}(A,B)=\left\{\begin{array}{cc}0& \mathrm{if}{\mathrm{\α}}_{[1,t]}\≠{\mathrm{\β}}_{[1,t]}\\ 1-\frac{\mathrm{VD}({\mathrm{\α}}_{(t+1,l\left(a\right))},{\mathrm{\β}}_{(t+1),l\left(\mathrm{\β}\right)})}{\mathrm{MVD}({\mathrm{\α}}_{(t+1,l\left(a\right))},{\mathrm{\β}}_{(t+1),l\left(\mathrm{\β}\right)})}& \mathrm{otherwise}\end{array}\right.$

VD表示上文中计算出来的邮件地址字符串之间的视觉距离，MVD表示字符串α、β之间理论上视觉相似度的最大值；

(3)将该邮件的收件人地址与用户历史发件记录的联系人列表的邮件地址计算得到的视觉相似度作为分类器中的VESA，Visual Similarity between Email Addresses)特征，来检测特定字符串如形式类似于电子邮件地址的视觉相似度；

(4)每一封邮件计算得到对应的VESA特征，将VESA特征作为分类器的一个特征，利用随机森林分类器对安然数据集中所有发送邮件进行分类训练和测试，以用于检测误发邮件。

2.根据权利要求1所述的确定文本视觉相似度的方法，其特征在于：所述步骤(4)中采用安然数据集进行性能训练和测试时，将安然数据集分成三份，第一份统计所有邮件用户的发件人列表，第二份用作训练集，以用户生成随机森林分类器、第三份用作测试集，以用于测试分类器的性能；对训练集中每一封邮件，计算该发件人与其历史收件人所有的字符串视觉相似度，取其中的最大值作为该封邮件的VESA特征；然后再针对测试集中的每一封邮件，利用随机森林进行分类，得到邮件是否误发的分类结果。