基于模式增长的高效用序列模式挖掘算法

高效用序列模式挖掘是数据挖掘领域的一项重要内容, 在生物信息学、消费行为分析等方面具有重要的应用.与传统基于频繁项模式挖掘方法不同, 高效用序列模式挖掘不仅考虑项集的内外效用, 更突出项集的时间序列含义, 计算复杂度较高.尽管已经有一定数量的算法被提出应用于解决该类问题, 挖掘算法的时空效率依然成为该领域的主要研究热点问题.鉴于此, 本文提出一个基于模式增长的高效用序列模式挖掘算法HUSP-FP.依据高效用序列项集必须满足事务效用闭包属性要求, 算法首先在去除无用项后建立全局树, 进而采用模式增长方法从全局树上获取全部高效用序列模式, 避免产生候选项集. 在实验环节与目前效率较好的HUSP-Miner、USPAN、HUS-Span三类算法进行了时空计算对比, 实验结果表明本文给出算法在较小阈值下仍能有效挖掘到相关序列模式, 并且在计算时间和空间使用效率两方面取得了较大的提高.     

基于向量和矩阵的频繁项集挖掘算法研究

为了能快速、高效地从事务数据库中挖掘所有的频繁项集,提出了一种基于向量和矩阵的VMA高效算法.该算法只需扫描数据库一次,将事物数据库转化到布尔向量中,对频繁1-项集按支持度大小进行非递减排序,排序后在很大程度上减少了用于扩展的k-项集(k＞2),生成一个2-项集支持度矩阵,由频繁k-项集(k≥2)扩展生成频繁(k+1)-项集.大量实验结果表明,VMA算法的性能不但明显优于Apriori算法,而且适应于大型事务数据库中频繁项集挖掘.     

在线挖掘数据流闭频繁项集的高效算法

数据流闭频繁项集挖掘算法得到了广泛的研究,其中一个典型的工作就是NewMomen、算法。针对New- Moment算法存在搜索空间大而造成算法时间效率低的问题,提出了一种改进的数据流闭频繁项集挖掘算法A-Ncw- Moment。它设计了一个二进制位表示项目与扩展的频繁项目列表相结合的数据结构,来记录数据流信息及闭频繁项 集。在窗体初始阶段,首先挖掘频繁1一项集所产生的支持度为最大的最长闭频繁项集,接着提出新的“不需扩展策略” 和“向下扩展策略”来避免生成大量中间结果,快速发现其余闭频繁项集,达到极大缩小搜索空间的目的。在窗体滑动 阶段,提出“动态不频繁剪枝策略”来从已生成的闭频繁项集中快速删除非闭频繁项集,并提出“动态不搜索策略”来动 态维护所有闭频繁项集的生成,以降低闭频繁项集的维护代价,提高算法的效率。理论分析与实验结果表明,A-New- Moment算法具有较好的性能。     

基于片上多核的频繁项集并行挖掘算法

关联规则挖掘中最主要的工作是如何高效地挖掘频繁项集。目前在单机平台上,由于计算量大等原因,大数据集上的关联规则挖掘很难得到理想结果。在分析现有频繁项集挖掘算法的基础上,结合Eclat和dEclat挖掘算法优点,针对大数据集和片上多核共享内存计算环境,提出一种高效的并行频繁项集挖掘算法PEclat,算法实现了任务级并行挖掘频繁项集,并在大数据集上进行了多项测试。实验结果表明,无论数据稠密程度如何,该算法均能取得较好的性能。     

一种有效的基于图的关联规则挖掘算法

基于图的关联规则挖掘算法是一种通过构建关联图并直接生成候选频繁项集，进而验证得到所有频繁项集的算法。在该算法中，对候选项集的验证操作占用了大量的时间，为此提出了改进算法。改进主要体现在两个方面：按支持度降序对频繁1项重新编号再构建关联图；利用Apriori性质删减用来生成候选项集的冗余扩展项节点。实验结果表明，在最小支持度阈值较小时，改进算法有效减少了冗余的候选频繁项集，提高了算法的性能。     

基于双阈值Apriori算法和非频繁项集的关联规则挖掘方法

针对从本文数据集中的正负关联规则挖掘问题,提出一种基于双阈值Apriori算法和非频繁项集的挖掘方法。首先,对通过逆文档频率(IDF)对语料库中的项(项集)进行加权,筛选出前N%的项集。然后,通过提出的双支持度阈值Apriori算法来提取频繁项集和非频繁项集,以此降低非频繁项集的数量。最后,通过置信度和升降度阈值的判断,分别从频繁项集和非频繁项集中挖掘正负关联规则。其中,创新性的利用了非频繁项集来挖掘正负关联规则。在一个医学文本数据集上的实验结果表明,提出的方法能够有效挖掘出正负关联规则,且能够大大降低项集和规则数量。     

