（计算机应用技术专业论文）svm分类器的扩展及其应用研究.pdf

硕上学位论文 摘要 支持向量机是数据挖掘中的一项新技术 是一个理论完备 适应性强 全局 优化 泛化性能好的分类器 在若干挑战性的应用中 获得了目前为止最好的性 能 本文的主要内容是在研究经典s v m 算法的基础上 以解决实际问题 拓广 s v m 的适用范围为出发点 研究s v m 分类方法及其分类应用 从支持向量依附的理论背景出发 学习目前s v m 训练算法的研究成果 分 析它在数据挖掘中 尤其是分类算法上 的应用 并总结了支持向量机在数据挖掘 领域中实现的方向 针对其在应用中的一些局限性 揭示s v m 的分类机理 提 出了两种提高s v m 分类性能的方法 并结合垃圾邮件过滤的应用 证实了这两 种方法对分类器的性能有不同程度的提高 1 利用未标记数据提高分类器性能的研究 提出了一个解决训练样本不足的方法 该方法自动从未标记数据中挑选样本 进行标记 加入s v m 训练集 并通过设置阈值在一定程度上保证所选样本的高 分辨性 2 基于集成学习思想提高分类器性能的研究 提出一种基于集成学习的k s u 分类方法 对于支持向量机不能很好判定的样 本 采用最近邻方法判断 该最近邻算法采用支持向量集作为最近邻居集 可以 提高分类准确率 将设计的分类模型引入垃圾邮件的过滤应用 分析了垃圾邮件产生的过程 对垃圾邮件过滤的常用方法进行了总结 详细阐述了基于内容的垃圾邮件过滤技 术过程 实验表明 与直接用分类面决策的经典s v m 相比 该模型在适用的样 本规模上表现出了一定的优越性 可以在提高分类准确率的同时 降低s v m 对 核函数及其参数选择的依赖 模型虽然增加了一定的时间复杂度 但可以保证与 s v m 空间复杂度的一致性 因而是有效的 实用的模型 关键词 数据挖掘 分类挖掘 支持向量机 训练算法 核函数 s v m 分类器的扩展及其应用研究 a b s t r a c t s u p p o r tv e c t o rm a c h i n e s v m i sn e wi nd a t am i n i n g w h i c h su s u a l l yu s e da s ac l a s s i f i e rw i t hi n t a c t t h e o r yb a c k g r o u n d s t r o n ga d a p t a b i l i t y a n de x c e l l e n t g e n e r a l i z a t i o nf u n c t i o n a l s ot h eo p t i m i z a t i o ni sf o ro v e r a l ls i t u a t i o n i ns o m e c h a l l e n g e da p p l i c a t i o n sa tp r e s e n t i th a sg a i n e dt h eb e s tp e r f o r m a n c e st i l ln o w a i m e dt or e s o l v ep r a c t i c a lq u e s t i o n sa n dt o e x p a n dt h ea p p l i c a b i l i t yo fs v m t h e p r i m a r yc o n t e n to ft h i sp a p e ri s t o i m p r o v et h em e t h o do fs v mc l a s s i f i c a t i o n a l g o r i t h m i ca n dt oe x p a n di t sa p p l i c a t i o n o nt h eb a s i so fs t u d y i n gc l a s s i c a ls v m a l g o r i t h m i c s t a r t e df r o mt h eb a c k g r o u n dt h e o r yo fs v m t h i sp a p e ra n a l y s e dt h er e s e a r c h r e s u l t so fs v m t r a i n i n ga l g o r i t h m i cu n t i ln o wa n di t sa p p l i c a t i o n si nd a t am i n i n g f i e l d e s p e c i a l l yi nc l a s s i f i c a t i o na l g o r i t h m a l s ot h i sp a p e ra n a l y s e dt h ea c h i e v e d d i r e c t i o no fs v mi nd a t am i n i n gf i e l da n dr e v e a l e ds v mc l a s s i f i c a t i o ns t r a t e g y a i m e da tl o o s e n i n gt h er e s t r i c t i n ga b o u tt h ea p p l i c a t i o n so fs v m t h i sp a p e rb r o u g h t f o r w a r dt w om e t h o d st o i m p r o v es v mc l a s s i f i c a t i o np e r f o r m a n c e s i th a sb e e n c o n f i r m e dt h a tt h e s et w om e t h o d sh a di m p r o v e dt h ec l a s s i f i c a t i o np e r f o r m a n c e si n t h ea p p l i c a t i o no fs p a m e m a i lf i l t r a t i o ni ns o m ed e g r e e 1 m a k i n gu s eo ft h eu n m a r k e dd a t at oi m p r o v ec l a s s i f i c a t i o np e r f o r m a n c e i tb r o u g h tf o r w a r dam e t h o di nt h es i t u a t i o no fi n s u f f i c i e n tt r a i n i n gs a m p l e s i t c h o s es a m p l ed a t at om a r kc l a s sl a b e l sv o l u n t a r i l y a n dt h e na d d e dt ot h es v m t r a i n i n gs e t b ys e t t i n gt h r e s h o l dv a l u e i tm a d es u r et h a tt h ec h o s e ns a m p l e sh a v e h i g hv a l i d i t y 2 i m p r o v i n gc l a s s i f i c a t i o np e r f o r m a n c eb a s e do nt h et h o u g h to fi n t e g r a t e d l e a r n i n g i t b r o u g h tf o r w a r dam e t h o dc a l l e dk s ub a s e do ni n t e g r a t e dl e a r n i n g t h e o p t i m i z a t i o nc l a s s i f i c a t i o ns u r f a c ec o u l dn o tg i v eav e r yg o o dc a t e g o r yd e c i s i o nt o s o m es a m p l e s s ow eu s e dk n e a r e s t n e i g h b o rm e t h o da sa na i da n du s e dt h e s u p p o r tv e c t o r sa s c e r t a i n e db ys v ma sk n e a r e s t n e i g h b o rt r a i n i n gs e t t h i s m e t h o dc a ni m p r o v et h ec l a s s i f i c a t i o na c c u r a t er a t e u s i n gt h i sc l a s s i f i c a t i o nm o d e lf o rs p a m e m a i lf i l t r a t i o n t h i sp a p e ra n a l y s e d w h ys p a me m a i l se x i s t e d s u m m a r i z e dt h eu s u a lm e t h o d sf o rs p a m e m a i lf i l t r a t i o n a n de x p o u n d e dd e t a i l e d l yt h ep r o c e d u r eo fs p a m e m a i lf i l t r a t i o nm e t h o d sb a s e do n h i 硕士学位论文 w e bc o n t e n t c o m p a r e dw i t hc l a s s i c a ls v mt h a tm a k e dd e c i s i o no n l y b yt h e o p t i m i z a t i o nc l a s s i f i c a t i o ns u r f a c e t h ee x p e r i m e n ti n d i c a t e dt h a tt h i sm e t h o dh a d s h o w ne n o u g hs u p e r i o r i t yi nt h es a m p l e ss c a l es u i t a b l ef o ru s e a n di tw a sv e r y o b v i o u st h a ti th a db e e nb e t t e ri n i m p r o v i n ga c c u r a t e r a t ea n dr e d u c i n gt h e s e n s i b i l i t yt ok e r n e la n dt ot h ep a r a m e t e r so fs v m t h i sm o d e li n c r e a s e dt h et i m e c o m p l i c a c yt o al i t t l e d e g r e e b u ti t c o u l da s s u r et h es a m es p a c ec o m p l i c a c ya s c l a s s i c a ls v m a c c o r d i n g l y i t se f f i c i e n ta n dp r a c t i c a l k e yw o r d s d a t am i n i n g c l a s s i f i c a t i o n s v m t r a i n i n ga l g o r i t h m i c k e r n e lf u n c t i o n i v s v m 分类器的扩展及j 应用研究 插图索引 图2 1 知识发现过程图 7 图2 2 模式与数据的关系图 一8 图3 1 结构风险最小化示意图 2 0 图3 2s v m 线性分类模型图 一2 3 图3 3s v m 高维分类模型图 2 3 图4 1n 个支持向量的非线性变换 2 6 图4 2s v m 分类预测过程图 3 4 图4 3 联合分类流程图 3 4 图4 4 训练过程子系统 3 5 图4 5 分类过程子系统 3 6 图4 6 运行流程图 一3 6 图4 7 载入训练集选择核参数进行训练 3 7 图4 8 训练得到分类模型 3 7 图4 9 保存训练模型 3 7 图4 1 0 选择模型进行预测 3 7 图4 1 1 读出模型分类规则 3 8 图4 1 2 预测测试集 一3 8 图5 1 电子邮件传输机制 4 0 图5 2 电子邮件头信息图 4 1 图5 3s v m 与k s u 在不同大小训练集下的准确率比较图 4 5 v 硕一f 学位论文 附表索引 表2 1 人工与数据挖掘解决问题步骤比较 1 0 表2 2 分类模型优缺点比较 一1 5 表5 1 u t i 练样本大小对s v m 分类准确率的影响 4 4 表5 2 不同核函数模型下s v m 和k s u 分类准确率比较 4 5 v i 湖南大学 学位论文原创性声明 本人郑重声明 所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果 除了文中特别加以标注引用的内容外 本论文不包含任 何其他个人或集体已经发表或撰写的成果作品 对本文的研究做出重要贡 献的个人和集体 均已在文中以明确方式标明 本人完全意识到本声明的 法律后果由本人承担 作者签名 哥点 日期 v 0 8 年罗月to 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留 使用学位论文的规定 同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版 允许论文 被查阅和借阅 本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索 可以采用影印 缩印或扫描等复制手段保存和汇 编本学位论文 本学位论文属于 1 保密口 在年解密后适用本授权书 2 不保密团 请在以上相应方框内打 作者签名 导师签名 露燕 匈p p 日期 加d g 年岁月sb 日 日期 o2 年厂月 日 硕十学位论文 第1 章绪论 1 1 研究背景及意义 由于计算机和信息技术的快速发展 大量数据能得到妥善保存和管理 这些 数据通常都来自某领域或系统的原始信息积累 有效分析这些历史数据 获取该 领域数据分布的规律 可以指导未来决策 然而 存放在大型和大量数据库中的 海量历史数据 没有强有力的工具 理解它们已经远远超出了人的能力 如何从 这些数据中发掘出有效的信息 这种挖掘信息的需要带来了对强有力的数据分析 工具的需求 数据挖掘 d a t am i n i n g d m 技术在这种背景下应运而生 对数据挖 掘的相关领域的研究 例如数据分类 聚类 函数模拟和规则抽取等技术 逐渐 成为当前计算机基础技术研究的重心之一 数据挖掘一词首次出现在1 9 8 9 年8 月举行的第1 1 届国际联合人工智能学术会 议上 近年来 其研究重点逐渐从发现方法转向系统应用 并且注重多种学科之 间的相互渗透 许多内容的专题会议也常把数据挖掘列为议题之一 成为当前计 算机科学界的一大热点 从目前的现状看 数据挖掘的研究仍然处于广泛研究和 探索阶段 一批具有挑战性和前瞻性的问题被提出 吸引越来越多的研究者 数据挖掘技术逐渐成熟 要有更多的接受者 数据挖掘必须和现存商业技术 相结合 目前已经有很多通用的数据挖掘系统 但是这些系统都趋向于提供适用 于各种商业应用的横向解决方案 而不是针对某个特定商业应用的解决方案 许 多数据挖掘研究者和开发者相信 数据挖掘比较有前途的方向是创建能够提供纵 向解决方案的数据挖掘系统 在对数据进行分析前 往往必须先对混淆在一起的各种数据进行分类 海量 数据的人工分类显然不能满足数据挖掘技术的要求 而且也不切实际 数据自动 分类技术作为数据挖掘的一个研究领域 在统计学 机器学习 神经网络和专家 系统中得到了较早的研究 到目前为止 已经研究的经典分类方法主要包括 决 策树方法 神经网络方法 遗传算法 贝叶斯分类 k 近邻算法和基于案例的推 理 粗糙集方法 模糊集方法和支持向量机是较新的分类方法 支持向量机 s u p p o r tv e c t o rm a c h i n e s v m 方法是新近提出的一种数据分类 方法 由于其独立的理论背景和特别的分类思想 能解决目前很多分类算法不能 解决的问题 所以一经提出 便引起广泛关注 支持向量机是数学规划理论在数 据管理中的应用 是一种优秀的机器学习算法 其本质是数学规划中的凸二次规 划问题 它建立在统计学习理论的v c 维理论和结构风险最小原理 s r m 基础上 s v m 分类器的扩展及其应用研究 如何准确 快速求解凸二次规划是支持向量机研究的基本问题 而这一问题的解 决与数学规划中的优化理论密切相关 在数学规划中 凸二次规划问题所求的局 部最优解就是全局最优解 这使得支持向量机具有很强的泛化能力 支持向量机应用于分类数据挖掘 目前还处于不断发展阶段 其严格的泛化 性理论指导和核函数强大的非线性映射能力使支持向量机和神经网络一样 具有 逼近任意连续有界非线性函数的能力 并且它还具有神经网络所不具有的许多优 点 如泛化能力强 学习问题不存在局部极小 可以自动确定学习机的结构 不 存在维数灾难等 由于这些优点 基于支持向量机的数据挖掘技术已经受到了数 据挖掘界的重视 对它的研究不断深入 支持向量机方法又称为核方法 这是因 为核的展开和计算是这 方法的关键 但核函数的嵌入也成为支持向量机方法应 用的缺点 如核函数选择缺乏理论指导 算法参数难以选择等 从本质上讲 s v m 是将理论上的风险进行了转移 它所获得的坚实的理论基础是以增加算法 参数选择难度为代价的 这给s v m 在实际应用的推广带来了困难 如何得到合 适且有效的核函数及其参数是采用支持向量机算法进行数据挖掘一个需要不断 探索的问题 目前 支持向量机已被成功地应用于函数模拟 模式识别和数据分类等领域 并取得了好的效果 同时 对于一些支持向量机尚不能解决或很好解决的问题 受到研究者的重视 这个方向上的突破会引起数据分类技术长足的进步 支持向 量机已成为国际人工智能领域和机器学习领域的新的研究热点 在美国科学杂志 上 支持向量机以及核学习方法被认为是 机器学习领域非常流行的方法和成功 的例子 并是一个十分令人瞩目的发展方向 本文对分类挖掘从理论基础 系统结构 模型构建等方面进行了较系统地研 究 对目前存在的分类算法进行分析比较 然后详细阐述了统计学习理论及结构 风险最小化原则 基于最大间隔分类超平面 对s v m 算法进行了理论推导 并 分析了s v m 作为一种新的分类方法所具有的优势 在此基础上 研究了把s v m 应用于数据挖掘分类任务时需解决的问题 如适用于大数据集训练的选块算法 分解算法和序列最小化算法 针对支持向量应用于分类应用的一些局限性 从训 练过程和分类过程两个阶段 对s v m 分类算法进行改进 提高分类性能 本文通过研究分类挖掘的模型表示 模型评价和算法的具体实施 希望提供 一个性能优秀 实用性强的基于s v m 的分类模型和算法 运用计算机编程的知 识对其进行验证 仿真实验结果 本文的意义在于 提出一种基于集成方法分类思想的s v m 分类算法 提高 分类性能 提出一种解决训练样本不足的半监督分类方法 与经典支持向量机相 比 本文研究的方法有较好的分类性能 是对s v m 分类方法的一个有效扩展 硕上学位论文 1 2 国内外研究现状 首先 支持向量机的理论发展经历了一个不断完善的过程 支持向量机的核 心内容从1 9 9 2 年才开始提出 是到目前为止统计学习理论最成功的实现 目前 仍处于不断发展阶段 虽然支持向量机发展时间很短 但是由于它的产生是基于 统计学习理论的 因此具有坚实的理论基础 近几年涌现出的大量的理论研究成 果 更为其应用研究奠定了坚实基础 a n t h o n ye ta l 1 9 9 1 等人给出了关于硬邻域支持向量机学习误差的严格理论 界限乜1 s h a w e t a y l o r 2 0 0 0 和c r i s t i a n i n i 2 0 0 0 也给出了类似的关于软邻域支持 向量机和回归情况下的误差界限n 1 w e s t o ne ta 1 1 9 9 9 h 1 和v a p n i k 等研究 了支持向量机的泛化性能及其在多值分类和回归问题的扩展问题等 s m o l a 和 s c h o e l k o p f 1 9 9 8 3 提出了支持向量机一般意义下的损失函数数学描述 在训练算法方面 支持向量机的最终求解问题归结为一个有约束的二次型规 划问题 可以利用标准二次型优化技术来求解这个优化问题 如牛顿法 共扼梯 度法 内点法等 但是 这些方法只适合小样本情况 当样本数目较大时 算法 复杂度会急剧增加 而且占用极大的系统内存 为降低计算资源 提高算法效率 已经提出许多针对大规模样本集的训练算法 1 9 9 5 年 c o r t e sa n dv a p n i k 给出了 一种求解支持向量机二次规划问题的分块算法n 们 1 9 9 7 年 o s u n a 提出了子集选 择算法 加快了支持向量机的训练速度n 引 1 9 9 9 年 j o a c h i m s 提出一种称为 s v m l i g h t 支持向量机分解学习算法n 该算法实际上是子集选择算法的推广 1 9 9 8 年 p l a t 提出了更为有效的支持向量机训练算法 即序列最小优化算法n8 2 0 0 1 年 c a u w e n b e r g h s 提出了一种增量减量式学习方法阳1 现今为止 训练算法 的优化仍是值得研究的一个方向 对核函数的构造和参数的选择理论研究 基于各个不同的应用领域 可以构 造不同的核函数 能够或多或少的引入领域知识 现在核函数广泛应用的类型有 多项式逼近 贝叶斯分类器 径向基函数 多层感知器 而参数的选择现在大多 利用交叉验证的方法来确认 随着支持向量机理论上深入研究 针对应用需求的不同 出现了许多变种支 持向量机 1 模糊支持向量机 引入样本对类别的隶属度函数 这样每个样本对于类 别的影响是不同的 这种理论的应用提高了s v m 的抗噪声的能力 尤其适合在 未能完全揭示输入样本特性的情况下 2 最小二乘支持向量机 这种方法是在1 9 9 9 年提出 经过这几年的发展 已经应用到很多相关的领域 研究的问题已经推广到对于大规模数据集的处理 处理数据的鲁棒性 参数调节和选择问题 训练和仿真 s v m 分类器的扩展及 应用研究 3 加权支持向量机 包括有偏样本的加权 有偏风险加权 4 主动学习的支持向量机 主动学习在学习过程中可以根据学习进程 选 择最有利于分类器性能的样本来进一步训练分类器 能有效地减少评价样本的数 量 也就是通过某种标准对样本对分类的有效性进行排序 然后选择有效样本来 训练支持向量机 5 粗糙集与支持向量机的结合 首先利用粗糙集理论对数据的属性进行约 简 能在某种程度上减少支持向量机求解计算量 6 基于决策树的支持向量机 对于多类问题 采用二岔树将要分类的样本 集构造出一系列的两类问题 每个两类构造一个s v m 7 分级聚类的支持向量机 基于分级聚类和决策树思想构建多类s v m 使 用分级聚类的方法 可以先把n 1 个距离较近的类别结合起来 暂时看作一类 把剩下的一类作为单独的一类 用s v m 分类 分类后的下一步不再考虑这单独 的一类 而只研究所合并的n 1 类 再依次下去 支持向量机的研究与发展是一个不断进化的过程 目前难于解决的问题主要 有以下几个方面 一方面 由于支持向量机找到的是全局最优解 因此 在很多问题上它都有 着其它统计学习技术所难以比拟的优越性 并已在一些领域获得了成功 但是 作为一种尚未成熟的新技术 支持向量机目前仍然存在着很多局限 最大的局限 就在于核函数的选择 由于在核确定之后 用户只能对参数c 进行调整 因此 核的选择对于支持向量机的性能非常重要 目前已有一些研究者对利用先验知识 限制核的选择进行了研究 但如何针对特定问题选择最佳的核仍是一个难以解决 的问题 另一方面 支持向量机的训练速度极大地受到训练规模的影响 对于超大规 模的数据集 比如数百万支持向量 如何高效地进行训练和测试也是一个需要研 究的重要问题n 8 1 此外 支持向量机对二类分划问题已经解决得非常好 但其对多类划分问题 及回归问题的处理能力仍有待进一步研究和改善h 朝 因此 目前对于支持向量机的学习研究 主要集中在如下的几个主要方向 1 提高支持向量机的分类准确率的研究 分类准确率一直是各种分类算法的研究重点 怎样通过各种技术提高支持向 量的分类准确率是很多研究者都在考虑的问题 研究方向主要有核函数构造和参 数选择的优化方法的探索 数据预处理 样本的重要度 属性的重要度 特征选 择等 方面方法的结合 将数据中脱离领域知识的信息 即数据本身的性质融入 支持向量机的算法中从而产生新的算法 以及支持向量机训练算法的探索等 卜 硕士学位论文 2 减少支持向量机对数据集的约束的研究 支持向量机可以较好地解决小样本 高维数据分类问题 但是数据集的分布 对分类效果的影响同样是存在的 支持向量机计算的复杂性依赖于支持向量的数 目 因此减少支持向量的数目成为一个重要的研究课题 对数据集的约束的减少 会扩大支持向量机方法的应用范围 另外 支持向量机从两类问题向多类问题的 推广也是这类研究的一个方向 3 支持向量机技术与其他技术的结合的研究 在知识发现中 不可能用一种方法处理所有的数据集 完成各种数据挖掘任 务 需要研究同其它方法相结合的问题 以提高处理效率和精度 例如s v m 和 决策树方法相结合可以用于多层分类 4 支持向量机技术的软件实现 将支持向量机技术软件化一直是其研究方向之一 如何开发出功能更加强 大 使用更加方便 界面更加友好的软件以实现支持向量机技术 是一个需要努 力的方向 以上是对s v m 的本身性质的研究 在加大s v m 应用研究方面 s v m 以及相 应的核方法已经越来越成为国际上数据挖掘领域如分类 回归 奇异探测等的流 行方法 国际上已经有很多关于s v m 的研究报道 s v m 在很多方面都有成功应 用实例 如粒子鉴定 脸谱识别 文本分类 生物信息 商用数据库等 在短短 的时间里取得令人瞩目的研究成果 1 3 本文主要研究内容和结构安排 1 3 1 本文主要研究内容 本文首先对本课题的研究背景和国内外研究现状进行了综述 然后介绍了数 据挖掘的过程和相关基本概念 对分类技术做了详尽的学习研究 在此基础上对 目前主要的分类模型进行了比较分析 分析了统计学习理论的学习原理 探讨了 s v m 分类方法的分类机理和特点 提出了两种提高分类性能 扩展s v m 分类应 用的方法 设计了算法系统 并将其应用于垃圾邮件过滤的模型中 从理论和实 验上验证了算法可行性和有效性 本文所做的主要工作包括 1 对本课题的研究背景和国内外研究现状进行了综述 然后介绍了数据挖 掘技术的理论基础和相关基本概念 对依赖于数据挖掘理论基础的分类技术进行 了深入地研究 探讨了基于机器学习分类技术的内涵 外延 以及模型的数学机 理 对目前存在的常用分类模型进行了分析和比较 s v m 分类器的扩展及j e 心用研究 2 对支持向量分类依赖的统计学习理论 支持向量分类思想 模型 性能 指标以及目前还不能解决的问题进行了深入剖析 3 针对统计学习理论本身带来的支持向量分类不能解决的难题 结合目前 热门的集成分类思想 提出了提高分类准确率和弱化模型参数敏感性的分类算 法 并设计了算法系统 从理论和实验上验证了算法可行性和有效性 4 提出利用未标记数据提高s v m 分类性能的方法 该方法设计算法从大量 未标记数据中挑选相似度高 区别度较大的数据加入s v m 训练集 从而解决人 工标记训练样本不足的问题 实验表明 该方法能在一定程度上提高s v m 的分 类性能 加快学习速度 5 介绍了垃圾邮件过滤的原理以及目前采用的方法 结合 3 4 对垃圾邮 件过滤方法进行改进 实验表明 3 4 所给出的方法能有效应用于垃圾邮件过 滤的应用 1 3 2 本文结构安排 本文结构安排如下 第一章为绪论 阐述了本文的研究背景及意义 综述了与本研究课题相关技 术的国内外研究现状 简述了本文的主要研究内容 第二章介绍了数据挖掘有关的基础理论 包括数据挖掘的起源 数据挖掘任 务 功能以及数据挖掘过程 对数据挖掘中分类技术的一般概念 数学机理 内 涵以及外延进行了归纳学习 介绍了目前主要的分类技术 算法性能评价标准 对介绍的几种算法进行了比较分析 第三章深入剖析支持向量机 重点分析了统计学习理论 支持向量分类思想 和模型 对支持向量的性能指标和目前还没有解决的问题进行了归纳总结 为后 续算法研究提供理论基础 第四章对基于s v m 的分类技术展开研究 针对统计学习理论本身带来的支 持向量分类不能解决的难题 提出两种提高分类性能的方法 一方面结合集成学 习分类思想 提出了提高分类准确率和弱化模型参数敏感性的分类算法 另一方 面针对训练样本不足影响s v m 分类性能的问题 提出利用未标记数据提高分类 性能的方法 并设计了算法系统 从理论和实验上验证了算法可行性和有效性 第五章分析垃圾邮件存在的原理和目前垃圾邮件过滤的主要方法 对本文设 计改进的模型进行分析并应用于垃圾邮件过滤 对算法的性能进行了验证和分 析 最后是结论 对全文的内容进行了总结 并展望了下一步的工作 6 硕士学位论文 第2 章用于数据挖掘的分类挖掘 2 1 知识发现 知识发现 k d d 是从数据中发现有用知识的整个过程 数据挖掘是知识发现 过程中的 个特定步骤 它用专门算法从数据中抽取新的 可能有用的和最终可 理解的模式 该过程首先要确定挖掘的任务或目的 确定了挖掘任务后 就要决 定使用什么样的挖掘算法 选择了算法后就可以实施数据挖掘操作 获取有用的 模式 k d d 过程是多个步骤相互连接 反复进行人机交互的过程 包括 1 1 学习某个应用领域 包括应用中的预先知识和目标 f 2 建立目标数据集 选择一个数据集或在多数据集的子集上聚焦 3 数据预处理 去除噪声或无关数据 去除空白数据域 考虑时间顺序和 数据变化等 4 数据转换 找到数据的特征表示 用维变换或转换方法减少有效变量的 数目或找到数据的不变式 5 选定数据挖掘功能 决定数据挖掘的目的 6 选定数据挖掘算法 用k d d 过程中的准则 选择某个特定数据挖掘算法 如汇总 分类 回归 聚类等 用于搜索数据中的模式 7 数据挖掘 搜索或产生一个特定的感兴趣的模式或一个特定的数据集 8 解释 解释某个发现的模式 去掉多余的不切题意的模式 转换某个有 用的模式 以使用户明白 f 9 发现知识 把这些知识结合到运行系统中 获得这些知识的作用或证明 这些知识 用预先 可信的知识检查和解决知识中可能的矛盾 整个过程如下 图2 1 知识发现过程图 s v m 分类器的扩腱及其应用研究 数据挖掘是k d d 最核心的部分 数据挖掘与传统统计分析工具不同的是数 据挖掘使用的是基于发现的方法 运用模式匹配和其它算法决定数据之间的重要 联系 而传统的统计学分析方法是建立在一定的假设之上的 假设的存在在一定 程度上限制了它的应用范围 另外 当数据量大时 数据挖掘相对统计学的优势 就会比较突出了 比如在计算速度和发现问题上 但是 数据挖掘并没有完全排 斥统计学 还是把统计学当中许多方法应用到数据挖掘当中 比如聚类 回归 时间序列等等 数据挖掘是一个集统计学 人工智能 模式识别 计算机科学 机器学习等多种学科为一体的产物 不仅是数据库系统和机器学习研究的重要课 题 还是孕育了巨大的商业前景的重要领域 2 2 数据挖掘 在工业和科研领域 各种各样的数据正以几何级增长 然而 在所存储的数 据中只有不到1 0 被拿出来进行分析 因为获取和存储这些数据比较容易 代 价也不高 而要很好地利用如此大量的数据却是困难的 代价也较高 很多时候我们又需要很快从海量数据中得到分析结果 手工分析不现实 因 此发现一些新工具和新方法来辅助人们从数据库中发现有用知识成为必需 这些 新工具和新方法就是数据挖掘所要研究的问题 数据挖掘 指的是从大型数据库或数据仓库中提取人们感兴趣的知识 这些 知识是隐含的 事先未知的潜在有用信息 如果能把这些信息从数据库中抽取出 来 将创造很多潜在的利润 数据挖掘是一个高级的处理过程 它从数据集中识 别出以模式来表示的知识 高级的处理过程是指一个多步骤的处理过程 多步骤 之间相互影响 反复调整 形成一种螺旋式上升过程 数据挖掘算法的好坏将直接影响到所发现知识的好坏 数据挖掘的任务是从 数据中发现模式 模式是一个用语言l 来表示的一个表达式e 它可用来描述数 据集f 中数据的特性 e 所描述的数据是集合f 的一个子集f e e 作为一个模 式要求它比列举数据子集f e 中所有元素的描述方法简单 图2 2 模式与数据的关系图 硕十学位论文 模式按功能可分为两大类 预测型模式和描述型模式 第一种预测型模式 通过对数据的分析处理 估计数据库中某些丢失数据的 可能值或某个属性值的分布情况 有以下方法 统计分析 主要用线性或非线性 回归模型和分类分析方法抽取属性间的依赖关系 关联分析 数据关联是数据库 中存在的一类重要的知识 若两个或多个属性的取值间存在某种规律性 就称为 关联 利用关联可预测目标属性值 关联分析的目的在于发现大型数据库中的关 联网 决策树 一个有根的二叉树 每个内部节点包含对条件属性的测试 数据 元组经过内部节点的循环测试 最终到达叶节点 到达同一个叶节点的所有数据 元组属性取相同值作为预测值 回归树 一个有根二叉树 每个内部节点包含用 关系数据库查询语言s q l 表达的条件属性测试 叶节点的属性平均值作为数字 目标属性的预测值 第二种描述型模式 分类 就是找出代表这类数据整体信息的内涵描述 这 种描述有两种 特征化描述和区别性描述 特征化描述反映目标数据的共同特性 区别性描述反映不同类或一个类之间数据的区别 回归分析 发现数据与实变量 之间的映象函数 及成员间的函数关系 聚集 识别一组聚集规则 将对象分组 构成相似对象类 聚集分析在统计 机器学习 空间数据库 数据采掘等领域中 己有不同侧重的研究 聚集分析方法主要基于可能性分析 概括 寻找数据子集 的简洁描述 采用关联规则 图表 表格等 构造依赖关系 构造变量间函数依 赖关系或相关关系的模型 偏差分析 偏差包括很大一类潜在有趣的知识 如结 果与期望的偏离 反常实例等 偏差分析的基本思想是寻找结果 如模式 与参照 值 如预测值或标准值 的差别 模式发现 空间数据库的两类相似模式采掘查询 为 对象相似查询和元素对相似查询 时间数据阵也有两类相似查询 完全匹配 和子序列匹配 路径发现 分布信息环境中 文档和对象通过连接便于用户存取 理解用户存取模式不仅有助于改进系统设计 而且有助于做出更好的市场决策 捕捉用户存取的模式称为路径模式采掘 在实际应用中 往往根据模式的实际作用细分为以下6 种 分类模式 回归 模式 时间序列模式 聚类模式 关联模式 序列模式 数据挖掘的过程与人类问题求解的过程是存在巨大相似性的 具体比较见 表2 1 挖掘过程可能需要多次的循环反复 每一个步骤一旦与预期目标不符 都要回到前面的步骤 重新调整 重新执行 s v m 分类器的扩展及 e 应用研究 表2 1 人工与数据挖掘解决问题步骤比较 人工解决问题数据挖掘 定义问题定义问题 收集实例 获取历史数据 分析实例性质处理数据 归纳总结 分析潜在的解设计模型 验证解的普遍性 验证模型 分析目标定义目标 评估所有解 确定最优解优化问题 找出问题的解 2 3 分类挖掘 2 3 1 分类问题的内涵 分类是一类重要的数据挖掘问题 分类技术在很多领域都有应用 例如可以 通过客户分类构造一个分类模型来对银行贷款进行风险评估 当前的市场营销中 很重要的一个特点是强调客户细分 客户类别分析的功能也在于此 采用数据挖 掘中的分类技术 可以将客户分成不同的类别 比如呼叫中心设计时可以分为 呼叫频繁的客户 偶然大量呼叫的客户 稳定呼叫的客户 其他 帮助呼叫中心 寻找出这些不同种类客户之间的特彳正 这样的分类模型可以让用户了解不同行为 类别客户的分布特征 其他分类应用如文献检索和搜索引擎中的自动文本分类技 术 安全领域有基于分类技术的入侵检测等等 机器学习 专家系统 统计学和神经网络等领域的研究人员已经提出了许多 具体的分类预测方法 但分类预测的流程都包括下面几个步骤 训练 训练集 特征选取 训练 分类器 分类 新样本 特征选取 分类 判决 其中 训练集通常是以往的一些经验数据 是一条条的数据库记录组成的 一条记录就是一个训练样本 训练集的每个样本还有一个特定的类标签与之对 应 样本包含若干条属性 或称为特征 组成一个特征向量 一个具体样本的形 式可以描述为样本向量 c 1 c 2 c m d 在这里c i 是字段值表示特征属性 d 是 类标签标记类别 分类就是 通过对训练集的学习 用样本的特征属性建立一个划分类别属性 的模型 也就是分类器训练过程 然后用测试集来评价模型的准确率 也称为分 类器的测试 达到测试标准的模型便可以对新数据进行分类 这个过程实际上是 将训练数据间的共性与个性具体化 形式化 并给出一个确定的 可操作的描述 硕上学位论文 这个训练和测试的过程被称为分类器构造 在分类器构造中 测试只是一个评估的过程 而训练是最为重要的 分类的 目的是 分析输入数据 通过训练集中的数据表现出来的特性 为每一个类找到 一种准确的描述或者模型 这种描述常常用谓词表示 由此生成的类描述用来对 未来的测试数据进行分类 尽管这些未来的测试数据的类标签是未知的 我们仍 可以由此预测这些新数据所属的类 该过程是一个预测过程 而不能肯定预测结 果的准确性 通过分析每类数据的特征 可以对数据中的每一个类有更好的理解 从实质上说 我们是获得了对这个类的知识 2 3 2 分类的数学机理 从更深入的观点来看 分类器构造的方法是通过对训练集中样本数据的学 习 尽可能从中得到事先未知的 隐藏于数据中的规律 即分类器判别函数 然 后选定一种带有参数的模型函数 通过学习确定模型函数的参数 用它来直接或 间接地拟合或逼近分类判别函数 这一过程就是分类器的训练 从数学上讲 就是在分类判别函数 事先未知的情况下 利用含有n 个样本 m 个属性c i 的训练集 i c i c 2 c m d i 1 2 n 构造一个特征域空间 c l c 2 c m 到类别域 d 空间的映射 模型函数g 来拟合或逼近类判别函数厂 实际上可以用数学中泛函的观点来统一的看待分类问题 设x 是一个无限 维赋范函数空间 分类判别函数厂e x 有限维真子空间gcx 分类器的训练 就是在子空间g 中找至l j g g 使得 i i 厂一g 幸l i m i n 脚0 一9 0 2 1 这里0i i 是函数空间x 的范数 在分类的相关研究中 一个重要的方向就是不断 提出各种分类器构造的方法模型 目前为止 国内外已有很多分类器构造的方法模型 实际上 一种分类器构 造的方法模型就对应着一个有限维真子空间g 由相关的泛函分析知识可以得 到 如果我们适当地选择模型 使得厂 g 那么g i 这时 i i 厂一g 木i l 叠o 说 明一种好的模型可以在理论上保证分类判别函数厂可以被毫无误差的拟合 正因 为如此 国内外的学者才会不断提出新的模型 以便能够得到更好的分类器构造 方法 实际上这些研究就是不断给出新的真子空间g 和它们的生成方法 另外 由于赋范函数空间是无限维的 而真子空间g 是有限维的 因此 根 据泛函分析的知识可以知道 不可能存在一个g 使得v 厂 x 厂e g 这说明不 可能有一个一劳永逸的模型 在各种类型的数据集上的分类结果均好于其他的模 型 这也就说明了为什么很多学者的实验显示 几乎所有的分类器构造算法 在 精度上都只是适用于某些类别的数据 而在另一些类型的数据上效果不佳 s v m 分类器的扩展及其应用研究 2 3 3 分类模型的特性 分类判别函数有一个最基本的要求 它必须具有光滑性 至少应该是分段光 滑的 光滑性意味着 若两个样本只有微小差异 它们在类别上就没有本质区别 光滑性比连续性的要求要高 只有分类判别函数满足光滑性的要求 才能使得一 个样本的类别可以由另一些差别不大的样本来刻画 因此 光滑性等价于要求分 类判别函数不是 局部 的 而是具有某种整体性 一个映射 若它每个点的取值只由该点自己决定 而与其它点无关 则称该 映射是完全局部的 若一个分类判别函数是完全局部的 那么每个样本点的类别 只能由它自己决定 因此这样的函数是没有办法拟合或逼近的 实际上 讨论这 样的分类判别函数是没有意义的 因为从某种程度上说 它是任意给定的 在理 想的情况下 所有样本数据的类别完全由分类判别函数决定 分类就是在分类判 别函数未知的情况下 利用模型函数对分段光滑的分类判别函数的拟合或逼近 2 3 4 分类问题的外延 2 3 4 1 特征选择 分类判断的一个前提 是要求有建立分类模型的历史数据 通过分析这些历 史数据的特征属性 得出对其它数据进行预测的判定条件 因此 这些数据特征 属性能很好地表达每个类别数据的特征是至关重要的 几个特征高度线性相关 甚至就是一个特征多次重复地出现 这些特征实际上取其一即可 其他的特征就 是冗余的特征 而无关特征通常理解为 该特征和类别是随机关系 即和类别是 无关的 冗余和无关特征会极大地影响分类器构造的效率和精度 必须删除 采 用某种方法找到这些冗余和无关特征的过程被称为特征选择 当特征域空间 c l c 2 c n 的维数很高 即样本含有大量的特征时 将会导致 1 过多的特征使得训练集的数据量过大 分类器构造算法的训练时间过长 减慢挖掘过程 2 过多的特征使得训练集的维数过高 经训练得到的分类器是数值不稳定 的 因此分类器的分类准确率会显著降低 3 1 1 i 练集特征过多 训练后的分类器得出的分类规则的前件过于冗长 不 容易理解 因此 当训练集中的样本包含很多特征时 光研究分类器构造本身还不足以 解决问题 还要涉及到特征选择的问题 特征选择问题是分类问题的一个重要研 究领域 特别是当面对复杂的基因数据库中的知识