信息工程与人工智能学院知识库

  高效用项集挖掘考虑项的重要性、利润、用户偏好等因素，给项赋予不同的权重以计算项集的效用，更加满足实际应用的需求。高效用项集挖掘领域是当前数据挖掘的研究热点之一。目前，数据的爆炸式增长给高效用项集挖掘算法的研究提出了新的挑战。

  通过文献分析发现，采用utility-list数据结构的一类高效用项集挖掘算法，可以进一步减少在挖掘过程中的连接操作。本文对使用utility-list的经典算法HUI-Miner和ULB-Miner在连接操作等方面进行改进，分别提出了改进算法HUIwTMS-Miner和ULBwTMS-Miner，并对其进行实验验证。由于单机多核处理器是实现复杂并行计算系统的基础之一，在单机多核处理器环境下的研究可以从微观的角度揭示并行计算的原理。本文在单机多核处理器环境下，利用Thread Pool框架分别设计、实现了ULB-Miner算法和ULBwTMS-Miner算法的并行算法PULB-Miner和PULBwTMS-Miner。主要研究工作如下：

（1）结合投影数据库技术和事务合并策略，分别对经典算法HUI-Miner、ULB-Miner进行改进。根据≻_T顺顺序对事务进行排序，使用剩余效用剪枝对1-项集进行二次剪枝，减少投影数据库的生成数量，同时对相同事务进行合并。本研究在SPMF公开资源库中的Retail、Pumsb、Connect、Mushroom、eCommerce数据集上分别设定了5个不同最小效用阈值，进行了算法性能对比实验。实验结果显示，HUIwTMS-Miner算法除在极稀疏数据集Retail外的稀疏数据集eCommerce和稠密数据集Pumsb、Connect、Mushroom上的运行时间明显减少，而内存消耗有所增加；ULBwTMS-Miner算法在稠密数据集Pumsb、Connect、Mushroom上的运行时间明显减少，在除Retail外的其他数据集上的内存消耗有所增加。

（2）设计了ULB-Miner算法的并行算法PULB-Miner。在单机多核处理器环境下，利用Thread Pool框架实现PULB-Miner算法。分别在Retail、Pumsb、Connect、Mushroom、eCommerce数据集的不同最小效用阈值、不同线程进行实验，对比分析ULB-Miner算法、PULB-Miner算法的性能。实验结果显示，PULB-Miner算法在五个数据集上均表现良好，表明该算法具有可行性和有效性。

（3）设计了ULBwTMS-Miner算法的并行算法PULBwTMS-Miner。在单机多核处理器环境下，利用Thread Pool框架实现PULBwTMS-Miner算法。分别在Retail、Pumsb、Connect、Mushroom、eCommerce数据集的不同最小效用阈值、不同线程进行实验，对比分析了ULBwTMS-Miner算法和PULBwTMS-Miner算法的性能，同时还对比分析了PULB-Miner算法和PULBwTMS-Miner算法的性能。实验结果显示，PULBwTMS-Miner算法在运行时间上明显低于ULBwTMS-Miner算法，内存消耗略有增加，在稠密数据集Pumsb、Connect、Mushroom上的运行时间明显低于PULB-Miner算法，内存消耗也减少，表明该算法具有可行性和有效性。

  High utility itemsets mining considers factors such as the importance, profit, and user preferences of items, assigns different weights to items to calculate the utility of itemsets, and better meets the needs of practical applications. The field of high utility itemsets mining is one of the current research hotspots in data mining. At present, the explosive growth of data poses new challenges to the research of high utility itemsets mining algorithms.

  Through literature analysis, it was found that a class of high utility itemsets mining algorithms using utility-list data structures can further reduce the number of connection operations during the mining process. This article improves the classic algorithms HUI-Miner and ULB-Miner using utility-list in connection operations, and proposes improved algorithms HUIwTMS-Miner and ULBwTMS-Miner, respectively, and conducts experimental verification on them. Due to the fact that single machine multi-core processors are one of the foundations for implementing complex parallel computing systems, research in single machine multi-core processor environments can reveal the principles of parallel computing from a microscopic perspective. This article designs and implements parallel algorithms PULB-Miner and PULBwTMS-Miner for ULB-Miner and ULBwTMS-Miner algorithms using the Thread Pool framework in a single machine multi-core processor environment. The main research work is as follows:

（1）By combining projection database technology and transaction merging strategy, improvements are made to the classic algorithms HUI-Miner and ULB-Miner, respectively. Sort transactions in  ≻_T  order, use residual utility pruning to perform secondary pruning on the 1-itemset, reduce the number of generated projection databases, and merge the same transactions. This study set 5 different minimum utility thresholds on the Retail, Pumsb, Connect, Mushroom, and eCommerce datasets in the SPMF public resource library and conducted algorithm performance comparison experiments. The experimental results show that the HUIwTMS-Miner algorithm significantly reduces running time on sparse datasets eCommerce and dense datasets Pumsb, Connect, and Mushroom, except for the extremely sparse dataset Retail, while increasing memory consumption; The ULBwTMS-Miner algorithm significantly reduces runtime on dense datasets such as Pumsb, Connect, and Mushroom, while increasing memory consumption on datasets other than Retail.

（2）Designed a parallel algorithm called PULB-Miner for the ULB-Miner algorithm. Implement the PULB-Miner algorithm using the Thread Pool framework in a single machine multi-core processor environment. Conduct experiments on different minimum utility thresholds and threads on the Retail, Pumsb, Connect, Mushroom, and eCommerce datasets to compare and analyze the performance of ULB-Miner algorithm and PULB-Miner algorithm. The experimental results show that the PULB-Miner algorithm performs well on all five datasets, indicating its feasibility and effectiveness.

（3）Designed a parallel algorithm called PULBwTMS-Miner for the ULBwTMS-Miner algorithm. Implement the PULBwTMS-Miner algorithm using the Thread Pool framework in a single machine multi-core processor environment. We conducted experiments on different minimum utility thresholds and threads on the Retail, Pumsb, Connect, Mushroom, and eCommerce datasets to compare and analyze the performance of ULBwTMS-Miner algorithm and PULBwTMS-Miner algorithm. We also compared and analyzed the performance of PULB-Miner algorithm and PULBwTMS-Miner algorithm. The experimental results show that the PULBwTMS-Miner algorithm has significantly lower runtime than the ULBwTMS-Miner algorithm, with a slight increase in memory consumption. The runtime on dense datasets such as Pumsb, Connect, and Mushroom is significantly lower than the PULB-Miner algorithm, and memory consumption is also reduced, indicating the feasibility and effectiveness of this algorithm.