数据挖掘课件第6章时间序列和序列模式挖掘幻灯片.ppt

序列挖掘—数据源的形式(续) 操作系统及其系统进程调用是评价系统安全性的一个重要方面。通过对正常调用序列的学习可以预测随后发生的系统调用序列、发现异常的调用。因此序列挖掘是从系统调用等操作系统审计数据中发现有用模式的一个理想的技术。表6-3给出了一个系统调用数据表示意，它是利用数据挖掘技术进行操作系统安全性审计的常用数据源。 序列挖掘—数据源的形式(续) 表6-3系统进程调用数据示例 进程号（Pro_id） 调用时间（Call_time） 调用号（Call_id） 744 744 1069 9 1069 744 1069 9 -1 04：01：10：30 04：01：10：31 04：01：10：32 04：01：10：34 04：01：10：35 04：01：10：38 04：01：10：39 04：01：10：40 23 14 4 24 5 81 62 16 表6-4系统调用序列数据表示例 进程号（Pro_id） 调用序列（Call_sequence） 744 1069 9 （23，14，81） （14，24，16） （4，5，62） 序列模式挖掘的一般步骤 序列模式五阶段分别是排序、大项集、转换、序列及选最大阶段。 1. 排序阶段 对数据库进行排序（Sort），结果将原始的数据库转换成序列数据库（比较实际可能需要其他的预处理手段来辅助进行）。如，交易数据库，客户号（Cust_id）和交易时间（trans-time）排序，通过对同一客户的事务进行合并可得对应的序列数据库。 2. 大项集阶段 该阶段要找出所有频繁项集（即大项集）组成的集合L，也同步得到所有大1-序列组成的集合，即{l | l ?L}。表6-2顾客序列数据库中，假设支持数为2，则大项集分别是(30),(40),(70),(40),(70)和(90)。实际操作中，常将大项集映射成连续的整数。上面大项集映射成表6-6对应的整数。映射目的是为处理的方便和高效。 Large Itemsets Mapped To （30） （40） （70） （40，70） （90） 1 2 3 4 5 序列模式挖掘的一般步骤(续) 3. 转换阶段 在寻找序列模式的过程中，要不断进行检测一个给定的大序列集合是否包含于一个客户序列中。 表6-7给出了表6-2数据库经过转换后的数据库。如，在对ID号为2的客户序列进行转换的时候，交易（10，20）被剔除了，因为它并没有包含任何大项集；交易（40，60，70）则被大项集的集合{（40），（70），（40，70）}代替。 4. 序列阶段 利用转换后的数据库寻找频繁的序列，即大序列（Large Sequence）。 5. 选最大阶段 在大序列集中找出最长序列（Maximal Sequences）。 Large Itemsets Mapped To （30） （40） （70） （40，70） （90） 1 2 3 4 5 时间序列及其应用 时间序列预测的常用方法 基于ARMA模型的序列匹配方法 基于离散傅立叶变换的时间序列相似性查找 基于规范变换的查找方法 序列挖掘及其基本方法 AprioriAll 算法 AprioriSome 算法 GSP算法 第六章 时间序列和序列模式挖掘  内容提要 AprioriAll算法 AprioriAll算法源于频繁集算法Apriori，它把Apriori的基本思想扩展到序列挖掘中，也是多遍扫描数据库的算法。 在每一遍扫描中都利用前一遍的大序列来产生候选序列，然后在完成遍历整个数据库后测试它们的支持度。 在第一遍扫描中，利用大项目集阶段的输出来初始化大1-序列的集合。 在每次遍历中，从一个由大序列组成的种子集开始，利用这个种子集，可以产生新的潜在的大序列。 在第一次遍历前，所有在大项集阶段得到的大1-序列组成了种子集。 AprioriAll算法 表6-2顾客序列表示例 1. AprioriAll算法描述 算法6-1 AprioriAll算法 输入：大项集阶段转换后的序列数据库DT 输出：所有最长序列 （1） L1={large 1-sequences}；// 大项集阶段得到的结果 （2） FOR（k=2；Lk-1 ? ?；k++） DO BEGIN （3） Ck=aprioriALL_generate(Lk-1)； // Ck是从Lk-1中产生的新候选者 （4） FOR each customer-sequence c in DT DO //对于在数据库中的每一个顾客序列c （5）