《数据把掘概念与技术》第八章(8-6) 多维关联规则挖掘

8.6多维关联规则挖掘 多维事务数据库DB的结构为 IDA1A2… A items),A是DB中的结 构化属性(例如顾客的年龄,职业,收入等) 而 items是同事务连接的项的集合(例如购 物篮中频繁项集)。每一个 组成:维信意(a1,2,3)和项集信息 ●挖掘过程分为两部分:挖掘维度信息的模 式和从投影的子DB中找出频繁项集

8.6 多维关联规则挖掘 • 多维事务数据库DB的结构为 (ID,A1 ,A2 ,…,An ,items) ，Ai是DB中的结 构化属性(例如顾客的年龄,职业,收入等)， 而items是同事务连接的项的集合(例如购 物篮中频繁项集)。每一个 t=(id,a1 ,a2 ,…,an ,items-t)由两部分信息 组成：维信息(a1 ,a2 ,…,an )和项集信息。 • 挖掘过程分为两部分：挖掘维度信息的模 式和从投影的子DB中找出频繁项集

·例如,事务DB如表8-3所示。 表8-3多维事务数据库DB D A1 A1 itel 01 YZ 00 1223 n Z W X.Z.W 04 c XY ·首先找出频繁多维值的组合,然后寻找DB 中相应的频繁项集。设支持度阈值为2,即 属性值的组合出现两次或两次以上为频繁项 集,称为多维模式或叫做MD-模式

• 例如，事务DB如表8-3所示。 • 首先找出频繁多维值的组合，然后寻找DB 中相应的频繁项集。设支持度阈值为2，即 属性值的组合出现两次或两次以上为频繁项 集，称为多维模式或叫做MD-模式

