孫 斌 韓艷玲 豐國超

(中國地質(zhì)大學(xué)信息工程學(xué)院 湖北 武漢 430074)

?

Apriori改進(jìn)算法在研究影響土壤反射率因素中的應(yīng)用

孫 斌 韓艷玲 豐國超

(中國地質(zhì)大學(xué)信息工程學(xué)院 湖北 武漢 430074)

首先簡短介紹Apriori算法相關(guān)概念、改進(jìn)算法的理論和實現(xiàn)步驟。繼而通過實例試探性地將其運(yùn)用到研究影響土壤反射率因素的應(yīng)用中。實驗結(jié)果表明：改進(jìn)的Apriori算法不僅提高了產(chǎn)生頻繁項集的效率，而且有效地減少了算法的計算時間。最后，驗證并說明了關(guān)聯(lián)規(guī)則、Apriori及其改進(jìn)算法適用的廣泛性以及有效性。

Apriori算法 土壤反射率 有機(jī)質(zhì) 關(guān)聯(lián)規(guī)則

0 引 言

Apriori算法[1]是由Agrawal等人提出的一種用于挖掘關(guān)聯(lián)規(guī)則中頻繁項集的算法[2]，其最顯著的特征就是應(yīng)用先驗知識即prior knowledge(頻繁項集性質(zhì))通過迭代方法逐層搜索數(shù)據(jù)庫。

Apriori 算法主要存在兩方面的問題: 一是算法在每產(chǎn)生一次候選項集，都必須重新掃描一遍事務(wù)數(shù)據(jù)庫D。對數(shù)據(jù)庫規(guī)模大的情況，掃描數(shù)據(jù)庫的過程將會在外部存儲介質(zhì)和內(nèi)存之間頻繁交換數(shù)據(jù)。二是連接操作和處理候選項目集的測試過程花費(fèi)大量的時間。這些都將使處理的時間復(fù)雜度很大[3]。Apriori的改進(jìn)算法，也都是基于這兩方面考慮的[4]：減少掃描事務(wù)數(shù)據(jù)庫D的次數(shù)以及刪除多余的無用的候選項目集。

1 Apriori算法及其改進(jìn)思想

1.1 算法簡介

在關(guān)聯(lián)規(guī)則中，支持度大于或等于最小支持度的項集稱為頻繁項集，簡稱頻集。為了生成所有頻繁項集，使用了遞歸的方法：先找到頻繁1-項集集合L1，然后用L1找到頻繁2-項集集合L2，接著用L2找L3，直到找不到頻繁K項集為止，找每個Lk都需要對數(shù)據(jù)庫掃描一次。然后通過得到的頻集來產(chǎn)生關(guān)聯(lián)規(guī)則，這些規(guī)則同樣必須滿足不小于最小支持度和最小可信度的條件，滿足該條件的關(guān)聯(lián)規(guī)則就是強(qiáng)關(guān)聯(lián)規(guī)則。最后用所得的頻集來產(chǎn)生我們所感興趣的關(guān)聯(lián)規(guī)則。

1.2 Apriori算法性質(zhì)及改進(jìn)

頻繁項集的性質(zhì)[5-6]。

性質(zhì)1 頻繁項集的所有非空子集也必須是頻繁的。即A∪B模式不可能比A更頻繁的出現(xiàn)。

性質(zhì)2 非頻繁項集的超集一定不是頻繁項集。即Apriori算法是反單調(diào)的，一個集合如果不能通過測試，則該集合的所有超集也不能通過相同的測試。

Apriori算法運(yùn)用第一個性質(zhì)，利用已得到的或者已知的頻繁項集來構(gòu)造長度更大的項集，這些更長的項集成為潛在頻繁項集(候選項集)。潛在頻繁K項集的集合Ck指的是那些有可能成為頻繁K項集的項集所組成的集合。以后只需計算潛在頻繁項集的支持度，而不必計算所有不同項集的支持度，因此在一定程度上減少了計算量。

性質(zhì)3 若Xk是數(shù)據(jù)集F的頻繁K項目集，那么Xk中任意項的任意元素在F的降冪子集——頻繁k-1項集L(k-1)的所有k-1子集合中出現(xiàn)次數(shù)至少是k-1次。

利用整理出來的性質(zhì)3[7]，我們可以對候選項集做進(jìn)一步的剪枝以獲得更有價值的項目集。

2 Apriori改進(jìn)算法的實現(xiàn)

2.1 Apriori改進(jìn)算法詳細(xì)步驟

1) 掃描事務(wù)數(shù)據(jù)庫產(chǎn)生候選項目集C1，記錄每個項元素的支持事務(wù)(項目編號TID)并統(tǒng)計支持事務(wù)數(shù)，記錄最小支持度閾值及項集。

