网页分类 (4)

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、 网页包含大量的结构化标签，比如，