（计算机应用技术专业论文）关联规则挖掘在心理分析中的应用研究.pdf

浙江大学硕士学位论文 摘要 摘要 随着数据库技术的成熟应用和i n t e r n e t 技术的迅速发展，人类面临的数据 量呈指数增长。当前，人们已经告别没有数据可用的年代，转而进入如何从海量 数据中提取出有用知识的年代。对这种海量数据，不能只应用传统的查询、统计 分析方法，两应该挖掘出数据更深层的规律和数据之闻的联系，从而为决策者提 供支持因此，数据挖掘技术应运而生。关联规则挖掘是数据挖掘技术的一个分 支，它根据给定的支持度和置信度阈值，从事务数据库中发现各数据之间的联系， 并以关联规则的形式体现出来。 本文的主要工作如下： 1 讨论数据挖掘技术，包括数据挖掘的产生背景、主要任务与功能、一般 挖掘过程、常用技术与方法、面临的困难与挑战等。 2 讨论关联规则挖掘技术，包括关联规则挖掘的背景、问题描述、一般挖 掘步骤、挖掘种类、目前挖掘算法存在的问题等。 3 讨论关联规则挖掘的经典算法，包括a p r i o r i 算法和s e t 黼算法。 4 针对经典算法采用水平数据布局事务数据库的数据压缩不足的缺点，提 出事务数据库垂直数据布局形式的频繁补项存储结构，并研究基于频繁补项存储 结构的频繁项集挖掘算法。 5 将基于事务数据库频繁补项存储结构的关联规则挖掘算法应用于团体心 理健康评估系统中。对测试系统得到的测试数据进行关联规则挖掘，以分析团体 中各心理影响因子之间的联系，为心理医生治疗疾病提供依据，促进人们心理健 康。 关键词数据挖掘关联规则频繁补项心理分析 浙江大学硕士学位论文a b s t r a c t a b s t r a c t w i t ht h em a t u r ea p p l i c a t i o no fd a t a b a s et e c h n o l o g ya n dr a p i dd e v e l o p m e n to f i n t e r n e tt e c h n o l o g y , a c c u m u l a t e dd a t aa r ee x p o n e n t i a l l yi n c r e a s i n g w eh a v eg o n e t h r o u g ht h et i m ew i t hn od a t at ob eu s e d , b u ta r cf a c i n gt ot h ep r o b l e mo fh o wt o e p o r a t eu s e f u lk n o w l e d g ef r o mm a s s i v ed a t a f o rt h e s em a s s i v ed a t ap e o p l ea r en o t s a t i s f i e dw i t ht h et r a d i t i o n a lm e t h o d ao fq u e r i e sa n ds t a t i s t i c s ，b u tl o n g i n gt of i n d d e e p e rr e g u l a t i o n sa n dr e l a t i o n sb e t w e e nd a t at op r o v i d es u p p o r tt od e c i s i o nm a k e r s s od a t am i n i n gt e c h n o l o g ym e r g e d a s s o c i a t i o nr u l em i n i n gi sab r a n c ho fd a t a m i n i n gt e c h n o l o g y w 曲t h ed e f i n i t em i n i m a ls u p p o r ta n dm i n i m a lc o n f i d e n c e ， a s s o c i a t i o nr u l em i n i n gc a nd i s c o v e rt h er e l a t i o n sb e t w e e nd a t af i , o mt r a n s a c t i o n d a t a b a s e ，a n dr e p r e s e n tt h e ma st h ea s s o c i a t i o nr u l e s 硼m a i nw o r k so f t h i sp a p e r 撇a sf o l l o w s ： 1 w r ed i s c u s s e dd a t am i n i n gt e c h n o l o g y , i n c l u d i n gi t sb a c k g r o u n d , n o r m a l p r o c e d u r e ，n o r m a lt e c h n i q u ea n dm e t h o d s ，a n dc u r r e n td i f f i c u l t i e sa n dc h a l l e n g e s 2 w ed i s c u s s e da s s o c i a t i o nr u l em i n i n gt e c h n o l o g y , i n c l u d i n gi t sb a c k g r o u n d ， p r o b l e md e s c r i p t i o n , n o r m a lm i n i n gp r o c e d u r e ，m i n i n gc a t e g o r y , a n dt h ep r o b l e m s w h i c hc 1 ：k r r e n ta l g o r i t h m sa r ef a c i n g 3 w ed i s c u s s e dc l a s s i c a la l g o r i t h m so fa s s o c i a t i o nr u l e sm i n i n g ，i n c l u d i n g a p r i o f ia l g o r i t h ma n ds e 聊a l g o r i t h m 4 t os o l v et h ed i s s a t i s f a c t o r yd a t ac o m p r e s s i o np r o b l e mo fc l a s s i c a la l g o r i t h m s b yu s i n gh o r i z o n t a ld a t al a y o u tt r a n s a c t i o nd a t a b a s e ，w ep r e s e n tt h ef c i - b a s e ds t o r a g e s t r u c t u r eo ft r a l s 枷o nd a t a b a s e ，w h i c hu s e sv e r t i c a ld a t al a y o u t t h e nw es t u d i e d a l g o r i t h m sf o rm i n i n g 丘e q u e n ti t e m s e t w h i c hw e i eb a s e do nt h ef c i - b a s e ds t o r a g e s t r u c t u r eo f 仃a u s a c f i o nd a t a b a s e 5 a p p l i e dt h ea s s o c i a t i o nr u l em i n i n ga l g o r i t h mb a s eo nt h ef c i - b a s e ds t o r a g e s t r u c l u r eo fu a n s a c t i o nd a t a b a s et ot h eg r o u pm e n t a lh e a l t he v a l u a t i o ns y s t e m w e a n a l r z e dt h er e l a t i o n sb e t w e e nd i f f e r e n tp s y c h o l o g i c a lf a c t o r sb yd o i n ga s s o c i a t i o n r u l em i n i n gf r o mt h et e s t i n gd a t a , t op r o v i d ee v i d e n c ef o rp s y c h o t h e r a p ya n dt o m a i n t a i np e o p l e sm e n t a lh e a l t h k e y w o r d s d a t am i n i n g , a s s o c i a t i o n r u l e s ，f r e q u e n tc o m p l e m e n t a r yi t e m , p s y c h o a n a l y s i s 浙江大学硕士学位论文图目录 图目录 图2 - 1 数据挖掘的一般过程9 图5 一l 表5 - l 所示的事务数据库的频繁补项存储结构3 2 图6 - l 团体心理健康评估系统功能模块4 3 图6 2 团体心理健康评估系统的硬件组成4 4 图6 _ 3 并行数据采集设备；红外线信号接收器和红外线答题器4 7 图6 4 最小置信度阈值为5 0 时不同支持度的关联规则数量5 2 图6 5 最小置信度阈值为5 0 时不同支持度的程序运行时间5 3 i 珏 浙江大学硕士学位论文 袁目录 表3 - 1 表3 - 2 表5 - 1 表5 2 表5 3 表5 - 4 表6 - 1 表6 - 2 表6 - 3 表目录 购物篮事务的例子1 5 购物篮数据的二元0 1 表示1 6 原始事务数据库( 水平数据布局形式) 2 8 转化后的事务数据库( 垂直数据布局形式) 2 9 事务数据库( 二进制形式表示的垂直数据布局形式) 2 9 过滤后的事务数据库( - - 进制表示的垂直数据布局形式) 3 0 测量表的数据库表格设计5 0 原始事务数据库中的部分事务5 1 挖掘顺序列表5 2 浙江大学硕士学位论文第1 章绪论 第1 章绪论 1 1 研究背景 改革开放以来，我国的社会生活正发生着深刻变化，各种新思想、新事务不 断进入人们的生产生活当中。这种变化对人们的生活方式产生较大的影响，同时 也在潜裼默化地影响着人们的心理。据调查，我国社会不同团体中分别出现不同 的心理问题，各种心理问题不断困扰着各个团体。例如，高校大学生团体中的心 理问题越来越突出；股民因为受股市波动的影响，心理问题也在不断出现。良好 的心理是健康的身体的一个重要组成部分。由于团体中成员数量较多，因此需要 一种自动化的方法来完成对团体的心理测验和分析，以了解团体心理状况，分析 团体心理问题，促进团体心理健康。 心理测验又叫心理评估，是关于心理测量的一门技术，用于测量心理特征的 个体差异。心理测验的功能有：甄别能力、发现特殊才能、协助诊断、心理咨询。 心理测验虽然重要，但在团体开展的并不理想，其原因：我国缺乏适合团体的心 理健康测验工具；测量手段落后，填表法、单机测验法，测验慢、处理慢、易出 错。因此，利用计算机技术研制新的心理测试系统，以进行自动化、批量化、并 行化心理测验，以提高心理测验效率，对目前团体的心理教育具有直接意义。本 文提出的心理健康评估系统采用红外并行采集技术，能够完成团体并行心理测 试，从而了解团体的心理状况，进行团体心理教育和疏导工作。 心理测试的目的不仅仅是得到测试结果，而且要分析测试结果，从测试结果 中了解测试对象的心理状况，从而对症下药、采取心理治疗措施，促进测试对象 的心理健康。在心理测试中，测试对象往往是数以万计的人员，对每个人员的测 试指标也通常成百上千，这样得到的测试结果是海量的。如何从海量的测试结果 中了解到测试对象的心理状况，成为心理测试的一个关键问题。人工分析海量数 据是耗时的，而且由于人类身体上的缺陷，人工分析容易出错，分析结果还有可 浙扛大学硕士学位论文第l 章绪论 能受到人们主观偏见的影响，这对正确得到测试对象的实际心理状况是不利的。 因此，研究并利用先进的智能数据分析技术，从大规模的测试结果中分析出有用 的知识，对了解测试对象的心理状况具有很重要的意义 智能数据分析技术从属于数据挖掘技术，它不仅可用于分析心理测试结果， 而且在基因数据分析、天体识别、市场分析、信用卡风险鉴别、网络故障诊断等 各方面都具有很广泛的应用前景。目前已经涌现出很多技术方法可以用于数据分 析。数据挖掘现在正逐渐成为国内外各研究机构的研究热点，包括关联规则挖掘、 人工神经网络、决策树、支持向量机等在内的很多技术都可以用于进行数据挖掘。 关联规则挖掘是发现大数据集中项之间的关联性或相关性，并以关联规则的形式 将这种联系表现出来。关联规则是当前堋研究的热点。但是，目前关联规则挖 掘的研究还存在一些问题，包括算法效率、挖掘的交互性、挖掘算法的并行性、 挖掘语言的研究和增量挖掘研究等。因此，研究新的关联规则挖掘算法，并将其 应用于心理分析中，可以充分利用数据挖掘技术来解决心理分析问题中人工分析 效率低下、易出错、可靠性不高的缺点，具有很强的现实意义。 本文以团体心理健康评估系统为应用背景，研究了基于事务数据库的频繁补 项存储结构的关联规则挖掘算法，并将算法应用于团体心理健康评估系统中，以 分析影响心理健康的几种因素之间的联系，从而为医生治疗心理疾病提供依据， 促进人们心理健康文中提出的关联规则挖掘算法不仅可以运行于心理分析中， 而且可以推广到其它应用当中，具有巨大的应用和社会价值。 1 2 本文工作 本文主要研究了数据挖掘技术中的关联规则挖掘。关联规则挖掘通常分解为 下面两个步骤来执行；生成频繁项集；生成规则。相对频繁项集生成而言，规则 的生成较为简单和直观。通常，生成频繁项集所需的计算开销远大于生成规则所 需的计算开销。目前，对关联规则挖掘的研究主要集中在提高频繁项集生成的效 率上。本文的工作也主要集中在关联规则挖掘步骤中的第一步，即频繁项集挖掘 匕。 2 浙江大学硕士学位论文第1 章绪论 ( i ) 关联规则挖掘的理论研究 关联规则挖掘是在海量数据中挖掘出各数据之间的相互联系，并以关联规则 的形式表现出来。本文在阅读大量文献的基础上，分析了目前关联规则挖掘算法 的种类、存在问题等。 ( 2 ) 事务数据库的频繁补项存储结构 采用精简压缩的数据结构存储事务数据库，对关联规则挖掘算法的效率影响 较大。传统的关联规则挖掘算法大都没有对事务数据库进行处理，直接读取事务 数据库，即采用水平数据布局数据库形式。本文提出一种链表与数组相结合的事 务数据库的频繁补项存储结构，使事务数据库得到有效压缩，并可以一次性装入 内存。这样可以避免频繁扫描事务数据库，显著提高算法效率。 ( 3 ) 频繁项集挖掘 频繁项集挖掘是关联规则挖掘的第一步。传统关联规则挖掘算法如经典 a p r i o r i 算法一般利用宽度优先的搜索策略，通过多次遍历事务数据库来发现所 有的频繁项集。这种方法需要多次遍历巨大的事务数据库，产生大量的i 0 ，使 得算法效率难以提高。目前的研究重点主要集中在设计压缩的数据结构，将巨大 的事务数据库存储在压缩的数据结构中，以便一次性装入内存，减少i 0 ，提高 算法效率。本文将事务数据库存储在数组和链表相结合的频繁补项存储结构中， 这种存储结构使事务数据库得到有效压缩而又不使信息丢失，频繁项集的挖掘在 这种频繁补项存储结构中进行。 ( 4 ) 频繁项集挖掘在团体心理测试系统中的应用 本文将基于事务数据库的频繁补项存储结构的频繁项集挖掘方法应用于团 体心理健康评估系统中。在对团体心理进行团体测试的基础上，得到大量的测试 结果。再利用关联规则挖掘算法对所得到的测试结果进行关联规则挖掘，从而发 现团体中人们心理各影响因素之间的联系，指导心理医生的心理治疗，促进人们 的心理健康。 浙江大学硕士学位论文第l 章绪论 1 3 论文结构 本文的组织结构如下： 第1 章先简要介绍了团体心理健康评估系统的项目背景，提出了系统中的数 据挖掘要求。然后介绍了本文所作的主要工作：分析了目前关联规则挖掘算法的 研究现状，提出了事务数据库的频繁补项存储结构，并在此存储结构的基础上研 究了频繁项集挖掘算法。最后介绍了本文的结构。 第2 章分析了数据挖掘技术的研究现状。在阅读大量文献的基础上，本文介 绍了数据挖掘技术的起源、任务与功能、一般挖掘过程、挖掘技术和方法以及当 前挖掘算法面临的困难与挑战等。 第3 章介绍分析了关联规则挖掘的研究现状。首先介绍了关联规则挖掘的基 本概念和一般步骤：关联规则挖掘通常分为频繁项集生成和强规则生成两个步 骤，其中频繁项集生成是关联规则挖掘中最耗时最重要的一步。接着介绍了关联 规则挖掘算法的种类和当前挖掘算法存在的问题。 第4 章介绍了经典的关联规则挖掘算法：a p r i o r i 算法和s e t m 算法。a p r i o r i 算法需要频繁扫描庞大的事务数据库，产生大量i o ，算法效率不尽如人意，还 有待改进在s 聊算法执行过程中，候选项集在它出现的每条事务中复制，因 而导致了大量的中间结果，而且，项集必须直接排序，即以升序对项集中的项进 行列表，会付出一定的时间代价。 第5 章提出了对a p r i o r i 关联规则挖掘算法的改进。首先提出了事务数据库 的压缩表示：链表与数组相结合的事务数据库的频繁补项存储结构。接着在频繁 补项存储结构的基础上，提出了关联规则挖掘中的频繁项集挖掘挖掘算法。 第6 章将本文提出的改进算法应用于团体心理健康评估系统中。在采集到心 理测试结果的基础上，利用关联规则挖掘算法对所得到的测试结果进行关联规则 挖掘，从而发现团体心理各影响因素之间的联系，指导心理医生的心理治疗，促 进人们的心理健康。 第7 章总结了本文工作和将来的努力方向。 4 浙江大学硕士学位论文 第2 章数据挖掘概述 第2 章数据挖掘概述 2 1 数据挖掘的产生背景 当今时代可谓是信息化的时代。1 9 4 6 年，世界上第一台计算机e n i a c 在美国 宾夕法尼亚大学诞生，为人类开辟了一个崭新的信息时代，使得人类社会发生了 巨大的变化半个多世纪，特别是2 0 世纪8 0 年代以来，信息技术得到了迅速发 展。首先，计算机的性能大幅度提高，但其价格却大幅度下降。2 0 世纪6 0 年代 中期，i n t e l 总裁m o o r e 曾经提出著名的摩尔定律。他预言，i c 上可容纳的晶体 管和电阻器数目，约每隔1 8 个月便会增加一倍，性能也将提升一倍；而其价格 却会以反比的速度大幅度降低。几十年来，摩尔定律在实践中得到了很好的验证。 正是计算机性能的不断提高和价格的不断下降，为以计算机为基础的信息技术的 广泛应用创造了条件，这就是自2 0 世纪8 0 年代以来发生的“微机革命”。计算 机不再是国家、研究所或是大型企业才能拥有的，只能用于科学计算、军事研究 等尖端领域的大型机器：相反，计算机带着生产、办公、教育、娱乐等功能，走 进了各个企业、科研单位和千家万户。计算机的广泛普及，迫切要求各用户能够 共享资料、相互交流。互联网( i n t e r n e t ) 技术应运而生。i n t e r n e t 把分布在世 界各地的计算机、计算机网络联接在一起，构成一个覆盖全球的超级计算机网络。 它覆盖全球，具有多种信息传送方式和服务类型，涉及到的行业和领域涵盖人类 社会盼各个方面，比如政治、军事、科学、技术、文化、教育、医疗卫生、经济、 商务以及邮电通信等。i n t e r n e t 和信息高速公路的出现，为把信息技术应用到社 会生活的各个方面创造了条件。耳前，信息技术已经广泛渗透到各行各业中，大 量的信息技术在各个领域得到充分应用，使得人类文明开始进入一个崭新的数字 化阶段。毫无疑问，信息技术的研究与应用水平是体现区域优势的重要手段与依 据。 在信息技术的众多应用中，有一类称为数据密集型应用的重要应用( d a t a i n t e n s i v ea p p l i c a t i o n s ) 。这类应用所涉及的数据量极大，一般内存中只能暂 浙江大学硕士学位论文 第2 章数据挖掘概述 存其中的一小部分，而全部数据需要存放在辅助存储器中；所涉及的数据一般为 持久数据( p e r s i s t e n td a t a ) ，即数据不是随着程序的运行而消失，而需要长期 保存在计算机系统中；应用所涉及的数据也不是为一个程序所独有，而是由多个 应用程序所共享，甚至在一个企业、地区、国家乃至全球共享。这是最大的计算 机应用领域，电子办公系统、管理信息系统、银行系统、民航订票系统、情报检 索系统等属于这一类。如何对大量、持久、共享的数据进行管理，是这类计算机 应用所面临的共同问题。早期的数据管理都采用文件系统。文件系统曾经在一定 时期内满足了这种需求，然而，由于文件系统具有编写应用程序很不方便、无法 避免数据冗余、不支持并发访问等缺点，信息技术的发展越来越要求一种新的数 据管理方法来提供更加强大的功能。数据库系统就是针对这些需求而产生的，以 统一管理和数据共享为主要特征的系统。在数据库系统中，数据不再由某一应用 程序或用户所独享，而是由一个数据库管理系统( d b 脑) 来统一管理。一般的数 据库管理系统都具有提供高级用户接口、查询处理和优化、数据目录管理、并发 控制、数据恢复、完整性约束检查和访问控制等功能，可以很好地满足数据管理 的要求。 信息技术总是以超乎人们想象的速度发展。在各种信息技术推广应用的同 时，积累了大量的数据，比如电子商务系统积累了客户的历史交易数据。据统计， 在i n t e r n e t 上传播的信息每月增长l o 以上，一年下来，其增长率可达2 0 0 9 6 以 上；目前全球的互联网网页数已达到8 亿个，这意味着“一个人不吃不睡不停地 浏览，而且以一秒钟看一页的速度也需要2 5 年零4 个月”。当前，企业和个人所 面临的不是信息短缺，数据逐步积累膨胀，将人类带入一个信息爆炸的时代。 信息爆炸时代的到来，使得我们可以很方便地获取各种信息。但网络信息量 的迅速增加，也加大了用户搜寻、选择有用信息的难度，造成了个人需求有限与 网络信息无限的矛盾。大量的信息带来了很多问题：我们发现自己处于信息的海 洋中，各种真假信息难以识别和消化，很难从浩瀚的数据海洋中提取出企业真正 需要的知识，企业普遍面临数据爆炸而有效的信息和知识却相对短缺的状态，因 此如何处理信息和提取知识已经成为当前企业迫切需要解决的问题。 6 浙江大学硕士学位论文 第2 章数据挖掘概述 我们对企业处理的信息进行分析，发现处理的信息类型主要有事务型处理和 信息型处理两大类。事务型处理也就是通常所说的业务操作处理，这种操作处理 土要是对管理信息进行日常操作，对信息进行查询和修改，从而满足企业特定的 日常管理需要。在这类处理中，管理者关心的是信息的迅捷处理、安全性能的保 证等方面。信息型处理则是指对信息做进一步的分析，从而为企业的管理人员提 供决策支持。信息数据往往隐含许多不为人知的有意义的信息和知识，而这些信 息和知识往往具有较高或者很高的价值，并可以为决策层进行决策提供依据。比 如为决策支持系统、经理信息系统等提供信息分析的支持，这种管理信息的信息 型处理，与传统的事务型处理只对当前的信息感兴趣的不同，必须访问大量的历 史数据才能完成，我们上面论述的提取知识也主要针对信息型处理数据而言的。 传统的数据库系统虽然在联机事务处理( o l t p ) 中获得了较大的成功，但其 服务重点在数据查询和处理方面，而无法满足管理人员的决策分析要求。管理人 员希望对企业中的大量数据进行分析，了解企业业务的发展趋势，而传统数据库 中只保留当前的管理信息，缺乏决策分析所需要的大量历史信息。数据挖掘“6 】 和知识发现( d m k d d ) 技术正是针对这一需求而产生的。数据挖掘( d a t a m i n i n g ) 起源于六、七十年代的人工智能和机器学习，实际上是一种文本型数据的模式识 别和知识发现，因此它也被称作数据库中的知识发现( k d d ) 。数据挖掘就是从大 量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中 的、人们事先不知道的、但又是潜在有用的信息和知识的过程。数据挖掘是为了 更好地适应应用的需求而产生的一种技术，目前已经在众多领域有了广泛的应 用，包括金融分析、w e b 挖掘、文档分析、通信警告分析、网络入侵检测和生物 信息学等。 2 2 数据挖掘的主要任务和功能 数据挖掘的主要功能是确定数据挖掘任务中要找的模式类型。数据挖掘任务 一般可以分为描述和预测两大类，描述性挖掘任务主要是刻画数据库中数据的一 般特性，预测性挖掘任务是在当前数据上进行推断，以进行预测。 7 浙江大学硕士学位论文 第2 章数据挖掘概述 数据挖掘功能以及它们可以发现的模式类型介绍如下： ( 1 ) 分类、预测o 町 分类就是通过研究已分类的样本集的特征，分析样本集的属性，建立一个分 类函数或分类模型，通过这个分类模型，未分类的或新的数据就可以分派到不同 的类别中，达到分类的目的分类和预测的应用十分广泛，例如，可以建立一个 分类模型，对银行的贷款客户进行分类，以降低贷款的风险；也可以通过建立分 类模型，对工厂的机器运转情况进行分类，用来预测机器故障的发生。 ( 2 ) 关联分析叭删 数据库中的数据之问一般都存在某种关联关系，即变量之间可能存在某种规 律，关联规则挖掘的任务就是找出数据库中哪些事物或属性共同出现的条件。随 着大量数据不停地收集和存储，许多业界人士对于从他们的数据库中挖掘关联规 则越来越感兴趣。从大量商务事务记录中发现有趣的关联关系，可以帮助许多商 务决策的制定。例如，可以通过关联规则挖掘来发现超级市场哪些商品经常被同 时购买，商家可以利用这些关联信息来确定进货的计划、商品应该如何摆放等， 可能可以诱发购买这些商品的顾客一路挑选其它的商品。由此可见，关联规则挖 掘能给企业带来极有价值的信息和知识。 ( 3 ) 聚类分析 聚类是将对象集合按照相似性归为若干类别，属于无指导分类，属于同一类 的对象具有较高的某种相似性，而不同类的对象之间的差别较大。通过聚类，识 别密集和稀疏的区域，发现全局的分布模式及数据属性之间的相互关系，帮助人 们建立宏观概念。聚类形成的每个类可以看作一个对象类，由它可以导出规则。 聚类也便于将观察到的内容组织成分层结构，把类似的事件组织在一起。 ( 4 ) 类概念描述“嘲 数据库中通常存放大量的细节数据。然而，用户通常希望以简洁的描述形式 观察汇总的数据集。用汇总的、简洁的、精确的方式描述每个类和概念，可以对 数据进行浓缩，给出它的总体的综合描述，实现对原始数据的总体把握。这种类 或概念的描述称为类概念描述。通过类概念描述使得人们能够在复杂数据库中 8 浙江大学硕士学位论文 第2 章数据挖掘概述 了解数据的意义以及产生数据的过程。 ( 5 ) 孤立点分析“3 “” 数据库中可能包含一些数据对象，它们与数据的一般行为或模式不一致，这 些数据对象就是孤立点。许多数据挖掘算法会将孤立点视为噪声或异常而丢弃， 使其影响最小化。但在一些特殊应用中，孤立点本身可能是非常重要的信息。例 如在欺诈探测中，孤立点可能预示着欺诈行为，这时孤立点显得比正常数据还重 要。 ( 6 ) 演变分析“删 数据演变分析描述行为随时问变化的对象的规律和趋势，并对其建模。可以 从股票交易数据中挖掘出整个股票市场和特定公司的股票演变规律，以帮助预测 股票市场的未来走向，帮助对股票投资做出决策。 2 3 数据挖掘的一般过程 数据挖掘过程吼酊不是一个线性的，而是由多个步骤相互连接、反复进行的 人机交互过程。一个完整的数据挖掘过程一般包括问题描述、数据选择、数据预 处理、数据转换、运行数据挖掘算法、结果评价，如图2 - 1 所示。 数据中心 目标数据预处理结果转换结果模式 知识 图2 - 1 数据挖掘的一般过程 ( 1 ) 问题描述 9 浙江大学硕士学位论文第2 章数据挖掘概述 闯题描述使领域专家、数据挖掘专家和用户之问的交流更为方便。领域专家 提出的翘题对他来说可能是清楚的，通过问题描述，可以让数据挖掘专家理解并 且能够选择恰当的解决方案在问题描述时要考虑诸如领域瓶颈、挖掘目标、人 机分工、评价标准等因素。在问题描述阶段，还应该根据知识的最终使用者确定 知识的表现形式，这样用户可以很好的利用挖掘结果。 ( 2 ) 数据选择 由于实际信息系统中的数据存储形式一般是多种多样的，对数据的选择往往 会涉及到多个系统，因此需要数据处理技术的支持，来统一各种数据形式。数据 选择阶段的任务就是通过数据库接口程序从数据库或数据仓库中选择相关的数 据，创建一个目标数据集，并以数据挖掘算法能访问的格式存放起来。数据仓库 技术是目前在数据挖掘中广泛采用的数据处理技术。所谓数据仓库是指面向主题 的、集成的、稳定的、不同时间的数据集合，用以支持经营管理中的决策制定过 程。 ( 3 ) 数据预处理 从多个数据库收集而成的大型的、现实世界数据库或数据仓库的共同特点。 是其中数据的不完整性和不一致性，数据中可能含有噪声和其它异常数据。数据 预处理的目的是通过一定的方法尽可能消除数据的不完整性和不一致性，以降低 实际挖掘所需要的时间，提高数据挖掘算法的效率、精度和有效性，提高数据挖 掘模式的质量。数据预处理的方法主要有数据清理、数据集成和变换、数据归约 等。 ( 4 ) 数据转换 数据转换包括数据的约简和变换。所谓数据约简是通过某种方法降低挖掘算 法的搜索空间，通常分为垂直约简和水平约简。垂直约简是使用降维或变换方法 减少变量数目( 在数据库中用属性表示) ，而水平约简是通过对象的分析如离散 化、泛化等，合并具有相同属性值的对象，减少对象数目。数据变换就是针对不 同的数据挖掘算法有不同的数据输入格式，对数据进行编码，使其成为挖掘方法 所要求的格式。 1 0 浙江大学硕士学位论文第2 章数据挖掘概述 ( 5 ) 数据挖掘 数据挖掘阶段是数据挖掘过程的核心内容，也是知识发现过程的难点。该阶 段应用挖掘算法从预处理的数据中发现模式。为了获得满意的结果，需要考虑数 据挖掘的类型、数据挖掘的方法和挖掘的效率。 ( 6 ) 结果评价 数据挖掘的结果是否符合用户要求，是否具有价值，需要通过结果评价阶段 来判断。结果评价解释并评价数据挖掘出来的模式。去掉多余的不切题意的模式， 转换成某个有用的模式，并把这些模式、规则和知识运用到实际的运行系统中， 用以验证它们的正确性和有效性。 2 4 数据挖掘的常用技术和方法 因为对数据挖掘的研究涉及到不同学科领域的技术和成果，目前数据挖掘技 术和系统也多种多样，主要有以下几神类型“”； ( 1 ) 关联规则挖掘 关联规则挖掘是发现大数据集中项之间的关联性或相关性。如发现交易数据 库中不同商品( 项) 之阗的联系，找出顾客购买行为模式，如购买了某一商品对 购买其他商品的影响。发现这样的规则可应用于商品货架设计、货物安排以及根 据购买模式对用户进行分类。关联规则是当前删研究的热点。 ( 2 ) 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ) 人工神经网络是由大量类似于神经元的处理元相互联结而成的非线性复杂 网络系统。人工神经网络方法模拟人脑神经元结构，以 i p 模型和h e b b 学习规则 为基础，建立三大类多种神经元网络，它具有较强的并行处理能力和高度的自学 习、自组织和自适应能力。前馈神经元网络以感知器网络、b p 网络等为代表，可 以用于分类和预测等方面；反馈式网络以h o p f i e l d 网络为代表，用于联想记忆 和优化计算：自组织网络以a r t 模型、k o h o n o n 模型为代表，用于聚类。 ( 3 ) 决策树 决策树方法利用信息论中的信息增益寻找数据库中具有最大信息量的字段， 浙江大学硕士学位论文第2 章数据挖掘概述 建立决策树的一个结点，再根据字段的不同取值建立树的分支，然后在每个分支 子集上重复建立树的下一层结点和分支。它用树型结构来表示决策集合这些决 策集合通过对数据集合的分类产生规则。决策树方法具有分类准确率高、生成的 规则简单等待点，它主要应用在数据挖掘的分类方面。国际上最早和最有影响的 决策树方法是q u i u l a n 提出的i d 3 方法，目前已经出现了在i d 3 方法的基础之各 种决策树的改进算法。 ( 4 ) 支持向量机( s ) 支持向量机是在统计学习理论的基础上发展起来的机器学习方法”。它根 据结构风险最小化原则，尽量提高学习机的泛化能力，具有良好的推广性能和较 好的分类精确性，能有效的解决过学习问题，现已成为训练多层感知器，r b f 神 经网络和多项式神经元网络的替代性方法。另外，支持向量机算法是一个凸优化 问题，局部最优解一定是全局最优解，这些特点都是包括神经元网络在内的其它 算法所不能及的。支持向量机可以应用于数据挖掘的分类、回归、对未知事物的 探索等方面。 ( 5 ) 遗传算法( g e n e t i ca l g o r i t h m s ，g h ) 脚 遗传算法是一种受生物进化启发的学习方法，它是在适应度函数约束下的智 能化搜索，在目标函数驱动下“优生劣汰”。这样通过多次迭代，逐步逼近目标。 遗传算法由三个基本过程组成：繁殖( 选择) 是从一个旧种群( 父代) 选出生命 力强的个体，产生新种群( 后代) 的过程；交叉( 重组) 选择两个不同个体( 染 色体) 的部分( 基因) 进行交换，形成新个体的过程；交异( 突变) 是对某些个 体的某些基因进行变异的过程。遗传算法己在优化计算和分类机器学习方面显示 了明显的优势。在数据挖掘中，可以被用作评估其他算法的适合度。 ( 6 ) 粗糙集( r o u g hs e t ) 方法 粗糙集理论是一种研究不精确、不确定性知识的表达、学习、归纳的数学工 具。它可以在缺少先验信息的情况下，只以考察数据的分类能力为基础，解决模 糊或不确定数据的分析和处理问题。粗糙集理论可以应用于数据挖掘中的分类、 发现不准确数据或噪声数据内在的结构联系；它与其他数据挖掘方法，如神经网 浙江大学硕士学位论文第2 章数据挖掘概述 络、模糊集理论、遗传算法结合起来，能够分析和处理更为复杂的菲线性化、非 结构化问题。 ( 7 ) 模糊集方法 模糊集方法利用模糊集理论对实际问题进行模糊评判、模糊决策、模糊模式 识别和模糊聚类分析模糊性是客观存在的系统的复杂性越高，精确化能力就 越低，即模糊性就越强。这是z a d e h 总结出的互克性原理。危机管理是一类带有 大量不确定因素的非结构化问题，模糊论方法具有一定的应用前景 ( 8 ) 贝叶斯网络 贝叶斯网络是用来表示变量集合的连续概率分布的图形模式，它提供了种 自然地表示因果信息的方法，用来发现数据间的潜在关系。贝叶斯网络的学习也 就是要找出一个能够最真实反映现有数据库中各数据变量相互之间的依赖关系 的贝叶斯网络模型。贝叶斯网络模型在处理不定性问题上具有许多优势，这是因 为它把图形理论的表达和计算能力与概率理论有机地结合在一起。贝叶斯网络模 型成为当前人工智能领域中不定性知识表达和推理的一个研究热点。 2 5 数据挖掘面临困难与挑战 数据挖掘是一个相对年轻而又非常活跃的研究领域，它虽然具有广泛的应用 领域，但还有很多的研究难题和面临的挑战。 ( 1 ) 有效处理巨量和高维数据 目前，百万条记录或数千兆字节的数据库已经司空见惯。数据挖掘的产生与 发展，一部分原因就是传统数据库无法处理这种巨量和高维数据，而处理这种数 据也成为数据挖掘技术的研究难点。超大规模的数据，不仅导致挖掘算法的搜索 空间异常巨大，而且容易搜索出许多无用数据。为了解决这些问题，需要有高效 的特别是线性复杂度算法、并行处理技术等。 ( 2 ) 改进用户交互性和充分利用背景知识 目前的数据挖掘研究重点往往在算法效率上，大多数数据挖掘系统还没有充 分考虑到用户的参与而交互性较差。只有通过图形、自然语言和可视化技术把发 浙江大学硕士学位论文第2 章数据挖掘概述 现的关系、规则、概念表示出来用户才能更好地评价和识别。有效的决策往往需 要交互和反复，用户的背景知识和指导作用可以加快挖掘过程。 ( 3 ) 数据噪声与缺值 通常把数据输入或汇集过程中发生的非系统误差称之为嗓声。错误或嗓声可 能来自于数据录入的误操作。通常要用概率方法来发现和表示带噪声的数据模 式。关系数据库中可能存在很多空值，这可能对数据挖掘造成缺值；另外在数据 库设计阶段遗忘考虑的某些属性或字段也可能造成缺值。对这种倩况，应当采用 具有决策能力的数据挖掘模型，主要的方法有模糊集合论和粗糙集理论。 ( 4 ) 数据的动态变化和知识的更新维护 数据通常具有动态变化的特点，这时，原有的模式不再有效。数据挖掘方法 应当具有增量( 渐进式) 学习的能力。 1 4 浙江大学硕士学位论文第3 章关联规则挖掘概述 第3 章关联规则挖掘概述 3 1 关联规则挖掘的产生背景 关联分析是数据挖掘领域的重要研究内容，它由r a g r a w a l 等人首先提出以 解决事务数据库分析等问题。关联规则挖掘的目的是寻找在大量的数据项中隐藏 着的联系或者相关性。在大量数据基础上挖掘出来的关联规则经常表明了某条规 律。关联规则可以揭示数据项间的依赖关系，以从一个数据对象的信息来推断另 一个数据对象的信息这种规律或依赖关系可以帮助人们做出决策，比如天体识 别、基因的相似性分析、市场分析、信用卡风险鉴别、网络故障诊断等。 关联规则应用的一个典型例子是购物篮分析嘲。如表3 - 1 所示。系统通过对 顾客在同一购物篮中所购买商品之间的联系的分析来调查顾客的购买行为模式， 了解顾客的购买习惯及行为特征。借此可以辅助零售商制定市场营销策略。例如， 在布置卖场时，将顾客经常一同购买的商品放置在一起，这样可以裁激顾客的消 费欲望，增加销售额。关联规则的挖掘通过规则的支持度和置信度进行兴趣度度 量，这两种度量反陕了所发现规则的有用性和确定性。一个关联规则是有趣的， 意味着它满足最小支持度阈值和最小置信度阙值。阈值由领域专家和用户设定。 一旦发现了有趣的规则，可以帮助零售商有选择地推销，从而引导消费。 表3 - i 购物篮事务的例子 t i d 项集 蛋乐酒乐鸡可啤可 ， ， ， ，酒酒布布啤啤尿尿奶布布奶奶牛尿尿牛牛包包奶包包面面牛面面 浙江大学硕士学位论文 第3 章关联规则挖掘概述 3 2 闯题描述 目前国内外已经有许多研究机构和研究者对关联规则挖掘问题进行了研究。 为了方便研究，一些研究者对关联规则挖掘问题进行了一些概念定义，这些定 义描述已经为大多数研究者所接受。 二元表示：表3 - l 所示的购物篮事务可以用二元形式来表示，如表3 - 2 所示。 表中的每一行对应一个事务，每列对应一个项。项可以用二元变量表示，如果项 在事务中出现，则它的值为1 ，否则为0 。 表3 - 2 购物篮数据的= 元0 1 表示 t i d 1 2 3 4 5 面包牛奶尿布啤酒鸡蛋 可乐 0 0 l o l 项集( i t e m s e t ) ：令i = ，易，毛) 是购物篮数据中所有项的集合，包含0 个或多个项的集合称为项集。如果一个项集包含| 个项，则称它为_ j 一项集。例如， 面包，尿布，啤酒) 是一个3 一项集。空集是指不包含任何项的项集。 事务( t r a n s a c t i o n ) ：设r = f l ，t ，“ 是所有事务的集合，其中每个事务 包含的项集都是，的子集。事务的宽度是事务中出现项的个数。如果项集x 是事 务，的子集，则称事务，包括项集石。 项集的支持度计数：项集的一个重要性质是它的支持度计数，即包含特定项 集的事务的个数。项集x 的支持度计数盯( x ) 用公式表示为： 盯( x ) = 4 识l x ，乃i 。其中，符号卜 表示集合中元素的个数。 频繁项集( f r e q u e n ti t e m s e t ) ：对一个给定的最小支持度阈值n f i n s u p ，项 集x 如果满足条件盯( x ) m i n s u p ，则称项集z 是频繁项集。 关联规则( a s s o c i a t i o nr u l e ) ：关联规则是形如z - l ，的蕴涵表达式，其 1 6 0 1 o o o 0 1 l l o 0 l l l l 1 0 1 l l l l o l 1 浙江大学硕士学位论文 第3 章关联规则挖掘概述 中x 和y 是不相交的项集，即x n y = a 。 支持度( s u p p o r t ) ：关联规则的支持度( s ) 定义为：j ( z - - ) y ) ：a ( _ x f u r 一) 度( c o n f i d e n c e ) ：关联规则的置信度( c ) 定义为：c 呻y ) = 里筹；产 关联规则可以用支持度和置信度来很好地判断其有效性和可信度。 支持度确定规则所表示的数据在整个数据集中出现的频繁程度。支持度是一 种重要度量，因为支持度很低的规则可能只在整个数据集中偶然出现。从商务角 度来看，低支持度的规则一般不会有很大的价值，比如对顾客很少同时购买的商 品进行促销一般不能产生利润。因此，支持度通常用来删去那些不令人感兴趣或 者价值不大的规则。 置信度表示y 在包含j 的事务中出现的频繁程度，置信度可以度量通过规则 进行推理的可靠性。对于给定的规则x 专】，置信度越高，y 在包含z 的事务中 出现的可能性就越大。置信度也提供在y 给定下的条件概率的估计。 关联规则发现：给定给定的事务集r ，关联规则发现是指从r