基于約束的多維Apriori 改進(jìn)算法

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

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

0 引言

現(xiàn)代社會(huì)，生產(chǎn)力快速發(fā)展，通過不斷變革生產(chǎn)信息技術(shù)，人們大大提高了創(chuàng)造和收集數(shù)據(jù)的能力，迅速擴(kuò)大了數(shù)據(jù)資料的規(guī)模。急劇增長的數(shù)據(jù)資料和數(shù)據(jù)庫迫使人們采用新的技術(shù)手段和工具來處理海量的數(shù)據(jù)，自動(dòng)自主地幫助人們管理、提取并分析有用的信息，來發(fā)掘有價(jià)值的知識(shí)，為人們提供決策服務(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ù)測(cè)、分類、異常分析以及相互關(guān)聯(lián)性分析。

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

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

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

現(xiàn)有的Apriori 算法主要適用于單維布爾型數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘，若想挖掘多維關(guān)聯(lián)規(guī)則，需將多維事務(wù)集的數(shù)據(jù)屬性進(jìn)行拆分、映射，轉(zhuǎn)化成單維布爾類型事務(wù)集，再利用Apriori 等算法進(jìn)行挖掘，但當(dāng)多維數(shù)據(jù)維度較高或?qū)傩匀≈递^多時(shí)，挖掘過程將會(huì)產(chǎn)生過多的候選項(xiàng)集，嚴(yán)重影響算法執(zhí)行效率。針對(duì)該問題，目前多是通過改進(jìn)典型Apriori 算法[10]、將多維事務(wù)集映射到新結(jié)構(gòu)上進(jìn)行挖掘[11]、結(jié)合智能算法[12]等方式進(jìn)行多維關(guān)聯(lián)規(guī)則的挖掘。然而這些方法大多僅僅通過支持度等客觀條件控制挖掘過程，導(dǎo)致挖掘結(jié)果缺乏針對(duì)性，存在大量用戶不感興趣的冗余規(guī)則。并且由于Apriori 算法中候選項(xiàng)集數(shù)量與最長頻繁項(xiàng)集的長度成指數(shù)關(guān)系，因此當(dāng)事務(wù)集包含項(xiàng)目數(shù)量過多時(shí)，算法將會(huì)面臨候選項(xiàng)集搜索空間爆炸的問題。

因此，針對(duì)以上不足，本文在前人研究的基礎(chǔ)上，以提高算法處理效率、深入挖掘數(shù)據(jù)間關(guān)聯(lián)規(guī)則為優(yōu)化目標(biāo)，將用戶約束引入挖掘過程，提出基于約束的多維Apriori 改進(jìn)算法（Algorithm of Multi-Dimensional Apriori with Constraints，MDAC），在進(jìn)行多維關(guān)聯(lián)規(guī)則挖掘的同時(shí)，降低了掃描數(shù)據(jù)庫的開銷，提高了檢索效率，實(shí)驗(yàn)證明MDAC 優(yōu)于傳統(tǒng)的多維Apriori 算法。

1 關(guān)聯(lián)規(guī)則挖掘

關(guān)聯(lián)規(guī)則挖掘是進(jìn)行大數(shù)據(jù)分析最常用的研究方法之一，它的目的在于從龐大數(shù)據(jù)集中找出各項(xiàng)之間的關(guān)聯(lián)，而這種關(guān)聯(lián)不會(huì)在數(shù)據(jù)中表現(xiàn)出來，需要進(jìn)行關(guān)聯(lián)分析，分析多個(gè)變量之間的聯(lián)系。關(guān)聯(lián)規(guī)則挖掘中最重要的兩個(gè)參數(shù)是支持度、置信度，參數(shù)取值會(huì)直接影響最后得到的關(guān)聯(lián)結(jié)果。

（1）關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則主要表示形式為A?B，A稱為規(guī)則前項(xiàng)，B稱為規(guī)則后項(xiàng)，符號(hào)?稱為關(guān)聯(lián)，A稱為?的先決條件，B則稱為?的結(jié)果。其中A≠?、B≠?且A∩B=?，在自然語言中，可以將其理解為“如果A，那么B”，該規(guī)則說明了A與B之間存在著某種關(guān)聯(lián)關(guān)系。

（2）支持度

支持度是用來衡量關(guān)聯(lián)規(guī)則重要性的關(guān)鍵量，支持度越高關(guān)聯(lián)規(guī)則越重要。假設(shè)D為事務(wù)集，關(guān)聯(lián)規(guī)則A?B在事務(wù)集D中成立，支持度s即包含A∪B的事務(wù)（即事務(wù)包含項(xiàng)集A和B中所有項(xiàng)）在D中的百分比，表示為P(A∪B)。支持度的計(jì)算公式如下所示：

