一種改進(jìn)的Apriori算法在精準(zhǔn)扶貧中的應(yīng)用研究

摘 要：隨著精準(zhǔn)扶貧建檔立卡工作的實(shí)施，精準(zhǔn)扶貧系統(tǒng)已積累了大量數(shù)據(jù)，利用高效的關(guān)聯(lián)規(guī)則算法挖掘其中隱含的有用信息對(duì)助力精準(zhǔn)扶貧工作具有重要意義。本文針對(duì)貧困戶建檔立卡數(shù)據(jù)的數(shù)據(jù)重復(fù)率高，屬性多樣特點(diǎn)，提出一種改進(jìn)的Apriori算法，利用對(duì)矩陣的數(shù)據(jù)結(jié)構(gòu)和集合的相關(guān)性質(zhì)來(lái)構(gòu)建候選項(xiàng)集，避免重復(fù)掃描數(shù)據(jù)庫(kù)以及逐層的剪枝連接運(yùn)算，提高算法挖掘效率;通過(guò)對(duì)實(shí)際貧困戶建檔立卡數(shù)據(jù)進(jìn)行挖掘，證明了該算法在最小支持度閾值較低的條件下挖掘效率優(yōu)于傳統(tǒng)Apriori算法。

關(guān)鍵詞：關(guān)聯(lián)規(guī)則; 頻繁項(xiàng)集;精準(zhǔn)扶貧;Apriori算法

中圖分類號(hào)：TP301.6

文獻(xiàn)標(biāo)識(shí)碼： A

近年來(lái)，基于互聯(lián)網(wǎng)的扶貧工作積累了大量的數(shù)據(jù)，如何有效利用這些數(shù)據(jù)來(lái)推動(dòng)扶貧工作的開(kāi)展成為了扶貧部門(mén)亟待解決的問(wèn)題。為幫助真正的貧困人口擺脫貧困，精準(zhǔn)扶貧工作需對(duì)大量扶貧數(shù)據(jù)進(jìn)行深入挖掘，精確瞄準(zhǔn)致貧原因[1]。Apriori[2]算法作為關(guān)聯(lián)分析領(lǐng)域最經(jīng)典的算法，目前許多關(guān)聯(lián)分析算法都是在其基礎(chǔ)上演化而來(lái)[3-6]，目的是為了解決Apriori算法產(chǎn)生大量候選項(xiàng)集以及多次掃描數(shù)據(jù)庫(kù)所造成的算法運(yùn)行效率問(wèn)題，此類改進(jìn)算法對(duì)于候選項(xiàng)集的構(gòu)建大多還是沿用Apriori算法中的連接和剪枝思想，但當(dāng)事物數(shù)據(jù)庫(kù)中的每個(gè)事物都包含有較多的數(shù)據(jù)項(xiàng)且數(shù)據(jù)項(xiàng)重復(fù)率較高時(shí)，在最小支持度閾值較低情況下，Apriori算法的連接和剪枝效率就會(huì)大大降低[7-8]，從而影響算法挖掘性能。

傳統(tǒng)Apriori算法為挖掘最大頻繁項(xiàng)集，需進(jìn)行逐步地剪枝并且需要頻繁掃描數(shù)據(jù)庫(kù)[9]。為了解決這兩個(gè)問(wèn)題，許多學(xué)者從不同的角度對(duì)Apriori算法進(jìn)行改進(jìn)，例如從減少掃描數(shù)據(jù)庫(kù)造成的I/O開(kāi)銷(xiāo)的角度，有學(xué)者提出了基于矩陣的改進(jìn)Apriori算法[10-12];文獻(xiàn)[10]提出一種基于矩陣和權(quán)重的改進(jìn)算法，利用0￣1矩陣來(lái)表示事物數(shù)據(jù)庫(kù)，避免對(duì)數(shù)據(jù)庫(kù)的重復(fù)掃描;文獻(xiàn)[11]通過(guò)增加向量的方式減小矩陣規(guī)模，避免多次掃描數(shù)據(jù)庫(kù);文獻(xiàn)[12]提出利用事物矩陣和項(xiàng)集矩陣相乘來(lái)改進(jìn)反復(fù)掃描數(shù)據(jù)庫(kù)的問(wèn)題，以此來(lái)提高算法運(yùn)行效率。上述算法在挖掘頻繁項(xiàng)集過(guò)程中，在剪枝效率高的前提下均能獲得較高挖掘效率，但當(dāng)剪枝效果不理想時(shí)，為確定不同長(zhǎng)度項(xiàng)集的支持度信息而多次處理和掃描矩陣反而會(huì)降低算法性能。

