基于最邻近标签传播算法的图像型垃圾邮件检测方法

摘要

为了提高图像型垃圾邮件检测的精度和召回率，节省检测图像型垃圾邮件的时间，导致需要一个高效率的检测图像型垃圾邮件的方法。本发明的目的是提供一种利用基于最邻近的标签传播算法检测图像型垃圾邮件的方法。通过提取图片的加速鲁棒性特征描述符，确保了图片的旋转和尺度不变性；通过获取图片聚类中心点信息，再按照该信息均值聚类图片加速鲁棒性特征描述符，确保了所有图片聚类后的信息具有可比性；通过利用基于最邻近的标签传播，选择与每个图像相似度最接近的K（K=已知类别的图像数+测试的图像数/10，表示表示选取与图像相似度最相近的图像幅数）个图像的标签进行传播，提高了标签的传播速率，节省了检测图像型垃圾邮件的时间。

说明书

技术领域

本发明是利用基于最邻近标签传播算法检测图像型垃圾邮件。主要思想是：首先获取图片聚类中心点信息；然后提取所有图片的加速鲁棒性特征描述符信息，进行均值聚类；最后采用基于最邻近的标签传播算法检测图像型垃圾邮件。主要解决了当今的技术对图像型垃圾邮件的检测效率和召回率低等问题，属于数据挖掘和机器学习领域。

背景技术

电子邮件是人们进行网络交流沟通的重要途径，因此随着电子邮件的流行，产生了垃圾邮件，并呈现了快速增长的趋势。虽然带来了巨大的商业、经济及政治利益，但是企业界和个人家庭的用户都花费了数百万美元来对抗垃圾邮件。由于垃圾邮件的增加，ISPs（互联网服务提供商）不得不花费更多的时间和精力处理日益增长的网络流量。因此，如果垃圾邮件继续增长，那么在不久的将来，ISPs可能会难以管理网络流量。

Hrishikesh B.Aradhye等在2005年提出了一种采用基于对象与基于边缘的文本定位方法来挖掘图像中的文本以及颜色特征的思想来对Image Spam（图像型垃圾邮件）进行分类。Giorgio Fumerai等在2006年提出了一种OCR（光学字符识别）技术检测图像型垃圾邮件的文本信息。该技术相对其他过滤系统来说，具有较好的检测效果。

Ngo Phuong Nhung等在2007年提出的通过挖掘图片的边缘特征的方法，使用的分类算法也是SVM（支持向量机）。该方法是通过比较从Email中提取出的图片与样本图片的边缘特征，得到特征向量，然后使用SVM将这些特征向量分别归入Spam与non-Spam类。总的来说使用边缘特征来检测图像Spam能够获取80%的准确率，从不同的图像特征分出Spam类的效率更高并且速度很快。

Battista Biggio等在2007年提出了一种通过计算图像周长复杂度的方法来判别一张图片是否经过了模糊技术的处理。通过文字周长复杂度可以标识断字符或者是噪音对象的出现。由于不能证实经过模糊处理的图像就是携带垃圾信息的图像，这种处理技术只能作为垃圾邮件过滤系统中预处理某个模块。

Eric Medvet等在2008年提出的检测方法结合了文本特征，嵌入的图像特征和全局特征，分别用于计算垃圾图像与合法图像的三方面的特征向量值。特征结合后选取相似度最高的几个特征进行进一步的相似程度计算，提高了检测的效率。然后计算出总的相似程度，若这个值超出了一定的阈值，就说明该邮件为图像型垃圾邮件。

Haiqiang Zuo等在2009年提出了使用一类SVM分类器来对图像型垃圾邮件的局部不变特征进行归类。将异常值检测视为异类分类问题。该算法采用核函数将样本点映射到高维空间以便于分类，采用的核函数是PMK。使用MSER与SURF检测器寻找每张图像的兴趣点，以sift、sc、SURF作为各类特征集合，并使用10交叉法进行可行性验证。该方法主要是针对那些为了逃避基于图像版面相似性的过滤器，而改变图像的总体布局的垃圾邮件。然而，他们并没有改变图像中的某些标记。

总之，以上的所有方法都存在不足之处，要么是不能保证提取图片的特征具有尺度不变性、旋转不变性，要么是不能改变图像一开始就确定的标签。然而，随着技术的发展，图像型垃圾邮件制造者也在不断地增强垃圾邮件逃避检测系统的能力，这就迫切需要一个检测图像型垃圾邮件效率高的系统或方法，从而产生了本文的思想，利用基于最邻近的标签传播算法检测图像型垃圾邮件。

