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所示。
? 首先找出频繁多维值的组合，然后寻找 DB
中相应的频繁项集。设支持度阈值为 2，即
属性值的组合出现两次或两次以上为频繁项
集，称为多维模式或叫做 MD-模式。
? 要挖掘 MD-模式时，可以使用最早由 beyer和
Ｒ amakrishnan(它是个有效的, 冰山立方
体,,见下图 )开发的改进 BUC算法。
? 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-模式,
图 8-6是 BUC算法对表 8-3的处理结果。
? 找到 MD-模式后，下一步对每个 MD-模式在
MD-投影中挖掘频繁项集。
8.7 WEB挖掘
? 在分布式的信息环境中,文档或对象通常被链接在
一起,从而可以起到互相访问的作用。例如，
WWW和在线服务，这类信息提供的环境，通过
工具 (如超链接,URL地址 )从一个对象转到另一个
对象，从而获得有用的信息。 WEB是一个超 8亿页
的超文本的载体，而且信息量还在不断增长。几
乎每天要增加 100万个页面，而且页面每几个月就
会更新一次，因此，每月会有几百 G字节的数据
在变化。
? Web挖掘可以定义为使用数据库挖掘技术
在 Web文档和服务中自动在发掘并且提取
信息。它涉及到整个挖掘的过程，而不仅
仅是应用标准的数据挖掘工具。 Web挖掘
任务划分为４个子任务,
1.寻找资源 ─ 这是一个从 Web上的多媒体资
源中在线或离线检索数据的过程。
电子时事通信、电子新闻专线、新闻组
以及通过删除 HTML标记得到的 HTML文档。
2.信息选择和预处理 ─ 这是在上面的子任务
中检索出的不同种类的原始数据的转换过程。
转换过程既可以是一种预处理，比例删除
停止字，障碍字等，或者旨在获得所需要的
表示法，例如查找在训练主体中的习语，以
第一顺序逻辑的形式表示文本等。
3.总结 ─ 总结是一个在个别 Web站点上自动
地发掘出综合模式的过程。
本阶段使用了不同的综合目的机器学习、
数据挖掘技术和指定的面向 Web的方法。
4.分析 ─ 在这一过程中，执行生效和／或解
释已挖掘出模式。
? Web挖掘可以基于所挖掘的部分进行分类，
分为 3类,
1.Web内容挖掘 ─ 描述从 Web文档发掘出有用
的信息。
内容包括：文本、图像、音频、视频、元
数据以及超链接。
2.Web结构挖掘 ─ 挖掘 Web上的链接结构中的
潜在模型。
3.Web使用挖掘 ─ 挖掘在网上冲浪的过程或行
为所产生的数据。
当 1类和 2类利用 Web上的真实或主要数据时，
3类就会从用户在同 Web进行交互时的行为
入手，挖掘第二级数据。这些数据包括访问
Web服务器日志、代理服务器日志、浏览器
日志、用户数据、注册数据、用户会话或交
易,Cookies、书签数据以及任何个人同
Web进行交互所产生的其他数据。
? 在下两小节中，介绍 Web挖掘的３个主要技
术。
8.8 HITS和 LOGSOM算法
? 到目前为止，基于索引的 Web搜索引擎是
用户搜索信息的主要工具。
? 问题是搜索引擎不适合那些大范围的不精
确的搜索任务。
? 我们的目标是能搜索出最主要的网页，即
相关的且是高质量的网页。因此 Web挖掘
中必须发掘出两种重要类型的网页：权威
页 (提供了指定主题的最佳信息来源 )和 Hub
页 (提供同权威页链接的集合 )。
? Hub页的一个显著特征就是：它们是某个焦
点主题的权威页的有力提供者。可以定义
一个好的 hub页，如果它是指向一些好的权
威页。与些同时，一个好的权威页，是被
一些好的 hub页所指向的。两者之间的这种
相互加强关系，正是 HITS算法 (Hyperlink-
Induced Topic search)的中心思想，它正是
一种搜索好的 hub页和权威页的算法。
? HITS算法的两个主要步骤,
? 1.取样组分 (sampling component)，构建在
相关信息中可能经常出现的网页的集合。
在取样阶段，将 Web视为一个网页的有
向图。 HITS算法首先构造子图，在子图中
可以搜索 hub页和权威页。目标是构造出蕴
含高相关性、权威性的网页的子图。在构
造子图之前，先使用查询方法从基本索引
的搜索引擎中收集网页的根集 (root set)。
算法希望根集含有部分权威页，或根集同
大多数权威网页相链接。
? 2.权重传播 (weight-propagation)，通过反
复的过程来估计 hub页和权威页，并且获得
最具相关性和权威性的网页的子页。
在权威传播阶段，通过为所有优秀的
hub页和权威页制定一个混合的数字表达式，
从基本集合 V中抽取它们。设非负的权威页
权重为 ap，非负的 hub页为 hp，且每一个网
页中 p∈ V。算法只对权重的相对值感兴趣，
因此对权重进行标准化，使权重的总和在
一定界限内。权重 a和 h的初始化均为一常
量，但最终的权重不受他们的影响。
? 算法按以下方式更新权威页和 hub页。如果
一个网页有一些好的 hub页来指向，那么就
增加它的权威页的权重，因此，将网页 p的
ap值设为所有指向 p的网页 q的 hq值之和,
相反，如果网页指向一些好的权威页，那
么就增加它的 hub页的权重,
pq,ha qqp ??? ? 例如
qp,ah qqp ??? ? 例如
? 有一种较简单的更新方法。首先对网页进
行编号 {1,2,…,n}，然后定义矩阵 A为 n× n
阶矩阵，第 (i,j)个元素的值如果为 1，则表
示网页 i和网页 j相连，为 0，相反。刚计算
时，所有页都是 hub页权威页，而且用下面
向量表示,
a={a1,a2,…,an}和 h={h1,h2,…,hn}
对权威页和 hub页的更新规则为,
a=ATh; h=Aa
或者,
a=ATh=(ATA)a; h=Aa=(AAT)h
? 上面关系是向量 a和 h的重复计算，依线性
代数的理论，最终结果标准化之后，收敛
于特征向量 ATA。可见，计算的 hub和权威
页实际上是所收集的链接网页的本质特征，
而不是初始权重中派生出来。算法输出一
个同指定的搜索主题相关的，由具有最大
权重的网页和具有最大权威权重的网页所
组成的列表。
? 例如，以图 8-7为例，演示算法的基本步骤。
? 假设在查询时，搜索引擎出 6个相关的文档，
希望从中选出最重要的权威页和 hub页。
? 所选择有文档在一个有向子图中相连接，
见图 8-7a所示 (少了 3指向 5)，图 8-7b为矩阵
A和初始权重向量 a和 h。
? HITS算法首先更改向量 a和 h,
在算法的第一步可得：文档 5最具权威性，
文档 1是最好的 hub。在随后的步骤中会纠
正两个向量的权重因子，但本例的得出的
权威页和 hub页的顺序保持不变。
? 由于 Internet的不断增长，在使用单个词进
行搜索时会检索出成千上万的文档，因此
挖掘变得相当复杂和低效率，并且还有一
些是不相干的网页，一些可能被删除，另
一些则可能禁止访问。
? HITS算法适用于静态网页的挖掘，而
LOGSOM算法可用于动态网页。
? LOGSOM算法将信息的布局完全组织成为一
个用户可以理解的图表。
? LOGSOM系统使用自组图谱 (SOM)按照用户
的导航模式将网页组织成一个二维表。
? SOM技术是 Web页的组织问题是最常用的
技术，它不仅可以将数据组织在一个类中，
而且可以以图表的形式来表示类之间的关
系。
? 系统首先创建一个 Web日志，用它来表示
日期、时间的所请求 Web页的地址，以及
用户计算机的 IP。
? 假设存在一个有限的惟一 URL的集合,
U={url1,url2,…,urln}
和一个有限的 m个用户事务集合,
T={t1,t2,…,tm}
事务用向量来表示,
t={u1,u2,…,un}
? 其中,
? 预处理日志文件可以用二进制矩阵的形式
来表示。表 8-4为一例子。
? tu r lifo t h e r w i s ei ?? 10iu
? 现实中,(n× m)维的事务表可能很大，需
要缩小数据量。通过使用 K-meams聚类算
法，可以将事务分组到预定的第 k(k<<m)
个事务组中。表 8-5为一减小的数据集的示
例，其中行中的元素表示事务组访问特定
的 URL的总次数 (表的形式和值只是一个示
例，与表 8-4中的值不直接相关 )。
? 缩小后的新表作为 SOM处理的输入。 SOM的
聚类技术在相关的人工神经网络文献中介绍，
此处只对应用 SOM算法得出的结果给予解释。
表 8-6是 SOM处理的典型结果。该表并不是
表 8-4和表 8-5的处理结果，只是一个示例。
? 每一个 URL会基于它同其他 URL的相似性，
根据用户的使用或是用户的导航模式 (表 8-5
中的事务组, 权重, )，都会被映射到一个
SOM上。
? 表中的空白节点表示不存在相应的 URL，其
中有标号的节点表示每个节点 (或每个类 )中
包含的 URL的数量。
? LOGSOM算法用于识别公司潜在的客户访问
了公司的哪些网页，从而为公司提供改善
决策的信息
? 如果一个节点中的网页能将客户成功在导
航他所想要的信息或页面中，在同一节点
的其他页面也可能获得成功。这样互联网
广告的投放由用户导航模式的直接支持。
8.9 挖掘路径遍历模式
? 改进公司的 WEB站点之前，先估计它的当
前用量。每个站点都由 Web服务器电子化
在管理，所有活动都会记入日志，存放在
日志文件中。用户的所有痕迹都存在这个
文件中。因此，可应用数据挖掘技术，从
该文件中提取一些可以间接在反应站点质
量的信息，也可以挖掘数据来优化 Web服
务器的性能，找出哪些产品被合在一起购
买，或者确定站点是否按照预期的情况使
用。
? LOGSOM方法重点在于 Web页面的相似性，而其
他技术则强调用户经过 Web的路径的相似性。
? 捕捉 Web环境中的用户访问模式被称为挖掘路径
遍历模式，它属于另一种数据挖掘技术。这种技
术还处于萌芽阶段，但却在互联网应用中显示出
了极光明的前景。
? 由于用户沿着信息路径在网上搜寻想要的信息，
一些对象或文档只是因为它们的位置而被访问，
而不是因为它们的内容。这个特征不可避免在增
加从遍历数据中获取有用信息的难度，同时也解
释了为什么当前的网络用量主要是为旅行点而不
是为旅行路径提供统计数据。
? 多维事务数据库 DB的结构为
(ID,A1,A2,…,An,items), Ai是 DB中的结构
化属性 (例如顾客的年龄,职业,收入等 )，而
items是同事务连接的项的集合 (例如购物篮
中频繁项集 )。每一个
t=(id,a1,a2,…,an,items-t)由两部分信息组成：
维信息 (a1,a2,…,an)和项集信息。
? 挖掘过程分为两部分：挖掘维度信息的模
式和从投影的子 DB中找出频繁项集。
? 例如，事务 DB如表 8-3所示。
? 首先找出频繁多维值的组合，然后寻找 DB
中相应的频繁项集。设支持度阈值为 2，即
属性值的组合出现两次或两次以上为频繁项
集，称为多维模式或叫做 MD-模式。
? 要挖掘 MD-模式时，可以使用最早由 beyer和
Ｒ amakrishnan(它是个有效的, 冰山立方
体,,见下图 )开发的改进 BUC算法。
? 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-模式,
图 8-6是 BUC算法对表 8-3的处理结果。
? 找到 MD-模式后，下一步对每个 MD-模式在
MD-投影中挖掘频繁项集。
8.7 WEB挖掘
? 在分布式的信息环境中,文档或对象通常被链接在
一起,从而可以起到互相访问的作用。例如，
WWW和在线服务，这类信息提供的环境，通过
工具 (如超链接,URL地址 )从一个对象转到另一个
对象，从而获得有用的信息。 WEB是一个超 8亿页
的超文本的载体，而且信息量还在不断增长。几
乎每天要增加 100万个页面，而且页面每几个月就
会更新一次，因此，每月会有几百 G字节的数据
在变化。
? Web挖掘可以定义为使用数据库挖掘技术
在 Web文档和服务中自动在发掘并且提取
信息。它涉及到整个挖掘的过程，而不仅
仅是应用标准的数据挖掘工具。 Web挖掘
任务划分为４个子任务,
1.寻找资源 ─ 这是一个从 Web上的多媒体资
源中在线或离线检索数据的过程。
电子时事通信、电子新闻专线、新闻组
以及通过删除 HTML标记得到的 HTML文档。
2.信息选择和预处理 ─ 这是在上面的子任务
中检索出的不同种类的原始数据的转换过程。
转换过程既可以是一种预处理，比例删除
停止字，障碍字等，或者旨在获得所需要的
表示法，例如查找在训练主体中的习语，以
第一顺序逻辑的形式表示文本等。
3.总结 ─ 总结是一个在个别 Web站点上自动
地发掘出综合模式的过程。
本阶段使用了不同的综合目的机器学习、
数据挖掘技术和指定的面向 Web的方法。
4.分析 ─ 在这一过程中，执行生效和／或解
释已挖掘出模式。
? Web挖掘可以基于所挖掘的部分进行分类，
分为 3类,
1.Web内容挖掘 ─ 描述从 Web文档发掘出有用
的信息。
内容包括：文本、图像、音频、视频、元
数据以及超链接。
2.Web结构挖掘 ─ 挖掘 Web上的链接结构中的
潜在模型。
3.Web使用挖掘 ─ 挖掘在网上冲浪的过程或行
为所产生的数据。
当 1类和 2类利用 Web上的真实或主要数据时，
3类就会从用户在同 Web进行交互时的行为
入手，挖掘第二级数据。这些数据包括访问
Web服务器日志、代理服务器日志、浏览器
日志、用户数据、注册数据、用户会话或交
易,Cookies、书签数据以及任何个人同
Web进行交互所产生的其他数据。
? 在下两小节中，介绍 Web挖掘的３个主要技
术。
8.8 HITS和 LOGSOM算法
? 到目前为止，基于索引的 Web搜索引擎是
用户搜索信息的主要工具。
? 问题是搜索引擎不适合那些大范围的不精
确的搜索任务。
? 我们的目标是能搜索出最主要的网页，即
相关的且是高质量的网页。因此 Web挖掘
中必须发掘出两种重要类型的网页：权威
页 (提供了指定主题的最佳信息来源 )和 Hub
页 (提供同权威页链接的集合 )。
? Hub页的一个显著特征就是：它们是某个焦
点主题的权威页的有力提供者。可以定义
一个好的 hub页，如果它是指向一些好的权
威页。与些同时，一个好的权威页，是被
一些好的 hub页所指向的。两者之间的这种
相互加强关系，正是 HITS算法 (Hyperlink-
Induced Topic search)的中心思想，它正是
一种搜索好的 hub页和权威页的算法。
? HITS算法的两个主要步骤,
? 1.取样组分 (sampling component)，构建在
相关信息中可能经常出现的网页的集合。
在取样阶段，将 Web视为一个网页的有
向图。 HITS算法首先构造子图，在子图中
可以搜索 hub页和权威页。目标是构造出蕴
含高相关性、权威性的网页的子图。在构
造子图之前，先使用查询方法从基本索引
的搜索引擎中收集网页的根集 (root set)。
算法希望根集含有部分权威页，或根集同
大多数权威网页相链接。
? 2.权重传播 (weight-propagation)，通过反
复的过程来估计 hub页和权威页，并且获得
最具相关性和权威性的网页的子页。
在权威传播阶段，通过为所有优秀的
hub页和权威页制定一个混合的数字表达式，
从基本集合 V中抽取它们。设非负的权威页
权重为 ap，非负的 hub页为 hp，且每一个网
页中 p∈ V。算法只对权重的相对值感兴趣，
因此对权重进行标准化，使权重的总和在
一定界限内。权重 a和 h的初始化均为一常
量，但最终的权重不受他们的影响。
? 算法按以下方式更新权威页和 hub页。如果
一个网页有一些好的 hub页来指向，那么就
增加它的权威页的权重，因此，将网页 p的
ap值设为所有指向 p的网页 q的 hq值之和,
相反，如果网页指向一些好的权威页，那
么就增加它的 hub页的权重,
pq,ha qqp ??? ? 例如
qp,ah qqp ??? ? 例如
? 有一种较简单的更新方法。首先对网页进
行编号 {1,2,…,n}，然后定义矩阵 A为 n× n
阶矩阵，第 (i,j)个元素的值如果为 1，则表
示网页 i和网页 j相连，为 0，相反。刚计算
时，所有页都是 hub页权威页，而且用下面
向量表示,
a={a1,a2,…,an}和 h={h1,h2,…,hn}
对权威页和 hub页的更新规则为,
a=ATh; h=Aa
或者,
a=ATh=(ATA)a; h=Aa=(AAT)h
? 上面关系是向量 a和 h的重复计算，依线性
代数的理论，最终结果标准化之后，收敛
于特征向量 ATA。可见，计算的 hub和权威
页实际上是所收集的链接网页的本质特征，
而不是初始权重中派生出来。算法输出一
个同指定的搜索主题相关的，由具有最大
权重的网页和具有最大权威权重的网页所
组成的列表。
? 例如，以图 8-7为例，演示算法的基本步骤。
? 假设在查询时，搜索引擎出 6个相关的文档，
希望从中选出最重要的权威页和 hub页。
? 所选择有文档在一个有向子图中相连接，
见图 8-7a所示 (少了 3指向 5)，图 8-7b为矩阵
A和初始权重向量 a和 h。
? HITS算法首先更改向量 a和 h,
在算法的第一步可得：文档 5最具权威性，
文档 1是最好的 hub。在随后的步骤中会纠
正两个向量的权重因子，但本例的得出的
权威页和 hub页的顺序保持不变。
? 由于 Internet的不断增长，在使用单个词进
行搜索时会检索出成千上万的文档，因此
挖掘变得相当复杂和低效率，并且还有一
些是不相干的网页，一些可能被删除，另
一些则可能禁止访问。
? HITS算法适用于静态网页的挖掘，而
LOGSOM算法可用于动态网页。
? LOGSOM算法将信息的布局完全组织成为一
个用户可以理解的图表。
? LOGSOM系统使用自组图谱 (SOM)按照用户
的导航模式将网页组织成一个二维表。
? SOM技术是 Web页的组织问题是最常用的
技术，它不仅可以将数据组织在一个类中，
而且可以以图表的形式来表示类之间的关
系。
? 系统首先创建一个 Web日志，用它来表示
日期、时间的所请求 Web页的地址，以及
用户计算机的 IP。
? 假设存在一个有限的惟一 URL的集合,
U={url1,url2,…,urln}
和一个有限的 m个用户事务集合,
T={t1,t2,…,tm}
事务用向量来表示,
t={u1,u2,…,un}
? 其中,
? 预处理日志文件可以用二进制矩阵的形式
来表示。表 8-4为一例子。
? tu r lifo t h e r w i s ei ?? 10iu
? 现实中,(n× m)维的事务表可能很大，需
要缩小数据量。通过使用 K-meams聚类算
法，可以将事务分组到预定的第 k(k<<m)
个事务组中。表 8-5为一减小的数据集的示
例，其中行中的元素表示事务组访问特定
的 URL的总次数 (表的形式和值只是一个示
例，与表 8-4中的值不直接相关 )。
? 缩小后的新表作为 SOM处理的输入。 SOM的
聚类技术在相关的人工神经网络文献中介绍，
此处只对应用 SOM算法得出的结果给予解释。
表 8-6是 SOM处理的典型结果。该表并不是
表 8-4和表 8-5的处理结果，只是一个示例。
? 每一个 URL会基于它同其他 URL的相似性，
根据用户的使用或是用户的导航模式 (表 8-5
中的事务组, 权重, )，都会被映射到一个
SOM上。
? 表中的空白节点表示不存在相应的 URL，其
中有标号的节点表示每个节点 (或每个类 )中
包含的 URL的数量。
? LOGSOM算法用于识别公司潜在的客户访问
了公司的哪些网页，从而为公司提供改善
决策的信息
? 如果一个节点中的网页能将客户成功在导
航他所想要的信息或页面中，在同一节点
的其他页面也可能获得成功。这样互联网
广告的投放由用户导航模式的直接支持。
8.9 挖掘路径遍历模式
? 改进公司的 WEB站点之前，先估计它的当
前用量。每个站点都由 Web服务器电子化
在管理，所有活动都会记入日志，存放在
日志文件中。用户的所有痕迹都存在这个
文件中。因此，可应用数据挖掘技术，从
该文件中提取一些可以间接在反应站点质
量的信息，也可以挖掘数据来优化 Web服
务器的性能，找出哪些产品被合在一起购
买，或者确定站点是否按照预期的情况使
用。
? LOGSOM方法重点在于 Web页面的相似性，而其
他技术则强调用户经过 Web的路径的相似性。
? 捕捉 Web环境中的用户访问模式被称为挖掘路径
遍历模式，它属于另一种数据挖掘技术。这种技
术还处于萌芽阶段，但却在互联网应用中显示出
了极光明的前景。
? 由于用户沿着信息路径在网上搜寻想要的信息，
一些对象或文档只是因为它们的位置而被访问，
而不是因为它们的内容。这个特征不可避免在增
加从遍历数据中获取有用信息的难度，同时也解
释了为什么当前的网络用量主要是为旅行点而不
是为旅行路径提供统计数据。