在貧困戶的建檔立卡數(shù)據(jù)中，同一地區(qū)的貧困戶由于地理環(huán)境、生活習(xí)慣、經(jīng)濟(jì)發(fā)展等因素，通常會(huì)具有許多相同的貧困特征，從而導(dǎo)致貧困特征事物數(shù)據(jù)庫(kù)具有貧困特征項(xiàng)多且重復(fù)率高的特點(diǎn)，傳統(tǒng)Apriori算法在處理此類數(shù)據(jù)庫(kù)時(shí)，挖掘效率較低。針對(duì)這一問(wèn)題，本文將事物數(shù)據(jù)庫(kù)轉(zhuǎn)換為矩陣表示的同時(shí)，通過(guò)計(jì)算矩陣行向量所代表集合的交集和子集來(lái)構(gòu)造候選項(xiàng)集，避免逐步的剪枝連接和重復(fù)掃描數(shù)據(jù)庫(kù)，解決了傳統(tǒng)Apriori算法在較低最小支持度閾值條件挖掘效率低的問(wèn)題。

1"頻繁項(xiàng)集挖掘

1.1"基本概念

（1）項(xiàng)與項(xiàng)集

設(shè)I={I1，I2，…，Im}表示m個(gè)不同項(xiàng)目的集合，則其中的每個(gè)Ik（k=1，2，…，m）稱為項(xiàng)，由每個(gè)Ik（k=1，2，…，m）所構(gòu)成的集合I則稱為項(xiàng)集，集合中所容納的項(xiàng)的數(shù)目則表示該項(xiàng)集的長(zhǎng)度，長(zhǎng)度為m的項(xiàng)集則稱之為m￣項(xiàng)集。

（2）事物與事物數(shù)據(jù)庫(kù)

事物T是項(xiàng)集I的子集[13]，即T={T1，T2，…，Tk}，Tk∈I，表示數(shù)據(jù)庫(kù)當(dāng)中記錄的集合，常用標(biāo)識(shí)符TID來(lái)表示，而所有事物的集合則稱為事物數(shù)據(jù)庫(kù)，常用D來(lái)表示。

（3）項(xiàng)集支持度與最小支持度

設(shè)XI為數(shù)據(jù)項(xiàng)集，k為X在事物數(shù)據(jù)庫(kù)D中出現(xiàn)的次數(shù)，n為D中所包含的事物的總數(shù)，則定義X的支持度（Support）為

Support（X）=kn。（1）

最小支持度（Minimum Support）是指在挖掘關(guān)聯(lián)規(guī)則的過(guò)程中，要求項(xiàng)集滿足的最低支持度閾值，當(dāng)某項(xiàng)集的支持度值高于該閾值時(shí)，定義該項(xiàng)集為頻繁項(xiàng)集[14]，否則定義為非頻繁項(xiàng)集。

（4）關(guān)聯(lián)規(guī)則與置信度

關(guān)聯(lián)規(guī)則可表示為：AB，其中AI，BI，A∩B≠，它的含義是，若項(xiàng)集A在某一事物中出現(xiàn)，則在同樣事物中一定存在項(xiàng)集B，且把A稱作該規(guī)則的先決條件，B稱為規(guī)則的結(jié)果，規(guī)則AB的置信度（Confidence）定義為：

confidence（AB）=Support（A∪B）Support（A）。（2）

最小置信度[15]（Minimum Confidence）則表示關(guān)聯(lián)規(guī)則必須滿足的最低置信度值，也即是關(guān)聯(lián)規(guī)則的最低可靠性。

1.2"相關(guān)性質(zhì)

性質(zhì)1"若一個(gè)項(xiàng)集為頻繁項(xiàng)集，則該項(xiàng)集的全部非空子集都必為頻繁項(xiàng)集。

性質(zhì)2"任何非頻繁項(xiàng)集的超集一定是非頻繁項(xiàng)集。