发明内容

技术问题：本发明的目的是提供一种利用基于最邻近的标签传播算法检测图像型垃圾邮件的方法。通过提取图片的加速鲁棒性特征描述符，确保了图片的旋转和尺度不变性；通过获取图片聚类中心点信息，再按照该信息均值聚类图片加速鲁棒性特征描述符，确保了所有图片聚类后的信息具有可比性；通过利用基于最邻近的标签传播，选择与每个图像相似度最接近的一定数量的图像的标签进行传播，提高了标签的传播速率，节省了检测图像型垃圾邮件的时间。

技术方案：本发明利用基于最邻近的标签传播算法检测图像型垃圾邮件所包含的步骤为：

步骤1）训练已知类别数据集，获取聚类中心点信息，其中类别分为正常图片和垃圾图片：

步骤1.1）输入已知类别数据集中的正常图片和垃圾图片；

步骤1.2）提取每幅图片的加速鲁棒性特征描述符信息：

步骤1.2.1）获取输入的图片；

步骤1.2.2）获取输入图片的积分图片；

步骤1.2.3）获取积分图片的像素点；

步骤1.2.4）输入图片的第一个像素点；

步骤1.2.5）判断图片该像素点是否存在，如果存在，转步骤1.2.6），否则，转步骤1.2.14）；

步骤1.2.6）计算该像素点的海森矩阵及行列式值；

步骤1.2.7）判断该点是否是极值点，如果是，转步骤1.2.8），否则，转步骤1.2.13）；

步骤1.2.8）确认该极值点为加速鲁棒性特征点；

步骤1.2.9）获取该特征点在原始图片中的位置、尺度信息；

步骤1.2.10）获取该特征点在原始图片中的主方向；

步骤1.2.11）根据该特征点的位置、尺度、主方向信息，计算该特征点的加速鲁棒性特征描述符；其中，加速鲁棒性特征描述符采用64维描述向量存储；

步骤1.2.12）输入图片下一个像素点，转步骤1.2.5）；

步骤1.2.13）系统自动舍弃该点，转步骤1.2.12）；

步骤1.2.14）输出图片的所有加速鲁棒性特征点描述符信息；

步骤1.3）随机初始化聚类中心点，根据均值聚类算法，同时聚类已知类别数据集中所有图片的加速鲁棒性特征描述符：

步骤1.3.1）获取需要聚类的所有加速鲁棒性特征点描述符信息；

步骤1.3.2）获取聚类中心点的个数；

步骤1.3.3）输入第一个加速鲁棒性特征点信息；

步骤1.3.4）判断该加速鲁棒性特征点是否存在，如果存在，转步骤1.3.5），否则，转步骤1.3.9）；

步骤1.3.5）分别计算该加速鲁棒性特征点到所有聚类中心点的距离；

步骤1.3.6）选择最短距离，获取与最短距离相应的聚类中心信息；

步骤1.3.7）将该加速鲁棒性特征点聚类到该聚类中心中；

步骤1.3.8）输入下一个加速鲁棒性特征点，转步骤1.3.5）；

步骤1.3.9）总结每个聚类中心中的加速鲁棒性特征点描述符信息；

步骤1.3.10）更新所有聚类中心点信息：将每个聚类中心中的加速鲁棒性特征点描述符信息求和再取平均；

步骤1.3.11）输出聚类后的所有的加速鲁棒性特征描述符信息；

步骤1.4）输出所有的聚类中心点信息，即聚类后的所有的加速鲁棒性特征描述符信息；

步骤2）训练已知类别数据集和测试数据集，获取每幅图片均值聚类后的加速鲁棒性特征描述符信息：

步骤2.1）输入已知类别数据集中的正常图片和垃圾图片、测试数据集中的测试图片；

步骤2.2）标签图片：若输入的图片属于正常图片数据集，则标签为0，若输入的图片属于垃圾图片数据集，则标签为1，若输入的图片属于测试图片数据集，则默认为垃圾图片，标签为1；

步骤2.3）提取每幅图片的加速鲁棒性特征描述符信息，具体提取方法采用步骤1.2）中的步骤1.2.1）至步骤1.2.14）；

步骤2.4）获取聚类中心点信息，具体获取方法采用步骤1）中的步骤1.1）至步骤1.4）；

