第十一章-序列模式挖掘.pptVIP

第十一章 序列模式挖掘 一、序列模式的概念及定义 举例说明，比如有顾客租借录像带，典型的顺序是先租“星球大战”，然后是“帝国反击战”，再是“杰达武士归来”(这三部影片是以故事发生的时间先后而情节连续的)。值得注意的是租借这三部电影的行为并不一定需要是连续的。在任意两部之间随便插租了什么电影，仍然还是满足了这个序列模式，并且扩展一下，序列模式的元素也可以不只是一个元素(如一部电影)，它也可以是一个项集(item set)。 项集，指的是多个物品组成的集合，内部元素不分排列顺序，比如“枕头和枕头套”就可以看作是由两个项(item)组成的项集，它也可以作为某一个序列模式的元素。 相关概念及定义 以商品交易为例子，数据源是一个给定的由客户交易组成的大型数据库，每个交易由客户号(customer-id)，交易时间以及在交易中购买的项组成。 项集(itemset):由项(item)组成的一个非空集合。 序列(sequence):是一列排好序的项集。 相关概念及定义 最大序列 相关概念及定义 客户序列 一个数据库中的交易记录可以表示成上表 相关概念及定义 序列模式 如果一个序列s包含于一个客户序列中，则称该客户支持序列s。一个序列的支持度定义为支持该序列的客户总数。 给定一个由客户交易组成的数据库D，挖掘序列模式的问题是：在那些具有客户指定最小支持度的序列中找出最大序列。而这样的最大序列就代表了一个序列模式。 示例 对于最小支持数为2的情况，有两个序列： (30) (90) 和 (30) (40,70) 在那些满足支持度约束的序列中是最大的，也是我们所需的序列模式。 序列挖掘算法 步骤 1) 排序阶段。数据库D以客户号为主键，交易时间为次键进行排序。这个阶段将原来的事务数据库转换成由客户序列组成的数据库。 2) 频繁项集阶段。找出所有频繁项集组成的集合L。也同步得到所有频繁1-序列组成的集合。 3) 转换阶段。在找序列模式的过程中，要不断地进行检测一个给定的频繁集是否包含于一个客户序列中。 4) 序列阶段利用已知的频繁集的集合来找到所需的序列。类似于关联的Apriori算法。 算法示例 1) 在给出的数据库中，找出所有频繁1-序列组成的集合： 和 2) 给一个可行的映射。 算法示例 3)转换。为了使这个过程尽量的快，用另一种形式来替换每一个客户序列。 在转换完成的客户序列中，每条交易被其所包含的所有频繁项集所取代。 如果一条交易不包含任何频繁集，在转换完成的序列中它将不被保留。 如果一个客户序列不包含任何的频繁项集，在转换好的数据库中这个序列也将不复存在。 一个客户序列被一列由频繁集组成的集合所取代，每个频繁集的集合表示为{l1,l2,…,ln}，l i表示一个频繁集。 算法示例 例：考察右图所示的一个客户序列组成的数据库，假定客户序列已经以转换的形式出现了，每一条交易都被包含其中的频繁项集取代，频繁项集则由整数代替。最小支持数据定义为2。 算法示例 结束语 数据挖掘涉及的是多学科的领域，涉及数据库技术、人工智能、机器学习、神经网络、统计学、模式识别、知识库系统、知识获取、信息检索、高性能计算和数据可视化。本身在不断发展。有目前有许多富有挑战的领域如文本数据挖掘、Web信息挖掘、多媒体信息挖掘、空间数据挖掘等。本课程是一个入门，希望对以后的进一步学习与研究打下一个基础。 * * 不失一般性假定项集中的项由一些连续整数代替，这样一个项集i可以表示为(i1,i2…im)，而这里的ij代表了一个项。一个序列s可以表示为s1,s2…sn，这里的sj代表的是一个项集。 两个序列A= a1,a2…an和B= b1,b2…bm，如果存在整数i1i2…in且a1包含于bi1，a2包含于bi2，…，an包含于bin，则称序列a包含于序列b。在一个序列集中如果序列s不包含于任何其它序列中，则称序列s为最大的。 比如序列 (3) (4,5) (8) 包含于序列 (7) (3,8) (9) (4,5,6) (8) ，因为(3)包含于(3,8)，(4,5)包含于(4,5,6)以及(8)包含于(8)。但是序列 (3) (5) 不包含于 (3,5) ，反之亦然。前者表示项3和项5是先后购买的，而后者则表示项3和项5是同时购买的，这就是区别所在。 一个客户所有的事务可以综合的看成是一个序列，每一个事务都由相应的一个项集来表示。事务按交易时间序排列成一个序列。称这样的序列为客户序列。通常，将一个客户的交易按交易时间排序成T1 ，T2 ，……，Tn。Ti中的项集定义