基于矩阵的频繁项集挖掘算法

如何高效地挖掘频繁项集是关联规则挖掘的主要问题。该文根据集合论和矩阵理论,提出一种基于矩阵的频繁项集挖掘算法。该算法只需扫描数据库一次,就能把所有事务转化为矩阵的行,把所有项和项集转化为矩阵的列,在对矩阵操作时能一次性产生所有频繁项集,且当支持度阈值改变时无需重新扫描数据库。实验结果表明,该算法的挖掘效率高于Apriori算法。     

高效的关联规则挖掘算法研究

目前已经提出了许多用于高效地发现大规模数据库中的关联规则的算法,但都是对关联规则中满足最小支持度的频繁项集的研究,没有对频繁项集中如何高效地计算得到满足最小置信度的关联规则进行研究.针对这种情况,提出了一种高效关联规则的挖掘算法EA,解决了在挖掘关联规则过程中如何高效挖掘满足最小置信度的关联规则问题.     

基于差异节点集的加权频繁项集挖掘算法

针对基于WN-list的加权频繁项集挖掘算法NFWI挖掘效率低的问题,提出一种基于WDiffNodeset的加权频繁项集挖掘算法DiffNFWI。对DiffNodeset数据结构进行扩展得到WDiffNodeset,采用集合枚举树和混合搜索策略相结合的方法查找加权频繁项集,以避免大量的交集运算并实现高效查找。使用差集策略计算项集的加权支持度,从而降低计算量。在mushroom、pumsb等数据集上的实验结果表明,DiffNFWI算法的运行效率优于NFWI算法。     

基于频繁项集与负规则的局部反馈查询扩展

针对信息检索中存在的词不匹配问题,提出了基于频繁项集和负关联规则挖掘的局部反馈查询扩展模型及其算法.该算法对前列n篇初检文档挖掘频繁项集和非频繁项集,并从频繁项集中提取关联词;从频繁项集和非频繁项集中挖掘负关联规则,提取负关联规则后件作为负关联词,计算负关联词与整个原查询词的相关性;根据相关性删除关联词库中与负关联词相同的词项,将余下的关联词项作为最终扩展词,并与原查询组合成新查询,实现查询扩展.实验结果表明,该算法能发现虚假的负关联词,有效地提高和改善信息检索性能.     

An efficient algorithm for mining temporal high utility itemsets from data streams

Utility of an itemset is considered as the value of this itemset, and utility mining aims at identifying the itemsets with high utilities. The temporal high utility itemsets are the itemsets whose support is larger than a pre-specified threshold in current time window of the data stream. Discovery of temporal high utility itemsets is an important process for mining interesting patterns like association rules from data streams. In this paper, we propose a novel method, namely THUI (Temporal High Utility Itemsets)-Mine, for mining temporal high utility itemsets from data streams efficiently and effectively. To the best of our knowledge, this is the first work on mining temporal high utility itemsets from data streams. The novel contribution of THUI-Mine is that it can effectively identify the temporal high utility itemsets by generating fewer candidate itemsets such that the execution time can be reduced substantially in mining all high utility itemsets in data streams. In this way, the process of discovering all temporal high utility itemsets under all time windows of data streams can be achieved effectively with less memory space and execution time. This meets the critical requirements on time and space efficiency for mining data streams. Through experimental evaluation, THUI-Mine is shown to significantly outperform other existing methods like Two-Phase algorithm under various experimental conditions.     

含负项top-k高效用项集挖掘算法

含负项高效用项集（HUI）挖掘是新兴的数据挖掘任务之一。为了挖掘满足用户需求的含负项HUI结果集,提出了含负项top-k高效用项集（THN）挖掘算法。为了提升THN算法的时空性能,提出了自动提升最小效用阈值的策略,并采用模式增长方法进行深度优先搜索;使用重新定义的子树效用和重新定义的本地效用修剪搜索空间;使用事务合并技术和数据集投影技术解决多次扫描数据库的问题;为了提高效用计数的速度,使用效用数组计数技术计算项集的效用。实验结果表明,THN算法的内存消耗约为HUINIV-Mine算法的1/60,约为FHN算法的1/2;THN算法的执行时间是FHN算法的1/10;而且该算法在密集数据集上的性能更好。     

Fuzzy utility mining with upper-bound measure

Fuzzy utility mining has been an emerging research issue because of its simplicity and comprehensibility. Different from traditional fuzzy data mining, fuzzy utility mining considers not only quantities of items in transactions but also their profits for deriving high fuzzy utility itemsets. In this paper, we introduce a new fuzzy utility measure with the fuzzy minimum operator to evaluate the fuzzy utilities of itemsets. Besides, an effective fuzzy utility upper-bound model based on the proposed measure is designed to provide the downward-closure property in fuzzy sets, thus reducing the search space of finding high fuzzy utility itemsets. A two-phase fuzzy utility mining algorithm, named TPFU, is also proposed and described for solving the problem of fuzzy utility mining. At last, the experimental results on both synthetic and real datasets show that the proposed algorithm has good performance.     

