稀疏数据频繁项集挖掘算法研究综述

频繁项集挖掘FIM是最重要的数据挖掘任务之一,被挖掘数据集的特征对FIM算法的性能有着显著影响。在大数据时代,稀疏是大数据的典型特征之一,对传统FIM算法的性能带来严峻挑战。针对在稀疏数据中如何高效进行FIM的问题,从稀疏数据的特征出发,分析了稀疏数据对3种类型FIM算法性能的主要影响,对已经提出的稀疏数据FIM算法进行了综述,对算法中采用的优化策略进行了讨论,最后通过实验对代表性的稀疏数据FIM算法进行了性能分析。实验结果表明,采用伪构造策略的模式增长算法最适合用于稀疏数据的FIM,在运算时间和存储空间上,相比其他算法该算法具有较大的优势。     

基于矩阵的数据流Top-k频繁项集挖掘算法

传统的数据挖掘算法在挖掘频繁项集时会产生大量的冗余项集,影响挖掘效率。为此,提出一种基于矩阵的数据流Top-k频繁项集挖掘算法。引入2个0-1矩阵,即事务矩阵和二项集矩阵。采用事务矩阵表示滑动窗口模型中的事务列表,通过计算每行的支持度得到二项集矩阵。利用二项集矩阵得到候选项集,将事务矩阵中对应的行做逻辑与运算,计算出候选项集的支持度,从而得到Top-k频繁项集。把挖掘的结果存入数据字典中,当用户查询时,能够按支持度降序输出Top-k频繁项集。实验结果表明,该算法在挖掘过程中能避免冗余项集的产生,在保证正确率的前提下具有较高的时间效率。     

一种基于矩阵的动态频繁项集挖掘算法

频繁项集的生成是关联规则挖掘中的关键问题,提出了一种基于上三角项集矩阵的动态频繁项集挖掘算法。当事务数据库和最小支持度发生变化时,本算法只需重新遍历一次上三角项集矩阵,即可得到新的频繁项集。与传统的频繁项集挖掘算法相比,在执行效率上有显著提高。     

一种混合型的增量数据关联规则挖掘算法

在数据库中增加数据且调整最小支持度时,数据库中关联规则会发生变化,为从数据量和最小支持度同时发生变化的数据库中快速获取频繁项集,发现变化后的关联规则,通过对FIM和AIUA算法进行分析,提出一种结合两种算法优点的增量数据关联规则挖掘My_FIM_AIUA算法,该算法能减少数据库扫描次数,减少候选项集数量。通过实验表明My_FIM_AIUA算法能在数据量和最小支持度同时变化时快速找到频繁项集,提高挖掘增量数据关联规则的速度。     

一种混合型的增量数据关联规则挖掘算法

在数据库中增加数据且调整最小支持度时,数据库中关联规则会发生变化,为从数据量和最小支持度同时发生变化的数据库中快速获取频繁项集,发现变化后的关联规则,通过对FIM和AIUA算法进行分析,提出一种结合两种算法优点的增量数据关联规则挖掘My_FIM_AIUA算法,该算法能减少数据库扫描次数,减少候选项集数量。通过实验表明My_FIM_AIUA算法能在数据量和最小支持度同时变化时快速找到频繁项集,提高挖掘增量数据关联规则的速度。     

基于倒排索引位运算的深度优先频繁项集挖掘

频繁项集挖掘是关联规则挖掘中的关键任务,非常耗费时间.为提高频繁项集的产生效率,提出一种基于倒排索引位运算的深度优先频繁项集挖掘算法(DF-FIMBII).该算法以二进制数组存储项目到事务的倒排索引,通过位运算计算两个项目的支持计数,并采用深度优先搜索策略递归地挖掘不同的k-频繁项集.在chess、mushroom、pumb_star、T40I10D100K等数据集上,对DF-FIMBII、Apriori、ECLAT、BitTableFI、Index-BitTableFI等算法进行了实验比较.实验结果表明,在数据规模不是非常巨大和支持度较小的情况下,无论数据集的稠密程度如何,DF-FIMBII均具有较好的时间优越性.     

一种基于FP-Growth的频繁项目集并行挖掘算法

FP-Growth算法是基于FP树挖掘频繁项目集的经典算法,为提高FP-Growth算法挖掘大规模数据频繁项目集的效率,提出了一种基于FP-Growth的频繁项目集并行挖掘算法FPPM。该算法基于Map/Reduce并行模型,在每个计算节点上首先构造局部频繁模式树,并对之进行挖掘得到局部频繁项目集,然后合并局部频繁项目集以得到全局频繁项集,由于此时得到的结果并不完备,所以对合并后未达到最小支持度阈值的项目集,重新计算其支持数。介绍了FPPM算法的设计思想,测试了其性能。实验结果表明FPPM算法具有较好的可扩展性。     