2) 把小于最小支持度閾值的項目集刪除，得到L1。對L1中的項集自連接產(chǎn)生候選2項集C2，并對L1的項目編號做交集運(yùn)算得到C2項集的事務(wù)標(biāo)識集和支持事務(wù)數(shù)，刪除事務(wù)數(shù)小于最小事務(wù)數(shù)的項集得到L2。

3) 用L(k-1)通過自連接生成候選K項集Ck的事務(wù)標(biāo)志集(改變原算法L(k-1)進(jìn)行自連接的判斷方式)，并對其計數(shù)。

4) 刪除Ck中事務(wù)數(shù)小于最小事務(wù)數(shù)的項集，然后根據(jù)剪枝理論對頻繁K項集中的項進(jìn)行進(jìn)一步刪除，得到進(jìn)一步壓縮的有價值新頻繁K項集。

下面給出已有剪枝方法的偽代碼：

Procedure Prunel(L(k-1))

//m是L(k-1)所有項元素的個數(shù)

For all itemset li∈L(k-1)

If count(li)<=k-1

Then delete all Lj from L(k-1)( li∈Lj)

End

Return L(k-1) //返回刪除L(k-1)中出現(xiàn)次數(shù)小于k-1的項目的項目集

對已有剪枝方法我們做些進(jìn)一步改進(jìn)：

Procedure Prunel(L(k-1))

