《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 其他 > 設(shè)計應(yīng)用 > 基于約束的多維Apriori改進(jìn)算法
基于約束的多維Apriori改進(jìn)算法
電子技術(shù)應(yīng)用
王志昊,蘇明月,李東方,沈煒,楊光
(北京計算機(jī)技術(shù)及應(yīng)用研究所,北京 100854)
摘要: 針對經(jīng)典多維關(guān)聯(lián)規(guī)則挖掘算法執(zhí)行效率不高、存在冗余規(guī)則的不足,提出基于約束的多維Apriori改進(jìn)算法,在多維Apriori算法的基礎(chǔ)上,將用戶約束引入挖掘過程,根據(jù)關(guān)于謂詞的約束產(chǎn)生用戶感興趣的頻繁謂詞集,并以此為依據(jù)刪減事務(wù)集。該算法一方面通過用戶約束大大縮減了候選謂詞集的產(chǎn)生,另一方面經(jīng)過刪減的事務(wù)集也降低了掃描數(shù)據(jù)庫的開銷,最終實(shí)現(xiàn)了挖掘效率的提高以及冗余規(guī)則的減少。應(yīng)用該算法在FPGA代碼缺陷事務(wù)集上進(jìn)行對比實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果證明了該算法相比多維Apriori算法,在搜索效率以及挖掘結(jié)果的準(zhǔn)確性方面均得到了改善,有效提高了FPGA代碼缺陷分析的準(zhǔn)確性。
中圖分類號:TP311 文獻(xiàn)標(biāo)志碼:A DOI: 10.16157/j.issn.0258-7998.233873
中文引用格式: 王志昊,蘇明月,李東方,等. 基于約束的多維Apriori改進(jìn)算法[J]. 電子技術(shù)應(yīng)用,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ù)的能力,迅速擴(kuò)大了數(shù)據(jù)資料的規(guī)模。急劇增長的數(shù)據(jù)資料和數(shù)據(jù)庫迫使人們采用新的技術(shù)手段和工具來處理海量的數(shù)據(jù),自動自主地幫助人們管理、提取并分析有用的信息,來發(fā)掘有價值的知識,為人們提供決策服務(wù)。由此,數(shù)據(jù)挖掘(Data Mining)[1] 在這樣的宏觀背景下誕生。將數(shù)據(jù)挖掘技術(shù)充分運(yùn)用到現(xiàn)實(shí)的生產(chǎn)中,提高企業(yè)生產(chǎn)的效率,降低生產(chǎn)成本。數(shù)據(jù)挖掘的應(yīng)用范圍較廣,如聚類、預(yù)測、分類、異常分析以及相互關(guān)聯(lián)性分析。

數(shù)據(jù)挖掘中,關(guān)聯(lián)規(guī)則是較為主要的研究對象。其中頻繁項(xiàng)集的產(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ù)項(xiàng)之間的相關(guān)關(guān)系[3]。

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

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



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




作者信息:

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

(北京計算機(jī)技術(shù)及應(yīng)用研究所,北京 100854)


微信圖片_20210517164139.jpg

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