基于词频统计的wap分类器设计与实现.doc

基于词频统计的 wap 分类器设计与实现靳相伟，戴志涛*（北京邮电大学计算机学院，北京 100876）510152025303540摘要：移动互联网时代的到来给人们上网带来了方便，但同时由于互联网信息的多样性，人们搜索信息时往往会遇到返回的都是一些广告信息，或者是一些与自己搜索毫无关系的信息，甚至是一些不良信息。为了增强 wap 用户搜索体验，本文基于词频和支持向量机模型实现了一款 wap 资源分类器，完成了游戏、软件、视频、音频、图片、主题六大类的分类，最后通过实验结果分析验证，该分类器分类准确率在 90%以上，召回率在 80%以上，通过本文的 wap 资源分类器大大提高了用户的搜索体验。关键词：wap；分类器；SVM；机器学习中图分类号：TP391.1Design and Implementation of wap classifier based on wordfrequency statisticsJIN Xiangwei, DAI Zhitao(Computer Science School,Beijing University of Posts and Telecommunications, Beijing 100876)Abstract: The arrival of the mobile Internet era has brought to us convenient, but at the same timedue to the diversity of information on the Internet, people search for information is often despairbecause of that the search result often has the advertising information, or there is nothinginformation could use, even there would be some bad information. To enhance wap users searchexperience, a wap resources classifier which is based on word frequency and support vectormachine model has completed in this paper. It complete the classification of the game software,video, audio, images, themes, and the accuracy rate of this wap classifier is more than 90%, therecall of this wap classifier is more than 80%. The wap resource classification has greatlyimproved the search experience for the users.Keywords: wap; classifier; SVM; machine learning0 引言随着嵌入式设备和移动互联网的发展，人们越来越倾向于使用手机等手持设备登陆互联网，浏览网页，查找资料等。互联网上充斥着各种各样的信息，有些是垃圾信息，有些是广告信息，更有些是不良信息，这些信息已经影响到了用户的体验，给用户带来了不悦。同时为了节省流量用户比较偏爱登陆 wap 网站，为了提高用户用手持设备登陆 wap 互联网搜索的体验，需要设计 wap 资源分类器，通过 wap 资源分类器将 wap 网页分类入库，在用户输入查询条件时，可以返回相关度比较高的结果，以增加用户体验。目前研究比较多的是基于web 网页的分类1，但随着移动互联网的发展，wap 网页分类也越来越受到重视。本文设计并实现了一款 wap 资源分类器，将 wap 网页分为了游戏、音乐、视频、主题、游戏、图像六大类。从选取网页特征，到数学建模，训练模型，最后编码实现网页分类器，并进行实验验证，实验结果显示，该分类器无论是从准确率还是在召回率上看，对提高用户搜索体验，提供了重要的帮助。作者简介：靳相伟，（1988-），男，硕士研究生，主要研究方向：嵌入式与网络通信；计算机体系结构。通信联系人：戴志涛，（1969-），男，北京邮电大学计算机科学与技术学院体系结构中心教授，硕士生导师，主要研究方向：嵌入式系统；宽带通信；计算机体系结构；可重构计算。 E-mail: -1-1 wap 资源分类的整体设计方案1.1 wap 资源分类在搜索中的位置Wap 资源分类器在搜索引擎的整个流程中处在很关键的位置，首先通过爬虫获取大量网页数据，选取其中比较有代表性的进行人工标注，对人工标注的页面进行分析提取出 wap4550网页的特征值，建立特征向量表，设计 wap 分类程序。将最终通过分类的 wap 网页建立索引，入库。客户端通过手持设备进入移动互联网，搜索网页，经过核心词分析，查找库中的索引，查找成功返回结果给客户端（图 1）。通过分析分类器在整个搜索引擎中的位置，可以发现 wap 资源分类的重要性，其性能的好坏，直接关系到最终的用户体验。图 1 Wap 资源分类器在搜索引擎中的位置1.2 基于词频的统计分类算法1.2.1wap 资源分类器设计方案5560设计方案主要包括四部分：备选特征、特征选择、模型训练、分类程序。大致的流程关系是：决定使用哪些备选特征；根据已标注的页面数据，从备选特征中选择好特征；根据选择的特征，在标注数据上进行训练，得到一个分类模型；根据这个模型，写出分类程序，上线运行。其中，备选特征、特征选择、模型训练是线下的，可放宽编程环境和运行效率的要求，使用 java。最后的 wap 资源分类程序必须上线运行，所以使用 C+，而且需要特别注意程序的优化问题2，提高效率运行效率。1.2.2特征选取（1）备选特征通过分析 wap 网页得到以下备选特征：下载链接的锚文；URL 信息；图片信息；Title信息；版本信息（一般软件会有版本信息）；评论信息分析；文件大小；分辨率信息；meta65信息；内容的分析；顶、踩、支持、下载、好评等信息；后缀名 Suffix 信息。-2-（2）选取特征分析备选特征，比较好选定的信息有下载链接的锚文、URL 信息、Title 信息、后缀名Suffix 信息和 meta 信息。但是对锚文信息的应用也一般是应用其锚文信息的后缀名，所以可以用后缀名 Suffix 信息来代替。70一个特征是 2 元的：特征类别+字符串，这样得到的备选特征会很多。在标注数据上对备选特征进行统计，对每一个特征，得到它出现的总次数、在 6 类中每类出现的次数。注意6 类次数加起来小于等于总次数，因为一些网页是不属于 6 类的。如果出现的总次数高于一个值（比如 10 次），并且 90%都出现在同一个类中，则认为这是一个好的特征，予以保留；否则删掉此特征。751.2.3模型训练模型训练的目的，是根据已选择好的特征，从标注数据中训练出一个模型；用这个训练好的模型，就能对一个未知的新页面，得出其分类。先从标注数据中，对所有备选特征中进行统计，根据统计结果，保留选择的大约 2000个特征。通过 SVM3模型对 6 种分类采用二分类模型训练，得到六个二分类模型，供分类80859095100程序调用。2 wap 资源分类程序实现2.1 wap 资源分类程序设计步骤一：将备选特征表读入内存，并组织成一定的数据结构（为了方便表述，以下称为数据结构 1）。该数据结构的每个数据项必须至少包含如下四项：特征类型（url、title、suffix、meta 四者之一），特征值（一个字符串），该数据项的分类（预先定义的六类之一，不包括 other 分类），特征项出现的次数（count）。步骤二：取得待分类网页本身的 url，经过拆分处理，得到其所有由字母和数字组成的字串。步骤三：遍历 DOM 树4，得到该网页的 title 及所有网页内的链接 suffix 和 meta 信息。步骤四：对步骤三得到的 title、suffix 和 meta 进行处理，具体处理方法为：获取 title 和meta 字符串的所有非空字串，获取所有 suffix 的后缀。步骤五：将步骤二和步骤四得到的所有特征存入一个数据结构（为了方便表述，以下称为数据结构 2），该数据结构的每个数据项必须至少包含如下两项：特征类型（url、title、suffix、meta 四者之一），特征值（一个字符串）。也可以在处理的同时存入。经过以上四步之后，得到了待分类网页的特征表。步骤六：将所有同时出现在数据结构 1 和数据结构 2 中特征项（特征类型+特征值）的行提取出来，形成一张新表。该新表的行结构与数据结构 1 相同，并且是为真子集。步骤七：第步骤六得到的新表，将表格转换成 SVM 标准接口形式。步骤八：将转换为 SVM 标准接口形式的表排队经过第一章中所训练好的六类模型进行判断，最后输出判断结果。步骤九：重复步骤二到步骤八，可以确定多个待分类网页的类别。具体流程如图 2 所示。-3-图 2分类器程序流程图1052.2 数据结构本模块最主要的涉及到三类数据结构：用于存储待分类网页特征的数据表；用于存储备选特征的数据表；用于返回判定结果的结构。Struct FeatureUnsigned char featureType;/特征类型，titlesuffixurlmeta 四者之一110;String value;/特征值Vector FeatureVector;/数据表备选特征数据表：Struct FeatureTableRow-4-115;Unsigned char featureType;String value;Unsigned char wapTyep;Unsigned int count;/特征类型，titlesuffixurlmeta 四者之一/ 特征值/网页类型 gamesoftmusicthemevideopicture/备选特征出现次数120Map FeatureTable;/备选特征数据表3 结果分析3.1 准确率和召回率准确率和召回率5是评定分类器重要的指标，本文的分类器的准确率和召回率如下图所125示（评测数据集为 8000 个人工标准的页面）。分类器准确率和召回率120%100%80%60%40%20%0%准确率召回率picturegamethemevideo software music3.2 稳定性图 3wap 资源分类器的准确率和召回率130135本分类器代码在 50 万级的测试数据上循环运行 48 小时无 core；内存使用为 20M；平均每个页面的识别效率为 1.6ms。本系统从分类角度将 wap 网页分为了图片、游戏、主题、视频、音乐和软件六大类。从扩充性上来看，今后可增加特征值改进系统的准确率和召回率，还可以从增加 wap 网页分类来实现更多的网页分类，进一步提高用户的搜索体验。4 结论本文通过词频统计和支持向量机模型实现了一款 wap 网页分类器，从整体设计和代码实现以及扩展性给出了详细的描述。通过选取特征，训练模型6，编写分类器代码，验证模型的准确率和召回率，并对稳定性做了测试。实验表明，本文的 wap 资源分类器，具有较高的稳定性和效率，整体上提高了用户搜索体验。140-5-参考文献 (References)12李净，袁小华，沈晓晶. Web 网页信息文本分类的研究J. 计算机工程与设计，2008，29（23）：6026-6028.陈宜，唐乐理. 程序优化的基本思路J. 实验