步骤2.5）根据聚类中心点信息，使用均值聚类算法，聚类每幅图片的加速鲁棒性特征描述符，具体聚类方法采用步骤1.3.1）至步骤1.3.11）；

步骤2.6）输出每幅图片均值聚类后的加速鲁棒性特征描述符信息；

步骤3）基于最邻近的标签传播算法分类图片：

步骤3.1）获取所有图片聚类后的加速鲁棒性特征描述符信息；其中，所有图片包括已知类别数据集中的图片和测试数据集中的图片；

步骤3.2）初始化已知类别数据集标签矩阵；

步骤3.3）初始化标签概率分布矩阵；

步骤3.4）根据图片的加速鲁棒性特征描述符，计算图片之间的相似度；

步骤3.5）根据相似度矩阵，计算图片之间的相似度排列矩阵；

步骤3.6）根据相似度排列矩阵，计算图片之间的相似度K排列矩阵，其中，K=已知类别的图像数+测试的图像数/10，表示表示选取与图像相似度最相近的图像幅数；

步骤3.7）根据相似度矩阵，计算图片之间的传播概率矩阵；

步骤3.8）将每张图片视为一个节点，生成带权完全连接图；

步骤3.9）根据每个节点的标签，进行标签传播：

步骤3.9.1）根据相似度排列矩阵，确定每个节点最邻近的节点个数；

步骤3.9.2）生成最邻近图；

步骤3.9.3）更新标签概率分布矩阵；

步骤3.9.4）限制已知类别数据，再次更新标签概率分布矩阵；

步骤3.9.5）判断标签概率分布矩阵是否收敛，如果收敛，转步骤3.9.6），否则，转步骤3.9.3）；

步骤3.9.6）根据标签概率分布矩阵，输出测试图片的标签；

步骤4）根据测试图片的标签，将测试图片进行正常图片与垃圾图片分类。

有益效果：本发明对比已有技术具有以下创新点：

提出了基于最邻近的标签传播算法检测图像型垃圾邮件的方法，根据与每个图像相似度最接近的一定数量的图像的标签，进行标签传播，确定标签概率分布，直到传播过程达到稳定，依据图像标签，检测出图像型垃圾邮件。

本发明对比已有技术具有以下显著优点：

1）提取图片加速鲁棒性特征，具有尺度和旋转不变性；

2）根据与每个图像相似度最接近的K个图像与标签概率分布，使用标签传播算法，传播并更新图像的标签，检测出垃圾图像。其中，K=已知类别的图像数+测试的图像数/10。

总之，提高了标签的传播速率，提高了图像型垃圾邮件检测的精度、准确率和召回率，节省了检测图像型垃圾邮件的时间。

附图说明

图1利用基于最邻近的标签传播算法分类器检测图像的整体流程图；

图2获取聚类中心点信息的流程图；

图3提取加速鲁棒性特征描述符的流程图；

图4均值聚类加速鲁棒性特征描述符的流程图；

图5基于最邻近的标签传播算法分类器的分类图片流程图。

具体实施方式

本发明是利用基于最邻近的标签传播算法检测图像型垃圾邮件。具体的实施方式如下：

步骤1）训练已知类别数据集，提取该数据集中所有图片的加速鲁棒性特征描述符信息，同时进行均值聚类，获取图片聚类中心点信息，具体过程如图2所示，其中类别分为正常图片和垃圾图片：

步骤1.1）获取已知类别数据集中的所有图片，包括正常图片和垃圾图片；

步骤1.2）提取步骤1.1）获取的所有图片的加速鲁棒性特征描述符信息，具体过程如图3所示：

步骤1.2.1）根据输入的图片，获取该图片的积分图片，再获取该积分图片的所有像素点，计算每个像素点的海森矩阵及行列式值；接着判断这些点是否为极值点，如果某点是极值点，那么确定该点为加速鲁棒性特征点，如果某点不是极值点，那么就舍弃该点；

步骤1.2.3）获取加速鲁棒性特征点在原图中的位置、尺度信息，以及主方向信息，根据这些信息，计算加速鲁棒性特征点的特征描述符；其中，加速鲁棒性特征描述符采用64维描述向量存储；

步骤1.3）根据聚类中心点的个数m，随机初始化m个聚类中心点，根据均值聚类算法，同时聚类已知类别数据集中所有图片的加速鲁棒性特征描述符，具体过程如图4所示：

