羅曉麗

（福州職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)系，福建 福州 350108）

溫室蔬菜生產(chǎn)由于是在人為控制生產(chǎn)，周年生產(chǎn)、難以輪作等因素，使得病害極易發(fā)生，傳統(tǒng)的病蟲(chóng)害檢測(cè)是通過(guò)專(zhuān)家觀察，憑經(jīng)驗(yàn)根據(jù)感病蔬菜葉片上病斑的顏色或形狀判斷病害的種類(lèi)。筆者在大量的數(shù)據(jù)基礎(chǔ)上，在項(xiàng)編碼基礎(chǔ)上，利用粗糙集約簡(jiǎn)的方法進(jìn)一步挖掘出病害受損程度的圖像特征屬性及特征區(qū)間。

1 基于項(xiàng)編碼的的Apriori算法及改進(jìn)算法

1.1 Apriori算法原理

Agrawal等首次提出將關(guān)聯(lián)規(guī)則[1]應(yīng)用于解決挖掘顧客交易數(shù)據(jù)中項(xiàng)目集間問(wèn)題，其核心是基于2階段頻繁集思想（即發(fā)現(xiàn)頻繁項(xiàng)目集和生成關(guān)聯(lián)規(guī)則）的遞推算法，其典型算法是Apriori算法，該算法的主要內(nèi)容如下：（1）使用逐層搜索的迭代方法。首先過(guò)掃描數(shù)據(jù)庫(kù)，計(jì)算出各個(gè)頻繁1-項(xiàng)集的支持度，找出所有頻繁1-項(xiàng)集L1，得到頻繁1-項(xiàng)集的集合。（2）連接步。由2個(gè)只有一個(gè)項(xiàng)不同的頻繁1-項(xiàng)集進(jìn)行JOIN運(yùn)算得到的候選頻繁2-項(xiàng)目集C2。（3）剪枝步。對(duì)C2進(jìn)行修剪得到頻繁項(xiàng)集L2。（4）通過(guò)掃描數(shù)據(jù)庫(kù)，計(jì)算各個(gè)項(xiàng)集的支持度，將不滿(mǎn)足支持度的項(xiàng)目集去掉，通過(guò)迭代循環(huán)，重復(fù)步驟2～4，直到找到最大頻繁項(xiàng)集，此時(shí)算法停止。

隨著掃描的數(shù)據(jù)量增大，Apriori算法也呈現(xiàn)出明顯不足：（1）候選集Ck中的每個(gè)元素都必須通過(guò)掃描數(shù)據(jù)庫(kù)一次計(jì)算支持度，來(lái)確定其是否能成為頻繁項(xiàng)集 Lk中的元素，而多次掃描事務(wù)數(shù)據(jù)庫(kù)，需要很大的I/O負(fù)載。（2）隨著掃描數(shù)據(jù)庫(kù)的事務(wù)量增大，可能有龐大的候選集產(chǎn)生。規(guī)模巨大的候選項(xiàng)集，不僅處理需要占用大量的主存空間，而且算法必須耗費(fèi)大量的時(shí)間來(lái)處理。例如：對(duì)于1-頻繁項(xiàng)集個(gè)數(shù)如果是10 000個(gè)，那么可能產(chǎn)生的候選集就會(huì)有個(gè)。

1.2 基于項(xiàng)編碼的CA算法

