海量数据中基于后缀划分的高效用高占用比项集挖掘算法

海量数据中基于后缀划分的高效用高占用比项集挖掘算法
1.技术领域
2.本发明属于海量数据挖掘与处理技术领域，涉及一种零售商和网络电商交易数据中高效用高占用比项集的挖掘方法。


背景技术：

3.海量数据上的模式（项集）挖掘是当前数据挖掘领域的研究热点之一。现如今，数据挖掘在购物篮分析、市场营销、金融交易和生物分析等领域得到了广泛的应用，日益成为国内外各领域广泛关注的研究热点。
4.频繁项集挖掘（fim）返回数据集中大量且频繁出现的表项集合，从中发现项集之间的关联关系和频繁模式。然而，频繁模式的挖掘仅仅考虑项集在事务中是否出现，忽略了项集在事务中对应的数量及其权重。因此，频繁模式挖掘可能会得到很常见但效用值低的项集，错过了稀有但高利润的项集，往往不具备现实意义。例如，在零售商交易数据集中，牛奶和面包是频繁出现在购物篮中的频繁项集，但其效用值（单位利润）往往比较低；而鱼子酱和香槟是购物篮中罕见的非频繁项集，但其效用值往往很高。因此，fim往往会忽略能带来巨大利润效用的非频繁项集，但这些被忽略的高效用项集往往能给零售商带来巨大利润效用。
5.高效用项集挖掘(huim)是频繁项集挖掘考虑项集权重的一种扩展，在fim的基础上对事务表中的项赋予权值，定义每个项拥有其内部效用（如：商品销售数量）和外部效用（如：利润、重要程度等），项的效用值为内部效用与外部效用的乘积，代表了该模式的总利润或贡献值。huim能发现大型事务或关系数据库中模式之间的关联性与相关性，可为分类设计、交叉营销和顾客购物习惯分析等许多商务决策提供帮助。然而，huim忽略了项集的数量特征，挖掘到的高效用项集可能是偶然出现的特殊情况，因此将其作为销售决策是不合适的。
6.现如今，大多数的研究要么使用频繁程度（如频繁项集挖掘），要么使用效用值（如高效用项集挖掘）作为主要的衡量标准。一方面，单独使用这两种衡量方式都有各自的局限性，频繁程度很高的项集其效用值可能很低，而效用值很高的项集其频繁度往往很低，可能是偶然出现的特例，并不具有实用价值。若将这些项集推荐给用户没有现实意义，甚至可能会造成误导。另一方面，现有算法通常只能对十万条事务的中小规模数据集进行计算，且随着数据量的增大，算法的性能将大大下降。此外，单一考虑效用值并不能体现项集与事务表整体的关系，需要从频繁程度和效用两方面综合考虑项集在支持事务中的占用情况或重要性。


技术实现要素：

