（计算机应用技术专业论文）基于支持向量机的数据挖掘.pdf

摘要 随着计算机技术特别是数据库技术的迅猛发展，以及人类活动范围的 扩展、 生活节奏的加快， 人们能以更快速更容易更廉价的方式获取和存储数据， 这就使 得数据及其信息量以指数方式增长。 面对这些极度膨胀的数据， 人们受到“ 信息 爆炸”和 “ 数据过剩”( d a t a g l u t )的巨大压力。这些海量数据如果不能有效利 用起来，将只会成为 “ 数据垃圾” 。对人类社会进步起到巨大作用的是知识。数 据挖掘就是从大量数据中发现潜在规律、提取有用知识的方法和技术。 数据挖掘包含的内容很多， 其中 很重要的一个方面是分类规则 挖掘。 分 类规 则挖掘可以根据训练数据， 利用适当的算法训练出分类器， 从而对新的未知样本 作出 预测。 支持向量机是基于统计学习理论的一种新的分类方法。 同 其它分类器 相比， 支持向量机具有很好的 推广性能， 对未知样本的预测有较高的 准确率， 因 此得到广泛应用。 简单的支持向量机只能处理二值分类问题。 本文在己有多分类支持向 量机基 础上， 提出一种新的几何距离多分类支持向量分类器; 在此基础上， 本文将二值 支持向量机的后验概率输出也推广到多分类问题， 避免了一般方法使用的迭代算 法， 在快速预测的前提下同样提高了预测准确率。 数值实验的结果表明， 这两种 方法都具有很好的推广性能，能明显提高分类器对未知样本的分类准确率。 本文首先介绍了数据挖掘产生的背景以 及相关的 理论与技术基础， 并介绍本 文研究内容。 第二章深入讨论了数据挖掘的分类、 处理过程模型以及挖掘中使用较多的一 些技术。 第三章介绍了用于数据挖掘的统计学习理论和支持向量机， 并在第四章提出 基于几何距离的多分类支持向量机， 在第五章提出一种将后验概率支持向量机推 广到多分类问题的方法，最后指出今后研究中需要解决的一些问题。 关键词:数 据挖掘 统计学习 理 论 支 持向 量 机 后 验概率 abs tract i n t h e p ast y e a r s , c o m p u t e r t e c h n i q u e s e s p e c i a l l y o f d a t a b a s e t e c h n i q u e s h a v e d e v e l o p e d g r e a t ly , a r e a o f p e o p l e s a c t i v it i e s h a s b e e n e x t e n d e d , r h y t h m o f l i f e h a s s p e e d e d u p . p e o p l e a r e a b l e t o g e t a n d s t o r e d a t a m o r e q u i c k l y , e a s i l y a n d c h e a p l y , w h i c h m a k e t h e d a t a a n d i n f o r m a t io n i n c re a s e e x p o n e n t i a l ly . f a c i n g t h e g r e a t c a p a c i t y o f d a t a , p e o p l e a r e u n d e r t h e p r e s s u r e o f i n f o r m a t i o n e x p l o s i o n a n d d a t a g l u t . i t w i l l b e g a r b a g e i f t h e m a s s i v e d a t a c a n t b e e x p l o i t e d . i t s t h e k n o w l e d g e t h a t h a s g r e a t e ff e c t o n t h e d e v e l o p m e n t o f s o c i e t y . d a t a m i n i n g i s a t e c h n o lo g y t h a t f i n d s u n d e r 如 n g r u l e s a n d e x t r a c t s v a l u a b l e k n o w l e d g e . t h e r e a r e l o t s o f b r a n c h e s i n d a t a m i n i n g , o n e o f t h e m i s c l a s s i f i c a t i o n ru l e s m i n i n g . w i t h p r o p e r t r a i n i n g a l g o r i t h m o n tr a i n i n g d a t a , i t w i l l g e n e r a t e c l a s s i f i e r s t h a t c o u l d g e t p r e d i c t i o n t o u n k n o w n e x a m p l e s . s u p p o rt v e c t o r m a c h i n e ( s v m ) i s a n e w c l a s s i fi c a t i o n a l g o r i t h m b as e d o n s t a t i s t i c a l l e a r n in g t h e o r y . c o m p a r e d t o o t h e r c l a s s i f i e r s , s v m h a s b e t t e r g e n e r a l i z a t i o n p e r f o r m a n c e a n d h i g h e r p r e d i c t i o n a c c u r a c y t o t e s t e x a m p l e . s o s v m h a s h a d a l o t o f a p p l i c a t io n n a i v e s v m i s o n l y a b l e t o d e a l w it h b i n a r y c l a s s i f i c a t i o n . i n t h i s t h e s i s , a ft e r d i s c u s s e d t h e c u r r e n t m u l t i c l ass s v ms , a n o v e l m u l t i c l a s s s v m c l a s s i f i e r b ase d o n g e o m e t r i c d i s t a n c e i s p r o p o s e d . a n d t h e p r o b a b i l i t y o u t p u t o f b i n a ry s v m i s g e n e r a l i z e d t o m u l t i c l as s s v m w i t h o u t i t e r a t i o n c o m p u t i n g , w h i c h i m p r o v e s p r e d i c t io n a c c u r a c y w it h f a s t c o m p u t a t i o n . t h e n u m e r i c e x p e r i m e n t p r o v e d th a t b o t h t h e a b o v e t w o m e t h o d s h a v e g o o d g e n e r a l i z a t i o n , w h i c h w i l l i n c r e a s e p re d i c t i o n a c c u r a c y t o u n k n o w n e x a m p l e s . i n c h a p t e r i o f t h i s t h e s i s , t h e h i s t o r y a n d r e l a t e d t h e o r ie s o f d a t a m i n i n g a r e i n t r o d u c e d . i n c h a p t e r 2 , t h e t a x o n o m y , p r o c e s s i n g m o d e l s a n d s o m e p o p u l a r t e c h n o l o g i e s a r e d i s c u s s e d . i n c h a p t e r 3 , s t a t i s t i c a l e a rn i n g t h e o r y a n d s v m a r e i n tr o d u c e d , a n d t h e n a n e w m u l t ic l a s s s v m b a s e d o n g e o m e t r i c d i s t a n c e i s p r o p o s e d i n c h a p t e r 4 . i n c h a p t e r 5 , t h e p r o b a b i l i t y o u t p u t i s g e n e r a l i z e d t o m u lt ic l a s s p r o b l e m s . a t l a s t s o m e i n t e r e s t i n g t a s k s in r e s e a r c h a r e p o i n t e d o u t . k e y wo r d s : d a t a m i n in g , s t a t i s t i c a l l e a r n i n g t h e o r y , s u p p o rt v e c t o r m a c h i n e , p o s t e r i o r p r o b a b i l i t y 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果， 除了文中特别加以标注和致谢之处外， 论文中不包含其他人己 经发表 或 撰 写 过 的 研 究 成 果 ， 也 不 包 含 为 获 得 2继一 或 其 他 教 育 机 构 的 学 位 或 证 书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名: 签 字 日 期 : 枷夺 年 月 分 日 学位论文版权使用授权书 本 学 位 论 文 作 者 完 全 了 解k ,圭 乞 有 关 保 留 、 使 用 学 位 论 文 的 规 定 。 特 授 权 -选生 可以 将 学 位 论 文 的 全 部 或 部 分内 容 编 入 有关 数 据库 进 行 检 索， 并采用影印、 缩印或扫描等复制手段保存、 汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 保密的学位论文在解密后适用本授权说明) 学位论文作者签名: 签 字日 期 : 2 0 午 年 郑 建 华 月9 。 导师签名: 签字日期: 第一章 引言 第一章 引言 1 . 1 问题的背景 计算机技术经历了半个世纪的发展，给人类社会带来了巨 大的影响与变化。 在支配人类社会的三大要素 ( 能源、 材料和信息) 中， 信息愈来愈显示出其重要 性和支配力， 它将人类社会由 工业化时代推向 信息化时代。 随着人类活动范围的 扩展、 生活节奏的加快以及技术的进步， 人们能以更快速更容易更廉价的方式获 取和存储数据， 这就使得数据及其信息量以 指数方式增长。 然而， 人类的各项活动都是基于人的智慧与知识， 根据对外部世界的观察和 了解， 做出正确的判断、 决策并采取适当的行动， 而数据仅仅是人们用各种工具 和手段观察外部世界所得到的原始材料，它本身没有任何意义。 从数据到知识， 需要经过分析加工处理精炼的过程。 早在八十年代， 人们在“ 物竞天择， 适者生存” 的大原则下， 就认识到“ 谁 最先从外部世界获得有用信息并加以 利用，谁就可能成为赢家” 。而今置身市场 经济且面向全球性剧烈竞争的环境下， 任何商家的优势都不单纯地取决于诸如产 品、 服务、地区等因素， 而在于创新。 用知识作为创新的原动力， 就能使商家长 期持续地保持竞争优势。 因此要能及时迅速地从日 积月累的庞大的数据库以及互 联网上获取与经营决策相关的知识， 自 然而然就成为满足易变的客户需求以及因 市场快速变化而引起激烈竟争局面的唯一武器。 如何对数据与信息快速有效地进 行分析加工提炼以获取所需知识，就成为计算机及信息技术领域的重要研究课 题。 数据挖掘 1 就是在这种应用需求推动下多 种学科融合的结果。 1 . 2 数据挖掘的理论与技术基础 数据挖掘的出现得益于计算机科学领域内几种理论与技术的蓬勃发展。 首先是数据库技术。 随着数据库技术的不断发展及数据库管理系统的广泛应 用， 大型数据库系统己 经在各行各业普及， 数据库中存储的数据量急剧增大。 在 大量的数据背后隐藏着许多重要信息，这些重要信息可以很好地支持人们的决 策。 可是目前用于对这些数据进行分析处理的工具却很少。目 前人们用到的主要 第一章 引言 第一章 引言 1 . 1 问题的背景 计算机技术经历了半个世纪的发展，给人类社会带来了巨 大的影响与变化。 在支配人类社会的三大要素 ( 能源、 材料和信息) 中， 信息愈来愈显示出其重要 性和支配力， 它将人类社会由 工业化时代推向 信息化时代。 随着人类活动范围的 扩展、 生活节奏的加快以及技术的进步， 人们能以更快速更容易更廉价的方式获 取和存储数据， 这就使得数据及其信息量以 指数方式增长。 然而， 人类的各项活动都是基于人的智慧与知识， 根据对外部世界的观察和 了解， 做出正确的判断、 决策并采取适当的行动， 而数据仅仅是人们用各种工具 和手段观察外部世界所得到的原始材料，它本身没有任何意义。 从数据到知识， 需要经过分析加工处理精炼的过程。 早在八十年代， 人们在“ 物竞天择， 适者生存” 的大原则下， 就认识到“ 谁 最先从外部世界获得有用信息并加以 利用，谁就可能成为赢家” 。而今置身市场 经济且面向全球性剧烈竞争的环境下， 任何商家的优势都不单纯地取决于诸如产 品、 服务、地区等因素， 而在于创新。 用知识作为创新的原动力， 就能使商家长 期持续地保持竞争优势。 因此要能及时迅速地从日 积月累的庞大的数据库以及互 联网上获取与经营决策相关的知识， 自 然而然就成为满足易变的客户需求以及因 市场快速变化而引起激烈竟争局面的唯一武器。 如何对数据与信息快速有效地进 行分析加工提炼以获取所需知识，就成为计算机及信息技术领域的重要研究课 题。 数据挖掘 1 就是在这种应用需求推动下多 种学科融合的结果。 1 . 2 数据挖掘的理论与技术基础 数据挖掘的出现得益于计算机科学领域内几种理论与技术的蓬勃发展。 首先是数据库技术。 随着数据库技术的不断发展及数据库管理系统的广泛应 用， 大型数据库系统己 经在各行各业普及， 数据库中存储的数据量急剧增大。 在 大量的数据背后隐藏着许多重要信息，这些重要信息可以很好地支持人们的决 策。 可是目前用于对这些数据进行分析处理的工具却很少。目 前人们用到的主要 第一章 引言 是数据库的存储功能，而隐藏在这些数据之后的更重要的信息则没有充分利用。 这些信息是关于数据整体特征的描述以及对发展趋势的预测， 在决策生成的过程 中具有重要的参考价值。数据库技术的日 益成熟为数据挖掘提供了发挥的平台。 数据仓库的出现， 为更深入地对数据进行分析提供了条件。 针对市场变化的 加速，人们提出了能进行实时分析和产生相应报表的在线分析工具o l a p ( o n l i n e a n a l y t i c a l p r o c e s s i n g ) . o l a p 能允许用户以 交互方式浏览数据仓库内 容， 并对其中的数据进行多维分析， 能及时地从变化的和不太完整的数据中提取 出与企业经营活动密切相关的信息。 其次， 在数据库技术飞速发展的同时， 人工智能领域的一个分支机器学 习的研究也取得很大进展。自 5 0 年代开始机器学习的研究以来， 先后经历了神经 模型和决策理论、 概念符号获取及知识加强和论域专用学习三个阶段， 根据人类 学习的不同模式人们提出了很多机器学习方法， 如: 基于实例的学习、 基于观察 和发现的学习、 神经网络和遗传算法等等。 其中某些常用且较成熟的算法己被人 们运用于实际的应用系统及智能计算机的设计和实现中。 数据挖掘中的许多方法 就来源于机器学习， 如分类规则挖掘中的 i d 3 算法等 2 0 数据挖掘处理的对象是某一专业领域中积累的数据; 挖掘过程是一个人机交 互、 多次反复的过程; 挖掘的结果要应用于该领域。 因此数据挖掘的整个过程都 离不开应用领域的专业知识。目 前数据挖掘技术在货篮数据( b a s k e t d a t a ) 分析、 金融风险预测、产品产量与质量分析、分子生物学、基因工程研究、i n t e rn e t 站 点的访问模式发现以及信息搜索和分类等许多领域得到了成功的应用。 一套金融 风险预测系统一年可以 挽回数千万美元的损失: “ 深蓝” 计算机 ( d e e p b l u e ) 能 够战胜人类国际象棋世界冠军， 其成功的一个重要因素是具有知识发现能力， 能 从存储了7 0 万盘棋谱的数据库中提取有用的知识; 如果你通过i n t e rn e t 访问著名 的亚马逊网上书店， 会发现当你选中一本书后， 将出现“ 该书的购买者中有百分 之x x同时购买了y y书”的推荐 ( 这是一个典型的挖掘关联规则的案例) 。可 见， 数据挖掘技术己 经步入人们日 常生活， 它是在应用需求推动下跨学科发展的 产物。 1 .3 数据挖掘的研究内容 目前数据挖掘领域的研究内容主要包括: 1 .基础理论研究。目前数据挖掘给人的印象是相关文献越来越多、可 用技术层出不穷，很活跃， 也很零乱。 这是因为数据挖掘的理论体系尚 不完整，还没有形成一门独立完整的学科。在1 9 9 9 年的k d d年会上， 第一章 引言 是数据库的存储功能，而隐藏在这些数据之后的更重要的信息则没有充分利用。 这些信息是关于数据整体特征的描述以及对发展趋势的预测， 在决策生成的过程 中具有重要的参考价值。数据库技术的日 益成熟为数据挖掘提供了发挥的平台。 数据仓库的出现， 为更深入地对数据进行分析提供了条件。 针对市场变化的 加速，人们提出了能进行实时分析和产生相应报表的在线分析工具o l a p ( o n l i n e a n a l y t i c a l p r o c e s s i n g ) . o l a p 能允许用户以 交互方式浏览数据仓库内 容， 并对其中的数据进行多维分析， 能及时地从变化的和不太完整的数据中提取 出与企业经营活动密切相关的信息。 其次， 在数据库技术飞速发展的同时， 人工智能领域的一个分支机器学 习的研究也取得很大进展。自 5 0 年代开始机器学习的研究以来， 先后经历了神经 模型和决策理论、 概念符号获取及知识加强和论域专用学习三个阶段， 根据人类 学习的不同模式人们提出了很多机器学习方法， 如: 基于实例的学习、 基于观察 和发现的学习、 神经网络和遗传算法等等。 其中某些常用且较成熟的算法己被人 们运用于实际的应用系统及智能计算机的设计和实现中。 数据挖掘中的许多方法 就来源于机器学习， 如分类规则挖掘中的 i d 3 算法等 2 0 数据挖掘处理的对象是某一专业领域中积累的数据; 挖掘过程是一个人机交 互、 多次反复的过程; 挖掘的结果要应用于该领域。 因此数据挖掘的整个过程都 离不开应用领域的专业知识。目 前数据挖掘技术在货篮数据( b a s k e t d a t a ) 分析、 金融风险预测、产品产量与质量分析、分子生物学、基因工程研究、i n t e rn e t 站 点的访问模式发现以及信息搜索和分类等许多领域得到了成功的应用。 一套金融 风险预测系统一年可以 挽回数千万美元的损失: “ 深蓝” 计算机 ( d e e p b l u e ) 能 够战胜人类国际象棋世界冠军， 其成功的一个重要因素是具有知识发现能力， 能 从存储了7 0 万盘棋谱的数据库中提取有用的知识; 如果你通过i n t e rn e t 访问著名 的亚马逊网上书店， 会发现当你选中一本书后， 将出现“ 该书的购买者中有百分 之x x同时购买了y y书”的推荐 ( 这是一个典型的挖掘关联规则的案例) 。可 见， 数据挖掘技术己 经步入人们日 常生活， 它是在应用需求推动下跨学科发展的 产物。 1 .3 数据挖掘的研究内容 目前数据挖掘领域的研究内容主要包括: 1 .基础理论研究。目前数据挖掘给人的印象是相关文献越来越多、可 用技术层出不穷，很活跃， 也很零乱。 这是因为数据挖掘的理论体系尚 不完整，还没有形成一门独立完整的学科。在1 9 9 9 年的k d d年会上， 第一章 引言 有关专家提出要加强数据挖掘的理论研究，使之成为一种主流技术。 2 .数据挖掘技术和算法的研究。包括新技术 ( 如支持向量机) 在数据 挖掘中的应用、算法的改进与优化、并行算法的设计与实现等。此外， 数据挖掘往往直接面对的是现实数据，因此对不完整、不确定或有噪声 的数据进行处理也是数据挖掘必须解决的问题。 3 .应用领域的拓展。这是数据挖掘最吸引人的地方，也是推动数据挖 掘发展的根本动力。一方面， 数据挖掘需要向更多的应用领域渗透;另 一方面，需要开发更多面向应用的数据挖掘系统和产品，建立行业内的 数据标准和通用挖掘平台、 建立可交换信息和共享知识的通用数据仓库 是今后要解决的问题。 随着数据挖掘的发展， 还会带来一些其它问题， 如购买商品、 访问站点会涉 及的个人隐私和企业销售数据所涉及的商业秘密等， 这些问题都值得人们进行关 注。 尽管存在许多问题， 但并不能阻止数据挖掘发展的蓬勃势头。 各类数据挖掘 的会议、研讨会纷纷涌现，许多领域的国际会议也将 k d d列为专题讨论。数据 挖掘不仅在学术界广受关注， 许多著名的计算机公司开始尝试数据挖掘商业软件 的 开 发。 比 较典型的 如s a s 公司的e n t e r p r i s e m i n e r , i b m公司的i n t e l l i g e n t m i n e r , s g i 公司的s e t mi n e r , s p s s公司的c l e m e n t i n e 等。 与国外相比，国内对数据挖掘的研究稍晚。1 9 9 3年国家自 然科学基金开始 对数据挖掘研究进行支持。 目 前国内许多高校和科研单位都在从事数据挖掘的基 础理论和应用研究工作。 1 . 4 笔者所做的工作 分类规则挖掘是数据挖掘中的一个重要方向。 现有的分类规则挖掘方法主要 有决策树 2 、 神经网络 1 , k近邻 3 , b a y e s 1 以 及支持向 量机 4 , 5 等。 其中 支 持向 量机是以统计学习理论 6 为基础发展起来的一种新的分类方法， 可以很容 易控制分类器的复杂性， 具有很好的推广性能， 而且对小样本数据训练出的分类 器仍有较高的预测准确率。 单纯的支持向 量机只能处理两类别( b i n a r y ) 分类问 题， 对多类别( m u l t i c l a s s ) 数据需要作进一步的扩展。 本文在已有的多分类支持向量机基础上， 从几何直观 和理论分析出发，提出一种新的基于几何距离的多分类支持向量机。 后验概率对分类器的设计非常有用 7 。 但是支持向量机只能输出 确定的 类 别标号， 不能直接输出类后验概率。 p l a tt 等提出了一种将支持向量机决策函数的 第一章 引言 有关专家提出要加强数据挖掘的理论研究，使之成为一种主流技术。 2 .数据挖掘技术和算法的研究。包括新技术 ( 如支持向量机) 在数据 挖掘中的应用、算法的改进与优化、并行算法的设计与实现等。此外， 数据挖掘往往直接面对的是现实数据，因此对不完整、不确定或有噪声 的数据进行处理也是数据挖掘必须解决的问题。 3 .应用领域的拓展。这是数据挖掘最吸引人的地方，也是推动数据挖 掘发展的根本动力。一方面， 数据挖掘需要向更多的应用领域渗透;另 一方面，需要开发更多面向应用的数据挖掘系统和产品，建立行业内的 数据标准和通用挖掘平台、 建立可交换信息和共享知识的通用数据仓库 是今后要解决的问题。 随着数据挖掘的发展， 还会带来一些其它问题， 如购买商品、 访问站点会涉 及的个人隐私和企业销售数据所涉及的商业秘密等， 这些问题都值得人们进行关 注。 尽管存在许多问题， 但并不能阻止数据挖掘发展的蓬勃势头。 各类数据挖掘 的会议、研讨会纷纷涌现，许多领域的国际会议也将 k d d列为专题讨论。数据 挖掘不仅在学术界广受关注， 许多著名的计算机公司开始尝试数据挖掘商业软件 的 开 发。 比 较典型的 如s a s 公司的e n t e r p r i s e m i n e r , i b m公司的i n t e l l i g e n t m i n e r , s g i 公司的s e t mi n e r , s p s s公司的c l e m e n t i n e 等。 与国外相比，国内对数据挖掘的研究稍晚。1 9 9 3年国家自 然科学基金开始 对数据挖掘研究进行支持。 目 前国内许多高校和科研单位都在从事数据挖掘的基 础理论和应用研究工作。 1 . 4 笔者所做的工作 分类规则挖掘是数据挖掘中的一个重要方向。 现有的分类规则挖掘方法主要 有决策树 2 、 神经网络 1 , k近邻 3 , b a y e s 1 以 及支持向 量机 4 , 5 等。 其中 支 持向 量机是以统计学习理论 6 为基础发展起来的一种新的分类方法， 可以很容 易控制分类器的复杂性， 具有很好的推广性能， 而且对小样本数据训练出的分类 器仍有较高的预测准确率。 单纯的支持向 量机只能处理两类别( b i n a r y ) 分类问 题， 对多类别( m u l t i c l a s s ) 数据需要作进一步的扩展。 本文在已有的多分类支持向量机基础上， 从几何直观 和理论分析出发，提出一种新的基于几何距离的多分类支持向量机。 后验概率对分类器的设计非常有用 7 。 但是支持向量机只能输出 确定的 类 别标号， 不能直接输出类后验概率。 p l a tt 等提出了一种将支持向量机决策函数的 第一章 引言 输出 映 射为 类后验概率的 算 法【 7 ， 但也只 针对二 值支持向 量 机。 本 文将 多分 类 支 持向 量机中的“ 一对多” ( o n e a g a i n s t a l l ) 方法和p l a tt的 算法结 合起来， 将 支持向量机的后验概率输出推广到多分类情形。 在u c i 和s t a t l o g 数据集上的 数值实验表明， 这两种方法对预测 准确率都有 明显提高。 第二章 数据挖掘理论与技术 第二章 数据挖掘理论与技术 数据挖掘( d a t a m i n i n g ) 是一种从大量数据中 发现潜在规律、 提取有用知识 的技术， 也是一个从有噪声、 不完整的数据中挖掘出有意义的知识的过程。 所挖 掘的数据对象可以 是数据库或数据仓库， 也可以是其它数据源。 数据挖掘是一个 新兴的多学科交叉领域， 这其中主要涉及数据库系统、 数据仓库、 统计学、 机器 学习、数据可视化、信息检索和高性能计算等，其它学科还包括人工神经网络、 模式识别、空间数据分析、图像数据库、 信号处理和归纳逻辑等。 数据挖掘是一 个包含多个处理步骤的知识发现过程， 其中主要包括数据清洗、 数据集成、 数据 选择、数据转换、数据挖掘、模式评估和知识表达输出等。 数据挖掘不但能够利用已有的先验知识， 而且能够发现未知的知识; 它所得 到的知识是 “ 显式”的，既能为人所理解，又便于存储和应用，因此一出现就得 到广泛的重视。 2 . 1 数据挖掘分类 目前对数据挖掘的研究非常活跃， 每年都有大量的研究文献涌现， 分别针对 数据挖掘的处理过程、 功能模型、 算法研究、 应用等不同层面。 本节尝试从数据 挖掘的功能模型和挖掘对象两个方面进行分类。 2 . 1 . 1 数据挖掘的功能模型 数据挖掘功能模型回答了“ 数据挖掘能够干什么” 的问题。 数据挖掘模型按 照功能分为预测模型和描述模型 1 。 在预测模型中， 用来预测的 称为独立变量， 要预测的称为相关变量或目 标变量。 预测模型包括分类模型、 回归模型和时间序 列模型等; 描述模型包括聚类模型、 关联模型和序列模型等。 前者有时又称为 有 监督学习，后者称为无监督学习。 分类模型 ( c l a s s if i c a t i o n mo d e l )用于提取能代表群体的特征属性。在数据 挖掘中， 分类模型通过对己知类别的个体进行归纳， 找出各类的特征属性，即分 类模式。 在有些情况下， 先由 领域专家对个体进行分类， 再通过分类模型提取分 类模式。 回归 模型 ( r e g r e s s i o n m o d e l ) 8 , 9 , 1 0 用属性的历史数据预测未来趋势。 在 第二章 数据挖掘理论与技术 第二章 数据挖掘理论与技术 数据挖掘( d a t a m i n i n g ) 是一种从大量数据中 发现潜在规律、 提取有用知识 的技术， 也是一个从有噪声、 不完整的数据中挖掘出有意义的知识的过程。 所挖 掘的数据对象可以 是数据库或数据仓库， 也可以是其它数据源。 数据挖掘是一个 新兴的多学科交叉领域， 这其中主要涉及数据库系统、 数据仓库、 统计学、 机器 学习、数据可视化、信息检索和高性能计算等，其它学科还包括人工神经网络、 模式识别、空间数据分析、图像数据库、 信号处理和归纳逻辑等。 数据挖掘是一 个包含多个处理步骤的知识发现过程， 其中主要包括数据清洗、 数据集成、 数据 选择、数据转换、数据挖掘、模式评估和知识表达输出等。 数据挖掘不但能够利用已有的先验知识， 而且能够发现未知的知识; 它所得 到的知识是 “ 显式”的，既能为人所理解，又便于存储和应用，因此一出现就得 到广泛的重视。 2 . 1 数据挖掘分类 目前对数据挖掘的研究非常活跃， 每年都有大量的研究文献涌现， 分别针对 数据挖掘的处理过程、 功能模型、 算法研究、 应用等不同层面。 本节尝试从数据 挖掘的功能模型和挖掘对象两个方面进行分类。 2 . 1 . 1 数据挖掘的功能模型 数据挖掘功能模型回答了“ 数据挖掘能够干什么” 的问题。 数据挖掘模型按 照功能分为预测模型和描述模型 1 。 在预测模型中， 用来预测的 称为独立变量， 要预测的称为相关变量或目 标变量。 预测模型包括分类模型、 回归模型和时间序 列模型等; 描述模型包括聚类模型、 关联模型和序列模型等。 前者有时又称为 有 监督学习，后者称为无监督学习。 分类模型 ( c l a s s if i c a t i o n mo d e l )用于提取能代表群体的特征属性。在数据 挖掘中， 分类模型通过对己知类别的个体进行归纳， 找出各类的特征属性，即分 类模式。 在有些情况下， 先由 领域专家对个体进行分类， 再通过分类模型提取分 类模式。 回归 模型 ( r e g r e s s i o n m o d e l ) 8 , 9 , 1 0 用属性的历史数据预测未来趋势。 在 第二章 数据挖掘理论与技术 最简单的情况下， 可以用标准统计方法， 如线性回归等。 但现实中往往非线性问 题居多，如股票价格的涨跌、机械系统故障的发生等，由于受许多因素的影响， 问题变得非常复杂。 回归模型的任务就是找出对这些变化的准确描述。 有些技术 既 可以 用于 分 类， 又 可以 用于回归， 如c a r t ( c la s s ifi c a t i o n a n d r e gr e s s io n t r e e s) 1 1 1 2 等。 时间 序列模型 ( t i m e s e r i e s m o d e l ) 用己 有的 数据序列预测未来【 1 3 。 从这 一点上看， 与回归模型很相似。 但回归模型不强调数据间的先后顺序， 而时间序 列模型要考虑时间特性，尤其要考虑时间周期的层次，如天、周、月、年等， 有 时还要考虑日历的影响，如节假日 等。 聚类模型 ( c l u s t e r i n g m o d e l ) 1 4 是将一个群体分成多个类， 使同 类个体尽 可能相似而不同类间个体差异尽可能大。 与分类模型不同的是， 聚类模型从未知 开始， 既不知道具体的分类标准， 也不知道会有些什么类别。 按照给定的聚类参 数 ( 如距离等) 进行分解、合并。 得到的结果由 领域专家进行甄别， 如果不满足 目 标要求，需要修改聚类参数并重新聚类，直到满足要求为止。 关联模型 ( a s s o c i a t i o n m o d e l ) 1 5 用于发现事物间的关联规则， 或称相关 程度。关联规则的一般形式是: 如果a发生，则b有百分之c 的可能发生 c 称为关联规则的置信度 ( c o n f i d e n c e ) 。例如: 如果i b m的股票价格上升，有7 0 %的可能微软的股票价格要下降; 买榔头的人有4 0 %的可能同时买钉子。 序列 模型 ( s e q u e n c e m o d e l ) t 1 6 与 关 联 模型 很相似，不同 的是 序 列 模 型的 对象是在时域分布的，发现的规则也与先后顺序有关。 2 . 1 . 2 数据挖掘的对象 按照不同的数据类型， 数据挖掘研究在时间序列数据、 空间数据、 文本数据、 多媒体数据等方面展开。 时间序列数据 ( t e m p o r a l 或 t i m e s e ri e s d a t a ) 1 3 是与时间 有关的 一系列 数据。 可以 进一步分为时间相关数据和序列相关数据。 时间相关数据与 数据产生 的绝对时间有关， 如股票价格、 银行帐务、设备运行日志等; 序列相关数据与数 据产生的绝对时间关系不大， 而注重数据间的先后次序。 典型的序列相关数据是 传感器输出数据，简称传感器数据 ( s e n s o r d a t a ) 。对时间序列数据的挖掘主要 是发现序列中事物出现的周期和规律，以及不同时间序列间的同步关系。 空间 数 据( s p a t i a l d a t a ) 1 4 是 与空间 位置 或 地 理信息 有关的 数 据， 如二 维、 三维图像数据、地理信息系统 g i s 数据、人口普查数据等。 第二章 数据挖掘理论与技术 最简单的情况下， 可以用标准统计方法， 如线性回归等。 但现实中往往非线性问 题居多，如股票价格的涨跌、机械系统故障的发生等，由于受许多因素的影响， 问题变得非常复杂。 回归模型的任务就是找出对这些变化的准确描述。 有些技术 既 可以 用于 分 类， 又 可以 用于回归， 如c a r t ( c la s s ifi c a t i o n a n d r e gr e s s io n t r e e s) 1 1 1 2 等。 时间 序列模型 ( t i m e s e r i e s m o d e l ) 用己 有的 数据序列预测未来【 1 3 。 从这 一点上看， 与回归模型很相似。 但回归模型不强调数据间的先后顺序， 而时间序 列模型要考虑时间特性，尤其要考虑时间周期的层次，如天、周、月、年等， 有 时还要考虑日历的影响，如节假日 等。 聚类模型 ( c l u s t e r i n g m o d e l ) 1 4 是将一个群体分成多个类， 使同 类个体尽 可能相似而不同类间个体差异尽可能大。 与分类模型不同的是， 聚类模型从未知 开始， 既不知道具体的分类标准， 也不知道会有些什么类别。 按照给定的聚类参 数 ( 如距离等) 进行分解、合并。 得到的结果由 领域专家进行甄别， 如果不满足 目 标要求，需要修改聚类参数并重新聚类，直到满足要求为止。 关联模型 ( a s s o c i a t i o n m o d e l ) 1 5 用于发现事物间的关联规则， 或称相关 程度。关联规则的一般形式是: 如果a发生，则b有百分之c 的可能发生 c 称为关联规则的置信度 ( c o n f i d e n c e ) 。例如: 如果i b m的股票价格上升，有7 0 %的可能微软的股票价格要下降; 买榔头的人有4 0 %的可能同时买钉子。 序列 模型 ( s e q u e n c e m o d e l ) t 1 6 与 关 联 模型 很相似，不同 的是 序 列 模 型的 对象是在时域分布的，发现的规则也与先后顺序有关。 2 . 1 . 2 数据挖掘的对象 按照不同的数据类型， 数据挖掘研究在时间序列数据、 空间数据、 文本数据、 多媒体数据等方面展开。 时间序列数据 ( t e m p o r a l 或 t i m e s e ri e s d a t a ) 1 3 是与时间 有关的 一系列 数据。 可以 进一步分为时间相关数据和序列相关数据。 时间相关数据与 数据产生 的绝对时间有关， 如股票价格、 银行帐务、设备运行日志等; 序列相关数据与数 据产生的绝对时间关系不大， 而注重数据间的先后次序。 典型的序列相关数据是 传感器输出数据，简称传感器数据 ( s e n s o r d a t a ) 。对时间序列数据的挖掘主要 是发现序列中事物出现的周期和规律，以及不同时间序列间的同步关系。 空间 数 据( s p a t i a l d a t a ) 1 4 是 与空间 位置 或 地 理信息 有关的 数 据， 如二 维、 三维图像数据、地理信息系统 g i s 数据、人口普查数据等。 第二章 数据挖掘理论与技术 文本数据 ( t e x t d a t a )就是我们一般的文字， 如报刊杂志、设备 维护手册、 故障 描述等的内 容。 对文本数据的挖掘 1 7 主要是发现某些文字出 现的 规律以 及 文字与语义、 语法间的联系， 用于自 然语言处理、 机器翻译、语音识别、 信息检 索等。当前一个十分活跃的研究方向 是w e b日 志 ( w e b l o g )的挖掘，目 的是有 效发现i n t e rn e t 用户访问站点的模式，从而提高服务的 针对性。 多 媒体数据 ( m u lt i m e d ia d a t a ) 1 8 是随着多媒体技术的蓬勃发 展和广泛应 用而日 益涌现的声音、图形、图像、 超文本等数据。 多媒体数据挖掘主要针对大 量图 像的存储和查询问 题而引起的 基于内容的图 像检索 ( c o n t e n t - b a s e d i m a g e r e t r i e v a l , c b i r ) 。由于与传统的文本数据不同，因此必须采用新的 挖掘手段来 发现内容和形式间的内在联系。 2 .2 数据挖掘处理过程模型 从工程角度讲， 数据挖掘是一个需要经过多次处理的反复的过程。 如同软件 工程在软件开发中的作用， 数据挖掘的处理过程模型为数据挖掘提供了宏观指导 和工程方法。 合理的处理过程模型能将各个处理阶段有机地结合在一起， 指导人 们更好地开发和使用数据挖掘系统。 从数据挖掘进入工程应用领域起，就有人对数据挖掘的过程进行归纳和总 结，提出了不同的数据挖掘处理过程模型。其中 u s a m a m.f a y y a d , g r e g o r y p i a t e t s k y - s h a p i r o等人给出的多处理阶段模型是一种通用模型， 也是 广为 接受的 一种处理模型，图2 - 1 所示的模型示意图在数据挖掘领域被广泛使用。 预处理 选择 原始数据 图2 - 1 u s a m a m .f a y y a d 的 数 据挖掘多 阶段处 理过程模型 1 9 9 6 年， b r a c h m a n 和a n a n d 通过对很多数据挖掘用户在实际工作中遇到的 第二章 数据挖掘理论与技术 文本数据 ( t e x t d a t a )就是我们一般的文字， 如报刊杂志、设备 维护手册、 故障 描述等的内 容。 对文本数据的挖掘 1 7 主要是发现某些文字出 现的 规律以 及 文字与语义、 语法间的联系， 用于自 然语言处理、 机器翻译、语音识别、 信息检 索等。当前一个十分活跃的研究方向 是w e b日 志 ( w e b l o g )的挖掘，目 的是有 效发现i n t e rn e t 用户访问站点的模式，从而提高服务的 针对性。 多 媒体数据 ( m u lt i m e d ia d a t a ) 1 8 是随着多媒体技术的蓬勃发 展和广泛应 用而日 益涌现的声音、图形、图像、 超文本等数据。 多媒体数据挖掘主要针对大 量图 像的存储和查询问 题而引起的 基于内容的图 像检索 ( c o n t e n t - b a s e d i m