性質(zhì)3"若一個(gè)事物中不存在任何的頻繁k￣項(xiàng)集，則該事物中也必然沒(méi)有任何的頻繁（k+1）￣項(xiàng)集存在。

性質(zhì)4"若一個(gè)非空集合為另一集合的子集，則他們的交集等于該集合本身。

性質(zhì)5"若有非空集合A，B，C，D，其中B為A的子集，若A∩C=D，則B∩C∈D。

性質(zhì)6"若事物中存在的數(shù)據(jù)項(xiàng)數(shù)目為k，則長(zhǎng)度大于k的頻繁項(xiàng)集不可能存在于當(dāng)前事物中。

2"算法改進(jìn)

2.1"Apriori_BOMS算法

（1）假設(shè)輸入數(shù)據(jù)庫(kù)D包含m條記錄，記錄中所包含的數(shù)據(jù)項(xiàng)總數(shù)為n，則將D轉(zhuǎn)換為m×n階矩陣，設(shè)置最小支持度閾值min_support，根據(jù)性質(zhì)2，將不滿足支持度閾值要求的元素所在列刪除，得到初始化矩陣以及頻繁1￣項(xiàng)集L1;

（2）提取所得矩陣每行不為零的元素所組成的項(xiàng)集（至少包含兩個(gè)元素，否則舍去），并計(jì)算所得項(xiàng)集在矩陣中的支持度，將項(xiàng)集及其支持度信息存儲(chǔ)于字典original_dic，其中支持度高于所設(shè)閾值的項(xiàng)集則定義為矩陣中的已確定初始頻繁項(xiàng)集sure。

（3）由于不同項(xiàng)集可能會(huì)產(chǎn)生相同的子集，要確定這些相同子集的支持度，需將其單獨(dú)提取出來(lái);此外，對(duì)于非頻繁項(xiàng)集，若其子集為頻繁項(xiàng)集，則其子集必然會(huì)出現(xiàn)在矩陣的其他行向量當(dāng)中;綜上所述，通過(guò)求解（2）中所得項(xiàng)集間的交集（產(chǎn)生的交集至少含有兩個(gè)元素，否則舍去）來(lái)獲得初始候選項(xiàng)集，利用性質(zhì)5，滿足條件的項(xiàng)集B則無(wú)需求解交集;若相交結(jié)果中包含有（2）中已確定的頻繁項(xiàng)集，由于其支持度已知，則將其從相交結(jié)果中刪除。

（4）為獲得最終候選項(xiàng)集，在得到初始候選項(xiàng)集后，求解其中所有項(xiàng)集的子集（該子集至少包含兩個(gè)元素，否則舍去），通過(guò)集合的并集運(yùn)算過(guò)濾其中的重復(fù)項(xiàng)，若產(chǎn)生的子集已存在于original_dic中，因其支持度信息已由（2）中求得，因此將其從本步驟所得結(jié)果中舍去，以此得到一個(gè)包含交集結(jié)果以及其滿足條件的子集的列表not_sure，列表中的集合則可看作為候選項(xiàng)集，通過(guò)判斷not_sure中的項(xiàng)集與original_dic中的項(xiàng)集是否為包含關(guān)系，則可確定not_sure中所有項(xiàng)集的支持度信息，并篩選出頻繁項(xiàng)集。

（5）根據(jù)步驟（2）得到的初始確定頻繁項(xiàng)集sure，求其中各項(xiàng)集的子集（至少包含兩個(gè)元素），并將其子集集合與not_sure做相交運(yùn)算，得到的交集再與該項(xiàng)集本身做對(duì)稱交集運(yùn)算即可快速得到該項(xiàng)集不存在于not_sure中的子集，該子集必為頻繁項(xiàng)集且支持度跟隨其本身，無(wú)需掃描矩陣即可得到滿足條件子集的支持度信息，至此完成所有頻繁項(xiàng)集挖掘。

算法流程圖如圖1所示。

2.2"Apriori_BOMS算法實(shí)例

表1為貧困戶貧困特征示例數(shù)據(jù)，其中包含5條貧困戶紀(jì)錄，共6個(gè)貧困特征項(xiàng)。