For( i=0;i

For all itemset li∈L(k-1)

If count(li)<=k-1

Then delete all Lj from L(k-1)( li∈Lj)

m=GetNewM(L(k-1))

End

End

Return L(k-1)

2.2 步驟演示

假設(shè)有如下所示原始事務(wù)數(shù)據(jù)庫(如表1所示)，設(shè)置最小支持事務(wù)為2。

表1 事務(wù)數(shù)據(jù)庫

首先對事務(wù)數(shù)據(jù)庫進(jìn)行一次掃描，得到數(shù)據(jù)庫的全部項元素I={A1，A2，A3，A4，A5，A6}以及單個元素項的支持事務(wù)集(事務(wù)標(biāo)識集)。將其中支持事務(wù)數(shù)小于2的項刪除(這里刪除A4)，得到新頻繁1-項集如表2所示。

表2 頻繁1-項集

頻繁1-項集自連接得到候選2-項集，再通過支持事務(wù)做交集運(yùn)算得到候選2-項集和相應(yīng)的支持事務(wù)集；刪除支持事務(wù)數(shù)小于2的項集，得到頻繁2-項集L2如表3所示。

表3 頻繁2-項集L2

根據(jù)改進(jìn)算法的剪枝方法對頻繁2-項集L2中的項進(jìn)行剪枝處理，將其中有項元素出現(xiàn)次數(shù)小于2的項刪除。A6的出現(xiàn)次數(shù)小于2，所以刪除包含A6的項集{A3，A6}，得到新的頻繁2-項集為如表4所示。

表4 新頻繁2-項集

運(yùn)用與生成新頻繁2-項集相同的方法，生成新頻繁3-項集：自連接，對支持事務(wù)做交集，刪除事務(wù)數(shù)小于2的項集。得到如表5所示頻繁3-項集L3。

表5 頻繁3-項集L3

根據(jù)剪枝理論對頻繁3-項集L3中的項進(jìn)行剪枝處理，將其中有項元素出現(xiàn)次數(shù)小于3的項刪除。由于A1、A2、A3、A5這四個項的出現(xiàn)次數(shù)都小于3，所以把所有項集都刪除，到這一步結(jié)束，搜索出全部頻繁集。

設(shè)置信度閾值為0.65，即minconf=0.65，那么產(chǎn)生的所有關(guān)聯(lián)規(guī)則如表6所示。我們可從中選出感興趣的規(guī)則。

表6 關(guān)聯(lián)規(guī)則表

3 Apriori改進(jìn)算法的應(yīng)用

3.1 數(shù)據(jù)基礎(chǔ)

我們知道，土壤粒度、含水量、有機(jī)質(zhì)、氧化鐵以及鹽組分及含量都會影響土壤光譜反射率。這些因素不同的土壤，其反射率一般都會發(fā)生變化，但土壤的光譜曲線常常能保持波形不變。故這里我們可以使用關(guān)聯(lián)分析對這里的某些因素進(jìn)行定性分析，對這些因素在某一波段內(nèi)對土壤反射率的影響進(jìn)行驗證。

氧化鐵對光譜曲線有較大影響，我們可選對有機(jī)質(zhì)較為敏感但氧化鐵影響較弱的紫外波段(372.01～400 nm)和可見光波段(590～700 nm)附近[8]。而土壤有機(jī)質(zhì)光譜敏感波段主要在600～800 nm，土壤有機(jī)質(zhì)光譜響應(yīng)范圍(600～800 nm)恰是土壤光譜與水分相關(guān)系數(shù)最低的波段區(qū)域。因此我們選擇這些波段的公共區(qū)域可見光波段的695 nm反射率進(jìn)行分析[9]。

所得的實驗數(shù)據(jù)是使用美國生產(chǎn)的儀器ASD FieldSpec 3在武漢市江夏區(qū)紙坊大街沿線所測。儀器采樣波長范圍是350～2 500 nm。在350～1 000 nm間采樣間隔為1.4 nm，1 000～2 500 nm采樣間隔為2 nm；在350～1 000 nm之間光譜分辨率為3 nm，1 000～2 500光譜分辨率為10 nm。測試土壤光譜時探頭垂直于圖樣表面，光源照射方向與垂直方向夾角小于15°，探頭到土壤表面距離15 cm；土壤取樣深度均為20 cm，天氣晴朗，風(fēng)速較小，取樣時間為10:30-15:00，其他因素出于實驗著想，盡可能保持一致。表7為部分原始數(shù)據(jù)。

表7 原始實驗數(shù)據(jù)

3.2 關(guān)聯(lián)分析

我們進(jìn)行關(guān)聯(lián)分析的目的是為了找出影響反射率較大的屬性(這里指有機(jī)質(zhì)、易容鹽量)，并對影響趨勢做定性分析。對屬性數(shù)據(jù)，按一定方式離散化(有機(jī)質(zhì)：1.5 g/kg 易溶鹽：0.25 g/kg 反射率：0.1)。如表8所示。

表8 離散化的屬性表

續(xù)表8

對離散化后的數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘，設(shè)最小支持度為10%，最小置信度為60%。那么整個項集所有元素為{A1，A2，B1，B2，D1，D2}，根據(jù)最小支持度，最小支持事務(wù)數(shù)應(yīng)該為：10%×15=1.5。如表9所示。

表9 候選1-項集

要求項的支持事務(wù)數(shù)大于或等于1.5，可以得到L1：{{A1}，{A2}，{B1}，{B2}，{C1}，{C2}，{D1}，{D2}}。對L1進(jìn)行自連接后得到候選2-項集C2，進(jìn)一步對C2進(jìn)行處理：刪除項集中支持事務(wù)數(shù)小于1.5的項，并刪除其中每個項元素出現(xiàn)次數(shù)小于2的所有項集，得到新頻繁2-項集L2。表10就是滿足條件的新頻繁2-項集L2。

表10 新頻繁2-項集L2

由L2得到候選3-項集C3，并刪除支持事務(wù)數(shù)小于1.5的項后得到頻繁3-項集L3，如表11所示。

表11 頻繁3-項集L3

算法到此結(jié)束。最終算法挖掘出來的最大頻繁模式為{A1，B1，D2}、{A1，B2，D1}、{A2，B1，D1}、{A2，B2，D1}。

3.3 結(jié)果分析

通過分析出來的最大頻繁模式，計算與反射率有關(guān)規(guī)則的置信度：

A1^B1?D2 confidence=P(D2/A∪B1)=P(A1∪B1∪D2)/ P(A1∪B1)=4/5≈80%

A1^B2?D1 confidence=P(D1/A∪B2)=P(A1∪B2∪D1)/ P(A1∪B2)=2/2≈100%

A2^B1?D1 confidence=P(D1/A∪B1)=P(A2∪B1∪D1)/ P(A2∪B1)=6/6≈100%

A2^B2?D1 confidence=P(D1/A∪B2)=P(A2∪B2∪D1)/ P(A2∪B2)=2/2≈100%

選出置信度大于60%的規(guī)則：

規(guī)則一：A1^B1?D2

規(guī)則二：A1^B2?D1

規(guī)則三：A2^B1?D1

規(guī)則四：A2^B2?D1

1) 從規(guī)則一和規(guī)則三可得，隨著有機(jī)質(zhì)含量的增加，土壤反射率會降低。

2) 由規(guī)則一和規(guī)則二可得，土壤反射率隨著含鹽量增加而降低，但是由規(guī)則三、規(guī)則四則得出不一致的結(jié)論，且這些規(guī)則的置信度都很高。分析原因，土壤中易溶鹽不同的組分的含量也可能是影像土壤反射率的另一因素；此外，也有可能是對數(shù)據(jù)進(jìn)行處理時的最小支持度設(shè)置過低，可以進(jìn)行適當(dāng)調(diào)整。

3.4 算法實驗與分析

為了驗證改進(jìn)后算法的效率，選取了影響土壤光譜反射率的全部采樣數(shù)據(jù)作為樣本，該數(shù)據(jù)庫共有7 837條記錄，在相同的硬件配置條件，不同的最小支持度下，得到改進(jìn)算法與經(jīng)典Apriori算法的運(yùn)行時間如圖1所示。

