（计算机应用技术专业论文）教学评测支持原型系统.pdf

摘要 数据仓库和数据挖掘是数据库研究、丌发和应用最活跃的分 支之一。也是决策支持系统的关键因素。数据仓库是个支持管理 决策过程的、面向主题的、”随时间而变的数据集合，它是集成的。 也是稳定的。数据挖掘是采用人工智能的方法对数据库和数据仓 库中的数据进行分析、获取知谚 的过程。它们的结合能更好地为 决策分析系统提供有力的依据。 纵观以往的教学评测系统，缺乏综合分析、辅助决策的能力， 并且对其历史积累的海量信息中隐藏知识的利用无能为力。而教 学评测支持原型系统是教学评估的重要手段，采用先进技术对教 学选课系统产生的数据进行多层次、多角度的分析，利用分析结 果辅助教学决策是保证教学质量、提高教学素质的必然要求。 本文从数据挖掘技术的研究入手，深入研究了关联规贝数掘 挖掘，并在此基础上，对经典的关联规则的挖掘算法a p r i o r i 算法 进行分析，指出其不足之处，提出了新的改进算法。改进的a p r i o r i 算法利用候选集c k 来对数据库进行筛选，减少项集在数据库中遍 历的记录数，从而提高了算法的效率。论文着重阐述了教师测评 模块的设计与实现，并将改进的a p r i o r i 算法应用到教师测评模块 挖掘关联规则，为管理人员提供决策支持。 关键词：数据仓库数据采集联机分析处理数据挖掘 a p r i o r i 算法 a b s t r a c t d a 协w a r e h o u s e 觚dd a 诅m i i l i n ga r et h em o s t t i v eb r a n c h e so f 出瞧b 船e g t u d y i n g ，d e v c l o p i n ga n d 州i o a t i o n ，a n da l s ot 1 e ya r e t h ek c yf 砒r so fd s s d 如w a r e h o u s ei sad e c i s i o ns u p p o n i n g ，s u b j e c t o r i e n t e d ，i n t e g 隅主e d ，s 诹b l e a n dt i m e d e p e n d e n tc o l l e c 廿0 no fd a ：七a d a t am i n i q gi st oa n a l y z ed a t aa n d 删l l i 咒k n o 、v l e d g e 丘o md a t a b a s ea n dw 甜e h o u s eu s m g 也em e 也0 do f 嘣i 丘d a l l l i g e n c e t h eb i n d i n go f 也e mw i up r o v i d eas t r o n gb 船i so f d e c i s i o n 髓a l y z i n gf o re n t e r p r i s e sa i l dr e la _ t e dd e p a n t i l e n t s m o s to ft h ep r e v i o u st e a c h 洫gs y s t e m sa r e 协a th a v en oa b i l i t yo f s y n 也e t i ca 1 1 a l y s i s ，d e c i s i o ns u p p o r t ，a n dt h eu t i l i 删o no f1 1 i d d e nk n o w l e d g e f 0 m s tl l i s t o r yi i l f o r m a t i o n a n a l y s i so ft e a c h i n gm a r 撮g e m e n ti sa n i m p o n a n tw 8 yt o 把a c he v a l u a 士i o n 王ti sn e c e s s a r yt og u a 阳n t e em eq u a l i t yo f t e a c h i n 窖a n di m p r o v et h es 缸行o fs n l d e n t sa n a l y z i n g 硅砖d a t am t 通ei n p r o c e s s e so f t e s t sa 1 1 dt e a c h i n g 、析mt l l er e s u l t so f 删y s i s t h e 幽e s i si n 乜d ( 1 u c e st l l ep r i n c i p l e so fd a t am i r 曲ga n dm em e m o d so f a s s o c i a t i o nr l l l e 协d e t a i l s t e mf b mt h e s ct h e o r y ，t l l ep a p e r 锄a l y s e st h e c l 硒s i ca s s o c i 8 t i o nr i i l ea i g o r i m m a p r i o r i 丘d mt 1 1 e 讲戗i c a l 锄dp r a c 吐c a l p e r s p e c t 沁e t om a k eu pf o ri t sd e f i c i e n c y ，an e wa l g o r i t h mh 嬲b e e n 口r o p o s e d ，w m c h 埘l i z e sc a n d i d a t e sc kt os h r i n km en u m b e ro fr e c o r d si n d a 诅b 硒e t h ea u t h o rp r e s _ t s 血t e n s i v e l yt l l ep 撇船o fd e s i g i l i n gt h e e d u c a t i o nm a n a g 锄e i l ts y s t e m ，e s p e c i a l l yt l l em o d u l eo ft e a c h e r t e s t i n g a p p l i e dt om i sm d u l e ，t h ea d a p t e da p r i 耐a 1 9 0 r i 吐l mm i n e sa m l d t i t i i d eo f a s s o c i a 士i o nm l e sf o rm a n a g c rd e c i s i o n k e yw o r d s ：d a t aw a r e h o u s i n g ( d w ) d a t ac o l l e c t i n g0 n - l i n e a n a i y t i c 曩lp r o c e 鹃i n g ( o l a p ) d a t am i n i g ( d m ) a p r i o r i 柚g o r i t h m 第一章绪论 1 1 引言 进入数字化、信息化时代的二十一世纪，人们对教育的需求日益增 加。随着计算机技术、通信技术、网络技术和多媒体技术在现代教育中 的广泛应用，教学的方式趋于多样化和科学化。而学校选课系统的采用 对提高教学水平起了一定的积极推动作用。如何看待选课系统中出现的 大量数据，并对这些数据进行科学地分析，是一个复杂的系统工程问题。 目前，许多院校使用了学生选课系统。这些系统或多或少实现了某些数 据的简单分析，包括学生所选的课程情况，教师的上课情况等信息。大 量的数据只是简单的放在数据库或文件中，有价值的信息还是被淹没在 数据中。因此甄有的基于关系数据库的分析系统已经不能满足我们的需 求。利用数据仓库和数据挖掘技术对教学过程产生的数据进行多层次分 析，能够解决教学中的问题，保证教学效果，提高教学质量。 教学评测支持原型系统是根据教育目标的要求，按一定的规则对教 学效果做出描述和确定，是教学各环节中必不可少的一环，它的目的是 检查和促进教与学，逐步建立起以促进学校和教师共同发展为根本目标 的教学评测系统，让教学评测系统中评价数据真正成为学校科学管理， 科学决策的重要依据。本文从数据挖掘技术的研究入手，深入研究了关 联规则数据挖掘，并在此基础上，对经典的关联规则的挖掘算法a p r i o r i 算法进行分析，指出其不足之处，提出了新的改进算法。改进的a p r i o r i 算法利用候选集c k 来对数据库进行筛选，减少项集在数据库中遍历的 记录数，从而提高了算法的效率。着重阐述了教师测评模块的设计与实 现，并将改进的a p r i o r i 算接摩用到教师测评模块挖掘关联规则，为管 理人员提供决策支持。 1 2 国内外研究现状 数据挖掘和知识发现( d m k d ) “1 是近年来一个十分活跃的研究领域。 从数据库中发现知识( k d d ) 一词酋先出现在1 9 8 9 年举行的第十一届国 际联合人工智能学术会议上。由美国人工智能协会主办的k 叩国际研讨 会，规模由原来的专题讨论会发展到国际学术大会，研究重点逐步从发 现方法转向系统应用，并且注重多种发现策略和技术的集成，以及多种 学科之间的相互渗透。数据库、人工智能、信息处理、知识工程等领域 的国际学术刊物也纷纷开辟了k d d 专题或专栏。i e e e 的k n o w l e d g ea n d d a t ae n g i n e e r i n g 会刊领先在1 9 9 3 年出版了k d d 技术专刊，所发表的5 篇论文代表了当时k d d 研究的最先成果和动态，较全面地论述了k d d 系统 方法论、发现结果的评价、k d d 系统设计的逻辑方法，集中讨论了鉴于 数据库的动态冗余、高噪音和不确定性、空值等问题，k d d 系统与其他 传统的机器学习、专家系统、人工神经网络、数理统计分析系统的联系 和区别，以及相应的基本对策。不仅如此，在i n t e r n e t 上还有不少k d d 电子出版物，其中以半月刊k n o w l e d g ed i s c o v e r yn u g g e t s 最为权威， 另一份在线周刊为d 黔( d s 代表决策系统) ，1 9 9 7 年1 0 月7 日开始出版。在 网上，还有一个自由论坛d me m a i lc l u b ，人们通过电予邮件相互讨论 嘲k d 的热点问题。而领导整个潮流的嘣k d 开发和研究中心，当数设在美 国e m d e n 的i b m 公司开发部。世界上研究数据挖掘的组织、机构或大学很 多。比较著名的如卡内基梅隆大学、斯坦福大学、麻省理工学院。著名 研究机构如：a c m ( a c ms p e c i a li n t e r e s tg r o u po nk n o w l e d g ed i s c o v e r y i nd a t aa n dd a t am i n i n g ) 、k d n e t ( t h ee u r o p e a nk n o w l e d g ed i s c o v e r y n e t w o r ko fe x c e l l e n c e ) 、n c d m ( t h en a t i o n a lc e n t e rf o rd a t am i n i n g ( n c d m ) a tt h eu n i v e r s i t yo f1 1 l i n o i sa tc h i c a g o ( u i c ) ) 。 随着洲l ( d 研究逐步走向深入，人们越来越清楚地认识到，d m l ( d 的研 究主要有3 个技术支持，即数据库、人工智能和数理统计。由于数据库 文化的迅速普及，用数据库作为知识源具有坚实的基础；在需求的驱动 下，很多数据库学者转向对数据仓库和数据挖掘的研究，从对演绎数据 库的研究转向对归纳数据库的研究。专家系统实质上是一个问题求解系 统，在研制专家系统时，知识工程师首先要从领域专家那里获取知识， 这一过程实质上是归纳过程，是非常复杂的个人到个人之间的交互过 程，有很强的个性和随机性。数理统计是应用数学中最重要、最活跃的 学科之一。 数据挖掘所能发现的知识有如下几种：广义型知识，反映同类事物 共同性质的知识；特征型知识，反映事物各方面的特征知识；差异型知 识，反映不同事物之间属性差别的知识；关联型知识，反映事物之间依 赖或关联的知识；预测型知识，根据历史的和当前的数据推测未来数据； 偏离型知识，揭示事物偏离常规的异常现象。所有这些知识都可以在不 同的概念层次上被发现，随着概念树的提升，从微观到中观，再到宏观， 以满足不同用户、不同层次决策的需求。数据挖掘的研究焦点集中几个 方面，研究专门知识发现的数据挖掘语言，寻求数据挖掘过程中的可视 化方法，使得知识发现的过程能够被用户理解，也便于在知识发现过程 中的人机交互。研究在网络环境下的数据挖掘技术，特别是在i n t e r n e t 上建立数据挖掘服务器，并与数据库服务器配合，实现数据挖掘。加强 对各种非结构化数据的挖掘。数据仓库和数据分析技术都在具体的实用 阶段迈进，同时，在分析能力上，也不断地提高分析水平，希望能够满 足更多的决策分析方面的业务应用。 与国外相比，国内对d m k d 的研究稍晚，没有形成整体力量。目前， 国内的许多科研单位和高等院校竞相开展知识发现的基础理论及其应 用研究。其中，北京系统工程研究所对模糊方法在知识发现中的应用进 行了较深入的研究，北京大学也在开展对数据立方体代数的研究，华中 理工大学、复旦大学、浙江大学、中国科技大学、中科院数学研究所、 吉林大学等单位开展了对关联规则开采算法的优化研究和改造；南京大 学、四川联合大学和上海交通大学等单位探讨、研究了非结构化数据的 知识发现以及w e b 数据挖掘。 1 3 本文的主要内容 本论文针对教学评测系统开发过程所面临的主要问题；数据仓库的 数据建模技术、系统的体系结构、数据仓库应用系统的实现方法、数据 装载和控制机制，0 l a p 技术、数据挖掘算法等进行了比较深入的研究， 利用数据仓库和数据挖掘技术基本实现了教学评测支持系统。主要工作 有： 1 ) 根据系统功能的要求进行了初步调研，基本了解了教学评测系 统的业务流程( 见图1 1 ) ，以及实现该系统所存在的一些需要解挟的问 题。并根据学校现有的各方面条件制订了系统的可行性分析报告。 柳始散据 评价数据 图1 1 教学评测 2 ) 通过分析讨论，从对教师职称、教师学历、教师政治面貌以及 学生评价等方面，制定了衡量教学综合素质的评价指标体系。 3 ) 设计开发评价初始数据处理子系统。主要实现了不同数据源数 据的集成、集成数据的规范化处理、各类评价数据表的自动生成。 4 ) 设计开发数据预处理予系统。数据预处理予系统主要是为数据 挖掘准备数据，将数据变换成适合予挖掘的形式，以保证数据挖掘引擎 能够挖掘出有用的知识。主要实现评价数据从实时操作数据库到数据仓 库的转存、数据变换和空缺属性的数据补齐等功能。 5 ) 在研究了数据挖掘关联规则的a p r i o r i 算法基础上，提出了一种 改进的a p r i o r i 算法，可以提高了算法执行速度和效率，并在系统中实 现。 参评教师可以根据评价数据分析结果对自己的教学情况的优点和 弱点有一个全面客观的认识，并能够制定出有针对性的自我完善措施。 学校可以通过评价信息宏观掌握学校教师的教学情况，作为制定教师进 修、教学质量的改革等教学管理决策的一项重要依据。 第二章数据仓库和数据挖掘 2 1 数据仓库技术 2 1 1 数据仓库的概念 传统的数据库技术是单一的数据资源，即以数据库为中心，进行事 务处理、批处理到决策分析等各种类型的数据处理。近年来，计算机技 术正向着两个不同的方向拓展：一是广度计算，二是深度计算。人们对 以往计算机的简单数据操作提出了更高的要求，希望计算机能够更多地 参与数据分析与决策制定等领域。数据库处理可以大致划分为两大类： 操作型处理和分析型处理。这种分离划清了数据处理的分析型环境与操 作型环境之间的界限，从而由原来的单一数据库为中心的数据环境发展 为一种新环境。这种分离的结果，导致了数据仓库技术的出现和迅速发 展。 数据仓库。3 是面向主题的、集成的、与时间相关的、不可修改、用 于进行战略决策的数据集合。数据仓库作为数据集成的中心点，是将数 据转换为信息的第一步。首先，它为用户提供数据的公共视图，以后解 释这些数据方面更具有灵活性。数据仓库提供了一个稳定的历史信息 源，该信息源对任何用户都是不变的、一致的和可信的。其次，由于对 历史信息有大量的需要，数据仓库可能增长到很大的规模，其设计的出 发点以有效的方法实现这种信息的增长。最后，数据仓库的建立为任何 形式的分析技术提供数据，即：许多数据集市可以从包含在数据仓库中 数据来建立，而不是每个数据集市作为其自身数据的产生者和消费者。 数据仓库的结构如图2 1 所示。 从图2 1 中可以看出，数据仓库系统包括如下几个部分： 源数据部分，数据抽取、转换和装载( e t l ) 部分，以及中央数据 仓库部分。经过这些环节，可以完成将数据从源数据装载到数据仓库中 的过程。 数据集市，根据部门的需要，可以从数据仓库中形成数据集市，以 满足部门级数据分析的需要。 数据访问和分析部分：在数据访问和分析过程中，可以采用o l a p 分析 及数据挖掘技术进行分析，得出有关的分析结果。 图2 1 数据仓库的结构图 2 1 2 数据仓库的开发设计 2 1 2 1 开发流程 1 ) 启动工程。建立开发数据仓库工程的目标及制定工程计划。 2 ) 建立技术环境。选择实现数据仓库的软硬件资源，包括开发平 台、d b m s 、网络通信、开发工具、终端访问工具及建立服务水平目标等。 3 ) 确定主题进行数据建模。根据决策需求确定主题，选择数据源， 对数据仓库的数据组织进行逻辑结构设计。 4 ) 设计数据仓库中的数据库。基于用户的需求，着重于某个主题， 开发数据仓库中数据的物理存储结构，即设计多维数据结构的事实表和 维表。 5 ) 数据转换程序。实现从源系统中抽取数据、清理数据、一致性 格式化数据、综合数据、装载数据等过程的设计和编码。 6 ) 管理元数据。定义元数据，即表示、定义数据的意义及系统各 组成部件之阀的关系。元数据包括关键字、属性、数据描述、物理数据 结构、源数据结构、映射及转换规则、综合算法、代码、缺省值、安全 要求、变化及数据时限等。 7 ) 开发用户决策的数据分析工具。建立结构化的决策支持查询， 实现和使用数据仓库的数据分析工具，包括优化查询工具、统计分析工 具、c s 工具、0 l a p 工具及数据挖掘工具等，通过分析工具实现决策支 持需求。 8 ) 管理数据仓库环境。数据仓库必须像其他系统一样进行管理， 艄倾 ；茎聩 黼碍 包括质量检测、管理决策支持工具及应用程序，并定期进行数据更新， 使数据仓库正常运行。 2 1 2 2 体系结构与实施框架概述 1 ) 体系结构与实施框架概述 在构建数据仓库之前，有一项重要的工作就是确定数据仓库系统 的体系结构它包括三个方面：物理体系结构、逻辑体系结构以及实施方 式。体系结构直接来源于应用的需求，它又决定数据仓库数据集市的 分布以及管理点的分布。体系结构有三种类型：统一的数据仓库；独立 的数据集市；统一的数据仓库+ 从属的数据集市。实施的方式有三种类 型：自上而下；自下而上；两者的混合。实施的方式与体系结构的选择 是独立的，不同的选择可以组合。数据仓库的实施选择如图2 2 。 图2 2 数据仓库的实施选择 每一个步骤都有若干个选择：物理结构可以选择全部集中存储，也 可以选择分布式存储：逻辑结构可以选择集中管理以及分布式管理；实 施方式可以选择自上而下、自下而上以及两者的混合方式。 2 ) 统一的数据仓库 统一的数据仓库是指数据高度集中，访问统一控制，能够满足所有 部门的分析需求，称为企业级的数据仓库，提供统一的数据视图。 3 ) 数据集市”1 数据集市通常用于为单位的职能部门提供信息。分为两种类型：独 立数据集市以及从属数据集市。 如果数据集市不依赖于中央的数据仓库，那么这个数据集市称为独 立数据集市。独立数据集市的逻辑结构如图2 3 。 在数据仓库的实施过程中，对于某些主题的业务分析问题，可能会 按照主题，采用数据集市的方式对数据进行进一步的组织。所以在数据 仓库的基础上根据分析需求会创建响应的从属的数据集市。从属数据集 市的数据直接来自于数据仓库。采用这种方式，可以较好地保持整体数 据的一致性。 图2 3 独立数据集市的逻辑结构 2 1 2 3 数据抽取，村伙，w w 飘、【l ，n 1 ) 数据的抽取( e x t r a c t i o n ) 数据的抽取是数据进入仓库的入口。由于数据仓库是一个独立的数 据环境，它需要通过抽取过程将数据从联机事务处理系统、外部数据源、 脱机的数据存储介质中导入数据仓库。数据抽取在技术上主要涉及互 连、复制、增量、转换、调度和监控等几个方面。数据仓库的数据并不 要求与联机事务处理系统保持实时的同步，因此数据抽取可以定时执 行，但多个抽取操作执行的时间、相互的顺序、成败对数据仓库中信息 的有效性则至关重要。目前市面上提供了一些数据抽取工具，这些工具 通过用户选定源数据和目标数据的对应关系，会自动生成数据抽取的代 码。但毕竟抽取工具支持的数据种类是有限的：而数据抽取过程涉及数 据的转换，它是与实际应用密切相关的部分，使得往往需要嵌入用户编 程来完成数据抽取工作。 2 ) 数据转换( t r a n s f o r m a t i o n ) 数据转换是指对从业务系统中抽取的源数据根据数据系统模型的 要求，进行数据的转换、清洗、拆分、汇总等处理，保证来自不同系统、 不同格式的数据的一致性和完整性，并要求装入数据仓库。采用数据转 换抽取过程中进行数据转换时，必须考虑抽取的性能以及对业务系统性 能的影响：采用异步数据加载并以文件方式处理时，必须充分考虑中间 磁盘的存储量以及e t l 整个流程的协调性工作，以及大量的非s q l 语句的 编程；采用在数据加载过程中进行数据转换时，必须考虑加载性能；采 用先将数据加载到数据仓库后处理时，必须考虑数据仓库引擎的海量数 据处理能力。 3 ) 数据加载 数据加载就是将从数据源系统中的抽取、转换后的数据加载到数据 仓库系统中。数据加载策略要考虑加载周期及数据追加策略两方面的内 容。数据的追加策略根据数据的策略以及业务规则确定，一般有三种类 型：直接追加、全部覆盖、更新追加。在实施系统中，具体采取何种方 式，要综合考虑效率、业务实现等因素。 2 1 2 4 构建数据仓库设计的关键问题 1 ) 数据仓库粒度问题 粒度问题是设计数据仓库的一个最重要方面。所谓的粒度，指数据 仓库的数据单位中保存数据的细化或综合程度的级别。细化程度越高， 粒度级别就越小。在数据仓库环境中，粒度之所以是主要的设计问题， 是因为它影响存放在数据仓库中的数据量的大小，越小的粒度能够回答 的问题越细致，也会增加数据仓库的数据量，从而增加存储设备的成本。 所以，在设计数据仓库时，一个重要的设计方面就是根据应用的特点， 在数据仓库中的数据量大小与满足查询的能力作出权衡。如果实际中处 理数据量极大，需要采用多重粒度。通过在数据仓库的细节级创建多重 粒度缴，可以在数据仓库中的数据量大小与查询的详细程度之间进行比 较好的平衡。如果什么时候需要分析更低的细节级，则可以到数据的最 底层。综合考虑建造成本、访问效率、访问和回答查询的能力，才决定 采用数据粒度的级别。 2 ) e t l 的处理策略。 数据抽取策略：数据抽取过程中，有多种可选的策略，表2 1 对这 些策略进行了比较。 表2 一l 数据抽取策略进行了比较 抽取策略比较点 同步实时抽取 异步数据抽取 业务系统数据源或其他系 业务系统数据源或其他 输入对象系统数据源提供的数据 统数据源 文件 源数据系统资源占用不占用 源数据适用类别变化更新数据流水型增长数据 数据量较小海量 数据逻辑 复杂 简单 源数据提供者需要做较 实施复杂程度由系统开发者自主掌握 多的接口工作 一般，若源数据系统按需求 安全性进行严格的数据授权可获高，与源数据系统隔离 得较好安全性 数据转换策略：表2 2 是转换方法以及各种方法相应的特点比较。 表2 2 是转换方法以及各种方法相应的特点比较 转换方法比抽取过程进 以文件方式数据加载过进入数据仓库 处理，异步数程中进行数以后再进行数 较点 行数据处理 据加载据处理据处理 转换效率低尚低高 机器处理能机器处理能机器处理能 力、源数据类力、源数据类力、源数据类数据仓库引擎 限制因素 别、数据逻辑别、数据逻辑别、数据逻辑的处理能力 复杂程度复杂稃度复杂程度 变化更新数 流水型增长 源数据类别所有数据所有数据 据数据 都可以，但需要 源数据逻辑 复杂简单复杂自己写内存过 复杂程度 程 实现复杂程 可利用工具 建议自己根 可利用工具 较复杂，且难以 产生转换逻 据数据源结 产生转换逻 度构，构造转换维护 辑 辑 程序 转换方法比 抽取过程中以文件方式数据加载过进入数据仓库 进行数据处处理，异步数程中进行数以后再进行数 较点 理 据加载据处理据处理 可能需要第可能需要第可能需要第不需要，成本较 投资保护 2 方t 且 三方工具 三方工具低 需要断点处 断点处理重新处理 重新处理重新处理 理 一般，如果数 安全性据源进行授高高 高 权可提高 转储空间不需要需要可能需要 不需要 生成适合数 一般直接输 据仓库导入 一般直接输 输出对象山到数据仓 的文件，再由 出到数据仓 输出到数据仓 数据仓库导库 库库 入一t ：具加载 到数据仓库 2 2 数据挖掘技术 2 2 1 数据挖掘的概念 数据挖掘是从大型数据库或者数据仓库中发现并提取隐藏在其中 的信息或者知识的过程。目的是帮助分析人员寻找数据之间的关联，发 现被忽略的要素，而这些信息对于预测趋势和决策行为是十分有用的。 数据挖掘是通过对文件系统和数据库中的数据进行分析，获得具有一定 可信度知识的算法和技术。它从不同侧面完成对决策过程的支持，相互 间有一定的内在联系。因此，将它集成到一个系统中，形成基于数据开 采的o l a p 工具可以更加有效的提高决策支持能力。数据挖掘的具体定义 为“数据挖掘是一个从大型数据库中抽取隐含的、事先未知的、具有潜 在有用的信息或知识的非平凡过程”。其流程图如图2 4 所示。 预 知 识 图2 4 数据挖捅过程 从广义上理解数据、信息也是知t 的表达形式，但人们更将概念、 规则、模式、规律和约束等看成知识。人们将数据看作形成知识的源泉， 原始数据可以是结构化的；也可以是半结构化及非结构化的，如文本、 图像等数据。发现知识的方法可以是数学的、非数学的、演绎的和归纳 的。发现的知识可以用于信息管理、查询优化、决策支持和过程控制等。 它把人们对数据的应用从低层次的简单查询提升到从数据库中挖掘知 识，提供决策支持。 2 2 2 数据挖掘的步骤“1 数据挖掘是一个利用各种分析工具在数据中发现模型和数据闯关 系的过程。这种模型和关系可以用来做出预测。基本数据挖掘步骤一般 包括以下三部分：数据的准备、模型的建立、模型的验证和评价。 1 ) 数据的准备 数据的准备包括数据取样、数据特征探索、分析和预处理，同时要 明确问题，选择适合的数据，必要时要进行调整。具体说来，例如计算 统计变量，再用图表或图片直观地表示出来，进而可以看出一些变量之 间的相关性。选择正确的数据源对整个数据挖掘项目的成败至关重要。 数据取样要把好数据的质量关，注意数据的完整性和有效性。 2 ) 建立模型 这一步是数据挖掘工作中的核心环节。对建立模型来说，要记住的 最重要的事就是它是一个反复的过程。仔细考察不同的模型以判断哪个 模型最有用，一旦决定挖掘类型后，就需要选择模型的类型。模型的类 型可能是一棵决策树、神经网络、甚至传统的数学统计。选择什么样的 模型决定了需对数据做哪些预处理工作。 3 ) 验证和评价模型 从上述过程中将会得出一系列的分析结果、模式或模型，评价的办 法之一是直接使用原来建立模型的样板数据来进行检验。另一种办法是 另外找一批数据，已知这些数据反映了客观实际的规律性。再一种办法 是在实际运行的环境中取出新鲜数据进行检验。 一般来说，使用模型得到的如果是一个直接的结论，则当然很好， 但是，这种情况非常少，更多的时候得出合理的是对目标问题的侧面描 述，这时要总结它们的规律性，提供合理的决策信息。所谓合理，实际 上是在所付出的代价和达到预期目标的可靠性的平衡上做出选择。假如 在数据挖掘中，就预见到最后要进行这样的选择，那么最好把这些平衡 的指标尽可能地量化，以利于综合抉择。 4 ) 模型的实施 模型建立并经过验证之后，可以有两种主要的使用方法。第一种是 提供给业务人员或分析人员做参考，通过察看和分析这个模型之后提出 行动方案建议。另种是把此模型应用到不同的数据集上。模型可以用 来标识一个事例的类别。还可以用模型在数据库中选择符合特定要求的 记录，并用o l a p 工具做进一步的分析。数据挖掘的步骤如图2 5 。 数据准各1 数据取丰羊人特征分析大预处理 模型建立 l 决策树人神经阿络人统计分析 序列分析 验证和评价 l 结论分析人调整数据人调整模型 实施 提交业务y 提交分析t 进一步 、人员人员分析 图2 5 数据挖掘的步骤示意图 2 2 3 数据挖掘的方法和技术 数据挖掘的技术基础是人工智能。人工智能是以自动机为手段，通 过模拟人类宏观外界的思维行为，从而高效率地解决现实世界问题的科 学和技术。下面介绍数据挖掘的几种常用方法： 1 ) 人工神经网络( a r t i f i c i a ln e u r a l t w o r k s ) 神经网络为解决大量复杂度问题提供了一种相对来说比较有效的 简单方法。神经网络可以很容易的解决具有上百个参数的问题( 当然实 际生物体中存在的神经网络要比我们这里所谎的程序模拟的神经网络 要复杂的多) 。神经网络常用于两类问题：分类和回归。 在结构上，可以把一个神经网络划分为输入层、输出层和隐含层， 如图2 6 所示。输入层的每个节点对应一个个的预测变量“1 。输出层的 节点对应目标变量，可有多个。在输入层和输出层之间是隐含层( 对神 经网络使用者来说不可见) ，隐含层的层数和每层节点的个数决定了神 经网络的复杂度。 输入层隐含层输出层 图2 6 神经网络结构图 除了输入层的节点，神经网络的每个节点都与很多它前面的节点 ( 称为此节点的输入节点) 连接在一起，每个连接对应一个权重，此节 点的值就是通过它所有输入节点的值与对应连接权重乘积的和作为一 个函数的输入而得到，我们把这个函数称为活动函数或挤压函数。 神经网络的每个节点都可表示成预测变量的值或值的组合。实际上 如果没有活动函数的话，神经元网络就等价于一个线性回归函数，如果 此活动函数是某种特定的非线性函数那神经网络又等价于逻辑回归。 调整节点间连接的权重就是在建立( 也称训练) 神经网络时要做的 工作。最早的也是最基本的权重调整方法是错误回馈法，现在较新的有 变化坡度法、类牛顿法、l e v e n b e r g m a r q u a r d t 法、和遗传算法等。无 论采用那种训练方法，都需要有一些参数来控制训练的过程，如防止训 练过度和控制训练的速度。 决定神经网络拓扑结构( 或体系结构) 的是隐含层及其所含节点的 个数，以及节点之间的连接方式。要从头开始设计一个神经网络，必须 要决定隐含层和节点的数目，活动函数的形式，以及对权重做哪些限制 等，当然如果采用成熟的软件工具的话，它会帮你决定这些事情。 在诸多的神经网络中，常用的是前向传播式神经网络，其过程如下： 前向传播”3 ：数据从输入到输出的过程是一个从前向后的传播过程， 后一节点的值通过它前面相连的节点传过来，然后把值按照各个连接权 重的大小加权输入活动函数再得到新的值，进一步传播到下一个节点。 回馈：当节点的输出值与我们预期的值不同，也就是发生错误时， 神经网络就要“学习”( 从错误中学习) 。我们可以把节点间连接的权重 看成后一节点对前一节点的“信任”程度( 它自己向下一节点的输出更 容易受它前面那个节点输入的影响) 。学习的方法是采用惩罚的方法， 过程如下：如果一节点输出发生错误，那么它看它的错误是受哪个( 些) 输入节点的影晌而造成的，是不是它最信任的节点( 权重最高的节点) 陷害了它( 使它出错) ，如果是则要降低对它的信任值( 降低权重) ，惩罚 它们，同时升高那些做出f 确建议节点的信任值。对那些收到惩罚的节 点来说，它也需要用同样的方法来进一步惩罚它前面的节点。就这样把 惩罚一步步向前传播直到输入节点为止。 对训练集中的每一条记录都要重复这个步骤，用前向传播得到输出 值，如果发生错误，则用回馈法进行学习。当把训练集中的每一条记录 都运行过一遍之后，我们称完成一个训练周期。要完成神经网络的训练 可能需要很多个训练周期，经常是几百个。训练完成之后得到的神经网 络就是在通过训练集发现的模型，描述了训练集中响应变量受预测变量 影响的变化规律。 由于神经网络隐含层中的可变参数太多，如果训练时间足够长的 话，神经网络很可能把训练集的所有细节信息都“记”录下来，而不是 建立一个忽略细节只具有规律性的模型，我们称这种情况为训练过度。 显然这种“模型”对训练集会有很高的准确率，而一旦离开训练集应用 到其他数据，很可能准确度急剧下降。为了防止这种训练过度的情况， 我们必须知道在什么时候要停止训练。在有些软件实现中会在训练的同 时用一个测试集来计算神经网络在此测试集上的正确率，一旦这个正确 率不再升高甚至开始下降时，那么就认为现在神经网络已经达到做好的 状态了可以停止训练。 神经元网络和统计方法在本质上有很多差别。神经网络的参数可以 比统计方法多得多。参数通过各种各样的组合方式来影响输出结果，以 至于很难对一个神经网络表示的模型做出直观的解释。实际上神经网络 也正是当作“黑盒”来用的，不用去管“盒子”里面是什么，只管用就 行了。在大部分情况下，这种限制条件是可以接受的。比如银行可能需 要一个笔迹识别软件，但它没必要知道为什么这些线条组合在一起就是 一个人的签名，而另外一个相似的则不是。在很多复杂度很高的问题如 化学试验、机器人、金融市场的模拟以及语言图像的识别等领域神经网 络都取得了很好的效果。 神经网络的另一个优点是很容易在并行计算机上实现。可以把它的 节点分配到不同的c p u 上并行计算。 在使用神经网络时有几点需要注意：神经网络很难解释，目前还没 有能对神经网络做出显而易见解释的方法学。神经网络会学习过度，在 训练神经网络时一定要恰当的使用一些能严格衡量神经网络的方法，如 前面提到的测试集方法和交叉验证法等。这主要是由于神经网络太灵 活、可变参数太多，如果给定足够的时间，它几乎可以“记住”任何事 情。除非问题非常简单，训练一个神经网络可能需要相当可观的时间爿 能完成。当然，一旦神经网络建立好了，在用它做预测时运行时还是 很快的。 建立神经网络需要做的数据准备工作量很大。一个很有误导性的神 话就是不管用什么数据，神经网络都能很好地工作并做出准确的预测。 这是不确切的，要想得到准确度高的模型必须认真的进行数据清洗、整 理、转换、选择等工作，对任何数据挖掘技术都是这样，神经网络尤其 注重这一点。比如神经网络要求所有的输入变量都必须是o l ( 或 一1 + 1 ) 之间的实数。 2 ) 遗传算法”1 ( g e n e t i ca l g o r i t h m s ) 遗传算法是模拟生物进化过程的算法，由三个基本算子( 或过程) 组 成： 繁殖( 选择) 。即从一个旧种群( 父代) 选出生命力强的个体，产生新 的种群( 后代) 的过程。 交叉( 重组) 。即对选择两个不同的个体的部分进行交换，形成新个 体的过程。 变异( 突变) 。即对某些个体的某些基因进行变异( 0 变l ，或1 变0 ) ，形 成新个体的过程。 这种遗传算法可起到产生优良后代的作用。这些后代需满足适应值， 经过若干代的遗传，将得到满足要求的后代( 即问题的解) 。遗传算法已 在优化计算和分类机器学习方面发挥了显著作用。 3 ) 决策树方法( d e c i s i o nt r e e s ) 决策树提供了一种展示类似在什么条件下会得到什么值这类规则 的方法。比如，在贷款申请中，要对申请的风险大小做出判断，决策树 的基本组成部分：决策节点、分支和叶子。决策树中最上面的节点称为 根节点，是整个决策树的开始。决策树的每个节点子节点的个数与决策 树在用的算法有关。如c a r t 算法得到的决策树每个节点有两个分支，这 种树称为二叉树。允许节点古有多于两个子节点的树称为多叉树。 每个分支要么是一个新的决策节点，要么是树的结尾，称为叶子。 在沿着决策树从上到下遍历的过程中，在每个节点都会遇到一个问题， 对每个节点上问题的不同回答导致不同的分支，最后会到达一个叶子节 点。这个过程就是利用决策树进行分类的过程，利用几个变量( 每个变 量对应一个问题) 来判断所属的类别，最后每个叶子会对应一个类别。 数据挖掘中决策树是一种经常要用到的技术，可以用于分析数据， 同样也可以用来做预测。常用的算法有c h a i d ，c a r t ，q u e s t 和c 5 o 。 建立决策树的过程，即树的生长过程是不断的把数据进行切分的过 程，每次切分对应一个问题，也对应着一个节点。对每个切分都要求分 成的组之间的“差异”最大。 各种决策树算法之间的主要区别就是对这个“差异”衡量方式的区 别。在此我们只需要把切分看成是把一组数据分成几份，份与份之间尽 量不同，而同一份内的数据尽量相同。这个切分的过程也可称为数据的 “纯化”。 实际中应用的决策树可能非常复杂。假定我们利用历史数据建立了 一个包含几百个属性、输出的类有十几种的决策树，这样的一棵树对人 来说可能太复杂了，但每一条从根结点到叶子节点的路径所描述的含义 仍然是可以理解的。决策树的这种易理解性对数据挖掘的使用者来说是 一个显著的优点。 然而决策树的这种明确性可能带来误导。比如，决策树每个节点对 应分割的定义都是非常明确毫不含糊的，但在实际生活中这种明确可能 带来麻烦。 建立颗决策树可能只要对数据库进行几遍扫描之后就能完成，这 就意味着需要的计算量较少，而且可以很容易地处理包含很多预测变量 的情况，因此决策树模型可以建立得很快，并适合应用到大量的数据上。 对最终要拿给人看的决策树来说，在建立过程中让其生长得太“枝 繁叶茂”是没有必要的，这样既降低了树的可理解性和可用性，同时也 使决策树本身对历史数据的依赖性增大，也就是说这是这棵决策树对此 历史数据可能非常准确，一旦应用到新的数据时准确性却急剧下降，我 们称这种情况为训练过度。为了使得到的决策树所蕴含的规则具有普遍 意义，必须防止训练过度，同时也减少了训练的时间。因此我们需要有 一种方法能让我们在适当的时候停止树的生长。常用的方法是设定决策 1 6 树的最大高度( 层数) 来限制树的生长。还有一种方法是设定每个节点 必须包含的最少记录数，当节点中记录的个数小于这个数值时就停止分 割。 与设置停止增长条件相对应的是在树建立好之后对其进行修剪。先 允许树尽量生长，然后再把树修剪到较小的尺寸，当然在修剪的同时要 求尽量保持决策树的准确度尽量不要下降太多。 对决策树常见的批评是说其在为一个节点选择怎样进行分割时使 用“贪心”算法。此种算法在决定当前这个分割时根本不考虑此次选择 会对将来的分割造成什么样的影响。抉句话说，所有的分割都是按顺序 完成的，个节点完成分割之后不可能以后再有机会回过头来再考察此 次分割的合理性，每次分割都是依赖于它前面的分割方法，也就是说决 策树中所有的分割都受根结点的第一次分割的影响，只要第一次分割有 一点点不同，那么由此得到的整个决策树就会完全不同。那么是否在选 择一个节点的分割的同时向后考虑两层甚至更多的方法，会具有更好的 结果呢? 目前我们知道的还不是很清楚，但至少这种方法使建立决策树 的计算量成倍地增长，因此现在还没有哪个产品使用这种方法。 而且，通常的分割算法在决定怎么在一个节点进行分割时，都只考 察一个预测变量，即节点用于分割的问题只与一个变量有关。这样生成 的决策树在有些本应很明确的情况下可能变得复杂而且意义含混，为此 目前新提出的一些算法开始在一个节点同时用多个变量来决定分割的 方法。 决策树很擅长处理非数值型数据，这与神经网络只能处理数值型数 据比起来，就免去了很多数据预处理工作。甚至有些决策树算法专为处 理非数值型数据而设计，因此当采用此种方法建立决策树同时又要处理 数值型数据时，反而要做把数值型数据映射到非数值型数据的预处理。 4 ) 关联分析1 ( a s s o c i a t i o n s ) 从用户指定的数据库中挖掘出满足一定条件的依赖性关系。关联规 则形如“a 1 = a 2 ，支持度( s u p p o r t ) = s ，置信度( c o n f i d e n c e ) = c ”， 其中s 和c 是用户指定的支持度和置信度的阀值。这种关联规则挖掘可以 在不同的抽象概念层次上进行。例如r 。：“尿布= 啤酒，支持度= 5 ，置 信度= 5 0 ”与r ：“婴儿用品类： 饮料类，支持度= 2 5 ，置信度= 8 0 ”相 比，r z 在更高的抽象层次上，更为宏观，因而有较大的支持度和置信度， 更适合高层决策需要。 5 ) 序列模式分析( s e q u e n tia lp a tt e r n s ) 序列模式分析和关联分析法相似，其目的也是为了挖掘出数据之间 的联系，但序列模式分析的侧重点在于分析数据间的前后( 因果) 关系。 它能发现数据库中形如“在某一段时间内，顾客购买商品a ，接着购买 商品b ，而后购买商品c ，即序列a 一 b 一 c 出现的频度较高”之类的知识， 序列模式分析描述的问题是：在给定交易序列数据库中，每个序列是按 照交易时间排列的一组交易集，挖掘序列函数作用在这个交易序列数据 库上，返回该数据库中出现的高频序列。在进行序列模式分析时，同样 也需要由用户输入最小置信度c 和最小支持度s 。关联规则中采用的 a p r i o r i 算法也可以用于序列模式的挖掘，因为若长