（计算机软件与理论专业论文）以概念分层为背景知识的关联规则挖掘算法的分析.pdf

摘要 随着数据库技术的快速发展以及人们获取数据手段的多样化，我们所拥有 的数据急剧增加，但对这些数据进行分析理解的工具却很少。数据库系统所能 做到的只是对这些数据进行存取和简单的操作。大量数据背后隐藏着对决策十 分有用的信息，例如数据的整体特征、数据所表现出来的发展趋势等，但从海 量的数据中获取这些信息却不是一件容易的事。数据挖掘就是从大量的、不完 全的、有噪声的数据中提取隐含在其中的、人们事先不知道的、但又是潜在的 有用信息和知识的过程。 关联分析是数据挖掘的先行者，并且与其他学科的交叉内容较少。a p t i o r i 算法是关联分析的基础，量化关联规则挖掘所关心的问题是将连续数值的关联 分析转换为布尔值，多维关联规则分析与约束性的关联分析都是解决实用问题 的算法。数据挖掘中应用的方法包括传统的统计分析、分类、估计、预测和相 关分析、关联规则、聚集，也包括最新发展起来的一些诸如数据可视化、决策 树和神经网络等一些较新的方法。 本文首先简要介绍了数据挖掘的产生、功能、分类和可供挖掘的数据源， 然后详细分析了关联规则挖掘过程中最常用的频集发现算法a p r i o r i ，指出了 该算法的不足之处。在此基础上，提出了一种以概念层作为背景知识的多层关 联规则挖掘的方法，包括在同一概念层、混合概念层以及交叉概念层上进行关 联规则挖掘的方法；同时，文中还给出了从单个属性具有背景知识的情况向多 个属性都具有背景知识的情况进行扩展的方法，形成了多维关联规则挖掘的方 法，从而克服了原有算法的缺点，极大的提高了算法的适用范围和功能。最后 对未来的工作提出了展望。 关键词：关联规则，概念分层，频繁项集 a b s t r a c t b e c a u s et h e r a p i dd e v e l o p m e n t o ft h ed a t a b a s e t e c h n o l o g y a n dm e t h o d d i v e r s i f i c a t i o nt h a tp e o p l eg e td a t a ，t h ed a t aw ec a na c c e s sa r ei n c r e a s i n gr a p i d l y b u tt h e r ea r ef e wt o o l st h r o u g hw h i c hw ec a na n a l y z ea n du n d e r s t a n dt h e s ed a t a t h i n g st h a t d a t a b a s e s y s t e m c a nd oa r ea c c e s s i n gt h e s ed a t aa n ds o m e s i m p l e o p e r a t i o n s t h e r ea r eal o to fi n f o r m a t i o nw h i c ha r eu s e f u l f o rd e c i s i o n m a k i n g b e h i n dt h el a r g ea m o u n to fd a t a ，b u ti ti sn o ta ne a s yt h i n gt ot a k et h e s eu s e f u l i n f o r m a t i o nf r o mt h eg r e a tl o to fd a t a d a t am i n i n gi sap r o c e s st h r o u g hw h i c h p e o p l ec a nt a k et h eu s e f u li n f o r m a t i o na n dk n o w l e d g ef r o mv a s t ，i n c o m p l e t ea n d n o i s y d a t a a s s o c i a t i o na n a l y s e si st h ef o r t h g o e ro ft h ed a t am i n i n g ，a n dw h i c hh a sf e w c o n t e n ti n t e r c r o s s e dw i t ho t h e r s u b j e c t a p r i o r ia l g o r i t h m i st h eb a s eo ft h e a s s o c i a t i o na n a l y s i s ，t h ec e n t r a lp r o b l e mo ft h eq u a n t i t a t i v ea s s o c i a t i o nr u l em i n e a l g o r i t h m i st oc o n v e r tt h ec o n t i n u o u sv a l u ea t t r i b u t ea s s o c i a t i o na n a l y s i si n t o b o o l e a nv a l u ea t t r i b u t ea s s o c i a t i o n a n a l y s i s a l g o r i t h m s o fm u l t i d i m e n s i o n a s s o c i a t i o nr u l ea n da s s o c i a t i o nr u l eb a s e do nc o n s t r a i n ta r em e t h o d sf o rs o l v i n g p r a c t i c a lp r o b l e m s t h e m e t h o d so fd a t a m i n i n g i n c l u d es t a t i s t i c s a n a l y s i s ， c l a s s i f i c a t i o n ，e s t i m a t e ，p r e d i c t i o n ，r e l e v a n ta n a l y s i s ，a s s o c i a t i o nr u l e ，c l u s t e r i n ga n d s o m en e wm e t h o d ss u c ha sd e c i s i o nt r e e ，n e u r a ln e t w o r k ，d a t av i s u a l i z a t i o n i nt h i sp a p e r , t h eo r i g i n ，t h ef u n c t i o na n dt h ec l a s s i f i c a t i o no ft h ed a t am i n i n g a r ei n t r o d u c e di nb r i e f t h ea l g o r i t h mo f a p r i o r ii sa n a l y z e di nd e t a i l ，w h i c hi su s e d t of i n dt h ef r e q u e n ti t e m - s e t si nt h ed a t a - m i n ep r o c e s so fa s s o c i a t i o nr u l e s ；a n dt h e s h o r t a g eo ft h i sa l g o r i t h mi s a l s os h o w e d o nt h i sb a s e ，an e wa s s o c i a t i o nr u l e f i n d i n gm e t h o di sg i v e n ，w h i c ht a k e s t h ec o n c e p th i e r a r c h ya st h eb a c k g r o u n d k n o w l e d g ea n di n c l u d e ss a m eh i e r a r c h ya l g o r i t h m ，m i x e dh i e r a r c h ya l g o r i t h ma n d c r o s s e d h i e r a r c h y r u l e s m i n i n g m e t h o d t h em u l t i d i m e n s i o na s s o c i a t i o nr u l e m i n i n g m e t h o db e c o m e sf r o mo n ea t t r i b u t ee x p a n d i n gt om u l t i a t t r i b u t ea tt h es a m e t i m e s ot h es h o r t a g eo ft h ea p r i o r ia l g o r i t h mw a so v e r c a m e ，a n dt h ef i m c t i o n a l i t y o ft h e a l g o r i t h ma n ds c o p ew h i c hc a nb e u s e da r ep r o m i n e n te n h a n c e d f i n a l l y , s o m ee x p e c t a t i o n sf o rf u t u r ew o r ka r ep r e s e n t e d k e y w o r d s ：a s s o c i a t i o nr u l e s ，c o n c e p th i e r a r c h y ，f r e q u e n t i t e m s e t 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：l 日期：加仁年z 一月拥 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规 签名：导师签名 引言 近年来，数据挖掘引起了信息产业界的极大关注，其主要原因是存在 大量数据，可以广泛使用，并且迫切需要将这些数据转换成有用的信息和 知识。获取的信息和知识可以广泛用于各种应用，包括商务管理、生产控 制、市场分析、工程设计和科学探索等。随着大量数据不停地收集和存储， 许多企业的决策人员对于从他们的数据库中挖掘关联规则越来越感兴趣。 关联规则挖掘可以用来发现大量数据中项集之间有趣的关联或相关联系。 从大量商务事务记录中发现有趣的关联关系，可以帮助许多商务决策的制 定，如分类设计、交叉购物和贱卖分析。 一个概念分层定义了一个映射序列，将低层概念映射到更一般的高层 概念。比如地理维的概念分层。地理维的值可能包括成都、绵阳、杭州1 、 广州、深圳等。进而每个城市都可以映射到它所属的省。如：成都和绵阳 映射到四川省，杭州映射到浙江省，广州、深圳映射到广东省。而所有的 省可以映射到国家。这些映射形成地理维的概念分层，将低层概念( 如城 市) 映射到更一般的高层概念( 如省) 。 尽管市场上已有许多“数据挖掘系统”，但是并非所有的都能进行真正 的数据挖掘。不能处理大量数据的数据分析系统，最多称作机器学习系统、 统计数据分析工具或实验系统原型。一个系统只能够进行数据或信息检索， 包括在大型数据库找出聚集值或回答演绎查询，应当归类为数据库系统， 或信息检索系统，或演绎数据库系统。由复旦大学开发的a m i n e r 是近年来 市场上较为成功的基于关联规则挖掘的应用系统。 第一章数据挖掘概述 1 1 数据挖掘的产生 数据挖掘是信息技术自然演化的结果。演化的过程分为以下几个阶段： 数据收集和数据库创建、数据管理( 包括数据存储和检索，数据库事务处 理) 、以及数据分析与理解( 涉及数据仓库和数据挖掘) 。数据收集和数据 库创建机制的早期开发己成为稍后数据存储和检索、查询和事务处理有效 机制开发的必备基础。随着提供查询和事务处理的大量数据库系统广泛付 诸实践，数据分析和理解自然成为下一个目标。 数据库和信息技术自诞生以来，已经系统地从原始的文件处理演化到 复杂的、功能强大的数据库系统。数据库系统的研究和开发已经从层次和 网状数据库系统发展到开发关系数据库系统、数据建模工具、索引和数据 组织技术。此外，用户通过查询语言、用户界面、优化的查询处理和事务 管理，可以方便、灵活地访问数据。联机事务处理( 0l tp ) 将查询看作 只读事务，对于关系技术的发展和广泛地将关系技术作为大量数据的有效 存储、检索和管理的主要工具作出了重要贡献。 此后，数据库技术的特点是广泛接受关系技术，研究和开发新的、功 能强大的数据库系统。这些使用了先进的数据模型，如扩充关系模型、面 向对象模型、对象一关系模型和演绎模型。包括空间的、时间的、多媒体的、 主动的和科学的数据库、知识库、办公信息库在内的面向应用的数据库系 统百花齐放。涉及分布性、多样性和数据共享问题被广泛研究。异种数据 库和基于i n t e r n e t 的全球信息系统，如w w w 也已出现，并成为信息产业 的生力军。 现在，数据可以存放在不同类型的数据库中。最近出现的一种数据库 结构是数据仓库。这是一种多个异种数据源在单个站点以统一的模式组织 的存储，以支持管理决策。数据仓库技术包括数据清理、数据集成和联机 分析处理( 0lap ) 。0lap 是一种分析技术，具有汇总、合并和聚集 功能，以及从不同的角度观察信息的能力。尽管0lap 工具支持多维分 析和决策，对于深层次的分析，如数据分类、聚类和数据随时间变化的特 征，仍然需要其他分析工具。 数据的丰富带来了对强有力的数据分析工具的需求，大量的数据被描 述为“数据丰富，但信息贫乏”。快速增长的海量数据收集、存放在大型和 大量数据库中，没有强有力的工具，理解它们已经远远超出了人的能力。 结果，收集在大型数据库中的数据变成了“数据坟墓”一难得再访问的数 据档案。这样，重要的决定常常不是基于数据库中信息丰富的数据，而是 基于决策者的直觉，因为决策者缺乏从海量数据中提取有价值知识的工具。 此外，考虑当前的专家系统技术，通常，这种系统依赖用户或领域专家人 工地将知识输入知识库。不幸的是，这一过程常常有偏差和错误，并且耗 时、费用高。数据挖掘工具进行数据分析，可以发现重要的数据模式，对 商务决策、知识库、科学和医学研究作出了巨大贡献。数据和信息之间的 鸿沟要求系统地开发数据挖掘工具，将数据坟墓转换成知识“金块”。 1 2 数据挖掘的定义 简单地说，数据挖掘是从大量数据中提取或“挖掘”知识。与数据挖 掘密不可分的是另一个术语：数据库中的知识发现( k d d ) 。知识发现主要 包括以下步骤： 1 ) 数据清理( 消除噪声或不一致数据) 2 ) 数据集成( 多种数据源可以组合在一起) 3 ) 数据选择( 从数据库中检索与分析任务相关的数据) 4 ) 数据变换( 数据变换或统一成适合挖掘的形式，如通过汇总或聚 集操作) 5 ) 数据挖掘( 基本步骤，使用智能方法提取数据模式) 6 ) 模式评估( 根据某种兴趣度度量，识别表示知识的真正有趣的模 式 7 ) 知识表示( 使用可视化和知识表示技术，向用户提供挖掘的知识) 从狭义上理解，数据挖掘是知识发现的一个步骤。 而从广义上理解，数据挖掘是从存放在数据库、数据仓库或其他信息 库中的大量数据中挖掘有趣知识的过程。基于这种观点，典型的数据挖掘 系统具有以下主要成分，如下图： 数据库、数据仓库或其他信息库：这是一个或一组数据库、数据仓 库、电子表格或其他类型的信息库。可以在数据上进行数据清理和 集成。 数据库或数据仓库服务器：根据用户的数据挖掘请求，数据库或数 据仓库服务器负责提取相关数据。 知识库：这是领域知识，用于指导搜索，或评估结果模式的兴趣度。 这种知识可能包括概念分层，用于将属性或属性值组织成不同的抽 象层。用户确信方面的知识也可以包含在内。可以使用这种知识， 根据非期望性评估模式的兴趣度。领域知识的其他例子有兴趣度限 制或阈值和元数据( 例如，描述来自多个异种数据源的数据) 。 数据挖掘引擎：这是数据挖掘系统基本的部分，由一组功能模块组 成，用于特征化、关联、分类、聚类分析以及演变和偏差分析。 模式评估模块：通常，此成分使用兴趣度度量，并与数据挖掘模块 交互，以便将搜索聚焦在有趣的模式上。它可能使用兴趣度阈值过 滤发现的模式。模式评估模块也可以与挖掘模块集成在一起，这依 赖于所用的数据挖掘方法的实现。对于有效的数据挖掘，建议尽可 能深地将模式评估推进到挖掘过程之中，以便将搜索限制在有兴趣 的模式上。 图形用户界面：本模块在用户和数据挖掘系统之间通信，允许用户 与系统交互，指定数据挖掘查询或任务，提供信息、帮助搜索聚焦， 根据数据挖掘的中间结果进行探索式数据挖掘。此外，此成分还允 许用户浏览数据库和数据仓库模式或数据结构，评估挖掘的模式， 以不同的形式对模式可视化。 从数据仓库观点，数据挖掘可以看作联机分析处理( 0lap ) 的高 级阶段。然而，通过结合更高级的数据理解技术，数据挖掘比数据仓库的 汇总型分析处理走得更远。 尽管市场上已有许多“数据挖掘系统”，但是并非所有的都能进行真正 的数据挖掘。不能处理大量数据的数据分析系统，最多称作机器学习系统、 统计数据分析工具或实验系统原型。一个系统只能够进行数据或信息检索， 包括在大型数据库找出聚集值或回答演绎查询，应当归类为数据库系统， 或信息检索系统，或演绎数据库系统。 数据挖掘涉及多学科技术的集成，包括数据库技术、统计学、机器学 习、高性能计算、模式识别、神经网络、数据可视化、信息检索、图象与 信号处理和空间数据分析。一个算法是可伸缩的，如果给定内存和磁盘空 间等可利用的系统资源，其运行时间应当随数据库大小线性增加。通过数 据挖掘，可以从数据库提取有趣的知识、规律或高层信息，并可以从不同 角度观察或浏览。发现的知识可以用于决策、过程控制、信息管理、查询 处理，等等。因此，数据挖掘被信息产业界认为是数据库系统最重要的前 沿之一，是信息产业最有前途的交叉学科。 1 3 数据挖掘的数据源 原则上讲，数据挖掘可以在任何类型的信息存储上进行。这包括关系数 据库、数据仓库、事务数据库、高级数据库系统、展开文件和w 1 i rw 。高级 数据库系统包括面向对象和对象一关系数据库；面向特殊应用的数据库，如 空间数据库、时间序列数据库、文本数据库和多媒体数据库。挖掘的挑战 和技术可能因存储系统而异。 1 3 1 关系数据库 数据库系统，也称数据库管理系统( dbms ) ，由一组内部相关 的数据( 称作数据库) ，和一组管理和存取数据的软件程序组成。软件 程序涉及如下机制：数据库结构定义，数据存储，并发、共享或分布的 数据访问，在面对系统瘫痪或未授权的访问时确保数据的一致性和安全 性。 关系数据库是表的集合，每个表都赋予一个唯一的名字。每个表 包含组属性( 列或字段) ，并通常存放大量元组( 记录或行) 。关系中 的每个元组代表一个被唯一的关键字标识的对象，并被一组属性值描 述。语义数据模型，如实体一联系( er ) 数据模型，将数据库作为一 组实体和它们之间的联系进行建模。通常为关系数据库构造er 模型。 关系数据可以通过数据库查询访问。数据库查询使用如sql 这样 的关系查询语言，或借助于图形用户界面书写。在后- - t o 情形下，用户 可以使用菜单指定包含在查询中的属性和属性上的限制。一个给定的查 询被转换成一系列关系操作，如连接、选择和投影，并被优化，以便有 效地处理。查询可以检索数据的一个指定的子集。关系查询语言也可以 包含聚集函数，如s u m ，a v g ( 平均) ，c o u n t ，i n a x ( 最大) 和m i n ( 最小) 。 当数据挖掘用于关系数据库时，你可以进一步搜索趋势或数据模 式。例如，数据挖掘系统可以分析顾客数据，根据顾客的收入、年龄和 以前的信用信息预测新顾客的信用风险。数据挖掘系统也可以检测偏 差，如与以前的年份相比，哪种商品的销售出人预料。这种偏差可以进 一步考察( 例如，包装是否有变化，或价格是否大幅度提高) 。 关系数据库是数据挖掘最流行的、最丰富的数据源，因此它是我们 数据挖掘研究的主要数据形式。 1 3 2 数据仓库 数据仓库是面向主题的、集成的、非易失的、随时间变化的数据 集合，用来支持管理决策。 通常，数据仓库用多维数据库结构建模。其中，每一维对应于模 式中的一个或一组属性，每个单元存放某个聚集度量值，如c o u n t 或 s a l e s a m o u n t 。数据仓库的实际物理结构可以是关系数据存储或多维 数据立方体( d a t ac u b e ) 。它提供数据的多维视图，并允许预计算和 快速访问汇总的数据。 通过提供多维数据视图和汇总数据的预计算，数据仓库非常适合 联机分析处理( 0lap ) 。0lap 操作使用数据的领域背景知识， 允许在不同的抽象层提供数据。这些操作适合不同的用户。0lap 操作的例子包括下钻( d r i l 】一d o w n ) 和上卷( r o l 卜u p ) ，它们允许用 户在不同的汇总级别观察数据。 尽管数据仓库工具对于支持数据分析是有帮助的，但是仍需要更 多的数据挖掘工具，以便进行更深入的自动分析。 1 3 3 事务数据库 一般地说，事务数据库由一个文件组成，其中每个记录代表一个 事务。通常，一个事务包含一个唯一的事务标识号( trans id ) ， 和一个组成事务的项的列表( 如，在商店购买的商品) 。事务数据库 可能有一些与之相关联的附加表，包含关于销售的其他信息，如事务 的日期、顾客的id 号、销售者的id 号、销售分店，等等。 事务可以存放在表中，每个事务一个记录。从关系数据库的观点， 事务表是一个嵌套的关系，因为事务通常都包含i t e m 的集合，每个 i t e m 都有一个表来描述其属性。由于大部分关系数据库系统不支持嵌 套关系结构，事务数据库通常存放在一个展开文件中。 在事务数据库上除了进行普通的查询外，最可能的查询问题是如： “哪些商品适合一起销售? ”这样的查询需求。这种“购物篮数据分 析”使你能够将商品捆绑成组，作为一种扩大销售的策略。例如，给 定打印机与计算机经常一起销售的知识，你可以向购买选定计算机的 顾客提供对一种很贵的打印机打折销售，希望销售更多较贵的打印 机。常规的数据检索系统不能回答上面这种查询。然而，通过识别频 繁地一起销售的商品，事务数据的数据挖掘系统可以做到。 1 3 4 高级数据库系统和高级数据库应用 关系数据库系统广泛地用于商务应用。随着数据库技术的发展， 各种高级数据库系统已经出现并在开发中，以适应新的数据库应用需 要。 新的数据库应用包括处理空间数据( 如地图) 、工程设计数据( 如 建筑设计、系统部件、集成电路) 、超文本和多媒体数据( 包括文本、 影象、图象和声音数据) 、时间相关的数据( 如历史数据或股票交易 数据) 和www ( 通过int ernet 可以使巨大的、广泛分布的 信息存储) 。这些应用需要有效的数据结构和可伸缩的方法，处理复 杂的对象结构、变长记录、半结构化或无结构的数据以及文本和多媒 体数据，并具有复杂结构和动态变化的数据库模式。 为响应这些需求，开发了高级数据库系统和面向特殊应用的数据 库系统。这些包括面向对象和对象关系数据库系统、空间数据库系 统、时间和时间序列数据库系统、文本和多媒体数据库系统、异种和 遗产数据库系统、基于www 的全球信息系统。 虽然这样的数据库或信息存储需要复杂的机制，以便有效地存储、 检索和更新大量复杂的数据，它们也为数据挖掘提供了肥沃的土壤， 提出了挑战性的研究和实现问题。 面向对象的数据库：每个实体看作一个对象。涉及一个对象的数 据和代码封装在一个单元中。每个对象关联：一个变量集，它描 述数据。这对应于实体一联系和关系模型的属性；一个消息集， 对象可以使用它们与其他对象或与数据库系统的其他部分通信； 一个方法集，其中每个方法存放实现一个消息的代码。一旦收到 消息，方法就返回一个响应值。 共享公共特性集的对象可以归入一个对象类。每个对象都是其 对象类的实例。对象类可以组成类子类层次结构，使得每个类 代表该类对象共有的特性。 对象一关系数据库：基于对象一关系数据模型构造。该模型通过提 供处理复杂对象的丰富数据类型和对象定位，扩充关系模型。此 外，它还包含关系查询语言的特殊构造，以便管理增加的数据类 型。通过增加处理复杂数据类型、类层次结构和如上所述的对象 继承的能力，对象一关系模型扩充了基本关系模型。在面向对象和 对象一关系系统中的数据挖掘具有某些类似性。与关系数据挖掘相 比，需要开发新的技术，处理复杂对象结构、复杂数据类型、类 和子类层次结构、特性继承以及方法和过程。 空间数据库：包含涉及空间的信息。这种数据库包括地理( 地图) 数据库、 vlsi 芯片设计数据库、医疗和卫星图象数据库。空 间数据可能以光栅格式( r a s t e rf o r m a t ) 提供，由n 维位图或象素 图构成。地图也可以用向量格式提供，其中，路、桥、建筑物和 湖泊可以用诸如点、线、多边形和这些形状形成的分化和网络等 基本地理结构表示。数据挖掘可以发现描述座落在特定类型地点 的房屋特征。其他模式可能描述不同海拔高度山区的气候，或根 据城市离主要公路的距离描述都市贫困率的变化趋势。此外，可 以构造“空间数据立方体”，将数据组织到多维结构和层次中，0 l ap 操作( 如下钻和上卷) 可以在其上进行。 时间数据库和时间序列数据库：都存放与时间有关的数据。时间 数据库( 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 ) 存放随时间变化的值序列，如 收集的股票交易数据。数据挖掘技术可以用来发现数据库中对象 演变特征或对象变化趋势。这些信息对于决策和规划是有用的。 例如，银行数据的挖掘可能有助于根据顾客的流量安排银行出纳 员。可以挖掘股票交易数据，发现可能帮助你制订投资策略的趋 势。通常，这种分析需要定义时间的多粒度。 文本数据库和多媒体数据库：文本数据库是包含对象文字描述的 数据库。文本数据库可能是高度非结构化的( 如w ww 上的网页) 。 有些文本数据库可能是半结构化的( 如e m a i l 消息) ，而其他的 可能是良结构化的( 如图书馆数据库) 。通常，具有很好结构的文 本数据库可以使用关系数据库系统实现。多媒体数据库存放图象、 音频和视频数据。多媒体数据库必须支持大对象，因为像视频这 样的数据对象可能需要兆字节级的存储。还需要特殊的存储和搜 索技术。因为视频和音频数据需要以稳定的、预先确定的速率实 时检索，防止图象或声音间断和系统缓冲区溢出，因此这种数据 称为连续媒体数据( c o n t i n u o u s m e d i ad a t a ) 。对于多媒体数据库 挖掘，需要将存储和搜索技术与标准的数据挖掘方法集成在一起。 异种数据库和遗产数据库：异种数据库由一组互连的、自治的成 员数据库组成。这些成员相互通信，以便交换信息和回答查询。 一个成员数据库中的对象可能与其他成员数据库中的对象很不相 同，使得很难将它们的语义吸收进一个整体的异种数据库中。遗 产数据库是一组异种数据库，它将不同的数据系统组合在一起。 这些数据系统如关系或面向对象数据库、层次数据库、网络数据 库、电子表格、多媒体数据库或文件系统。遗产数据库中的异种 数据库可以通过内部计算机网或互联计算机网连接。 w w w ：www 和与之关联的分布式信息服务( 如美国在线，y a h o o ! ， a 1 t a v i s t a ，p r o d i g y ) 提供了丰富的、世界范围的联机信息服务； 这里，数据对象被链接在一起，便于交互访问。用户通过链接， 从一个对象到另一个，寻找有趣的信息。这种系统对数据挖掘提 供了大量机会和挑战。尽管网页看上去好看并且信息丰富，但它 们实际上是非结构化的并且缺乏预定义的模式、类型和格式。这 样，对于系统地进行信息检索和数据挖掘，计算机很难理解各种 网页的语义并把它们以有组织的形式结构化。提供基于关键字的 搜索服务，而不理解特定网页的上下文，只能给用户提供有限的 帮助。 1 4 数据挖掘的功能 数据挖掘功能用于指定数据挖掘任务中要找的模式类型。数据挖掘任 务一般可以分两类：描述和预测。描述性挖掘任务刻划数据库中数据的一 般特性。预测性挖掘任务在当前数据上进行推断，以进行预测。 在某些情况下，用户不知道他们的数据中什么类型的模式是有趣的， 因此可能想并行地搜索多种不同的模式。这样，重要的是，数据挖掘系统 要能够挖掘多种类型的模式，以适应不同的用户需求或不同的应用。此外， 数据挖掘系统应当能够发现各种粒度( 即不同的抽象层) 的模式。数据挖 掘系统应当允许用户给出提示，指导或聚焦有趣模式的搜索。由于有些模 式并非对数据库中的所有数据都成立，通常每个被发现的模式带上一个确 定性或“可信性”度量。 1 4 1 概念类描述：特征化和区分 数据可以与类或概念相关联。用汇总的、简洁的、精确的方式描 述每个类和概念通常是用户所期望的。这种类或概念的描述称为类 概念描述( c l a s s c o n c e p td e s c r i p t i o n ) 。这种描述可以通过下述方 法得到：1 ) 数据特征化，一般地汇总所研究类( 通常称为目标类 ( t a r g e tc l a s s ) ) 的数据；2 ) 数据区分，将目标类与一个或多个 比较类( 通常称为对比类( c o n t r a s t i n gc l a s s ) ) 进行比较；3 ) 数据 特征化和比较。 数据特征化( d a t ac h a r a c t e r i z a t i o n ) 是目标类数据的一般特征 或特性的汇总。通常，用户指定类的数据通过数据库查询收集。有许 多有效的方法，将数据特征化和汇总。种面向属性的归纳技术可以用 来进行数据的概化和特征化，而不必一步步地与用户交互。数据特征 的输出可以用多种形式提供。包括饼图、条图、曲线、多维数据立方 体和包括交叉表在内的多维表。结果描述也可以用概化关系 ( g e n e r a l i z e dr e l a t i o n ) 或规则形式( 称作特征规则) 提供。 数据区分( d a t ad i s c r i m i n a t i o n ) 是将目标类对象的一般特性与一 个或多个对比类对象的一般特性比较。目标类和对比类由用户指定， 而对应的数据通过数据库查询检索。例如，你可能希望将上一年销售 增加l0 的软件产品与同一时期销售至少下降30 的那些产品进 行比较。用于数据区分的方法与用于数据特征化的类似。区分描述输 出的形式类似于特征描述，但区分描述应当包括比较度量，帮助区分 目标类和对比类。用规则表示的区分描述称为区分规则 ( d i s c r i m i n a n tr u l e ) 。用户应当能够对特征和区分描述的输出进行 操作。 1 4 2 关联分析 关联分析( a s s o c i a t i o na n a l y s i s ) 发现关联规则，这些规则展示 属性一值频繁地在给定数据集中一起出现的条件。关联分析广泛用于 购物篮或事务数据分析。更形式地，关联规则( a s s o c i a t i o nr u l e ) 是 形如xj y ，即“a ，八八a 。jb ， ab 。”的规则，其中， a ， ( i 1 ，i i 】) ) ，b 。( j l ，n ) ) 是属性一值对。关联规则 xjy 解释为“满足x 中条件的数据库元组多半也满足y 中条件”。 1 4 3 分类和预测 分类( c l a s s i f i c a t i o n ) 是这样的过程，它找出描述并区分数据 类或概念的模型( 或函数) ，以便能够使用模型预测类标记未知的对象 类。导出模型是基于对训练数据集( 即其类标记己知的数据对象) 的 分析。 导出模式可以用多种形式表示，如分类( i f t h e n ) 规则、判定树、 数学公式或神经网络。判定树是一个类似于流程图的树结构，每个 节点代表一个属性值上的测试，每个分支代表测试的一个输出，树叶 代表类或类分布。判定树容易转换成分类规则。当用于分类时，神经 网络是一组类似于神经元的处理单元，单元之间加权连接。 分类可以用来预测数据对象的类标记。然而，在某些应用中，人 们可能希望预测某些空缺的或不知道的数据值，而不是类标记。当 被预测的值是数值数据时，通常称之为预测( p r e d i c t i o n ) 。尽管预 测可以涉及数据值预测和类标记预测，通常预测限于值预测，并因此 不同于分类。预测也包含基于可用数据的分布趋势识别。 相关分析( r e l e v a n c ea n a l y s i s ) 可能需要在分类和预测之前进行， 它试图识别对于分类和预测无用的属性。这些属性应当排除。 1 4 4 聚类分析 与分类和预测不同，聚类( c l u s t e r i n g ) 分析数据对象，而不考 虑已知的类标记。一般情况下，训练数据中不提供类标记，因为不知 道从何开始。聚类，可以用于产生这种标记。对象根据最大化类内的 相似性、最小化类间的相似性的原则进行聚类或分组。即对象的簇( 聚 类) 这样形成，使得在一个簇中的对象具有很高的相似性，而与其他 簇中的对象很不相似。所形成的每个簇可以看作一个对象类，由它可 以导出规则。聚类也便于分类编制( t a x o n o m yf o r m a t i o n ) ，将观察 到的内容组织成类分层结构，把类似的事件组织在一起。 1 4 5 孤立点分析 数据库中可能包含一些数据对象，它们与数据的一般行为或模型 不一致。这些数据对象是孤立点( o u t l i e r ) 。大部分数据挖掘方法 将孤立点视为噪声或异常而丢弃。然而，在一些应用中( 如欺骗检测) ， 罕见的事件可能比正常出现的那些更有趣。孤立点数据分析称作孤 立点挖掘( o u t l i e rm i n i n g ) 。 孤立点可以使用统计试验检测。它假定一个数据分布或概率模型， 并使用距离度量，到其他聚类的距离很大的对象被视为孤立点。基于 偏差的方法通过考察一群对象主要特征上的差别识别孤立点，而不是 使用统计或距离度量。 1 4 6 演变分析 数据演变分析( e v o l u t i o na n a l y s i s ) 描述行为随时间变化的对象 的规律或趋势，并对其建模。尽管这可能包括时间相关数据的特征化、 区分、关联、分类或聚类，这类分析的不同特点包括时间序列数据分 析、序列或周期模式匹配和基于类似性的数据分析。 1 5 数据挖掘的分类 由于数据挖掘源于多个学科，因此数据挖掘研究就产生了大量的、各 种不同类型数据挖掘系统。这样，就需要对数据挖掘系统给出一个清楚的 分类。这种分类可以帮助用户区分数据挖掘系统，确定最适合其需要的数 据挖掘系统。根据不同的标准，数据挖掘系统可以分类如下： 根据挖掘的数据库类型分类：数据挖掘系统可以根据挖掘的数据库类 型分类。数据库系统本身可以根据不同的标准( 如数据模型，或数据或所 涉及的应用类型) 分类，每一类可能需要自己的数据挖掘技术。这样，数 据挖掘系统就可以相应分类。 根据挖掘的知识类型分类：数据挖掘系统可以根据所挖掘的知识类型 1 2 分类。即根据数据挖掘的功能，如特征化、区分、关联、分类聚类、孤立 点分析和演变分析、偏差分析、类似性分析等分类。一个全面的数据挖掘 系统应当提供多种和或集成的数据挖掘功能。 此外，数据挖掘系统可以根据所挖掘的知识的粒度或抽象层进行区分， 包括概化知识( 在高抽象层) ，原始层知识( 在原始数据层) ，或多层知识 ( 考虑若干抽象层) 。一个高级数据挖掘系统应当支持多抽象层的知识发 现。 数据挖掘系统还可以分类为挖掘数据规则性( 通常出现的模式) 和数 据不规则性( 如异常或孤立点) 。一般地，概念描述、关联分析、分类、预 测和聚类挖掘数据规律，将孤立点作为噪声排除。这些方法也能帮助检测 孤立点。 根据所用的技术分类：数据挖掘系统也可以根据所用的数据挖掘技术 分类。这些技术可以根据用户交互程度( 例如自动系统、交互探查系统、 查询驱动系统) ，或所用的数据分析方法( 例如面向数据库或数据仓库的技 术、机器学习、统计学、可视化、模式识别、神经网络等) 描述。复杂的 数据挖掘系统通常采用多种数据挖掘技术，或采用有效的、集成的技术， 结合一些方法的优点。 根据应用分类：数据挖掘系统可以根据其应用分类。例如，可能有些 数据挖掘系统特别适合金融、电信、d na 、股票市场、e m a i l ，等等。不 同的应用通常需要集成对于该应用特别有效的方法。因此，普通的、全能 的数据挖掘系统可能并不适合特定领域的挖掘任务。 第二章关联规则挖掘技术 随着大量数据不停地收集和存储，许多企业的决策人员对于从他们的数据 库中挖掘关联规则越来越感兴趣。关联规则挖掘可以用来发现大量数据中项集 之间有趣的关联或相关联系。从大量商务事务记录中发现有趣的关联关系，可 以帮助许多商务决策的制定，如分类设计、交叉购物和贱卖分析。 本章将先给出关联规则挖掘的一些核心概念，然后详细分析现有的关联规 则发现方法，进而指出它的不足之处。 2 1 关联规则挖掘的基本概念 关联规则挖掘的一个典型例子是购物篮分析。该过程发现顾客放入其购物 篮中不同商品之间的联系，分析顾客的购买习惯。通过了解哪些商品频繁地被 顾客同时购买，这种关联的发现可以帮助零售商制定营销策略。例如，在同一 次去超级市场，如果顾客购买牛奶，他也购买面包的可能性有多大? 通过帮助 零售商有选择地经销和安排货架，这种信息可以促进销售。 定义1 关联规则挖掘的数据集记为d ( 一般为事务数据库) ，d = t ，屯，屯，乙) ，tk = j 。厶，j 。 ，t k ( k = l ，2 ，) 称为事务 ( t r a n s a c t i o n s ) ，i 。( m = 1 ，2 ，p ) 称为项目( i t e m ) 。 定义2 设i = j ，厶，l ) 是d 中全体项目组成的集合，i 的任何子集x 称为d 中的项目集( i t e m s e t ) ，lx i = k 称为集合x 为k 项目集( k i t e m s e t ) 。 设t 。和x 分别为d 中的事务和项目集，如果x t 。称事务t t 包含项目集x 。 每一个事务都有个唯一的标识符，称为t i d 。 定义3 数据集d 中包含项目集x 的事务数称为项目集x 的支持数，记为o ，。项目集x 的支持度记为s u p p o r t ( x ) ： s u p p o r t ( x ) = 羔1 0 0 ，6 ( 或s u p p o n ( x ) = 熹) lu iiu i 其中f d f 是数据集d 的事务数，若s u p p o r t ( x ) 不小于用户指定的最小支持 度( m i n s u p p o r t ) ，则称x 为频繁项目集，简称频集( 或大项目集) ，否则称x 为非频繁项目集，简称非频集( 或小项目集) 。包含k 个项的项集称为k 项集， 相应的，k 一项集若是频繁的则称为频繁k 一项集，通常记作l k 。 定义4 若x 、y 为项目集，且x n y = o ，蕴涵式x j 】，称为关联规则，x 、 y 分别称为关联规则x ；】，的前提( 或前件) 和结论( 或后件) 。项目集x u y 的支持度称为关联规则x jy 的支持度，记做： s u p p o r t ( xjy ) ，s u p p o r t ( xjy ) = s u p p o r t ( xuy ) 关联规则的置信度记做c o n f i d e n c e ( xj y ) ： c o n f i d e r i c e ( xj y ) ：s u p p o r t ( x u y ) 1o o s u p p o r t ( x ) 通常用户根据挖掘需要指定的最小置信度记为m i n c o n f i d e n c e 。 支持度和置信度是描述关联规则的两个重要概念，前者用于衡量关联规则 在整个数据集知道统计重要性，后者用于衡量关联规则的可信程度。一般来说， 只有支持度和置信度都较高的关联规则才可能是用户感兴趣、有用的关联规则。 定义 5若 s u p p o r t ( x jy ) m i n s u p p o r t ，且 c o n f i d e n c e ( x j y l m i n c o n f i d e n c e ，称关联规则x j r 为强规则，否则称关 联规则x jy 为弱规则。 定理1 设x 、y 是数据集d 中的项目集： ( 1 ) 若x y ，则s u p p o r t ( x ) s u p p o r t ( y ) 。 ( 2 ) 若一y ，如果x 是非频繁集，则y 也是非频繁集。 ( 3 ) 若x y ，如果y 是频繁集，则x 也是频繁集。 关联规则挖掘的任务就是要挖掘出d 中所有的强规则。