將其中各個(gè)貧困特征賦予特定貧困特征標(biāo)識(shí)Ii，每個(gè)貧困戶對(duì)應(yīng)事物數(shù)據(jù)庫(kù)中的一個(gè)事物Ti，如表2所示。

設(shè)置最小支持度閾值為0.3，根據(jù)式（1），因?yàn)閟upport（I6）=1/5=0.2lt;0.3，則將矩陣中低于最小支持度閾值的元素所在列刪除得到初始化矩陣A1以及頻繁1￣項(xiàng)集及其支持度信息，L1={{1}： 08， {2}： 0.8， {3}： 0.6， {4}： 0.8， {5}： 1};

將矩陣中原始項(xiàng)集及其支持度信息存貯在字典original_dic中，則original_dic={{1， 2， 3， 4， 5}： 0.2， {1， 3， 5}： 0.4， {1， 2， 4， 5}： 0.6， {2， 3， 4， 5}： 0.4}，得到確定的初始頻繁項(xiàng)集及其支持度信息：sure={{1， 3， 5}： 0.4，{1， 2， 4， 5}： 06， {2， 3， 4， 5}： 0.4};

求解original_dic中項(xiàng)集間滿足條件的交集commen={{1， 5}， {3， 5}， {2， 4， 5}};計(jì)算其中各項(xiàng)集滿足條件子集的支持度信息：{{4， 5}： 08，{1， 5}：0.8，{2， 4， 5}： 0.8， {2， 5}： 0.8， {2， 4}： 0.8， {3， 5}： 0.6};

根據(jù)頻繁項(xiàng)集的子集必為頻繁項(xiàng)集，求初始頻繁項(xiàng)集sure={{1， 3， 5}： 0.4，{1， 2， 4， 5}： 0.6， {2， 3， 4， 5}： 0.4}中所有項(xiàng)集的子集，刪除已存在于not_sure以及original_dic中的子集后，其余子集支持度跟隨原項(xiàng)集本身，則可得到sure中各項(xiàng)集及其滿足條件子集的支持度信息：

sure={{1， 3}：0.4， {1， 3， 5}： 0.4，{1， 2}：06， {1， 4}：0.6， {1， 4， 5}：0.6， {1， 2， 4}：0.6， {1， 2， 5}：0.6， {1， 2， 4， 5}： 0.6， {2， 3， 5}：04， {2， 3}：0.4， {2， 3， 4}：0.4， {3， 4， 5}：0.4， {2， 3， 4， 5}：0.4， {3， 4}： 0.4}。

合并每一步求得的頻繁項(xiàng)集，整理得到各個(gè)長(zhǎng)度頻繁項(xiàng)集及其支持度信息：

L1={{I1}：0.8;{I2}：0.8;{I3}：0.6;{I4}：0.8;{I5}：1};

L2={{I1，I2}：0.6;{I1，I3}：0.4;{I1，I4}：0.6;{I1，I5}：0.8;{I2，I3}：0.4;{I2，I4}：0.8;{I2，I5}：0.8;{I3，I4}：0.4;{I3，I5}：0.6;{I4，I5}：0.8};

L3={{I2，I4，I5}：0.8;{I1，I3，I5}：0.4;

{I1，I4，I5}：0.6;{I1，I2，I4}：0.6;

{I1，I2，I5}：0.6;{I2，I3，I5}：0.4;

{I2，I3，I4}：0.4;{I3，I4，I5}：0.4};

L4={{I1，I2，I4，I5}：0.6;{I2，I3，I4，I5}：0.4}。

得到頻繁項(xiàng)集及其支持度信息后，根據(jù)式（2）計(jì)算相應(yīng)的關(guān)聯(lián)規(guī)則的置信度，例如：

Confidence（家庭年純收入低住房為危房）=

Confidence（I1I4）

=Support（{I1，I4}）Support（{I1}）=0.60.8=075。

設(shè)置最小置信度值為0.7，選取結(jié)果中部分規(guī)則如表3所示。

