结构化数据核函数的研究

论文摘要

核函数是支持向量机中非常重要的一个研究方向,尽管在统计学习理论出现之前,核函数的概念与技术早已存在,但它在机器学习中真正的成功应用,是从支持向量机开始的。正是支持向量机与核函数技术的结合,才使得以支持向量机为代表的核机器学习得到了快速的发展和广泛的应用。本论文的所有工作正是基于支持向量机与核函数的结合而展开的,主要包括三个方面的内容:核函数的构造、核函数的实现以及核函数的应用。支持向量机的输入数据一般定义在向量空间,常用的核函数如多项式核、径向基核等都能取得很好的效果。但是,还有很多机器学习问题在解决的时候涉及到一些含有结构信息的数据（我们称为结构化数据）,如字符串和图像等,采用这些常用的核函数往往无法取得满意的效果,因为这些数据在转换成向量时将会丢失一些结构信息。因此针对这些结构化数据的核函数构造问题,已经提出了许多新型的核函数以及实现算法。本论文以结构化数据的核函数作为研究对象,提出了一些新的核函数以及它们的实现算法;并且对已有核函数的实现进行改进,降低计算复杂度;然后将一些新型字符串核函数应用于入侵检测领域。（1）核函数的构造。在归纳和总结了现有的字符串核函数的基础上,本论文将字符串核函数划分为基于序列的以及基于概率的两大类字符串核函数。基于序列的字符串核函数比较常见,包括间隙加权核以及谱核等常用的核函数。谱核没有考虑不连续的子序列对核函数的影响,而间隙加权核函数则惩罚长度较大的子序列,实际上,在有些应用中我们应该奖励长度较大的子序列,而非惩罚。在详细分析之后,本论文提出了一种基于序列的字符串核函数,叫做长度加权核函数,在这个核函数中长度越大的子序列所占的权重越大。另外,提出了一种变种——长度加权一次核函数,在这个核函数中重复出现的子序列我们只考虑一次。基于序列的字符串核只计算在两个字符串中出现的匹配子序列对核值的贡献,而没有考虑依次出现的字符之间的依赖关系。为了在核函数中体现字符之间的依赖关系,我们依据马尔可夫模型提出了基于概率的混合阶马尔可夫核函数,它也是一种字符串核函数。（2）核函数的实现。已经有许多算法用来实现字符串核函数,包括基于动态规划的、基于后缀树的以及基于后缀核的算法。在分析了后缀核的概念之后,本论文提出了一系列基于后缀核的实现算法,能够用来解决目前的间隙核函数以及本论文提出的长度加权核函数。另外,我们将位并行算法应用于核函数的实现算法中,分析表明这种处理在一定条件下能够加快定长度加权核函数的计算。为了快速实现混合阶马尔可夫核函数,本论文采用了后缀树存储结构,并利用它的匹配统计量计算混合阶马尔可夫核函数,能够在线性时间内求出核函数的值。（3）入侵检测是信息安全中很重要的一个环节。支持向量机作为一种分类算法已经被应用于基于网络的入侵检测中,但是在基于主机的入侵检测中,由于输入数据大部分为命令序列或者系统调用序列,采用常见的径向基或者多项式核函数的支持向量机并不合适。针对基于主机的入侵检测系统,我们利用训练数据构造了基于字符串核函数的1-类支持向量机,包括现有的以及本论文提出的字符串核函数,并用这个1-类支持向量机对测试数据进行测试,实验结果表明本论文提出的一些字符串核函数比现有的一些字符串核函数更加适用于基于主机的入侵检测系统。

论文目录

• 致谢
• 摘要
• Abstract
• 第一章 绪论
• 1.1 机器学习的发展
• 1.2 核机器学习
• 1.3 支持向量机
• 1.3.1 支持向量机的研究进展
• 1.3.2 支持向量机的应用
• 1.3.3 存在的问题
• 1.4 本文的主要工作
• 第二章 支持向量机
• 2.1 支持向量机
• 2.1.1 线性支持向量机
• 2.1.2 非线性支持向量机
• 2.1.3 υ-支持向量机
• 2.1.4 回归支持向量机
• 2.2 核函数
• 2.2.1 核函数的理论基础
• 2.2.2 核函数的基本数学性质
• 2.2.3 常用核函数
• 2.3 小结
• 第三章 面向结构化数据的核函数
• 3.1 引言
• 3.2 组合核
• 3.3 句法驱动核
• 3.3.1 字符串核函数
• 3.3.2 词序列核
• 3.3.3 文法树核
• 3.3.4 排序树核
• 3.4 模型驱动核
• 3.4.1 Fisher核
• 3.4.2 边界化核
• 3.5 指数核
• 3.6 小结
• 第四章 基于序列的字符串核函数
• 4.1 字符串核
• 4.2 子串核函数
• 4.2.1 谱核
• 4.2.2 失配核
• 4.3 间隙核函数
• 4.3.1 间隙加权核
• 4.3.2 长度加权核
• 4.3.3 长度加权一次核
• 4.4 基于后缀核的高效算法
• 4.4.1 间隙加权核
• 4.4.2 长度加权核
• 4.4.3 长度加权一次核
• 4.5 实验
• 4.5.1 任意字符串集合
• 4.5.2 UNM数据集
• 4.6 小结
• 第五章 基于概率的字符串核函数
• 5.1 马尔可夫核函数
• 5.1.1 马尔可夫链
• 5.1.2 马尔可夫核
• 5.2 基于后缀树的快速算法
• 5.2.1 构造后缀树
• 5.2.2 匹配统计量
• 5.2.3 计算马尔可夫核函数
• 5.3 实验
• 5.4 小结
• 第六章 基于字符串核函数的入侵检测
• 6.1 引言
• 6.2 入侵与入侵检测
• 6.3 1-类SVM技术
• 6.4 基于SVM的入侵检测系统模型
• 6.5 实验
• 6.5.1 实验数据集
• 6.5.2 UNM数据集实验
• 6.5.3 SEA数据集实验
• 6.5.4 实验结果分析
• 6.6 小结
• 第七章 结束语
• 7.1 本文工作的总结
• 7.2 进一步研究的展望
• 参考文献
• 攻读博士期间所发表的论文