N个最频繁项集挖掘算法

频繁项集挖掘算法的计算复杂性和生成的频繁项集数量随着事务集项数的增加呈指数增长,最小支持度阈值成为控制这种增长的关键.然而,实际应用中仅使用支持度阈值难以有效控制频繁项集的规模.为此定义N个最频繁项集挖掘问题,并提出基于支持度阈值动态调整策略的宽度优先搜索算法NApriori和深度优先搜索算法IntvMatrix挖掘N个最频繁项集.实验表明,本文的2种方法的效率比朴素方法高2倍以上,特别当N值较低时,本文方法的效率优势更为明显.     

高激励项集的挖掘研究

基于支持度的关联规则只能找出所有的频繁集,无法找到那些非频繁但效用很高的项集;基于效用的关联规则致力于发现所有高效用项集,无法找到效用不高但支持度与效用的积很大的项集。为克服支持度与效用的不足,提出了一种新的项集重要性的度量方法（即激励）及一种自下而上的挖掘高激励项集的算法HM-Two-Phase-Miner。激励集成了支持度与效用的优点,能同时表达项集的语义特性与统计特性。HM-Two-Phase-Miner利用事务权重激励向下封闭特性进行减枝,有效提高了算法的性能。     

基于二进制的关联规则挖掘算法*

将二进制引入关联规则求解中,充分利用二进制操作方便、运算速度快、节省空间的优势.在求解事务项集真子集和支持度时,对事务数据库中相同事务只求解一次,并给出了真子集的具体求解算法.本算法一次扫描数据库可以挖掘出所有频繁集,而且可以根据需求对最小支持度和最小置信度进行修改,修改后不需要再次扫描数据库即可求出频繁项集,大大提高了挖掘效率.     

Paradigm and performance analysis of distributed frequent itemset mining algorithms based on Mapreduce

FrequentItemsetMining (FIM) is one of the most important data mining tasks and is the foundation of many data mining tasks. In Big Data era, centralized FIM algorithms cannot meet the needs of FIM for big data in terms of time and space, so Distributed Frequent Itemset Mining (DFIM) algorithms have been designed to meet the above challenges. In this paper, LocalGlobal and RedistributionMining which are two main paradigms of DFIM algorithm are discussed; Two algorithms of these paradigms on MapReduce named LG and RM are proposed while MapReduce is a popular distributed computing model, and also the related work is discussed. The experimental results show that the RM algorithm has better performance in terms of computation and scalability of sites, and can be used as the basis for designing the DFIM algorithm based on MapReduce. This paper also discusses the main ideas of improving the DFIM algorithms based on MapReduce.     

基于图游走的并行协同过滤推荐算法

针对目前协同过滤推荐算法存在的数据稀疏性问题和可扩展性问题,本文进行了相关研究。针对稀疏性问题,在传统的皮尔逊相关相似度中引入交占比系数计算用户间直接相似度,该方法缓解了用户间共同评分项的占比问题;提出一种基于图游走的间接相似度计算方法,该方法根据用户间的直接相似度建立用户网络图,在用户网络图上通过游走计算用户间的间接相似度,并进行推荐。在Spark平台上实现本文方法的并行化,缓解了数据规模增加带来的可扩展性问题。实验结果表明:本文提出的算法在不同数据集上均取得了良好效果,有效地提高了推荐准确度,并且在分布式环境下具有良好的可扩展性。     

基于特征融合的多约束非负矩阵分解算法

针对非负矩阵分解后数据的稀疏性降低、单一图像特征不能够很好地描述图像内容的问题,提出一种基于特征融合的多约束非负矩阵分解算法。该算法不仅考虑了少量已知样本的标签信息和稀疏约束,还对其进行了图正则化处理,而且将分解后的具有不同稀疏度的图像特征进行了融合,从而增强了算法的聚类性能和有效性。在Yale-32和COIL20数据集上进行的对比实验进一步验证了该算法具有更好的聚类精度和稀疏性。     

直接从空间数据中挖掘频繁模式

为简化空间频繁模式挖掘的预处理步骤并提高挖掘效率, 提出一种可以直接以空间矢量和栅格图层作为输入的挖掘算法FISA(fast intersect spatial Apriori)。该算法利用图层求交和面积计算操作实现谓词集支持度计数进而实现频繁谓词集和关联规则挖掘。相对于基于事务空间关联规则挖掘算法, FISA不需要预先进行空间数据事务化处理, 并且所得结果均有对应图层, 便于实现结果的可视化; 相对于其他基于空间分析的挖掘算法, FISA支持空间数据的矢量和栅格格式, 且引入了快速求交方法以保证其可伸缩性。实验结果表明该算法可以直接从空间数据中高效正确地挖掘出频繁模式。     