●要挖掘MD-模式时,可以使用最早由 beyer 和 Ramakrishnan(它是个有效的“冰山立 方体”,见下图)开发的改进BUC算法 0D(顶点)方体 1-D方体 2D方体 (age, income (a 3-D(基本)方体 图6-17方体的格形成3D数据立方体(每个方体代表一个不同分组,基本 方体包含三个谓词age, income和buys)

• 要挖掘MD-模式时，可以使用最早由beyer 和Ｒamakrishnan(它是个有效的“冰山立 方体”，见下图)开发的改进BUC算法

·BUC算法的基本步骤如下:首先,在第—维 (A1)中按值的字母顺序将每个项进行排序 1在该维中仅有的MD-模式为(a,*,*),因为 只有a值的支持度大于2。其它维的值(*)在 第一步不相关,可取任意值。 在DB中选择那些具有MD-模式的项。即 T01和T03事务。针对第二维(A2),值1和2, 对简化的DB进行再一次排序。没有符合支 持度的模式,所以不存在A1和A2值的MD 模式。因此可忽略A2

• BUC算法的基本步骤如下:首先，在第一维 (A1)中按值的字母顺序将每个项进行排序。 1.在该维中仅有的MD-模式为(a,*,*)，因为 只有a值的支持度大于2。其它维的值(*)在 第一步不相关，可取任意值。 在DB中选择那些具有MD-模式的项。即 T01和T03事务。针对第二维(A2),值1和2, 对简化的DB进行再一次排序。没有符合支 持度的模式，所以不存在A1和A2值的MD- 模式。因此可忽略A2

在第三维(A3)中按字母顺序进行排序。子集 (a,*m)出现两次,因此它是一个MD-模式。 2.重复步骤1的过程:只从A2开始,不需要搜 索第一维。 第二次迭代从A2开始,MD-模式为(*,2,*), 针对A3,不存在其它MD-模式。最后一次迭 代,从A3开始,(*,*,m)为MD-模式

在第三维(A3)中按字母顺序进行排序。子集 (a,*,m)出现两次，因此它是一个MD-模式。 2.重复步骤1的过程：只从A2开始，不需要搜 索第一维。 第二次迭代从A2开始，MD-模式为(*,2,*), 针对A3，不存在其它MD-模式。最后一次迭 代，从A3开始，(*,*,m)为MD-模式

图8-6是BUC算法对表8-3的处理结果。 (A1*,*) (*A2,·) (*,A3) (A,A2,*) A,,A3) 图86对表8-3中的数据库,使用BUC算法得到的数据处理树 找到MD-模式后,下一步对每个MD-模式在 MD-投影中挖掘频繁项集

图8-6是BUC算法对表8-3的处理结果。 • 找到MD-模式后，下一步对每个MD-模式在 MD-投影中挖掘频繁项集

8.7WEB挖掘 在分布式的信息环境中文档或对象通常被链接在 一起,从而可以起到互相访问的作用。例如, WWW和在线服务,这类信息提供的环境,通过 工具(如超链接、URL地址)从一个对象转到另 个对象,从而获得有用的信息。WEB是一个超8 亿页的超文本的载体,而且信息量还在不断增长。 几乎每天要增加100万个页面,而且页面每几个 月就会更新一次,因此,每月会有几百G字节的 数据在变化

8.7 WEB挖掘 • 在分布式的信息环境中,文档或对象通常被链接在 一起,从而可以起到互相访问的作用。例如， WWW和在线服务，这类信息提供的环境，通过 工具(如超链接、URL地址)从一个对象转到另一 个对象，从而获得有用的信息。WEB是一个超8 亿页的超文本的载体，而且信息量还在不断增长。 几乎每天要增加100万个页面，而且页面每几个 月就会更新一次，因此，每月会有几百G字节的 数据在变化

web挖掘可以定义为使用数据库挖掘技术 在Web文档和服务中自动在发掘并且提取 信息。它涉及到整个挖掘的过程,而不仅 仅是应用标准的数据挖掘工具。Web挖掘 任务划分为4个子任务 1寻找资源这是一个从Web上的多媒体资 源中在线或离线检索数据的过程。 电子时事通信、电子新闻专线、新闻组 以及通过删除HTML标记得到的HTML文档

• Web挖掘可以定义为使用数据库挖掘技术 在Web文档和服务中自动在发掘并且提取 信息。它涉及到整个挖掘的过程，而不仅 仅是应用标准的数据挖掘工具。Web挖掘 任务划分为４个子任务： 1.寻找资源─这是一个从Web上的多媒体资 源中在线或离线检索数据的过程。 电子时事通信、电子新闻专线、新闻组 以及通过删除HTML标记得到的HTML文档

2.信息选择和预处理这是在上面的子任务 中检索出的不同种类的原始数据的转换过程。 转换过程既可以是一种预处理,比例删除 停止字,障碍字等,或者旨在获得所需要的 表示法,例如查找在训练主体中的习语,以 第一顺序逻辑的形式表示文本等。 3总结总结是一个在个别Web站点上自动 地发掘出综合模式的过程。 本阶段使用了不同的综合目的机器学习 数据挖掘技术和指定的面向Web的方法

2.信息选择和预处理─这是在上面的子任务 中检索出的不同种类的原始数据的转换过程。 转换过程既可以是一种预处理，比例删除 停止字，障碍字等，或者旨在获得所需要的 表示法，例如查找在训练主体中的习语，以 第一顺序逻辑的形式表示文本等。 3.总结─总结是一个在个别Web站点上自动 地发掘出综合模式的过程。 本阶段使用了不同的综合目的机器学习、 数据挖掘技术和指定的面向Web的方法

4.分析在这一过程中,执行生效和/或解 释已挖掘出模式。 wveb挖掘可以基于所挖掘的部分进行分类, 分为3类: 1.Web内容挖掘描述从Web文档发掘出有用 的信息。 内容包括:文本、图像、音频、视频、元 数据以及超链接

4.分析─在这一过程中，执行生效和／或解 释已挖掘出模式。 • Web挖掘可以基于所挖掘的部分进行分类， 分为3类: 1.Web内容挖掘─描述从Web文档发掘出有用 的信息。 内容包括：文本、图像、音频、视频、元 数据以及超链接