数据流频繁项挖掘及相关性分析算法的研究

发布时间：2018-11-04 11:44

【摘要】：数据流应用最早出现于传统的银行和股票交易等金融领域,后来则出现在天文观测、交通、医疗、地质测量、气象等众多领域。尤其是随着无线通信网(通话记录)和互联网(网络流量监控,点击流)的广泛应用,需要对数据流类型的数据进行分析与挖掘。比如,数据流频繁项技术及相关性分析技术可被应用到智慧医疗和识别可疑洗钱行为的领域中,具有非常重要的应用价值。而且,数据流频繁项挖掘和相关性分析算法是众多数据流挖掘技术的基础,因此具有非常重要的学术研究价值。数据流挖掘的常用技术主要有频繁项(集)挖掘、相关性分析、分类分析、聚类分析、时序模式分析等。一般来说,数据流挖掘算法都试图从两个方面来研究:一是查询响应时间问题,即如何高效实时地处理数据,以匹配数据流高速到达的特性。在技术层面上通过提出新的或者改进已有的高效的数据结构、有效的剪枝策略等来解决。二是压缩存储空间并保证高精度的查询结果。在技术层面上通过构造一个内存占用少、并能提供近似结果的数据结构以存放被压缩的数据流数据。综上分析,本文致力于解决数据流频繁项发现及相关性分析问题中,如何更好的解决以上提出的两大问题(提高查询响应时间和压缩存储数据所花费空间)。在现有的数据流挖掘技术研究基础上,以有效管理海量数据和提高查询效率以及精确度为优化目标,展开一系列能够满足实际应用需要的挖掘技术研究;提出高效的数据流概要结构和挖掘算法。本文研究主要包括以下内容:延迟数据流的频繁项挖掘方法研究:所谓“延迟”即基于时间延迟模型。该模型考虑了不同时刻的数据的重要性不同,即已到达的数据项的重要性随时间逐渐衰减。为了提高查询响应时间,本文研究了一个可以在内存维持的,并能保证高效地更新和检索其中的信息的数据结构,从而提高数据流频繁项挖掘算法的效率。此外,为了压缩存储数据所花费空间,本文还设计了一种新的数据流概要结构,从而提高数据流频繁项挖掘结果的准确度。数据流最热项概念的提出及其查询方法研究:针对不断出现的多样的查询需求,例如,在促销中,商户希望找到巅峰销售记录,以宣传其产品的受欢迎程度,目前已有的数据流挖掘概念并不能适用于这一新的需求。因此,本文研究了一个自适应可变滑动窗口的数据流频率问题——数据流最热项问题。由于无法用现有的挖掘算法来解决数据流最热项问题,因此,本文深入研究了实时挖掘数据流最热项的算法。一是设计一个高效的数据结构来存储已到达的数据项的关键信息,使得可以在其上进行数据流最热项的挖掘,并且可以保证高效地存储、更新和检索其中的信息。二是,在该数据结构的基础上,设计几种剪枝策略以提高实时查询效率。数据流自适应的延迟相关性分析方法研究:已有的延迟关联分析主要集中在两个方面,一是延迟关联被计算在整个数据流上;二是,需要设置一个合适长度的滑动窗口来计算延迟关联性。然而,没有一个最佳的窗口长度适用于所有的场景,因为合适的窗口长度取决于查询、时间、数据和应用领域等因素。因此,本文设计了一种滑动窗口大小可自适应调整的延迟相关性查询。也就是,基于可变的滑动窗口排序目标数据流与给定的查询数据流之间的延迟关联关系。因此,本文开展研究了数据流自适应的延迟相关性分析算法。本文首先研究了数据流中的数据项出现次数问题,也即数据流频繁项挖掘方法的研究;接着将出现次数问题扩展到出现频率的问题,即提出了一种新的数据流挖掘概念-数据流最热项问题及其查询方法的研究;最后本文探究了数据流之间相关性分析的方法,研究了基于可变滑动窗口的延迟相关性分析方法的研究。本文的研究还只是初步进行了尝试和探索,但是仍有许多的研究工作需要进一步深入和开拓。比如研究适应流速率变化的数据流的挖掘问题,利用现有的分布式框架,如Hadoop、Spark等来处理数据流挖掘问题等。
[Abstract]:......
【学位授予单位】：浙江大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：TP311.13

【参考文献】