基于代价敏感SVM的直接优化F-measure算法研究

摘要

随着社会的发展、科学的进步，数据挖掘和机器学习等领域的研究正逐渐改变我们的生活。数据分类作为机器学习和数据挖掘领域的重要组成部分，成为众多学者的研究重点，人们提出了不同的分类算法来构建不同的分类器。以二分类为例，当样本数据分布不平衡时，为了更准确的度量分类器的性能，一般选用查准率和查全率的调和平均——F-measure作为评估标准。由于F-measure在不平衡分类的广泛应用，如何设计出有效的面向F-measure的分类器是近年来的研究热点。但是由于F-measure的非凸性，直接优化起来较为困难，现有的优化算法主要通过代价敏感算法或者直接优化算法构造面向F-measure的学习器。不同于已有的研究，本文以SVM为工具，提出一种结合代价敏感和直接优化F-measure的新型算法。
　　本文的主要工作如下:
　　(1)文中从二分类入手，介绍了基于支持向量机的二分类学习及不平衡二分类的度量标准F-measure，并在此基础上，分析了现有代价敏感算法和直接优化F-measure算法的研究现状，提出了一种将二者相融合的新方法。
　　(2)新方法首先给出了从最大化F-measure到代价敏感SVM的一个直接转换。针对新的目标函数具备非光滑从而导致传统梯度优化算法难以直接使用的特点，提出使用基于次梯度的束方法进行求解。不仅可以解决上述问题，且算法的迭代次数仅为O（1/ε），不依赖于样本数。不平衡数据集上的实验表明:相比起已有面向F-measure的分类器，本文所提算法得到的模型明显更加精确。
　　(3)针对束方法在求解主问题最小值时是通过转换成对偶问题来解决的，而算法内部的每次迭代只能保证对偶问题的单调递增，并不能保证主问题的单调递减，可能降低算法的收敛速度。提出一个高效的线性搜索算法，确保了主问题的单调递减，消除了主问题的波动，进一步提高了算法的效率。大规模数据集上的实验表明，该算法不仅能获得高精度的二分类模型，且相比起已有其他直接优化F-measure算法也更为高效。

目录

声明

摘要

图目录

表目录

第一章 绪论

1．1 研究背景及意义

1．2 国内外研究现状

1．3 本文的工作与安排

第二章 相关理论

2．1 二分类学习的概述

2．2 支持向量机的概述

2．2．1 支持向量机的基本原理

2．2．2 线性支持向量机

2．2．3 支持向量机的实现

2．3 二分类学习的度量标准———F-measure

2．4 代价敏感学习算法概述

2．5 直接优化F-measure算法概述

2．6 本章小结

第三章 一种融合代价敏感与直接优化F-measure的新型算法

3．1 从直接优化F-measure到代价敏感SVM

3．2 基于束方法算法的优化

3．2．1 束方法的基本思想

3．2．2 基于束方法的求解过程

3．3 实验结果与分析

3．3．1 折中因子对实验结果影响

3．3．2 代价参数对实验结果影响

3．3．3 不同算法性能对比实验

3．4 本章小结

第四章 面向大规模应用的高效直接优化F-measure算法

4．1 BM-CS算法的主问题波动

4．2 高效直接优化F-measure算法的实现

4．2．1 算法的基本思想

4．2．2 高效线性搜索算法的实现

4．3 算法的复杂度分析

4．4 实验结果与分析

4．4．1 实验数据集及比较算法

4．4．2 对比实验与分析

4．5 本章小结

第五章 总结与展望

5．1 论文总结

5．2 工作展望

参考文献

致谢

攻读硕士学位期间发表的论文

攻读硕士学位期间参加的科研项目