（管理科学与工程专业论文）关联规则挖掘算法的研究与应用.pdf

山东师范大学硕士学位论文 摘要 随着计算机技术，特别是数据库技术的发展，在各行业数据库中积累了大量的 数据。如何发现隐含在这些数据中的规则和知识，并辅助决策，成了要解决的问题。 数据挖掘技术的出现和发展为此提供了有力的支持。数据挖掘就是从大量的、不完 备的数据中，提取出事先未知的、但具有价值的信息和知识的过程。 关联规则挖掘是数据挖掘的一个重要研究分支，主要用于发现数据集中项之间 的相关联系。由于关联规则形式简洁、易于解释和理解并可以有效地捕捉数据间的 重要关系，从大型数据库中挖掘关联规则问题己成为数据挖掘中最成熟、最重要、 最活跃的研究内容。 教学评价依据一定的教学目标与教学规范，对教学活动以及教学成果给予价值 判断。教学评价首先应该根据教学效果，确立教学优秀的质量标准体系，进而建立 一套分类判定标准，其次应该能够发现评价标准和结果之间的规律，便于改进现有 教学环节或过程中的不足之处。数据挖掘是一种决策支持过程，是深层次的数据信 息分析方法，将数据挖掘技术应用于对教学的评价无疑是非常有益的，它可以全面 地分析测试评价结果与各种因素之间隐藏的内在联系，通过数据挖掘分析，其评价 结果能给教学带来前所未有的收获。 本文首先对数据挖掘作了讨论，包括数据挖掘的概念、数据挖掘的过程和数据 挖掘的任务等。然后，对关联规则挖掘算法做了深入的研究，分析了关联规则中经 典的a p r i o r i 算法，指出了挖掘中的关键步骤及该算法的不足。并针对a p r i o r i 算法 的不足，提出了对a p r i o r i 算法进行了改进，使得寻找频繁项集的工作得以分布化， 并行化。最后将关联规则数据挖掘的方法运用到教学评价中，从教学评价数据中进 行数据挖掘。找到教学效果与教师基本情况的关系，为教师提供有价值的参考，帮 助教学部门进行决策，从而更好地开展教学工作，提高教学质量。 关键词：数据挖掘；关联规则；a p r i o r i 算法；教学评价 山东师范大学硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to ft h ec o m p u t e rt e c h n o l o g y , e s p e c i a l l yt h ed a t a b a s e t e c h n o l o g y , l o t so fh u m a nr e s o u r c ed a t ah a v eb e e na c c u m u l a t e di nt h ee n t e r p r i s e d a t a b a s e h o wt od i s c o v e rt h er u l e sa n dk n o w l e d g eh i d i n gi nt h e s ed a t as oa st o p r o v i d et h ea s s i s t a n td e c i s i o ns u p p o r th a sb e c o m e a nu r g e n tp r o b l e mt ob es o l v e d t h e a p p e a r a n c ea n dd e v e l o p m e n to ft h ed a t am i n i n gt e c h n o l o g yh a sp r o v i d e dp o w e r f u l s u p p o r t t ot h i sn e e d t h ea s s o c i a t i o nr u l ei sad a t am i n i n gi m p o r t a n tr e s e a r c hb r a n c h ，m a i n l yu s e si n d i s c o v e r i n gb e t w e e nt h ed a t as e tm e a nt e r m st h ec o r r e l a t i o nr e l a t i o n b e c a u s et h e c o n n e c t i o nr u l ef o r ms u c c i n c t ，e a s yt oe x p l a i na n dt h eu n d e r s t a n d i n ga n dm a yc a t c h t h ed a t ae f f e c t i v e l yt h ei m p o r t a n tr e l a t i o n s ，e x c a v a t e sc o n n e c t i o nr u l eq u e s t i o no n e s e l f f r o mt h el a r g e s c a l ed a t a b a s et ob e c o m ei nt h ed a t am i n i n gt ob em a t u r e s ，i m p o r t a n t l y , t h em o s ta c t i v er e s e a r c hc o n t e n t i na c c o r d a n c et ot h er e l a t e dt e a c h i n go b j e c t i v e sa n ds t a n d a r d s ，t e a c h i n ga p p r a i s a l a f f o r d sv a l u ee v a l u a t i o nt ot e a c h i n ga c t i v i t i e sa n da c h i e v e m e n t s i ti n c l u d e st w os t e p s t h ef i r s ti st od e f i n es t a n d a r ds y s t e mo fe x c e l l e n tt e a c h i n gq u a l i t y t h es e c o n di st o e s t a b l i s has e to fc l a s s i f i c a t i o ne v a l u a t i o ns t a n d a r d s t h et h i r di st of i n do u tt h er u l e s g o v e r n i n ga p p r a i s a ls t a n d a r da n dr e s u l ts oa st oi m p r o v et h et e a c h i n gc o u r s e t h ed a t a m i n i n gi so n ek i n do fp o l i c y - m a k i n gs u p p o r tp r o c e s s ，i st h ed e e pl e v e ld a t am e s s a g e a n a l y s i sm e t h o d ，a p p l i e st h ed a t am i n i n gt e c h n o l o g y i nt ot h et e a c h i n gt h ea p p r a i s a li s e x t r e m e l yb e n e f i c i a lw i t h o u td o u b t ， i t m a ya n a l y z e t h et e s t a p p r a i s a lr e s u l t c o m p r e h e n s i v e l yt h ei n n e rl i n kw h i c hh i d e sw i t he a c h k i n do ff a c t o rb e t w e e n ，t h r o u g h t h ed a t am i n i n ga n a l y s i s ，i t sa p p r a i s a lr e s u l tc a nb r i n gt h eu n p r e c e d e n t e dh a r v e s tt o t h et e a c h i n g t h i sp a p e rf i r s th a sm a d et h ed i s c u s s i o nt ot h ed a t am i n i n g ，i n c l u d i n gd a t a m i n i n gc o n c e p t ，d a t am i n i n gp r o c e s sa n dd a t am i n i n gd u t ya n ds oo n t h e n ，t ow a s c o n n e c t e dt h er u l ee x c a v a t i o na l g o r i t h mt od ot h et h o r o u g hr e s e a r c h ，h a sa n a l y z e di n i i 山东师范大学硕士学位论文 t h ec o n n e c t i o nr u l et h ec l a s s i c a la p r i o r ia l g o r i t h m ，h a dp o i n t e do u ti nt h ee x c a v a t i o n e s s e n t i a ls t e pa n dp r o p o s e dt h ea l g o r i t h mi n s u f f i c i e n c y i nv i e wo ft h ea p r i o r i a l g o r i t h mi n s u f f i c i e n c y , p r o p o s e dh a sm a d et h ei m p r o v e m e n tt ot h ea p r i o r ia l g o r i t h m ， c a u s e st os e e kt h ef r e q u e n ti t e mo fc o l l e c t i o nt h ew o r kt ob ea b l et od i s t r i b u t e ， p a r a l l e l i z a t i o n f i n a l l yw i l lb ec o n n e c t e dt h er u l ed a t am i n i n gt h em e t h o dt ou t i l i z e i n t h et e a c h i n ga p p r a i s a l ，c a r r i e so nt h ed a t am i n i n gf r o mt h et e a c h i n ga p p r a i s a ld a t a f o u n dt h et e a c h i n ge f f e c ta n dt h et e a c h e rb a s i cs i t u a t i o nr e l a t i o n s ，p r o v i d e st h e v a l u a b l er e f e r e n c ef o rt h et e a c h e r , h e l p st h et e a c h i n gd e p a r t m e n tt oc a r r yo nt h e d e c i s i o n - m a k i n g ，t h u sd o e st h et e a c h i n gw o r kw e l l ，i m p r o v e st h eq u a l i t yo ft e a c h i n g i i i k e yw o r d s ：d a t am i n i n g ；a s s o c i a t i o nr u l e ；a p r i o r ia l g o r i t h m ；t e a c h i n ga p p r a i s a l 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得( 注：如没有其他需要特别声 明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：住五加 导师签字： ，r ” 学位论文版权使用授权书 拯碥毫 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文披查阅和借阅? 本人授权兰 丝可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印 或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 挚位论文作者签名牟硷价 导师糠 易致幺气 厶 签字日期：2 0 0 8 年4 月1 日签字日期：2 0 08 年l f 月r 日 山东师范大学硕士学位论文 第一章绪论 1 1 数据挖掘的历史及研究现状 近年来，随着计算机技术突飞猛进的发展及数据管理技术的成功应用，各部门 信息化程度的不断提高，人们所拥有的数据量急剧增大。这些数据十分繁杂，要从 中发现有价值的信息和知识，达到决策的目的，是一个非常艰巨的任务。利用传统 的数据分析方法( 例如统计) ，人们无法有效地理解并使用这些数据，只能获得这些 数据的表层信息，很难对数据进行深层次的处理，而且不能获得数据属性之间的内 在关系和隐含的信息，即不能获得重要的有价值的知识。大型数据库系统也不能从 根本上解决这一问题。因为决策者们需要得到这些蕴含在海量数据中的知识并用于 决策指导。很容易陷入“数据富有但知识贫乏”的尴尬局面。显然，人们需要一种 崭新的、高级的数据分析工具来完成理解己有的数据并用于预测未来走势的任务。 在这种情况下，“数据挖掘 一种新型的数据分析技术于1 9 9 5 年诞生了【1 1 】。十多年 来，数据挖掘的研究工作取得了很大的进展，各种数据挖掘软件的应用极大地推动 了人们掌握、处理信息的能力，并为人们带来了很好的经济效益。 1 9 8 9 年8 月，在美国底特律召开的第1 1 届国际人工智能联合会议的专题讨论 会上首次出现k d d 这个术语，即数据库中的知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e 简称i ( d d ) ，是指低层数据一直抽象到高层知识的整个过程。随后在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年都举行k d d 专题讨论会，汇集来自各个领域的研究人员和 应用开发者，集中讨论了数据统计、海量数据分析算法、知识表示、知识运用等问 题。随着参与人员的不断增多，k d d 国际会议发展成为年会。1 9 9 5 年，在美国计 算机年会( a c m ) _ l ，提出了数据挖掘( d m ：d a t am i n i n g ) 的概念。1 9 9 8 年在美国纽约 举行的第四届知识发现与数据挖掘国际学术会议，不仅进行了学术讨论，并且有3 0 多家软件公司展示了他们的数据挖掘软件产品，不少软件已在北美、欧洲等国得到 应用。 由于数据库中的数据被形象地比喻为矿床，因此，数据挖掘一词很快流传开来。 由于它应用的普遍性及由此带来的高效益，数据挖掘已成为一个具有广阔应用前景 的热门研究方向。目前，世界上比较有影响的典型数据挖掘系统有：s a s 公司的 e n t e r p r i s em i n e r ，i b m 公司的i n t e l l i g e n tm i n e r ，s g i 公司的s e tm i n e r ，s p s s 公司 山东师范大学硕士学位论文 的c l e m e n t i n e ，s y b a s e 公司的w a r e h o u s es t u d i o ，r u l eq u e s tr e s e a r c h 公司的s e e 5 ， 还有c o v e rs t o r y ，e x p l o r a ，k n o w l e d g ed i s c o v e r yw o r k b e n c h ，d bm i n e r ，q u e s t 等【1 2 】。与国外相比，国内对数据挖掘的研究稍晚，没有形成整体力量，直到1 9 9 3 年国家自然科学基金才首次支持该领域的研究项目，到9 0 年代中后期，初步形成 了知识发现和数据挖掘的基本框架。自9 0 年代中期一批研究成果( 学术论文) 逐渐发 表在计算机学报、计算机研究与发展、软件学报、人工智能与模式识别 等刊物上，研究重点也正在从发现方法转向系统应用，并且注重多种发现策略和技 术的集成，以及多种学科之间的相互渗透。但是基本上还是以学术研究为主，实际 应用上处于起步阶段。目前，国内的许多科研单位和高等院校竞相开展知识发现的 基础理论及其应用研究，研究所涉及的领域很多，一般集中于算法的研究，数据挖 掘的实际应用以及有关数据挖掘理论方面的研究，如北京系统工程研究所对模糊方 法在知识发现中的应用进行了较深入的研究；北京大学也在开展对数据立方体代数 的研究；华中科技大学、复旦大学、浙江大学、中国科技大学、中科院数学研究所、 吉林大学等单位开展了对关联规则开采算法的优化和改造；南京大学、四川大学和 上海交通大学等单位探讨、研究了非结构化数据的知识发现以及w e b 数据挖掘 b 3 1 1 4 】【1 5 】。但是到目前为止还没有商用工具问世，像复旦大学设计的基于关联规则的 数据挖掘工具a r m i n e r 等也只是处于实验室研究阶段。目前进行的大多数研究项目 是由政府资助进行的，如国家自然科学基金、8 6 3 计划等。 1 2 问题的提出背景及意义 目前，数据挖掘的主要技术为关联规则、聚类、粗糙集、神经网络和遗传算法 等方面。关联规则表示数据库中一组对象之间某种关联关系的规则。 关联规则问题由a g r a w a l 等人于1 9 9 3 年首先提出，以后诸多的研究人员对关 联规则的挖掘问题进行了大量的研究。他们的工作包括对原有的算法进行优化，如 引入随机采样、并行的思想、增加衡量标准、规则约减、改变存储结构等，以提高 算法挖掘规则的效率。对关联规则的应用进行推广，从最初的商业指导到生活中的 其他领域，如教育、科研、医学等。 随着计算机的快速发展，各行各业都在实行信息化管理。再加上高校的学校规 模的扩大，对大型的、复杂的和信息丰富的数据集进行分析将不可避免而且也很必 2 山东师范大学硕士学位论文 要，各高校多年来的教学与管理积累了大量的数据，利用这些数据理性的分析学校 各方面工作的成效以及学生培养过程当中的得失变得十分重要【1 6 】【1 7 1 。数据挖掘技术 能从大量的数据中发现有用的知识，这些知识对高校的教学管理的决策支持是十分 有意义的。但是目前对教学管理进行评价大多数是采用一些定性的方法，这种方法 虽然在过去的教学质量评价中起过十分重要的作用，但随着教育改革的深入，定性 评价的不足日渐显露，定性的评价弹性太大，过于粗略，不能客观、准确、深入的 反映教学实际情况，与现代教学管理对教学评价的要求相差甚远。因此，采用定量 的方法对教学管理进行评价也就势在必行了，与定性评价相比，量化评价应该说是 教学质量评价中比较客观的一种手段，量化评价是教学评价的发展趋势之一【l 引。 为了解决传统教学评价中定性与定量评价的不足，我们将数据挖掘这一现代分 析技术引入到教学评价中，运用数据挖掘中的关联规则对教学质量进行评价，利用 所建的基于数据挖掘的教学评价系统对高校多年来积累的教学评价数据进行挖掘、 评价，评价结果给高等学校教学管理、教育行政部门的决策提供了帮助，尤其是给 老师的教学工作提供了有益的参考【1 9 】【2 0 1 。 1 3 论文的研究内容及结构安排 本文的研究工作源于上述的背景。目的是对数据库知识发现进行深入的研究， 主要围绕关联规则对数据挖掘理论和方法进行了以下几方面的工作： 第一章绪论。主要叙述数据挖掘的历史及国内外研究现状，介绍问题提出的背 景和意义，并提出本论文所研究的内容及论文结构的安排。 第二章数据挖掘的基本知识。主要介绍了数据挖掘的定义、过程、任务、方法 等，为之后章节中的数据挖掘的实际应用奠定了坚实的理论基础。 第三章关联规则挖掘概述。主要叙述关联规则的定义、基本概念、关联规则的 分类、关联规则挖掘算法的步骤以及关联规则的研究和发展方向。 第四章关联规则中算法的分析与优化。主要介绍关联规则中的算法- a 叫o r i 算法，f p g r o w t h 算法。对于a p r i o f i 算法存在的瓶颈，提出了对a p r i o r i 算法的改 进，使得寻找频繁项集的工作得以日常化，挖掘工作分布化、并行化，编程简易化。 以此为基础，根据实际需要设计并实现了关联规则挖掘算法。 第五章教学评价挖掘系统的分析与设计。详细并完整实现了关联规则在教学评 山东师范大学硕士学位论文 价中的挖掘过程，并且比较了改进算法与a p r i o r i 算法在教学评价数据挖掘的优势， 并得出教学评价为优秀的关联规则。 结束语。主要总结了在论文研究中所进行的工作，并对今后的发展提出了展望。 1 4 本章小结 本章主要讨论了数据挖掘的历史及发展，当前国内外的研究现状，并分析了本 文问题提出的背景和意义，最后说明了本论文的研究内容及结构安排。 4 山东师范大学硕士学位论文 第二章数据挖掘概述 随着数据库管理系统的广泛应用，使得各个领域的数据和信息急剧增加，人们 希望能够对其进行更深层次的分析，从急速增长的数据背后挖掘出隐藏的重要的信 息，以便更好地利用这些数据。目前的数据库系统可以高效地实现数据的录入、查 询、统计等功能，但无法发现数据中存在的关系和规则，无法根据现有的数据预测 未来的发展趋势。由于缺乏挖掘数据背后隐藏的知识的技术，导致了数据爆炸但知 识缺乏。于是，人们尝试用成熟的数据库管理系统来存储数据，用机器学习的方法 来分析数据，挖掘大量数据背后的知识，这两者的结合促成了数据库中的知识发现 的产生，并且已成为人工智能和数据库应用等领域近年来的研究热点【2 h 。 历史上，从数据中发现模式的提法很多，如知识发现、知识提取、信息收割、 数据采集等等。在数据库领域一般称为数据挖掘，而在机器学习领域则更多地称作 知识发现。 数据挖掘起源于8 0 年代末期的“在数据库中的知识发现”，1 9 8 9 年8 月份召开 了数据挖掘和知识发现的第一次国际讨论会；1 9 9 5 年在加拿大的m o n t r e a l 召开了 首届知识发现和数据挖掘的国际性会议( k d d 9 5 ) ；1 9 9 7 年在新加坡举行了首届亚 太数据挖掘会议( e k d d 9 8 ) ：法国、加拿大等国家的有关科研机构也纷纷开展相关 的研究。迄今为止，由美国人工智能协会主办的k d d 国际研讨会已召开了多次， 规模由原来的专题讨论会发展到国际学术大会，研究重点也逐渐从发现方法转向系 统应用，注重多种发现策略和技术的集成，以及多学科之间的相互渗透【2 2 j 。从大型 数据库中发现信息或知识已经成为数据库和机器学习领域的一个重要的研究课题， 同时许多公司也意识到数据挖掘是提高公司决策能力，增加企业收益提高企业竞争 力的一个重要方面。数据挖掘发现的知识可以应用于信息管理、决策支持、过程控 制等领域，包括数据库领域、机器学习、统计学、知识工程与知识管理、人工智能 【2 3 】等领域的专家都对数据挖掘产生了浓厚的兴趣。 2 1 数据挖掘的定义 数据挖掘与知识发现有很大的重合度，大部分学者认为数据挖掘与知识发现是 山东师范大学硕士学位论文 等价的概念，也有学者把数据挖掘看作知识发现过程的一部分。但数据挖掘更着眼 于高效的数据挖掘算法以达到从巨量数据中发现知识的目的。数据挖掘是一门交叉 学科，涉及数据库、人工智能、数理统计、可视化、并行计算等许多方面的知识。 它以人工智能为技术基础，利用人工智能中一些己经成熟的算法和技术，如人工神 经网络( 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 ca l g o f i t l u n s ) 、关联规则 ( a s s o c i a t i o nr u l e ) 、决策树( 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 ) 、粗糙集方法( r o u g hs e t ) 等。 对数据挖掘比较权威的定义是加拿大j i a w e ih a n 教授等人提出的：数据挖掘是 从大量的、不完全的、有噪声的、模糊的、随机的数据中提取隐含在其中的、人们 事先不知道的、但又是潜在有用的信息和知识的过程【。提取的知识表示为概念 ( c o n c e p t s ) 、规贝, l j ( r u l e s ) 、规律( r e g u l a r i t i e s ) 、模式( p a t t e r n s ) 等形式。数据挖掘主要 是从数据库中发现合理的、新奇的、有用的、可理解的模式的过程，其主题是发现 合适的算法，对数据进行搜索，即发现有趣的知识。 2 2 数据挖掘的过程 数据挖掘是根据对数据的分析，建立对数据的特性以及数据问关系描述模式的 过程。在这个描述中，数据是一系列事实的集合( 例如数据库中的实例) ，而模式是 使用某种语言对数据集合中一个子集的描述。数据挖掘的过程主要分为三个步骤： 数据准备、挖掘操作、结果表述和解释。知识发现则可以简单的认为这几个步骤的 循环操作过程。 1 、数据准备阶段又可以分为四个阶段：数据准备、数据选择、数据预处理和 数据缩减。数据准备主要是了解数据挖掘的相关情况，熟悉有关背景知识，并弄清 楚用户的要求；数据选择则是根据用户的要求从数据中提取出与数据挖掘有关的数 据，数据挖掘算法将主要从这些数据中进行知识提取。在此过程中，将会利用些 数据库操作对数据进行操作处理，其目的是为了辨别出数据挖掘对象的集合，从而 缩小处理范围，提高效率；数据预处理主要是对选择后的数据进行再加工，检查数 据的完整性以及数据的一致性，对其中的噪声数据进行处理，对丢失的数据则可以 利用统计的方法或其他方法进行填补，以此达到克服数据挖掘工具的局限性；数据 缩减则是对预处理后的数据根据数据挖掘的目的进行再加工，主要是通过投影算法 6 山东师范大学硕士学位论文 或数据库中的其他操作减少数据量。 2 、数据挖掘过程主要分为三个阶段：确定数据挖掘的目标、算法和数据挖掘。 首先根据用户的要求确定数据挖掘的目标，即确定用户所需要的知识是何种类型， 因数据挖掘的不同类型会影响到算法的选取。然后根据用户的目标或任务要求确定 采取何种算法，其中包括选取适当的模型和参数，以使得数据挖掘算法与整个数据 挖掘的评价标准相_ 致。最后是运用数据挖掘算法提取出用户所需的知识，即数据 挖掘，这些知识可以用一种特定的方式表示和描述，如利用关联规则算法挖掘出来 的知识以规则形式呈现给用户。 3 、结果表述和解释是为了把数据挖掘出来的信息或知识以用户可以理解的方 式表达出来，若此结果不能令用户满意则需重新进行上面的数据挖掘过程的操作。， 在上述的处理阶段数据挖掘系统可以根据用户的目的重新进行某些处理过程，同时 在处理的任意阶段都可以返回以前的阶段进行再处理。以上数据挖掘过程只是众多 模式之一，还有其它著名的过程模型如b r a c h a m a n 和a n a n d 提出的以用户为中心的 数据挖掘处理模型等，有些专家也称此处理模型为知识发现的处理过程。 2 3 数据挖掘的任务 在实际应用中，数据挖掘多按照任务进行分类。教学评价数据挖掘系统也是从 该角度对数据挖掘方法进行分析、比较，从中选择一种适合教学评价的方法。下面， 先来介绍几种主要的数据挖掘任务。 2 3 1 关联分析 关联分析，即利用关联规则进行数据挖掘，是数据挖掘中的一类重要方法。若 两个或多个数据项的取值之问重复出现且概率很高时，它们就存在某种关联，可以 建立起这些数据项的关联规则。数据关联是数据库中存在的一类重要的、可被发现 的知识，它反映一个事件和其他事件之间依赖或关联。如果两项或多项属性之间存 在关联，那么其中一项的属性值就可以依据其他属性值进行预测。例如，买面包的 顾客中9 0 还买牛奶，这就是一条关联规则。在商场中将这两样物品摆放在一起销 售，将会提高销售量。 在大型数据库中，这种关联规则是很多的，需要进行筛选，一般用“支持度 7 山东师范大学硕士学位论文 和“置信度”两个阙值来淘汰那些无用的关联规则。“支持度”表示该规则所代表 的事例( 元组) 占全部事例( 元组) 的百分比。“置信度 表示该规则所代表事例占满足 前提条件事例的百分比例。在数据挖掘研究领域，最著名、最重要的关联规则发现 算法是r a g r a w a l 等人提出的a p r i o r i 算法。随着对于关联分析的研究深入，人们提 出了多种关联规则的挖掘算法，使得关联规则发现的研究趋势从单一概念层次关联 规则发现发展到多概念层次的关联规则发现。另外，关联规则知识的进一步处理、 模糊关联规则的发现、高效率的关联规则挖掘算法、网络数据中关联规则发现也是 未来关联规则挖掘要深入研究和解决的问题。 2 3 2 分类分析 类是数据挖掘中应用最多的任务，是在已有数据的基础上学会一个分类函数或 构造出一个分类模型( 即通常所说的分类器( c l a s s i f i e r ) ) 。该函数或模型能够把数据库 中的数据记录映射到某一个给定类别中，从而进行数据预测。例如信用卡公司的数 据库中保存着各持卡人的记录，公司根据信誉程度将持卡人记录分成三类：良好、 一般、较差，并且类别标记已赋给了各个记录。分类分析就是分析该数据库的记录 数据，对每个信誉等级做出准确描述，如“信誉良好的客户是指那些年收入在5 万 元以上，年龄在4 0 到5 0 岁之问的人士”，然后根据这些描述对其它具有相同属性 的数据库记录进行分类。 在分类分析中，分类模型的构造方法有决策树法、贝叶斯法，神经网络方法、 近邻学习或基于事例的学习等方法。另外，近年来又出现了一种称为粗糙集的 ( r o u g hs e t ) 新理论方法，将知识表示为产生式规则。不同的分类器有不同的特点， 分类的效果一般与应用背景及数据的特点有关，不存在某种方法能适用任何应用问 题，适合于各种特点的数据【2 4 1 。目前，研究的方向是将多种算法集成，常用的方法 有组合方法和选择方法两类。 2 3 3 聚类分析 聚类是一种常见的描述工作，它主要是把一组个体按照相似性归纳成若干类 别，即“物以类聚”。与分类分析不同，聚类分析输入的是一组未分类记录，并且 这些记录应分成几类事先也不知道。聚类分析就是通过分析数据库中的记录数据， 山东师范大学硕士学位论文 根据一定的分类规则，合理地划分记录集合，确定每个记录所在类别。因此在聚类 之后要有一个对业务很熟悉的人来解释这样分群的意义。很多情况下一次聚集得到 的分群对业务来说可能并不好，这时需要删除或增加变量以影响分群的方式，经过 几次反复之后才能最终得到一个理想的结果。 聚类方法包括统计分析方法、机器学习方法和神经网络方法等。在统计分析方 法中，聚类分析是基于距离的聚类。这种聚类分析方法是一种基于全局比较的聚类， 它需要考察所有的个体才能决定类的划分。在机器学习方法中，聚类是无导师的学 习。此时距离是根据概念的描述来确定的，又称为概念聚类，当聚类对象动态增加 时，概念聚类则称为概念形成。在神经网络中，自组织神经网络方法用于聚类。如 a r t 模型、k o h o n e n 模型等，这是一种无监督学习方法。当给定距离阙值后，各样 本按阙值进行聚类。 2 3 4 时序模式 时序模式是指通过时间序列搜索出的重复发生概率较高的模式【2 5 1 ，主要是强调 时间序列的影响。例如，在所有购买激光打印机的人中，半年后8 0 的人再购买新 硒鼓，2 0 的人用旧硒鼓装碳粉。在时序模式中，需要找出在某个最小时问内出现 比率一直高于某一最小百分比( 最小支持度阙值) 的规则。这些规则会随着形势的 变化作适当的调整。一个有重要影响的方法是“相似时序 的方法，要按时间顺序 查看时间事件数据库，从中找出另一个或多个相似的时序事件。 2 3 5 预测 预测是预测新事物的特征，它利用现有的数据找出变化规律，即建立模型，并 用此模型来预测未来数据的种类、特征等。典型的方法是回归分析，即利用大量的 历史数据，以时间为变量建立线性或非线性回归方程。预测时，只要输入任意的时 间值，通过回归方程就可求出该时间的状态。近年来，新发展起来的神经网络方法， 如b p 模型，它实现了非线性样本的学习，能进行非线性函数的判别。 分类也能进行预测，但分类一般用于离散数值，回归预测用于连续数值，神经 网络方法预测既可以用于连续数值，也可以用于离散数值。 9 山东师范大学硕士学位论文 2 3 6 偏差分析 数据库中的数据存在很多异常情况，发现数据库中数据存在的异常情况是非常 重要的。例如在银行的1 0 0 万笔交易中有5 0 0 例的欺诈行为，银行为了稳健经营， 就要发现这5 0 0 例的内在因素，减小以后经营的风险。偏差分析就是对分析对象的 少数的、极端的特例的描述，揭示内在的原因。 2 4 数据挖掘的主要方法 数据挖掘的方法很多，每种方法都有其特定适用领域。一种方法不可能胜任所 有的数据挖掘任务，一个复杂的数据挖掘系统常常采用多种数据挖掘方法，通过整 合多种数据挖掘方法来弥补单个数据挖掘方法所存在的不足。数据挖掘的方法主要 有以下几种。 2 4 1 基于决策树的方法 决策树也称为判定树，它是用于分类和预测的主要方法之一。决策树技术发现 数据模式和规则的核心是归纳算法。它的目的是根据某个新记录的属性，将其分派 到预先定义好的若干类中的一个，并为其添加一个字段以标识该记录的类别。构建 决策树的算法很多，其中最具代表性的是i d 3 和c 4 5 算法。它们的算法思想大致 如下： 将给定训练集作为决策树的根结点，训练集中的记录具有标识类别的字段，利 用信息增益来寻找结点上具有最大信息量的字段，根据对该字段的不同取值建立该 结点的若干分支，并为所有分支子集建立对应的结点。在每个分支子集中重复建立 下层分支和结点，直到结点中所有记录的类别都相同为止，这样便生成了一棵完整 的决策树。因为完整的决策树不利于分类和预测，因此还要对该决策树进行剪枝处 理，产生最终的决策树。然后把决策树的结点分裂过程转化为“i f t h e n 的规则， 利用这些规则就可以对新数据进行分类。决策树方法在许多应用领域被广泛地应 用，其主要优点有： 第一生成的规则容易理解：决策树产生的规则能够轻易地转化为“i f t h e n 这种形式的关联规则，也可以被翻译成自然语言或s q l 语句，而且决策树模型的 l o 山东师范大学硕士学位论文 建立过程也比较直观。 第二决策树进行分类时所需的计算量不大。 第三决策树既支持离散数据也支持连续数据。 第四决策树的输出包含属性的排序。决策树能够清楚地指出哪一个数据域对 决策是最重要的。 当然，决策树方法也存在着一定的不足，例如训练一棵决策树的耗费很大，对 具有连续值的属性预测比较困难，在类过多的情况下分类容易出错等。 2 4 2 基于神经网络的方法 神经网络最早是由心理学家和神经生物学家提出的。神经网络是大量的简单神 经元按一定规则连接构成的网络系统，这种网络能够模拟人类大脑的结构和功能， 采用某种学习算法从训练样本中学习，并将获取的知识存储在网络各单元之间的连 接权中。神经网络和基于符号的传统人工智能技术相比，具有直观性、并行性和抗 噪声等优点。目前己出现了多种网络模型和学习算法，主要用于分类、优化、模式 识别、预测和控制等领域。在数据挖掘领域，主要采用前向神经网络提取分类规则。 从网络中提取规则，主要有下述两种方向： 1 、网络结构分解的规则提取。它以神经网络的隐层结点和输出层结点为研究 对象，把整个网络分解为许多单层子网的组合。通过研究较简单的子网，便于从中 挖掘知识。k t 算法是有代表性的方法，但其缺点是通用性差，并且当网络比较复 杂时算法的复杂性高，容易产生组合爆炸问题。所以，对于大规模网络，此类算法 在提取规则前，需要对网络结构进行剪枝和删除冗余结点等预处理工作。 2 、由神经网络的非线性映射关系提取规则。这种方法直接从网络输入和输出 层数据入手，不考虑网络的隐层结构，避免了基于结构分解的规则提取算法的不足。 s e s t i t o 等人的相似权值法是一个典型的算法。 在数据挖掘领域，神经网络的规则提取还存在许多问题，如进一步降低算法的 复杂度、提高所提取规则的可理解性、提取规则的评估标准、在训练中从神经网络 动态提取规则从而及时修正神经网络并提高神经网络性能等。 山东师范大学硕士学位论文 2 4 3 基于遗传算法的方法 遗传算法利用了自然进化的思想，最早由h o l l a n d 于2 0 世纪7 0 年代提出。遗 传算法包括选择、交叉和变异三个基本算子。首先，创建一个随机产生的规则组成 的初始群体。每个规则可以用一个二进位串表示；然后，根据适者生存的原则，形 成由当前群体中最适合的规则组成的新的群体，以及这些规则的后代，一般用规则 的适应度来对训练样本集的分类准确率进行评估；第三，通过使用交叉和变异等遗 传操作来创建后代。在交叉操作中，通过来自规则对子串的交换，形成新的规则， 在变异操作中，反转规则串中随机选择的位。由先前的规则群体产生新的规则群体 的过程迭代进行，直到p “进化”，p 中每个规则满足事前指定的适应度阙值。 在应用遗传算法进行数据挖掘时，需要把数据挖掘任务表达为一种搜索的问 题，以便发挥遗传算法的搜索能力。它是基于群体的、具有随机和定向搜索特征的 迭代过程。 2 3 4 贝叶斯方法 贝叶斯网络是由r h o w a r d 和j m a t h e s o n 于1 9 8 1 年提出的，它是一种概率推理 方法，它能从不完全、不精确和不确定的知识和信息中做出推理，可以处理不完整 和带有噪音的数据集，解决数据间不一致和相互独立的问题。贝叶斯分类是统计学 分类方法，它可以预测类成员关系的可能性。比较简单的朴素贝叶斯方法是一种基 于概率的分类方法，它通过样本的属性值计算样本属于某一个类的可能性，然后， 将样本归属到最有可能的类中。朴素贝叶斯分类在应用于大型数据库时，表现出高 准确率和高速度。 2 4 5 基于粗糙集的方法 粗糙集作为一种软计算方法，它可以不需任何辅助信息，如统计学中的概率分 布、模糊集中的隶属度等，仅依据数据本身提供的信息就能对数据进行化简并求得 知识的最小表达。粗糙集方法可以克服传统的不确定信息的处理方法的不足，并且 能和它们有机结合，进一步增强对不确定、不完全信息的处理能力。粗糙集方法首 先用近似的方法把信息系统中的属性值离散化，然后对每一个属性划分等价类，再 1 2 山东师范大学硕士学位论文 利用集合的等价关系进行信息系统的属性约简，最后得到一个最小决策关系，便于 获得规则。目前成熟的关系数据库管理系统和新发展起来的数据仓库管理系统为基 于粗糙集的数据挖掘奠定了坚实的基础。 2 5 数据挖掘应用领域 数据挖掘工具的出现，已经让人们意识到数据挖掘技术带来一定的有利的应用 前景。它的应用主要体现在以下几个方面： 1 、科学研究领域 从科学研究方法学的角度看，随着先进的科学数据收集工具的使用，如遥感遥 测、天文观测、d n a 分子技术等，数据量非常大，传统的数据分析工具己经无能 为力，因此迫切需要一种强大的智能性自动数据分析工具。这种需求推动了数据挖 掘技术在科学研究领域的应用发展，并取得了一些重要的成果。例如，在d n a 数 据分析方面，人类有约十多万个基因，一个基因通常由上百个核苷酸按一定的顺序 排列而成。核苷酸不同的次序形成不同的基因，要从中找出导致各种疾病的特定基 因序列模式，非数据挖掘技术莫属。 。另外，。数据挖掘在社会科学领域的应用前景也被越来越多的人所认识到。比如 数据挖掘可以从大量的历史数据中发现社会发展规律，预测社会发展趋势，或者从 人类社会行为模式的变化中寻找人的行为规律并应用于各种社会问题的解决。 2 、商品零售业 零售业积累了大量的销售数据，顾客购买历史记录、货物进出、消费与服务记 录等。数据量的不断迅速膨胀，特别是由于日益增长的电子商务上的商业方式的方 便和流行，使得零售业成为数据挖掘的一个重要应用领域。销售是以获得最大利润 为目的的，销售什么样的商品、采用什么样的销售策略能够获得最大利润就成了商 家最关心的问题。通过数据挖掘( 如关联规则挖掘) 能够对商场销售数据进行分析， 从而得到顾客的购买特性，并据此采取有效的策略，促进利润最大化的形成。 3 、金融投资业 很多银行和金融机构都提供丰富多样的业务，储蓄服务、信用服务和投资服务 等，有些还提供保险服务和股票投资服务。在这些服务过程中产生的数据通常相对 比较完善、可靠和较高的质量，这大大有利于系统化的数据分析和数据挖掘。如在 山东师范大学硕士学位论文 银行业务中，可以根据客户的收入水平，偿还与收入比率，受教育水平等来进行贷 款偿还预测和客户信用政策分析，尽量降低银行的贷款风险，同时对信用度不同的 客户调整贷款发放政策。对金融数据的分析还可以帮助侦破沈黑钱和其他金融犯罪 活动。 4 、电信业 电信业己经迅速地从单纯的提供市话和长话服务演变为提供综合电信服务，如 语音，传真，寻呼，移动电话，图像，电子邮件，计算机和w e b 数据传输，以及其 他数据通信服务。利用数据挖掘技术，通过分析电信网络运行中已有的警告信息来 得到一些有价值的信息用于网络故障的定位检测和严重故障的预