《電子技術(shù)應用》
您所在的位置：首頁 > 其他 > 设计应用 > 基于约束的多维Apriori改进算法
基于约束的多维Apriori改进算法
电子技术应用
王志昊，苏明月，李东方，沈炜，杨光
（北京计算机技术及应用研究所，北京 100854）
摘要： 针对经典多维关联规则挖掘算法执行效率不高、存在冗余规则的不足，提出基于约束的多维Apriori改进算法，在多维Apriori算法的基础上，将用户约束引入挖掘过程，根据关于谓词的约束产生用户感兴趣的频繁谓词集，并以此为依据删减事务集。该算法一方面通过用户约束大大缩减了候选谓词集的产生，另一方面经过删减的事务集也降低了扫描数据库的开销，最终实现了挖掘效率的提高以及冗余规则的减少。应用该算法在FPGA代码缺陷事务集上进行对比实验，实验结果证明了该算法相比多维Apriori算法，在搜索效率以及挖掘结果的准确性方面均得到了改善，有效提高了FPGA代码缺陷分析的准确性。
中圖分類號：TP311 文獻標志碼：A DOI: 10.16157/j.issn.0258-7998.233873
中文引用格式： 王志昊，蘇明月，李東方，等. 基于約束的多維Apriori改進算法[J]. 電子技術(shù)應用，2023，49(10)：100-105.
英文引用格式： Wang Zhihao，Su Mingyue，Li Dongfang，et al. Algorithm of multi-dimensional Apriori with constraints[J]. Application of Electronic Technique，2023，49(10)：100-105.
Algorithm of multi-dimensional Apriori with constraints
Wang Zhihao，Su Mingyue，Li Dongfang，Shen Wei，Yang Guang
(Institute 706， Second Academy of China Aerospace Science and Industry Corporation， Beijing 100854， China)
Abstract： Aiming at the inefficiency of multi-dimensional association rules mining algorithm and the existence of redundant rules, an algorithm of multi-Dimensional apriori with constraints is proposed. Based on the multi-dimensional Apriori algorithm, the algorithm controls the mining process with user constraints. According to the predicate constraint, the frequent predicate set that is of interest to the user is generated, and the transaction set is deleted based on the predicate constraint. On the one hand, the algorithm greatly reduces the generation of candidate predicate sets through user constraints. On the other hand, the reduced transaction set also reduces the scanning database overhead. Finally, the efficiency of mining is improved and the redundant rules are reduced. This algorithm is used to compare experiments on FPGA code defect transaction sets. The experimental results show that compared with the multi-dimensional Apriori algorithm, this algorithm has improved the search efficiency of frequent predicate sets and the accuracy of mining results.
Key words : association rules mining；multi-dimensional association rule；Apriori；frequent predicate set；predicate constraint；data mining

0　引言

現(xiàn)代社會，生產(chǎn)力快速發(fā)展，通過不斷變革生產(chǎn)信息技術(shù)，人們大大提高了創(chuàng)造和收集數(shù)據(jù)的能力，迅速擴大了數(shù)據(jù)資料的規(guī)模。急劇增長的數(shù)據(jù)資料和數(shù)據(jù)庫迫使人們采用新的技術(shù)手段和工具來處理海量的數(shù)據(jù)，自動自主地幫助人們管理、提取并分析有用的信息，來發(fā)掘有價值的知識，為人們提供決策服務。由此，數(shù)據(jù)挖掘（Data Mining）[1] 在這樣的宏觀背景下誕生。將數(shù)據(jù)挖掘技術(shù)充分運用到現(xiàn)實的生產(chǎn)中，提高企業(yè)生產(chǎn)的效率，降低生產(chǎn)成本。數(shù)據(jù)挖掘的應用范圍較廣，如聚類、預測、分類、異常分析以及相互關(guān)聯(lián)性分析。

數(shù)據(jù)挖掘中，關(guān)聯(lián)規(guī)則是較為主要的研究對象。其中頻繁項集的產(chǎn)生是最核心、最受關(guān)注的問題。關(guān)聯(lián)規(guī)則反映了一個事物與其他事物之間的相互依存和關(guān)聯(lián)性[2]。換句話說，關(guān)聯(lián)規(guī)則是一種隱含在數(shù)據(jù)中的知識模型，其通過量化數(shù)字，從海量數(shù)據(jù)中挖掘出有價值的數(shù)據(jù)項之間的相關(guān)關(guān)系[3]。

關(guān)聯(lián)規(guī)則挖掘最初由Agrawal[4]等人于1993年提出，通過關(guān)聯(lián)規(guī)則的挖掘可以找出潛藏在數(shù)據(jù)庫中各個屬性之間的關(guān)系，輔助人們更合理地進行商業(yè)活動、金融決策和生產(chǎn)生活等。

目前，典型的挖掘關(guān)聯(lián)規(guī)則的算法主要是Apriori算法[5]，其核心在于找到數(shù)據(jù)庫中的所有頻繁項集。Apriori算法通過逐級產(chǎn)生頻繁項集并利用先驗性質(zhì)縮減候選項集產(chǎn)生。在掃描數(shù)據(jù)集的過程中，Hossain提出可使用自動遞歸連接來挖掘候選項目集[6]，然后剪枝用于挖掘頻繁項集。2021年，Li等人提出基于時序約束的關(guān)聯(lián)規(guī)則挖掘，減小了系統(tǒng)開銷[7]。Wang等人利用MapReduce的思想改進Apriori算法，有效提高了搜索效率[8]。2022年，Dhinakaran等人集成Apriori算法和仿生算法，通過降低處理大型數(shù)據(jù)集時的低運行時性能來解決頻繁項集問題[9]。



本文詳細內(nèi)容請下載：http://m.ihrv.cn/resource/share/2000005721




作者信息：

王志昊，蘇明月，李東方，沈煒，楊光

（北京計算機技術(shù)及應用研究所，北京 100854）


微信圖片_20210517164139.jpg

此內(nèi)容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權(quán)禁止轉(zhuǎn)載。

相關(guān)內(nèi)容