基于項(xiàng)編碼的 CA算法[2]，只需要掃描數(shù)據(jù)庫(kù)一次，并對(duì)每個(gè)項(xiàng)完成編碼轉(zhuǎn)換，根據(jù)它在數(shù)據(jù)庫(kù)中出現(xiàn)的事務(wù)記錄用0和1進(jìn)行編碼，以后的過(guò)程都是針對(duì)編碼進(jìn)行運(yùn)算，統(tǒng)計(jì)1的個(gè)數(shù)計(jì)算支持?jǐn)?shù)k項(xiàng)頻繁項(xiàng)集，通過(guò)編碼與運(yùn)算生成K+1項(xiàng)頻繁項(xiàng)集，不需要再次掃描數(shù)據(jù)庫(kù)。其具體特點(diǎn)如下：（1）編碼運(yùn)算。該算法只需要掃描一次數(shù)據(jù)庫(kù)，并對(duì)每個(gè)項(xiàng)在某個(gè)事務(wù)記錄中是否出現(xiàn)進(jìn)行編碼，以“出現(xiàn)為1，不出現(xiàn)為0”的原則進(jìn)行編碼，以后的過(guò)程都是針對(duì)編碼進(jìn)行與運(yùn)算。與Apriori算法相比，該算法僅掃描數(shù)據(jù)庫(kù)一次，因而減少了算法的I/O負(fù)載。（2）連接前剪枝。CA算法在對(duì)頻繁(k-1)-項(xiàng)集Lk-1通過(guò)與運(yùn)算進(jìn)行連接，得到候選頻繁k-項(xiàng)集Ck，并對(duì)Lk-1中1的個(gè)數(shù)進(jìn)行計(jì)數(shù)處理，根據(jù)計(jì)數(shù)結(jié)果刪除Lk-1中包含出現(xiàn)次數(shù)小于(k-1)的項(xiàng)的項(xiàng)集，以減少參加連接的(k-1)項(xiàng)的數(shù)量，從而降低了組合的數(shù)據(jù)量，也減小了候選頻繁 k-項(xiàng)集 Ck的大小。但該算法在進(jìn)行編碼轉(zhuǎn)換時(shí)需要消耗大量時(shí)間，而且編碼數(shù)位過(guò)長(zhǎng)，I/O的負(fù)載過(guò)大；同時(shí)由于編碼過(guò)長(zhǎng)，造成與運(yùn)算的繁復(fù)，可見(jiàn)記錄的個(gè)數(shù)極大地影響了該算法運(yùn)行的時(shí)間。

1.3 改進(jìn)算法

通過(guò)上述分析可知，要提高算法的運(yùn)行效率，可從如下方面進(jìn)行處理：（1）降低掃描事務(wù)的記錄數(shù)；（2）計(jì)算支持度時(shí)減少掃描數(shù)據(jù)庫(kù)的次數(shù)。由此筆者提出通過(guò)減少數(shù)據(jù)庫(kù)的記錄數(shù)來(lái)減小編碼轉(zhuǎn)換時(shí)間的改進(jìn)算法，其基本思路是先進(jìn)行一次掃描，計(jì)算出候選頻繁1-項(xiàng)目集，將含有1-項(xiàng)目集的記錄重新組合生成新的數(shù)據(jù)庫(kù)（比原來(lái)的數(shù)據(jù)庫(kù)記錄大為減少，尤其是海量數(shù)據(jù)庫(kù)減少的記錄數(shù)量更多），并利用CA算法對(duì)新生成數(shù)據(jù)庫(kù)進(jìn)行編碼轉(zhuǎn)換。這樣以后不再掃描的數(shù)據(jù)庫(kù)，而是通過(guò)編碼與運(yùn)算生成候選頻繁項(xiàng)集，通過(guò)統(tǒng)計(jì)項(xiàng)編碼中1的個(gè)數(shù)計(jì)算支持度。由于只進(jìn)行一次掃描，且縮小了掃描范圍，因而加快了運(yùn)算速度，提高數(shù)據(jù)挖掘的效率。

改進(jìn)算法的具體描述如下：

輸入：事務(wù)數(shù)據(jù)庫(kù)D；最小支持度閾值min_sup

輸出：D中的頻繁項(xiàng)集L

{C1=candidate1-Itemsets}；//生成候選頻繁1-項(xiàng)目集，一般情況下，令T1={{I1},{I2},{I3}…{Im}}，即T1為所有項(xiàng)目的集合。

L1={p∈T|Sup (p)≥min_sup}；//掃描事務(wù)數(shù)據(jù)庫(kù)D一次，生成頻繁1-項(xiàng)集。

Copy * to D2for c ∈L1//生成縮小的新的數(shù)庫(kù)，并對(duì)該數(shù)庫(kù)進(jìn)行編碼轉(zhuǎn)換。

2 粗糙集約簡(jiǎn)算法[3]

2.1 決策表

設(shè)Q=（U, A, V, f）是一個(gè)信息系統(tǒng)，U為論域，即為數(shù)據(jù)庫(kù)所有對(duì)象集合，A為屬性集，C為條件屬性，D為決策屬性，V為屬性集的值域，f:U×A→V，A=C∪D。