（3）置信度

置信度是用來衡量關(guān)聯(lián)規(guī)則可靠性的關(guān)鍵參數(shù)，置信度的高低代表關(guān)聯(lián)規(guī)則可信程度的高低。關(guān)聯(lián)規(guī)則A?B在事務(wù)集D中具有置信度c，其中c是D中事務(wù)在包含項(xiàng)集A的條件下也包含項(xiàng)集B的概率，表示為條件概率P(B|A)。置信度的計(jì)算公式如下所示：

（4）強(qiáng)關(guān)聯(lián)規(guī)則

假設(shè)D為事務(wù)集，A、B為項(xiàng)集，若存在規(guī)則A?B的支持度s和置信度c分別不小于預(yù)先設(shè)定的最小支持度閾值（min_sup）和最小置信度閾值（min_conf），則稱規(guī)則A?B為強(qiáng)關(guān)聯(lián)規(guī)則。根據(jù)式（1）和式（2），可以得出由支持度計(jì)算置信度的公式：

式（3）表明規(guī)則A?B的置信度可從A和A∪B的支持度計(jì)數(shù)推出，即一旦得到A、B和A∪B的支持度計(jì)數(shù)，則可導(dǎo)出對(duì)應(yīng)的關(guān)聯(lián)規(guī)則A?B和B?A，并且可以直觀判斷它們是否為強(qiáng)關(guān)聯(lián)規(guī)則。

（5）多維關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則根據(jù)規(guī)則所涉及的謂詞數(shù)，可以分為單維關(guān)聯(lián)規(guī)則和多維關(guān)聯(lián)規(guī)則兩類。若關(guān)聯(lián)規(guī)則的前項(xiàng)和后項(xiàng)包含兩個(gè)或更多的謂詞，則為多維關(guān)聯(lián)規(guī)則。多維關(guān)聯(lián)規(guī)則由于涉及多個(gè)謂詞，每個(gè)謂詞各自包含自身的項(xiàng)目集合，因此挖掘過程需要從多維事務(wù)集中搜索頻繁謂詞集。

典型的多維Apriori 算法采用的方法是在連接頻繁集生成候選集時(shí)，提前判斷連接之后的結(jié)果中是否存在重復(fù)的維度屬性，若不重復(fù)則進(jìn)行連接并根據(jù)Apriori 性質(zhì)完成剪枝，重復(fù)則取消本次連接。這是由于存在重復(fù)維度的候選集在事務(wù)集中并不存在，刪減此類候選集，可有效避免后續(xù)無意義的數(shù)據(jù)庫掃描計(jì)數(shù)操作所導(dǎo)致的算法開銷，提高了多維關(guān)聯(lián)規(guī)則的挖掘效率。除此之外，研究人員關(guān)于多維關(guān)聯(lián)規(guī)則挖掘算法還進(jìn)行了其他改進(jìn)方向的研究[10-14]，主要研究成果包括通過將多維事務(wù)集映射到新結(jié)構(gòu)上進(jìn)行挖掘、結(jié)合智能算法等算法改進(jìn)思路，各類算法對(duì)比情況如表1 所示。

由表1 可知，多維Apriori 算法更具有普適性，但因挖掘過程中產(chǎn)生過多候選謂詞集導(dǎo)致掃描數(shù)據(jù)庫次數(shù)較多，影響算法執(zhí)行效率，這促使本文提出MDAC 算法，通過用戶約束條件限制候選謂詞集的產(chǎn)生，減少數(shù)據(jù)庫掃描次數(shù)，同時(shí)能夠保證挖掘結(jié)果更符合用戶的興趣度，減少冗余規(guī)則生成。

2 基于約束的多維Apriori 改進(jìn)算法

Apriori 算法主要分為兩步：第一步是找到數(shù)據(jù)庫中滿足最小置信度閾值的項(xiàng)目集；第二步是找出所有支持度大于閾值的項(xiàng)目集，并找出置信度大于閾值的強(qiáng)關(guān)聯(lián)規(guī)則。傳統(tǒng)多維Apriori 算法的挖掘過程僅僅采用支持度和置信度等客觀條件進(jìn)行控制，缺乏用戶的主動(dòng)參與，導(dǎo)致挖掘結(jié)果缺乏針對(duì)性。通過將約束引入挖掘過程，可以通過用戶興趣控制挖掘流程，進(jìn)而減少部分候選謂詞集的產(chǎn)生，一方面提高了算法執(zhí)行效率，另一方面也保證最終生成用戶感興趣的關(guān)聯(lián)規(guī)則。

