[發(fā)明專利]一種基于布爾矩陣和二進(jìn)制編碼改進(jìn)的關(guān)聯(lián)規(guī)則Apriori算法

在審

• 申請(qǐng)?zhí)枺?/td>: 202111113072.3
• 申請(qǐng)日: 2021-09-23
• 公開（公告）號(hào): CN113806424A
• 公開（公告）日: 2021-12-17
• 發(fā)明（設(shè)計(jì)）人: 吳海玲;裴樹軍;張宇
• 申請(qǐng)（專利權(quán)）人: 哈爾濱理工大學(xué)
• 主分類號(hào): G06F16/2458
• 分類號(hào): G06F16/2458;G06F16/22
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發(fā)明提出一種基于布爾矩陣與二進(jìn)制編碼改進(jìn)的關(guān)聯(lián)規(guī)則Apriori算法。通過用布爾矩陣存儲(chǔ)數(shù)據(jù)庫的方式，使得整個(gè)算法對(duì)數(shù)據(jù)庫只進(jìn)行一次掃描操作，然后利用二進(jìn)制編碼之間的“與”運(yùn)算，獲取項(xiàng)集的事務(wù)支持度，同時(shí)增加了非頻繁項(xiàng)集的記錄表，對(duì)候選項(xiàng)集提前剪枝，大大提高了算法的效率。

技術(shù)領(lǐng)域

本發(fā)明涉及一個(gè)基于布爾矩陣和二進(jìn)制編碼改進(jìn)的關(guān)聯(lián)規(guī)則Apriori算法，屬于數(shù)據(jù)挖掘領(lǐng)域。

背景技術(shù)

Apriori算法是最經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法之一，其核心思想就是利用連接產(chǎn)生候選項(xiàng)集，同時(shí)利用最小支持度對(duì)候選項(xiàng)集進(jìn)行剪枝，最終生成頻繁項(xiàng)集，但是隨著數(shù)據(jù)爆發(fā)性的增長，傳統(tǒng)的Aprior算法需要多次掃描數(shù)據(jù)庫并且容易產(chǎn)生大量的候選項(xiàng)集，使得算法效率低下。

因此本發(fā)明提出一種基于布爾矩陣與二進(jìn)制編碼改進(jìn)的關(guān)聯(lián)規(guī)則Apriori算法，通過用布爾矩陣存儲(chǔ)數(shù)據(jù)庫的方式，使得整個(gè)算法對(duì)數(shù)據(jù)庫只進(jìn)行一次掃描操作，然后利用二進(jìn)制編碼之間的“與”運(yùn)算獲取項(xiàng)集的事務(wù)支持度，同時(shí)增加了非頻繁項(xiàng)集的記錄表，對(duì)候選項(xiàng)集提前剪枝，大大提高了算法的效率。

發(fā)明內(nèi)容

為了解決Apriori算法需要多次掃描數(shù)據(jù)庫與產(chǎn)生大量候選項(xiàng)集的缺點(diǎn)，本發(fā)明提出了一種基于布爾矩陣與二進(jìn)制編碼改進(jìn)的關(guān)聯(lián)規(guī)則Apriori算法。

為實(shí)現(xiàn)上述目的，本發(fā)明提供了如下技術(shù)方案：

1.一種基于布爾矩陣和二進(jìn)制編碼改進(jìn)的關(guān)聯(lián)規(guī)則Apriori算法，其特征在于，該方法包括以下步驟：

(1)掃描數(shù)據(jù)庫，生成布爾矩陣，獲得頻繁1-項(xiàng)集；

(2)壓縮布爾矩陣；

(3)提前預(yù)剪枝，同時(shí)建立非頻繁項(xiàng)集的記錄表；

(4)建立輔助表；

(5)更新非頻繁項(xiàng)集記錄表；

(6)縮減算法流程；

(7)壓縮布爾矩陣，預(yù)剪枝，同時(shí)返回到步驟4，直到頻繁k-項(xiàng)集個(gè)數(shù)小于k+1時(shí)，迭代結(jié)束。

2.根據(jù)權(quán)利要求1所述的一種基于布爾矩陣和二進(jìn)制編碼改進(jìn)的關(guān)聯(lián)規(guī)則Apriori算法，其特征在于，所述步驟(1)中，掃描數(shù)據(jù)庫，生成布爾矩陣，獲得頻繁1-項(xiàng)集，具體步驟為：

步驟1-1首先掃描數(shù)據(jù)庫，用布爾矩陣來存儲(chǔ)，行表示事務(wù)id，列表示項(xiàng)，其中矩陣中的a_ij的可能取值為0或1，取值為1就代表此項(xiàng)目存在于事務(wù)中，0就代表不存在。計(jì)算各個(gè)事務(wù)的項(xiàng)目數(shù)，并按這個(gè)值對(duì)矩陣進(jìn)行降序排列，在矩陣最后增加2列，第1列n，n用來記錄每行中“1”的個(gè)數(shù)，第2列w，w用于將事務(wù)數(shù)據(jù)庫中重復(fù)出現(xiàn)的事務(wù)壓縮為1行，從而保證矩陣存儲(chǔ)中每1條事務(wù)信息都不重復(fù)，在矩陣最后增加1行s，s用來記錄每列的和；

步驟1-2根據(jù)布爾矩陣，獲得頻繁1-項(xiàng)集。

3.根據(jù)權(quán)利要求1所述的一種基于布爾矩陣和二進(jìn)制編碼改進(jìn)的關(guān)聯(lián)規(guī)則Apriori算法，其特征在于，所述步驟(2)中，計(jì)算各個(gè)事務(wù)的項(xiàng)目數(shù)，并按這個(gè)值對(duì)矩陣進(jìn)行降序排列，將非頻繁1-項(xiàng)集所在的列刪除，重新計(jì)算矩陣列n的值，按降序重新排列矩陣，同時(shí)在求頻繁k-項(xiàng)集(k≥2)時(shí)，將矩陣中的事務(wù)數(shù)小于k的行直接刪除，重新計(jì)算矩陣中各列的值并重新排列矩陣。

4.根據(jù)權(quán)利要求1所述的一種基于布爾矩陣和二進(jìn)制編碼改進(jìn)的關(guān)聯(lián)規(guī)則Apriori算法，其特征在于，所述步驟(3)中，提前預(yù)剪枝，同時(shí)建立非頻繁項(xiàng)集的記錄表，具體步驟為：

步驟3-1利用“若能生成頻繁k-項(xiàng)集(k≥2)，則頻繁(k-1)-項(xiàng)集中每個(gè)項(xiàng)的個(gè)數(shù)不能小于k-1”的性質(zhì)，對(duì)候選k-項(xiàng)集(k≥2)進(jìn)行剪枝；

步驟3-2建立非頻繁項(xiàng)集的記錄表；