2.2 等價(jià)類(lèi)及相關(guān)概念

設(shè)數(shù)據(jù)庫(kù)U={x1, x2, x3, x4, x5, x6,…}，屬性集A={a1,a2, a3, a4, a5, a6,…}，條件屬性C={a0, a1, a2, a3, a4, a5,a6, …}，決策屬性D={am}，屬性集的值域V={V1, V2, V3,V4, V5, ……}。

定義1 對(duì)于屬性集A中任意一個(gè)屬性a，若xi和xj所對(duì)應(yīng)屬性a的取值相等，則有xi，xj基于屬性a等價(jià)。

定義 2 屬于同等價(jià)類(lèi)的記錄歸為一類(lèi)，論域基于屬性A的劃分可表示為U={U1, U2, U3, U4, U5, U6, ……}。

2.3 屬性約簡(jiǎn)與規(guī)則生成

（1）對(duì)于每一個(gè) a∈C，按屬性值個(gè)數(shù)排列，排序后為{a0, a1, a2, a3, a4, a5, a6, ……ak}；

（2）令a0=0, a1=1……ak-1=k-1, j=0, c=aj+1, aj+1=aj

If aji=a(j+1)i ‘判斷決策表是否相容

相容：a(j+2)i=a(j+2-1)i……, aki=a(k-1)i，則合并相同的行

不相容：a(j+1)i=c

令j=j+1, if j=k，則輸出a0, a1, a2, a3, a4, a5, a6, …ak-1

Else goto (2)

3 研究目標(biāo)與方案確定

研究目的是找出病斑受病害程度嚴(yán)重與其他特征的關(guān)聯(lián)規(guī)則。運(yùn)用改進(jìn)的Apriori算法得到極大相關(guān)組，其屬性值的劃分過(guò)細(xì)，存在數(shù)據(jù)冗余現(xiàn)象，進(jìn)一步通過(guò)屬性約簡(jiǎn)，可以得到更為客觀科學(xué)的關(guān)聯(lián)規(guī)則。因此本文采用粗糙集約簡(jiǎn)理論合理劃分屬性區(qū)間，以使挖掘出的規(guī)則更科學(xué)。

4 應(yīng)用

4.1 圖像數(shù)據(jù)挖掘

傳統(tǒng)的數(shù)據(jù)挖掘[4]稱(chēng)為數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn)（Knowledge Discovery in Database，KDD），是從存放在數(shù)據(jù)庫(kù)、數(shù)據(jù)倉(cāng)庫(kù)或其他信息庫(kù)中的大量復(fù)雜的原始的數(shù)據(jù)中，提取出對(duì)人們的決策有價(jià)值的知識(shí)或規(guī)則的過(guò)程。而這種知識(shí)或規(guī)則是人們事先不知道的但又對(duì)決策者分析歷史或現(xiàn)在數(shù)據(jù)，挖掘出有價(jià)值的數(shù)據(jù)模型，對(duì)現(xiàn)在的決策或?qū)?lái)的預(yù)測(cè)有價(jià)值的規(guī)則或知識(shí)。隨著圖形圖像及多媒體信息的日益發(fā)展，圖像數(shù)據(jù)挖掘顯得越來(lái)越重要。從圖像數(shù)據(jù)庫(kù)中取得一些先驗(yàn)知識(shí)對(duì)圖像信息的進(jìn)一步提取的準(zhǔn)確性及時(shí)效性顯得尤為重要。圖像數(shù)據(jù)庫(kù)的建立有微觀和宏觀角度兩種，微觀是把圖像看成由無(wú)數(shù)個(gè)象素點(diǎn)作為對(duì)象的數(shù)據(jù)庫(kù)，研究每個(gè)象素點(diǎn)的灰度、顏色、像距等；宏觀可以把圖像的局部作為對(duì)象創(chuàng)建數(shù)據(jù)庫(kù)，進(jìn)而研究對(duì)象的灰度、顏色、大小、紋理等屬性。

4.2 實(shí)驗(yàn)步驟及結(jié)果

（1）實(shí)驗(yàn)環(huán)境：在同樣的實(shí)驗(yàn)條件下（服務(wù)器：P4 2.0 GHz、4 G內(nèi)存、SQL Server2000；客戶(hù)機(jī)： P4 3.9 GHz、2 G內(nèi)存）。