7.为了克服现有技术中存在的上述问题，本发明提出海量数据中基于后缀划分的高
效用高占用比项集挖掘算法。
8.本发明解决其技术问题所采用的技术方案是：海量数据中基于后缀划分的高效用高占用比项集挖掘算法，具体包括预处理和项集挖掘两个阶段，所述预处理阶段具体为根据后缀对数据集进行分区，并存储为垂直结构；所述项集挖掘阶段具体过程为：对长度不大于2的项集进行计算，直接计算其效用占用比并判断是否为高效用占用比项集，非高效用占用比项集直接剪枝；对长度大于2的项集，构建一个基于链表的双向栈结构存储分区中的拓展项，利用双向栈中的项构建集合枚举树，在集合枚举树上按照深度优先搜索顺序对项集进行遍历挖掘，根据支持度向下闭合属性、效用占用比向下闭合属性、3-项集完全剪枝策略对项集进行剪枝，并采用项集链接优化策略和剩余tid交叉计数优化策略进行挖掘。
9.上述的海量数据中基于后缀划分的高效用高占用比项集挖掘算法，所述分区处理过程具体为：对给定数据集t进行序列扫描，对数据集t的所有子序列进行划分，具有相同后缀的项集放入同一分区中。
10.上述的海量数据中基于后缀划分的高效用高占用比项集挖掘算法，所述垂直存储过程具体为：在每个分区中，为每个项构建一个垂直格式的效用列表，效用列表按照项对应的支持度降序排列，支持度不小于预先设定的支持度阈值的项及其对应的效用列表被依次读入到内存中。
11.上述的海量数据中基于后缀划分的高效用高占用比项集挖掘算法，所述支持度向下闭合属性具体为：当分区的支持度上界小于预先设定的最小支持度阈值，则该分区无符合支持度阈值的高效用占用比项集，对该分区进行剪枝；当项集的支持度小于预先设定的最小支持度阈值，则该项集及其超集均不满足支持度阈值，对该项集及其超集进行剪枝。
12.上述的海量数据中基于后缀划分的高效用高占用比项集挖掘算法，所述效用占用比向下闭合属性具体为：效用占用比上界的计算公式为：其中，t是包含项集x的一个事务，是项集x在分区中的事务效用值，是x所在的事务t的效用值，是预先设定的最小支持度阈值，n是数据集中事务的数量，是项集x在事务t中的效用占用比，是项集x在事务t中的剩余效用占用比；其中，表示项集x中的第j个项，表示项集x中第j项在事务t中的效用值，是x中最后一个项对应的下标，是x所在的事务t的效用值；
其中，表示事务中的第j个项，表示事务中第j个项的效用值，，是x的最后一个项的下一个项的下标，是x所在的事务t的效用值；当效用占用比上界小于预先设定的效用占用比阈值，则x及其超集都不满足效用占用比阈值，对项集x及其超集进行剪枝；当分区中第一项的效用占用比上界小于预先设定的效用占用比阈值，则该分区无符合效用占用比阈值的高效用占用比项集，对该分区进行剪枝。
13.上述的海量数据中基于后缀划分的高效用高占用比项集挖掘算法，所述基于链表的双向栈结构包括基数序列和操作数序列。
14.上述的海量数据中基于后缀划分的高效用高占用比项集挖掘算法，所述基于链表的双向栈结构存储过程包括：a、分区中的项按支持度降序排列，且载入内存中的每个项都是频繁的；b、分区中的第一个项被存储到基数序列中，后续其他项按顺序存储到操作数序列中；c、先将操作数序列中的项按降序自下而上放入到双向栈结构中，然后将基数序列中的项放入到双向栈结构中；d、至顶向下提取双向栈结构中的项，从双向栈结构输出的序列用于后续项集挖掘过程及剪枝过程中。
15.上述的海量数据中基于后缀划分的高效用高占用比项集挖掘算法，所述基于项集链接优化策略具体为：挖掘一个长度大于3的项集时，将该项集链接到其先前分区中的祖先项集和当前分区中的父项集，得到祖先项集和父项集的支持度信息，祖先项集是频繁项集，则对祖先项集和父项集二者的列表进行交叉计数，得到该项集的支持度并判断是否生成并计算该项集；祖先项集或父项集非频繁，则可以在集合枚举树中对该项集及其超集进行剪枝。
16.上述的海量数据中基于后缀划分的高效用高占用比项集挖掘算法，所述基于剩余tid交叉计数优化策略具体处理过程包括：步骤2.1：初始化和分别指向和的第一个元素，其中是一个指向项集中某个项位置的索引；步骤2.2：对剩余上界进行初始化，，其中n是数据集中事务的数量，是最小支持度阈值，表示项集对应的tid列表的长度，表示项集对应的tid列表的长度，且；步骤2.3：判断的大小，，则不需要进行交叉计数操作，直接对
及其超集进行剪枝；，则进行交叉计数操作；步骤2.4：在进行交叉计数过程中，比较和指向的tid，表示索引指向的tid，表示索引指向的tid：1)，则说明索引指向的tid是和二者交集中的一个元素，于是将该索引指向的公共tid存入中，和分别向后移动一位；2），则ind1向后移动一位；3），则；步骤2.5：重复循环步骤2.4，直到《0或和二者其一指向了集合的末尾，则交叉计数过程结束；然后根据集合的大小判断项集的支持度是否满足阈值，若频繁则继续计算其效用占用比，否则直接对及其超集进行剪枝。
17.本发明的有益效果是：（1）本专利提出了一种新的高效用高占用比项集挖掘算法—基于后缀划分的高效用占用比项集挖掘算法（sho算法：suffix-based high-utility occupancy itemset mining），能在大规模的海量数据上进行有效计算；（2）提出了基于后缀划分的策略，将事务表划分为若干个基于后缀的分区，并进行垂直存储，这些分区彼此互不交叠，且所有分区的并集是整个数据集，每个分区对于分配的内存足够小，从而使分区能够完整地读入内存，项集的支持度和效用占用比可以在某一分区中进行计算，而不需要遍历整个数据集，极大地节省了算法的空间开销和时间开销；（3）提出了项集链接优化策略和剩余tid交叉计数优化策略，能尽可能早地对项集进行剪枝，（4）设计了剪枝策略和效用占用比的上界，使得效用占用比满足向下闭合的属性，从而有效剪枝掉大量无希望的项集，减小了计算开销。
附图说明
18.下面结合附图和实施例对本发明进一步说明。
19.图1为本发明算法流程图；图2为本发明算法预处理阶段和分区读取流程图；图3为本发明实施例中事务表数据库t；图4为本发明实施例中每个项对应的外部效用值；图5为本发明实施例数据集根据后缀划分的结果示意图；图6为本发明实施例垂直存储结构；图7为分区p6构建的基于链表的双向栈结构；图8为分区p5的深度优先增长的枚举树结构；图9为支持度变化对算法性能的影响实验结果图；
图10为效用占用比变化对算法性能的影响实验结果图。
具体实施方式
20.为使本领域技术人员更好的理解本发明的技术方案，下面结合附图和具体实施方式对本发明作详细说明。
21.本实施例公开了一种海量数据中基于后缀划分的高效用高占用比的项集挖掘算法，算法包括如下步骤：步骤1：对数据集进行预处理；步骤2：对每个分区进行剪枝、挖掘，得到最终的高效用高占用比项集；预处理具体为根据后缀将数据集进行分区，并存储为垂直结构，具体流程如图2所示。其中分区处理的具体过程是：对给定的数据集进行序列扫描，假设事务t包含个不同的项，即，其中，是t中的第j个项，是项在事务t中内部效用。子序列将被划分到以为后缀的分区中；当对t的处理结束时，w个子序列将被放入相应的分区。当数据集t上的序列扫描结束后，将得到m个基于后缀的分区，这些分区互不重叠，且它们的并集就是数据集t，从而能在某一确定的后缀分区中计算出项集支持度和效用值，便于对项集进行挖掘。
22.垂直存储的具体过程是：在分区中，为每个项构建一个垂直的效用列表，即项出现的所有tid和其对应的效用值的列表，效用列表将按照其大小降序排列，其大小等于项对应的支持度计数。分区的第一个项具有最大的支持度计数，位于分区中最后位置的项支持度最小。项和其效用列表被依次读入到内存中，直到某个项的支持度计数小于用户指定的支持度阈值，由于项按照支持度降序存储，此时位于当前项之后的项其支持度都小于给定的支持度阈值，支持度小于阈值的项不是高效用占用比项集，故这些项集都将被剪枝。
23.在本实施例中提出一个如图3所示的数据集，并在后续步骤中，以图3所示的数据集为例进行描述，图4为数据集中每个项的外部效用值。根据上述分区过程，将图3中数据集划分为p
1-p7七个分区，如图5所示，并对分区的数据存储为垂直结构，如图6所示，在图6(a)中，每个分区按照垂直格式存储项及其对应的效用列表信息。在分区p1中，第一个条记录是i1={(t1,4), (t2,5), (t3,2), (t4,2),(t6,2), (t9,1), (t
10
,3)}，这说明项i1出现在数据集的7个事务中，其中(t1,4)表示项i1在事务t1中的内部效用值为4，即iu(i1, t1)=4；如图6(b)所示，每个分区中的效用列表按支持度计数降序排列，例如在分区p3中，项i1、i2、i3的支持度计数分别为4、3、5，根据支持度排序后第一条记录为utility-list(i3)={ (t3,1), (t4,3), (t5,5), (t6,3), (t9,2)}，其后是项i1，项i2位于最后。
24.项集挖掘阶段的具体步骤如图1所示，需要注意的是，在图1中x1、x2、x3是指当前遍历的项集。在步骤2项集挖掘阶段，依次将每个分区从磁盘读入内存，首先分别对1-项集（图1中对应的x1）和2-项集（图1中对应的x2）进行计算，判断其是否为高效用高占用比项集；对长度大于2的项集（图1中对应的x3）构建一个基于链表的双向栈结构存储分区中的拓展项，利用双向栈中的项构建集合枚举树，在集合枚举树上按照深度优先搜索顺序对项集进行遍历挖掘，根据支持度向下闭合属性、效用占用比向下闭合属性、3-项集完全剪枝策略对项集
进行剪枝，并采用项集链接优化策略和剩余tid交叉计数优化策略进行挖掘。
25.双向栈结构（如图7所示）由基数序列和操作数序列两部分组成，首先，分区中的项按支持度降序排列，且载入内存中的每个项都是频繁的。分区中的第一个项将被存储到左侧的基数顺序中，后续其他的1-项集，将按顺序放入右侧的操作数序列中，在操作数序列中，支持度最低的项存储在尾部，而支持最高的项存储在头部；然后，先将操作数序列中的项放入双向栈结构中，再将基数顺序中的项放入双向栈结构中；最后，至顶向下提取双向栈结构中的项，从双向栈结构输出的序列可用于生成集合枚举树和后续的项集挖掘过程中。
26.在本实施例中，对图5中的p6分区构建基于链表的双向栈结构如图7所示，中含有五个不同的项，，中的支持度小于预先设定的支持度阈值，所以不会被读入内存因此不会出现在中，由于项根据其支持降序排列，即，项的支持度计数最大，故将其放入左侧的基数序列中，项、、、将被依次放入右侧的操作数序列中；随后将操作数序列中的项依次输出；位于操作数序列的头部，故先将输出到双向栈结构中，随后输出、和。然后再输出基数序列中的并放入双向栈结构的顶部，从而得到该分区的双向栈结构。在构造集合枚举树时，双向栈结构中的项将以的顺序输出，该双向栈结构项列表将用于在此分区中生成具有相同后缀的项集。双向栈结构可在逻辑上根据使用顺序组织分区中包含的项，通过利用双向栈结构能有效地减少搜索空间，提高算法效率。
27.对具体剪枝策略及优化策略进行详细解释：1、支持度的向下闭合属性根据数据集分区及垂直存储的结果，分区中的第一个项是后缀项，分区中的最大支持度计数上界可直接通过后缀项获得，若最大支持度上界小于预先设定的最小支持度阈值，则此分区中不可能生成高效用高占用比项集，因此可以直接跳过该分区；当项集的支持度小于预先设定的最小支持度阈值，则该项集及其超集均不满足支持度阈值，对该项集及其超集进行剪枝。
28.2、效用占用比的向下闭合属性效用占用比上界的计算公式为：其中，t是包含项集x的一个事务，是项集x在分区中的事务效用值，是事务t的效用值，是预先设定的最小支持度阈值，n是数据
集中事务的数量，是项集x在事务t中的效用占用比，是项集x在t中的剩余效用占用比；其中，表示项集x中的第j个项，表示在事务t中项集x中第j项的效用值，是x的最后一个项的下标，是x所在的事务t的效用值；其中，表示事务中的第j个项，表示事务中第j项的效用值，，是x的最后一个项的下一项的下标，是x所在的事务t的效用值；当效用占用比上界小于预先设定的效用占用比阈值，则x及其超集都不满足效用占用比阈值，对项集x及其超集进行剪枝；当分区中第一项的效用占用比上界小于预先设定的效用占用比阈值，则该分区无符合效用占用比阈值的高效用占用比项集，对该分区进行剪枝。
29.3、3-项集完全剪枝策略在以项i为后缀项的分区pi中，是一个包含m个项的项列表。首先，通过简单的序列扫描挖掘所有的1-项集和2-项集，由于得到1-项集和2-项集都是频繁的，因此可直接计算其效用占用比并判断是否为高效用占用比项集；接下来，通过结合两个2-项集来生成一个3-项集，但在生成3-项集前可判断它所有2-子集是否频繁，若不是可直接跳过该候选集，而不需要进行交叉计数和计算其支持度和效用占用比；最后，结合深度优先的集合枚举树对运行实例中的长度为3及其以上的项集进行挖掘。假设在构建集合枚举树时支持度阈值为0，即分区中的所有1-项集都频繁，1-项集都能被读入内存，深度优先增长的枚举树结构如图8所示。图8中包含p1到p5五个分区的信息。通过对项集{i
2, i3}和{i
2, i4}进行交叉计数生成{i
2, i
3, i4}，其中项集{i
2, i4}和{i
3, i4}已在当前分区p4中计算过，项集{i
2, i3}已在分区p3中计算过，因此可利用支持度向下闭合的属性对3-项集{i
2, i
3, i4}进行完全剪枝。若其中存在任意一个2-子集为非频繁项集，则不需要生成{i
2, i
3, i4}，避免了资源浪费。
30.通过使用集合枚举树对3-候选项集进行剪枝，能大大减少交叉计数的计算开销，并跳过许多候选项集，从而缩短了项集挖掘的时间开销。3-项集的完全剪枝策略不仅可以减少搜索空间，而且可以提高算法的效率。
31.4.项集链接优化策略具体为：当项集的长度大于2时，按深度优先搜索（dfs）顺序挖掘项集，尽管设计的3-项集完全剪枝策略可以对3-项集进行有效剪枝，然而当集合枚举树的层数增加时，其搜索空间仍然非常庞大。因此，提出了项集链接剪枝优化策略（li策略）对长度大于3的项集进
行剪枝。
32.祖先项集：假设x是一个长度大于3的项集，，是项集x中的最后一个项。项集x的祖先项集。
33.父项集：假设x是存储在集合枚举树中的一个项集，存储在x的父节点上的项集被称为x的父项集。
34.在集合枚举树上进行深度优先搜索的过程中，项集x由父项集生成，当确定是否生成一个k-项集x时(k》3)，能很容易地得到x的父项集。如果项集x的父项集不是频繁的，则x及其超集将直接被剪枝。反之，若项集x是频繁的，可以得到项集x的父项集的效用列表，并对项集x的父项集和祖先项集的集合进行交叉计数，然后计算并得到项集x的效用列表从而确定项集x是否为高效用占用比项集。在运行的示例中，项集是由父项集生成的，在挖掘项集时，通过删除x的最后一个元素将x链接到，且该项集在p3中已经进行了计算，根据是否频繁可预判是否需要生成项集，若频繁，则对和的集合进行交叉计数，从而得到的支持度并确定是否需要生成项集。
35.本优化策略主要思想是将项集与其两个子集联系起来。通过删除最后一项，在逻辑上将项集连接到它的祖先项集。挖掘一个长度大于3的项集时，将该项集链接到其先前分区中的祖先项集和当前分区中的父项集，得到祖先项集和父项集的支持度信息，祖先项集是频繁项集，则对祖先项集和父项集二者的列表进行交叉计数，得到该项集的支持度并判断是否生成并计算该项集；祖先项集或父项集非频繁，则可以在集合枚举树中对该项集及其超集进行剪枝。
36.5.剩余上界的交叉计数策略基于剩余tid交叉计数优化策略具体处理过程包括：步骤2.1：初始化和分别指向和的第一个元素，其中是一个指向项集中某个项位置的索引；步骤2.2：对剩余上界进行初始化，，其中n是数据集中事务的数量，是最小支持度阈值，表示项集对应的tid列表的长度，表示项集对应的tid列表的长度，且；
步骤2.3：判断的大小，，则不需要进行交叉计数操作，直接对及其超集进行剪枝；，则进行交叉计数操作；步骤2.4：在进行交叉计数过程中，比较和指向的tid，表示索引指向的tid，表示索引指向的tid：1)，则说明索引指向的tid是和二者交集中的一个元素，于是将该索引指向的公共tid存入中，和分别向后移动一位；2），则ind1向后移动一位；3），则；步骤2.5：重复循环步骤2.4，直到《0或和二者其一指向了集合的末尾，则交叉计数过程结束；然后根据集合的大小判断项集的支持度是否满足阈值，若频繁则继续计算其效用占用比，否则直接对及其超集进行剪枝。
37.在本实施例中，给定一个项集x，通过在x中分别添加两个不同的项a和b，可以得到x的1-拓展项集和。同理，通过将a和b同时添加到x得到x的2-扩展项集。θ(x)是项集x的剩余上界。本实施例中定义和分别为和对应的tid列表，||和||分别为和对应的tid列表的长度，且||||，是一个指向项集中项位置的索引。在分区中，若项集x是1-项集，则和是2-项集，当前生成的为3-项集。2-项集的集合可通过直接读取支持度较小的项的集合作为2-项集的集合。例如，在访问分区p3时，项集的集合可通过直接访问项所对应的集合得到。
38.当新生成的项集长度大于2时，则利用对交叉计数操作进行优化。假设给定最小支持度计数阈值为4，，，则剩余优化策略的处理过程如下：在本实施例中，交叉计数过程中，首先初始化和分别指向和的第一个元素，，；接下来，对剩余上界进行初始化，，需要进行交叉计数
操作。在第一轮比较中，，，，此时，并将向后移动一位。在第二轮比较中，tid(，然后将存入项集的集合，并将和分别向后移动一位。在第三轮比较中，，，，此时，再将向后移动一位。在第四轮比较中，，，，将向后移动一位。在第五轮比较中，，，，此时。由于故停止交叉计数过程。
39.综上所述，引入剩余上界可以评估两个集合交叉求并集的结果，能尽早对无用的项集停止计算，尽早舍弃无用的项集。当预先设定的支持度阈值越大，则该优化策略跳过的计算步骤越多，优化效果越好。
40.为了验证本发明算法（sho算法）的性能，通过java（open jdk-15.0.2-1）进行实验。实验环境为dell vostro 5880 intel(r) core(tm) i7-10700 cpu @ 2.90ghz 2.90 ghz(8 cores) 16g内存 64bit windows10。数据集所使用的具体参数设置见下表。parameterusedvaluesupportthresholdinpercentage(%)(syn)0.3~0.9supportthresholdinpercentage(%)(rea)0.1~0.22utility-occupancythresholdinpercentage(%)(syn)5~60utility-occupancythresholdinpercentage(%)(rea)10~80transactionnumber(106)(syn)0.1~100numberofitems(syn)500~4000averagetransactionwidth...5~20
41.在实验中，将从预先设定的支持度阈值（min_sup）、预先设定的效用占用比阈值（min_uo）两个方面对本发明基于后缀划分的高效用高占用比项集挖掘算法（sho算法）性能进行测试，并与当前最先进的huopm算法和ba算法进行比较。
42.为了研究支持度阈值对算法的影响，本实验使用三个不同类型的数据集，其中包含一个真实数据集（retail），和两个合成数据集（t100ki1kd5和t100ki1kd10）。对于变化的支持度阈值（min_sup）分别对比huopm、ba以及sho算法的性能，其实验结果如图9所示。
43.由图9可以看出，随着支持度阈值的升高，三组实验的运行时间均呈总体下降的趋势，其中ba算法与huopm算法的运行时间较为接近。图9(a)中，给定数据集n=100k，d=1000，w=10，其中，n表示数据集中事务的数量，d表示数据集中项的数量，w表示平均事务长度，设置效用占用比阈值min_uo=0.3，当支持度阈值min_sup为0.3%时，huopm算法的运行时间是sho算法的64.9倍，ba算法的运行时间是sho算法的56.8倍；随着支持度阈值min_sup的增加，当支持度阈值min_sup为0.6%时，huopm算法的运行时间是sho算法的328.2倍，ba算法的运行时间是sho的189倍。这充分说明在真实数据集和以上两个合成数据集上，sho算法的性能明显优于huopm和ba。
44.在图9(b)中，给定数据集n=100k，d=1000，w=5，设置效用占用比阈值min_uo=0.2，
分别相比于huopm算法和ba算法。sho算法在支持度阈值min_sup=0.9%时优势最明显，为huopm算法的15.7倍，在支持度阈值min_sup=0.3%时为ba算法的6.1倍。
45.在图9(c)的真实数据集retail中，给定效用占用比阈值min_uo=0.1，sho算法的性能更为稳定，当支持度很小时其运行时间不会受太大影响。
46.为了研究效用占用比对阈值算法的影响，本实验使用真实数据集（retail）和两个合成数据集（t100ki1kd5和t100ki1kd10）进行实验。给定支持度阈值min_sup=0.5%，对于变化的效用占用比（min_uo）分别对比huopm、ba以及sho算法的性能，其实验结果如图10所示。
47.在图10(a)中，给定数据集n=100k，d=1000，w=10，其中，n表示数据集中事务的数量，d表示数据集中项的数量，w表示平均事务长度，设置支持度阈值min_sup=0.5%，在各组阈值中的最佳情况下，sho算法比huopm算法快约540.3倍，sho算法比ba算法快约240.2倍。
48.在图10(b)中，给定数据集n=100k，d=1000，w=5，其中，n表示数据集中事务的数量，d表示数据集中项的数量，w表示平均事务长度，设置支持度阈值min_sup=0.5%，sho算法平均比huopm算法快约129.5倍，sho算法平均比ba算法快约81.5倍。
49.在图10(c)中，采用真实的里零售商数据集进行测试。给定支持度阈值min_sup=0.16%，随着效用占用比阈值min_uo的增加三种算法的运行时显示出总体下降趋势，且当效用占用比阈值min_uo较大时，sho的性能较好。
50.一方面，随着效用占用比阈值min_uo升高，挖掘时间是波动减小的；另一方面，效用占用比阈值min_uo变化对于挖掘时间的影响远小于支持度阈值min_sup对挖掘时间的影响，其原因是效用占用比是一个更为全面的事务特征属性，能客观反应项集在整个数据集中的占用情况，因此在不同数据集中计算得到的高效用占用比模式相比于频繁模式更能反应数据集的整体特性。
51.以上实施例仅为本发明的示例性实施例，不用于限制本发明，本发明的保护范围由权利要求书限定。本领域技术人员可以在本发明的实质和保护范围内，对本发明做出各种修改或等同替换，这种修改或等同替换也应视为落在本发明的保护范围内。