現(xiàn)有的基于約束的關(guān)聯(lián)規(guī)則挖掘算法主要包括了MultipleJoins、Reorder、Direct 以及Separate 等算法[15-17]，其中Separate 算法直接生成滿足項(xiàng)約束的頻繁項(xiàng)集，在此基礎(chǔ)上逐層迭代得到全部頻繁項(xiàng)集，相比于其他算法在生成的候選集數(shù)量上更有優(yōu)勢(shì)。本文主要借鑒了Separate 算法的思想，針對(duì)多維Apriori 算法進(jìn)行改進(jìn)。

2.1 相關(guān)定義

假設(shè)D={d1,d2,…,dn}是多維事務(wù)集所有維度的集合，其中維度dk的屬性取值包括{ik1,ik2,…,ikm}，每一個(gè)維度對(duì)應(yīng)規(guī)則中的一個(gè)謂詞。

挖掘算法在上述事務(wù)集上搜索頻繁謂詞集L，若其中包含謂詞數(shù)為k，則稱為頻繁k謂詞集，記作Lk。

用戶可對(duì)謂詞進(jìn)行約束，并采用布爾表達(dá)式的形式進(jìn)行表示，如(A∧B) ∨C，該式表明約束條件為“包含謂詞A和B或包含謂詞C的多維關(guān)聯(lián)規(guī)則”。進(jìn)一步針對(duì)謂詞的取值進(jìn)行約束，則如(A=a1) ∧B，表示“包含謂詞A和B且謂詞A取值為a1的多維關(guān)聯(lián)規(guī)則”。

2.2 改進(jìn)方法

上文提到，經(jīng)典的 Apriori 算法對(duì)數(shù)據(jù)庫進(jìn)行了多次遍歷，為此形成了大量的候選集，給系統(tǒng) I/O 產(chǎn)生了比較大的負(fù)載，對(duì)系統(tǒng)內(nèi)存的調(diào)動(dòng)也有較大的壓力。MDAC 通過對(duì)數(shù)據(jù)庫進(jìn)行壓縮來改進(jìn) Apriori 算法，根據(jù)Apriori 性質(zhì)的定義，頻繁謂詞集的任意非空子集也必定是頻繁的，由此可以推出，若某一謂詞集是非頻繁的，那么包含該謂詞集的任意超集也同樣是非頻繁的。

因此，為了縮減候選謂詞集以達(dá)到提高挖掘效率的目的，MDAC 根據(jù)用戶約束條件，例如針對(duì)規(guī)則中謂詞的約束或是更進(jìn)一步針對(duì)某個(gè)謂詞取值的約束，確定滿足用戶約束的頻繁謂詞集，在此基礎(chǔ)上，再將其余未約束維度加入進(jìn)來，逐層迭代搜索符合約束條件的所有頻繁謂詞集。依照上述思想，MDAC 掃描數(shù)據(jù)庫次數(shù)大大減少，挖掘結(jié)果也更具有針對(duì)性。

具體來說，首先依據(jù)用戶約束條件，將多維事務(wù)集依照維度進(jìn)行劃分，選取僅包含被約束維度數(shù)據(jù)的部分事務(wù)集，稱為約束事務(wù)集。之后掃描約束事務(wù)集，確定滿足用戶約束條件和支持度要求的頻繁謂詞集及其支持度計(jì)數(shù)。同時(shí)記錄包含頻繁謂詞集的事務(wù)ID，利用該事務(wù)ID 集合（即全部事務(wù)ID 集合的一個(gè)子集）可對(duì)事務(wù)集進(jìn)行刪減，將已確定不滿足約束條件的事務(wù)提前剔除，事務(wù)數(shù)量的減少可以有效加快后續(xù)掃描數(shù)據(jù)庫的速度。然后，以滿足約束的頻繁謂詞集為基礎(chǔ)，與其他未約束維度下的頻繁1 謂詞集進(jìn)行連接，生成新的頻繁謂詞集，再不斷迭代直到不再產(chǎn)生新的謂詞集為止，過程中同樣利用Apriori 性質(zhì)完成剪枝。

