·684· 智能系统学报 第13卷 1)创建集合L,设置集合L的最小对比度阈 数据集，记录了两个不同类型的DNA序列。在 值minTopkCR=O; E.Coli数据集中，每个DNA序列前面都用“+”和 2)创建队列，初始化队列queue为空； “-”标记出了序列所属的类别。UI数据集，记录 3)计算正例集D,的字母表Σ，将字母表中的 了超过11000个独立的手写数字。ADLs数据 元素加入到queue中； 集，记录了一段时间内不同的人在自己家中的活 4)创建树的根节点，建立由根节点分别指向 动情况。Question数据集，记录了各种不同的问 字母表中每个元素的指针，令min TopkCR=get- 题，可以将每个问题看作由不同单词组成的序 MinTopkCR (L); 列。前3个数据集来自UCI的机器学习数据集。 5)如果(Sup(e,D,)≤minTopkCR)则从字母表 最后一个数据集是Question的训练数据集。实验 Σ中删除元素e,对Σ中的每一个元素e,把e添加 运行的环境是：Core i.3的处理器，Windows7操作 到队列的第一个序列的末尾，组成新的序列P: 如果Sup(P,D,)≥minTopkCR,则把P加入到 系统，2 GB RAM的计算机上完成。表5中列出了 队列中： 实验中用到的数据集的特征。 如果叫<k,则在集合L寻找P的子序列P; 表5数据集的特征 如果P被找到且P不是相对于P的冗余序 Table 5 The characteristics of the data sets 列，则把P加入集合L,更新minTopkCR,否则把 数据集 类别 DD☒ D P加入集合L,更新min TopkCR; E.Coli E.Coli+E.Coli- 53534106 6)如果☑=k,并且CR(P,D,D-)>minTopkCR UJI Write+Write- 784784101568 则在集合L寻找P的子序列P; ADLs Activity+Activity- 13219 34 如果P被找到，并且P不是相对于P的冗余 Question Question+Question- 151156146307 序列，则用P替换集合L中对比度最小的序列， 更新minTopkCR,否则用P替换集合L中对比度 4.2 实验结果分析 最小的序列更新minTopkCR; 1)实验1（去冗余前后Top-k集合对比实验） 7)重复步骤5)、6)，直到队列为空。 实验1的目标是比较去冗余前后Top-k集合 4实验结果 中序列模式的变化，来验证去冗余算法的有效 性。在该实验中，使用了3组数据来对比去冗余 4.1实验环境 前后Top-k结果集合的不同。每组数据分别找出 本文设计了一系列实验来评估算法的有效 了含有冗余序列的Topk集合和不含冗余序列的 性。算法用C+语言来实现。实验中所用到的数 Top-k集合，并比较其中序列的组成。在实验中， 据集为4组真实数据。这4组数据分别是：E.Coli k值设置为5。实验结果如表6~8所示。 表6去冗余前后Top-k序列模式集合的变化(ADLs数据集) Table 6 The set of Top-k sequential patterns before and after eliminating redundancy(ADLs data set) 冗余Top-k集合 去冗余Topk集合 序列 对比度 序列 对比度 洗澡、吃早餐 1 洗澡、吃早餐 梳妆、洗澡、吃早餐 0.846154 梳妆、洗澡、吃早餐 0.769231 上厕所、梳妆、洗澡 0.769231 睡觉、上厕所、梳妆、洗澡 0.692308 洗澡、吃早餐、休息 0.769231 睡觉、上厕所、梳妆 0.59707 上厕所、梳妆、洗澡、吃早餐 0.769231 梳妆、洗澡 0.56044 通过实验结果可以发现，去冗余Top-k集合 2)实验2（加入剪枝策略前后的对比实验） 中出现了冗余T0p-k集合中没有出现的序列模 实验2的目标是比较算法1与加入剪枝策略 式。同时，去冗余Top-k集合中删去了冗余的序 后算法效率的变化。分别在ADLs数据集和 列模式。因此，本文的算法能够有成效地去除冗 Question数据集上进行对比实验，比较算法1和 余对比序列模式。 算法2运行的时间，来衡量算法的效率。minTopkCR = 0 1）创建集合 L，设置集合 L 的最小对比度阈 值 ； 2）创建队列，初始化队列 queue 为空； 3）计算正例集 D+的字母表 Σ ，将字母表中的 元素加入到 queue 中； 4）创建树的根节点，建立由根节点分别指向 字母表中每个元素的指针，令 min TopkCR = get￾MinTopkCR (L)； Sup(e,D+) ⩽ minTopkCR Σ e Σ e 5）如果 ( ) 则从字母表 中删除元素 ，对 中的每一个元素 ，把 e 添加 到队列的第一个序列的末尾，组成新的序列 P； 如果 Sup(P,D+) ⩾ minTopkCR ，则把 P 加入到 队列中； |L| < k P 如果 ，则在集合 L 寻找 P 的子序列 ′； P ′ P ′ P L minTopkCR 如果 被找到且 P 不是相对于 的冗余序 列，则把 加入集合 ,更 新 ，否则 把 P 加入集合 L，更新 min TopkCR； |L| = k CR(P,D+,D−) > min L P P ′ 6）如果 ，并且 TopkCR， 则在集合 寻找 的子序列 ； P ′ minTopkCR minTopkCR 如果 被找到，并且 P 不是相对于 P'的冗余 序列 ，则用 P 替换集合 L 中对比度最小的序列， 更新 ，否则用 P 替换集合 L 中对比度 最小的序列更新 ； 7）重复步骤 5）、6），直到队列为空。 4 实验结果 4.1 实验环境 本文设计了一系列实验来评估算法的有效 性。算法用 C++语言来实现。实验中所用到的数 据集为 4 组真实数据。这 4 组数据分别是：E.Coli 数据集,记录了两个不同类型的 DNA 序列。在 E.Coli 数据集中，每个 DNA 序列前面都用“+”和 “–”标记出了序列所属的类别。UJI 数据集，记录 了超过 11 000 个独立的手写数字。ADLs 数据 集，记录了一段时间内不同的人在自己家中的活 动情况。Question 数据集，记录了各种不同的问 题，可以将每个问题看作由不同单词组成的序 列。前 3 个数据集来自 UCI 的机器学习数据集。 最后一个数据集是 Question 的训练数据集。实验 运行的环境是：Core i3 的处理器，Windows 7 操作 系统，2GB RAM 的计算机上完成。表 5 中列出了 实验中用到的数据集的特征。 表 5 数据集的特征 Table 5 The characteristics of the data sets 数据集 类别 |D+ | |D– | |Σ| |D| E.Coli E.Coli+E.Coli- 53 53 4 106 UJI Write+Write- 784 784 10 1 568 ADLs Activity+Activity- 13 21 9 34 Question Question+Question- 151 156 146 307 4.2 实验结果分析 1) 实验 1(去冗余前后 Top-k 集合对比实验) 实验 1 的目标是比较去冗余前后 Top-k 集合 中序列模式的变化，来验证去冗余算法的有效 性。在该实验中，使用了 3 组数据来对比去冗余 前后 Top-k 结果集合的不同。每组数据分别找出 了含有冗余序列的 Top-k 集合和不含冗余序列的 Top-k 集合，并比较其中序列的组成。在实验中， k 值设置为 5。实验结果如表 6~8 所示。 通过实验结果可以发现，去冗余 Top-k 集合 中出现了冗余 Top-k 集合中没有出现的序列模 式。同时，去冗余 Top-k 集合中删去了冗余的序 列模式。因此，本文的算法能够有成效地去除冗 余对比序列模式。 2) 实验 2(加入剪枝策略前后的对比实验) 实验 2 的目标是比较算法 1 与加入剪枝策略 后算法效率的变化。分别 在 ADLs 数据集 和 Question 数据集上进行对比实验，比较算法 1 和 算法 2 运行的时间，来衡量算法的效率。 表 6 去冗余前后 Top-k 序列模式集合的变化 (ADLs 数据集) Table 6 The set of Top-k sequential patterns before and after eliminating redundancy(ADLs data set) 冗余 Top-k 集合 去冗余 Top-k 集合 序列 对比度 序列 对比度 洗澡、吃早餐 1 洗澡、吃早餐 1 梳妆、洗澡、吃早餐 0.846 154 梳妆、洗澡、吃早餐 0.769 231 上厕所、梳妆、洗澡 0.769 231 睡觉、上厕所、梳妆、洗澡 0.692 308 洗澡、吃早餐、休息 0.769 231 睡觉、上厕所、梳妆 0.597 07 上厕所、梳妆、洗澡、吃早餐 0.769 231 梳妆、洗澡 0.560 44 ·684· 智 能 系 统 学 报 第 13 卷