根據(jù)上述算法實(shí)例應(yīng)用，可知對(duì)扶貧數(shù)據(jù)進(jìn)行挖掘，可發(fā)現(xiàn)各不同貧困戶之間潛在的關(guān)聯(lián)信息，能夠更全面地考慮不同貧困戶的需求，探索扶貧工作的內(nèi)在規(guī)律;并且，利用所挖掘的關(guān)聯(lián)信息有利于實(shí)現(xiàn)扶貧方式、內(nèi)容與扶貧對(duì)象的有效匹配，合理分配扶貧資源，提高扶貧工作的效率與精度。

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

為比較本文所提出的Apriori_BOMS算法與傳統(tǒng)Apriori算法的性能，在相同實(shí)驗(yàn)環(huán)境下，利用兩

種算法對(duì)相同貧困數(shù)據(jù)集中的頻繁項(xiàng)集進(jìn)行挖掘。

3.1"實(shí)驗(yàn)環(huán)境與數(shù)據(jù)

操作系統(tǒng)：64位Windows7操作系統(tǒng);處理器：Intel（R） Core（TM） i5￣6500 CPU， 3.20 GHz， 8 Gb內(nèi)存;兩種算法均采用Python語(yǔ)言編程。

實(shí)驗(yàn)數(shù)據(jù)為貴陽(yáng)市某區(qū)7319條貧困戶建檔立卡數(shù)據(jù);該數(shù)據(jù)包含貧困戶家庭情況調(diào)查的多個(gè)屬性，為使得數(shù)據(jù)滿足算法輸入要求，需對(duì)原始數(shù)據(jù)進(jìn)行預(yù)處理，首先挑選了該數(shù)據(jù)集中不含有缺失值

以及較有代表性的屬性（如家庭年收入、家庭人均收入、耕地面積、是否飲水困難、住宅面積等）共20個(gè)屬性，并對(duì)每個(gè)屬性值進(jìn)行離散化，若某一條貧困戶數(shù)據(jù)中“是否飲水困難”的屬性值為“是”時(shí)，表示該貧困戶存在飲水困難的貧困特征，因此將屬性值“是”替換為相應(yīng)的特征標(biāo)號(hào)i，反之則置為0;當(dāng)年收入或耕地面積的值低于特定數(shù)值時(shí)，將該值替換為相應(yīng)特征標(biāo)號(hào)i，表示該貧困戶具備此貧困特征，反之則置為0，表示不具有此貧困特征，完成對(duì)屬性值的處理后，得到滿足算法要求的輸入數(shù)據(jù)。

最后，為驗(yàn)證算法通用性，利用UCI數(shù)據(jù)集中的Mushroom數(shù)據(jù)對(duì)算法進(jìn)行測(cè)試，該數(shù)據(jù)集包含8 124條記錄，共22個(gè)屬性，每個(gè)屬性下有2～12個(gè)枚舉值，剔除其中包含有缺省值和僅有兩個(gè)有效枚舉值的屬性（bruises，gill￣attachment，gill￣size，stalk￣shape，stalk￣root，veil￣type），剩余16個(gè)屬性，將每個(gè)屬性下出現(xiàn)次數(shù)低于總記錄數(shù)20%的枚舉值置0，其他枚舉值則置為當(dāng)前屬性的標(biāo)號(hào)，得到用于測(cè)試的輸入數(shù)據(jù)。

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

將Apriori_BOMS算法與傳統(tǒng)Apriori算法在不同大小的數(shù)據(jù)集上進(jìn)行測(cè)試，設(shè)置min_support=30%，實(shí)驗(yàn)結(jié)果如圖2所示。由實(shí)驗(yàn)結(jié)果可看出本文所提出的Apriori_BOMS算法在同等數(shù)據(jù)量的條件下，運(yùn)行時(shí)間明顯低于傳統(tǒng)Apriori算法。

由于最小支持度閾值的改變同樣會(huì)對(duì)算法性能造成影響，實(shí)際往往會(huì)設(shè)置較低的最小支持度閾值，挖掘更多滿足條件的頻繁項(xiàng)集，以此產(chǎn)生適應(yīng)不同約束條件的關(guān)聯(lián)規(guī)則。因此，改變最小支持度閾值，對(duì)比兩種算法性能，實(shí)驗(yàn)結(jié)果如圖3所示。

