基于FP-Tree的共享前缀频繁项集挖掘算法

在数据挖掘中发现关联规则是一个基本问题,而发现频繁项集是关联规则挖掘中最基本、最重要的问题。提出了基于FP-Tree的共享前缀频繁项集挖掘算法-FP-SPMA算法。构造FP-Tree来压缩事务数据库,通过共享前缀和前瞻剪枝快速减小候选项集,无需递归构造条件模式树,算法性能有明显的提高。

一种基于共享前缀的两级索引结构

大多数倒排索引结构并未提出词汇表的组织形式,传统的基于Hash算法组织的词汇表存在大量碰撞的索引词。本文提出一种基于共享前缀的两级索引结构,通过对汉字、英文、数字进行统一编码,把具有相同首字的索引词映射到一级索引的相同位置;二级索引使用共享前缀树的结构组织索引词,既能通过二分查找快速定位索引文件存储块的位置,又能通过共享前缀的方式减少对相同字的存储,有效地减少了索引文件占用的存储空间。实验结果表明,该结构索引文件与源文档大小的压缩比达到0.59,与顺序索引和Hash索引相比,具有较高的时空效率。

基于前缀共享树的频繁情节挖掘算法

经典的频繁情节挖掘算法NONEPI及其改进算法NONEPI+存在时空复杂度高、"重复计算"等问题,基于最小且非重叠发生的支持度定义,提出一个基于前缀共享树的频繁情节挖掘算法PST_NONEPI,该算法采用深度优先搜索策略,将发现的频繁情节压缩到前缀共享树中,通过动态维护前缀共享树来发现所有的频繁情节。该算法只需扫描事件序列一次,大大提高了频繁情节挖掘的效率。实验证明,PST_NONEPI算法能有效地挖掘频繁情节。

关联规则挖掘在证券业个性化服务中的应用

提出了一种适用于证券业交易数据库挖掘的频繁模式链表关联规则挖掘算法,它采用共享前缀交易项树和频繁模式链表结构,无须产生候选项集,FPL-growth算法通过直接排列出链路中的频项组合,就可得到完整的频繁模式集,且支持多阈值挖掘,挖掘到的关联规则带有时间段属性,特别适用于证券业的个性化信息需求获取。

关联规则挖掘在证券业中的应用

基于证券业急需一种能帮助其提高个性化服务质量的系统,该文提出了一种适用干证券业单交易项交易数据库挖掘的频繁模式链表 关联规则挖掘算法,它采用共享前缀交易项树和频繁模式链表结构,无须产生候选项集,FPL-growth算法通过直接排列出链路中的频项组 合,就可得到完整的频繁模式集,且支持多阈值挖掘,挖掘到的关联规则带有时间段属性,特别适用于证券业的个性化信息需求获取。

一种基于Hadoop的关联规则挖掘算法

传统的并行关联规则算法对每一次迭代都定义一个MapReduce任务,以实现候选项集的生成和计数功能,但多次启动MapReduce任务会带来极大的性能开销。文中定义了一种并行关联规则挖掘算法PST-Apriori,该算法采取分治策略,在每个分布式计算节点定义一个前缀共享树,通过递归调用的方式将事务T生成的候选项集逐层压缩到前缀共享树(PST)中。然后广度遍历PST,逐层将每个节点对应的〈key,value〉作为map函数的输入,并由MapReduce框架自动按照key值进行聚集。最后调用reduce函数对多个任务的处理结果进行汇总,得到满足最小支持度阈值的频繁项集。算法只使用两个MapReduce任务,且PST按照key值排序便于Mapper端的shuffle操作,提高了运行效率。

基于自动机的XML流多查询处理

XML流数据处理在研究领域引起广泛关注,该文针对XML流上的多查询处理提出一种算法,把多个查询合并为一个共享前缀的查询树,应用自动机和运行时栈相结合的方法,单遍扫描XML流处理数据流上的多个查询。该算法采用一种分层栈结构保存查询模式匹配候选集,利用XML节点的区间编码来确定节点之间的关系,返回整条匹配路径。

一种适于XPath查询的自动机最小化算法

近年来,XM L数据流的查询处理引起了国内外学者的广泛兴趣。如何在XM L流中有效地查询大量XPath表达式是当今研究的一个热点问题。先将多个XPath式通过共享前缀处理,构造一个非确定的有穷自动机(NFA)模型,再将其转化为确定的有穷自动机(DFA),以实现状态转移的确定性,然后对DFA进行最小化,提出了一种普遍适用的改进的最小化算法,在执行效率和空间代价方面它都优于一般性算法。

XML关键字检索中Dewey码存储方式的研究

Dewey码是XML关键字检索中采用的重要编码方式。在目前的研究当中,Dewey码通常以字符形式进行存储,这种方式造成Dewey码存储代价过大,并且在LCA求解过程中也必须通过字符比较才能获得Dewey码各层的数值,影响LCA求解效率。提出采用前缀共享和变长整形编码思路的PSVL存储方式,在消除字符比较操作的同时减少了Dewey码集合的存储代价。实验证明利用该存储方式对Dewey码集合进行存储,可以有效地降低其存储代价,并且减少获取Dewey码各层数值这一步骤花费的时间,间接提高了LCA的求解效率。

数字图书馆下的文献阅读智能推荐

数字图书馆以其信息容量大、传输速度快、时空限制少等优势,已成为读者阅读文献的主流平台。如何向读者提供导向性强、个性化好的服务,是数字图书馆向智慧图书馆转变的关键。鉴于此,提出一种文献阅读智能推荐算法。该算法只需单遍扫描文献阅读流,以深度优先搜索策略来挖掘频繁情节,以共享前缀树来存储频繁情节,以情节单调性来压缩搜索空间。实验表明,与经典算法相比,所提算法具有较好的时空性能和较高的挖掘质量,挖掘结果能够揭示读者的阅读习惯和预测读者的阅读倾向,从而有助于数字图书馆提高文献资源的利用率并向读者提供更好的个性化服务。

基于模式匹配的目标轨迹预测方法

本文在目标轨迹预测中采用了数据挖掘的方法,提出了一个具体的基于移动模式匹配的目标轨迹预测算法。该方法通过不断挖掘历史移动轨迹来构造前缀共享树的方法挖掘出频繁移动模式,之后通过模式匹配预测出目标的移动轨迹。仿真结果表明该算法的时间消耗和空间消耗较小,同时具有很高的预测准确性。