数据挖掘系统设计

1、2000年9月文章编号:100026788(2000 0920056208系统工程理论与实践第9期数据挖掘系统设计汤宇松, 刘相峰, 黄亚楼, 卢桂章(南开大学计算机与系统科学系, 天津300071摘要:随着海量数据库技术的不断发展, 出现了数据丰富但知识贫乏的现象为解决这一问题, 近年来, 提出了数据挖掘(D ata M ining 和知识发现(KDD 技术本文介绍了数据挖掘系统的概念及具体的运做流程, 并提出了一个原形系统的构建模型最后, 指出在数据挖掘技术发展中面临的一些问题关键词:数据库; 数据挖掘; 原形系统中图分类号:T P 182A rchetypal D esign fo r

2、D ata M in ing SystemTAN G Yu 2song , L I U X iang 2feng , HU AN G Ya 2lou , LU Gu i 2zhang(D ep t . of Compu ter &System Science , N ankai U n iv . , T ian jin 300071Abstract :In th is paper , w e discu ss the techno logy of data m in ing , analysis how D ataM in ing w o rk s , and give an arch

3、etypal design fo r data m in ing system . In the end , w e. list som e p rob lem s that no t be so lved w ell in the mo st real data m in ing system sKeywords :database ; data m in ing ; archetypal system1引言数据库技术的发展提供了存储海量数据信息的可能, 但当面对越来越多迅速膨胀的超级数据库时, 人们却无从着手去理解数据中包含的信息, 更难以获得有价值的信息! 原有的决策支持系统(D SS

4、已不能满足需要, 人们迫切需要把这些看似分散的数据, 提炼成一条条有价值的信息, 来指导今后的行为随着数据库技术和计算机硬件的进一步发展, 出现了数据挖掘(D ata M in ing 技术, 为解决上述问题提供了较好的方案对于数据挖掘技术的研究, 在国外已经有几年的历史了, 国内也已经起步关于这方面的文章虽然很多, 但往往将重点放在局部的具体挖掘算法上, 很少对整个系统的构建进行论述数据挖掘系统是一个有机的整体, 各个部分之间有着密切的关系, 应该说所有的算法都是为某一个挖掘系统服务的, 如果不仔细的对系统结构进行分析, 势必会导致各种算法之间的重复工作, 从而不利于多种不同算法的嵌入而且对

5、算法来讲, 只有与系统其他模块紧密结合, 才能充分发挥作用为此, 本文从系统的结构入手, 提出一个具有基本功能的系统框架, 对各个部分的数据流和控制流的走向进行较为细致的分析2应用数据挖掘技术的基础和前提数据挖掘是一种从大型数据库或数据仓库中提取隐藏的预测性信息的技术, 它能挖掘出数据间潜在的模式(pattern , 找出最有价值的信息和知识(know ledge , 指导商业行为或辅助科学研究其中, 模式是利用挖掘算法得到的结果, 是对一种可能性分布的简单描述; 知识或信息是通过对模式进行处理而得到的易于理解的结果从广义上讲, 数据挖掘将发现两种类型的模式:预测型的(p redictive

6、和信息型的(info rm ative 模式, 收稿日期:1999201231或分别称做监督型的(supervised 和非监督型的(un supervised 从挖掘过程则亦可称为证明驱动(V erificati on 2driven 或发现驱动(D iscovery 2driven 类型1 预测型的模式, 通过输入集合的值来计算某一属性, 或某几种属性的值, 预测型的模式用来解决一个指定的问题, 从数据库中的一些属性来预测另外一个或多个属性值它的重要特征是利用已知的属性值去合理地猜测一个未知的属性值2 信息型的模式, 用于预测将来要发生的事情; 信息型模式不解决某一个指定问题, 而是提供给

7、某领域的专家以前可能不知道的有兴趣的模式信息型模式比预测型模式难评估, 因为它们的价值在于, 是否提供给某领域专家一些建议和这些建议的有效性数据挖掘工具通过预测未来趋势及行为, 为公司作出前摄的(p roactive 、基于知识的决策在典型的决策支持系统中, 数据挖掘可自动提供对未来情况的分析结果, 这远远超过传统工具所提供的历史情况分析数据挖掘的思想早在计算机应用于商业之初就有, 数据挖掘技术是长期研究和产品不断发展的结果, 随着数据存储技术的发展和实时数据导航技术的出现, 数据挖掘利用并发展了这些技术, 它由四个成熟技术支持:大规模数据采集功能强大的并行处理机数据挖掘算法数据库技术数据挖掘

8、是一个集多种领域知识为一体的综合技术它包含了统计学、机器学习、人工智能、不确定性理论、数据库、知识获取、模式识别、信息抽取、可视化、分布式多媒体环境的智能代理、数字库(D igit L ib raries 和管理信息系统3数据挖掘的过程所有的数据挖掘系统都要有数据准备、执行挖掘算法和表达结果等几个阶段数据挖掘过程细分为以下几个步骤:1 理解和定义问题2 数据的搜集和抽取3 数据净化4 数据引擎5 算法引擎6 运行数据挖掘算法7 评估结果8 重新精化数据和问题9 使用结果上述的九个步骤在数据挖掘过程中要反复多次如下图所示其中, 每一个步骤都是必不可少的, 下面分别讨论各个步骤(图1 :1 理解和

9、定义问题理解和定义问题是解决任何事情的必经步骤, 这个过程往往容易被人们简单化但在数据挖掘过程中, 它却要花费很多的时间数据挖掘不同于一般意义的分析过程, 不是简单的把数据挖掘算法应用到数据库上, 然后得到一些结果因此如果没有很好的理解问题, 得到的结果将没有任何用处一个问题有多种解决办法, 但有些是行得通, 有些是行不通的即使是行得通的办法, 也要考虑其执行效率等方面的问题2 数据的搜集和抽取一旦问题定义完毕, 就要进行相关数据的搜集大多数情况下, 相关数据是从已存在的数据库或数据 图1仓库中提取的通常, 数据挖掘算法不能直接在任何一个随意的数据库中工作我们需要从相关的数据库中提取数据, 并

10、将它们存储为数据挖掘算法可以识别的格式在数据挖掘算法中, 一般采用标准数据库查询语言SQL , 或自行设计DM QL 1因为挖掘算法的大部分时间都花费在对数据库的访问上, 所以通过数据库管理系统的查询引擎, 可以大大提高数据挖掘过程的速度对于实际的数据库系统, 它包含了多个原始的数据库, 这就是后面提到的静态数据库概念而对于某一个特定的挖掘任务, 需要从中提取更进一层的关联数据库, 这就是在实际应用中的定制数据库在大多数情况下, 最好的方法是创建一个全新的数据库, 但这通常是不可行的在统计学中曾经探讨过怎样采集数据的问题, 但将这些方法应用于数据挖掘中来发现复杂模式时, 都不十分合适这是一个有

11、待研究的问题目前, 数据挖掘算法通常是基于一个抽取出来的二维关系表对于用户所提出的发现任务, 确定感兴趣的属性域, 进行各种数据汇集的操作利用抽样技术对数据库中符合条件的元组进行抽样统计学工具已经给出了各种抽样方法、诸如纯随机抽样(简单随机抽样 、机械抽样(等距抽样 、分层抽样、典型抽样等, 具体进行统计运算, 对相同元组进行归并, 增加必要的统计属性域3 数据净化和数据理解一旦搜集完相关的数据, 接下来就要花费一些时间来处理数据库这有两方面的原因:a 数据分析者要理解数据库的内涵, 而不是仅停留在知道数据库中有哪些字段b 在数据搜集的过程中(通常是由几个库抽取出信息组成一个新的数据库 , 不

12、可避免的存在着一些错误另外对于关联库本身, 在产生时经常出现如下的错误:如a 字段值输入错误;b 字段名称发生错误;c 字段内容不详;d 对于同一字段的同一内容的不同表达方式, 也可能会造成算法对数据含义理解的不确切性净化带噪音的数据是一个复杂、牵扯到多方面的过程数据净化过程的步骤, 按顺序如下:检查拼写错误去掉重复的(D up licate 记录补上不完全的(Incomp lete 记录解决不一致的(Incon sisten t 记录用测试查询来验证数据根据验证结果反复迭代上述步骤数据净化的目标是保证所表达数据的一致性(Con sisten tly , 确保数据的参照完整性(R eferen

13、 tial更改和修复数据, 需要有一个描述整个净化过In tegrity 和数据的精确性为了在将来可以很容易的扩充、程的步骤在数据净化阶段, 通常采用统计学提供的技术来检测异常值, 必要时平滑数据和估计噪音参数用于处理对丢失数据的评估方法也是必要的4 数据引擎前面所涉及的步骤都是在谈论如何产生和净化一个挖掘的基础, 即一个从原始的静态数据库到一个定制数据库的过程这个定制数据库由所有要在数据挖掘过程中使用到的信息组成在这个过程中, 存在着三个问题:在静态数据库中包含了许多可以忽略掉的属性如何选择静态数据库中包含的所有属性的子集, 是一个重点另外, 定制数据库中包含的数据信息量有可能远远超过我们所

14、要求的在有限时间内所能处理的信息量, 因此, 我们必须从中找出样本数据库2存在于定制数据库中的信息, 对于某一特定的问题, 可能有不同的表达方式在数据挖掘的过程中, 探索对这些问题的不同解决方案时, 数据引擎要重复多次来形成针对某个任务的定制数据库对于数据挖掘的全过程而言, 静态数据库只形成一次, 而定制数据库在数据引擎的过程中要形成多次, 以便决定不同属性的使用, 不同样本的大小和对要解决问题的不同的精确定义在生成定制数据库的过程中, 人为的智力因素很多注意到, 大多数成功的机器学习的例子要归功于问题的公式化和表达方式的制定3, 它分别映射为数据挖掘的问题定义和数据规划到此为止, 上述步骤均

15、为整个过程的数据准备阶段, 工作量之大约占全部的60%而且也是较难深入的部分5 算法规划在选择了定制数据库后, 有很多的数据挖掘算法, 但我们需要知道选择哪种算法和怎样应用它算法的选择直接影响着所挖掘模式的质量另外, 即使选定了某一种算法, 这个算法中参数的改变也会影响所产生的模式例如用C 4. 5分类树算法产生的模式, 受参数的影响就很大在许多时候, 有效的数据挖掘算法也可能不能直接用来解决问题, 还需做一些辅助的工作来修改算法这可能因为数据挖掘系统中的工具集不全, 或者还没有一个解决某种特定问题的合适算法6 运行数据挖掘算法如何运行数据挖掘算法是数据挖掘分析者和相关领域专家最关心的阶段因为

16、只有这个阶段才能给出人们所关心的东西这个阶段称之为真正意义上的数据挖掘4所有的数据挖掘算法都要事先提出一些标准来度量产生的模式, 并在搜寻所有模式的过程中, 使用这些标准来决定保留什么, 丢弃什么, 哪些模式需要继续挖掘目前, 通常利用一些简单的统计属性作为评估标准, 如支持度(Suppo rt 、置信度(Confidence 和感兴趣度(In teresting 等对预测型模式好坏的判断比较容易由于可预测型模式是预测某一属性的值, 而这个属性的值又存在于训练集合中, 所以一般来说, 通过把预测的值与存在于训练集中的那个属性的实际输出值相比较, 计算模式的误差程度, 从而做出对模式的评估相比较

17、, 对信息型模式的评估较难, 然而, 一些数学方法可以较有效地找出一些潜在的有兴趣的模式7 结果的初步评估用来评估可预测型模式好坏的方法依赖于所要解决的问题, 所以仅仅给出某种模式的精确度是没有用的最重要的是, 使用模式模拟实际的行为并给出使用它的结果报告但要注意, 由于数据挖掘所找到的模式可能只是某一段时间内的较短暂的规律, 所以即使我们选用了各种评判方法, 如数学的或其他的非客观性的方法, 它也只是一种估测真正的检测只能在实际的应用中进行在实际的应用中, 相关领域的专家对某种模式的解释是很必要的一般来讲, 专家对一种模式的态度可能会是下面几种情况之一:专家对模式很满意, 但是认为他已经知道

18、了模式包含的内容专家对模式很满意, 但是认为他对一些模式所包含的内容感到有些惊奇专家对模式很不满意对于第一种情况, 没有什么不知道的新模式被发现, 所以原有模式可以继续被很好的使用对于后两种情况, 就涉及到有必要重新精化数据挖掘的问题8 重新精化数据和问题如果专家对生成模式的评价是:这不是我想要的那么, 就要重新进行新一轮的数据挖掘过程通常, 数据挖掘的过程是由粗略到细致, 由简单到复杂的过程依照这个原则, 可以很好地在分析者和领域专家之间进行沟通经过几次反复精化之后, 如果模式的执行情况足够好, 而且得到了专家的认可, 就可以进入到使用结果的阶段了在这一部分中, 涉及到对获得的结果或知识的表

19、达问题, 数据可视化(D ata V isualizati on 是一种表达方式数据的可视化问题是数据挖掘中一个重要的组成部分, 它把挖掘到的信息组成和提供成易于做决策的表达方式可以说, 没有提供很好的数据可视化的数据挖掘系统, 不是一个完善的系统目前的绝大多数数据挖掘系统提供的数据可视化部分是各种三维图形的表示9 使用结果在前面讨论了数据挖掘的许多准备工作及论证所挖掘出的模式的有效性一旦当到达了数据挖掘的最后一步, 我们就可以应用基于所发现模式的决策了4数据挖掘系统的原型框架根据上面对数据挖掘过程的论述, 提出一个挖掘系统的原型结构(见图2 图2图2中黑粗线表示各种形式的数据流, 如原始数据

20、、处理后的数据等; 双线代表模式、知识; 细线表示控制流, 即用户对流程的控制信息, 如制定挖掘任务, 选取阈值、选取算法等系统分成三个部分:第9期 数据挖掘系统设计 61 数据流, 构成从原始数据到最终知识这样一个完整的挖掘数据流程, 控制实现模块, 直接控制数据流, 它们是一些处理函数库 用户控制接口, 用户通过它控制整个数据挖掘流程各个阶段的工作 数据流和控制实现模块处于服务器端, 用户控制接口处于客户端 系统的输入是原始数据, 即日常事 务处理所得到的大量原始数据, 可以是多样异构的数据库或文件数据 系统的输出是知识, 即经过挖掘得 到的有价值的信息 知识的表示形式有多种, 如自然语言

21、、 逻辑规则, 图形表示等 系统的运做流程, 首先要从用户提出的要求开始 按照用户的要求, 选取相应的数据, 在此基础上, 由 系统自动或由用户自己选择待发现模式的形式, 找到相应的算法, 自动或人为的制定所需的所有参数, 进 行挖掘 将得到的结果进行知识表达, 自动或人为的根据得到的知识, 进行下一轮的挖掘或填写到知识库 中 每次得到的知识, 不仅仅提交给用户, 还应当以某种形式存储起来, 供系统挖掘新知识时使用, 这样, 就 可以在进行更高层知识的发现时, 不用重新创建所有的数据, 从而达到基于知识的挖掘 下面, 分别论述这 几个模块: 1 用户 数据挖掘是一个知识发现的过程, 需要用户大

22、量的介入 用户可能要担当多种角色: 数据专家, 数据挖 掘专家和相关领域的专家, 相应的, 他所需要承担的工作也是多样的 一般来讲, 用户往往提出一些具体的要求, 而不是无的放矢 通常, 这个要求限定了数据的来源, 应用 的范围, 结果的形式, 评判的标准, 甚至暗含了应该使用什么类型的算法 如: 在服装店中, 经理提出在第二 季度童装的销售中哪些种类的服装销售量相关, 要求发生的概率大概在 70% 以上 这里, 用户限定了数据 的范围是整个数据库中的时间属于第二季度范围内的童装数据部分, 结果的形式为: 任意前件的销售量的 增减其他后件销售量的增减 评判标准是最小可信度为 70% 挖掘算法应

23、选择关联规则类 理者, 而不是数据库专家和数据挖掘专家 2 转换器 挖掘效率, 提高知识发现的起点和准确度 它具有下列子模块: a 数据收集与数据转换 征表示, 减少有效变量的数目, 其操作包括过滤、 剪枝等 该模块不需考虑数据本身的内涵 b 数据简化与数据净化 身的内容的理解 c 元数据 © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 由于用户提出的问题是千差万别的, 所以相对应的结果模式就存在着很大的不同 如: 什么事件发生 将导致另外其他什么事件的发生, 什么事件共同发生, 根据

24、数据推导出暗含的公式, 或指定前件及后件的 个数, 前件或后件中必然包含的项目, 要挖掘出时间序列的关系等等 所有的这些, 在理想的挖掘系统的用 户界面中, 应接受用户以一种接近自然语言提出的问题 因为系统最终面对的使用者绝大部分是高层的管 位于用户层之下的转换器模块, 其目的是接受用户指定的要求, 将其转化为数据库模块的输入参数: 如字段名, 概念层次范围等; 挖掘核心的输入参数: 如结果模式, 算法类型, 相关的参数及评判标准等 3 数据预处理 此模块的输入为转化器的输出中提供的挖掘任务所涉及到的对应于数据库中真正的字段及任务指定 的范围, 输出则为数据挖掘内核提供干净、 准确、 简化的数

25、据 其作用是减少挖掘内核的数据处理量, 提高 主要针对现实中异构和多样的原始数据环境, 将它们转变成易于系统处理的统一格式的数据 数据收 集提供跨平台的多种异构数据库的访问能力, 包括数据接口驱动和内部数据结构 数据转换找到数据的特 数据简化主要有两个途径: 属性选择和数据抽样, 分别针对数据库中的属性与记录 属性选择现有的 算法有 R elief 算法和 LV F 算法, 利用基于数据内容的加权, 主要问题在于权值的表示阈值的确定 基于 Rough Set 的数据浓缩可以同时实现属性和实例的简约 5 该模块完成数据的选择抽取, 简化的数据需要 做净化处理; 完成数据最后的处理, 将抽取的正确

26、可靠的数据提交给挖掘内核 该模块必须参照对数据本 62 系统工程理论与实践 2000 年 9 月 元数据是管理数据的数据, 指导整个数据预处理 对于一个设计较好的数据库系统而言, 除了存储数 据外, 还应具备数据库维护表等, 负责维护数据库 一般来讲, 挖掘任务中往往包含了层次关系的挖掘, 这 就要求数据预处理模块能根据用户的要求, 构建相应的库结构逻辑层次图, 使用户对数据库中包含信息的 范围有所了解, 便于有目的地进行任务的制定 每次挖掘结束所得到的知识, 在将其存入知识库的同时, 还 要反映在这个逻辑层次图上, 便于后续挖掘工作的进行 4 挖掘内核 进行实际的挖掘操作, 从预处理完的数据

27、中发现模式、 规则 该模块实现各种挖掘技术, 每种挖掘技术 构成一个子模块, 它们在功能上是相互独立的 每种挖掘技术包含一些不同的具体实现算法 如最常用的 分类、 聚类、 关联分析和可视化等挖掘技术 分类内核, 发现能够从给定的若干域预测指定域的模式 具体实现方法有决策树、 回归分析、 神经网 络、 统计分析等方法 聚类内核, 将数据划分为若干个子集目前算法有简单距离聚类、 IRCH、 terva l、 SCAN 、 I E B In DB CL QU 等改进的聚类算法 关 联 分 析, 根 据 事 务 同 时 发 生 的 几 率 寻 找 事 务 间 的 关 联 规 则 主 要 算 法 有 A

28、 p rio ri 经 典 算 法、 A p rio riT I , 和 DH P 等改进算法 D 可视化, 从多角度展示数据分布, 利用人本身的观察判断能力发现潜在模式 5 模式表达 挖掘内核得到的模式并不是最终知识, 模式有可能是冗余的, 无效的, 甚至是错误的, 这就需要做进一 步的处理模式表达实现对模式的解释表达, 使用户能够理解, 进而能够做出评估判断该模块主要使用一 些可视化技术和传统的知识表达技术 6 模式管理器 该模块是用户的控制接口, 用户通过它控制整个挖掘流程, 使挖掘工作能够不断反馈进行下去 包括 下列子模块 数据定义, 控制数据预处理模块 定义系统使用的数据结构、 处理

29、操作, 确定一些阈值 挖掘向导, 控制挖掘内核接收从用户对模式判断得到的反馈信息, 调整挖掘技术和挖掘算法, 它包 括技术和算法的选取, 算法参数的设定等 模式筛选, 数据挖掘是一个反复的过程, 过程的终止条件是用户对发现的知识满意, 因此用户对发 现模式的判断和筛选就是整个系统的反馈环节 用户对模式进行判断和筛选, 如果满意, 模式就成为知识, 经过一些表达处理, 添加到知识库里去 如果不满意, 就要反馈作用于挖掘向导, 进而调整挖掘内核的操 作, 实现挖掘流程的继续, 并逐渐接近用户的挖掘目标 5 数据挖掘面临的问题 目前, 数据挖掘技术虽然得到了大范围的应用, 并也取得了显著的成效, 但

30、仍存在着许多尚未解决的 问题 在数据准备阶段, 尚没有较好的方法快速去除或修改噪音数据及处理空缺的数据 挖掘的对象问题数据挖掘需要面对更大型的数据库、 更高的维数和属性之间更复杂的关系而目 前的很多数据挖掘系统还没有建立在较先进的数据仓库基础上 即使建立在关系型数据库的数据挖掘系 统, 也没有深入到考虑各个表, 乃至各子数据库之间关联关系的程度, 而往往只是停留在人为抽取的简单 二维表中, 如交易表 (T ran saction T ab le 数据挖掘系统目前还不能支持多平台, 导致支持的局限性及不易与其他系统集成 在算法执行的过程中, 只考虑算法本身的复杂度, 缺乏对所利用的硬件环境资源的

31、考虑, 从而导致 算法的实际的执行时间过长 多种形式的输入数据 在数据挖掘的定义中所提到的数据的概念, 其范围很广, 包含结构化数据和 © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 第9期 数据挖掘系统设计 63 多种半结构、 无结构的数据类型, 而目前的绝大部分工作还只停留在对结构化数据的研究上 在知识的表达及对问题的解释上, 应超越传统的关联规则的表达形式, 引入模糊的表达概念, 从而 符合实际的状态分布 数据挖掘的结果应能用广义的或多层概念的术语来解释, 目前的系统往往缺乏对整

32、 体挖掘结果的总结与概括 在数据可视化方面, 还只停留在对结果的简单图形描述, 而没有体现到可视化的真正内涵: 即通过 对数据库各个属性及关系的图形描述, 把暗含的关系展现在操作者面前, 通过人的最敏感的模糊识别来发 现深层次的关系 目前, 所有的数据挖掘系统, 由于不是面向任务 ( 或问题 的系统, 而导致系统不易被掌握, 从而偏离 了数据挖掘容易使用的目标 没有较好的算法来确定各种评判标准的阈值, 如支持度、 可信度及感兴趣度的取值 应该使数据挖掘过程的背景知识可用 目前的数据挖掘系统或工具很少能真正让用户参与到挖掘 过程中 将相关领域的知识融入数据挖掘系统中是一个重要但没有很好解决的问题 知识的维护和更新: 新的数据积累可能导致以前发现的知识失效, 这些知识需要动态维护和及时更 新 证实技术的局限, 如何证实所得到的结果, 目前的技术还很不成熟 上面只是目前数据挖掘技术所面临问题的一部分, 这些问题很多是非常困难的 它们的解决, 将使对 数据挖掘技术的研究更加深入 6 结束语 随着各行各业数据量的剧增, 为了从数据中及时、 准确的获取信息, 出现