基于滑动窗口的数据流高效用模糊项集挖掘_单芝慧_.pdf

第 卷第 期 年 月南京师大学报（自然科学版）（）.，收稿日期：基金项目：国家自然科学基金项目（、）、宁夏自然科学基金项目（）通讯作者：韩萌，博士，教授，研究方向：数据挖掘：基于滑动窗口的数据流高效用模糊项集挖掘单芝慧，韩 萌，韩 强（北方民族大学计算机科学与工程学院，宁夏 银川）（北方民族大学图像图形智能处理国家民委重点实验室，宁夏 银川）摘要 高效用项集挖掘可以提供有趣的结果集，但并不能提供单个项的数量，因此，本文提出了高效用模糊项集 但是，现实世界的数据是不断出现的，需要实时处理新到来的数据 为解决当前高效用模糊项集不能处理数据流的问题，又提出了模糊效用列表（，）结构用于存储当前窗口中项的批次号、项在事务中的事务标识符、项的模糊效用以及项的剩余模糊效用，该结构能有效的对批次进行插入和删除操作 最后，基于 提出了数据流高效用模糊项集挖掘算法 对真实数据集和合成数据集进行了广泛的实验，结果证实了算法的效率及可行性关键词 数据流挖掘，滑动窗口，高效用项集挖掘，模糊效用，效用列表中图分类号 文献标志码 文章编号（），（，）（，）：（），（），：，高效用项集挖掘（，）是数据挖掘领域中一个热点的研究课题 发现数据集中具有高利润的项集组合，即高效用项集（，）之后，又不断提出了 的扩展项集，如闭合（，），高平均效用项集（，）等在不同类型数据集上也有相应的模式挖掘，如序列数据集上的序列项集挖掘，空间数据集上的空间高效用项集挖掘等但这些算法仅提供项集，并未提供项集中单个项的数量信息，不利于用户制定更精准的决策策略 为了同时考虑高效用的项集及项集中单个项的数量信息，研究者提出了高效用定量项集（，）挖掘算法，但其结果集存在冗余问题 等还提出了模糊项集挖掘，将模糊集理论与效用挖掘结合，从定量数据集中挖掘高效用模糊项集（，）等还定义了一个模糊效用函数来评估数据集中项目的模糊效用，将项目的数量信息转化为模糊域 例如，一个量化事务单芝慧，等：基于滑动窗口的数据流高效用模糊项集挖掘图 隶属度函数.（，），（，），（，），其中符号和数字分别代表购买的物品及其购买数量 假设三个物品为如图 所示的隶属度函数，将项的数量信息转化为三个模糊区域：、和 （，）中的 可以转化为占比 的 和 的 量化事务（，），（，），（，）可以转化为（，），（，），（，），然后根据相关定义计算模糊项集的效用，挖掘 使用 不但可以给用户提供高效用的项集，而且可以说明不同项目如何在产品组合中获得合适的产品推广数量，为用户提供更详细的信息随着大数据时代的到来，每时每刻都有新数据在产生，如何高效的处理新产生的数据获取更详细的信息具有一定的研究意义 研究者提出了在数据流上挖掘 及其扩展模式，但都是提供高效用的项集并不提供项集中单个项的数量信息 为了获取数据流上更详细的数据信息，本文提出了基于滑动窗口的数据流 挖掘算法 具体来说，本文的主要贡献包括 个方面：（）提出了模糊效用列表（，）结构存储项的模糊效用信息，该结构能够有效的插入和删除批次中项的模糊效用信息；（）基于 提出了基于滑动窗口模型的数据流 挖掘算法（，）与（，）；（）为了评估提出的算法，在真实数据集与合成数据集上进行了广泛的实验 实验结果表明，提出的算法能够有效挖掘数据流 相关工作由于 只提供产品组合的各个项，而不包含单个项的数量信息，故 等提出了模糊效用挖掘，定义了模糊效用函数，通过其隶属度函数中相应的语言区域值和度值来评估项的模糊效用 之后，等提出了一种两阶段模糊效用挖掘算法（，），使用模糊最小算子来评估项集的模糊效用 但该算法使用两阶段算法，需要产生大量的没有希望的候选项集，消耗时间 等进一步提出了渐进式数据缩减模糊效用挖掘算法（，），该算法运行时间优于 等提出了一阶段时间模糊效用挖掘算法，这种算法可以找到所有高时间模糊效用项集，能够以更少的内存和更快的执行速度获得良好的性能 研究者还将遗传算法、进化算法等群智能优化算法与 相结合，改善算法性能 但是当前的 挖掘算法仅适用于静态数据，当新数据插入时，需要重新扫描整个数据集，极其耗时在现实生活中，数据是不断产生的，及时处理新产生的数据是很必要的 宋威等提出了基于事务型滑动窗口的数据流高效用项集挖掘算法（，），使用二进制向量表示数据，基于高事务加权效用项集树对候选项集搜索空间剪枝 等提出了一种基于加权滑动窗口模型的 一阶段算法 但该算法产生了大量错误的候选项集，消耗了大量的内存 等提出了一阶段算法（，）挖掘数据流上的高效用项集，该算法使用投影数据库方法和滑动窗口技术挖掘，具有较好的性能 研究者还提出了在数据流上挖掘 高效用项集和闭合高效用项集 但是当前数据流上的算法仅能挖掘 及其扩展模式，并不能提供项集中单个项的数量信息 为了处理数据流上的，本文提出了基于滑动窗口的 挖掘算法 问题定义本节描述了从定量数据集中挖掘 的相关定义，为一组具有 个项的集合，是一组数据库事务，其中（），（），（），（），（），是事务 中物品 的购买数量 数量信息由隶属度函数转化为模糊域 项目 的第 个模糊区域，表示为模糊项目（），由模糊隶属函数（）表示，其中，并且 是项目 的模糊区域最大值（用户定义）南京师大学报（自然科学版）第 卷第 期（年）定义 模糊度 事务 中（）的模糊项（）的模糊度定义如下：（）（）（）（）（）（）图 数据流示例数据.表 外部效用表 项外部效用值 例如，在图 与表 中的数据流示例中，通过图 所示的隶属度函数将项的数量转化为模糊域 在事务 中项 的数量为，即（），转化为（）与（）分别是和 定义 加权外部效用 模糊项（）的加权外部效用定义为项的外部效用与项所在模糊域的数量的乘积，表示为（）（），（）（）例如，在事务 中项的加权外部效用为项 的外部效用 与对应数量 的乘积，即（）定义 模糊项的效用 模糊项的效用定义为模糊项的模糊度与项的外部加权效用的乘积，即（）（）（）（）例如，在事务 中的效用为的模糊度 与其加权外部效用 的乘积，即（）（）（）定义 模糊项集在窗口中的效用 窗口 中模糊项集 的效用值为该项集在事务中的效用和，记为（），表示为（）（）（）（）（），其中（），（）例如，在窗口 中项集（，）的模糊效用为（，）在事务、的效用和，可以表示为（，）（）（）（）（）（）（）定义 窗口 的效用 给定窗口 的效用为窗口中所有不同模糊项的效用之和，记为（），表示为（）（）例如，窗口 的模糊效用为（）（）（）（）（）（）（）定义 高效用模糊项集 若模糊项集 的效用大于用户定义的最小效用阈值，则认为模糊项集 是，即（）（），其中（）是窗口 中项集 的效用，（）是当前窗口的效用，是用户定义的最小效用阈值定义 事务最大效用 事务 的事务最大效用，记为（），是事务 中不同项的模糊度中效用最大的项的和，即（）（）（）（）（）例如，事务 的事务最大效用为项 所在模糊度的效用最大值 与 所在模糊度的效用最大值 的效用之和 即（）（），（）（），（）定义 模糊项集的事务加权最大效用 模糊项集 的事务加权最大效用，记为（），是所有包含模糊项集 的事务的最大效用的和，即（）（）（）例如，项集（，）的事务最大效用为（，）（）（）（）算法介绍本节提出了模糊效用列表 结构存储模糊项的效用信息，并基于此结构提出了 与 算法来挖掘 本节先介绍了 结构，然后介绍了提出的算法 模糊效用列表定义 模糊项集 之后的模糊项 给定一个模糊项集 和一个事务，在事务 中项集 之后且单芝慧，等：基于滑动窗口的数据流高效用模糊项集挖掘与模糊项集 中的项不同的模糊项 定义为 定义 模糊剩余效用 模糊项集 的剩余效用定义为（，），是根据对事务排序后，项集 之后的模糊项 的模糊效用和，表示为（，）（，）的构造需要扫描两次窗口中的事务 在第一次扫描中，将项的数量信息通过隶属度函数转化为模糊域，然后计算项目的，并根据 对模糊项进行排序 在第二次扫描期间，创建每个模糊项的 存储当前窗口中模糊项的效用信息，该结构存储项的批次号以及一个包含、元组的条目 存储包含项集的事务标识符，是模糊项集的效用，是模糊项集的剩余模糊效用当新一批事务到达时，新事务中模糊项的效用信息会存储到 中 当到来的批次数量大于窗口大小时将移除最旧的一批事务，插入新一批的事务 数据结构的优点是可以快速执行批次的插入和删除 例如，在图 中第一个滑动窗口 的模糊项（）的 如图 所示，当新的批次加入后，更新后项（）的 分别如图 所示（）（）图 项 的.（），（）图 项集（），（）的.（），（）由两个模糊项组成的模糊项集的 是通过两个模糊项的 中的 相交来创建的 例如，分别从（）和（）的 构造项集（），（）的 （）和（）的 具有共同的批次 和 在 中（）和（）在 和 中同时出现，在 中（）和（）在 同时出现 项集（），（）的 如图 所示 算法在本节中提出了 算法挖掘数据流 算法将输入 个参数：（）数据流事务数据，（）利润数据集，（）窗口大小，（）批次大小，（）用户定义的最小效用阈值算法 算法执行结束将返回 对于给定的数据流，读取数据流中的信息，将批次中的事务加入到滑动窗口当中，当加入的批次数目大于等于窗口大小时，处理当前窗口中的数据 当有新的批次加入时，删除窗口中最旧批次的信息，即旧批次中所包含事务的模糊项的效用信息，然后将新批次中模糊项的效用信息更新到窗口中，并更新批次中的 及效用列表中的信息（算法 的行）对于当前窗口中的事务，先进行第一次数据扫描，通过隶属度函数将项的数量信息转化为模糊域，并计算单个模糊项的；然后进行第二次数据扫描，构建单个模糊项的 与估计模糊效用共现结构（，），该结构改进了 中的（，）结构（算法 的行）然后调用挖掘算法，挖掘窗口中的（算法 的?I1行）算法 输入：；输出：；南京师大学报（自然科学版）第 卷第 期（年）?I1（，）挖掘过程将输入 个参数：（）前缀模糊项集，（）用于扩展模糊项集 的集合，（）模糊效用列表，（）估计模糊效用共现结构，（）用户定义的最小效用阈值 算法 显示了 的伪代码 中的每个模糊项集 的模糊效用大于等于，则 及其相关的扩展为（算法 的行）若 的模糊效用小于，进一步判断 的模糊效用与剩余模糊效用和是否大于等于，若大于等于则可以对 进一步扩展，否则对其剪枝 使用 消除低效用扩展，对高效用的扩展 构造其，项集 的所有 扩展的 进行递归处理（算法 的?I4行）然后进行递归挖掘操作，直至挖掘出当前窗口中的全部（算法 的?I4行）算法 输入：；：；输出：；（）（）（）；（，）；（，）；?I1 ；?I2?I3?I4 （，）；?I5?I6 算法 算法对窗口中重复批次的事务中项的 进行了重用，使用了上一个窗口构建的项的模糊效用信息 但是当新的批次插入后，模糊项的剩余效用信息及 会产生一定的变化，造成 排序后，中的模糊剩余效用值不准确，使得挖掘算法性能降低 为了提高挖掘算法的性能，本文提出了 算法，当新批次插入时，删除旧批次，插入新批次，不重用重复批次的，每个窗口的 都从头开始构建，算法的其它过程与 相同 相比 会产生更多的连接操作，降低了算法性能 在第 部分对两个算法的性能进行了对比 复杂度分析算法的时间复杂度主要包括 的构造与更新和挖掘过程 令 表示窗口中不同项的数量，表示当前窗口中的事务数 算法先进行第一次数据集扫描，将项的数量信息转化为模糊域所需时间（），转化后每个项最多都包含了 个模糊域用于组合产生，同时计算项的 需要时间为（），然后进行第二次数据集扫描创建 与，需要根据 对项进行排序，需要时间为（）；创建 需要检查事务中的共现所需时间为（）挖掘过程包括比较两个（）项集与一个（）项集的 产生 项集，其时间复杂度为（）（）令经过剪枝策略之后生成的项集数量为，构造效用列表的总时间复杂度为（），则总的时间复杂度为（）（）与 的区别在于当有新的批次加入到窗口中，单芝慧，等：基于滑动窗口的数据流高效用模糊项集挖掘 会根据批次号删除旧事务的效用信息，构建新事务的，令新加入的事务数为，需要扫描处理的事务数为 而 需要处理的事务数量为 此外，由于排序结果的差异