基于SVM的程序设计相关网页判别系统

1、背景介绍

ACM/ICPC，国际大学生程序设计竞赛的重要性与含金量不言而喻，东华大学一直致力于此竞赛的学生选拔与学生培养，并搭建了本校自己的Online Judge系统（简称DHUOJ）。此系统在汇总了一些其他著名OJ题库的习题同时，也在互联网中收集了不少相应的解题报告，供师生参考学习。

DHUOJ的解题报告收集模块现在是这样工作的：以题号为关键字在搜索引擎中搜索，对前面若干个搜索结果进行判别，判别规则为网站域名对比、关键词匹配等，较为机械，准确率也不是很高，词库需要人工维护且扩展性不强。

此系统利用基于统计的机器学习算法，期望得到更好的判别效果。

2、研究现状

文本分类,是指计算机将一篇文章归于预先给定的某一类或某几类的过程。计算机并不具有人类的智慧，不能读懂文字，所以必须把文本转化成计算机能够理解的形式，即进行文本表示．目前文本表示模型主要是Gerard Salton和McGill于1969年提出的向量空间模型(VSM)。向量空间模型的基本思想是把文档简化为特征项的权重为分量的向量表示：(w1,w2,…,wn)，其中wi为第i个特征项的权重，一般选取词作为特征项，权重用词频表示。

目前统计学习的方法已经成为了当前文本分类的主流，其实际的性能也非常的优秀，误判率比较低。但是，我们必须承认，文本是一种信息载体，其所携带的信息由几部分组成：组成元素（词语）的信息、组成元素之间顺序关系带来的信息以及上下文信息。Vector Space这种文档表示方法，基本上忽略了除元素的信息以外所有的部分，这使得它能表达的信息量存在上限，也直接导致了基于这种模型构建的文本分类系统，几乎不可能达到人类的分类能力。

3、课题研究内容

3.1  简述

该判别系统接受一个url（或文本）作为输入x，判别后输出字符串y，阐明该网页（或文本）的类别。记集合A={文档|它的内容与算法实践相关，也即描述的是计算机数据结构编程的相关内容}。那么y为“yes”或“no”，前者表示x∈A；后者表示x∉A。

该系统可用于自动化收集各大Online Judge（程序在线评测平台）上题目的解题报告。

该系统可分为三个层次。第一层实现原始数据到结构化的文档的处理，分词也在这一步完成；第二层对训练样本集进行统计求出初始特征空间，并通过卡方检验得到抽取后的特征空间，由此可计算每篇文档的特征向量；第三层把上步得到的归一化后的特征矩阵与标签矩阵送往SVM进行训练，通过对较关键的参数调优，得到训练好的模型。

机器学习完成后即可使用得到的模型对未知样本进行预测，即类别判断。

3.2 示例

假设urlA，http://a.com/a.html的正文内容为下面一段，用斜体表示：

图论总述。图的存储。图通常用G=（V,E）表示。V为顶点（vertex）集合，E为边(Edge)的集合。 图的物理存储，有两种方法。 1.邻接矩阵，就是二维数组，较直观，但不能存储重边。 2.邻接表，它是一种顺序与链式兼有的存储。 n个顶点的连通图至少有多少条边? 答：至少要有（n-1）条边。对于简单图而言至多有n*(n-1)/2条边，此时即是完全图。  二部图 二部图：存在一种划分方法，将图G的顶点划分为两个集合A和B，使得图中任意一条边的两个邻接顶点分属不同的顶点集。 匹配：二部图中没有公共顶点的边集。边数最多的匹配叫最大匹配。若图中每个顶点都被匹配边邻接，叫完美匹配。 未盖点：不与任何匹配边邻接的顶点。 增广路：从未盖点出发，经非匹配边、匹配边、非匹配边......交替进行，最终以未盖点结尾，此路径叫增广路。在增广路中，把原匹配边与非匹配边对换，则得到的新匹配比原来的多一条边。 匈牙利算法：不断寻找增广路，最终得到最大匹配。

假设urlB，http://b.com/b.html的正文内容为下面一段，用斜体表示：

人民日报全媒体平台3月5日电  （记者杜尚泽）习近平参加上海代表团审议时，杨雄第一个发言，主题是加快建设具有全球影响力的科技创新中心。讲到环境保护时，习近平格外关注。“空气质量优良的能占多少？”“70%。”这时有人插话说：“有时候是靠天吃饭”。笑声中，习近平接话说：“不能只靠借东风啊！事在人为。” 谈人才政策：地方手脚还要放开一些 谈及人才政策，习近平说，人才是创新的根基，创新驱动实质上是人才驱动。要择天下英才而用之，实施更加积极的创新人才引进政策。“人才政策方面手脚还要放开一些，要集聚一批站在行业科技前沿、具有国际视野和能力的领军人才。”

