（计算机应用技术专业论文）基于数据仓库的关联规则抽样算法研究.pdf

哈尔滨工程大学硕士学位论文 摘要 数据挖掘是从存放数据库、数据仓库或其它信息库中的大量数据中挖掘 有趣知识的过程。它包含关联规则挖掘、预测、分类、聚类、演化分析等多 种技术手段，其中关联规则挖掘是一种主要的也是用途最广的数据挖掘方法。 关联规则概念最早是由在i b m 工作的r a k e s ha g r a w a l 博士于1 9 9 3 年提出 的，用于刻画事务数据库中交易项目之间的关系，即频繁关系。本文对关联 规则挖掘的经典算法：a p r i o r i ，a p r i o r i t i d ，a p r i o r i h y b r i d 及f u p 2 算法进行 了研究。 抽样对于数据挖掘技术来说实用性很强，因为类似技术在大多数事件中 已经极大的满足了使用者的要求，作者想通过使用改进抽样技术来维护关联 规则，目前，已经针对数据库改变时维护关联规则做了一些研究。所有这些方 法不仅要对原始数据库中改变的部分扫描，同时也要扫描对未改变的部分， 工作量很大，要花费很多时间。而且，如果在数据库上更新的规则执行的很 频繁但原有规则调整改变不大时，就会浪费大量的精力。在本文中，作者将改 进一种抽样技术的算法来估算数据库更新前后关联规则的差别，这种差别可 以用来决定是否更新挖掘关联规则，如果估算的差别很小，那么在原始数据库 中的规则对于更新过的数据库就是一个很好的近似。因而，作者就不必花费精 力去更新规则，在真正更新规则之前作者可以累计部分更新，从而避免了过度 频繁的更新规则，实验结果证明此算法是有效的和高度精确的。 关键词：数据挖掘；关联规则；抽样；更新；置信区间 哈尔滨工程大学硕士学位论文 a b s t r a c t d a t am i n i n gi st h ep r o c e s so fd i s c o v e r i n gi n t e r e s t i n gk n o w l e d g ef r o ml a r g e v o l u m e so fd a t aw h i c ha r es t o r e de i t h e ri nd a t a b a s e s ，d a t aw a r e h o u s e s ，o ro t h e r i n f o r m a t i o nr e p o s i t o r i e s i ti n c l u d e sl o t so ft e c h n i c a lm e a s u r e ss u c ha sa s s o c i a t i o n r o l em i n i n g ，p r e d i c t i o n ，c l a s s i f i c a t i o n ，c l u s t e r i n ga n de v o l u t i o n a r ya n a l y s i s o f t h e s et e c h n i q u e s ，t h ea s s o c i a t i o nr u l em i n i n gt e c h n i q u ei st h em o s ti m p o r t a n ta n d a l s ot h em o s tw i d e l y u s e dm e t h o d t h ec o n c e p to fa s s o c i a t i o nr u l ew a sf i r s tp r o p o s e di n19 9 3b yd r r a k e s h a g r a w a lw h ow a sw o r k i n ga ti b m ，t od e s c r i b e t h er e l a t i o n s h i pb e t w e e n t r a n s a c t i o n a li t e m si nt r a n s a c t i o nd a t a b a s e s ，i e t h ef r e q u e n tr e l a t i o n s h i p t h e p a p e rf i r s ts t u d i e ss o m et y p i c a la s s o c i a t i o n r u l e m l n i n ga l g o r i t h m ss u c h a s a p r i o r i ，a p r i o r i t i d ，a p r i o r i h y b r i d ，a n df u p 2a l g o r i t h m s s a m p l i n gi sa na p p e a l i n gt e c h n i q u ef o rd a t am i n i n g ，b e c a u s ea p p r o x i m a t e s o l u t i o n si nm o s tc a s e sm a ya l r e a d yb eo fg r e a ts a t i s f a c t i o nt ot h en e e do ft h e u s e r s w ea t t e m p tt ou s es a m p l i n gt e c h n i q u e st oa d d r e s st h ep r o b l e mo f m a i n t a i n i n gi s c o v e r e da s s o c i a t i o nr u l e s s o m es t u d i e sh a v eb e e nd o n eo nt h e p r o b l e m o fm a i n t a i n i n gt h ed i s c o v e r e da s s o c i m i o nr u l e sw h e nu p d a t e sa r em a d et o t h ed a t a b a s e a l lp r o p o s e dm e t h o d sm u s te x a m i n en o to n l yt h ec h a n g e dp a r tb u t a l s ot h eu n c h a n g e dp a r ti nt h eo r i g i n a ld a t a b a s e ，w h i c hi sv e r yl a r g e ，a n dh e n c e t a k em u c ht i m e w o r s ey e t ，i f t h eu p d a t e so nt h er u l e sa l ep e r f o r m e df r e q u e n t l yo n t h ed a t a b a s eb u tt h eu n d e r l y i n gr u l es e th a sn o tc h a n g e dm u c h ，t h e nt h ee f f o r t c o u l db em o s t l yw a s t e d i nt h i sp a p e r ，w ed e v i s ea na l g o r i t h mw h i c he m p l o y s s a m p l i n gt e c h n i q u e st oe s t i m a t et h ed i f f e r e n c eb e t w e e nt h ea s s o c i a t i o nr u l e si na d a t a b a s eb e f o r ea n da f t e rt h ed a t a b a s ei su p d a t e d t h ee s t i m a t e dd i f f e r e n c ec a nb e u s e dt od e t e r m i n ew h e t h e rw es h o u l du p d a t et h em i n e da s s o c i a t i o nr u l e so rn o t i f t h ee s t i m a t e dd i f f e r e n c ei ss m a l l ，t h e nt h er u l e si nt h eo r i g i n a ld a t a b a s ei ss t i l la g o o da p p r o x i m a t i o nt ot h o s ei nt h eu p d a t e dd a t a b a s e h e n c e ，w ed on o th a v et o 哈尔滨工程大学硕士学位论文 s p e n dt h er e s o u r c e st ou p d a t et h er u l e s w ec a na c c u m u l a t em o r eu p d a t e sb e f o r e a c t u a l l yu p d a t i n gt h er u l e s ，t h e r e b ya v o i d i n gt h eo v e r h e a d so fu p d a t i n gt h er u l e s t o of r e q u e n t l y e x p e r i m e n t a lr e s u l t ss h o wt h a to u ra l g o r i t h mi sv e r ye f f i c i e n ta n d h i g h l ya c c u r a t e 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 nr u l e s ；s a m p l i n g ；u p d a t e ；c o n f i d e n c ei n t e r v a l 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ： 了虑 日期：矽磊年z ，月z 十日 哈尔滨工程大学硕士学位论文 1 1 数据挖掘的产生 第1 章绪论 数据挖掘是信息技术自然演化的结果。 1 1 1 2 0 世纪6 0 年代以来，数据库和信息技术已经系统地从原始的文件处理 演化到复杂的、功能强大的数据库系统，数据库技术正式进入了飞速发展的 崭新阶段。自7 0 年代以来，数据库系统的研究和开发己经从层次和网状数据 库系统发展到开发关系数据库系统、数据建模工具、索引和数据组织技术。 此外，用户通过查询语言、用户界面、优化的查询处理和事务管理，可以方 便、灵活地访问数据库。联机分析处理( o n l i n ea n a l y s t i c a lp r o c e s s i n g ，o l a p ) 将查询看作只读事务，对于关系技术的发展和广泛地将关系技术作为大量数 据的有效存储、检索和管理的主要工具做出了重要贡献。 在8 0 年代中期以后，数据库技术的特点是广泛接受关系技术，研究和开 发新的、功能强大的数据库系统。首先是各种类型的数据模型被广泛采用， 如扩充关系模型、面向对象模型、对象一关系模型和演绎模型。其次是数据 库存储内容的应用范围不断丰富，包括空间的、时间的、多媒体的、主动的 和科学的数据库、知识库、办公信息库在内的面向应用的数据库系统。涉及 分布性、多样性和数据共享问题被广泛研究。同时，异种数据库和基于i n t e r n e t 的全球信息系统也成为信息产业的主力军。 近年来，随着数据库技术的不断发展，存储在数据库中的信息量也在增 加。然而，传统的数据库仅仅提供一般的投影、选择、连接、并、交等简单 的查询操作，虽然己经带来了无与伦比的方便，但大量的数据显然仍未得到 充分的利用。快速增长的海量数据收集、存放在大型和大量数据库中，没有 强有力的工具，理解它们已经远远超出了人的能力。结果，收集在大型数据 库中的数据变成了难得再访问的数据档案。怎样从海量数据中挖掘出有价值 的信息逐渐成为一个重要的课题，由此带动了数据挖掘技术的产生和飞速发 展。 哈尔滨工程大学硕士学位论文 数据库技术进一步的研究试图从海量数据中发现有价值的信息，这就是 数据库中的知识发现( k d d ) 。k d d 采用数据库技术、统计学、机器学习、 可视化、神经网络等既有成果，从数据库、数据仓库或其他信息库中挖掘出 隐藏在数据中的有趣知识，这一步又被称为数据挖掘。 统计数据证明：数据挖掘能够给企业构建竞争优势并带来巨大的经济效益 1 2 。过去的几年里，在关系数据库中的知识发现取得了丰硕的成果，己经开发 了很多数据挖掘系统，如：i n t e l l i g e n tm i n e r ( q u e s t ) ，m i n e s e t ，d b r n i n e r , i m a c s ，s k i c a t , e x p l o r a 等己经在大型的数据库和数据仓库系统中使用的软 件口j 【4 i 。 数据挖掘是一个应市场需求而生的学科，又是一个多学科相互融合相互 渗透而产生的交叉学科。数据库技术、机器学习、统计技术、信息科学的发 展为数据挖掘的诞生奠定了理论基础，不可限量的市场需求为数据挖掘的发 展提供了广阔的空间p j 。 1 2 什么是数据挖掘 简单的说，数据挖掘就是从大量的数据中提取或者“挖掘”知识。许多人 把数据挖掘视为另一个常用术语数据库中的知识发现或k d d 的同义词。但 是，更科学的说法是将数据挖掘视为数据库中知识发现的一个基本步骤。在 这种情况下，数据库中的知识发现由以下七个步骤组成： 1 数据清理。消除噪声和不一致的数据。 数据清理试图填充空缺的值，识别孤立点、消除噪声，并纠正数据中的 不致，旨在提高下一步中建模所需的数据的质量。一些技术可用于数据清 理，如：数据规范化、处理空缺值、数据规约等。 2 数据集成。将数据由多种数据源合并成一致的数据存储，如数据仓库 或数据立方体。 3 数据选择。从数据库中检索与分析任务相关的数据。在海量数据上进 行复杂的数据分析和挖掘将需要很长时间，使得这种分析不现实或不可行。 数据选择用来得到数据集的子集表示，子集小的多，但仍接近于保持原数据 哈尔滨工程大学硕士学位论文 的完整性。在选择后的子集上挖掘将更有效，并产生几乎相同的分析结果， 它包括选择属性和记录。 4 数据变换。根据数据挖掘工具的要求对数据的格式进行规范化处理， 将数据转换成适合于挖掘的形式。 可能涉及以下的内容：平滑、聚集、数据概化、规范化、属性构造等。 属性构造是由给定的属性添加和构造新的属性，或根据需要产生新的记录。 例如：在一些情况下根据需要为没有购买产品的顾客创建记录。 5 数据挖掘。k d d 的基本步骤，使用智能方法提取数据模式。 6 模式评估。根据某种兴趣度度量，识别表示知识的真正有趣的模式。 7 知识表示。使用可视化和知识表示技术，向用户提供挖掘的知识。 数据挖掘步骤可以与用户或知识库交互，把有趣的模式提供给用户，或 作为新的知识存放在知识库中。尽管将数据挖掘视为数据库中知识发现过程 的一个基本步骤更为科学，然而，在产业晃、媒体和数据库研究界，“数据挖 掘”比“数据库中知识发现”更流行。因此，数据挖掘有了一个更为广义的概念： 数据挖掘是从存放在数据库、数据仓库或其它信息库中的大量数据中挖掘有 趣知识的过程。 基于这种观点，典型的数据挖掘系统具有以下主要成分： 1 数据库、数据仓库或其它信息库：这是一个或一组数据库、数据仓库、 电子表格或其它类型的信息库。可以在数据上进行数据清理和集成。 2 数据库或数据仓库服务器：根据用户的数据挖掘请求，数据库或数据 仓库服务器负责提取相关数据。 3 知识库：是用于指导搜索，或评估结果模式的兴趣度的领域知识。这 种知识可能包括概念分层，用户将属性或属性值组织成不同的抽象层。用户 确信方面的知识也可以包含在内，可以使用这种知识评估模式的兴趣度。 4 数据挖掘引擎：是数据挖掘系统的基本部分，由一组功能模块组成， 用于特征化、关联、分类、聚类分析以及演变和偏差分析。 5 模式评估模块：此成分通常使用兴趣度度量，并与数据挖掘模块交互， 以便将搜索聚集在有趣的模式上。它可能使用兴趣度阀值过滤发现的模式。 哈尔滨工程大学硕士学位论文 根据数据挖掘方法的实现方式，模式评估模块可以与数据挖掘模块集成在一 起。对于有效的数据挖掘，建议尽可能地将模式评估推进到挖掘过程之中， 以便将搜索限制到有兴趣的模式上。 6 图形用户界面：本模块在用户和数据挖掘系统之间通信，允许用户和 系统交互，指定数据挖掘查询或任务，提供信息，帮助搜索聚焦，根据数据 挖掘的中间结果进行搜索式挖掘。还可以浏览数据库和数据仓库模式或数据 结构，评估挖掘的模式，以不同的形式实现模式可视化。 1 3 数据挖掘的应用范围 原则上讲，数据挖掘可以在任何类型的存储信息上进行，包括关系数据 库、数据仓库、事务数据库、高级数据库系统、展开文件和w w w 。高级数 据库系统包括面向对象和对象一关系数据库：面向特殊应用的数据库包括空 间数据库、时间序列数据库、文本数据库和多媒体数据库等。 1 3 1 关系数据库 数据库系统，也称为数据库管理系统( d b m s ) ，由一组内部相关的数据 和组管理和存储数据的软件程序组成。软件程序涉及如下机制：数据库结 构定义，数据存储，并发、共享或分布的数据访问，在面对系统瘫痪或未授 权访问时确保数据的一致性和安全性。 关系数据库是表的集合，每个表都赋予一个唯一的名字。每个表包含一 组属性( 列或字段) ，并通常包含大量元组( 记录或行) 。每个元组代表一个 被唯一的关键字标识的对象，并被一组属性值描述。语义数据模型，如实体 一联系( e r ) 数据模型，将数据库作为一组实体和它们之间的联系进行建模。 通常为关系数据库构造e r 模型。 关系数据可以通过数据库查询访问，数据库查询使用查询语言如s q l ， 或借助于用户界面书写。一个给定的查询被转化成一系列关系操作，如连接、 选择和投影，并被优化，以便有效地处理j 。 当数据挖掘应用于关系数据库时， 如，数据挖掘系统可以分析顾客数据， 4 可以进一步搜索趋势或数据模式。例 根据顾客的收入、年龄和以前的信用 哈尔滨工程大学硕士学位论文 信息预测新顾客的信用风险。数据挖掘也可以检测偏差，如与以前的月份相 比，哪种商品的销售出乎意料。这种偏差可以进行进一步的考察，以帮助制 定决策。 在数据挖掘应用的所有数据源中，关系数据库是数据挖掘最流行的、最 丰富的数据源，因此也是数据挖掘研究的主要数据形式。 1 3 2 数据仓库 简单的说，数据仓库是一个数据库，它与组织机构的操作数据库分别维 护，是一种语义上一致的数据存储。允许将各种应用系统集成在一起，为统 一的历史数据分析提供坚实的平台，对信息处理提供支持。按照w h i n m o n 的说法，“数据仓库是一个面向主题的、集成的、时变的、非易失的数据集合， 支持管理部门的决策过程”。与其他的数据存储系统( 如关系数据库系统、事 务处理系统和文件系统) 相比，数据仓库具有以下四个关键特征1 7 1 ： 1 面向主题的：数据仓库围绕一些主题，如顾客、供应商、产品和销售 组织。数据仓库关注决策者的数据建模与分析，而不是集中于组织机构的日 常操作和事务处理。因此数据仓库排除对于决策无用的数据，提供特定主题 的简明视图。 2 集成的：通常，数据仓库是将多个数据源，如关系数据库、一般文件 和联机事务处理记录集成在一起。 3 时变的：数据存储从历史的角度提供信息，数据仓库中的关键结构， 隐式或显式地包含时间因素。 4 非易失的：数据仓库总是物理地分离存放数据，这些数据源于操作环 境下的应用数据。由于这种分离，数据仓库不需要事务处理、恢复和并发控 制机制。通常，需要两种数据访问：数据的初始化装入和数据访问。 简言之，数据仓库是一种语义上一致的数据存储，它充当决策支持模型 的物理实现，并存放企业战略决策所需信息。数据仓库也常常被看作一种体 系结构，通过将异种数据源中的数据集成在一起而构造，支持结构化和专门 的查询、分析报告和决策制订。 通过提供多维数据视图和汇总数据的预计算，数据仓库非常适合联机分 e 哈尔滨工程大学硕士学位论文 析处理( o l a p ) 。o l a p 操作使用数据的领域背景知识，允许在不同的抽象 层提供数据，这些操作适合不同的用户。o l a p 操作的例子包括下钻、上卷 等，允许用户在不同的汇总级别观察数据，例如，可以对季度汇总的销售数 据下钻，观察按月汇总的数据。类似的，可以对按城市汇总的销售数据上卷， 观察按国家汇总的数据。 尽管数据仓库工具对予支持数据分析是有帮助的，但是仍需要更多的数 据挖掘工具，以便进行更深入的自动分析。 1 3 3 事务数据库 一般来说，事务数据库是由一个文件组成，其中每个记录代表一个事务。 通常，一个事务包含一个唯一的事务标识号( t r a n s a c t i o n i d ) ，和一个组成事 务的项的列表。假如想挖掘出哪些商品适合一起销售，“购物簸数据分析”使 得能够将商品捆绑成组，作为一种扩大销售的策略。例如，给定打印机与计 算机经常一起销售的知识，可以向购买选定计算机的顾客提供一种很贵的打 印机打折销售，希望销售更多较贵的打印机。常规的数据检索系统不能回答 上面这种查询，然而通过识别频繁地一起销售的商品，事务数据的数据挖掘 系统可以做到9 i 。 1 3 4 高级数据库系统和高级数据库应用 随着数据库技术的发展，各种高级数据库系统已经出现并仍在开发中， 以适应新的数据库应用需要。这些新的数据库应用包括： 1 面向对象的数据库 面向对象的数据库采用基于面向对象的程序设计范例。每个实体被看作 一个对象，涉及一个对象的数据和代码封装在一个单元中。每个对象关联： t 一个变量集，它描述数据。这对应于实体一联系和关系模型的属性。 一个消息集，对象可以使用它们与其它对象或与数据库系统的其它部分 通信。 一个方法集，其中的每个方法存放实现一个消息的代码。一旦收到消息， 方法就返回一个响应值。 6 哈尔滨工程大学硕士学位论文 共享公共特性集的对象可以归入一个对象类。每个对象都是其对象类的 实例。对象类可以组成类子类层次结构，使得每个类代表该类对象共有的特 性。 2 对象一关系数据库 对象关系数据库基于对象一关系数据模型构造。该模型通过提供处理复 杂对象的丰富数据类型和对象定位，扩充关系模型。此外，它还包含关系查 询语言的特殊构造，以便管理增加的数据模型。通过增加处理复杂数据模型、 类层次结构和如上所述的对象继承的能力，对象一关系模型扩充了基本关系 模型。 3 空间数据库 空间数据库包含涉及空间的信息。这种数据库包括地理( 地图) 数据库， v l s i 芯片设计数据库、医疗和卫星图像数据库等。空间数据挖掘是对空间数 据库中非显式存在的知识、空间关系或其它有意义的模式的提取。空间数据 挖掘需要综合数据挖掘和空间数据库技术，它可用于对空间数据的理解，空 间关系和空间与非空间数据间关系的发现，空间知识库的构造，空间数据库 的重组和空间查询的优化。 4 时间数据库和时间序列数据库 时间数据库和时间序列数据库都存放与时间有关的数据。时间数据库 ( t e m p o r a ld a t a b a s e ) 通常存放时间相关属性的数据。这些属性可能涉及若干 时间戳。每个都具有不同的含义。时间序列数据库( t i m e s e r i e sd a t a b a s e ) 存 放随时间变化的序列值，如收集的股票交易数据。数据挖掘技术可以用来发 现数据库中对象演变特征或对象变化趋势。 5 文本数据库 文本数据库是包含对象文字描述的数据库。通常，这种词描述不是简单 的关键词，而是长句或短文，如产品介绍、错误或故障报告、警告信息等。 文本数据库可能是高度非结构化的( 如w w w 上的网页) ，可能是半结构化 的( 如一些h t m l x m l 网页) ，也可能是良结构化的( 如图书馆数据库) 。 6 多媒体数据库 哈尔滨工程大学硕士学位论文 多媒体数据库存放图像、音频和视频数据。它们用于基于图像内容的检 索、声音传递、视频点播、w w w 和识别口语命令的基于语音的用户界面等 方面。多媒体数据库必须支持大对象，因为像视频这样的数据对象可能需要 兆字节级的存储，还需要特殊的存储和搜索技术。 1 4 数据挖掘的功能 数据挖掘功能用于指定数据挖掘任务中要找的模式类型。数据挖掘任务 一般可以分为两类：描述和预测。描述性挖掘任务刻画数据库中数据的一般 属性；预测性挖掘任务在当前数据上进行推断，以进行预测。 在某种情况下，用户不知道什么类型的数据模式是有趣的，因此可能想 并行地搜索多种不同的模式，这就要求数据挖掘系统要能够挖掘多种类型的 模式，以适应不同的用户需求或不同的应用。此外，数据挖掘系统应当能够 发现各种粒度( 即不同的抽象层) 的模式。数据挖掘系统应当允许用户给出 提示，指导或聚集有趣模式的搜索。数据挖掘功能以及它们可以发现的模式 类型介绍如下： 1 概念类描述：特征化和区分 数据可以与类或概念相关联。例如销售的商品类包括计算机和打印机， 顾客概念包括b i g s p e n d e r s 和b u d g e t s p e n d e r s 。用汇总的、简洁的、精确的方 式描述每个类和概念可能是有用的，这种类或概念的描述称为类概念描述。 这种描述可以通过下述方法得到： ( 1 ) 数据特征化：是目标类数据的一般特征或特征的汇总。 ( 2 ) 数据区分：将目标类对象的一般特性与一个或多个对比类对象的一 般特性比较。目标类和对比类由用户指定，而对应的数据通过数据库查询检 索。 ( 3 ) 数据特征化和比较。 2 关联分析 关联分析用于发现关联规则，这些规则展示属性一值频繁地在给定数据 集中一起出现的条件。关联分析广泛用于购物篮或事务数据分析，关联规则 哈尔滨工程大学硕士学位论文 将在以下的章节中详细讨论。 3 分类和预测 分类和预测是两种数据分析形式，可以用于提取描述重要数据类的模型或 预测未来的数据趋势。数据分类是一个两步的过程，第一步，建立一个模型， 描述给定的数据集，通过分析由属性描述的数据元组来构造模型，这部分的算 法有：判定树( d e c i s i o nt r e e ) 【1 0 1 c c a s t “1 、贝叶斯分类算法 ( b a y e s i a n c l a s s i c a t i o n ) 、后向传播算法( b a c k p r o p a g a t i o n ) ，k 一最临近分类 算法( k - n e a r e s t n e i g h b o rc l a s s i f i e r s ) 、基于案例的推理( c a s e b a s e d r e a s o n i n g ) 、遗传算法( g e n e t i ca l g o r i t h m s ) 1 2 1 粗糙集算法( r o u g hs e t a l g o r i t h m s ) 、模糊集算法( f u z z ys e t a p p r o a c h e s ) 、神经网络等1 1 ”。 分类是找出描述并区分数据类或概念类的模型或函数的过程，以便能够 使用模型预测类标记未知的对象类。导出模型是基于对训练数据集( 即其类 标记己知的数据对象) 的分析。预测是构造和使用模型评估无标号样本类， 或评估给定样本可能具有的属性值或值区间。分类是预测离散或标称值，而 预测用于预测连续或有序值。分类和预测的区别是：用预测法预测类标号( 或 离散值) 为分类，用预测法预测连续值( 例如使用回归方法) 为预测。 分类和预测具有广泛的应用，包括信誉证实、医疗诊断、性能预测和选 择购物等。 4 聚类分析 聚类是将数据对象分组成为多个类或簇，在问一簇中的对象之间具有较 高的相似度，而不同簇中的对象差别较大。与分类和预测不同，聚类分析数 据对象，而不考虑已知的类标记。 聚类分析已经广泛地应用于许多方面，包括模式识别，数据分析，图像 处理，以及市场研究等。 5 孤立点分析 数据库中可能包含一些数据对象，它们与数据的一般行为或模型不一致。 这些数据对象被称为是孤立点，大部分数据挖掘方法将孤立点视为噪声或异 常而丢弃。然而在一些应用中，孤立点事件可能比正常出现的事件更有趣， 哈尔滨工程大学硕士学位论文 孤立点数据分析称作孤立点挖掘。 孤立点分析可以发现信用卡欺骗。通过检测一个给定账号与正常的付费 相比，以付款数额特别大来发现信用卡欺骗性使用。孤立点值还可以通过购 物地点和类型，或购物频率来检测。 1 5 数据挖掘面临的主要问题 本文提出的数据挖掘的主要问题，考虑挖掘方法、用户交互、性能和存 储的各种数据类型问题。 一 1 5 1 挖掘方法与用户交互问题 这类问题涉及所挖掘的知识类型、在多粒度上挖掘知识的能力、领域知 识的使用、特定的挖掘和知识显示。 ( 1 ) 在数据库中挖掘不同类型的知识：由于不同的用户可能对不同类型 的知识感兴趣，数据挖掘系统应当覆盖范围很广的数据分析和知识发现任务， 包括数据特征化、区分、关联、分类、聚类、趋势和偏差分析以及类似性分 析。这些任务可能以不同的方式使用相同的数据库，并需要开发大量数据挖 掘技术。 ( 2 ) 多个抽象层的交互知识挖掘：由于很难准确地知道能够在数据库中 发现什么，因此需要数据挖掘的过程具有交互性。对于包含大量数据的数据 库，应当使用适当的抽样技术，进行交互式数据探查。交互式挖掘允许用户 聚焦搜索模式，根据返回的结果提出和精炼数据挖掘请求。用户通过交互地 在数据空间和知识空间下钻、上卷和转轴来挖掘知识，以不同的粒度和从不 同的角度观察数据和发现模式。 ( 3 ) 结合背景知识；可以使用背景知识或结合所研究领域的信息来指导 发现过程，并使得发现的模式以简洁的形式在不同的抽象层表示。数据库的 领域知识，如完整性约束和演绎规则，可以帮助聚焦和加快数据挖掘过程， 或评估发现的模式的兴趣度。 ( 4 ) 数据挖掘查询语言和特定的数据挖掘：关系查询语言( 如s q l ) 允许用户提出特定的数据检索查询。同样需要开发高级数据挖掘查询语言， 1 0 哈尔滨工程大学硕士学位论文 使得用户通过说明分析任务相关的数据集、领域知识、肼挖掘的数据类型、 被发现的模式必须满足的条件和约束，描述特定的数据挖掘任务。高级数据 挖掘查询语言应当与数据库或数据仓库查询语言集成，并且对于有效的、灵 活的数据挖掘是优化的。 ( 5 ) 数据挖掘结果的表示和显示：数据挖掘中发现的知识应当用高级语 言、可视化或其它的形式表示，使得知识易于理解，能够直接被用户使用， 这对于交互式的数据挖掘系统尤为重要。它要求系统采用有表达能力的知识 表示技术，如树、表、规则、图、图表、交叉表、矩阵或曲线等。 ( 6 ) 处理噪声和不完全数据：存放在数据库中的数据可能反映噪声、异 常情况或不完全的数据对象。这些对象可能搞乱分析过程，导致数据与所构 造的知识模型过分适应，使得所发现的模式的精确性很差。需要处理数据噪 声的数据处理方法和数据分析方法，以及发现和分析异常情况的孤立点挖掘 方法。 ( 7 ) 模式评估：数据挖掘系统可能发现数以千计的模式，对于给定的用 户，许多模式不是有趣的，它们表示公共知识缺乏新颖性。开发模式兴趣度 的评估技术，特别是关于给定用户类，基于用户的信赖或期望，评估模式价 值的主观度量是一个极具挑战性的问题。 1 5 2 性能问题 包括数据挖掘算法的有效性、可伸缩性和并行处理i l 。 ( 1 ) 数据挖掘算法的有效性和可伸缩性：数据挖掘一个重要的特点是去 产生假设，但它并不去验证假设【1 1 。为了有效地从数据库的大量数据中提取 信息，数据挖掘算法必须是有效的和可伸缩的。即对于大型数据库，数据挖 掘算法的运行时间必须是可预计的和可接受的i l ”。 ( 2 ) 并行、分布式和增量挖掘算法：数据库的大容量、数据广泛和一些 数据挖掘算法的计算复杂性促使开发和研究了并行、分布式和增量挖掘算法。 这些算法将数据划分成多个部分，这些算法可以并行处理，然后将各个处理 结果合并。数据挖掘过程的高花费导致了对增量数据挖掘算法的需要，增量 算法与数据库更新结合在一起，而不必随着数据库的更新重新挖掘全部数据， 1 1 哈尔滨工程大学硕士学位论文 算法渐增地进行知识更新，修正和加强先前业已发现的知识【l 。 1 5 3 关于数据库的多样性问题 ( 1 ) 关系的和复杂的数据类型的处理：数据库和数据仓库可能包含复杂 的数据对象、超文本和多媒体数据、空间数据、时间数据或事务数据。由于 数据类型的多样性和数据挖掘目标的不同，指望一个系统挖掘所有类型的数 据是不现实的。为挖掘特定类型的数据，应当构造特定的数据挖掘系统。大 多数数据挖掘系统缺少共享的底层挖掘语言，使得数据挖掘产品的标准化和 在不同的数据挖掘系统之间进行交互操作比较困难，制定数据挖掘的标准是 十分重要的1 15 1 。 ( 2 ) 由异种数据库和全球信息系统挖掘信息：局域网和广域网连接了多 种数据源，形成了庞大的、分布式的和异种的数据库。从具有不同数据语义 的结构化的、半结构化的和非结构化的不同数据源发现知识，对数据挖掘提 出了巨大挑战。数据挖掘可以发现多个异种数据库中的数据规律，这些规律 多半难以被简单的查询系统发现；数据挖掘可以改进异种数据库的信息交换 和互操作性。w e b 挖掘发现关于w e b 内容、w e b 使用和w e b 动态情况的有 趣知识，成为数据挖掘的一个非常具有挑战性的领域。 1 6 数据挖掘的研究现状和发展趋势 数据挖掘语言的设计，高效而有用的数据挖掘方法和系统的开发，交互 和集成的数据挖掘环境的建立，以及应用数据挖掘技术解决大型应用问题， 都是目前的研究和就开发热点，下面描述的是一些数据挖掘的应用趋势： ( 1 ) 应用的探索：早期的数据挖掘应用主要集中在帮助企业提升竞争能 力，随着数据挖掘的日益普及，数据挖掘也日益探索其它应用范围，如生物 医学、金融分析和电信等领域。随着电子商务和电子市场逐渐成为零售业的 主流因素，数据挖掘也在不断扩展其在商业领域的应用面i l7 1 1 8 。 ( 2 ) 可伸缩的数据挖掘方法：与传统的数据分析方法相比，数据挖掘必 须能够有效地处理大量数据，并尽可能是交互式的；由于数据量是在不断的 激增，因此针对单独的和集成的数据挖掘功能的可伸缩算法显得十一分重要。 l ， 哈尔滨工程大学硕士学位论文 一个重要的方向是基于约束的挖掘，它致力于在增加用户交互的同时如何改 进挖掘处理的总体效率。 ( 3 ) 数据挖掘与数据库系统、数据仓库和w e b 数据库系统的集成：数 据挖掘系统的理想体系是与数据库和数据仓库的紧耦合方式。事务处理、查 询处理、联机分析处理和联机分析挖掘应集成在一个统一框架中，这将保证 数据的可获得性，数据挖掘的可移植性、可伸缩性、高性能，以及形成对多 维数据分析和探查的集成信息处理环境。 ( 4 ) 数据挖掘语言的标准化：标准的数据挖掘语言或其它方面的标准化 工作将有助于数据挖掘的系统化开发，改进多个数据挖掘系统和功能间的相 互操作，促进数据挖掘系统在企业和社会中的教育和使用。 ( 5 ) 可视化数据挖掘：可视化数据挖掘是从大量数据中发现知识的有效 途径。系统研究和开发可视化挖掘技术将有助于推进数据挖掘成为数据分析 的基本工具。 ( 6 ) 复杂数据类型挖掘的新方法：复杂数据类型挖掘是数据挖掘中一项 重要的前沿研究课题，虽然在地理空间挖掘、多媒体挖掘、时序挖掘、序列 挖掘以及文本挖掘方面取得了一些进展，但它们与实际应用的需要仍存在很 大距离。对此需要进一步的研究，尤其是针对上述数据类型的现存数据分析 技术与数据挖掘方法集成起来的研究。 ( 7 ) w e b 挖掘：由于w e b 上存在大量信息，并且w e b 在当今社会扮演 越来越重要的角色，有关w e b 内容挖掘、w e b 日志挖掘和因特网上的数据挖 掘服务，将成为数据挖掘中一个最为重要的子领域。 ( 8 ) 数据挖掘中的隐私保护与信息安全：随着数据挖掘工具和电信与计 算机网络的日益普及，数据挖掘面对的一个重要问题是隐私保护和信息安全。 需要进一步开发有关方法，以便在适当的信息访问和挖掘过程中确保隐私保 护与信息安全。 1 7 本文的研究内容、目的及意义 数据挖掘是一个交叉学科领域，涉及多个学科，包括数据库系统、统计 哈尔滨工程大学硕士学位论文 学、机器学习、可视化和信息科学。依赖于所用的数据挖掘方法，以及可以 使用的其它学科的技术，如神经网络、模糊和粗糙集理论、知识表示、归纳 逻辑程序设计或高性能计算。依赖于所挖掘的数据类型或给定的数据挖掘应 用，数据挖掘系统可能集成空间数据分析、信息检索、模式识别、图像分析、 信号处理、计算机图形学、w e b 技术、经济、商业、生物信息学或心理学领 域的技术。 在本文中，作者研究数据挖掘抽样算法的有用性。更新关联规则的试验 证实这一点。利用抽样技术，作者用频繁项集差分估计算法对于更新前后的 数据仓库关联规则的差异给出了一个近似的上边界( 算法使用抽样和统计的 方法给出了一个可以信赖的上边界) 。如果边界值低，那么关联规则改变的数 量小，所以，旧的关联规则可以作为新关联规则的一个很好的近似。如果边 界值高，那么就有必要给出使用更新算法来计算新的关联规则。试验表明， 频繁项集差分估计算法不仅是有很高的可靠性，而且也是可升级的。在维护 关联规则节省机器资源方面是非常有效的。作者已经讨论如何通过算法扩展 来处理交易删除事件，如何修改算法来使其执行更加有效。实验的结果让作 者确认此抽样算法在数据挖掘中是非常有效的。 哈尔滨工程大学硕士学位论文 第2 章数据挖掘中的关联规则算法研究 在事务数据库中挖掘关联规则是数据挖掘中一个非常重要的研究课题， 用来发现大量数据有趣的模式和趋势。许多业界人士对于从他们的数据库中 挖掘关联规则越来越感兴趣，从大量商务事务记录中发现有趣的关联关系， 可以帮助许多商务决策的制定，如分类设计、交叉购物和贱卖分析等【2 】。 关联规则一个典型例子是“购物蓝分析”，该过程通过发现顾客放入其购 物蓝中不同商品之间的联系，分析顾客的购买习惯，了解哪些商品频繁地被 顾客同时购买，抽取的关联模式可以帮助制定营销策略。给定一个项集 ，= i ii 2 ，i m ，d 是一组事物数据的集合，每一个事务表示为 t d ，其中t i d 为事务标识号，t i d 为全局唯一，项目 4 i t e m s e t ( i = 1 2 m ) 。关联规则形如x jy 的蕴含式， 即 4 1 a 2 4 j 且 最 b 的规则，其中4 ( ， 1 2 崩 ) ， b ，( _ ， 1 ，2 ，h ) 是属性一值对，并且4 n b = a 。关联规则互j y 解释为：“满 足x 中条件的数据库元组多半也满足y 中的条件”。 有两个关键参数用来发现关联规则，他们是被如下定义的： ( 1 ) 支持度s u p p o r t ( s ) 给定一个任务相关的数据元组集合或事务数据库的集合，关联规则 工jy 的支持度s u p p o r t ( s ) 是数据库d 中事务包含x u y ( 即x 和y 二者) 的百分比，他是概率尸( x u y ) 。例如：xjy 的支持度s = 5 意味着全部事 务的5 同时包含x 和y 。 支持度的定义为s u p p o r t ( u y ) = p ( u 】，1 ( 2 ) 置信度c o n f i d e n c e ( c 】 每个发现模式都应当有一个表示其有效性或“值得信赖性”的确定性度 量。规则等y 在事务数据库d 中具有置信度c ，如果d 中包含x 的事务同 时也包含y 的百分比是c ，这是条件概率p ( y x ) 。如果x 等y 的置信度 c = 2 0 意味着包含x 的2 0o 0 的事务同时包含y 。 置信度的定义为：c o n f i d e n c e ( jy ) = p ( y 工) o 哈尔滨工程大学硕士学位论文 同时满足最小支持度( m i n _ s u p ) 和最小置信度( m i r lc o n f ) 的规则称作 强规则，或称为有趣的。 关联规则的挖掘是一个两步的过程： ( 1 ) 找出所有频繁项集 根据定义，这些相集出现的频繁性要大于或等于预定义的最小支持计数。 ( 2 ) 由频繁项集产生强关联规则 根据定义，这些规则必须满足最小支持数和最小置信度。只要求频繁项 集和他们出现的频繁性，这一步比较容易解决。 2 1a p r i o r i 算法 a p d o n 算法是一种最有影响的挖掘关联规则的算法1 1 9 】。算法的名字基于 这样的事实：算法使用频繁项集性质的先验知识。a p f i o f i 使用一种称作逐层 搜索的迭代方法。k 项集用于搜索( ( k + 1 ) 一项集。算法利用“在给定的事务数据 库d 中，任意频繁项集的子集都是频繁项集；任意弱项集的超集都是弱项集” 这一原理对事务数据库进行多遍扫描，第一次扫描得出频繁1 一项集厶，第k ( k 1 ) 次扫描前首先利用第k 1 次扫描的结果一来产生候选k 一项集q ，然后 在扫描过程中确定c 中元素的支持度，最后在每一遍扫描结束时计算出频繁 k 一项集三。，算法在当候选k 项集g 为空时结束。算法包括两步： 1 连接步：为找厶，通过t 矿与自己连接产生候选k 项集的集合。该 候选集的集合记为q 。=