【摘要】 现有数据挖掘算法的缺点是在挖掘大数据时会出现大量候选模式,从而造成可伸缩性瓶颈,个别算法虽然不生成候选模式,但是计算代价高昂,缺乏有效剪裁,运行效率存在瓶颈。为此,提出一个全新的单阶段不生成候选模式的数据挖掘算法,其创新性有3点:一是基于前缀生长的模式枚举和基于效用上限值评估的剪裁策略;二是基于稀疏矩阵和虚拟投影的效用信息表达;三是节省存储空间的深度优先搜索方法。大量实验表明,新算法的时间效率比现有算法高5倍以上,并且内存使用量比现有算法少20%~60%,可伸缩性高。更多还原

【Abstract】 Most of the latest works on utility mining generates a huge number of candidates in dealing with big data,which suffers from the scalability issue. Some work does not generate candidates, but suffers from the efficiency issue due to lack of strong pruning and high computation overhead. A novel algorithm that finds high utility patterns in a single phase without generating candidates was proposed. The novelties lie in a prefix growth strategy with strong pruning, and a sparse matrix based representation of transactions with pseudo projection. The proposed algorithm works in a depth first manner and does not materialize high utility patterns in memory, which further improves the scalability. Extensive experiments on synthetic and real-world data show that the proposed algorithm outperforms the latest works in terms of running time, memory overhead, and scalability.更多还原