网页分类
更新时间：2023-09-15 07:41:01 阅读量： 资格考试认证 文档下载
摘 要
随着互联网的高速发展，web上的信息越来越丰富，为了让人们更快捷轻松的找到需要的信息，网页分类的方法越来越多的得到应用。本文描述的分类方法采用基于支持向量机（Support Vector Machine）的分类方法。 本文首先介绍了网页分类的整体框架，包括特征提取、训练数据的整合、模型训练以及基于模型文件对网页进行分类。特征提取是网页分类的基础，它主要是通过对页面进行解析，得到页面的节点信息，以结构+属性的形式来描述页面特征，其中结构代表页面中特定元素的集合，属性代表结构具备的一些基本信息。根据结构和属性的配置，我们对每个页面可以提取到若干特征。 SVM是一种有监督的学习方法，它的任务是通过对训练数据的学习得到分类超平面，然后以此对随机数据进行二分类，所以首先我们需要构建一批训练数据。特征提取为我们提供了这样的帮助，通过对一批页面进行特征提取，以及一些相关的数据处理如规范化、离散化、信息统计、过滤等操作，我们得到一批可以用来进行SVM训练的数据，并且通过SVM模型训练得到模型文件。在对随即页面进行分类时，首先进行特征提取的工作，然后根据模型文件及特征提取结果进行相关计算，进而判断页面是否为某一类型。 对不同类型以及不同语言的分类步骤大致相同，我主要进行了两种类型的网页分类工作，最后得到的类型A准确率和召回率分别为92.3%和86.7%，类型B的准确率和召回率分别为82.0%和84.5%，基本符合预期。
关键词 SVM，特征提取，网页分类，二分类
I
ABSTRACT
With the rapid pace of Internet’s development, web becomes informative. The methods of web page classification are widely applied to make it more convenient for individuals to find the needed information. The methods of classification adopt the methods of classification based on Support Vector Machine.
This paper initially introduces the whole structure of web page classification, including feature extraction, training data integration, model training and the classification based on the model file. Feature selection that obtains the inode of html page by analyzing the pages is the basis of web page classification. It describes the feature of page in the form of structure and attribution, where the structure refers to the specific elements sets and the attribution stands for some basic information of the structure. According to structure and attributive configuration, we can select several features in each page.
SVM is supervised learning method whose task is to obtain classification hyperplane by learning the training data, thus, 2-class the random data. Due to that, we initially need structure a chain of training data. Feature selection offers help by conducting feature selection in pages and by dealing with some relevant data, such as normalization, discretization, information statistics and filter. We gain several data for SVM training, and from that we gain the model file. For classifying the random pages, we are expected to conduct feature selection firstly. Then according to the model file and feature selection results, we perform relevant calculation. So we can determine the type of the page
The procedure of classifying the different types is similar to that of different language. I mainly conduct the page classification of two language types, finding that the accuracy and the recalling rate of type A are 92.3% and 86.7% respectively, and that the accuracy and the recalling rate of type B are 82.0% and 84.5% respectively, they all generally meet the expectation.
KEYWORDS SVM, feature extraction, web page classification, 2-class
II
目录
摘 要............................................................................................................................... I ABSTRACT ....................................................................................................................... II 目录............................................................................................................................... III 第1章 前 言 ............................................................................................................... 1
1.1项目意义及来源 .............................................................................................. 1 1.2 项目内容 ......................................................................................................... 1 1.3 作者完成的工作 ............................................................................................. 2 1.4 论文章节安排 ................................................................................................. 2 第2章 网页分类技术简介 ......................................................................................... 3
2.1 网页分类基本步骤 ......................................................................................... 3 2.2 常用分类算法 ................................................................................................. 4 第3章 网页分类过程概述 ......................................................................................... 6
3.1 网页分类流程 ................................................................................................. 6 3.2 特征提取概述................................................................................................. 6 3.3 模型训练概述................................................................................................. 7 3.4 结果评估 ......................................................................................................... 8 3.5 小结................................................................................................................. 8 第4章 SVM简介 ......................................................................................................... 9
4.1 最大边缘超平面............................................................................................. 9 4.2 线性支持向量机........................................................................................... 10
4.2.1 线性分类器的边缘............................................................................ 10 4.2.2 线性SVM模型.................................................................................... 11 4.3 非线性支持向量机....................................................................................... 12 4.4 核技术 ........................................................................................................... 14 4.5 小结............................................................................................................... 14 第5章 页面特征提取 ............................................................................................... 16
5.1 网页预处理 ................................................................................................... 16
5.1.1 网页解析 ............................................................................................. 16 5.1.2 语义信息的提取 ................................................................................. 17 5.1.3 对DOM树分块 ................................................................................... 18 5.2 网页特征提取 ............................................................................................... 18
5.2.1 特征的表示形式 ................................................................................. 19 5.2.2 特征提取 ............................................................................................. 19 5.3 特征筛选 ....................................................................................................... 20
5.3.1 特征频率 ............................................................................................. 20 5.3.2 文档频率 ............................................................................................. 20 5.3.3 信息增益 ............................................................................................. 21 5.3.4 期望交叉熵 ......................................................................................... 21
III
5.3.5 ?2统计法 ............................................................................................ 22
5.3.6 互信息法 ............................................................................................. 22 5.4小结 ................................................................................................................ 23 第6章 网页分类 ....................................................................................................... 24
6.1训练数据的组织 ............................................................................................ 24 6.2 模型训练 ....................................................................................................... 25 6.3 网页分类 ....................................................................................................... 26
6.3.1 初过滤 ................................................................................................. 26 6.3.2模型加载 .............................................................................................. 26 6.4 数据结果以及分析 ....................................................................................... 27 6.4 小结 ............................................................................................................... 28 第7章 总结与展望 ................................................................................................... 30 参考文献...................................................................................... 错误！未定义书签。 致谢.............................................................................................. 错误！未定义书签。 毕业设计小结.............................................................................. 错误！未定义书签。
IV
第1章 前 言
1.1项目意义及来源
随着internet的高速发展，尤其是WWW的全球普及，web上的信息资源已经涵盖了生活中方方面面的东西，我们也越来越依赖于网络，在网络上寻求我们想要的信息，而这些庞大的信息往往是纷乱无章的，网络信息过载的问题也日益突出，于是web挖掘技术和web信息检索技术也随之迅速发展。
Web信息处理的重要手段是搜索引擎，目前的搜索主要是采用基于关键字搜索的技术，而在实际的应用中，互联网数据太过庞大，这势必会影响到检索的效率以及准确度，往往会导致收索到的结果相关性不高。处理海量数据的一个重要方法就是将它们分类，网页分类是web文本挖掘领域的一个重要的研究方向，通过自动分类可以将网页按照类别建立相应的数据库，提高收索引擎的搜索效率以及查全率和准确率，从而建立自动的分类信息资源，为用户提供良好的分类信息目录。
1.2 项目内容
网页分类是对互联网页面进行某一类型的判断，为二分类问题，当然一个页面也可以被分类成若干种类型，其中每一种类型对应一个分类任务。我们通过对网页进行分类，相当于给每个页面打上标签，比如某个页面可能被标记为论坛或者新闻页面。 网页分类是一个偏向于应用性的项目，它依赖于很多基础模型和算法比如朴素贝叶斯、支持向量机、神经网络等，这里我们选取的是支持向量机（SVM）的算法。我们还需要对数据的进行一些预处理，由于网页是一堆文本信息，要想对网页进行分类，首先要对网页进行解析，最简单的就是构造DOM树，这是根据了html语言特有的结构性，将网页解析并存储成树的结构，有助于我们对信息的查找以及相关计算。 支持向量机算法很重要的一步就是构造训练语料，这里我们需要寻找到一批具有典型特征的页面，并对其进行解析等操作，构造一批适合SVM模型的训练集，通过对训练集的学习，SVM模型会输出模型参数，根据模型参数我们可以对随机页面进行分类。为了使SVM取得良好的效果，我们还需要对训练语料进行调整以得到最佳模型参数。 构造训练语料是SVM训练中重要的一步，我们得到的原始语料只是一批随即网页，这些网页是复杂且无规则的，为了让其适合SVM模型的训练，我们需
1
噪音影响，而且也会影响分类模型效率。网页的特征包含着不同层面的特征，包括内容的特征，网站的特征，url的特征等等，比如一些关键词会集中出现在某些网站上，则这样的关键词就具有很强的区分能力，再如url上也会有一些关键词如forum，novel等等出现，从这些关键词我们就可以窥探网页的类别。 特征提取的任务就是对无规律的网页提取出适合分类的特征信息，模型根据对这些特征的学习得到分类参数，这样就可以对随即的网页进行分类。良好的特征对网页分类将会有很大的正面影响，根据不同类型的页面，也要根据不同策略提取出相应特征，不能一概而论。
特征提取在网页分类中的位置如下：
上层应用：机器学习、网页分类、
页面是否作弊等等
页面基础特征
特征提取参数
特征提取模块
页面解析模块
URL/PACK/HTML
图3-2 模块关系图
3.3 模型训练概述
SVM模型是一种有监督的学习算法，基于对训练数据的学习得到模型参数，进而对随机页面进行分类的工作。
模型训练首先要获得训练数据，训练数据就是一些网页样本，但是原始的网页并不能直接来作为训练集合，因为原始网页具有复杂无规律的信息，我们需要根据原始网页提取有用的特征，如内容特征，网站特征，url特征等等。由于网页信息的庞大，过多的特征等于提升了训练样本的维度，这对训练模型来说有很大的负面影响，我们还需要降低训练数据的温度，这就包括一些特征筛选的方法比如特征频率(TF)、文档频率(DF)、信息增益(IG)、互信息(MI)、卡方拟和检验(CHI)以及期望交叉熵(ECE)，通过这些方法降低训练数据的维度，同时去除那些
7
信息含量较低的特征，尽量保留具有区分度的特征集合。良好的特征直接影响到分类的质量，所以特征提取和筛选是非常重要的一步。
通过一次训练并不能保证模型的良好性，这有几方面的原因，一来训练数据自身存在偏差，比如会存在标记错误的现象，二来训练数据的正负例比例不协调，导致模型无法学习到好的参数，还有一种情况就是训练数据覆盖的种类太少，对某型特殊页面不能很好分类。对于这些情况，我们需要反复迭代训练数据，通过添加语料，调整正负例比例，完善训练语料覆盖面等等，让训练数据力争达到覆盖全面、无差错的效果。
3.4 结果评估
通过训练数据得到的模型最终需要对测试集进行测试来得到最终效果，网页分类是二分类问题，样本点会被标记为正例或负例，分类模型也会将样本分类为正例或负例，这样就会产生四种组合，如下：
表 3-1 数据评估
被分类为正例 被分类为负例
实际正例 A C 实际负例 B D 我们用召回率和准确率还评估模型的分类效果，这里我们只考虑正例的分类效果：
召回率R?准确率P?A A?CA A?B 召回率和准确率是相互影响的评价指标，我们往往需要根据具体需求考虑一种折中的情况。
3.5 小结
本章主要对网页分类的整体流程进行了概述，由于网页分类涉及到多个模块的工作，所以这样可以增加读者对整体框架的把握。在此基础上，下面会对SVM模型进行简单的介绍以及对特征提取方法做出介绍，并对模型预处理的一些步骤进行一些讲解。
8
第4章 SVM简介
支持向量机（support vector machine, SVM）是一种有监督的机器学习方法，依靠小样本学习后的模型参数进行分类，它已经成为了一种备受关注的分类计数，这种技术具有坚实的统计学理论基础，并且在手写识别、文本分类等等问题中展示了很好的实际效果。另外，SVM可以避免维数灾难，很好的解决高维数据的分类问题。支持向量机有一个独特特点，它使用训练集的一个子集来表示边界，该子集叫做支持向量（support vector）。支持向量机的基本思想是找到一个最大边缘超平面，并以此来对数据进行分类
4.1 最大边缘超平面
下图显示了一个数据集，它包含两类数据，其中方块代表一类，圆圈代表一类，并且这个数据集是可分的，也就是说可以找到一个超平面，使得所有的方块位于超平面一侧，圆圈位于另一侧。这样的超平面可能存在无数个，且他们的训练误差都等于零，但是我们并不能保证在未知的测试数据上，它们都会取得同样好的效果。
b21 B2 b22
B2的边缘 B1 b11
B1的边缘 b12
图 4-1 决策边界的边缘
我们观察两个决策边界B1和B2，如图3.1所示。这两个边界都能准确无误的
9
将训练样本划分到各自的类别中，每个决策边界Bi都对应一对超平面，记为
bi1和bi2，其中bi1是这样得到的：平行向左移动一个和决策面平行的超平面，直到触到最近的训练样本为止；类似的，bi2是向右移动触到最近的训练样本得到的超平面。这两个超平面之间的距离成为分类器的边缘。从图4-1可以看到，B1的边缘显著大于B2的边缘，其中B1就是训练样本的最大边缘超平面。
4.2 线性支持向量机
线性SVM是这样一个分了器，它可以寻找最大边缘超平面，因此它也常常被称为最大边缘分类器。 4.2.1 线性分类器的边缘
考虑一个包含N个训练样本的二元分类问题，每个样本可以表示成一个二元
组(xi,yi)(i?1,2,……,N)，其中xi?(xi1,xi2,……,xid)T，对应于第i个样本的属性集。我们令yi?{?1,1}表示它的类别标号，一个线性分类器的决策边界可以写成如下形式：
w?x?b?0
其中w和b是模型参数
wx+b=0
wx+b=1 wx+b=-1 图4-2 SVM的决策边界和边缘
10
任何位于决策面上方的样本点xs，我们可以证明：
w?xs?b?k （4-1）
其中k?0，同理，对于决策面下方的样本点xc，我们可以证明：
w?xc?b?k' （4-2）
其中k'?0
我们令所有方块的类别标号为1，所有圆圈的类别标号为-1，则对于一个新
来的测试样本z，可以用下面方法判断其类别标号y
?1如果w?z?b?0y????1如果w?z?b?0
考虑那些里决策边界最近的样本点，由于方块位于决策面的上方，因此对于
某个正值k，它必然满足公式（4-1）；而对于某个负值k'，下方的样本点必然满足公式（4-2），调整决策面的参数w和b，两个平行的超平面bi1和bi2可以表示如下：
bi1:w?x?b?1bi2:w?x?b??1
决策边界的边缘由这两个超平面之间的距离给定。设x1和x2分别是bi1和bi2上的点，带入公式并相减得到
w?(x1?x2)?2 即w?d?2 所以d?2 w4.2.2 线性SVM模型
SVM的训练就是从训练样例中估计决策边界的参数w和b，选择的参数必须满足一下条件：
11
w?xi?b?1如果yi?1w?xi?b??1如果yi??1
也就是要求所有标号为1的样本点都在超平面w?xi?b?1上或上方，所有标号为-1的样本点都在超平面w?xi?b??1上或下方。将这两个不等式表示成更紧凑的形式如下：
yi(w?xi?b)?1,i?1,2,……,N
约束条件是决策边界的边缘必须的最大的，而最大化边缘等价于最小化下面的目标函数：
wf(w)=2
综合上面的介绍，SVM的学习任务可以归纳为以下被约束的优化问题：
2wminf(w)=2subjecttoyi(w?xi?b)?1,i?1,2,……,N
该问题的解应用到了拉格朗日乘子的方法，由于本文只是将SVM应用到网页分类中，并不是专门讨论SVM模型的求解，所以这里省略求解的分析过程，只给出最后求解结果，具体过程可以参考数据挖掘导论(Pang-Ning Tan, Michael Steinbach, Vipin Kumar)[1][2]。
引入拉格朗日算子构造对偶优化问题：
2LD=??i?i=1NN1??i?jyiyjxixj2i,j
求解得到?i，再根据w???iyixi和?i[yi(w?xi?b)?1]?0求解模型参数w和
i?1b。则决策边界可以表示成
(??iyixi?x)?b?0i?1N
4.3 非线性支持向量机
前面描述的线性支持向量机是构建一个线性的决策面面，从而把训练数据划分到各自的类别中，而在很多情况下，线性的决策面并不能很好的准确无误的划
12
分数据，比如下面的情况：
图4-3 线性不可分
我们并不能用线性决策面将训练机划分到两个类别中，对此我们需要一个非
线性变换?，将数据从原来的特征空间映射到一个新的空间，使决策面在新的特征空间里成为线性可分的。这里我们不讨论如何选择合适的映射函数，这已经超出本文研究的范畴，我们只是将SVM作为一种分类方法做简单的介绍
假定我们已经找到合适的映射函数?(x)，变换后我们需要构建一个线性的决
策边界，把样本划分到它们各自的类别中，在变化后的空间里，线性决策边界具有以下形式：
w??(x)?b?0
和线性SVM的优化问题类似，非线性SVM的学习任务可以表示为如下的优
化问题：
wminw2subjecttoyi(w??(x)?b)?1,
2
i?1,2,……,N非线性SVM的学习任务和线性SVM的学习任务很相似，它们主要的区别在于，
学习任务是在变换后的属性?(x)，而不是在原来的属性x上执行的。和线性SVM问题类似，我们可以得到非线性SVM优化问题的对偶拉格朗日函数：
LD???i?i?1n1?i?jyiyj?(xi)?(xj) ?2i,j13
使用二次规划技术得到?i后，通过下面的方程求出参数w和b：
w???iyi??xi?i?i{yi(??jyj?(xj)??(xi)?b)?1}?0j
要注意的是，上面的一些公式都涉及到变换后的空间中向量对之间的点积
，在多维空间中这种计算是相当麻烦的，可能导致维数灾?(xi)?(xj)（即相似度）
难，这一问题的解决方案是一种称为核技术的方法。
4.4 核技术
点积常常用来表示向量之间的相似度，例如?(xi)?(xj)可以看做两个实例xi和xj在变换后的空间中的相似性度量
核技术是一种使用原有属性集计算变换后空间中的相似度的方法，比如对于
映射
?:(xi,xj)?(x12,x22,2x1,2x2,2x1x2,1)
两个输入向量u,v在变换后的空间里的点积可以表示成如下形式：
?(u)??(v)?(u12,u22,2u1,2u2,2u1u2,1)?(v12,v22,2v1,2v2,2v1v2,1)?u12v12?u22v22?2u1v1?2u2v2?2u1u2v1v2?1?(u?v+1)2
该分析表明，变换后空间中的点积可以用原来空间中的相似度函数表示：
K(u,v)??(u)??(v)?(u?v+1)2
这个在原属性空间中计算的相似度函数K就称为核函数，核函数有助于处理
如何实现非线性SVM的一些问题，核函数的选取必须满足一个称为Mercer定理的数学原理，这里就不作介绍了。常用的核函数有如下几个：
K(x,y)?(x?y+1)pK(x,y)?eK(x,y)?tanh(kx?y??)
?x-y/(2?2)24.5 小结
本章主要对SVM模型进行了简要介绍，其中省略了很多理论性的推导，因为本文的目的不是研究SVM模型本身，而是基于SVM模型做网页分类的工作，所以
14
下面的重心会偏重于网页分类的具体工作，如特征的提取，训练语料的处理以及如何将SVM模型和网页分类相结合起来。
15
第5章 页面特征提取
网页分类的质量很大程度上取决于特征提取的好坏，网页本身具有复杂无规律的很多特征，而我们需要对这些特征进行提取还筛选，选取那些具有区分度的特征，特征的选取主要是通过对网页的预处理提取出网页的文本信息和结构信息，然后利用一些成熟的特征筛选方法进行筛选，包括特征频率(TF)、文档频率(DF)、信息增益(IG)、互信息(MI)、卡方拟和检验(CHI)以及期望交叉熵(ECE)，主要是因为原始网页特征维度太大，其中包含很多噪声，区分度不明显，无法对后序SVM学习提供帮助，而且这些未经处理的特征甚至会给分类算法的计算带来巨大的开销，同时也会对分类效果产生负面影响，因此我们有必要在分类前对这些特征进行提取和筛选，对数据维度进行压缩，保证准确度的前提下尽量减少训练数据的空间维度。
5.1 网页预处理
网页主要是由html语言书写，它与纯文本之间存在很大差别，主要体现在一下几方面[8]：
1、 网页包含大量的结构化标签，比如
，