步骤1.3.1）获取步骤1.2）中提取的已知类别数据集中所有图片的所有加速鲁棒性特征点描述符信息，分别计算这些加速鲁棒性特征点到m个聚类中心的距离；接着选择最短的距离，获取与该最短距离相应的聚类中心点的信息，将相应的加速鲁棒性特征点聚类到该聚类中心中；

步骤1.3.2）总结每个聚类中心中的加速鲁棒性特征点描述符信息，并更新m个聚类中心点信息，即重新计算m个聚类中心点信息：将每个聚类中心中的加速鲁棒性特征点描述符信息求和再取平均，得到聚类后的m个加速鲁棒性特征描述符信息；

步骤1.4）获取m个聚类中心点信息，即聚类后的m个加速鲁棒性特征描述符信息；

步骤2）训练已知类别数据集和测试数据集，针对这两个数据集中的图片，预先将已知类别数据集中的图片按类别标签，将测试数据集中的图片初始化为垃圾类别标签，提取出旋转和尺度不变的加速鲁棒性特征描述符，再根据聚类中心点信息，使用均值聚类法，统一化所有图像的特征描述符个数，即获取每幅图片均值聚类后的加速鲁棒性特征描述符信息，具体过程如图1所示：

步骤2.1）获取已知类别数据集中的正常图片和垃圾图片、测试数据集中的测试图片；

步骤2.2）标签步骤2.1）中获取的所有图片：若图片属于正常图片数据集，则标签为0，若图片属于垃圾图片数据集，则标签为1，若图片属于测试图片数据集，则默认为垃圾图片，标签为1；

步骤2.3）提取步骤2.1）中获取的所有图片的加速鲁棒性特征描述符信息，具体提取方法见步骤1.2）中的步骤1.2.1）至步骤1.2.3），具体过程如图3所示；

步骤2.4）获取聚类中心点信息，具体获取方法见步骤1）中的步骤1.1）至步骤1.4），具体过程如图2所示；

步骤2.5）根据步骤2.4）中获取的聚类中心点信息，使用均值聚类算法，聚类每幅图片的加速鲁棒性特征描述符，具体聚类方法见步骤1.3.1）至步骤1.3.2），具体过程如图4所示；

步骤2.6）获取每幅图片均值聚类后的加速鲁棒性特征描述符信息；其中，每幅图片聚类为m个64维加速鲁棒性特征描述符，存储在矩阵F_nM中，其中，n：表示已知类别数据集和测试数据集中的所有图片数；M=64×m，m：表示聚类中心点的个数；

步骤3）计算每幅图像之间的相似度，存储于相似度数组中；从而计算每幅图像之间的相似度排列矩阵、传播概率矩阵；接着，将每幅图像视为一个节点后，构造出图像的最邻近图；最后，在该图上进行标签传播，直到标签矩阵概率分布达到收敛，根据标签矩阵概率分布分类测试数据集中的图片，具体过程如图5所示：

步骤3.1）获取步骤2）中提取的所有图片聚类后的加速鲁棒性特征描述符信息F_nM；

步骤3.2）初始化已知类别数据集标签矩阵Y_lc：

其中，Y_ij表示类别数据集标签矩阵Y_lc的第i行第j列的元素值；l表示已知类别数据集中的图片数；c=2，表示分类的类别数，共两类，分为正常图片类别（j=0）和垃圾图片类别（j=1）；

步骤3.3）初始化标签概率分布矩阵LP_nc：

$>{\mathrm{lp}}_{\mathrm{ij}}=\left(\begin{array}{ccc}{y}_{\mathrm{ij}}& 0\le i<l& \\ 0& 1\le i<n,j=0,& 0\le i<n,0\le j<c\\ 1& 1\le i<n,j=1& \end{array}\right)---\left(2\right)$>

其中，lp_ij表示标签概率分布矩阵LP_nc的第i行第j列的元素值；n表示已知类别数据集和测试数据集中的所有图片数；c=2，表示分类的类别数，共两类，分为正常图片类别（j=0）和垃圾图片类别（j=1）；y_ij表示已知类别数据集标签，计算过程见公式（1）；

步骤3.4）根据图片的加速鲁棒性特征描述符，计算图片之间的相似度W_nn：

$>w_{\mathrm{ij}}=\left(\begin{array}{cc}1& i=j\\ \frac{1}{\sqrt{{\Sigma }_{h=1}^{64\times m}{(f_{\mathrm{ih}}-f_{\mathrm{jh}})}^2}}& i\ne j,0\le i<n,0\le j<n\end{array}\right)---\left(3\right)$>

