（计算机科学与技术专业论文）数据挖掘在高校学生管理中的应用研究.pdf

学位论文版权使用授权书 i n l l lupill|lu l l | j h | | l y 1 7 8 0 9 6 。0 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。 同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：彦红柏 签字同期： 硼p 年占月2 f 日 导师签 签字日期 分f 日 中图分类号：t p 3 1 1 u d c - 0 0 4 9 学校代码：1 0 0 0 4 密级：公开 北京交通大学 硕士学位论文 数据挖掘在高校学生管理中的应用研究 r e s e a r c ho nt h ea p p l i c a t i o no fd a t am i n i n gi nt h e m a n a g e m e n to fs t u d e n t s 作者姓名：李红梅学号：0 8 1 2 0 5 0 5 导师姓名：贾卓生职称：高级工程师 学位类别：工学学位级别：硕士 学科专业：计算机科学与技术研究方向：网络与数据库 北京交通大学 2 0 1 0 年6 月 致谢 本论文的工作是在我的导师贾卓生老师的悉心指导下完成的，贾卓生老师严 谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢两年来 贾卓生老师对我的关心和指导。 贾卓生老师悉心指导我们完成了实验室的科研工作，在学习上和生活上都给 予了我很大的关心和帮助，对于我的科研工作和论文都提出了许多的宝贵意见， 在此表示衷心的感谢。 在实验室工作及撰写论文期间，王芳老师、高博老师、于樊鹏老师、李珊娜 老师、唐红老师以及尚治宇、王岫、朱振等同学对我论文的研究工作给予了热情 帮助，在此向他们表达我的感激之情。 感谢我的家人和朋友，他们的理解和支持使我能够在学校专心完成我的学业。 中文摘要 摘要：随着数字化校园建设步伐的加快，各大高校都有了比较完善的校园网 系统。与此同时，高校在日常教学管理过程中积累了大量的数据，这些数据都是 宝贵的信息资源。但是目前，这些数据主要的用途只是提供简单的查询和报表统 计，对这些数据所隐藏的深层次的信息没有充分地利用。如何更好地利用这些数 据，为高校管理部门提供重要决策依据，从而进一步提高高校管理水平和效益， 成为一个新的研究课题。 本论文主要从研究高校学生校园学习生活各方面行为的统计特征及特征之间 的关联性出发，为高校学生管理工作者从整体上了解和解释学生的行为提供了新 方法。目的是为今后的学生管理和教学安排工作提供决策依据。 本论文的主要工作是采用数据仓库、联机分析处理和数据挖掘三种技术对高 校学生校园生活及学习信息进行分析处理，充分利用并结合这三种核心技术内在 联系性和互补性，实现了高校学生管理的决策支持系统框架。该系统首先定期地 从各信息系统提取学生行为信息，经过清洗、转换等预处理后存储于数据仓库。 然后在此基础上，应用联机分析处理和数据挖掘技术，对数据仓库中的数据进行 深入分析和挖掘，找出规律性和价值性的知识。其中，联机分析处理主要从学生 课程、学生借阅、学生上网及学生就餐等四个方面进行多维分析，了解学生行为 的特征及趋势；数据挖掘主要是从以下方面进行挖掘分析：学生群体分类及各分 类特征，学生成绩影响因素，学生毕业去向影响因素等。最后，本系统开发出相 应的客户端工具，用于多维分析、挖掘结果的交互式地查询和展现，以及挖掘模 型的预测。 关键词：学生管理；决策支持；数据挖掘 分类号：t p 3 1 1 a bs t r a c t a b s t r a c t ： w i t ht h ea c c e l e r a t e dp a c eo fd i g i t a lc a m p u sc o n s t r u c t i o n , m a j o ru n i v e r s i t i e sh a v ea f a i r l yc o m p l e t ec a m p u sn e t w o r ks y s t e m a tt h es a m et i m e , i nt h ed a i l yp r o c e s so f t e a c h i n ga n dm a n a g e m e n t ，t h e s eu n i v e r s i t i e sh a v ea c c u m u l a t e dl a r g ea m o u n t so fd a t a w h i c hi sv a l u a b l ei n f o r m a t i o nr e s o u r c e a tp r e s e n t ，t h em a i nu s e so ft h e s ed a t aa r ej u s t t op r o v i d eas i m p l eq u e r ya n ds t a t i s t i c a lr e p o r t s ，b u tt h ei n f o r m a t i o ni n - d e p t hh i d d e ni s n o t a d e q u a t e l yu t i l i z e d h o w t om a k eb e t t e ru s eo ft h e s ed a t at o p r o v i d e d e c i s i o n - m a k i n gb a s i s f o r t h e u n i v e r s i t yt om a k ef u r t h e ri m p r o v e m e n to nt h e m a n a g e m e n tl e v e la n de f f i c i e n c yb e c o m e san e w r e s e a r c hs u b j e c t t i l i st h e s i sm a i n l ys t u d i e dt h es t a t i s t i c a lc h a r a c t e r i s t i c so ft h es t u d e n t s b e h a v i o r so f c a m p u sl i f ea n dt h ec o r r e l a t i o nb e t w e e nc h a r a c t e r i s t i c s ，a n do nt h ew h o l ep r o v i d e da n e wm e t h o dt ou n d e r s t a n da n de x p l a i nt h eb e h a v i o ro ft h es t u d e n t s 1 1 1 ep u r p o s ei st o p r o v i d ead e c i s i o nb a s i sf o rt h es t u d e n tm a n a g e m e n ta n dt e a c h i n ga r r a n g e m e n t si n f u t u r e st h e s i sd e s i g n e dad e c i s i o ns u p p o r ts y s t e mo nm a n a g e m e n to fs t u d e n t s ，w h i c h p r o c e s s e da n da n a l y z e dt h ei n f o r m a t i o no ft h ec a m p u s l i f ea n dl e a r n i n go fs t u d e n t sw i t h t h et e c h n o l o g yo fd a t aw a r e h o u s e ，o n l i n ea n a l y t i c a lp r o c e s s i n ga n dd a t am i n i n g , c o m b i n i n ga n dm a k i n gf u l lu s eo ft h ei n t e r n a lr e l a t i o n sa n dc o m p l e m e n t a r i t yo ft h e t h r e ec o r et e c h n o l o g y f i r s t l y ，t h es y s t e me x t r a c t e ds t u d e n t s b e h a v i o r a li n f o r m a t i o n f r o ma l lk i n d so fi n f o r m a t i o ns y s t e mp e r i o d i c a l l y , a n dt h ei n f o r m a t i o nw a ss t o r e di nt h e d a t aw a r e h o u s ea f t e rt h ep r e p r o c e s s i n gs u c ha sb e i n gc l e a n e d ，t r a n s f o r m e da n de t c t h e n ， t h ed e c i s i o ns u p p o r ts y s t e mu s e dm u l t i - d i m e n s i o n a la n a l y s i sa n dd a t am i n i n gt o o l st o a n a l y z et h ed a t ad e e p l yt of i n do u tt h ek n o w l e d g e f o re x a m p l e ，t h eo n l i n ea n a l y t i c a l p r o c e s s i n gl e a r n e dt h ec h a r a c t e r i s t i c sa n dt r e n do ft h es t u d e n tb e h a v i o ri nt h ea s p e c t so f s t u d e n tc o u r s e s ，s t u d e n tb o r r o w i n g ，s t u d e n ts u r f i n ga n ds t u d e n td i n i n g d a t am i n i n g s t u d i e dt h ef o l l o w i n g s ：s t u d e n t sc l a s s i f i c a t i o na n df e a t u r e so fc l a s s i f i c a t i o n ，s t u d e n t p e r f o r m a n c er e l a t e df a c t o r s ，s t u d e n te m p l o y m e n tr e l a t e df a c t o r sa n ds oo n f i n a l l y , w i t h t h er e l a t e dd e v e l o p m e n tt o o l s ，t h i st h e s i si m p l e m e n t e dac l i e n tw h i c hc a ni n t e r a c t i v e l y q u e r ya n dd i s p l a yr e s u l t sa n dp r e d i c tt h ef u t u r ed a t aw i t ht h em i n i n gm o d e l s k e y w o r d s ：m a n a g e m e n to fs t u d e n t s ；d e c i s i o ns u p p o r ts y s t e m ；d a t am i n i n g c i 。a s s n 0 ：t p 3 1 1 目录 中文摘要i i i a b s t r a c t i v l 绪论1 1 1研究的背景与意义1 1 2本文的主要研究工作2 l - 3本文的组织结构2 2数据仓库、联机分析处理和数据挖掘技术3 2 1数据仓库3 2 1 1 数据仓库的概念3 2 1 2 数据仓库的基本特征及组织结构4 2 2联机分析处理6 2 3数据挖掘一7 2 3 1 数据挖掘算法分类7 2 3 2 相关算法介绍8 2 3 3 数据挖掘结果评估1 8 2 4数据挖掘工具1 8 2 4 1 产品介绍18 2 4 2 数据仓库的选择1 9 3应用系统分析与设计2 0 3 1设计目标2 0 3 2系统的体系结构2 0 3 3统功能模块设计2 2 4数据仓库的建立和管理2 4 4 1数据源2 4 4 2数据抽取、转换和加载2 5 4 2 1 数据清洗2 5 4 2 2 数据换算2 6 4 2 3 数据转换2 6 4 2 4 数据的抽取、转换和加载所使用的工具2 6 4 3建立多维数据集2 7 4 3 1 设计多维数据集2 7 4 3 2 建立多维数据集2 9 4 3 3 多维数据集的访问3 0 4 4构建数据挖掘模型3 4 4 4 1 数据挖掘模型的建立一3 5 4 4 2 数据挖掘模型的访问3 6 5应用案例分析4 0 5 1基于o l a p 的学生相关主题分析4 0 5 1 1 学生课程主题分析4 0 5 1 2 学生就餐主题分析。4 1 5 1 3 学生借阅主题分析4 3 5 1 4 学生上网主题分析4 4 5 2基于数据挖掘的分析及预测4 5 5 2 1 学生聚类分析及预测。4 5 5 2 2 学生成绩影响因素分析及预测5 0 5 2 3 学生毕业去向影响因素分析及预测5 4 6总结。5 8 参考文献5 9 独创性声明6 1 学位论文数据集6 2 1 绪论 1 1研究的背景与意义 随着计算机技术和网络技术的不断发展，高校信息化建设发展迅速，信息化 规模不断扩大。目前国内高校几乎都已建立起校园网，而且校园网经过多年持续 不断的基础设施建设和应用提升，让广大教职员工和学生充分享受了校园网带来 的便利。与此同时，如何利用信息技术更有效地为教学管理服务，成为一个新的 研究课题。尤其是随着数据挖掘技术的逐渐成熟，并被广泛地应用于金融、保险 等行业领域，带来了巨大的经济利益和社会价值，数据挖掘技术应用在教育领域 相对而言较少。因此将数据挖掘技术引入高等学校教学管理之中，利用数据挖掘 技术对教务管理系统现存的数据进行分析，进而为学生、教师和管理人员提供服 务就成为教育信息化进程中高校教务管理面临的新的课题。 数据挖掘技术可以对现有教学管理系统中的数据进行多角度的分析和数据挖 掘，从而发现对学校教学管理有用的知识。这些知识作为提高教学质量、优化教 学资源的依据，辅助学校各级领导部门的决策，进而提高学校的竞争力，为学校 在激烈的竞争中掌握主动发挥重要的作用。另一方面随着高校扩招，学生人数大 幅度增加，教学管理模式的变化( 如学分制的实行) 等都给学校的教学管理工作带来 了诸多问题，使得学校的管理变得越来越复杂，同时也对学校管理的科学性、规 范性、服务性提出了更高的要求。 学生成绩及毕业去向作为考核的结果，不仅是对学生学习效果和教师教学效 果的检验和评定，而且也是一种信息，具有反馈于教学活动、服务于教育决策、 为教育科研提供资料等作用。传统的分析方法往往还是基于教学本身来考虑或者 只是简单的统计，比如在后续专业课学完时，是公共课或专业基础课前导课程对 其影响最大等。然而，在平时教学过程中，存在某些不易察觉的因素在影响着学 生的成绩，除此之外，还有一些教学之外的因素也在影响着学生的学习成绩。这 些都需要进一步分析，从而得出结论，供教育管理人员做出相应的决策，但这些 信息无法从目前的教学管理系统使用的学生成绩分析方法中获得。 本文利用数据挖掘技术将学生的基本信息、选课信息、学习成绩、毕业去向、 就餐信息、上网信息、借阅信息及宿舍门禁信息等等学生活动行为信息综合起来 分析，找出其中的规律及潜在的知识，对于辅助高校学生管理决策是可行的而且 必要的。 1 2本文的主要研究工作 本论文的主要研究工作就是结合数据仓库、联机分析处理和数据挖掘三种技 术，实现针对学生管理的决策支持系统。主要从以下几个方面进行研究： ( 1 ) 参阅大量文献，对数据仓库技术和数据挖掘技术进行了深入的研究。 ( 2 ) 通过抽取、转换、清洗、装载，将决策支持所需的数据从业务数据中分 离出来，建立规范的学生行为分析数据仓库。 ( 3 ) 引入联机分析机制，将各分析主题需要的数据集成到多维立方体中。通 过把数据构造成一个立方体的结构，可以对其内容进行上钻和下钻，查看数据总 体趋势及明细数据，以交互式的图表来展示学生各种行为主题的信息。 ( 4 ) 引入数据挖掘机制，挖掘学生各种行为之间的关联。建立了学生细分聚 类模型、学生成绩影响因素分析模型和学生毕业去向影响因素分析模型。 ( 5 ) 开发出相关的客户端工具用于展现多维分析和数据挖掘结果，并实现挖 掘模型的预测功能。 1 3本文的组织结构 本文总共可以分为六章，其组织结构如下： 第一章为绪论，介绍本文的研究背景及研究意义。 第二章论述相关的技术背景，介绍了数据仓库、联机分析处理( o l a p ) 及数据 挖掘技术的概念，详细描述了本文使用到三种挖掘算法，最后介绍了常用挖掘工 具。 第三章对应用系统进行了分析和设计，包括系统的设计目的、体系结构设计， 以及功能模块设计。 第四章为应用系统实现过程的介绍，包括对原始业务数据进行抽取、转换， 并加载到数据仓库中，建立多维数据库，分别在多维立方体和数据仓库的基础上 构建数据挖掘模型，访问和展示多维模型和挖掘模型的结果。 第五章为学生管理决策支持系统的应用案例分析，主要从联机分析处理和数 据挖掘两个层面介绍了分析过程及分析结果的现实意义。 第六章结论，主要总结了本文的工作，并提出下一步的改进方向。 2 2 数据仓库、联机分析处理和数据挖掘技术 数据仓库、联机分析处理( o l a p ) 和数据挖掘是作为三种独立的信息处理技 术出现的。数据仓库用于数据的存储和组织，联机分析处理集中于数据的分析， 数据挖掘则致力于知识的自动发现。联机分析处理能够将多维数据按照任意的维 度路径，以直观的方式展现给数据分析员，但是联机分析处理只能告诉数据分析 员系统过去和现在的情况，无法告诉数据分析员事物之间潜在的重要联系，因此 有必要进行数据挖掘，从而自动发现事物之间潜在的重要联系。由于这三种技术 内在的联系性和互补性，将它们结合起来用于高校学生管理的决策支持系统中， 可以提高系统相应的处理和分析能力。 ( 1 ) 底层的数据库作为数据源，用于保存大量的事务级细节数据，这里主要 包括学生基本信息表、学生选课表、学生借阅记录表、学生上网记录表、学生就 餐信息表、学生宿舍门禁信息表、学生毕业去向信息表等等学生校园学习及生活 相关的信息。 ( 2 ) 数据仓库对底层数据库中的事务级数据进行集成，形成面向全局的数据 视图，包括学生选课信息、学生上网信息、学生借阅信息、学生就餐信息、学生 事实表等等。 ( 3 ) o l a p 从数据仓库中集成数据出发，构建面向分析的多维数据模型，从 多个不同的角度对数据进行分析、比较，实现基本的统计和分析工作。 ( 4 ) 数据挖掘则以数据仓库和多维数据库中的大量数据为基础，发现数据中 的潜在的模式，并以这些模式为基础对学生分类、成绩和毕业去向作出预测。 其中( 3 ) 和( 4 ) 比较复杂，是本论文的重点研究部分。 2 1数据仓库 2 1 1数据仓库的概念 数据仓库【1 2 】是一个面向主题的、集成的用来支持管理人员决策的数据集合。 它将这些分散的数据进行清理、转换为新的存储格式，集中到一个更大的库( 即 数据仓库) 中。最终用户在数据仓库中运行查询，制作报表，进行数据分析。数 据仓库侧重于存储和管理面向决策主题的数据。数据仓库收集存储于各个不同数 据源中的数据，通过数据的组织给决策支持提供分布于整个企业内部、跨平台的 数据，即为决策支持目标把数据聚合起来，作为决策分析的基础，从理论上解决 3 了从不同系统的数据库中提取数据的难题。 在高校中这些数据大部分来自管理信息系统。高校内部存在着多种数据库管 理系统，如教务管理系统、一卡通信息系统、图书馆信息系统等等，这些系统都 有非常宝贵的实时信息和历史信息。但由于各部门业务的不同，往往由不同的厂 家开发，采用不同的平台、数据库统、开发工具也不尽相同，最初的开发都是基 于日常事务处理和统计所需，缺乏统一的规划和协调。根据现状，要提高决策的 准确性与即时性，构建数据仓库，将各部门的数据源尽快组织起来是解决这一问 题的有效途径。 2 1 2数据仓库的基本特征及组织结构 l 、数据仓库中的数据其有以下基本特征1 3 1 ： ( 1 ) 面向主题( s u b j e c t o r i e n t e d ) 数据仓库中的数据是面向主题的。主题是一个抽象的概念，是在较高层次上 将信息系统中的数据综合、归类并进行分析利用的抽象。主题是决策者进行决策 所关心的业务的重点。面向主题的数据组织方式是在较高层次上对分析对象的一 个完整的、一致的描述，能够完整统一的描述各个分析对象所涉及的各项数据及 数据之间的关系。面向主题是指数据仓库内数据是按主题进行组织，以支持用户 在主题范围内的有效决策。 ( 2 ) 集成化( i n t e g r a t e d ) 数据仓库的数据是从原有分散的数据库数据中提取出来的。这些数据是对操 作型数据进行清理和归整的结果，而不是简单的归并和拷贝。数据在进入数据仓 库之前，必然先经过加工和集成将原数据结构作一个从面向应用到面向主题的转 变。 ( 3 ) 历史化( h i s t o r i c a l ) 数据仓库中的数据不仅是关于某一时点的信息，而是记录了有效的历史数据， 以用于决策。数据仓库以时间为基准来管理数据，允许用户了解过去和现在的业 务数据。 ( 4 ) 稳定性( s t e a d y ) 数据仓库的数据主要是为决策分析提供依据。一般情况下并不对数据进行修 改，数据仓库的数据是不同时间数据库数据快照的集合，而不是联机处理的数据。 数据仓库的数据不可更新是相对于联机处理( 0 l t p ) 的操作型数据的频繁变化而 言，并非是在数据仓库生命周期过程中一直保持不变。当数据仓库中的数据己经 超过数据存储期限时将会把这些数据从数据仓库中清除出去。 4 ( 5 ) 动态数据( d y n a m i c ) 数据仓库的数据必须不断捕捉o l t p 数据库中的数据变化，经统一集成后增加 到数据仓库中形成历史数据；另外数据仓库中的数据超过储存期限后需要删除。 数据仓库内大量的综合数据都与时间有关，这些数据需要随时间变化不断进行重 新综合。 2 、典型的数据仓库数据组织结构附】如图2 1 所示。 图2 1 数据仓厍数据组织结构 f i g u r e2 1t h es t r u c t u r eo fd a t ai nd a t aw a r e h o u s e 数据仓库中的数据分为四个级别：早期细节级、当前细节级、轻度综合级、 高度综合集。数据仓库中的数据存在着不同的综合级别。源数据经过综合后，首 先进入当前细节级。并根据需要进行进一步的综合，进入轻度综合级乃至高度综 合级。 综合级别又称为粒度，粒度越大，表示细节程度越低，综合程度越高。它影 响数据仓库中数据量的多少，也影响数据仓库所能回答查询的种类。不能太低也 不能太高，应根据具体情况设计合适的粒度。 元数据是用于描述数据的数。在传统的数据库中，元数据是对数据库中各个 对象的描述，数据库中的数据字典就是一种元数据。在关系数据库中，这种描述 就是对数据库、表、视图等对象的定义。在数据仓库中，元数据同样也定义了数 据仓库中许多对象表、列、查询、商业规则及数据仓库内部的数据转移。元 数据是数据仓库的重要构件，是数据仓库的指示图。 5 2 2 联机分析处理 联机分析处理【7 。1 0 】( o n l i n e a n a l y t i c a lp r o c e s s i n g ，o l a p ) 是信息技术领域的一 种新的决策支持技术。它解决了对大量数据进行数值计算的问题，可以对数据仓 库提供的数据进一步作深加工，即有效地集中分析和深入研究数据，发现趋势， 看到异常情况，并得到重要细节。 o l a p 主要用于决策分析，它的处理对象是按照主题组织的多维数据集( 立方 体) 。立方体中有度量和维度等对象，其中维度可以包含多个层次，度量的语义依 赖于提供上下文语义的维的信息。多维分析就是对以多维形式组织起来的数据采 取切片、切块、旋转、钻取等各种分析动作，以剖析数据，使用户能从多个角度、 多个侧面、多个层次来观察数据仓库中的数据。因此在o l a p 的立方体中关键的 操作是对度量在某些维度上的聚集操作，多维数据分析算法研究的核心就是如何 高效地实现在维度上的聚集操作。 o l a p 操作： ( 1 ) 切片。切片是选定多维空间的某两维，在这两维上取某一区间或任意维 成员，而其余维度都取定一个维成员，这样得到一个二维平面。 ( 2 ) 切块。切块是选定多维空间的某三个维度，在这三个维度上分别取某一 个区间或者任意的维成员，而将其余的维都取定一个维成员。 ( 3 ) 旋转。旋转是在进行切片或者切块后形成的报表和页面上改变其显示的 维方向。 ( 4 ) 钻取。钻取可以分为上钻和下钻，下钻是指用户从某一个粒度比较大的 数据出发，去考察分析与这一数据有关的、粒度比该数据小的数据。上钻跟下钻 刚好相反。 按照o l a p 的不同存储组织方式可分为基于关系数据库的o l a p 实现 ( r o l a p ，r e l a t i o n a lo l a p ) 和基于多维数据库的o l a p 实现( m o l a p ， m u l t i d i m e n s i o n a lo l a p ) 。本论文主要涉及的是r o l a p 。 o l a p 的具体实现方案通常采用三层客户服务器体系结构，如图2 2 所示。 图2 2o l a p 三层体系结构 f i g u r e2 2t h et h r e e - t i e ra r c h i t e c t u r eo fo l a p 6 第一层是数据仓库，它实现与基层运营的数据库系统的连接，完成企业级数 据一致和数据共享的工作；第二层是o l a p 服务器，它根据最终客户的请求实现 分解成o l a p 分析的各种动作，并使用数据仓库中的数据完成这些动作：第三层 是前端的展现工具，用于将o l a p 服务器处理得到的结果用直观的方式，如多维 报表、饼图、柱状图、三维图形等展现给最终用户。其中，第二层o l a p 服务器 核心的技术就是o l a p 分析引擎( a n a l y t i c a l e n g i n e ) 。o l a p 引擎工作流程如下： 首先把用户的输入命令转化成各种参数，然后再把参数输入到一个对应的存储过 程，接收的参数受到分析后，生成一系列的s q l 语句，得到多维结果集，最后返 回给数据呈现子层。 2 3数据挖掘 数据挖掘 i ! - i 4 1 指的是分析数据，使用自动化或半自动化的工具来挖掘隐含的模 式。数据挖掘的主要目的是：从已有数据中提取模式，提高已有数据的内在价值， 并且把数据提炼成知识。 数据挖掘与传统的数据分析( 如查询、报表) 的本质区别是数据挖掘是在没有明 确假设的前提下去挖掘信息、发现知识。数据挖掘所得到的信息应具有先未知、 有效和可实用三个特征。先前未知的信息是指该信息是预先未曾预料到的，即数 据挖掘是要发现那些不能靠直觉发现的信息或知识，甚至是违背直觉的信息或知 识，挖掘出的信息越是出乎意料，就可能越有价值。 2 3 1数据挖掘算法分类 从功能上可将数据挖掘分析方法划分为：关联分析( 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 l a s s i f i e r s ) 、聚类分析( c l u s t e r i n g ) 。 关联分析是为了挖掘出隐藏在数据间的相互关系。从一组给定的数据项以及 交易集合中，分析出数据项集在交易集合中出现的频度关系。使用关联分析方法 挖掘的模式称为关联规则。著名的“啤酒和尿布就是一个关联规则的例子，啤 酒和尿布分别是一个数据项集，通过关联分析，发现这两个数据项集之间存在频 度的关系。 序列模式分析和关联分析相似，也是为了挖掘出数据之问的关系，但前者关 注的是数据在发生时间上的先后关系，即因果关系。例如，序列模式分析可能会 挖掘出这样的模式：购买了空调的顾客中有8 0 在一个月之内又购买了热水器。 分类分析给定一个记录集合和一组标记，标记就是一组具有不同特征的类别。 7 首先为每一个记录赋予一个标记，即按照标记将记录分类，然后分类分析检查这 些标定的记录，描述记录的特征。利用这些特征可以分类新的记录。例如在银行 数据库中保存着信用卡用户记录，并根据信誉程度将持卡人分为三类：良好、普 通、差，分类分析将检查这些记录，然后给出一个对信誉等级的显式描述：“信誉 良好的用户是那些收入在x 元以上，年龄在a 到b 之间，居住在c 地区附近的人 士 。 聚类分析与分类分析不同，其输入集合是一组未标定的记录，即输入的记录 还未被进行任何分类，聚类分析根据一定规则，合理划分记录集合，并用显式或 隐式的方法描述不同类别。聚类是不依赖预先定义的类和带标号的训练实例，属 于观察式学习，而分类是示例式学习。 以上四类数据挖掘方法有着不同的使用范围，通常是综合地使用这四类方法 于一个真正的数据挖掘系统中。 通常解决同一问题可以有不同的挖掘方案，如何从中选择最合适的，在实际 应用中常用的选择方法是，用交叉验证法( 或其它合适的预计方法) ，重复几次， 选择估计误差率较小的方案。 2 3 2相关算法介绍 下面主要介绍本论文涉及的主要算法： l 、聚类算法 聚类【1 5 1 ( c l u s t e r i n g ) 是一个将数据集划分为若t - 组( c l a s s ) 或类( c l u s t e r ) 的过程， 并使得同一个组内的数据对象具有较高的相似度；而不同组中的数据对象是不相 似的。聚类算法依赖于猜测和假设。猜测数据的分组，并且创建一组聚类，把各 个事例分布到每一个聚类。假定这猜测是正确的，就创建了现实世界实际的模型， 并可以把训练数据的每个事例分到模型中合适的聚类中。可以通过移动分组调整 模型以使该模型更适合于现实世界，重复操作，反复进行猜测和假设，直到某些 事例不再聚类之间来回切换，或者认为该模型已经处于一个比较准确的状态时， 就可以停止猜测和假设。 在实际情况中，通常需要针对数据的所有维进行随机初始化，以便初始化聚 类。聚类方法对初始的点非常敏感，并且一个在局部收敛的聚类，可能不是全局 最优的。为了解决这个问题，可以在开始初始化多个候选模型，并且并发地训练 这些模型。当这些模型都收敛完成或者通过其他方式结束训练之后，在这些模型 中选择一个最好的。 下面介绍一下常见的聚类方法： ( 1 ) 硬聚类算法与软聚类算法 在聚类算法中的一个重要的特点是该算法如何把事例分配到聚类中。 m i c r o s o f t 聚类算法有两种截然不同的方法把事例分配到聚类中：k m e a n 算法和期 望最大化( e x p e c t a t i o nm a x i m i z a t i o n ，e m ) 算法。 k m e a n s 算法以距离值的平均值对聚类成员进行分配，k 意思是打算分组出的 聚类的数量。如果一个对象属于一个聚类，则该数据一定较靠近聚类的中心，因 为聚类的中心位于所有被分配到该聚类的对象中间。这种技术被认为是硬聚类 ( h a r d c l u s t e r i n g ) ，因为每一个对象只能被分配到一个聚类，聚类与聚类之间不互 相连接，也不互相重叠。 e m 算法使用概率进行度量，而不是使用严格的距离来度量，它通过度量某对 象的概率来决定该对象属于哪一个聚类。与k m e a n s 不同，e m 算法不是为每一个 维选择一个点，然后计算距离，而是把每一维作为一个钟型曲线，并且计算平均 计算平均差和标准差。当一个点落到一个钟型曲线内的时候，它以某一概率分配 给某一个聚类。因为每个聚类的曲线可以重叠，所以每一点能够以不同的概率属 于多个聚类。因为该算法允许聚类之间重叠，并且允许模糊的边界，所以这种技 术被称为软聚类。这种算法可以找出连接的聚类，比如稠密区。聚类前后对比图 如图2 3 所示。 i - a _ h r 聚类前 聚类后 图2 3e m 算法聚类前后对比图 f i g u r e 2 3t h ec o m p a r i s o nc h a r to fe mc l u s t e r i n ga l g o r i t h m ( 2 ) 离散聚类 前面的聚类都是针对数值的，这种类型的值比较容易比较和关联，也容易计 算距离，但是实际中聚类对象的属性不容易比较，比如大理石的材料不能用数值 表示和比较。庆幸的是，聚类技术也能够处理离散的变量。可以随机分布离散的 属性，例如，如果红色、蓝色、绿色和黄色这四种颜色的大理石数量相等，则每 9 一种颜色全局的概率都将会是2 5 。初始化每一个聚类的时候，假设这些大理石 的颜色是随机分布的，分布情况如表2 4 所示： 颜色絮类l 聚鬓2絮餐3聚类4 红色 5 7 0 3 5 口 蓝包 1 5 5 4 5 3 口 绿色 5 0 2 5 0 2 5 黄色 3 0 0 2 0 4 5 图2 4 大理石颜色分布图 f i g u r e 2 4t h ed i s t r i b u t i o no fm a r b l ec o l o r 离散聚类的初始化。 当使用e m 算法的时候，选择一块大理石( 假设绿色) ，然后可以说该大理石 有2 5 的概率属于聚类2 。当确定事例中每一个离散属性的概率的时候，可以计算 它在每一个聚类中的概率，并把每一个概率值赋给相应的聚类。 由于k - m e a n s 算法是基于距离进行聚类的，所以不适合于利用概率进行聚类 的模型，通常也不用于离散属性聚类。如果可以从聚类中计算出距离值，则还是 可以使用k m e a n s 算法。m i c r o s o f t 聚类算法实现了计算距离的方法，这个距离值 是1 减去聚类的概率值。例如，如果一块绿色的大理石属于聚类2 ，则1 - 0 2 5 = 0 7 5 ， 0 7 5 就是距离值，这个距离值相当于连续属性情况下的距离值。 离散聚类不仅可以用于多值的属性( 如某物体的颜色) ，还可以应用于一个嵌套 表中的聚类属性。在电影零售商的例子中，不仅可以利用客户的人口统计信息和 他们看电影的行为习惯来对他们进行聚类，还可以利用客户实际观看的电影来对 客户进行聚类。对于这种属性，聚类算法认为每一部电影只有两个可能的属性值： 存在和不存在，并且这种考虑电影属性的方式类似于其他离散的属性。 ( 3 ) 可伸缩聚类 对数据进行聚类时有一个问题：要对数据进行合适的划分，就要对数据集进 行多次训练。在小的数据集中，这不成问题，因为在存储器中对数据集进行多次 训练非常快。但是当数据集的数据量超过了存储器能容纳的容量时，聚类算法的 性能会很低，不再适合于对数据集进行分析。为了解决这个问题，聚类算法有一 种可伸缩框架，它可以高效地对数据集进行聚类，不受数据集大小的影响。 可伸缩框架的基本原理是：当进行重复训练的时候，对不会在聚类之i 、日j 来回 移动的数据进行压缩，不把这些数据加载到内存，这样就可以腾出更多的内存空 间。在这种方式下，整个数据流可以一次性装载到内存，每一次处理一块数据。 1 0 另外，模型可能在每一块数据上进行收敛，甚至不需要看到所有数据就可以完成 数据的聚类。 m i c r o s o f t 聚类算法是可伸缩类聚类算法，其可伸缩框架实现的基本过程如下： 1 ) 设置一组候选模型的随机初始化点。 2 ) 收集数据源样本来填充存储器的缓冲区。 3 ) 对每一个模型执行如下可伸缩步骤： a 对数据进行多次聚类。 b 添加来自前面可伸缩步骤中收集的信息。 c 重新对丢失的聚类进行初始化或者合并聚类。 直到收敛或者已经完成了足够循环才停止工作。 4 ) 如果从上一次可伸缩步骤之后模型已经收敛，或者训练的数据已经训练 完成，则这个操作就完成了。之后，在这些候选的模型当中选择最好的模型。 5 ) 清空缓冲区中的数据，并且为每一个模型添加足够的统计信息。 6 ) 从步骤2 ) 再重复执行。 m i c r o s o f t 聚类算法涉及的一些关键指标，如表2 1 所示。 表2 1m i c r o s o f t 聚类算法参数表 t a b l e2 1t h ep a r a m e t e r so fm i c r o s o f tc l u s t e r i n ga l g o r i t h m 参数说明 聚类分析方法( c l u s t e rm e t h o d )指定算法要使用的聚类分析方法。有下列聚类分析 方法可以用：s c a l a b l ee m 、n o n s c a l a b l ee m 、s c a l a b l e k - m e a n s 、n o n s c a l a b l ek - m e a n s 。分别用参数1 、2 、 3 、4 表示。默认值为l 。 分类数( c l u s t e rc o u n t )指定将由算法生成的大致分类数。如果将 c l u s t e rc o u n t 设置为0 ，则算法将使用试探性 方法最准确地确定要生成的分类数。默认值为1 0 。 最小事例数( m i n m u ms u p p o r t )指定每个分类中的最小事例数。默认值为l 。 收敛值( s t o p p i n g1 o l e 凡n c e )指定何时达到收敛而且算法完成建模。当分类概率 中的整体变化小于s t o p p i n g t o l e r a n c e 参数 与模型人小之比时，即达到收敛。默认值为1 0 。 事例数( s a m p l es i z e )指定算法可缩放聚类分析方法中每个传递使用的事 例数。如果设置为0 ，则会对整个数据集进行聚类 分析操作，有可能导致内存和性能问题。默认值为 5 0 0 0 0 。 2 、关联规则算法 关联规则【蟠19 】是描述数据记录集中数据项之间所存在的关系的规则，即根据一 个事务中某些项的出现可导出另一些项在同一事务中也出现，即隐藏在数据间的 关联或相互关系。在s q ls e r v e r2 0 0 5 中使用的是m i c r o s o f t 关联规则算法，它 属于a p r i o n 关联规则算法家族。a 州o r i 关联规则算法的基本思想是：首先找出所 有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样；然后由频集 产生强关联规则，这些规则必须满足最小支持度和最小可信度。 挖掘关联规则的总体性能由第一步决定，第二步相对容易实现。 首先产生频繁1 项集l l ，然后是频繁2 项集l 2 ，直到有某个r 值使得l r 为 空，这时算法停止。这里在第