普适计算环境下基于SVM的信息分类方法的研究

摘要

在普适计算环境中,情境信息分析非常重要,它对普适计算环境下的应用能否提供正确服务起着决定性的作用。普适计算的应用要求对情境信息快速而准确的分类和管理,然而收集到的信息往往数量巨大,类别繁多,因此找出一种有效的分类方式并应用于普适计算环境具有很重要的意义。支持向量机分类方法是一种基于统计学习理论的机器学习方法,在非线性和高维样本训练中都表现出特有的优势。支持向量机分类方法以其理论优势,在文本分类应用领域已经取得优秀的效果,同时支持向量机分类方法在人脸识别和图像处理等其他领域也有广泛的研究和应用。
　　本文在研究了支持向量机的多种算法之后,针对向量乘法提出了半稀疏算法,并将其应用于序列最小优化方法,提高了在大规模稀疏矩阵中向量乘法的运算速度,从而优化了SVMTorch分类器的计算性能。通过理论分析,在两个分别含有m和n个元素的向量上进行比较和寻址时,使用传统的稀疏算法的SVMTorch算法需要消耗O(m+n)的时间,而半稀疏算法则可以在O(n)的时间内完成这两个向量的乘法处理,同时不影响支持向量机分类器的精确度。实验结果显示,基于半稀疏算法的SVMTorch分类器计算性能显著优于原始SVMTorch分类器的性能。在WebKB和20-newsgroup两个语料库上,基于半稀疏算法的SVMTorch训练时间分别是原始SVMTorch的54.32％和74.95%。此外,本文还对支持向量机的SVMTorch分类器加以拓展,使它不仅支持多分类单标签的分类问题,同时还支持多分类多标签的分类问题,通过更新SVMTorch分类器的训练和测试检验算法,使其输出结果支持多标签分类运算,并在Reuters-21578语料库上对多分类标签功能进行了验证。为了进一步提高SVMTorch分类器的计算性能,本文使用消息传递接口模型(MPI)将SVMTorch分类器并行化,使其可以在多核处理器及分布式集群上并行计算。本文最终实现了一个基于半稀疏算法的、使用多标签分类功能、并行化的SVMTorch的功能原型,并将其应用于中文网页分类。

目录

摘要

ABSTRACT

表格索引

插图索引

第一章 绪论

1.1 研究背景

1.1.1 普适计算

1.1.2 支持向量机

1.2 研究意义

1.3 关键技术

1.4 本文组织结构

1.5 本章小结

第二章 相关理论和研究

2.1 支持向量机简介

2.2 支持向量机的算法

2.2.1 基于分解的算法

2.2.2 序列最小优化算法

2.2.3 其他重要算法

2.3 本章小结

第三章 半稀疏算法

3.1 传统的稀疏算法

3.2 半稀疏算法的设计与实现

3.2.1 半稀疏算法

3.2.2 半稀疏算法的实现

3.2.3 半稀疏算法的性能分析

3.2.4 静态实现与动态实现

3.3 半稀疏算法的讨论

3.4 实验和验证

3.4.1 数据集

3.4.2 参数设置

3.4.3 性能综述

3.4.4 分类精确度

3.4.5 训练时间与参数c的关系

3.5 本章小结

第四章 多标签分类及并行实现

4.1 多分类问题

4.1.1 多分类单标签问题

4.1.2 多分类多标签问题

4.1.3 SMO对于训练失衡的自适应性

4.1.4 基于SVMTorch的多标签分类方法

4.2 并行化的SVMTORCH设计

4.3 实验数据与分析

4.4 本章小结

第五章 SVMTORCH在网页分类中的应用

5.1 系统框架

5.2 中文网页的表示

5.3 中文网页的分词处理

5.4 中文网页的特征提取

5.5 基于SVMTORCH的特征提取

5.6 实验结果和分析

5.7 本章小结

第六章 全文总结

6.1 全文结论

6.1.1 半稀疏算法

6.1.2 多标签分类

6.1.3 SVMTorch的并行程序实现

6.1.4 改进的SVMTorch在网页分类中的应用

6.2 研究展望

参考文献

致谢

攻读硕士学位期间已发表或录用的论文