其中，w_ij表示相似度矩阵W_nn的第i行第j列的元素值；n表示已知类别数据集和测试数据集中的所有图片数；f_ih表示第i张图片的第h个加速鲁棒性特征描述符信息，具体提取过程采用步骤2）的步骤2.1）至步骤2.6）；

步骤3.5）根据相似度矩阵W_nn，计算图片之间的相似度排列矩阵：

其中，表示相似度排列矩阵的第i行第j列的元素值；n表示已知类别数据集和测试数据集中的所有图片数；W_nn是相似度矩阵，w_ij表示第i幅图片与第j幅图片之间的相似度，计算过程见公式（3）；

步骤3.6）根据相似度排列矩阵，计算图片之间的相似度K排列矩阵P_nn：

$>p_{\mathrm{ij}}=\left(\begin{array}{cc}0& p_{\mathrm{ij}}^{\prime }\ne 1\left|2\right|...|K\\ 1& p_{\mathrm{ij}}^{\prime }=1\left|2\right|...|K\end{array}\right),0\le i<n,0\le j<n---\left(5\right)$>

其中，P_ij表示相似度K排列矩阵P_nn的第i行第j列的元素值；n表示已知类别数据集和测试数据集中的所有图片数；表示第i幅图片与第j幅图片之间的相似度的排列位置，计算过程见公式（4）；K=已知类别的图像数+测试的图像数/10，表示表示选取与图像相似度最相近的图像幅数，表示标签传播算法中的K值，也表示选取与图像相似度最相近的K幅图像；

步骤3.7）根据相似度矩阵W_nn，计算图片之间的传播概率矩阵T_nn：

$>t_{\mathrm{ij}}=\frac{w_{\mathrm{ij}}}{{\Sigma }_{h=1}^n{w}_{\mathrm{ih}}},0\le i<n,0\le j<n---\left(6\right)$>

其中，，t_ij表示传播概率矩阵T_nn的第i行第j列的元素值；n表示已知类别数据集和测试数据集中的所有图片数；w_ij表示第i幅图片与第j幅图片之间的相似度，计算过程见公式（3）；

步骤3.8）将每张图片视为一个节点，生成带权完全连接图，其中节点i和节点j之间的权值为步骤3.4）中的相似度矩阵w_ij；

步骤3.9）根据每个节点的标签，进行标签传播：

步骤3.9.1）根据步骤3.5）中的相似度排列矩阵P_nn，确定每个节点最邻近的节点个数，生成最邻近图；

步骤3.9.2）；更新标签概率分布矩阵LP_nc：

$>{\mathrm{lp}}_{\mathrm{ij}}=\underset{h=1}{\overset{n}{\Sigma }}{t}_{\mathrm{ih}}{p}_{\mathrm{ih}}{\mathrm{lp}}_{\mathrm{hj}},0\le i<n,0\le j<c---\left(7\right)$>

其中，lp_ij表示标签概率分布矩阵LP_nc的第i行第j列的元素值；n表示已知类别数据集和测试数据集中的所有图片数；c＝2，表示分类的类别数；t_ij表示第i幅图片与第j幅图片之间的传播概率，计算过程见公式（6）；p_ij表示第i幅图片与第j幅图片之间的相似度的排列位置是否属于前K个，计算过程见公式（5），K=已知类别的图像数+测试的图像数/10，表示表示选取与图像相似度最相近的图像幅数；

步骤3.9.3）限制已知类别数据，再次更新标签概率分布矩阵LP_nc：

$>{\mathrm{lp}}_{\mathrm{ij}}=\left(\begin{array}{cc}{y}_{\mathrm{ij}}& 0\le i<l\\ {\mathrm{lp}}_{\mathrm{ij}}& l\le i<n\end{array}\right),0\le i<n,0\le j<c---\left(8\right)$>

其中，，lp_ij表示标签概率分布矩阵LP_nc的第i行第j列的元素值；n表示已知类别数据集和测试数据集中的所有图片数；c＝2，表示分类的类别数；y_ij表示第i幅图片是否属于类别j，计算过程见公式（1）；

步骤3.9.4）判断标签概率分布矩阵LP_nc是否收敛，如果收敛，结束计算，转步骤3.9.5），否则，转步骤3.9.2）；

步骤3.9.5）根据标签概率分布矩阵LP_nc，输出测试数据集中所有测试图片的标签；

步骤4）根据测试图片的标签，将测试图片进行正常图片与垃圾图片分类，从而达到了检测图像型垃圾邮件的目的。