圖1 算法計算時間與最小支持度的關(guān)系

從圖1中可以看出，在相同記錄數(shù)下，改進(jìn)Apriori算法比經(jīng)典 Apriori算法的運(yùn)行效率有顯著的提高，并且計算時間隨最小支持度的增加而減小，且在最小支持度很小時，效果更為明顯。

4 結(jié) 語

從算法本身的角度來說，改進(jìn)的關(guān)聯(lián)規(guī)則算法與Apriori算法比較主要有兩大優(yōu)勢。① 縮減了掃描數(shù)據(jù)庫消耗的系統(tǒng)I/O開銷。② 候選項集的裁剪使得在剪枝和連接上時間效率得到一定程度的提高。

從實例分析角度來說，Apriori算法(及其改進(jìn)理論)不僅適用于市場營銷領(lǐng)域，在遙感數(shù)據(jù)分析方面(土壤光譜相關(guān)性分析、山火預(yù)警以及區(qū)域成礦預(yù)測[10]等)也有較好的實用性，是一種對數(shù)據(jù)、結(jié)論進(jìn)行分析、驗證的有力手段。但不足之處在于在進(jìn)行大數(shù)據(jù)量數(shù)據(jù)分析，本文未得到驗證；在進(jìn)行屬性數(shù)據(jù)離散化時，雖然不會導(dǎo)致結(jié)果的錯誤，但也存在部分偶然性。

[1] Agrawal R,Srikan R.Fast algorithms for mining association rules in large databases[C]//Proceedings of the Twentieth International Conference on Very Large Databases,Santiago,Chile.1994,9:487-499.

[2] Agrawal R,Imielinshi T,Swami A.Mining association rules between sets of items in large database[C]//Proceedings of ACM SIGMOD Conference on the Management of Data.Washington DC.1993:207-216.

[3] Ng R T,Lakshmanan L V S,Han J,et al.Exploratory mining and pruning optimizations of constrained associations rules[C]//SIGMOD 1998,Proceedings ACM SIGMOD International Conference on Management of Data,June 2-4,1998,Seattle,Washington,Usa.DBLP,1998:13-24.

[4] 吳蘭岸,劉延申,劉怡,等.歐美國家知識發(fā)現(xiàn)與數(shù)據(jù)挖掘過程模型研究及其教育領(lǐng)域應(yīng)用啟示[J].遠(yuǎn)程教育雜志,2016,35(3):24-31.

[5] Han Jiawei,Kamber M.Data Mining:Concepts and Techniques[M].北京:機(jī)械工業(yè)出版社,2001.

[6] Witten I H,Frank E.Data Mining:Practical Machine Learning Tools and Techniques[M].北京:機(jī)械工業(yè)出版社,2006.

[7] 劉宏強(qiáng).Apriori關(guān)聯(lián)規(guī)則挖掘算法分析與改進(jìn)[J].中國石油大學(xué)勝利學(xué)院學(xué)報,2009,23(1):17-19.

[8] 楊揚(yáng),高小紅,賈偉,等.三江源區(qū)不同土壤類型有機(jī)質(zhì)含量高光譜反演[J].遙感技術(shù)與應(yīng)用,2015,30(1):186-198.

[9] 彭杰,周清,張楊珠,等.有機(jī)質(zhì)對土壤光譜特性的影響研究[J].土壤學(xué)報,2013,50(3):517-524.

[10] 何彬彬,崔瑩,陳翠華,等.基于地質(zhì)空間數(shù)據(jù)挖掘的區(qū)域成礦預(yù)測方法[J].地球科學(xué)進(jìn)展,2011,26(6):615-623.

APPLICATION OF IMPROVED APRIORI ALGORITHM IN STUDYING FACTORS OF SOIL REFLECTIVITY

Sun Bin Han Yanling Feng Guochao

(CollegeofInformationEngineering,ChinaUniversityofGeosciences,Wuhan430074,Hubei,China)

Firstly, the concepts of Apriori algorithm are briefly introduced, and the theory and implementation steps of the algorithm are improved. Then, it is applied to the study of factors affecting the soil reflectivity through the example tentatively. The experimental results show that the improved Apriori algorithm not only improves the efficiency of generating frequent itemsets, but also effectively reduces the computation time of the algorithm. In the end, the generalization and validity of association rule, Apriori and its improved algorithm are proved.

Apriori algorithm Soil reflectivity Organic matter Association rules

2016-06-03。孫斌，副教授，主研領(lǐng)域：空間數(shù)據(jù)庫，GIS應(yīng)用。韓艷玲，碩士生。豐國超，碩士。

TP311.13

A

10.3969/j.issn.1000-386x.2017.07.054