相比于多維Apriori 算法，MDAC 通過約束確定了用戶感興趣的頻繁謂詞集，之后通過連接與剪枝等操作產(chǎn)生的候選謂詞集均是該頻繁謂詞集的超集，MDAC 一方面可以避免無關(guān)謂詞集的產(chǎn)生，減少數(shù)據(jù)庫掃描次數(shù)；另一方面也基于約束盡早地刪減了數(shù)據(jù)集中事務(wù)的數(shù)量，降低了掃描數(shù)據(jù)庫的開銷。最終得到的全體頻繁謂詞集，既滿足最小支持度閾值要求又符合用戶約束，可由此生成用戶感興趣的多維關(guān)聯(lián)規(guī)則。

2.3 算法描述

在算法運(yùn)行之前，預(yù)先設(shè)置最小支持度閾值min_sup 和最小置信度閾值min_conf，以及用戶約束條件。根據(jù)約束條件，從多維事務(wù)集T選取約束事務(wù)集Tcstr。具體挖掘過程如下：

（1）掃描Tcstr，得到滿足約束的各謂詞集及支持度計(jì)數(shù)，并與min_sup 進(jìn)行對(duì)比，得到頻繁謂詞集Lcstr，同時(shí)記錄包含頻繁謂詞集的事務(wù)ID 集合Tid；

（2）根據(jù)步驟（1）得到的Tid，對(duì)事務(wù)集進(jìn)行刪減，僅保留Tid部分，得到刪減后的事務(wù)集T′；

（3）針對(duì)刪減后的事務(wù)集T′，搜索未約束維度下的頻繁1 謂詞集F；

（4）連接Lcstr和F，生成候選k謂詞集Ck；

（5）根據(jù)Ck掃描T′相應(yīng)維度并計(jì)數(shù)，得到頻繁k謂詞集Lk；

（6）由Lk連接生成候選k+1 謂詞集Ck+1，連接過程判斷是否有重復(fù)維度，若重復(fù)則取消本次連接，并利用Apriori 性質(zhì)剪枝；

（7）根據(jù)Ck+1掃描T′相應(yīng)維度并計(jì)數(shù)，得到頻繁k+1謂詞集Lk+1；

（8）循環(huán)步驟（6）和步驟（7），直到不產(chǎn)生新的候選謂詞集，最終得到全部頻繁謂詞集L；

（9）根據(jù)最小置信度閾值min_conf，生成多維關(guān)聯(lián)規(guī)則集。

因此，基于約束的多維Apriori 改進(jìn)算法MDAC 的挖掘過程如圖1 所示。

圖1 基于約束的多維Apriori 改進(jìn)算法挖掘流程

上述算法流程中，步驟（6）由頻繁k-1 謂詞集Lk-1連接生成候選k謂詞集Ck的偽代碼示意如下：

在最終得到滿足用戶約束條件的頻繁謂詞集L后，即可根據(jù)最小置信度閾值生成多維關(guān)聯(lián)規(guī)則。需要說明的是，此時(shí)若用戶對(duì)于被約束謂詞在規(guī)則中出現(xiàn)的位置同樣提出了要求，那么可以在規(guī)則生成過程中限定關(guān)聯(lián)規(guī)則的模式，例如要求被約束的謂詞出現(xiàn)在規(guī)則的右部，形如{A,B,…} ?CSTR，那么相應(yīng)的規(guī)則生成偽代碼示意如下：

輸入：頻繁謂詞集L、最小置信度閾值 min_conf；

輸出：關(guān)聯(lián)規(guī)則集R。

3 實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)所用數(shù)據(jù)來自某第三方FPGA 評(píng)測(cè)機(jī)構(gòu)，包含多種FPGA 測(cè)試工具結(jié)果、經(jīng)測(cè)試人員分析確認(rèn)后的FPGA 代碼設(shè)計(jì)缺陷信息等多個(gè)維度數(shù)據(jù)，實(shí)驗(yàn)應(yīng)用基于約束的多維Apriori 算法，期望發(fā)現(xiàn)FPGA 代碼缺陷與測(cè)試工具結(jié)果之間的關(guān)聯(lián)關(guān)系。

在進(jìn)行挖掘之前為了給挖掘算法提供更高質(zhì)量的數(shù)據(jù)，需要先對(duì)采集到的原始數(shù)據(jù)進(jìn)行預(yù)處理。首先針對(duì)數(shù)據(jù)采集過程中種種原因?qū)е碌臄?shù)據(jù)缺失、數(shù)據(jù)重復(fù)等問題進(jìn)行數(shù)據(jù)清理，然后將來自不同數(shù)據(jù)源的數(shù)據(jù)進(jìn)行集成，并檢測(cè)屬性間的相關(guān)性，以刪減掉冗余屬性，最后再將其中的數(shù)值型數(shù)據(jù)離散化，以便于得到更好挖掘效果。

