（计算机应用技术专业论文）基于聚类和压缩矩阵的apriori算法的研究与应用.pdf

苏州大学学位论文使用授权声明 本人完全了解苏州大学关于收集、保存和使用学位论文的规定， 即：学位论文著作权归属苏州大学。本学位论文电子文档的内容和纸 质论文的内容相一致。苏州大学有权向国家图书馆、中国社科院文献 信息情报中心、中国科学技术信息研究所( 含万方数据电子出版社) 、 中国学术期刊( 光盘版) 电子杂志社送交本学位论文的复印件和电子 文档，允许论文被查阅和借阅，可以采用影印、缩印或其他复制手段 保存和汇编学位论文，可以将学位论文的全部或部分内容编入有关数 据库进行检索。 涉密论文口 本学位论文属 在年一月解密后适用本规定。 非涉密论文口 论文作者签名： 导师签名：鼢谗秒 日期：垫! ! ：苎：il e l 期：型叫 关联规则挖掘是一种重要的数据挖掘技术，其主要研究目的就是从大型数据集中 发现隐藏的、有趣的、属性间的规律，即关联规则。针对关联规则经典算法a p r i o r i 算法的缺点已有许多学者做出改进，本文在已有改进算法的基础上，设计了一种基于 聚类和压缩矩阵( c l u s t e r & c o m p r e s s i o nm a t r i x ) 的a p f i o f i 改进算法叫c m _ a p r i o f i 算法。论文的主要内容如下： ( 1 ) 对数据仓库和数据挖掘技术进行阐述和归纳，重点介绍了聚类分析和关联规则 的基本概念、思想及代表算法，并分析了算法的优缺点。 ( 2 ) 运用聚类分析和布尔向量的关系运算思想，设计了一种基于聚类和压缩矩阵的 a p r i o f i 改进算法叫c ma p r i o r i 算法。该算法通过聚类和对相同事务的计数来压缩 矩阵以减小数据库规模，并且只需扫描一次数据库，无需产生候选项集直接生成频繁 项集，较大地提高了算法的效率。 ( 3 ) 在原有的高校教务管理系统中，运用数据仓库和c c m 成绩和历史选课记录预测学生选修的课程和人数，实现了选修课决策支持系统，为学 院选修课的开设提供决策支持。 关键词：数据仓库；数据挖掘；聚类分析；c c ma p r i o r i 算法；关联规则 作者：李志亮 指导老师：邓伟 a b s t r a c tr e s e a r c ha n da p p l i c a t i o no f a p r i o r ia l g o r i t h mb a s e do nc l u s t e ra n dc o m p r e s s i o nm a t r i x r e s e a r c ha n d a p p l i c a t i o no fa p r i o r ia l g o r i t h mb a s e do n c l u s t e ra nd c o m p r e s s i o nm a t r i x a b s t r a c t f r o mt h ed a t am i n i n gt h e o r ya p p e a r e di nl a s t19 8 0 s ，i th a sd e v e l o p e ds p e e d i l y d a t a m i n i n g i s b e c o m i n gm u c hm o r ei m p o r t a n ta s t h e a m o u n to fd a t a b a s e s k e e p s i n c r e a s i n g m a n yr e s e a r c h e r sh a v es h o w ng r e a ti n t e r e s ti nd a t am i n i n g t h ea p p l i c a t i o no f d a t am i n i n gi sa l s oe x t e n d e dt ov a r i o u sf i e l d s d a t am i n i n ge m e r g e da sar a p i d l yg r o w i n g t e c h n o l o g yi no r d e rt oe x t r a c tv a l u a b l ei n f o r m a t i o na n dk n o w l e d g ei nl a r g ev o l u m e so f d a t a a s s o c i a t i o nr u l e sm i n i n gi sa l li m p o r t a n tt e c h n o l o g yo fd a t am i n i n g ，w h i c hd i s c o v e r s p r e v i o u s l yu n k n o w na n di n t e r e s t i n gr e l a t i o n s h i p sa m o n ga t t r i b u t e si nt h el a r g ed a t a b a s e s m a n ys c h o l a r sh a v em a d ei m p r o v e m e n t st oa p f i o f ia l g o r i t h m t h i sa r t i c l ei so nt h eb a s i s o fi m p r o v e da l g o r i t h m ，w ed e s i g na l la l g o r i t h mw h i c hb a s e do nc l u s t e ra n dc o m p r e s s i o n m a t r i x - c c m _ a p r i o r ia l g o r i t h m t h ew o r k so f t h i sd i s s e r t a t i o na r ea sf o l l o w s ： ( 1 ) d e s c r i b e sa n ds u m m a r i z e sd a t aw a r e h o u s ea n dd a t am i n i n gt e c h n i q u e s ，t h e nf o c u s e s o nt h eb a s i c c o n c e p t s o fc l u s t e ra n a l y s i sa n da s s o c i a t i o n r u l e s ，i d e a s ，a n d o nt h e r e p r e s e n t a t i v ea l g o r i t h m s ，a tl a s ta n a l y z e st h e i ra d v a n t a g e sa n dd i s a d v a n t a g e s ( 2 ) u s e dc l u s t e ra n dr e l a t i o n s h i po p e r a t i o no ft h eb o o l e a nv e c t o r ，w ed e s i g na na l g o r i t h m w h i c hb a s e do nc o m p r e s s i o nm a t r i xa n dc l u s t e r t h ea l g o r i t h mr e d u c e st h es i z eo ft h e d a t a b a s eb a s e do na f f a i r sc o m p r e s s i o na n dc l u s t e r i ts c a n st h ed a t a b a s eo n l yo n c ea n dd o e s n o td i r e c t l yg e n e r a t ec a n d i d a t ei t e m s e t sg e t e df r e q u e n ti t e m s e t s t h u sr a i s e st h ea l g o r i t h m o p e r a t i o ne f f i c i e n c ye f f e c t i v e l y ( 3 ) u s i n gt h ed a t aw a r e h o u s ea n dc c m _ a p r i o r ia l g o r i t h mi nt h eo r i g i n a ls y s t e mo f e d u c a t i o n a la d m i n i s t r a t i o nm a n a g e m e n ts y s t e mi n c o l l e g e a c c o r d i n gt o t h es t u d e n t s h i s t o r ye l e c t i v er e c o r d sa n d t e s ts c o r e s ，w ec o u l df o r e c a s tt h en a m eo fe l e c t i v ec o u r s e sa n d t h en u m b e ro ft h es t u d e n t s ，a n dr e a l i z et h ee l e c t i v ec o u r s ed e c i s i o ns u p p o r ts y s t e m i t p r o v i d e sd e c i s i o ns u p p o r tf o ro p e n i n ge l e c t i v ec o u r s e si nt h ec o l l e g e k e y w o r d s ：d a t aw a r e h o u s e ；d a t am i n i n g ；c l u s t e ra n a l y s i s ；c c m _ a p r i o r ia l g o r i t h m ； a s s o c i a t i o nr u l e s ； i i w r i t t e nb y ：l iz h i l i a n g s u p e r v i s e db y ：d e n gw e i 2 1 数据仓库理论基础4 2 1 1 数据仓库基本概念4 2 1 2 数据仓库系统结构。5 2 1 3 数据仓库组成6 2 1 4 数据仓库与数据库的关系8 2 2 数据挖掘技术9 2 2 1 数据挖掘的定义和过程。9 2 2 3 数据挖掘特点1 0 2 2 4 数据挖掘的主要研究内容1 1 2 2 5 数据挖掘的常用方法1 2 2 2 6 数据挖掘当前热点1 5 2 2 7 数据挖掘未来研究方向1 6 第三章聚类和关联规则基础理论17 3 1 聚类分析1 7 3 1 1 聚类分析的数据类型1 7 3 1 2 主要聚类算法18 3 1 3k m e a n s 算法2 0 3 2 关联规则2 2 3 2 1 基本概念2 2 3 2 2 关联规则挖掘的分类2 3 3 2 3 关联规则研究方向2 4 3 2 4 关联规则挖掘步骤2 6 3 2 5a p r i o r i 算法2 6 3 2 6 f p g r o w t h 算法2 9 第四章基于聚类和压缩矩阵的a p r i o r i 改进算法3 1 4 1c c ma p r i o r i 算法3 2 4 2a p r i o r i 算法与c c m _ a p r i o r i 算法实例3 5 4 3c c m _ a p r i o r i 算法与a p r i o r i 算法及f p - g r o w t h 算法性能比较4 1 第五章c c ma p r i o r i 算法在高校教务系统中的应用。4 3 5 1 系统研究背景和意义4 3 5 2 系统开发说明4 3 5 - 3 选修课决策系统挖掘模型。4 4 5 4 系统实现与结果分析4 6 5 4 1 关联规则挖掘的实现4 7 5 4 2 选修课程决策分析的实现5 2 5 4 3 成绩查询分析的实现5 3 第六章总结与展望。5 5 6 1 总结5 5 6 1 1 本文主要工作及成果5 5 6 1 2 研究和开发方面的不足5 6 6 2 展望5 6 参考文献5 7 攻读硕士学位期间公开发表的论文6 0 至5 【谢6 1 基于聚类和压缩矩阵的a p f i o f i 算法 1 1 研究背景 随着信息时代的不断发展，人们更加迫切地需要掌握大量的知识。知识是一种概 念、规则、规律和模式，它不像数据和信息那样具体，但它却是人们不懈追求的目标。 将数据信息转化为知识表示，即从数据中发现模式，有多种提法：知识发现( k n o w l e d g e d i s c o v e r yi nd a t a b a s e ，k d d ) 、知识提取、数据挖掘( d a t am i n g ，d m ) 、数据采集等。 自1 9 8 9 年8 月第l 届国际联合人工智能学术会议上首次提出知识发现这一概念以来， 数据挖掘技术日益受到人们的关注【l 】，已经成为当前计算机领域的一大热点。 1 9 9 6 年k d d 国际会议上对k d d 下了最新的定义：k d d 是识别出存在于数据库 中有效的( v a l i d ) 、新颖的( n o v e l ) 、具有潜在效用的( p o t e n t i a l l yu s e f u l ) 乃至最终可理解 的( u l t i m a t l yu n d e r s t a n d a b l e ) 模式的非平凡过程。这里的模式就是我们所说的知识。 k d d 是一个多步骤的处理过程，包括数据预处理、数据挖掘、知识评估及同化。k d d 过程如图1 1 所示。 数选择目标 预处理 预处理 转换 转换 数据。 模 知识 知 rr rr 同一七7 j ljlj l 院j钮 式识据数据数据数据 j l 1r 图1 1 知识发现过程 数据挖掘可以从大型数据库中的大量原始数据中提取人们感兴趣的、隐含的、尚 未被发现的、有用的信息和知识。数据挖掘是一个融合数据库、机器学习、数理统计、 可视化和信息科学技术为一体的新兴的交叉学科领域【2 】。它的发展可以帮助人们从数 据库，特别是数据仓库的相关数据集中提取出感兴趣的知识、规则或更高层次的信息， 并可以帮助人们从不同角度去分析它们，从而可以更加有效地利用数据库或数据仓库 中的数据。数据挖掘技术不仅可以用于描述过去数据的发展过程，还可以进一步预测 未来趋势。 第一章 基于聚类和压缩矩阵的a p r i o r i 算法的研究与应用 关联规则是描述数据库中数据项之间潜在关系的规则。关联规则挖掘的一般对象 是事务数据库，起初主要应用于零售业，比如超级市场的销售管理。关联规则就是通 过辨别这些交易资料，来分析顾客的购买模式。根据关联规则提供的信息可以用做商 品销售目录设计、商品摆放、针对性的市场营销策略等。虽然关联规则是伴随着零售 业的飞速发展而产生的一种需求，但它的应用绝不仅仅局限在零售业上，还可应用到 银行业、保险业、安全交易、计算机硬件和软件、医药、交通、电信、教育等多个领 域，所以展开对关联规则的研究具有重大意义。 1 2 选题的依据和意义 1 9 9 3 年r a g r a w a l 等人首先提出了挖掘顾客交易数据库中项集间的关联规则问 题【3 】，并于1 9 9 4 年提出了挖掘关联规则的经典算法a p r i o r i 算法【4 】。后来有不少学者 对关联规则的挖掘算法进行优化，如采用基于散列、事务划分、模式矩阵存储【5 】等的 优化方法，以提高算法挖掘规则的效率。有的学者为了避免频繁项集产生方法的一些 缺陷，提出了独立于a p r i o r i 算法的挖掘关联规则的新方法，如j i a w e ih a r t 等人提出 的不产生候选频繁项集的f p g r o w t h 算法【6 】。挖掘关联规则的挑战性在于数据量巨 大，算法的效率是关键，因此有必要研究出占用内存小、i o 操作少、执行速度快的 高效算法。 随着我国高校的信息化迅速发展，几乎全国的高校都已经建立起校园网。如何利 用信息技术更有效地为校园管理服务，提高校园信息化程度，已经成为衡量教学管理 质量的重要标志之一。把数据挖掘技术引入到教务管理领域中，不仅可以提高教学管 理的科学性，而且能够增强数字化教育的实效性。通过数据挖掘技术从大量数据中发 现有用的知识，目标是从教务系统数据中发现隐含的、有意义的知识，预测教学活动 的未来趋势及行为，帮助学校做出前瞻性的决策，增强学校的竞争力和影响力。 1 3 论文所作工作及创新点 本文对数据仓库和数据挖掘基本理论进行了系统的归纳和总结，在此基础上，重 点研究了关联规则的经典算法a p r i o r i 算法。论文的主要内容包括： 1 、聚类分析和关联规则的基础理论。 2 基于聚类和压 2 、在 3 、使 4 、基 本文的主要创新点如下： 1 、通过对关联规则算法的学习和研究，设计了一种基于聚类和压缩矩阵 ( c l u s t e r & c o m p r e s s i o nm a t r i x ) 的a p d o r i 改进算法叫c ma p r i o r i 算法，通过实 验证明该算法与a p r i o d 算法相比其效率有了较大的提高。 2 、将c c ma p d o r i 算法应用到高校的教务管理系统中，对高校选修课模块运用 数据挖掘技术，根据学生成绩和历史选课记录预测学生选修的课程及人数，为学院的 选修课开设提供决策支持。 1 4 本文组织结构 本文共6 章： 第一章绪论。介绍了课题的背景，课题的意义和本文组织结构。 第二章数据仓库和数据挖掘基础理论。介绍了数据仓库和数据挖掘的基本概念、 方法和技术。 第三章聚类和关联规则基础理论。介绍数据挖掘中聚类和关联规则的相关概念， 思想和经典算法。 第四章基于聚类和压缩矩阵的a p r i o r i 改进算法。针对a 埘。一算法的缺点，设 计了一种基于聚类和压缩矩阵的a p r i o d 改进算法c ma 研o r i 算法，并通过实 验将该算法与a p r i o r i 算法进行了时间效率对比。 第五章系统的实现与结果分析。将c c ma p f i o f i 算法应用到学校的教务管理系 统中，得到挖掘结果，对挖掘结果进行了分析和说明。 第六章本文的总结与展望。 第二章 基于聚类和压缩矩阵的a p d o d 算法的研究与应用 第二章数据仓库和数据挖掘基础理论 随着信息技术的迅速发展，数据库规模的不断扩大，从而产生了大量的数据。激 增的数据背后隐藏着许多重要的信息，人们希望能够对数据进行更合理的分析，以便 更好地利用这些数据。但大量的数据往往使人们无法辨别隐藏在其中的、能为决策者 提供决策支持的信息，而传统的查询、报表工具无法满足挖掘这些信息的需求。因此， 需要一种新的数据分析技术来处理数据，并从中抽取有价值的潜在知识，数据挖掘 ( d a t am i n i n g ) 技术由此应运而生【4 0 1 。数据挖掘技术也正是伴随着数据仓库( d a t a w a r e h o u s e ) 技术的发展而逐步完善起来的。 2 1 数据仓库理论基础 数据仓库思想形成于2 0 世纪8 0 年代中后期，数据仓库专家可以访问数据仓库， 而且这些专家可以创建检索、汇总和格式化信息所需的复杂查询，供分析人员和高级 决策者使用。但随着社会的发展，越来越多的领域需要应用数据仓库。它与人们所熟 悉的数据库的区别在于：数据库是获取数据，而数据仓库则是分析数据，使研究者可 从数据中获取潜在的知识。 2 1 1 数据仓库基本概念 目前，数据仓库一词尚没有一个统一的定义，著名的数据仓库专家w h i n m o n 对数据仓库给予如下描述：数据仓库( d a t aw a r e h o u s e ) 是一个面向主题的( s u b j e c t o r i e n t e d ) 、集成的( i n t e g r a t e ) 、相对稳定的( n o n v o l a t i l e ) 、反映历史变化( t i m e v a r i a n t ) 的数据集合，用于支持管理决策【7 1 。对于数据仓库的概念我们可以从两个层 次予以理解：首先，数据仓库用于支持决策，面向分析型数据处理，它不同于企业现 有的操作型数据库；其次，数据仓库是对多个异构的数据源有效集成，集成后按照主 题进行了重组，并包含历史数据，而且存放在数据仓库中的数据一般不再修改。 根据数据仓库概念的含义，数据仓库有以下四个特点1 7 】： l 、面向主题 4 基于聚类和压缩矩阵的a p r i o r i 算法的研究与应用 第二章 数据仓库中的数据是按照一定的主题进行组织的。主题是一个抽象的概念，是指 用户使用数据仓库进行决策时所关心的重点方面，一个主题通常与多个操作型信息系 统相关。 2 、集成的 、 数据仓库中的数据是在对原有分散的数据库数据抽取、清理的基础上经过系统加 工、汇总和整理得到的，消除了源数据中的不一致性，以保证数据仓库内的信息是关 于整个企业的一致的全局信息。 3 、相对稳定的 数据仓库的数据主要供企业决策分析使用，所涉及的数据操作主要是数据查询， 一旦某个数据进入数据仓库以后，一般情况下将被长期保留，也就是数据仓库中一般 有大量的查询操作，但修改和删除操作很少，通常只需要定期的加载、刷新。 4 、反映历史变化 数据仓库中的数据通常包含历史信息，系统记录了企业从过去某一时间点( 如开 始应用数据仓库的时间点) 到目前的各个阶段的信息，通过这些信息，可以对企业的 发展历程和未来趋势做出定量分析和预测。 数据仓库的根本任务是把信息及时交给需要这些信息的使用者，加以整理归纳， 并结合一些分析工具，如o l a p 和数据挖掘工具，在数据仓库中进行统计、分析和挖 掘，以获得用于决策的信息或相关规律并及时提供给相应的管理决策人员，使他们做 出改善其业务经营的决策。 2 1 2 数据仓库系统结构 数据仓库系统由数据源、数据存储与管理、o l a p 服务器和前端工具四部分组成， 其结构形式如图2 1 所示。 1 、数据源 数据仓库的数据来自多个数据源，包括企业内部数据、市场调查与分析及各种文 档之类的外部数据。 2 、数据的存储与管理 在确定数据仓库信息需求后，首先进行数据建模，然后确定从源数据到数据仓库 第二章 基于聚类和压缩矩阵的a p r i o r i 算法的研究与应用 的数据抽取、清洗和转换过程，最后确定数据仓库的物理存储结构。元数据是数据仓 库的核心，它用于存储数据模型和定义数据结构、转换规则、仓库结构、控制信息等。 3 、分析工具 用于完成实际决策问题所需要的各种查询检索工具、多维数据的o l a p 分析工 具、数据挖掘d m 工具等，以实现决策支持系统的各种要求。 4 、前端工具 前端工具是为决策者或分析者提供从数据仓库中提取决策信息的工具。主要包括 各桌面产品、定制的分析工具和客户程序。通过前端的工具分析、查询数据仓库中的 数据，挖掘其中的信息，并通过报表等各种形式展示。 r - 一 f = = = 1 【j 厂 i 数据集 数据源数据的存储与管理o l a p 服务器前端工具 2 1 3 数据仓库组成 图2 1 数据仓库系统结构图 数据仓库由数据仓库数据库，数据抽取工具，元数据，访问工具，数据集市，数 据仓库管理和信息发布系统组成。 1 、数据仓库数据库 数据仓库数据库是整个数据仓库环境的核心，是数据存放的地方并提供对数据检 索的支持。相对于操作型数据库来说，其突出的特点是对海量数据的支持和快速的检 索技术。 2 、数据抽取工具 数据抽取工具把数据从各种各样的存储方式中取出来，进行必要的转化、整理， 再存放到数据仓库内。对各种不同数据存储方式的访问能力是数据抽取工具的关键， 6 圆圈圈回 答。 基于聚类和压缩矩阵的a p r i o r i 算法的研究与应用 第二章 应能生成c o b o l 程序、m v s 作业控制语言( j c l ) 、u n i x 脚本和s q l 语句等，以 访问不同的数据。数据转换包括：删除对决策应用没有意义的数据段；转换到统一的 数据名称和定义；计算统计和衍生数据；给缺值数据赋给缺省值；把不同的数据定义 方式统一。 3 、元数据 元数据是描述数据仓库内数据的结构和建立方法的数据。可将其按用途的不同分 为两类：技术元数据和商业元数据。 元数据为访问数据仓库提供了一个信息目录( i n f o r m a t i o nd i r e c t o r y ) ，这个目录全 面描述了数据仓库中都有什么数据、这些数据怎么得到的和怎么访问这些数据。元数 据是数据仓库运行和维护的中心，数据仓库服务器利用它来存贮和更新数据，用户通 过它来了访问数据。 4 、访问工具 访问工具为用户访问数据仓库提供手段。有数据查询和报表工具，应用开发工具， 管理信息系统( e i s ) 工具，在线分析( o l a p ) 工具，数据挖掘工具等。 5 、数据集市 数据集市是为了特定的应用目的或应用范围，而从数据仓库中独立出来的一部分 数据，也可称为部门数据或主题数据。在数据仓库的实施过程中往往可以从一个部门 的数据集市着手，以后再用几个数据集市组成一个完整的数据仓库。需要注意的就是 在实施不同的数据集市时，同一含义的字段定义一定要相容，这样在以后实施数据仓 库时才不会造成大麻烦。 6 、数据仓库管理 安全和特权管理，跟踪数据的更新，数据质量检查，管理和更新元数据，审计和 报告数据仓库的使用和状态，删除数据，复制、分割和分发数据，备份和恢复，存储 管理。 7 、信息发布系统 把数据仓库中的数据或其他相关的数据发送给不同的地点或用户。基于w e b 的 信息发布系统是解决多用户访问的最有效方法。 7 第二章 基于聚类和压缩矩阵的a p f i o d 算法的研究与应用 2 1 4 数据仓库与数据库的关系 数据仓库的出现，并不是要取代数据库。目前，大部分数据仓库还是用数据库管 理系统来管理的。可以说，数据库、数据仓库相辅相成、各有千秋。数据库是面向事 务的设计，数据仓库是面向主题设计的。数据库一般存储在线交易数据，数据仓库存 储的一般是历史数据。 数据库设计时尽量避免冗余，一般采用符合范式的规则来没计。数据仓库在设计 时有意引入冗余，采用反范式的方式来设计。数据库是为捕获数据而设计，数据仓库 是为分析数据而设计，它的两个基本的元素是维表和事实表。数据仓库与数据库的区 别主要表现在以下几个方面【8 】： 1 、数据来源 数据库的数据主要来自于企业外部：数据仓库的数据主要来自于目前正在运作的 业务系统，还来源于长期的信息处理过程中积累下来的历史数据、企业内部的办公系 统的数据、因特网的数据、外部数据及来自于数据源的元数据等。 2 、数据目标 数据库中数据是面向应用的，为业务操作人员的日常业务处理提供支持；数据仓 库中的数据是面向决策分析的，为中高层管理人员提供决策支持。 3 、数据内容 数据库中的数据是动态变化的。只要有业务操作发生，数据就会被更新。即数据 库中始终存储当前数据，以支持日常的业务处理；而数据仓库中的数据相对来说是静 态的。不进行更新，只进行添加、刷新。把业务处理系统中变化的数据添加到数据仓 库中来。所以数据仓库中存储了大量的历史数据，以支持决策分析。 4 、数据结构 数据库设计是基于某个范式的，经过规范化的过程。因此，数据库中的数据是高 度结构化的，适合操作计算。数据仓库中的数据为了提高性能，能更好地支持决策分 析，需要进行反规范化处理，因此，数据结构比较简单。 5 、数据的访问与使用 数据库中的数据使用频率较高，完成事务处理需要访问的数据量比较小。数据仓 库中的数据使用频率较相对来说较低，完成决策分析可能要访问大量的数据。 8 基于聚类和压缩矩阵的a p r i o f i 算法的研究与应用 6 、响应时间 数据库对响应时间的要求非常严格，通常以秒或毫秒为单位。数据仓库对 间要求较宽松，有的决策分析的时间可能以小时为单位。 2 2 数据挖掘技术 数据库技术从二十世纪8 0 年代开始，已经得到广泛的普及和应用。数据仓库作 为一种新型的数据存储和处理手段，被数据库厂商普遍接受，并且把相关辅助建模和 管理工具快速推向市场，成为多数据源集成的一种有效的技术支撑环境。因此，人们 已经具备利用多种方式存储海量数据的能力。计算机性能的提高和先进的体系结构的 发展使数据挖掘技术的研究和应用成为可能【4 1 1 。概率论和数理统计这一学科可以为我 们从数据归纳知识，为数据挖掘技术提供理论基础。于是数据挖掘技术在继承已有的 人工智能相关领域的研究成果的基础上，摆脱了以前象牙塔式研究模式，真正开始客 观地从数据集中发现蕴藏的知识。 2 2 1 数据挖掘的定义和过程 数据挖掘，简单的讲就是从大量的数据中挖掘或抽取出知识。数据挖掘没有一个 统一的定义，比较公认的定义是：数据挖掘就是从大量的、不完全的、有噪声的、模 糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但是又潜在有用的信 息和知识的过程【9 】。提取的知识表示为概念、规则、规律、模式等形式。 数据挖掘通常包含多个相互联系的步骤，如定义和分析主题、数据预处理、选取 算法、提取规则、评价和解释结果、将模式构成知识，最后是应用。数据挖掘的基本 过程通常包括：( 1 ) 数据选择( 2 ) 数据清理( 3 ) 数据集成( 4 ) 数据变换( 5 ) 数据挖掘( 6 ) 模式评估 ( 7 ) 知识表示。其中( 1 ) ( 2 ) ( 3 ) ( 4 ) 四个过程被称为数据预处理。它占了数据挖掘过程总工作 量的6 0 左右【l0 1 ，数据预处理将放在后面详细介绍。数据挖掘的过程如图2 2 所示， 具体过程如下： 1 、数据选择 数据选择有时也称为数据取样或数据简化，数据选择是在对发现任务和数据本身 内容理解的基础上，寻找依赖于发现目标的表达数据的有用特性，以缩减数据规模， 9 对象识别问 5 、数据挖掘 使用数据挖掘方法对数据进行分析，挖掘用户需要的规则、趋势、分类、模式等。 6 、模式评估 对发现的规则、趋势、分类、模式等进行评估，从而保证发现模式的正确性。 7 、知识表示 将挖掘结果以可视化的形式展现在用户面前，向用户提供挖掘的知识。 数据i 选择i 目标i 清洗i 预处理l 转换l 转换i 挖掘i 模式 i 解释i 知识 卜一i 数据卜|数据卜- l 数据卜_ 叫卜i 2 2 2 数据挖掘特点 图2 2 数据挖掘过程示意图 数据挖掘技术具有以下特点，这些特点与数据挖掘要处理的数据和目的是密切相 关的： 1 、处理的数据规模十分庞大，达到g b 、t b 数量级，甚至更大。 1 0 基于聚类和压缩矩阵的a p f i o f i 算法的研究与应用 第二章 2 、查询一般是决策制定者( 用户) 提出的即时随机查询，往往不能形成精确的 查询要求，需要靠系统本身寻找其可能感兴趣的东西。 3 、在一些应用( 如商业投资等) 中，由于数据变化迅速，因此要求数据挖掘能 快速做出相应反应以随时提供决策支持。 4 、数据挖掘中，规则的发现基于统计规律。因此，所发现的规则不必适用于所 有数据，而是当达到某一临界值时，即认为有效。因此，利用数据挖掘技术可能会发 现大量的规则。 5 、数据挖掘所发现的规则是动态的，它只反映了当前状态的数据库具有的规则， 随着不断地向数据库中加入新数据，需要随时对其进行更新。 2 2 3 数据挖掘的主要研究内容 随着d m k d 研究逐步走向深入，数据挖掘和知识发现的研究已经形成了三根强 大的技术支柱：数据库、人工智能和数理统计1 1 1 】。目前d m k d 的主要研究内容包括 基础理论、发现算法、数据仓库、可视化技术、定性定量互换模型、知识表示方法、 发现知识的维护和再利用、半结构化和非结构化数据中的知识发现以及网上数据挖掘 等。数据挖掘发现的知识最常见的有以下五类： 1 、广义知识 广义知识指类别特征的概括性描述知识。根据数据的微观特性发现其表征的、带 有普遍性的、较高层次概念的、中观和宏观的知识，反映同类事物共同性质，是对数 据的概括、精炼和抽象。广义知识的发现方法和实现技术有很多，如数据立方体、面 向属性的归约等。 2 、关联知识 关联知识反映一个事件和其他事件之间依赖或关联的知识。如果两项或多项属性 之间存在关联，那么其中一项的属性值就可以依据其他属性值进行预测。最为著名的 关联规则发现方法是r a g r a w a l 提出的a p f i o f i 算法。关联规则的发现可分为两步。 第一步是迭代识别所有的频繁项目集，要求频繁项目集的支持度不低于用户设定的最 低值；第二步是从频繁项目集中构造置信度不低于用户设定的最低值的规则。识别或 发现所有频繁项目集是关联规则发现算法的核心，也是时间消耗最大的部分。 第二章 基于聚类和压缩矩阵的a p r i o r i 算法的研究与应用 3 、分类知识 分类知识反映同类事物共同性质的特征型知识和不同事物之间的差异型特征知 识。最为典型的分类方法是基于决策树的分类方法。它是从实例集中构造决策树，是 一种有指导的学习方法。该方法先根据训练子集形成决策树。如果该树不能对所有对 象给出正确的分类，那么选择一些例外加入到窗口中，重复该过程一直到形成正确的 决策集。最终结果是一棵树，其叶结点是类名，中间结点是带有分枝的属性，该分枝 对应属性的某一可能值。 数据分类还有统计、粗糙集( r o u g hs e t ) 等方法。线性回归和线性辨别分析是 典型的统计模型。为降低决策树生成代价，人们还提出了一种区间分类器。最近也有 人研究使用神经网络方法在数据库中进行分类和规则提取。 4 、预测型知识 它根据时间序列型数据，由历史的和当前的数据去推测未来的数据，也可以认为 是以时间为关键属性的关联知识。 目前，时间序列预测方法有经典的统计方法、神经网络和机器学习等。由于大量 的时间序列是非平稳的，其特征参数和数据分布随着时间的推移而发生变化。因此， 仅仅通过对某段历史数据的训练，建立单一的神经网络预测模型，还无法完成准确的 预测任务。为此，人们提出了基于统计学和基于精确性的再训练方法，当发现现存预 测模型不再适用于当前数据时，对模型重新训练，获得新的权重参数，建立新的模型。 也有许多系统借助并行算法的计算优势进行时间序列预测。 5 、偏差型知识 此外，数据挖掘还可以发现其他类型的知识，如偏差型知识( d e v i a t i o n ) ，它是对 差异和极端特例的描述，揭示事物偏离常规的异常现象，如标准类外的特例，数据聚 类外的离群值等。所有这些知识都可以在不同的概念层次上被发现，并随着概念层次 的提升，从微观到中观、到宏观，以满足不同用户不同层次决策的需要。 2 2 4 数据挖掘的常用方法 利用数据挖掘进行数据分析常用的方法主要有统计分析、关联分析、遗传算法、 粗集方法、决策树方法、神经网络方法、聚类方法、可视化技术等，它们分别从不同 1 2 基于聚类和压缩矩阵的a p f i o n 算法的研究 的角度对数据进行挖掘【2 】。 l 、统计分析方法 统计分析方法是利用统计、 他们之间的关系和规律。统计分 计分析方法有判别分析、因子分析、相关分析、回归分析等。 2 、关联分析 关联分析的目的是为了挖掘出隐藏在数据间的相互关系。关联分析就是给定一组 数据项和一个记录集合，通过分析记录集合，推导出数据项之间的相关性。关联分析 广泛用于购物篮或事物数据分析。关联分析算法主要有a p r i o r i 、a 研o f f t i d 、 f p g r o w t h 、m a q a 、i u a 、p i u a 算法等。 3 、遗传算法 遗传算法是一种优化技术，它利用生物进化的一系列概念进行问题的搜索，最终 达到优化的目的。在遗传算法的实施中，首先要对求解的问题进行编码( 染色体) ， 产生初始群体；然后计算个体的适应度，再进行染色体的复制、交换、突变等操作， 便产生新的个体。重复以上操作，直到求得最佳或较佳的个体。遗传算法往往具有计 算简单、优化效果好的特点，它在处理组合优化问题方面也有一定的优势，是一种应 用遗传学原理和自然选择机制来搜索最优解的方法。 4 、粗集方法 粗集方法是模拟人类的抽象逻辑思维，它以各种更接近人们对事物的描述方式的 定性、定量或者混合信息为输入，输入空间与输出空间的映射关系是通过决策表简化 得到的。它通过考察知识表达中不同属性的重要性，来确定哪些知识是冗余的，哪些 知识是有用的，进行简化知识表达的空间是基于不可分辨关系的思想和知识简化的方 法，从数据中推理逻辑规则作为知识系统的模型。它以对观察和测量所得数据进行分 类的能力为基础，从中发现、推理知识和分辨系统的某些特点、过程、对象等，特别 适合于数据简化、数据相关性的发现、发现数据的相似或差别、发现数据模式、数据 的近似分类等。 5 、决策树方法 决策树利用树型结构来表示决策集合，这些决策集合通过对数据集的分类产生规 则。首先，利用训练集生成一个测试函数，根据不同取值建立树的分支；在每个分支 13 第二章 基于聚类和压缩矩阵的a p r i o r i 算法的研究与应用 子集中建立下层节点和分支，这样便生成一棵决策树。然后对决策树进行剪枝处理， 最后把决策树转换为规则，利用这些规则可以对事例进行分类。 6 、神经网络方法 神经网络是模拟人类的形象直觉思维，在生物神经网络研究的基础上，根据生物 神经元和神经网络的特点，通过简化、归纳，提炼总结出来的一类并行处理网络。利 用非线性映射的思想和并行处理的方法，神经网络本身结构可以表达输出与输入的关 联知识。输入空间与输出空间的映射关系，是通过网络结构的不断学习、调整，最后 以网络的特定结构来表达的。神经网络主要用来进行分类、估计和预测等有向数据挖 掘，也可以用于聚集等无向数据挖掘，如自组织图。 7 、聚类方法 聚类算法是通过对变量的比较，把具有相似性特征的数据归为一类。因此，通过 聚类以后，数据集就转化为类集。在类集中，同一类数据具有相似的变量值，不同类 数据的变量值不具有相似性。聚类用于描述和发现数据库中以前未知的数据类别。其 中，样本数据中不包含类别变量，数据挖掘将具有共同趋势和模式的数据元组聚集为 一类，使类内各元组相似程度最高，类间差异最大。区分不同的类是属于数据挖掘过 程的一部分，这些类不是事先定义好的，而是通过聚类算法采用全自动方式获得。聚 类与分类不同，分类的类别是按应用的要求事先给定的，根据表示的事物特征的数据， 可以识别其类别。而聚类的类型不是事先指定的，而是分析数据的结果。 8 、可视化技术 可视化技术是通过直观的手段分析数据关系，采用图形方式将信息模式、数据的 关联或趋势呈现给用户。例如，把数据库中的多维数据变成多种图形，揭示数据的状 况、内在本质及规律。可视化技术主要包括数据、模型和过程3 个方面。其中，数据 可视化主要有直方图和散点图等；模型可视化的具体方法则与数据挖掘采用的算法有 关；过程可视化则采用数据流图来描述知识发现的过程。可视化技术拓宽了传统的图 表功能，可以交互的分析数据关系，使用户对数据的剖析更清楚，改善了数据挖掘的 速度和深度。 1 4 基于聚类和压缩矩阵的a p r i o r i 算法的研 2 2 5 数据挖掘当前热点 就目前来看，数据挖掘相 生物信息或基因的数据挖掘、文本的数据挖掘、分布式数据挖掘、可视化的数据挖掘 等。下面就这几个方面加以简单介绍。 1 、w 曲数据挖掘 w e b 上有海量的数据信息，怎样对这些数据进行复杂的应用成了现今数据库技术 的研究热点。相对于w e b 的数据而言，传统的数据库中的数据结构性很强，即其中 的数据为完全结构化的数据