面向不平衡二分类准则的稀疏模型构造算法研究

摘要

社会的进步，科学的发展，给人们生活带来了日新月异的变化。与此同时各种数据信息的不断积累，在方便人们的同时，也带来了新的挑战。如何从这些大量数据中发现有用信息成为当前急需解决的迫切问题。机器学习的出现为解决上述挑战提供了一种有效的手段，其中的分类学习特别是二分类学习由于在众多领域的广泛应用更是成为当前的研究热点。然而在现实的生活中，很多应用（如网络搜索引擎、个性化推荐系统等）都是不平衡二分类问题，且具有数据维度高的特点，已有面向小数据的传统二分类算法很难直接应用在上述问题中。对此，近些年有学者提出研究直接优化不平衡准则的稀疏二分类模型构造算法，并取得了较好的效果。但这些研究考虑的不平衡准则都是AUC或F1等简单易分解的标准，对于其他较复杂的不平衡准则，如何获得相应的稀疏模型，则研究较少。本文就是在这样的背景下，主要研究了面向复杂不平衡准则的稀疏模型构造算法。
　　全文的主要工作如下:
　　(1)文中从二分类学习入手，首先介绍了传统二分类和不平衡二分类在评估准则的差异，然后总结了面向不平衡二分类算法的研究现状，重点分析了不平衡稀疏模型构造算法的进展，在此基础上，提出研究基于L1范式的复杂不平衡稀疏模型构造算法。
　　(2)不同于已有不平衡稀疏模型构造算法多关注AUC或F1等简单准则，本文研究了面向复杂不可分QM准则的稀疏模型构造算法。算法首先定义了基于QM的新目标函数，针对该目标非光滑难以直接优化，提出使用割平面算法进行求解，不仅解决上述问题，且算法的外围迭代次数仅为O(1/ε)。不平衡基准数据集上的实验结果表明，当用QM为评价标准时，本文提出的算法不仅有很好的精度还有较高的稀疏度。
　　(3)针对已有不平衡稀疏模型构造算法都采用批学习，当面对大规模数据集时，计算效率较差，本文提出一种基于随机学习的稀疏模型构造算法。更具体的说，我们关注的不是某一个具体的不平衡标准，而是具有一类通用特性（如伪线性）的评价准则。文中首先将直接优化伪线性准则问题变成一个代价敏感问题。针对新问题，如果直接使用随机梯度法求解难以获得满意的稀疏度，因此提出使用COMID算法作为优化方法，确保了解的稀疏性。同时针对已有COMID算法即使是强凸目标函数，也仅能获得O(logT/T)收敛速度，给出一种基于多项式衰减的改进方法，并从理论上证明了所提新方法具有0(1/T)的最优收敛效率。不平衡基准数据集上的实验证明了本文所提算法的高效性和有效性。

目录

声明

摘要

第一章 绪论

1．1 研究背景及意义

1．2 国内外研究现状

1．3 本文的工作与安排

第二章 相关工作

2．1 二分类学习的概述

2．2 二分类的度量准则

2．2．1 传统二分类的度量准则

2．2．2 不平衡二分类的度量准则

2．3 面向不平衡二分类的改进算法

2．4 稀疏模型概述

2．5 面向不平衡准则的稀疏模型

2．6 本章小结

第三章 基于割平面法的直接优化QM稀疏模型构造算法

3．1 算法的框架和目标函数

3．2 基于割平面算法的优化求解

3．2．1 割平面算法的基本思想

3．2．2 算法的优化求解

3．3 不平衡数据集上的实验

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

3．3．2 算法参数对实验性能的影响

3．3．3 和其他算法的比较

3．4 本章小结

第四章 一种具有最优收敛速度的面向伪线性准则的稀疏随机模型构造算法

4．1 伪线性准则及特点

4．2 面向伪线性准则的稀疏随机算法

4．2．1 算法的框架

4．2．2 算法的内部优化

4．3 算法的复杂度分析

4．4 基于大规模数据集的实验

4．4．1 算法性能的比较与分析

4．4．2 算法的收敛性

4．4．3 算法稀疏度的比较与分析

4．5 本章小结

第五章 总结与展望

5．1 论文总结

5．2 未来工作的展望

参考文献

图索引

表索引

致谢

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

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