不确定数据流中频繁项集挖掘算法的研究

作     者：谢明烨 

作者单位：黑龙江大学 

学位级别：硕士

导师姓名：谭龙

授予年度：2020年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 

主      题：数据挖掘 不确定数据 频繁模式 数据流 

摘      要：现如今的数据中,越来越多的数据以数据流的形态存在,例如金融交易信息数据、网页浏览数据、气象监测数据、电商购物数据以及各类传感器探测数据等。在这庞大的数据流中,相当一部分数据因为数据源更新、环境噪音、数据复写或者冲突以及传输设备故障等原因导致数据的缺失,从而形成了所谓的不确定数据。现有的单一针对确定数据流或者不确定数据库的挖掘算法无法直接应用。因此,设计面向不确定数据流的高效频繁模式的挖掘算法就极为必要了。本文基于现有的频繁模式挖掘算法以及不确定数据流的应用环境,展开了以下工作:(1)提出一种基于列表存储结构的不确定数据流挖掘算法UFS-mine。该领域现有的主流算法几乎均以前缀树结构存贮模式信息,只有数据项相同且概率也相同的节点才能共享分支路径,导致形成大量冗余节点,极大的消耗了内存。而且在整个挖掘过程中,会频繁的对整棵结构树进行遍历,时间开销巨大。为了解决这些问题,在依托滑动窗口模型的条件下,本文提出了基于列表存储结构的不确定数据流挖掘算法UFS-mine,该算法将所有独特的数据项信息均存储在列表中,每个数据项都对应着自己的概率信息以及存在事务的编号,避免产生冗余节点,节省了内存,对于相应模式的期望统计也更加快速,从而大幅度的提高了算法的性能。(2)提出一种加权衰减的不确定数据流挖掘算法DWUFS-mine。在大多数挖掘不确定频繁模式的过程中,通常只是简单将模式包含的元素的概率相乘来计算期望,没有考虑到不同元素的权重问题,随着时间的推移,数据的价值也会逐渐的降低,新鲜的数据比旧有的数据更具有参考和研究价值。因此,本文在UFS-mine算法的基础之上,提出一种加权衰减的不确定数据流挖掘算法DWUFS-mine。该算法能够兼顾数据不确定性和权重属性,并且对于旧的数据,根据预设的衰减因子降低其期望,实验证明该算法能够有效的运用于注重数据权重且对新鲜信息更加敏感的应用场景。