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

孫 斌 韓艷玲 豐國超

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

?

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

孫 斌 韓艷玲 豐國超

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

首先簡短介紹Apriori算法相關(guān)概念、改進(jìn)算法的理論和實(shí)現(xiàn)步驟。繼而通過實(shí)例試探性地將其運(yùn)用到研究影響土壤反射率因素的應(yīng)用中。實(shí)驗(yàn)結(jié)果表明：改進(jìn)的Apriori算法不僅提高了產(chǎn)生頻繁項(xiàng)集的效率，而且有效地減少了算法的計(jì)算時(shí)間。最后，驗(yà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ī)則中頻繁項(xiàng)集的算法[2]，其最顯著的特征就是應(yīng)用先驗(yàn)知識(shí)即prior knowledge(頻繁項(xiàng)集性質(zhì))通過迭代方法逐層搜索數(shù)據(jù)庫。

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

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

1.1 算法簡介

在關(guān)聯(lián)規(guī)則中，支持度大于或等于最小支持度的項(xiàng)集稱為頻繁項(xiàng)集，簡稱頻集。為了生成所有頻繁項(xiàng)集，使用了遞歸的方法：先找到頻繁1-項(xiàng)集集合L1，然后用L1找到頻繁2-項(xiàng)集集合L2，接著用L2找L3，直到找不到頻繁K項(xiàng)集為止，找每個(gè)Lk都需要對(duì)數(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)

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

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

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

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

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

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

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

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

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

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

3) 用L(k-1)通過自連接生成候選K項(xiàng)集Ck的事務(wù)標(biāo)志集(改變?cè)惴↙(k-1)進(jìn)行自連接的判斷方式)，并對(duì)其計(jì)數(shù)。

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

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

Procedure Prunel(L(k-1))

//m是L(k-1)所有項(xiàng)元素的個(gè)數(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的項(xiàng)目的項(xiàng)目集

對(duì)已有剪枝方法我們做些進(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ù)庫

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

表2 頻繁1-項(xiàng)集

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

表3 頻繁2-項(xiàng)集L2

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

表4 新頻繁2-項(xiàng)集

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

表5 頻繁3-項(xiàng)集L3

根據(jù)剪枝理論對(duì)頻繁3-項(xiàng)集L3中的項(xiàng)進(jìn)行剪枝處理，將其中有項(xiàng)元素出現(xiàn)次數(shù)小于3的項(xiàng)刪除。由于A1、A2、A3、A5這四個(gè)項(xiàng)的出現(xiàn)次數(shù)都小于3，所以把所有項(xiàng)集都刪除，到這一步結(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ì)、氧化鐵以及鹽組分及含量都會(huì)影響土壤光譜反射率。這些因素不同的土壤，其反射率一般都會(huì)發(fā)生變化，但土壤的光譜曲線常常能保持波形不變。故這里我們可以使用關(guān)聯(lián)分析對(duì)這里的某些因素進(jìn)行定性分析，對(duì)這些因素在某一波段內(nèi)對(duì)土壤反射率的影響進(jìn)行驗(yàn)證。

氧化鐵對(duì)光譜曲線有較大影響，我們可選對(duì)有機(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í)驗(yàn)數(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。測試土壤光譜時(shí)探頭垂直于圖樣表面，光源照射方向與垂直方向夾角小于15°，探頭到土壤表面距離15 cm；土壤取樣深度均為20 cm，天氣晴朗，風(fēng)速較小，取樣時(shí)間為10:30-15:00，其他因素出于實(shí)驗(yàn)著想，盡可能保持一致。表7為部分原始數(shù)據(jù)。

表7 原始實(shí)驗(yàn)數(shù)據(jù)

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

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

表8 離散化的屬性表

續(xù)表8

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

表9 候選1-項(xiàng)集

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

表10 新頻繁2-項(xiàng)集L2

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

表11 頻繁3-項(xiàng)集L3

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

3.3 結(jié)果分析

通過分析出來的最大頻繁模式，計(jì)算與反射率有關(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ì)含量的增加，土壤反射率會(huì)降低。

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

3.4 算法實(shí)驗(yàn)與分析

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

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

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

4 結(jié) 語

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

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

[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] 吳蘭岸,劉延申,劉怡,等.歐美國家知識(shí)發(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é)報(bào),2009,23(1):17-19.

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

[9] 彭杰,周清,張楊珠,等.有機(jī)質(zhì)對(duì)土壤光譜特性的影響研究[J].土壤學(xué)報(bào),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