在最小支持度閾值低于0.34時(shí)，Apriori_BOMS算法挖掘效率明顯高于傳統(tǒng)Apriori算法，最小支持度閾值越小，兩種算法的性能差異越明顯;當(dāng)最小支持度閾值變大使得剪枝效率增加時(shí)，傳統(tǒng)Apriori算法性能才會(huì)改善，而Apriori_BOMS算法受最小支持

度閾值影響較小，性能更加穩(wěn)定;因此，試驗(yàn)結(jié)果驗(yàn)證了本文所提出的算法能夠有效解決傳統(tǒng)Apriori算法在剪枝不理想條件下挖掘效率低的問(wèn)題。

為驗(yàn)證本文所提出的Apriori_BOMS算法相較于傳統(tǒng)Apriori算法在面對(duì)數(shù)據(jù)重復(fù)率高的數(shù)據(jù)集時(shí)仍具備高效的挖掘能力，對(duì)貧困戶建檔立卡數(shù)據(jù)屬性進(jìn)行離散化處理時(shí)，通過(guò)降低設(shè)置屬性標(biāo)號(hào)的數(shù)值，可得到屬性值重復(fù)率更高的數(shù)據(jù)集（貧困戶數(shù)據(jù)集2），相同實(shí)驗(yàn)環(huán)境下，在該數(shù)據(jù)集上測(cè)試兩種算法的挖掘性能，實(shí)驗(yàn)結(jié)果如圖4、圖5所示，Apriori_BOMS性能在密集數(shù)據(jù)集下同樣明顯優(yōu)于傳統(tǒng)Apriori算法。

為證明Apriori_BOMS算法在其他數(shù)據(jù)集上仍具有不錯(cuò)效果，設(shè)置最小支持度閾值為20%，在Mushroom數(shù)據(jù)集上的測(cè)試結(jié)果如圖6、7所示，由實(shí)驗(yàn)結(jié)果可知，Apriori_BOMS算法性能同樣優(yōu)于傳統(tǒng)Apriori算法。

綜上所述，本文提出的Apriori_BOMS算法解決了傳統(tǒng)Apriori在最小支持度閾值較低以及數(shù)據(jù)重復(fù)率高條件下剪枝效果不理想而造成的挖掘效率低的問(wèn)題，并且避免了多次掃描數(shù)據(jù)庫(kù)，節(jié)約了系統(tǒng)的I/O開(kāi)銷(xiāo);在面對(duì)數(shù)據(jù)重復(fù)率高的貧困戶建檔立卡數(shù)據(jù)集時(shí)，在較低的最小支持度閾值條件下仍能更加高效地挖掘數(shù)據(jù)集中隱含的有用信息，為精準(zhǔn)扶貧工作提供助力。

4"結(jié)語(yǔ)

本文利用數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則挖掘算法來(lái)發(fā)現(xiàn)貧困戶建檔立卡數(shù)據(jù)中不同貧困特征之間潛在的聯(lián)系，為精準(zhǔn)扶貧工作提供更直觀的數(shù)據(jù)參考。由于貧困戶建檔立卡數(shù)據(jù)具有數(shù)據(jù)重復(fù)率高、屬性多樣的特點(diǎn)，傳統(tǒng)Apriori算法在面對(duì)此類數(shù)據(jù)庫(kù)時(shí)挖掘效率較低。因此，本文引入矩陣及集合間運(yùn)算的概念，提出一種改進(jìn)Apriori算法，通過(guò)在實(shí)際貧困戶建檔立卡數(shù)據(jù)及Mushroom數(shù)據(jù)集上進(jìn)行測(cè)試，驗(yàn)證了Apriori_BOMS算法的有效性，同時(shí)，證明了該算法性能優(yōu)于傳統(tǒng)Apriori算法，在實(shí)際應(yīng)用中，能夠更高效地挖掘由貧困特征構(gòu)成的頻繁項(xiàng)集，支撐貧困特征關(guān)聯(lián)規(guī)則的生成，助力精準(zhǔn)扶貧工作的實(shí)施。如何對(duì)算法做進(jìn)一步優(yōu)化使其具備更高挖掘效率并且適用于不同數(shù)據(jù)集的挖掘?qū)⑹窍乱徊街饕芯磕繕?biāo)。

參考文獻(xiàn)：

