（信号与信息处理专业论文）排课算法的研究与实现.pdf

排课算法的研究与实现 摘要 本论文以数据集市为基础通过引入粗糙集理论和贪心算法，在研究生院 局域网环境下完成了一个c s 模式的教务排课系统的分析、设计与实现。重点 讨论了建立排课模型、组建面向排课问题的数据集市、设计算法策略以及应用 软件的开发。系统中的开发环境是n ts e v e n 0 操作系统和s q ls e v e r 7 0 数据 库，采用的高级语言是d e l p h i 5 0 。 关键词：排课数据集市粗糙集 a b s t r a c t b a s e do l lt h ed a t am a r k e ta n d t h r o u g h t h et h e o r y o f r o u g h s e ta n d g r e e da l g o r i t h m ， t h i sp a p e rd e s c r i b e st h ea n a l y s i s ，d e s i g n a t i o na n dr e a l i z a t i o no fac sm o d e s c h e d u l i n g s y s t e mi nt h ee n v i r o n m e n to fag r a d u a t es c h o o ll o c a ll o o p e m p h a s i si sp u t0 1 3 t h e c r e a t i o no ft h es c h e d u l i n gm o d e l ，t h eo r g a n i z a t i o no ft h ed a t am a r k e tf o rs c h e d u l i n g p r o b l e m s ，t h ed e s i g n a t i o no fa l g o r i t h m ，a n dt h ed e v e l o p m e n to fa p p l i c a t i o ns o f t w a r e t h ed e v e l o p m e n te n v i r o n m e n to ft h e s y s t e m i sn ts e v e r 4 0 s y s t e m a n ds q l s e v e r 7 0d a t a b a s e w i t hd e l p h i 5 0a st h ep r o g r a m m i n gl a n g u a g e k e y w o r d ：s c h e d u l i n gp r o b l e m d a t am a r k e t r o u g h s e t 摊课算法的 i j i = 究与实现 月l j罱 计算机排课问题是人们一直非常关注、j j 义未能尉满解决的一个现实问题。对于该问 题的研究早在二十世纪六十年代就已经玎始丁】9 6 3 年c c 高特烈给出了课表问题的 数学模型，使之成为数学家和计算机应_ 【1 _ j 专家j 刑研究的课题。但山于在实际巾遇到 了种种困难，因此并未取得满意成果。1 9 7 5 年s 艾温证l 纠了课表问题是n p 一完全的， 宣布了这一时空组合问题的学术地位和难度。 排课问题就其实质而言可咀抽象为个叫削与空问的数学组合问题，即在满足各种 已知约束条件的情况下找出一个最优的时空组合，同时在具体实践上它受到教学组织 形式、客观物质条件等多种因素的相互影响，使这一问题在实际解决时呈现出受具体 条件制约的特点。山此得知，要解决排墚问题1 i 仪要建立完善的逻辑模型，还要深入 了解教学组织形式及其客观或物质条件特点。 目前解决排课问题使用的工具主要为计算机，技术支持手段为数据库技术、人工 智能技术等一些相关的信息处理技术，并已有多家公司推出他们研制的应用系统。由 于排课问题具有要选出最优时空组合的特点，因此可作为专家系统应用的对象进行研 究。课表编排决策专家系统是一种较小规模的决策专家系统，之所以蜕其规模较小， 是由于其决策所需要的信息量相剥缎少，知识涉及的领域不是很广，但是相当具有代 表性。 在人工智能领域中对于信息处理的研究出现了许多新兴的技术和理论，这些技术 和理论极大地丰富了知识获取和信息处理的方法。例如现在流行的数据库中的知识发 现( k d d ) 、粗糙集理论等等。如何将这些新兴的技术手段与排课问题结合起来，为排课 问题的解决寻找一条新思路这是一个颇具挑战性的研究方向。 对于计算时间呈指数增长的n p 一完全问题，我们知道到目前为止，数学上尚没有 找到有效的算法解决，然而有许多n p 一完全问题具有很重要的实际意义，所以只能利 用近似算法来解决，如利用回溯法或限界剪枝法等算法求解。具体到计算机排课这个 n p 一完全问题，首先要对课表编排问题有准确透彻的认识，这里既要抓住排课问题的 抽象本质，又要结合具体单位的各自特点，简化出现实可行的逻辑模型，其次选择好 合适的理论与算法，这样才能实现一个相对实用、优秀的应用系统。 本文共由六章组成，第一章为排课问题的概述，内容包括排课问题的描述、排课 理论以及目前市场上一些流行商业排课软件的简要介绍：第二章介绍有关排课的技术 支持手段与算法；第三章对西电研究生院的教学组织情况进行介绍，抽取领域专家的 先验知识：第四章论述了根据理论结合西电实际确定课表的数学模型，诠释排课思 想，并结合西电具体情况选择出合适的算法；第五章主要介绍了西电排课系统功能模 2 排课算法a i , r f 究与实现 块的划分及如何实现：第六章总结系统设计心得系统存在的缺陷及未来排课问题解 决的发展方向。 排课算法的研究与实现 第一章排课问题概述 1 1 排课问题的描述 排课是将教师与学生在时间和空间上根据不同的约束条件进行排列组台，以使教 学正常进行。这里约束条件主要为避免冲突，所谓冲突，它所包含的内容很广泛，例 如：同一时间对同一名教师安排了两门不同的课程，则对于该教师来说课程的安排是 冲突的，对学生也是如此；同一时间给同一教室安排两门不同的课程则对于这两门课 程来说安排的教室是冲突的。在满足全部约束条件的基础上，对教师、教室、学生及 时间等几部分资源进行最优化组合，以保证整个教学计划正常进行。 在排课问题中要解决的核心问题是避免冲突，这里的冲突主要包括上课时间、教 师、教室以及上课学生等四方面因素。这里讨论的冲突可能涉及上述多个因素。例 如：教师或学生不能在同一时间上两门课，在同一时间应该有足够的教室容纳上课的 学生等等。由于各教学单位的教学组织方式各不相同，因此各单位在解决冲突问题上 的侧重也有所不同，在最终解决排课问题时所采取的策略也不相同。对于中、小学的 教学主要采取的是固定学生上课的教室，由教师来适应上课时间、上课教室。在这种 方式下某一学生旦确定在某个教室上课，那么这名学生的大部分课程就会在这个教 室进行，不同的课程会有不同的教师来这一固定教室上课。在这种情况下上课的单元 是班级即同一班级的学生所上课程都是一样的，流动的只是教师，解决冲突主要是避 免同一教师在同时间上两门或以上的课程，这里的冲突体现在时间、教师之间。而 对于大学高年级的教学组织安排要考虑的就不仅仅是这些了，学生上课并不固定在具 体的某个教室，每个学生的课程由学生自己选择，同一班级的学生所选的课程会有可 能不相同。这里要流动的既包含有教师又包含有学生。同前一情况相比这里不仅要考 虑教师的冲突还要考虑学生的冲突以及教室的安排。 1 2 排课问题的理论研究 排课问题早在7 0 年代初期就已被证明是一个n p 完全问题，即此算法的计算时间 是呈指数增长的，这一论断确立了排课问题的理论深度。对于n p 完全问题目前在数 学上是没有一个通用的算法能够很好地解决。然而报多n p 完全问题具有很重要的实 际意义，例如，大家熟悉地路由算法就是很典型的一个n p 完全问题，路由器要在众 多的节点中找出最短路径完成信息的传递。既然都是n p 完全问题，那么很多路由算 法就可以运用到解决排课问题上，如d i j k s t r a 算法、节点子树剪枝构造网络最短路径 法等等。 4 排课算法f h 研究! i 实现 目前大家对n p 完全问题研究的主要思想是如何降低其计算复杂度，即利用一个 近似算法来替代，力争使得解决i - j 题的n j 问从指数增长化简到多项式增长。结合到课 表问题就是建立一个奋适的现实简约模型，利用陔简约模型能够大大降低算法的复杂 度，便于程序实现，这是解决排课问题一个很好的思路。本文的设计也是基于这样的 出发点。 如何对现实情况简化从而建立简约模型，这一过程是和实际情况紧密结合的，在 具体实现中必须要对实际情况有深刻的认识，逊而能够识别出哪些条件可以忽略，哪 些条件必须考虑，这样才能抽象出一个较为理想的模型。 i 3 市场上的排课软件简介 目前市场上的一些排课软件主要面向以中、小学这样教学组织形式为主的客户 群，它们有这样一些特点：选课的基本单元为班级，学生以班级来区分，课程的冲突 主要以教师冲突来体现，每个班级的课程安排较为固定，变动主要为班级的数量教 师的变动等。这些软件中应用较为广泛的是厦门正信华科技公司开发的正信华【课程 表安排管理系统】，这是一套针对中、小学学校的课程安排而开发的全自动化管理系 统，其主要功能模块包括： 系统管理 包括：系统初始化、系统登录设置、用户管理( 新增用户、修改用户、删除用 户、密码更改) 、系统数据备份与恢复等。 排课管理 i 、课表管理：新建课表、打开课表、删除课表、排课向导。 2 、基本信息设置：班级设置、科目设置、教师设置、上课节数：可对它们进行新 增、插入、修改、删除、打印等。 3 、教学计划设置：课程设置表、教师任课表、备课活动表( 可新增、插入、修 改、删除、打印) 等。 4 、排课计划设置：教师授课表( 可新增、修改、删除、打印) 、班级课程表( 可 对各班级课程进行设置) 、排课条件( 可为各科目设置安排时间，条件可以新增、删 除、打印等) 、科目优先级( 定义哪门课先排，是否可连继安排等) 。 5 、排课管理：教师授课表安排( 分为手工安排与自动安排；可以重新安排、预览 结果、教师调整、教师课时量统计、查询、打印输出等) 、课程表安排( 可以重新安 排、预览结果、课程表调整、另外保存、查嘲、打印输出等) 。 课表查询 可查询各学年、各学期的全校班级课程表、全校教师课程表、班级课程表、教师 课程表、教师任课表、教师授课表、课程设置表、备课活动表等。 排课算法的研究与实现 这套软件的排课思路采用“并行回溯”的算法。所谓并行，是指所有教学班的课 表同时生成；而回溯指的是，在排课过程中，系统自动产生一系列的断点，记录排课 的进度，若安排到某节课找不到满足条件的科目时，则返回到上一节课再作重新安 排，如此循环，直到所有班的课程表安排完为止。课表的安排是采用随机安排的方 式，因此，每次安排的课表都不可能相同。为解决系统中科目安排的顺序，系统引进 必选科目、优先科目的概念。所谓必选科目，就是该班该日必须要安排的科目：而优 先科目，则是根据用户定义的优先级别来安排的。在排课过程中系统遵循以下原则： l 、一个班或一个教师在每一节课中最多只能安排一门课： 2 、一个班的一门课只由一个教师讲授； 3 、用户先输入学校基本信息，并进行排课条件限制的设置，然后排好教师授课 表，根据排好的教师授课表进行课表的安排。 4 、先排设定好的课程，然后是只能排的课、必选课、优先课，最后按优先级从可 选课中选择。 5 、充分考虑课程安排的均匀性和老师授课的均匀性。 6 摊1 ! 算法f 向研究与实现 第二章技术手段与算法研究 对于排课问题传统的技术解决手段主要集中在数据库技术、人工智能技术等领域 中。随着这些年的发展，新理沦与新技术不断出现，极大地丰富了知识获取的方法， 也对排课问题的解决提出了新的思想。本章重点讨论数据仓库、数据挖掘、粗糙集理 论及算法研究等几方面内容。 2 1 数据仓库与数据挖掘t ： 随着信息社会的飞速发展，各行各业的数据存储的规模越来越庞大，例如电信部 门每日的通话信息高达1 0 g b 。面对如此巨量的数据，如何利用这些信息，从海量数据 中发现内在的规律及相关性，并能识别和抽取出潜在的有价值的规则知识，成为日益 关注的问题。数据挖掘技术就是在这样的背景下被提出的。在进行数据挖掘时要处理 大量信息，充足的数据是保证挖掘出正确且有价值规则知识的基础，所以如何组织管 理这些数据成为要迫切解决的问题，数据仓库因此应运而生。 2 1 1 数据仓库 2 1 _ 1 1 什么是数据仓库 目前对于数据库系统大家接触普遍的是关系型数据库，例如：s y b a s e 、o r a c l e 、 i n f o r m i x 等等，它们广泛应用于联机事务处理( o l t p ) 。随着人们对信息功能要求的大 大提高，数据库系统不再仅仅局限于传统的事务处理或操作型处理，而是向分析型处 理发展了。尽管数据库在事务处理方面的应用获得了巨大的成功，但它对分析处理的 支持一直不能令人满意，尤其是当以业务处理为主的联机事务处理( 9 l t p ) 应用与分析 处理为主的决策支持系统( d s s ) 应用若存于一个数据库系统时，这两种类型的处理发生 了明显的冲突。人们逐渐认识到，事务处理和分析处理具有极不相同的性质，直接使 用事务处理环境来支持d s s 是行不通的。 具体来说，事务处理环境不适宜d s s 应用的原因概括起来主要有以下几方面： ( 1 ) 事务处理和分析处理的性能特性不同。 在事务处理环境中，用户的行为特点是数据的存取操作频率高而每次操作处理的 时间短。在分析处理环境中，用户的行为模式与此完全不同，某个d s s 应用程序可能 需要连续运行几个小时，从而消耗大量的系统资源。 ( 2 ) 数据集成问题。 排课算法的研究与实现 d s s 需要集成的数据。全面而正确的数据是有效的分析和决策的首要前提，相关数 据收集得越完整，得到的结果就越可靠。因此，d s s 不仅需要整个企业各部门的相关数 据，还需要企亚内部、竞争对手等处的相关数据。 事务处理的目的在于使业务处理自动化，一般只需要与本部i 3 业务有关的当前数 据。而对整个企业范围内的集成应用考虑很少。当前绝大部分企业内部数据的真正状 况是分散而非集成的。造成这种分散的原因有多种，主要有事务处理应用分散、“蜘 蛛网”问题、数据不一致问题、外部数据和非结构化数据等等。 ( 3 ) 数据动态集成问题。 如果在数据集成后数据源中数据发生了改变，这些变化没有及时反映给决策者， 导致决策者使用过时的数据。对于决策者来说，虽然并不要求随时准确地探知系统内 的任何数据变化，但也不希望他所分析的是过时的数据。因此，集成数据必须以定 的周期进行刷新，我们称其为动态集成。显然，事务处理系统不具备动态集成的能 力。 ( 4 ) 历史数据问题。 事务处理一般只需要当前数据，在数据库中一般也只存储短期数据，且不同数据 的保存期限也不一样即使有一些历史数据保存下来了，也被束之高阁，未得到充分 利用。但对于决策分析而言，历史数据是相当重要的，许多分析方法必须以大量的历 史数据为依托。没有对历史数据的详细分析，是难以把握企业的发展趋势的。 社会的需求推动了技术的发展。人们逐渐尝试对数据库中的数据进行再加工，形 成一个综合的、面向分析的环境，以更好地支持决策分析。数据仓库的思想逐渐开始 形成。但对于什么是数据仓库，许多人提出了不同的看法，我比较赞同的是下面的定 义： 数据仓库就是一个用以更好地支持企业或组织的决策分析处理的、面向主题的、 集成的、不可更新的、随时间不断变化的数据集合。 从上面可以看出数据仓库数据具有四个基本特征：面向主题；集成的；不可更 新；随时间不断变化的。 面向主题的数据组织方式是根据分析要求将数据组织成一个完备的分析领域， 即主题域。主题域应该具有：独立性，这一主题域可以和其他的主题域有交叉部 分，但它必须具有独立内涵，即要求有明确的界限，规定某项数据是否属于该主题。 完备性，即满足对这一主题域进行分析处理所要求的一切内容。 数据是集成的。这里包括两方面的工作：要统一源数据中所有矛盾之处，如 字段的同名异义、异名同义、单位不统一、字长不一致等等。进行数据综合和计 算。数据仓库中的数据综合工作可以在从原有数据库抽取数据时生成，但许多是在数 据仓库内部生成的。 排课算法的研究与实现 数据是不可更新的。数据仓库的数据主要供企业决策分析之用，所涉及的数据 操作主要是数据查询，一般情况下并不进行修改操作。 数据是随时间不断变化的。数据仓库中的数据不可更新是针对应用来说的也 就是浣，数据仓库的用户进行分析处理时是不进行数据更新操作的。但并不是说，在 从数据集成数据仓库输入开始到最终被删除的整个数据生存周期中，所有的数据仓库 数据都是永远不变的。它体现在以下三方面：数据仓库随时间变化不断增加新的数 据内容。数据仓库系统必须不断捕捉o l t p 数据库中变化的数据，追加到数据仓库中 去。数据仓库随时间变化不断删除旧的数据内容。数据仓库的数据也有存储期限， 一旦超过了这一期限，过期数据就要被删除。数据仓库中包含大量的综合数据，这 些综合数据中很多跟时问有关，这些数据要随时间的变化不断地进行重新综合。 需要指出一点，目前数据仓库仍是采用关系数据库技术来实现的，也就是说数据 仓库的数据最终也表现为关系。 2 1 1 2 数据仓库中的数据组织 一个典型的数据仓库的数据组织结构如图3 1 所示。 3 高度综合级 二 轻度综台级 习当前细节级 户早期细节级 图2 i 数据仓库的数据组织结构 在图中我们看到元数据( m e t a d a t a ) 。元数据就是“关于数据的数据”，如传统数据 库中的数据字典。 在数据仓库中的数据分为四个级别，早期细节级、当前细节级、轻度综合级、高 度综合级。源数据经过综合后，首先进入当前细节级，并根据具体需要进行进一步的 综合从而进入轻度综合级乃至高级综合级老化的数据将进入早期细节级。从中可以 看出，数据仓库中存在着不同的综合级别，我们一般称之为“粒度”。粒度越大，表 示细节程度越低，综合程度越高。级别的划分是根据粒度进行的。下面我们介绍数据 仓库中的两个重要概念： 粒度 粒度可以分为两种形式第一种粒度是对数据仓库中的数据的综合程度高低的一 个度量它既影响数据仓库中的数据量的多少也影响数据仓库所能回答询问的种 类。我们容易推想出：粒度越小，细节程度越高，综合程度越低，回答查询的种类就 排课算法的研究与实现9 越多，但这必然造成数据仓库中数据的大量堆积，降低了查询的效率。粒度的提高将 会提高查询效率，但同时也造成回答细节问题能力的下降。另一种特殊形式的粒度， 即样本数据库f 同通常意义的粒度不同，样本数据库的粒度级别不是根据综合程度的 不同来划分的，而是根据采样率的高低来划分的。 分割 分割是数据仓库中的另一个重要数据。它是指将数据分散到各自的物理单元中去 以便能分别独立处理，以提高数据处理效率。数据分割后的数据单元称为分片。进行 数据分割的理由是，我们在进行实际的分析处理时，对于存在某种相关性的数据集合 的分析是最常见的，如对某一时段的数据分析、对特定业务领域的数据分析等等。如 果我们将具有这种相关性的数据组织在一起，无疑会提高效率。 数据仓库中的数据组织形式常见的有几种，如简单堆积文件、轮转综合文件、简 化直接文件、连续文件等。简单堆积就是将每日由数据库中提取并加工的数据逐天积 累地存储起来。轮转综合为将数据存储单位分为几个级别，从低向高依次轮转存储。 简化直接文件可以认为是按一定的时间间隔对数据库的采样。通过比较两个的简单直 接文件的不同而生成连续文件。 2 1 1 3 数据库体系化环境 对一个企业建立一个大而全的数据仓库，并不能取得满意的效果。虽然数据仓库 的数据组织是面向主题的，并为分析的需要保存了许多综合数据，但分析要求干变万 化，我们不可能要求一个单一层次的数据仓库能符合各种各样的分析的需求，数据仓 库的主题需要不断完善，不断调整，综合数据的内容和形式也要灵活多变。另外，随 着数据不断载入，数据仓库将越来越庞大，分析工作若完全基于单一层次的数据仓 库，性能将十分低下，因而需要建立起分层的数据仓库，例如图3 2 中，根据管理层 次的不同需要，在全局级数据仓库的基础上又导出了部门级和个人级数据仓库，全局 级、部门级及个人级数据仓库三者浑然一体，适应不同层次的要求，并与原有的操作 型环境形成了一个多层次的体系化环境。 注： 数据 操作型环境全局级部门级个人级 操作型环境l 。1 - 一 一”表示 图2 2 数据仓库在体系化环境中的位置 从上面数据抽取关系来看，三层数据仓库的实现应该采用“自项向下”的方法， 即先建立一个全局的数据仓库结构，然后再在这一全局数据仓库的基础上建立部门级 0 排深算法的研究与实现 和个人级的数据仓库，这样的建设路径有利于各级数据仓库的一致性的控制。但是， “自顶向下”地建设多级数据仓库必然要求先从原来分散的操作型环境中来建立一个 全局数据仓库。而全局级数据仓库的规模往往较大，在原来分散的操作型环境基础上 建立这样一个大而全的数据仓库，其实施周期长，见效慢，费用昂贵，这些往往是许 多企业不愿意或不能承担的。所以这时一种“自底向上”地建设多级数据仓库的思想 也就自然而然形成了，即就是下面介绍的数据集市的思想。这种思想的核心是，从最 关心的部分开始，先以最少的投资，完成企业当前需求，获得最快的回报然后再不 断完善。 2 1 1 4 数据集市 数据集市是相当于图2 2 中的部门级数据仓库的、小型的、面向部门或工作组的 数据仓库，不同的数据集市可以按业务的分类来组织。当数据集市的数据增长时由 于其结构简单，管理也较容易些。数据集市一般包含有关某一特定业务领域的数据， 如人力资源、财务、销售、市场等。不同的数据集市可以分布在不同的物理平台上， 也可阻逻辑地分布于同一物理平台上。这种灵活性使得数据集市可以独立地实拖，因 而企业人员可以快速获取信息。当更多的主题加入数据集市时，应将这些数据集市加 以集成，最终建立一种结构，即构成企业级数据仓库的数据。数据集市的组织标准是 多样的，除了上述的业务来划分外，也可以按照数据仓库的主题或数据的地理分布来 组织。需要注意的是建立数据集市时，应有全局的观点，使得数据集市在扩展后可 阻集成为全企业级的数据仓库。 2 1 2 联机分析处理( o l a p ) 6 0 年代末，e f c o d d 所提出的关系数据模型促进了关系数据库及联机事务处理 ( o l t p ) 的发展。数据不再以文件方式同应用程序捆绑在一起，而是分离出来以关系表 方式供大家共享。随着政府及商业应用的发展，数据量从8 0 年代的兆( m ) 字节及千兆 ( g ) 字节过度到现在的兆兆( t ) 字节和干兆兆( p ) 字节同时用户的查询需求也越来越复 杂，涉及的已不仅是查询或操纵一张关系表中的一条或几条记录，而且要对多张表中 千万条记录的数据进行数据分析和信息综合。关系数据库系统已不能全部满足这一要 求。这两类应用操作型应用和分析型应用，特别是在性能上难以两全，尽管为了 提高性能，人们常常在关系数据库中放宽了对冗余的限制引入了统计及综合数据， 但这些统计综合数据的应用逻辑却是分散杂乱的，非系统化的，因此分析功能有限， 不灵活，维护困难。在国外，不少软件厂商采取其发展其前端产品来弥补r d b m s 支持 的不足，他们通过专门的数据综合引擎，辅之以更加直观的数据访问界面，力图统一 分散的公共应用逻辑，在短时间内响应非数据处理专业人员的复杂查询要求。1 9 9 3 排课算法的研究与实现 年，e f c o d d 将这类技术定义为“o l a p ”。鉴于t o d d 的影响，o l a p 的提出引起了很 大反响。 o l a p 是针对特定问题的联机数据访问和分析。通过对信息( 这些信息已经从原始的 数据进行了转换) 的很多种可能的观察形式进行快速、稳定一致和交互性的存取，允许 管理决策人员对数据进行深入观察。 o l a p 的实现是基于多维数据库的基础上的，在这里的维是一个很重要的概念，它 是人们观察数据的特定角度。例如，企业常常关心产品销售，所以时间就是一个维( 时 间维) 。人们观察数据的某个特定角度( 即某个维) 还可以存在细节程度不同的多个描述 方面，我们称这多个描述方面为维的层次。一个维往往具有多个层次，例如描述时间 维时，可以从日期、月份、季度、年等不同层次来描述，那日期、月份、季度、年等 就是时间维的层次。维的一个取值称为该维的一个维成员。如果一个维是多层次的， 那该维的维成员是在不同维层次的取值的组合。例如，我们考虑时间维具有日期、月 份、年这三个层次，分别在日期、月份、年上各取一个值组合起来，就得到了时间维 的一个维成员，即“某年某月某日”。根据用户确定的维组成数据立方体，以此来观 察数据进行多维分析。数据的多维分析是指以多维形式组织起来的数据采取切片 ( s l i c e ) 、切块( d i c e ) 、旋转等各种分析动作，以求剖析数据，使最终用户能从多个角 度、多侧面地观察数据库中的数据，从而深入地了解包含在数据中的信息、内涵。多 维分析迎合了人的思维模式，因而减少了混淆并且降低了出现错误解释的可能性。 2 1 3 数据挖掘 确切地讲，数据挖掘( d a t am i n i n g ) 是一种决策支持过程，它主要基于人工智能、 机器学习、统计学等技术，高度自动化地分析企业原有的数据，作出归纳性的推理， 从中挖掘出潜在的模式，预测客户的行为，帮助企业的决策者调整市场策略，减少风 险，作出正确的决策。同样作为分析型工具，d m 是一种挖掘型的分析工具，而 o l a p ( 联机分析处理) 则是一种验证型分析工具。 数据挖掘并不是一项全新的技术，它的出现与发展有着其自身的必然性。随着公 司数据库的猛增，特别是数据仓库的出现，原有的数据库工具已无法满足用户的需 求，用户不仅需要一般的查询和报表工具，更需要的是那些能够帮助他们从数据海洋 中提取出高质量信息( 预测性) 的工具，d m 的出现和发展正符合了这一潮流。 2 1 3 1d m 的方法与技术 d m 的技术基础是人工智能。人工智能是以自动机为手段，通过模拟人类宏观外显 的思维行为，从而高效率地解决事实世界问题的科学和技术。可以看出，人工智能的 目标非常高，除了需要复杂的算法外还需要特定的系统，甚至还需要特定的机器但 1 2 排课算法的研究与实现 d m 仅仅利用了人工智能中一些已经成熟的算法和技术，例如，人工神经网络 ( a r t i f i c i a ln e u r a ln e t w o r k s ) 、遗传算法( g e n e t i c a 1 9 0 r i t h m s ) 、决策树 ( d e c i s i o nt r e e s ) 、规则推理( r u l ei n d u c t i o n ) 、模糊逻辑( f u z z yl o g i c ) 等其问题 的复杂度和难度比人工智能降低了许多。 2 1 3 2d m 的分析方法 从功能上可以将d m 的分析方法划分为以下四种( 根据i b m 的划分方法) ：关联分析 ( a s s o c i a t i o n s ) 、序列模式分析( s e q u e n t i a lp a t t e r n s ) 、分类分析( c i a s s i f i e r s ) 、 聚类分析( c l u s t e r i n g ) 。 关联分析是为了挖掘出隐藏在数据间的相互关系。从一组给定的数据项咀及交易 集合中，分析出数据项集在交易集合中出现的频度关系。使用关联分析方法挖掘的模 式称为关联规则。著名的“啤酒和尿布”就是一个关联规则的例子，啤酒和尿布分别 是一个数据项集，通过关联分析，发现这两个数据项集之间存在频度的关系。 序列模式分析和关联分析相似，也是为了挖掘出数据间的关系，但前者关注的是 数据在发生时间上的先后关系，即因果关系。例如，序列模式分析可能会挖掘出这样 的模式：凡购买了空调顾客中的8 0 在一个月之内又购买了热水器。 分类分析给定一个记录集合和一组标记，标记就是一组具有不同特征的类别。首 先为每一个记录赋予一个标记，即按照标记将；己录分类，然后分类分析检查这些标定 的记录，描述记录的特征。利用这些特征可以分类新的记录。例如在银行数据库中保 存着信用卡用户记录，并根据信誉程度将持卡人分为三类：良好、普通、差，分类分 析将检查这些记录，然后给出一个对信誉等级的显式描述：“信誉良好的用户是那些 收入在x 元以上，年龄在a 到b 之间，居住在c 地区附近的人士”。 聚类分析与分类分析不同，其输入集合是一组未标定的记录，即输入的记录还未 被进行任何分类聚类分析根据一定规则，合理划分记录集合并用显式或隐式的方 法描述不同类别。实际上，聚类分析和分类分析是互逆的过程。 以上四种d m 方法虽然有着不同的适用范围但在一个真正的d m 系统中经常是综 合地利用这四种方法的。以零售商为例，在为某种商品进行市场定位时( 例如微波 炉) ，d m 可能会协同使用这四种分析方法： ( 1 ) 运用关联分析法发现最常被起购买的商品 ( 2 ) 运用序列模式分析方法找出几类重要的用户群，他们具有如下的购物模式： 在购买了某些商品后购买微波炉。 ( 3 ) 基于( 2 ) 的分析结果，运用分类分析法定义( 2 ) 的分类标准，即购物模式。 ( 4 ) 将上述的购物模式作为分析规则，运用聚类分析法就可以找出具有该购物模 式并且尚未购买微波炉的用户，他们，就是市场人员所要争取的对象。 排课算法的研究与实现 上述的四种分法摘自i b m d a t am i n i n g 版本1 3 0 白皮书。但基于同样的基本 技术，d a t a m a t i o n 白皮书将d m 的方法分为以下四种： ( 1 ) 预厕模型( p r e d i c t i v em o d e l i n g ) 。在o l a p 中是演绎推理，而在d m 中则是归 纳推理。 ( 2 ) 数据库分段( d a t a b a s es e g m e n t a t i o n ) 。将数据库中的数据自动地分类，包括 分类分析和聚类分析。 ( 3 ) 联系分析( l i n ka n a l y s i s ) 。确定数据间的相互关系，包括关联分析和序列分 析。 ( 4 ) 偏差检测( d e v i a t i o nd e t e c t i o n ) 。检测并解释数据分类的偏差为什么有 些记录不能归入段( s e g m e n t ) 中。 与i b m 白皮书对d m 方法的分类相比，d a t a m a t i o n 白皮书的分类层次更高，例如数 据库分段和联系分析涵盖了分类分析法、聚类分析法、关联分析法和序列分析法，而 预测模型在i b m 白皮书中所列的四种方法中都包含了，只不过在d a t a 姒t 1 0 n 白皮书中 被特别提出来了。两种分类法最大的差异在于偏差检测，这是i b m 白皮书中没有列出 来的。 2 1 _ 3 3 数据挖掘的步骤 d m 的数据分析过程可以分为三个步骤。 数据准备( d a t ap r e p a r a t io n ) 本阶段又可进一步细分为两步：数据集成；数据选择和预分析。 ( 1 ) 集成( i n t e g r a t i o n ) 。在这一步中，将从操作型环境中提取并集成数据，解决 语义二义性问题，消除脏数据等等。很明显，数据集成的目的和所利用的技术与数据 仓库的数据集成完全一致，都是为了建立统一的数据视图。数据挖掘不一定需要建立 在数据仓库的基础上，但如果数据挖掘与数据仓库能协调工作，则必将大大地提高数 据挖掘的工作效率，并且因为数据仓库的数据来源于整个企业，从而保证了数据挖掘 中数据来源的广泛性和完整性，这样才不会漏掉任何与主题相关的信息。另外，为了 保证结果的正确性，d m 需要大量的基础数据，数据仓库可以很好地满足这个要求。 ( 2 ) 数据选择和预分析( d a t as e l e c t i o na n dp r e - a n a l y s i s ) 。这一步将负责数据 范围，提高数据挖掘的质量，前面提到的验证型工具长子对数据的细致深入地观察和 表述，在这一步中可以发挥相当的作用。 挖掘( m i n i n g ) 数据挖掘器( d a t am i n i n gp r o c e s s o r ) 综合利用前面提到的四种数据挖掘方法分析 数据库中的数据。 表述( p r e s e n t a t i o n ) 1 4 排课算法的研究与实现 与验证型工具一样，数据挖掘将获取的信息以便于用户理解和观察的方式反映给 用户，这时可以利用可视化工具。由于用户要求的不同，d m 分析的数据的范围会有所 不同，例如分析一年内或三个月内的销售情况，再例如分析东部地区或西部地区的销 售情况，这样d m 系统会得出不同的结论。这些基于不同数据集合的分析结果除了通过 可视化工具提供给用户还可以存储在知识库中，供日后进一步分析和比较。 评价( a s s e s s ) 如果分析人员对分析结果不满意，可以递归地执行上述三个过程，直到满意为 止。 根据功能，整个d m 系统可以大致划分为三级结构( 见图2 - 4 ) 。 c 1 图2 4d m 系统的三级结构 2 2 粗糙集理论 。 在数据挖掘技术中基于粗糙集理论的知识获取技术是较新的一种方法，粗糙集理论 ( r 0 u g hs e t ) 是由波兰数学家z p a w l a k 教授在1 9 8 2 年提出的。在该方法中，假设知识是 排课算法的研究与实现 基于对对象分类的能力。它从新的角度认识知识，把知识和分类紧密联系起来，不需 要预先给定某些特征或属性的数量描述，而是直接从给定问题的描述集合出发，通过 不可分辨关系和不可分辨类确定给定问题的近似域，从而找出该问题中的内在规律。 且粗糙集发现的知识是显式的定量描述，可被人理解。粗糙集理论为处理不精确、不 完全等数据的分类问题提供了更符合人类认知的数学工具。该理论目前在医疗诊断、 模式识别、专家系统、机器学习、图像处理等领域获得了广泛的应用。 2 2 1 粗糙集理论基础 粗糙集对知识的表达是建立在知识表达系统上的，个知识表达系统形如表3 ，1 。 对于知识表达系统s 是用一个有序4 元组 表示，其中：u = “，x ：，x 。) ， 是全部有限个处理对象( o b j e c t ) 集合，即全体样本。a = c u d 是全部有限个属性 ( a t t r i b u t e s ) 的集合，c 是条件属性( c o n d i t i o na t t r i b u t e ) 集合，即对象的特征，d 是决策属 性( d i c i ；i o na t t r i b u t e ) 集合，即对象的类别，且c n d = 庐。设是任一属性，丑是任一个 对象，则0 。，口) 表示而在d 属性的取值。例如，表2 1 有3 个条件属性( 症状) i ，a 2 ， ，一个决策属性( 病症) d i 和6 个对象( 病例) 朋工6 。如果日= 乏力，x i = n ，则 a x ，a ) = f l x 2 ，乏力) = 是 表2 1 信息表示例一 属性a条件属性c决策属性d 对象u 头痛乏力发烧流感 x 】是是正常否 x 2 是是偏高是 x 3是是很高是 x 4否是正常否 x 5 否否 偏高 否 x 6否是很高是 设任一属性子集b a ，r ( b ) 称为不可分辨关系，如果 只( b ) = ( x ，x ，) u 2 l v a b ，f ( x 。，a ) = f ( x j ，口) ) ( 2 1 ) 属性子集日将全部样本u 划分成若干等价类，称为b 基本元素( b - e l e m e n t a r y ) 。 显然，一个b 基本元素中的任意两个对象x ，y 根据b 是不可区分的称 b 一不可分辨的( b i n d i s c e r n i b & ) 。即v a b ，如果厂( x ，d ) = f ( y ，c 1 ) ，我们说x 1 ，x 2 在 属性集合口上不可分辨。 例如，如果取b = 头痛，乏力) ，则表2 1 成为表2 2 。 6 排课算法的研究与实现 表3 2 信息表示例二 属性属性b 对象 头痛乏力 z i是 是 x 2是是 x 3 是是 x 4否是 x 5 否否 否是 这样在表2 2 中，工j = x 2 = x ，斯= 坼，奶，即属| 生子集b 将全部样本u 划分成3 个 等价类扛j ，。厶。，) ， j 4 ，) ， x 5 ) ，构成表2 2 的3 个基本元素。显然每个等价类内的 元素在表2 2 中是无法区分的即是口一不可分辨的。 如果用b ( z ) 表示对象x 所属的那个占基本元素( 一个等价类，如用b 0 ，) 代表等价 类 。，即，x ，) ) ，对于有限个对象的一个集合x ，如果满足 且( x ) = x u ：1 1 ( x ) 肖 ， ，。 b ( ) = x u ：b ( x ) n z 庐 ， 集合且( j ) 称为的b 一下近似( b l o w e r a p p r o x i m a t i o n ) ，b + ( ) 称为x 的 b 一上近似( b u p p e ra p p r o x i m a t i o n ) 。 b n 。( j ) = b 。( x ) 一1 1 ( )( 2 3 ) 称为肼勺b 一边界区间。 例如：取“流感= 否”的集合_ ，和，x 如秘 ，取b = ( 头痛，乏力 b 将表2 i 划分成3 个基本元素 x ，x 2 ，x s ， x 4 ，粕 ， x 5 ) ，则 b ( x ) = 妒u 妒u x s 2 鄞) 口( x ) = x l ，x 2 ，x 3 ) u x 4 ，x 6 k d ( 工5 ) = x 】，工2 ，b ，x ，x 5 ，x 6 ) b n 。( ) = b ( ) 一鼠( x ) 2 x t ，x 2 ，x 3 ，x 4 ，x 6 ) 上、下近似的含义是：上近似代表“可能”，下近似代表“一定”。对上例来 说，有x 5 症状的一定不是流感，有与x j ，工2 ，x 3 ，x 4 ，x j ，x 6 任意一个相同症状的可能不是流 感，可能的程度取决于不确定对象的多少，即边界区间的大小。注意，这里的“症 状”是针对口特征集合的，即针对头痛，乏力症状而言的。 由于边界区间的存在，使得属性集合b 对u 的划分是“粗糙”的如果边界区间 为空，即所有对象都是确定的，则蜕化成为完全确定问题。显然刻划这种粗糙程度 的指标可以用 排课算法的研究与实现1 7 郴) = 粼 眨。， 来表示，称为近似精确度( a c c u r a c yo f a p p r o x i m a t i o n ) ，lzj 表示集合的势。此外还有 椭= 韦裂 僻s ， 称为粗糙隶属函数( r o u g hm e m b e r s h i pf u n c t i o n ) 。粗糙隶属函数表示了x 属于z 的确 定程度。显然，卢，( 砷【0 , 1 】。 脚( c ，d ) _ 等掣 ( 2 s ) 其中 p o s c ( d ) = u c ( )( 2 7 ) 称为属性集合d 对c 时裂生程度( d e g r e eo fd e p e n d e n c y ) ，u d 是d 在u 上的划 分。记为 c j d( 28 ) 表示d 在k 程度上依赖于c 。显然，有 肥d ) _ 。；。晋 ，) 又称为近似质量( q u a l i t yo f a p p r o x i m a t i o n ) 。 如果d 是全部决策属性，c 是全部条件属性，则r ( c ，d ) 表示用c 对u 划分后，任 一x e u 能被正确划分到决策类( 按决策属性d 划分的集合，是我们希望的目标分类) 的 概率；同时刻划了条件属性c 描述决策属性d 的能力。 进一步，如果c 是c 去掉某些条件属性后的条件属性集合，并能保持近似质量不 变，即 r ( c 。，d ) = r ( c ，d )( 2 1o ) 则c 称为c 的一个d 一约简( d r e d u c t o f c ) 。 例如：在表2 1 中，条件属性c = 头痛，乏力，发烧 将整个表划分成 x l ， 恐 ， 商， 凰 ，( 嚣) ， 商，c r _ 头痛，发烧 对整个表的划分也是 x s ) ， , r e ， 商， 丑 ， 商，( ) ，显然“乏力”属性对分类不起作用，去掉该属性后仍能保持分类精 度不变，满足式( 2 1 0 ) 。 相对于不可分辨类x 的所有简约的集合记作s r z d ( c ，x ) ，s c o r e ( c ，x 。) = n s r e d ( c ，x 。) 称相对于x ；的核。通过一系列的简约，可以得到决策系统s = ( u ，c u d ) ) 中最简单的规则集。其中，每个相对简约就是一条规则的前件。 2 2 2 基于粗糙集理论的知识获取方法 8 排课算法的研究与实现 根据前面的介绍，知识表达系统将论域描述为一个二维表格，每一行描述一个对 象，每一列描述一个属性，属性分别为条件属r 性和决策属性。知识推理的过程，首先 要进行条件属性的简化，消去重复行，然后对每一决策规则进行冗余属性的简化。一 般情况下，一个知识表达系统的简化不止一种，这些简化都维持了与原有条件属性相 同的分类能力，因此要得到使用意义上的母小决策规则就要合理地选择有效属性来正 确或近似地表征研究的论域。 普通情况下，决策者会拥有对各对象的条件属性权重的先验知识，权重用来衡量属 性的相对重要性。在不同的决策环境下，相同的属性对决策输出会有不同的影响。粗 糙集理论中的属性依赖度即表达了在当前的数据环境下属性对决策规则的影响，但它 并不能反映决策者的先验知