那么输入x为urlA时，我们期望得到的输出y是“yes”；输入x为urlB时，我们期望得到的输出y是“no”。

3.3系统效果评判

该系统接受的输入为url或文本文件。输入url时系统会将其预处理为文本文件，然后操作流程一致。要求它们的内容为一段有意义的中文段落。

机器学习完成后即可使用得到的模型对未知样本进行预测，即类别判断。

我们可以这样评价该系统的优劣：用一组事先人工分好类的文本，这些文本由互联网中随机抽取的页面得到，送往该系统进行判断。得出的结果与人工分类的结果进行对比，得出准确率等量化指标。

4、技术路线

4.1  利用Jsoup在互联网中摘取指定url的页面并剔除html标签，得到正文。

4.2  利用IKAnalyzer与Lucene对中文文本进行分词，得到满意的分词后的词组列表。

4.3  从训练样本集中统计出出现过词组的全集，并通过卡方检验进行特征抽取。

4.4  根据卡方检验得到的特征空间计算文章的特征向量并进行归一化。

4.5  将训练集标签与训练集特征矩阵送往SVM进行训练，并对SVM进行参数调优。

4.6  得到训练好的SVM模型，它可以对新的未知样本进行预测，达到目的。

5、关键技术介绍

5.1  摘取指定url的页面并得到正文

一个url标识着互联网中的一个网页，通常通过带有get方法的http请求得到。通过浏览器批量获得网页效率太低，于是想到Jsoup这一java工具，能得到html源文件并剔除其中的标签记号，得到正文。

5.2  IKAnalyzer中文分词器

相比于英文文本分类，中文文本分类的一个重要的差别在于预处理阶段：中文文本的读取需要分词，不像英文文本的单词那样有空格来区分。这里使用IKAnalyzer中文分词器，并配置自己的停止词词典与扩展词典。

5.3  SVM的应用

支持向量机的主要思想是建立一个分类超平面作为决策曲面,使得正例和反例之间的隔离边缘被最大化,支持向量机的理论基础是统计学习理论,更精确的说,支持向量机是结构风险最小化的近似实现。这个原理基于这样的事实:学习机器在测试数据上的误差率(即泛化误差率)以训练误差率和一个依赖于VC维数(Vapnik-Chervonenkis dimension)的项的和为界,在可分模式情况下,支持向量机对于前一项的值为零,并且使第二项最小化。因此,尽管它不利用问题的领域内部问题,但在模式分类问题上支持向量机能提供好的泛化性能,这个属性是支持向量机特有的。

6、要解决的技术问题

6.1  有些网站会封堵爬虫，所以需要巧妙地构造Jsop的http请求。

6.2  中文分词以及停用词处理问题。

6.3  弄懂svm的数学原理。

6.4  svm的训练与使用。

6.5  批量下载url指定的网页并保存在本地，用于离线环境下的svm学习。

7、日程安排

8、参考文献

[1]同济大学数学系。工程数学线性代数。北京：高等教育出版社，2012。

[2]（土耳其）Ethem Alpaydin著，范明，昝红英，牛长勇等译。机器学习导论。北京：机械工业出版社，2014。

[3]（加）Simon Haykin著，申富饶等译。神经网络与机器学习。北京：机械工业出版社，2014。

[4]Microsoft Developer Network 资源库。 http://msdn.microsoft.com/library。

[5]刘浩，韩晶著。Matlab R2012a完全自学一本通。北京：电子工业出版社，2014.

[6]陈明 等著。MATLAB神经网络原理与实例精解。北京：清华大学出版社，2014.

[7]Fabrizio Sebastiani.Machine learning in automated text categorization[J].ACM Computing Surveys,2002,334(1):1-47.

[8]Arbib,M.A.,The Handbook of Brain Theory and Neural Networks,2d ed.,Cambridge,MA:MIT Press.2003.

[9]Boyan,J.A.,”Technical update:Least-squares temporal difference learning,”Machine Leaning,vol。49，pp.1-15.2002.

[10]埃史尔 著, 陈昊鹏 译。Java编程思想(第4版)。北京：机械工业出版社，2007。

[11]Michael McCandless,Erik Hatcher, Otis Gospodnet著,牛长流,肖宇译。Lucene实战(第2版)。北京：人民邮电出版社，2012。