經(jīng)過數(shù)據(jù)處理后得到的FPGA 代碼缺陷事務(wù)數(shù)據(jù)庫共有事務(wù)38 942個(gè)，包含4 個(gè)數(shù)據(jù)維度。本文采用R 語言進(jìn)行算法的實(shí)現(xiàn)，為了證明MDAC 的性能，本節(jié)將MDAC 與未引入約束的多維Apriori 算法進(jìn)行對(duì)比，其余實(shí)驗(yàn)設(shè)置保持相同，所有實(shí)驗(yàn)均進(jìn)行了10次，實(shí)驗(yàn)結(jié)果為10 次實(shí)驗(yàn)的平均值。

假設(shè)用戶期望發(fā)現(xiàn)與FPGA 代碼缺陷數(shù)據(jù)中缺陷類型維度相關(guān)的多維關(guān)聯(lián)規(guī)則，約束條件設(shè)置為“包含謂詞缺陷類型的關(guān)聯(lián)規(guī)則”。在不同的最小支持度閾值min_sup 條件下，多維Apriori 算法與引入約束后的改進(jìn)算法MDAC 在頻繁謂詞集搜索過程上的時(shí)間開銷對(duì)比如圖2 所示。

圖2 不同支持度下算法時(shí)間開銷對(duì)比示意圖

由圖2 中可以看出，隨著最小支持度閾值設(shè)置的變化，MDAC 算法在搜索頻繁謂詞集的過程中，通過縮減事務(wù)集以及壓縮不符合約束的候選謂詞集，有效減小了時(shí)間開銷，相比于多維Apriori 算法，MDAC 平均減少時(shí)間開銷幅度約為46.85%。并且，由于用戶可以通過加強(qiáng)對(duì)于關(guān)聯(lián)規(guī)則結(jié)果的約束，消減更多不滿足約束的事務(wù)以及候選謂詞集，降低掃描數(shù)據(jù)庫帶來的開銷，進(jìn)一步提高了算法效率。

除去時(shí)間開銷降低之外，MDAC 算法在生成頻繁謂詞集數(shù)量方面同樣有所變化。假設(shè)約束條件同樣設(shè)置為“缺陷類型”維度，在不同支持度閾值條件下，不考慮頻繁1 謂詞集（頻繁1 謂詞集不用于生成多維關(guān)聯(lián)規(guī)則），兩個(gè)算法搜索得到的頻繁謂詞集數(shù)量對(duì)比情況如圖3 所示。

圖3 不同支持度下頻繁謂詞集生成數(shù)量對(duì)比示意圖

在不同支持度閾值下，基于約束的改進(jìn)算法MDAC搜索得到的頻繁謂詞集，相比未引入約束的多維Apriori算法而言，謂詞集數(shù)量普遍下降，降低幅度約為41.06%。此處以最小支持度閾值設(shè)置為16%為例進(jìn)行進(jìn)一步對(duì)比，多維Apriori 算法挖掘得到的頻繁謂詞集如表2 所示，而MDAC 算法挖掘出的頻繁謂詞集如表3所示。

表3 基于約束的改進(jìn)算法生成頻繁謂詞集

由表2、表3 可知，通過引入約束減少頻繁謂詞集數(shù)量的同時(shí)，用戶感興趣的包含缺陷類型維度屬性的頻繁謂詞集也并沒有出現(xiàn)任何錯(cuò)誤或者遺漏的情況，相比于多維Apriori 算法產(chǎn)生的頻繁謂詞集，減少的部分謂詞集均不滿足用戶約束條件，對(duì)于用戶感興趣的多維關(guān)聯(lián)規(guī)則挖掘結(jié)果不會(huì)產(chǎn)生影響。

4 結(jié)論

本文提出基于約束的多維Apriori 改進(jìn)算法MDAC，該算法通過將用戶約束引入挖掘過程，縮減候選謂詞集的產(chǎn)生，提高了算法執(zhí)行效率，并減少了冗余規(guī)則的產(chǎn)生，彌補(bǔ)了原算法缺乏用戶主動(dòng)控制的不足。通過實(shí)驗(yàn)對(duì)比，證明了該算法相比于傳統(tǒng)的多維Apriori 算法，從頻繁謂詞集的搜索效率以及挖掘結(jié)果的準(zhǔn)確性方面均獲得了改善。