Distributed high dimensional indexing for k-NN search

Although conventional index structures provide various nearest-neighbor search algorithms for high-dimensional data, there are additional requirements to increase search performances, as well as to support index scalability for large-scale datasets. To support these requirements, we propose a distributed high-dimensional index structure based on cluster systems, called a Distributed Vector Approximation-tree (DVA-tree), which is a two-level structure consisting of a hybrid spill-tree and Vector Approximation files (VA-files). We also describe the algorithms used for constructing the DVA-tree over multiple machines and performing distributed k-nearest neighbors (NN) searches. To evaluate performances of the DVA-tree, we conduct an experimental study using both real and synthetic datasets. The results show that our proposed method has significant performance advantages over existing index structures on different kinds of dataset.     

基于深度学习的图像质量评价方法综述

图像质量评价是对图像或视频的视觉质量的一种度量,主要分析了最近10年图像质量评价算法的研究情况。介绍了图像质量评价算法的衡量指标以及常用的图像质量评价数据集,对图像质量评价方法的分类做了阐述,重点分析了基于深度学习技术的图像质量评价算法。目前,该类算法的基础模型主要包括深度卷积神经网络、深度生成对抗网络和变换器,其性能通常高于传统的图像质量评价算法。描述了基于深度学习技术的图像质量评价算法的原理,重点介绍了基于深度生成对抗网络的无参考图像质量评价算法,通过增强对抗学习强度提高模拟参考图的可靠性。深度学习技术需要海量训练数据的支持,探讨和总结数据集增强的方法,对数字图像质量评价方法的未来研究进行展望。     

Weighted frequent itemset mining over uncertain databases

Frequent itemset mining (FIM) is a fundamental research topic, which consists of discovering useful and meaningful relationships between items in transaction databases. However, FIM suffers from two important limitations. First, it assumes that all items have the same importance. Second, it ignores the fact that data collected in a real-life environment is often inaccurate, imprecise, or incomplete. To address these issues and mine more useful and meaningful knowledge, the problems of weighted and uncertain itemset mining have been respectively proposed, where a user may respectively assign weights to items to specify their relative importance, and specify existential probabilities to represent uncertainty in transactions. However, no work has addressed both of these issues at the same time. In this paper, we address this important research problem by designing a new type of patterns named high expected weighted itemset (HEWI) and the HEWI-Uapriori algorithm to efficiently discover HEWIs. The HEWI-Uapriori finds HEWIs using an Apriori-like two-phase approach. The algorithm introduces a property named high upper-bound expected weighted downward closure (HUBEWDC) to early prune the search space and unpromising itemsets. Substantial experiments on real-life and synthetic datasets are conducted to evaluate the performance of the proposed algorithm in terms of runtime, memory consumption, and number of patterns found. Results show that the proposed algorithm has excellent performance and scalability compared with traditional methods for weighted-itemset mining and uncertain itemset mining.     

基于LSCP算法的比特币网络异常交易检测

异常检测是比特币交易数据分析的研究热点之一。针对现有的基于机器学习的异常交易检测方法难以对多种异常类型进行准确概括、泛化能力不足的问题,对比特币交易数据构建网络结构并提取异常行为模式相关特征,应用基于局部动态选择组合的并行集成算法（LSCP）构建检测模型,并在算法中融入7种经典的异常检测算法,利用基学习器对不同异常类型的敏感性,提升检测模型的可靠性和稳定性。实验结果表明,与传统的检测方法相比,结合异构基学习器的LSCP算法在整体检测性能上具有更好的效果。     

一种基于全局代表点的快速最小二乘支持向量机稀疏化算法

非稀疏性是最小二乘支持向量机（Least squares support vector machine,LS-SVM）的主要不足,因此稀疏化是LS-SVM研究的重要内容.在目前LS-SVM稀疏化研究中,多数算法采用的是基于迭代选择的稀疏化策略,但是时间复杂度和稀疏化效果还不够理想.为了进一步改进LS-SVM稀疏化方法的性能,文中提出了一种基于全局代表点选择的快速LS-SVM稀疏化算法（Global-representation-based sparse least squares support vector machine,GRS-LSSVM）.在综合考虑数据局部密度和全局离散度的基础上,给出了数据全局代表性指标来评估每个数据的全局代表性.利用该指标,在全部数据中,一次性地选择出其中最具有全局代表性的数据并构成稀疏化后的支持向量集,然后在此基础上求解决策超平面,是该算法的基本思路.该算法对LS-SVM的非迭代稀疏化研究进行了有益的探索.通过与传统的迭代稀疏化方法进行比较,实验表明GRS-LSSVM具有稀疏度高、稳定性好、计算复杂度低的优点.