Apriori改進算法在研究影響土壤反射率因素中的應用

孫 斌 韓艷玲 豐國超

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

?

Apriori改進算法在研究影響土壤反射率因素中的應用

孫 斌 韓艷玲 豐國超

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

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

Apriori算法 土壤反射率 有機質 關聯規則

0 引 言

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

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

1 Apriori算法及其改進思想

1.1 算法簡介

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

1.2 Apriori算法性質及改進

頻繁項集的性質[5-6]。

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

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

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

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

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

2 Apriori改進算法的實現

2.1 Apriori改進算法詳細步驟

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

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

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

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

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

Procedure Prunel(L(k-1))

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

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)中出現次數小于k-1的項目的項目集

對已有剪枝方法我們做些進一步改進：

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 步驟演示

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

表1 事務數據庫

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

表2 頻繁1-項集

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

表3 頻繁2-項集L2

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

表4 新頻繁2-項集

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

表5 頻繁3-項集L3

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

設置信度閾值為0.65，即minconf=0.65，那么產生的所有關聯規則如表6所示。我們可從中選出感興趣的規則。

表6 關聯規則表

3 Apriori改進算法的應用

3.1 數據基礎

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

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

所得的實驗數據是使用美國生產的儀器ASD FieldSpec 3在武漢市江夏區紙坊大街沿線所測。儀器采樣波長范圍是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，天氣晴朗，風速較小，取樣時間為10:30-15:00，其他因素出于實驗著想，盡可能保持一致。表7為部分原始數據。

表7 原始實驗數據

3.2 關聯分析

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

表8 離散化的屬性表

續表8

對離散化后的數據進行關聯規則挖掘，設最小支持度為10%，最小置信度為60%。那么整個項集所有元素為{A1，A2，B1，B2，D1，D2}，根據最小支持度，最小支持事務數應該為：10%×15=1.5。如表9所示。

表9 候選1-項集

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

表10 新頻繁2-項集L2

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

表11 頻繁3-項集L3

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

3.3 結果分析

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

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%的規則：

規則一：A1^B1?D2

規則二：A1^B2?D1

規則三：A2^B1?D1

規則四：A2^B2?D1

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

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

3.4 算法實驗與分析

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

圖1 算法計算時間與最小支持度的關系

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

4 結 語

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

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

[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] 吳蘭岸,劉延申,劉怡,等.歐美國家知識發現與數據挖掘過程模型研究及其教育領域應用啟示[J].遠程教育雜志,2016,35(3):24-31.

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

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

[7] 劉宏強.Apriori關聯規則挖掘算法分析與改進[J].中國石油大學勝利學院學報,2009,23(1):17-19.

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

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

[10] 何彬彬,崔瑩,陳翠華,等.基于地質空間數據挖掘的區域成礦預測方法[J].地球科學進展,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。孫斌，副教授，主研領域：空間數據庫，GIS應用。韓艷玲，碩士生。豐國超，碩士。

TP311.13

A

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