频繁和高效用项集挖掘

对从事务数据库中挖掘有意义的项集的研究已超过10年.然而,大多数的研究要么使用频繁度或支持度(如频繁项集挖掘),要么使用效用值或利润(如高效用项集挖掘)作为主要的衡量标准.单独使用这两种衡量方式都有各自的局限性,比如频繁度很高的项集其效用值有可能很低,而效用值很高的项集其频繁度往往很低,将这些项集推荐给用户没有意义.将这两种衡量标准综合考虑,希望找出那些频繁度和效用值都很高的项集.该项工作最大的挑战是效用值既不满足单调性也不满足反单调性.因此,提出了高效算法FHIMA.FHIMA采用PrefixSpan的思想,挖掘时能避免产生非频繁的候选项集.此外,还根据效用和质量上界的一些性质,有效地缩小了搜索空间,极大地提高了FHIMA算法的效率.     

An incremental mining algorithm for high utility itemsets

Association-rule mining, which is based on frequency values of items, is the most common topic in data mining. In real-world applications, customers may, however, buy many copies of products and each product may have different factors, such as profits and prices. Only mining frequent itemsets in binary databases is thus not suitable for some applications. Utility mining is thus presented to consider additional measures, such as profits or costs according to user preference. In the past, a two-phase mining algorithm was designed for fast discovering high utility itemsets from databases. When data come intermittently, the approach needs to process all the transactions in a batch way. In this paper, an incremental mining algorithm for efficiently mining high utility itemsets is proposed to handle the above situation. It is based on the concept of the fast-update (FUP) approach, which was originally designed for association mining. The proposed approach first partitions itemsets into four parts according to whether they are high transaction-weighted utilization itemsets in the original database and in the newly inserted transactions. Each part is then executed by its own procedure. Experimental results also show that the proposed algorithm executes faster than the two-phase batch mining algorithm in the intermittent data environment     

HHUIM：一种新的启发式高效用项集挖掘方法

针对基于启发式的高效用项集挖掘算法在挖掘过程中可能丢失大量项集的问题,提出一种新的启发式高效用项集挖掘算法HHUIM。HHUIM利用哈里斯鹰优化算法进行种群的更新,能够有效减少项集的丢失。提出并设计了鹰的替换策略,解决了搜索空间较大的问题,降低了适应度函数值低于最小效用阈值的鹰的数量。此外,提出存储回溯策略,可有效防止算法收敛过快达到局部最优。大量的实验表明,所提算法优于目前最先进的启发式高效用项集挖掘算法。     

减少候选项集的数据流高效用项集挖掘算法

大数据环境下高效用项集挖掘算法中过多的候选项集极大地降低了算法的时空效率,提出了一种减少候选项集的数据流高效用项集挖掘算法。首先,通过数据流中当前窗口的一次扫描建立一个全局树,并降低全局树中头表入口与节点的冗余效用值;然后,基于全局树生成候选模式,基于增长算法降低局部树的候选项集效用;最终,从候选模式中选出高效用模式。基于真实数据流的实验结果表明,本算法的时空效率与内存占用比均优于其他数据流的高效用模式挖掘算法。     

高速边界扫描主控器设计

分析边界扫描测试技术的工作机制和对测试支撑系统的功能需求,提出一种基于USB总线的高速边界扫描测试主控器的设计方案。利用CY7C68013作为USB2．0接口控制器,使用CPLD实现JTAG主控硬核,完成JTAG协议和USB总线协议的相互转换。JTAG的TCK时钟频率可调,最高可达48MHz。用户可利用该边界扫描控制器方便高效地进行边界扫描测试。     

Effective utility mining with the measure of average utility

Frequent-itemset mining only considers the frequency of occurrence of the items but does not reflect any other factors, such as price or profit. Utility mining is an extension of frequent-itemset mining, considering cost, profit or other measures from user preference. Traditionally, the utility of an itemset is the summation of the utilities of the itemset in all the transactions regardless of its length. The average utility measure is thus adopted in this paper to reveal a better utility effect of combining several items than the original utility measure. It is defined as the total utility of an itemset divided by its number of items within it. The average-utility itemsets, as well as the original utility itemsets, does not have the “downward-closure” property. A mining algorithm is then proposed to efficiently find the high average-utility itemsets. It uses the summation of the maximal utility among the items in each transaction with the target itemset as the upper bound to overestimate the actual average utilities of the itemset and processes it in two phases. As expected, the mined high average-utility itemsets in the proposed way will be fewer than the high utility itemsets under the same threshold. The proposed approach can thus be executed under a larger threshold than the original, thus with a more significant and relevant criterion. Experimental results also show the performance of the proposed algorithm.