【作者】 郝广浩；

【导师】 郑永清；

【作者基本信息】 山东大学 ， 电子商务与信息技术， 2011， 硕士

【摘要】 当今时代是信息的时代是数字化的时代,随着通信、互联网的发展,社会各行各业存储的数据越来越庞大,在这种背景下,一种新的数据形式——数据流引起了计算机从业人员的关注。如何在海洋一样广阔的数据流中准确的挖掘有价值的信息成为了数据挖掘研究工作新的挑战。面向数据流的关联规则挖掘是数据挖掘的新形式,近些年来的研究热点,被广泛的应用于网络通信、设备维护、证券交易等领域,对于社会的生产和日常生活有着重要的意义。数据挖掘工作者对数据流的关联规则挖掘工作展开了大量的相关研究,对数据挖掘的思想、流程、算法提出了许多新的设计。然而这些方法大都把主要的研究工作放在了挖掘的过程、数据处理等方面,忽略了对于关联规则挖掘结果精确度的关注,同时在对挖掘过程的设计中,对于数据准确性的研究也比较有限。数据挖掘的目的是获得可信的、准确的、有价值的信息,由于在数据流环境下的挖掘只能够得到近似的挖掘结果,因此,挖掘结果的精确度将是评价挖掘的关键指标。本文围绕着提高挖掘结果精确度的目的,提出了面向数据流的关联规则挖掘的方法,在数据流的获取、处理以及信息的发现等挖掘流程的设计过程中,从处理细节入手,将提高挖掘精确度的思想贯穿其中。本文对数据流关联规则挖掘的工作主要分为三个部分的研究成果：数据获取部分、数据存储部分和数据挖掘部分,围绕着如何提高挖掘精确度,对每一个部分的设计进行了详细的描述。首先,在数据获取部分提出了使用滑动时间窗口模型获取数据,并按照每个窗口将数据流分割成为事务形式,这个模型既符合了数据流的特点,又满足了频繁项集挖掘对数据的要求。其次,数据存储模型由数据存储结构、数据更新算法和最大误差的选取三部分组成。通过对经典算法FP-growth算法中FP树的改进,本文提出了一个新的数据存储结构FP-Atree,这个存储结构符合了只能一遍读取数据的数据环境要求,节省了数据存储空间,简化了数据逻辑,压缩了存储体积。数据更新算法把整个数据存储时间划分为多个时间框,在时间框结束时对FP-Atree进行剪枝,删除支持度小于最大误差的项集,从而保证了有限的空间资源的到充分的利用,避免了因为数据流的无边界性而导致的存储数据的无限扩张。第三部分为最大误差的选取,研究中使用了多项式近似的策略,发现了最大误差与环境资源参数之间的关系,既有效地控制了空间资源,又尽量避免了有效信息的丢失,为提高挖掘结果精确度提供了保障。数据挖掘模型的主要意义在于提高了挖掘精确度,在这一模型中本文提出了基于滑动时间窗口的新阈值,最小支持度阈值S经过修正,每个项集都有适用于本身的阈值。这个模型保证了所有真实支持度大于S的项集都能成为频繁项集,减少了结果项集中非频繁项集的比例,提高了挖掘结果的精确度。更多还原

【Abstract】 Nowadays, at the digital age, with the development of telecommunication and World Wide Web, the volume of data is increasing extremely. The data stream comes up. Discovering the useful information and knowledge in the data, just like mining the precious in the huge ocean, is a challenge that we face up to. Mining the frequent patterns in the data stream is a new task in recent years, it is meaningful to the social production and our daily life, it can be widely used in telecommunication, facilities maintenance, security exchange and etc.The data mining works and researchers make great effort on the data stream mininig and advance a lot of new design on the mininig procedures and algorithms. However most of the researches only put the attention on the mining process, lack of the work on the mining result. The aim of the data mining is the precise, credible and useful information, and as the reverse of our expect, the result of association rules mining on the data stream can only be approximative. So the precision of the mining result should be the parameter key of the association rules mininig.In the essay, it illustrate a new method on mining frequent patterns in data stream and algorithms ensuring the precise result. It modify the details of the mining method on the obtaining data, data storage and information discovering. Our research consist of three part:obtaining data, data storage and knowledge discovering, it works for ensuring the precision of the mining result on every method detailsFirstly the sliding time windows divide the data stream to itemsets, drop the items which appears more than twice, then sort the itemset as the sequence of the first layer child node in the FP-Atree from the left to right. After that the itemset can be seen as transactions.Secondly the data storage consist of storage structure, data update algorithm and computing the maximum error. Our researcher advanced a new data storage structure named FP-Atree, different the FP-tree, it consist of a prefix tree, without the head-node list and the head-node point. The data update algorithm divide the whole time to time frames, after each frame, the node which support less than the maximum error should be pruned.Finally it proposes the polynomial strategy to estimate the value of the maximum error, and in Chapter 4 the minimum support threshold has been modified. The proper value of the maximum error and modified minimum support threshold are two parameter keys for increasing the precision of the mining result.更多还原