（2）實(shí)驗(yàn)數(shù)據(jù)預(yù)處理：選用563片黃瓜霜霉病葉片利用photoshop工具分離病斑圖像共計(jì)2 457塊病斑連通圖像區(qū)域數(shù)據(jù)，取得圖像特征屬性：面積A、顏色C、亮度B、位置P、周長(zhǎng)G、灰度均值H、形狀R等。如表1。

表1 黃瓜葉片病斑圖像特征

（3）運(yùn)用改進(jìn)的Apriori算法得到支持度大于30%的極大相關(guān)組{ACHR}，表明受害程度與亮度、位置無(wú)關(guān)，與面積、顏色、灰度均值、形狀極大相關(guān)。

（4）并根據(jù)每個(gè)特征最大與最小值，劃屬性區(qū)間，將屬性值離散化，將顏色屬性定為決策屬性按淺綠和淺黃、棕色和褐色C={1,2,3}（顏色的深淺表明受害程度的大小），D={A, P, H, R }為條件屬性，如面積按[0, 0.5]，[0.5, 1]，[1，1.5]，[1.5, 2]，[2, +∞]區(qū)間離散 A={1, 2, 3, 4, 5}；灰度均值按[120，130]，[130，140]，[140，150]，[140，150]，[160，+∞]區(qū)間離散 H={1，2，3，4，5, 6, 7}；形狀按圓形、三角形、長(zhǎng)條形得到集合R={1, 2, 3}。原始數(shù)據(jù)初始化如表2。

表2 黃瓜葉片病斑受害情況決策表

（5）利用粗糙集約簡(jiǎn)算法，對(duì)上述表中屬性進(jìn)行約簡(jiǎn)，發(fā)現(xiàn)相對(duì)于顏色決策屬性，面積屬性值1、2合并，3、4、5合并約簡(jiǎn)，灰度均值1、2合并，3、4合并，5、6合并，形狀屬性值2、3、4合并約簡(jiǎn)。

挖掘結(jié)果：病斑面積較小低于1時(shí)，形狀接近圓形，且顏色較淺，顏色偏綠色黃色，灰度均值在區(qū)間[12，140]，受害程度較輕。而當(dāng)面積較大超過(guò)1時(shí)，形狀不規(guī)則，且顏色較深，顏色偏棕褐色，灰度均值在[140，+∞]，受害程度較為嚴(yán)重。

5 結(jié)論

借鑒經(jīng)典的Apriori算法及其優(yōu)化解決方案，提出了一種保留含有頻繁1-項(xiàng)集的數(shù)據(jù)庫(kù)作為掃描的數(shù)據(jù)庫(kù)，不僅縮小了掃描數(shù)據(jù)庫(kù)的規(guī)模，而且減少了編碼轉(zhuǎn)換位長(zhǎng)，逐步縮小了數(shù)據(jù)庫(kù)搜索的時(shí)間和進(jìn)行運(yùn)算的時(shí)間，從而極大提高了算法的運(yùn)行效率。對(duì)于圖像數(shù)據(jù)量大、繁雜，這種算法尤為適合。對(duì)于圖像數(shù)據(jù)預(yù)處理，使用粗糙集約簡(jiǎn)算法得出的挖掘規(guī)則，可以科學(xué)動(dòng)態(tài)地劃分離散區(qū)間，從而挖掘出的結(jié)果更具科學(xué)性。

[1] 黃建明.關(guān)聯(lián)規(guī)則挖掘算法的研究與應(yīng)用[D].西安:西安建筑科技大學(xué),2009.

[2] 李磊,向正義.一種基于二項(xiàng)編碼的改進(jìn)設(shè)計(jì)[J].微計(jì)算機(jī)信息,2009(21):214-215.

[3] 張亦軍.基于粗糙集和遺傳算法的大數(shù)據(jù)集數(shù)據(jù)挖掘應(yīng)用研究[D].太原:太原理工大學(xué),2012.

[4] 韓家瑋.數(shù)據(jù)挖掘·概念與技術(shù)[M].北京:機(jī)械工業(yè)出版社,2006:66-69.