论文部分内容阅读
近年来,随着现代计算机技术的高速发展,在科学研究和社会生活等各个领域中积累了大量的数据,为各种不同应用提供了重要的支持。与此同时如何从这些数据中发现更多的有用信息也成为人们的一个迫切需求,数据挖掘和机器学习的出现很好地满足了这一需求。作为数据挖掘中的一个基本方法:分类学习已经引起广大科研工作者的关注,而二分类更是由于其广泛的应用基础成为其中的研究重点,但是在真实的应用中,很多二分类场景都是不平衡的,已有的平衡二分类算法难以直接使用,对此,近些年人们提出研究面向不平衡数据集的二分类算法,其基本思路分为面向数据的改进和面向算法的改进;而后者更是由于不需要对数据做预处理成为当前研究的重点。本文就是在此基础上,以SVM为工具,重点研究了基于结构化SVM的不平衡二分类算法,文中首先介绍了基于SVM的二分类算法以及不平衡二分类的应用背景,然后分析了不平衡二分类算法的研究现状,并在此基础上提出采用基于直接优化不平衡准则的方法来构造面向不平衡数据的改进SVM算法。不同于已有基于SVM的改进算法,本文提出将不平衡二分类问题看成一个学习分类队列的过程,并提出使用结构化SVM进行求解。本文的主要工作有:(1)针对AM,QM等不平衡评价准则,提出使用基于n-slack的结构化SVM作为算法框架,并定义了面向AM和QM的目标函数。针对目标函数的非光滑难以直接优化,提出使用割平面算法进行求解,使得算法的迭代次数为o(1/s2),其中ε为允许的错误。同时针对AM,QM算法内部“寻找最大最违约”子过程,分别设计了两个高效的算法,其时间复杂度均仅为o(mlogm)。不平衡数据集上的实验表明:所提算法不仅明显优于传统SVM算法,且相比起面向数据的改进算法也更加有效。(2)针对GTP/PR评估标准,提出一个基于1-slack结构化SVM的直接优化算法。算法首先定义了面向GTP/PR的目标函数,该目标比已有面向F1的目标函数更紧凑,针对新目标函数非光滑,提出使用基于1-slack的割平面算法进行求解,使得算法的迭代次数仅为o(1/ε),也更适合大规模的应用场景。面向大规模不平衡数据集的实验结果表明,所提算法不仅优于已有其他的改进算法,且算法的效率更加高效。