[1]丁翔， 丁榮余， 金帥. 大數(shù)據(jù)驅(qū)動(dòng)精準(zhǔn)扶貧：內(nèi)在機(jī)理與實(shí)現(xiàn)路徑[J]. 現(xiàn)代經(jīng)濟(jì)探討， 2017（12）： 119-125.

[2]AGRAWAL R， IMIELINSKI T， SWAMI A N. Mining association rules between sets of items in large databases[C]// Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 1993： 207-216.

[3]文武， 郭有慶. 結(jié)合遺傳算法的Apriori算法改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(jì)， 2019（7）： 1922-1926.

[4]李龍， 劉澎， 張可佳， 等. 改進(jìn)的Apriori算法的研究與應(yīng)用[J]. 計(jì)算機(jī)與數(shù)字工程， 2019， 47（6）： 1293-1297.

[5]周凱， 顧洪博， 李愛(ài)國(guó). 基于關(guān)聯(lián)規(guī)則挖掘Apriori算法的改進(jìn)算法[J]. 陜西理工大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2018， 34（5）： 40-44.

[6]JI Q ， ZHANG S . Research on sensor network optimization based on improved Apriori algorithm[J]. EURASIP Journal on Wireless Communications and Networking， 2018， 2018（1）： 258.

[7]于守健， 周羿陽(yáng). 基于前綴項(xiàng)集的Apriori算法改進(jìn)[J]. 計(jì)算機(jī)應(yīng)用與軟件， 2017， 34（2）： 290-294.

[8]韓天鵬， 白玲玲， 王浩. 基于候選項(xiàng)集剪枝的Apriori算法的研究[J]. 阜陽(yáng)師范學(xué)院學(xué)報(bào)（自然科學(xué)版）， 2014， 31（4）： 79-83.

[9]朱付保， 白慶春， 湯萌萌， 等. 基于改進(jìn)Apriori算法的鐵路軌道質(zhì)量分析與評(píng)價(jià)[J]. 微電子學(xué)與計(jì)算機(jī)， 2015， 32（10）： 159-162.

[10]邊根慶， 王月. 一種基于矩陣和權(quán)重改進(jìn)的Apriori算法[J]. 微電子學(xué)與計(jì)算機(jī)， 2017， 34（1）： 136-140.

[11劉芳， 吳廣潮. 一種基于壓縮矩陣的改進(jìn)Apriori算法[J]. 山東大學(xué)學(xué)報(bào)（工學(xué)版）， 2018， 48（6）： 82-88.

[12]王蒙， 方睿， 鄒書(shū)蓉. 基于矩陣相乘的Apriori改進(jìn)算法[J]. 計(jì)算機(jī)與數(shù)字工程， 2018， 46（10）： 1974-1979.

[13]張璽.數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則算法的研究與改進(jìn)[D]. 北京： 北京郵電大學(xué)， 2015.

[14]彭敏， 黃佳佳， 朱佳暉， 等. 基于頻繁項(xiàng)集的海量短文本聚類與主題抽取[J]. 計(jì)算機(jī)研究與發(fā)展， 2015， 52（9）： 1941-1953.

[15]劉毓， 李莎. 一種基于權(quán)重的Apriori改進(jìn)算法[J].西安郵電大學(xué)學(xué)報(bào)， 2017， 22（4）： 95-100.

（責(zé)任編輯：周曉南）

An Application Research of an Improved Apriori

Algorithm in Targeted Poverty Alleviation

HE Qing*， LIU Liang

（Institute of Big Data and Information Engineering， Guizhou University， Guiyang 550025，China）

Abstract：

With the implementation of the targeted poverty alleviation archiving work， the targeted poverty alleviation system has accumulated a larger amount of data. It is of great significance to use efficient association rules algorithm to mine the hidden useful information. "The text aims at the characteristics of high repetition rate and diverse attributes of archived card data of poor households. An improved Apriori algorithm is proposed to construct candidate item sets by utilizing the data structure of the matrix and the relevant properties of the set， so as to avoid repeated scanning of the database and pruning connection operation layer by layer， so as to improve the efficiency of algorithm mining. By mining the data of the actual family in poverty， it is proved that the mining efficiency of this algorithm is better than traditional Apriori algorithm under the condition of low minimum support threshold.

Key words：

association rules; candidate item sets ; targeted poverty alleviation; Apriori algorithm