（计算机软件与理论专业论文）多维多层数据挖掘算法mpfp的设计及其应用研究.pdf

多维多层数据挖掘算法m p f p 的设计及其应用研究 注 摘 要 数据挖掘是2 0 世纪9 0 年代中期兴起的一项新技术， 它是知识发现过程中的关 键步骤，也是当前知识发现领域中的一个研究热点。 关联规则的发现是数据挖掘中 的一项重要任务。关联规则表示数据库中一组对象之间某种关联关系。通常，对于 一个规则的衡量有两个标准:支持度和可信度。 挖掘关联规则的问题就是找出这样 的一些规则:他们的支持度和可信度分别大于用户指定的最小支持度和最小可信 度。长期以来，挖掘频繁模式主要采用a p r i o r i 算法及其改进形式，这类算法需要 产生大量候选项集，并反复扫描数据库，降低了挖掘的效率。 f p - 增长算法是一种基于模式增长的频繁模式挖掘算法， 它只需要两次扫描数 据库， 避免了 大量候选项集的产生，效率比a p r i o r i 算法快一个数量级。 然而， 此 算法也 存在着局限性和不足。 它的不足和局限性主要表现在以 下三方面: qf p 一 增 长算法只是用来挖掘单层、单维的频繁模式， 并且只能设定统一的最小支持度， 这 将会导致丢失支持度较低的有效集合。 当数据库很大或挖掘时设置的最小支持度 阐 值很小时， 构造基于整个数据库的f p 一 树不能存放入内存，使得f p 一 增长算法不 能很好地对大型数据库进行挖掘。 在构造f p 一 树的过程中，必须对数据库中每个 事务的每个频繁项逐个进行判断，决定如何插入到树中，严重影响了算法效率。 本文针对f p - 增长算法的不足，设计了一种新的算法 卜 - m p f p 算法，新的算法 很好地解决了算法的不足。 m p f p 算法有以下几种优点: 可以挖掘多维、多层数 据， 并在不同层次间可以指定多个不同的最小支持度来进行关联规则的挖掘。 对 于大型数据库采用了将数据库划分成投影数据库的集合并对生成的投影数据库构 造能够存放于内 存的f p - t r e e 树。在构造基于投影数据库的f p 一 树时，采用了一 种树和投影技术相结合的方法， 按层次构造基于投影数据库的f p 一 树。 算法具有良 好的可伸缩性，同时大大提高了系统的性能。 然后， 根据新的关联规则挖掘算法- 一 - -m p f p 算法， 结合航运企业业务的实际情 注 :本论文得到 “ 集装箱信息系统”项目的支持。 ， 设计了面向航运企业的数据挖掘模型r s - m i n e r ， 在挖掘模型r s - m 工 n e r 的实现过程 中， 运用支持多乎台的j a v a 开发语言， 采用了 面向 对象的设计和开发方法。同 时， 在知识的表达和解释机制方面也作了很多工作，使知识的表达不仅限于数字和符号， 而是更容易理解的表格、 图形等， 并对获得的模式进行了 简单的解释和评估。 r s - m i n e r 控掘模型以航运行业为背景，功能完善，操作简单，可扩展性强。 关键词 数据挖掘，关联规则， a p r i o r i 算法，f p 一 增长算法，可信度，支持度 ab s tr act a s a n e w t e c h n o lo g y b o o m e d in t h e m id - 1 9 9 0 s , d a t a m in i n g r e p r e s e n t s a k e y s t e p in t h e p r o c e d u r e s o f k n o w le d g e d is c o v e r in g a n d is a ls o a h o t r e s e a r c h t o p ic i n t h e d o m a i n o f k n o w le d g e d is c o v e r in g . t h e d is c o v e ry o f a s s o c ia t io n r u le is a n imp o r t a n t t a s k i n d a t a mim i n g . a s s o c ia t io n r u le r e p r e s e n t s s o m e a s s o c ia t io n r e la t io n s r u le b e t w e e n a s e t o f o b j e c t s . g e n e r a lly , t h e r e a r e t w o s t a n d a r d t o m e a s u r e a r u le : s u p p o rt a n d c o n f id e n c e . t h e s t u d y o f m in in g a s s o c ia t io n r u le a im s t o f i n d t h e f o l lo w i n g r u le s : t h e ir s u p p o rt a n d c o n f id e n ce a r e m o r e t h a n t h e u s e r s m i n im u m r e s p e c t iv e ly . f o r a lo n g t i m e , a c a t e g o ry o f a p r io r i- lik e a lg o r it h m s h a s b e e n a d o p t e d f o r m in in g f r e q u e n t p a tt e r n s . b u t t h e y s u ff e r f ro m t a k in g m a n y s c a n s o f d a t a b a s e s f o r h u g e n u m b e r o f c a n d id a t e p a tt e rn o c c u r r e n ce f r e q u e n c ie s c h e c k in g . f p - g r o w t h a lg o r it h m a d o p t s p a tt e r n f r a g m e n t g ro w t h m e t h o d a n d o n ly s c a n s d a t a b a s e t w ic e . it is a b o u t a n o r d e r o f m a g n it u d e f a s t e r t h a n t h e a p r io r i a lg o r it h m . h o w e v e r , it s t ill h a s d is a d v a n t a g e s a n d d e f ic ie n c ie s . h e r e in a ft e r , t h e t h r e e a s p e c t s is t h e e m b o d im e n t o f it s d is a d v a n t a g e a n d d e f ic ie n c y : ( d f p - g r o w t h a lg o r it h m c a n o n ly m in e t h e s in g le - le v e l , s i n g le - d im e n s io n a l f r e q u e n t p a tt e r n s . a n d it c a n s e t o n e m in im u m s u p p o rt . s o it w ill le a d t o lo s e f r e q u e n t p a tt e r n s w h ic h h a v e lo w e r s u p p o rt . wh e n d a t a b a s e is v e ry h u g e o r s e tt in g a s m a l l m in i m u m s u p p o rt , c o n s t r u c t i n g a f p - t r e e b a s e o n t h e w h o le d a t a b a s e c a n n o t p u t in e m s m e m o ry . it m a k e s f p -g r o w t h a lg o r it h m c a n n o t m in e t h e l a r g e - s c a le d a t a b a s e v e ry w e l l.o i n t h e p r o ces s o f c o n s t r u c t in g f p - t r e e , it w i ll b e m u s t j u d g e e v e ry f r e q u e n t it e m in t h e t r a n s a c t io n a n d t h i n k o f h o w t o i n s e rt it i n t o t h e t r e e . t h i s m e a n s i n f e c t t h e e ff ic ie n c y o f t h e f p - g r o w t h a lg o r it h m b a d ly . a i m in g a t t h e d is a d v a n t a g e s a n d d e f ic ie n c ie s o f f p - g r o w t h a lg o r it h m, i d e s ig n a n e w a lg o r it h m -m p f p a lg o r it h m . t h e n e w m p f p a lg o r it h m r e s o lv e s t h e d is a d v a n t a g e s a n d d e f ic ie n c ie s o f f p - g r o w t h a lg o r it h m c o m m e n d a b ly . m p f p a lg o r it h m h a s t h r e e s t r o n g p o in t s :olt c a n m in e m u lt i- d im e n s io n a l , m u lt i - le v e l d a t a a n d t a k e a s s o c ia t io n a l r u le s t h o u g h t s e tt in g m a n y m in im u m s u p p o rt in d iff e r e n t i e v e l. f o r t h e la r g e - s c a le d a t a b a s e , t h e m p f p a lg o r it h m a d o p t s t o p a rt it io n t h e l a r g e d a t a b a s e t o m a n y p r o j e c t io n d a t a b a s e . a n d it c o n s t r u c t f p - t r e e b a s e o n t h e p r o j e c t io n d a t a b a s e . s l n t h e p r o c e s s o f c o n s t r u c t in g f p - t r e e , m p f p a lg o r it h m a d o p t s a w a y w h ic h i n t e g r a t e t h e t e c h n ic o f t r e e a n d p r o j e c t io n . it c o n s t r u c t s f p - t r e e a c c o r d i n g t o le v e l . m p f p a lg o r it h m h a s a g o o d r e t r a c t ilit y a n d s im u lt a n e it y t h e p e r fo r m a n c e o f s y s t e m h a s b e e n imp r o v e d c o n s u m e d ly . b a s e d o n t h e n e w m in e a s s o c ia t io n r u le a lg o r it h m -m p f p a lg o r it h m a n d t a k in g t h e d a ily r e t a il b u s i n e s s o f t h e s h ip p i n g t r a d e in t o c o n s id e r a t i o n , t h e a u t h o r d e s ig n s a s h ip p in g t r a d e - o r ie n t e d d a t a m i n in g m o d e l :r s - m i n e r . i n t h e r e a l iz a t io n o f t h e m i n in g m o d e l o f r s - m i n e r , t h e a u t h o r e m p lo y s j a v a d e v e lo p la n g u a g e w h ic h s u p p o rt m u lt i- p la ff o r m a n d t h e o b j e c t - o r ie n t e d m e t h o d o f d e s ig n i n g a n d d e v e lo p i n g . m e a n w h i le , t h e a u t h o r h a s w o r k e d a lo t i n k n o w le d g e e x p r e s s io n a n d e x p la n a t io n t o e n a b le t h a t t h e k n o w le d g e is n o t o n ly d e m o n s t r a t e d b y d ig it a n d s y m b o l b u t t a b le s a n d g r a p h ic s w h ic h a r e e a s ily c o m p r e h e n d e d . t h e a u t h o r a ls o e x p la i n e d a n d e v a l u a t e d t h e r e s u lt o f d a t a m in in g 一 t h e f r e q u e n t p a tt e r n. t a k in g s h ip p in g t r a d e a s it s b a c k g r o u n d , r s - m i n e r m i n e m o d e l is c h a r a c t e r iz e d b y p e rf e c t f u n c t io n , s im p le o p e r a t io n a n d s t r o n g e x t e n s i b i lit y . g ia n l i ( c o m p u t e r s o f tw a r e a n d t h e o ry ) d i r e c t e d b y p r o f . z h o u g u a n g s h e n g k e y wo r d s : d a t a m in in g , a s s o c ia t io n r u le s , a p r io r i a lg o r it h m , f p - g r o w t h a lg o r it h m , c o n f id e n c e , s u p p o rt 丫b4 u -jua 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。 论文 中 除了 特别加以 标注和 致谢的 地方外， 不包含其他人或其他机构已 经发表或 撰写过的 研究成果. 其他同 志对本研究的启发和 所做的贡献均已 在论文中 作 了明 确的声明 并表示了谢意。 作 者 签 名 :代刊日 期 :1s 0 v . 7 . - 论文使用授权声明 $ 娜 稗 上 海 海 运 学 院 有 关 保 留 、 使 用 学 位 论 文 的 ”， 即 : 学 校 有 权 保 留 迭 交 龟 未 粼 印 件 ， 允 许 论 文 被 查 阅 和 借 阅 ; 学 校 可 以 上 网 公 布 论 文 的 全 部或部分内 容， 可以 采用影印、 缩印或者其它复制手段保存论文。 保密的论 文在解密后遵守此规定。 作 者 签 名 :椒剥导 师 签 名 : a 4 弃 一 日 期: 理共对了 第一章 数据库中的知识发现和数据挖掘 1 . 1 引言 近年来， 随着数据库技术的不断发展以及数据库管理系统的广泛应用， 各行各 业积累数据的能力和速度达到了惊人的地步， 造成了海量数据的存储。 然而，多数 数据库系统仍只能对数据库进行录入、 查询、 统计等简单操作， 人们通过这些操作 所获得的信息量仅仅是整个数据库所包含的信息量的一部分， 隐藏在这些数据之后 的更重要的信息是关于这些数据的整体特征的描述及对其发展趋势的预测， 这些信 息在决策生成的过程中具有重要的参考价值， 但这些信息却不能被发现。这样使得 信息量的急剧增大和现有技术的局限性之间形成了一对矛盾， 面对如此丰富的信息 和数据却不能很好的利用，形成了 现今 “ 数据监狱” 和 “ 数据爆炸但知识贫乏”的 尴尬局面。 因此在商业领域和科学研究领域都迫切要求发展这样一种能够从如此海 量的数据中抽取出模式，找出 数据变化的规律和数据之间的相互依存关系的技术。 使人们能够从宏观的高层次的角度来审视数据， 充分发掘数据的潜力， 指导人们的 行为， 为决策和科学发现提供有力的支持。 于是， 知识发现及数据挖掘技术应运而 生。 1 . 2 数据库中的知识发现 1 . 2 . 1 知识发现的定义 知识发现 ( k n o w l e d g e d i s c o v e r y i n d a t a b a s e , k d d )一词是在1 9 8 9 年8 月于 美国底特律市召开的第一届k d d 国际学术会议上正式提出的。 随着k d d 研究的不断 深入，人们对k d d 的理解越来越全面，对k d d 有了一个比较公认的定义: 从大量数据中提取有效的、 新颖的、潜在有用的、并能最终被人理解的模式的 非平凡的处理过程。 “ 模式” 或称 “ 项目 集”可以 看成是知识的雏形，经过验证、 完善后形成知识。 下面分别对此定义中的一些名词进行进一步解释: 数据( d a t a ) : 一个有关事实f的集合，用来描述事物有关方面的信息。 如学生 档案中关于每个学生基本情况的记录。 处理过程( p r o c e s s ) : 包括数据预处理、模式提取、知识评估和优化等步骤。 多 1页 可理解/ 新颖/ 潜在作用( u n d e r s t a n d a b l e n o v e l / p o t e n t i a l l y u s e f u l ) : k d d提 取出的模式必须是可理解的: 必须是新颖的( 至少对系统来说) ; 必须在实践中有潜 在的作用。它们都可以采用度量函数来度量。 1 . 2 . 2数据库中 知识发现的 处理过程模型 关于k d d 的研究是为了将知识发现的成果应用于实际数据处理中， 为科学的决 策提供支持。 为了使得k d d 能够更好地应用于实践， 建立合适的处理过程模型能将 各个处理阶段有机地结合在一起， 以便于人们开发及使用k d d 应用系统是必不可少 的。下面介绍一个具有代表性的面向多阶段处理过程的k d d 处理过程模型。 多处理阶段模型将数据库中的知识发现看作是一个多阶段的处理过程，在整个 知识发现的过程中包括很多处理阶段。图1 - 1 是u . f a y y a d 等人给出的知识发现的 处理模型的简易图。 卜 赢犷no ! 4 丽丽 10 i - 评估与表示 知识 数据清洗与转换 日 数据库 目标数据 图 1 - 1数据库中知识发现的处理过程 图1 - 1 处理模型中， k d d 处理过程共分为三个处理阶段: 数据准备、 数据挖掘、 模式解释及知识评价。下面一一简要介绍。 ( 1 )数据准备:了解 k d d相关领域的有关情况，包括应用中的预先知识和目 标，熟悉有关的背景知识，并弄清楚用户的要求。主要工作内容包括: 数据选择:根据用户的要求从数据库中提取与k d d 相关的数据，k d d 将主要从 这些数据中进行知识提取， 在此过程中， 会利用一些数据库操作对数据进行处理， 建立一个目 标数据集，选择一个数据集或在多数据集的子集上聚焦。 数据预处理:主要是对阶段2 产生的数据进行再加工，检查数据的完整性及数 第 z页 据的一致性， 对其中的噪音数据进行处理， 对丢失的数据可以 利用统计方法进行填 补，去除噪声或无关数据，去除空白 数据域，考虑时间顺序和数据变化等。 数据转换:对经过预处理的数据， 根据知识发现的任务对数据进行再处理， 找 到数据的特征进行编码，减少有效变量的数目。 确定k d d 的目 标:根据用户的要求，确定k d d 是发现何种类型的知识，因为对 k d d 的不同要求会在具体的知识发现过程中采用不同的知识发现算法。 确定知识发现算法:根据所确定的目 标，选择合适的知识发现算法( 如汇总、 分类、回归、聚类等) ，这包括选取合适的模型和参数，并使得知识发现算法与整 个k d d 的评判标准相一致。 ( 2 ) 数据挖掘:运用 选定的知识发现算法，搜索或产生一个特定的感兴趣的 模式或数据集， 从数据中提取出 用户所需要的知识， 这些知识可以用一种特定的方 式表示或使用一些常用的表示方式，如产生式规则等。 ( 3 )模式解释与知识评估，其工作内容为: 模式解释:对发现的模式进行解释，去掉多余的不切题意的模式，转换成某个 有用的模式为知识。 知识评价: 根据最终用户的决策目的对提取的信息进行分析和评价，把最有价 值的信息、区分出来，并且通过决策支持工具呈现给用户。 以上处理步骤往往需要经过多次的反复，以不断提高学习效果。 1 . 3数据挖掘技术 1 . 3 . 1数据挖掘概念 由上述知识发现的处理过程模型可以看出，数据挖掘是知识发现过程中关键的 一个部分。 数据挖掘 ( d a t a m i n i n g ) : 是应用一系列技术从存放在数据库、数据仓库或其 它 信 息 库 中 的 大 量 数 据 中 提 取 人 们 感 兴 趣 的 信 息 和 知 识 ， 这 些 知 识 或 信 息 是 隐 含 的，事先未知而潜在有用的，提取的知识表示为概念、规则、规律、 模式等形式。 它是一类深层次的数据分析。 数据挖掘意味着在大量事实或观察数据的集合中发掘信息和知识的决策支持 过 程， 提 取的 知 识 可以 表示 为 概 念( c o n c e p t s ) 、 规则( r u l e s ) 、 规律( r e g u l a r i t i e s ) , 模式( p a t t e r n ) 等形式。 第 3页 1 . 3 . 2数据挖掘的任务 数据挖掘任务主要有以下几种: ( 1 )分类( c l a s s i f i c a t i o n ) 分类是数据挖掘中应用最多的任务之一。分类是找出一个类别的概念描述， 它 代表了 该类数据的整体信息，即该类的内 涵描述。一般用规则或决策树模式表示， 该模式能把数据库中的数据项影射到给定类别中的某一个。 一个类的内 涵描述分为: 特征描述( c h a r a c t e r i z a t i o n d e s c r i p t i o n ) 和区分描 述( d i s c r i m i n a t i o n d e s c r i p t i o n )。 特征描述是对类中对象的共同 特征的描述。 区分描述是对两个或多个类之间的区别的描述。 特征描述允许不同类中具有共同特 征，而区分描述对不同类不能有相同特征。 分类模式往往表现为一棵分类树， 根据数据的值从树根开始搜索， 沿着数据满 足的分支往上走， 走到树叶就能确定类别。 例如， 关于疾病的分类规则可以从已 知 病例( v ii 练集) 提取出来， 然后结合新病员的症状， 可用于对新病员进行诊断。分类 是利用训练样本集( 己知数据库元组和类别所组成的样本) 通过有关算法而求得。 建 立分类决策树的典型方法有i d s . c 4 . 5 等。 建立分类规则的 方法有a q 方法、粗糙 集方法、遗传分类器等。 ( 2 )聚类( c l u s t e r i n g ) 是根据客体属性对一系列未分类客体进行类别的识别， 把一组个体按照相似性 归成若干类别，即 “ 物以 类聚” 。它的目的是使得属于同一类别的个体之间的距离 尽可能的小而不同类别的个体间的距离尽可能的大。 客体的聚类应使得类内相似性 最大， 而类间相似性最小。 一旦聚类得以确定，各个客体就作相应的聚类标记， 并 概括同 一聚类中的各个客体的 共同 特性， 从而形成类别描述。 例如， 一系列的新疾 病可以根据其症状的相似性进行分组， 从而形成基本类别， 同一类别中各疾病的共 同症状便可用于描述该组疾病. 与分类模式不同， 进行聚类前并不知道将要划分成 几个组和什么样的组，也不知道根据哪一( 几) 个数据项来定义组。 聚类方法包括统计分析方法，机器学习方法和神经网络方法等。 在统计分析方法中，聚类分析是基于距离的聚类，如欧氏距离、海明距离等。 这种聚类分析方法是一种基于全局比 较的聚类， 它需要考察所有的个体才能决定类 的划分。 第 4页 在机器学习方法中， 聚类是一种非监督的学习。 在这里距离是根据概念的描述 来确定的，故聚类也称概念聚类。当聚类对象动态增加时， 概念聚类则称为概念形 成。 在神经网络中，自 组织神经网络方法用于聚类。 如a r t 模型、 k o h o n e n 模型等， 这是一种无监督学习方法。当给定距离闭值后，各样本按阐值进行聚类。 ( 3 )特征化( c h a r a c t e r i z a t i o n ) 是指将与任务相关的数据集概括或抽象为某个关系，称之为广义关系 ( g e n e r a l i z e d r e l a t i o n ) 。该广义关系可用于提取特征规则( c h a r a c t e r i z a t i o n r u l e ) 。 特征规则可以 在多层概念级上表示称之为目 标类的数据集特征。例如，某 种疾病的各种症状可以概念为一系列的特征规则。 ( 4 )区分( d i s c r i m i n a t i o n ) 是指发现分辨目 标类( t a r g e t c l a s s ) 与对照类( c o n t r a s t i n g c l a s s ) 的特征与 性质。从这些分辨目标类与对照类的特性中，可以发现一系列的区分规则 ( d i s c r i m i n a t i o n r u l e ) 。 例如，为了将某种疾病与其它种类的疾病区分开，区分 规则应能概括该种疾病不同与其它种类疾病的症状。 ( 5 ) 关联分析 ( a s s o c i a t i o n a n a l y s i s ) 是指发现客体之间的相互关系。若两个或多个数据项的取值之间重复出现几概 率很高时，它就存在某种关联，可以 建立起这些数据项的关联规则( a s s o c i a t i o n r u l e ) 。关联规则就是描述在一个事务中物品之间同时出现的规律的知识模式。它 展示属性一值频繁地在给定数据集中一起出现的条件。 例如，买面包的顾客有 7 0 9 6 的人还买牛奶，这是一条关联规则。若商店中将面 包和牛奶放在一起销售， 将会提高他们的销量。 在大型数据库中， 这种关联规则是 很多的，需要进行筛选， 一般用支持度( s u p p o r t ) 和可信度( c o n f i d e n c e ) 两个闲值 来淘汰那些无用的关联规则。关联规则的具体叙述详见后面有关章节. ( 6 ) 序列模式( s e q u e n t i a l p a t t e r n ) 是指在多个数据序列中发现共同的行为 模式。 序列模式与关联模式不同的是把 数据之间的关联性与时间 联系起来。 为了 发现序列模式， 不仅需要知道事件是否发 生， 而且需要确定事件发生的时间。 例如， 在购买彩电的人们当中，6 0 %的人会在 3 个月内购买影碟机。在序列模式中，需要找出在某个时间内出现比率一直高于某 第 ，页 一 最小百分比( 阐 值) 的规则。 这些规则会随着形式的变化做适当的调整。 ( 7 )时间序列模式 时间 序列模式根据数据随时间变化的趋势预测将来的值。 这里要考虑到时间的 特殊性质， 像一些周期性的时间定义如星期、月、 季节、 年等， 不同的日 子如节假 日可能造成的影响，日 期本身的计算方法， 还有一些需要特殊考虑的地方如时间前 后的相关性( 过去的事情对将来有多大的影响力) 等。 只有充分考虑时间因素， 利用 现有数据随时间变化的一系列的值，才能更好地预测将来的值。 ( 8 )情节( e p i s o d e ) 是指在事件序列中发现频繁情节( f r e q u e n t e p i s o d e ) 。所谓情节是指在给定长 度的时间区间内出 现的事件的有序集合， 而频繁情节是指在事件序列中具有一定出 现频率的情节。 如果在事件序列中发现了 频繁情节， 就可以生成描述或预测该序列 的行为。 ( 9 )偏差检测( d e v i a t i o n d e t e c t i o n ) 是指在与时间相关数据库中 某客体的偏离模式的发现与评估。客体的期望行为 通常由用户给定或根据假设( 如平均、 线性增长) 计算得知。 例如发现某些股票在某 段时间内 其行为不同与大多数股票的发展趋势。 数据库中的 数据存在很多异常情况， 从数据分析中发现这些异常情况也是很重 要的，以引起人们对它更多的注意。 偏差包括很多有用的知识，如: 分类中的反常实例 模式的 例外 观察结果与模型预测的偏差 值随时间的变化 偏差检测的 基本方法是寻找观察结果与参照之间的差别。 观察常常是某一个阐 值或多个阐值的 汇总， 而参照是给定模型的预测、外界提供的标准或另一个观察。 ( i 0 )预测( p r e d i c t i o n ) 预测是利用历史数据找出变化规律， 建立模型， 并用此模型来预测未来数据的 种类、特征等。 典型的方法是回归分析( r e g r e s s i o n a n a l y s i s ) ，即利用大量的历史数据，以 第 6页 时间为变量建立线性或非线性回归方程。 预测时， 只要输入任意的时间值， 通过回 归方程就可求出该时间的状态。 近年来， 发展起来的神经网 络方法， 如b p 模型， 它实现了非线性样本的学习， 能进行非线性函数的判别。分类也能进行预测， 但分类一般用于离散数值。 回归预 测用于连续数值.神经网络方法预测既可用于连续数值，也可以 用于离散数值。 1 . 3 . 3数据挖掘方法简介 数据挖掘方法是由人工智能、 机器学习的方法发展而来， 结合传统的统计分析 方法、 模糊数学方法以 及科学计算可视化技术，以数据库为研究对象，形成了数据 挖掘方法和技术。随着k d d 研究的深入，目 前己 有很多数据挖掘方法， 下面介绍几 种有代表性的数据挖掘方法。 粗糙集( r o u g h s e t ) 方法 粗糙集理论是一种研究不精确、不确定性知识的数学工具。知识工程研究中， 一直存在着信息的含糊性( v a g u e n e s s ) 等问 题。 含糊性有三种: 术语的模糊性， 如高 矮;数据的不确定性，如噪声引起的;知识本身的不确定性，如规则的前件 ( a n t e c e d e n t ) 和后件( c o n s e q u e n t ) 间的依赖关系并不是完全可靠的。 人工智能的基 础理论之一、 经典逻辑不足以解决这些不确定问题。 为此， 人们提出了一些解决 方法，如统计方法、模糊集( f u z z y s e t ) 理论以 及d e m p s t e r - s h a f f e r 证据理论。但 这些方法都有一些内在缺陷或限定范围。 例如， 基于统计的方法在理论上还令人难 以 信服， 而模糊集方法则存在的问 题是如何确定成员隶属度。 相比之下， 粗糙集方 法则有几个优点: 不需要预先知道的额外信息，如统计中要求的先验概率和模糊集 中要求的隶属度;算法简单，易于操作。 粗糙集对不精确概念的描述方法是: 通过上近似概念和下近似概念这两个精确 概念来表示。一个概念( 或集合) 的下近似( l o w e r a p p r o x i m a t i o n ) 概念( 或集合) 指 的是，其下近似中的元素肯定属于该概念; 一个概念( 或集合) 的上近似( u p p e r a p p r o x i m a t i o n ) 概念( 或集合) 指的 是，其上近似中的元素可能属于该概念。 人工神经网络( a r t i f i c i a l n e u r a l n e t w o r k s ) 在k d d 出 现以 前， 人工神经网 络的学习算法就己 广泛的 运用于许多机器学习系 统。 传统的神经网络算法推导出的模型可理解性较差，且运行效率不高，因而不宜 第 7页 直接用于数据挖掘: 发现的知识的可理解性和运行效率在实际应用中都是决定性的 因素。 而近年来该方向的发展己逐步克服了这两个弱点。目 前的算法已可以从受约 神经网络( t r a i n e d n e u r a l n e t w o r k s ) 中提取用符号表示的规则，或推导出可理解 的模型， 且效率己 有较大的提高。 此外，对于某些性质的问 题而言，使用神经网络 更合适。 决策树( d e c i s i o n t r e e ) 决策树方法的起源是概念学习系统( c o n c e p t l e a r n i n g s y s t e m s , c l s ) ， 然后 发展到i d 3 方法为高潮， 最后又演化为能处理连续属性的c 4 . 5 ， 有名的决策树方法 还有c a r t 和a s s i s t a n t 。 决策树构造的输入是一组带有类别标记的 例子， 构造的结 果是一棵二叉或多叉树。二叉树的内部节点( 非叶子节点) 一般表示为一个逻辑判 断， 如形式为( a i = v i ) 的逻辑判断， 其中a 。 是属性， v 。 是该属性的某个属性值; 树的 边是逻辑判断的分支结果。多叉树( i d 3 ) 的内部节点是属性，边是该属性的所有取 值，有几个属性值，就有儿条边。树的叶子节点都是类别标记。 构造决策树的方法是采用自 上而下的递归构造。以多叉树为例，它的构造思路 是， 如果训练例子集合中的所有例子是同类的， 则将之作为叶子节点，节点内容是 该类别标记。否则，根据某种策略选择一个属性，按照属性的各个取值， 把例子集 合划分为若干子集合，使得每个子集上的所有例子在该属性上具有同样的属性值。 然后再依次递归处理各个子集。 这实际 上就是 “ 分而治之”( d i v i d e a n d c o n q u e r ) 的思路。 概念格( c o n c e p t l a t t i c e ) 概念格的思想源于哲学中的形式概念， 上世纪8 0 年代初， w i l l e 教授在文中 提 出由 二元关系来建造相应概念格的 基本思想。这种特殊形式的格结构及其相应的 h a s s e 图就反映了一种概念层次结构， 它本质上描述了对象和属性之间的联系，表 明了 概念间的 泛化与例化关系， 同时体现了 概念内 涵和外延的统一。 作为 概念分析 的一种形式化工具，概念格己 经广泛地应用于软件工程、知识工程等领域。 在挖掘规则知识过程中， 规则本身是用内涵集之间的关系来描述的， 而体现于 相应外延集之间的包含( 或近似包含) 关系。 概念格结点反映了概念内涵和外延的统 一， 结点间关系体现了概念之间的泛化和例化关系， 因此非常适合作为规则发现的 基础性数据结构。为了将概念格用于知识规则发现领域，g o d i n 和王志海等分别提 第 吕页 出了由 概念格来提取蕴涵规则的算法。 覆盖正例排斥反例方法 它利用覆盖所有正例， 排斥所有反 例的思想来寻找规则。 a q 系列的核心算法是 在正例集中任选一个种子， 它到反例集中逐个比较， 对字段取值构成的选择子相容 则舍去，相斥则保留。按此思想循环所有正例种子，将得到正例集的规则( 选择子 的合取式) 。 a e 系列方法是在扩张矩阵中寻找覆盖正例排斥反例的字段值的公共路 径 ( 规则) 。 遗传算法 这是模拟生物进化过程的算法。 它由三个基本算子组成: 繁殖( 选择) : 从一个 旧种群( 父代) 选择出生命力强的个体产生新种群( 后代) 的过程。交叉( 重组) : 选 择两个不同个体( 染色休) 的部分( 基因) 进行交换，形成新个体。变异( 突变) : 对 某些个体的某些基因进行变异( 1 变0 , 0 变1 ) 。 这种遗传算法起到产生优良 后代的作用。 这些后代需要满足适应值， 经过若干 代的遗传， 将得到满足要求的后代( 问题的解) 。 遗传算法已在优化计算和分类机器 学习方面发挥了显著的效果。 公式发现 在工程和科学数据库( 由实验数据组成) 中对若干数据项( 变量) 进行一定的数 学运算， 求得相应的数学公式。 例如， 物理定律发现系统 b a c o n , b a c o n发现系统 完成了物理学中大量定律的重新发现。 它的基本思想是对数据项进行初等数学运算 ( 加、减、乘、除等) 形成组合数据项，若它的值为常数项，我们就得到了组合数据 项等于常数的公式。 统计分析方法 利用统计学原理对数据库中的数据进行分析。 以下介绍几种常用的统计分析方 法: ( 1 ) 常用统计: 求大量数据中的最大值、最小值、总和、平均值等。 ( 2 ) 相关分析: 求相关系数来度量变量间的相关程度。 ( 3 ) 回归分析: 求回归方程( 线性或非线性) 来表示变量间的数量关系。 ( 4 ) 差异分析: 从样本统计量的值得出差异， 来确定总体参数之间是否存在差异 ( 假设检验) 。 第，页 ( 5 ) 聚类分析: 直接比较样本中各样本之间的距离， 将距离较近的归为一类。 而 将距离较远的分在不同类中。 ( 6 ) 判别分析: 建立一个或多个判别函数， 并确定一个判别标准。 对未知对象利 用判别函数将它划归某一个类别。 模糊数学方法 利用模糊集合理论对实际问 题进行模糊评判、 模糊决策、 模糊模式识别和模糊 聚类分析。 由 于模糊性是客观的存在， 而且系统的复杂性愈高， 精确化能力便愈低， 这就意味着模糊性愈强。以上提到的模糊方法都取得了较好的效果。 可视化技术 可视化数据分析技术拓宽了传统的图表功能， 使用户对数据的剖析更清楚。 例 如把数据库中多维的数据变成多种图形， 这对于揭示数据中的状况，内在本质以及 规律性起到很强的作用。 1 . 3 . 4数据挖掘算法的评价 数据挖掘总的有效性可以从以下三个方面来衡量: ( 1 ) 精确度: 精确度的大小将直接影响到商业的利润和投资回报， 精确度越高其可 用性就越强， 就越有利于做出正确的决策。 精确度将决定于算法的设计和历史数据 量以及用户的期望值，所以有些时候不得不在精度和速度之间折衷。 ( 2 ) 速度: 虽然决策支持要操作海量的历史数据， 速度不是主要的但是速度仍然是 需要考虑的因素， 毕竟数据量在不停地膨胀。因此算法必须是实际可行的，数据处 理的并行、分布以 及高效的数据分片都是提高速度的有效方法。 ( 3 ) 开销: 花销将最终决定是否采用数据挖掘进行决策支持， 好的算法不应该是开 销巨大的， 应该有很好的可移植性，不依赖于特定的环境和硬件。 1 . 3 . 5数据挖掘的发展趋势 目 前， 数据挖掘技术的研究还不够成熟， 其应用还有较大的局限性。当前数据 挖掘研究和应用主要面临一下问 题: ( 1 ) 挖掘的对象: 更大型的数据库、更高的维、更多属性之间的更复杂的关系。 数据挖掘要处理的数据量通常是十分巨大的。 成百上千的数据表， 几百万条事务记 录， 数据库容量达到g b 字节， 甚至t b 字节。目 前的研究发展到用并行处理或抽样 ( s a m p l i n g ) 的方法处理大规模数据，获得了 较高的计算效率。 第 1 0页 ( 2 ) 多种形式的输入数据: 目 前数据挖掘工具能处理的数据形式有限。一般可以 处理数值型的结构化数据， 但大多不能对文本、图形、 数学公式、图像或w e b 资源 等这些半结构、无