韓格格，黃艷紅，姜娜娜，徐曉慶

(寧夏氣象信息中心,寧夏銀川，750002)

0 引言

Apriori是數(shù)據(jù)挖掘經(jīng)典算法之一，但是也具有一定局限性。Apriori算法每次生成頻繁集都要重復(fù)掃描一次數(shù)據(jù)庫，因此時(shí)間成本較大。王偉等［1］提出一種B_Apriori算法，該算法只需對(duì)數(shù)據(jù)庫進(jìn)行一次掃描，然后通過邏輯運(yùn)算的方式，計(jì)算出每一項(xiàng)的次數(shù)，最終得到頻繁項(xiàng)集。李亮等［2］針對(duì)經(jīng)典Apriori算法的性能存在的問題，提出T-Apriori算法，該算法也只需要掃描一次數(shù)據(jù)庫，將數(shù)據(jù)轉(zhuǎn)化為布爾值矩陣，通過計(jì)算找出頻繁項(xiàng)集。這些改進(jìn)后的算法與Apriori算法相比，雖然達(dá)到一定縮減時(shí)間的目的，但只是減少了數(shù)據(jù)庫掃描的次數(shù)，并沒有縮小數(shù)據(jù)庫的規(guī)模。本文提出一種基于布爾矩陣的壓縮矩陣頻繁項(xiàng)集挖掘算法，將矩陣進(jìn)行多次壓縮，對(duì)壓縮后矩陣的行向量進(jìn)行邏輯運(yùn)算，計(jì)算出每一項(xiàng)出現(xiàn)的次數(shù)，最終得到頻繁項(xiàng)集，可以同時(shí)達(dá)到縮減掃描數(shù)據(jù)庫次數(shù)和縮小數(shù)據(jù)庫規(guī)模的目的。

1 基于關(guān)聯(lián)規(guī)則算法的氣象觀測(cè)數(shù)據(jù)質(zhì)量控制模型

基于關(guān)聯(lián)規(guī)則的氣象觀測(cè)數(shù)據(jù)質(zhì)量控制算法包括以下三個(gè)步驟，即數(shù)據(jù)離散化處理、產(chǎn)生關(guān)聯(lián)規(guī)則、進(jìn)行規(guī)則匹配［3］。

2 數(shù)據(jù)離散化處理

關(guān)聯(lián)規(guī)則的挖掘需要離散型數(shù)據(jù), 臺(tái)站得到的氣象觀測(cè)數(shù)據(jù)都是連續(xù)的，因此首先要對(duì)得到的基礎(chǔ)數(shù)據(jù)做離散化處理。將基礎(chǔ)數(shù)據(jù)中的各個(gè)氣象要素按照現(xiàn)行標(biāo)準(zhǔn)，進(jìn)行等級(jí)劃分。以溫度為例，將數(shù)據(jù)按照以下等級(jí)劃分：大寒（-10 ～-14.9℃）、小寒 (-5 ～-9.9℃ )、輕寒 (-4.9 ～0℃ )、微寒 (0 ～4.9℃ )、涼 (5 ～9.9℃ )、溫涼 (10 ～11.9℃ )、微溫涼(12 ～13.9℃ )、溫和 (14 ～15.9℃ )、微濕和 (16 ～17.9℃ )、溫暖 (18 ～19.9℃ )、暖 (20 ～21.9℃ )、熱 (22 ～24.9℃ )等。

3 產(chǎn)生關(guān)聯(lián)規(guī)則

3.1 Apriori算法

3.1.1 定義及性質(zhì)

定義：Apriori算法是一種用迭代思想來挖掘出頻繁項(xiàng)集的算法，通過”k-1項(xiàng)頻繁項(xiàng)集"得到”k-項(xiàng)候選項(xiàng)集"，進(jìn)而得到“k-項(xiàng)頻繁項(xiàng)集”。首先，找出頻繁”1-項(xiàng)集"的集合L1，通過L1找出頻繁”2-項(xiàng)集"的集合L2，依次尋找L3、L4… Lk-1，直到不能找出頻繁”k-項(xiàng)集"為止。

支持度（support）：support(A=>B) = P(A ∪ B)，表示要素A和要素B同時(shí)出現(xiàn)的概率。

性質(zhì)1 若項(xiàng)集Lk是頻繁項(xiàng)，那么Lk除空集外的所有子集也都是頻繁的；

推論1 若項(xiàng)集Lk是非頻繁項(xiàng)，那么所有包含Lk的項(xiàng)集都是非頻繁項(xiàng)集，因此包含Lk的項(xiàng)集可以直接刪除［4］。

3.1.2 算法流程

步驟1:設(shè)定一個(gè)最小支持度，將項(xiàng)集中所有不小于最小支持度的項(xiàng)，作為頻繁1-項(xiàng)集 L1；步驟2：通過L1自身連接生成候選項(xiàng)集C2；步驟3：根據(jù)上述性質(zhì)1和推論1，將候選項(xiàng)集C2進(jìn)行剪枝處理；步驟4：生成2-項(xiàng)頻繁項(xiàng)集L2；步驟5：重復(fù)步驟2～步驟4，直到不能找出頻繁”k-項(xiàng)集”為止。

3.1.3 產(chǎn)生關(guān)聯(lián)規(guī)則

通過以上步驟，將得到的所有滿足最小支持度的頻繁項(xiàng)集作為關(guān)聯(lián)規(guī)則，形成關(guān)聯(lián)規(guī)則庫。

3.2 改進(jìn)算法

不難看出，Apriori算法每一次尋找Lk的過程都要掃描數(shù)據(jù)庫D，挖掘頻繁項(xiàng)集存在時(shí)間效率低下的局限性，因此本文提出壓縮矩陣的頻繁項(xiàng)集挖掘算法。根據(jù)頻繁項(xiàng)集的性質(zhì)，通過對(duì)矩陣壓縮來縮小數(shù)據(jù)庫規(guī)模，進(jìn)而對(duì)壓縮后矩陣的行向量作邏輯“與”運(yùn)算，加快計(jì)算的速度，提高效率，即本文提出的MC_Apriori算法。

3.2.1 布爾矩陣定義及性質(zhì)

定義: 將數(shù)據(jù)庫D按以下規(guī)則轉(zhuǎn)化為矩陣M，項(xiàng)作為行，事務(wù)作為列，如果第j個(gè)項(xiàng)集在第i個(gè)事務(wù)中存在，則矩陣M的第i行、第j列的值dij＝1，如果不存在，則dij＝0。若數(shù)據(jù)庫 D 中含有n個(gè)事務(wù)（T1,T2…Tn）, m個(gè)項(xiàng)(I1,I2…Im)，則M可以表示為：

性質(zhì)2：如果布爾矩陣M中某一項(xiàng)dnm與其他項(xiàng)進(jìn)行“邏輯與”運(yùn)算時(shí)，結(jié)果都是非頻繁項(xiàng)集，則可以將此列從布爾矩陣 M中刪除。

性質(zhì)3：如果布爾矩陣中某一行的項(xiàng)數(shù)之和小于k，尋找頻繁k-項(xiàng)集時(shí)，則可以將此行從布爾矩陣 M中刪除。

3.2.2 MC_Apriori算法流程

步驟1: 將數(shù)據(jù)庫D轉(zhuǎn)化為布爾矩陣M；

步驟2：對(duì)布爾矩陣M中的列向量進(jìn)行運(yùn)算，與設(shè)定的最小支持度比較，得到1-項(xiàng)頻繁集L1；

步驟3：尋找頻繁1-項(xiàng)集時(shí)，如果項(xiàng)Ii是非頻繁的，則可以將此列從布爾矩陣 M中刪除，生成壓縮矩陣M1，得到頻繁1-項(xiàng)集；

步驟4：尋找頻繁k-項(xiàng)集時(shí)（k>=2），某一行的項(xiàng)數(shù)之和小于k，則可以將此行從布爾矩陣 M中刪除，生成壓縮矩陣Mk，計(jì)算得到頻繁k-項(xiàng)集；

步驟5：重復(fù)步驟4，直到不能產(chǎn)生頻繁k-項(xiàng)集為止。

4 規(guī)則匹配

將得到的所有滿足最小支持的頻繁項(xiàng)集作為關(guān)聯(lián)規(guī)則，用待檢測(cè)的氣象觀測(cè)數(shù)據(jù)中的每條記錄及其所有組合與關(guān)聯(lián)規(guī)則庫中的關(guān)聯(lián)規(guī)則進(jìn)行匹配，直到遍歷完所有的規(guī)則為止，如果出現(xiàn)k條相匹配的規(guī)則，則認(rèn)定當(dāng)前觀測(cè)記錄為正常記錄，否則為異常記錄。

5 算法實(shí)驗(yàn)

5.1 數(shù)據(jù)的采集與預(yù)處理

選取寧夏石炭井站2020年7月～8月的700條數(shù)據(jù)作為樣本數(shù)據(jù)，選擇氣溫、10分鐘平均風(fēng)速、本站氣壓、整點(diǎn)相對(duì)濕度四個(gè)要素為例進(jìn)行實(shí)驗(yàn)。經(jīng)過等級(jí)劃分預(yù)處理過的數(shù)據(jù)如圖1所示。

圖1 預(yù)處理之后數(shù)據(jù)

5.2 數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘

(1)產(chǎn)生關(guān)聯(lián)規(guī)則

用Apriori關(guān)聯(lián)規(guī)則算法和MC_Apriori算法計(jì)算頻繁項(xiàng)集，設(shè)置最小支持度閾值為0.05,獲得實(shí)驗(yàn)數(shù)據(jù)集中的頻繁項(xiàng)集共85項(xiàng)，將這些頻繁項(xiàng)集作為關(guān)聯(lián)規(guī)則。獲得的部分關(guān)聯(lián)規(guī)則如圖2。

圖2 部分關(guān)聯(lián)規(guī)則

(2)改進(jìn)前算法和改進(jìn)后算法的時(shí)效對(duì)比

將Apriori關(guān)聯(lián)規(guī)則算法和MC_Apriori算法處理數(shù)據(jù)產(chǎn)生頻繁項(xiàng)集的時(shí)間進(jìn)行對(duì)比。

對(duì)比結(jié)果表明：最小支持度小于0.35時(shí)，改進(jìn)后的算法在時(shí)間效率上明顯優(yōu)于改進(jìn)前的算法。

5.3數(shù)據(jù)的規(guī)則匹配

在700條樣本觀測(cè)數(shù)據(jù)中，植入30條異常數(shù)據(jù)進(jìn)行測(cè)試。以氣溫為例，在原始?xì)鉁刂档幕A(chǔ)上將每條氣溫值增加10攝氏度作為異常數(shù)據(jù)。設(shè)置質(zhì)量控制參數(shù)k=8，如果滿足匹配8條關(guān)聯(lián)規(guī)則庫中的規(guī)則時(shí)判定為正常數(shù)據(jù)，否則判定為異常數(shù)據(jù)。

檢測(cè)結(jié)果為：30條異常數(shù)據(jù)中檢測(cè)出28條，存在2條異常數(shù)據(jù)被誤檢，找出錯(cuò)誤數(shù)據(jù)率達(dá)到93.3%。其余670條數(shù)據(jù)中檢測(cè)出正確數(shù)據(jù)為662條，存在8條數(shù)據(jù)被誤檢，誤檢率為1%。

6 結(jié)論

本文提出基于關(guān)聯(lián)規(guī)則的氣象觀測(cè)數(shù)據(jù)質(zhì)量控制算法的模型，分析了Apriori算法存在的不足，提出了一種改進(jìn)的MC_Apriori算法，對(duì)事務(wù)數(shù)據(jù)庫對(duì)應(yīng)的布爾矩陣進(jìn)行行、列壓縮縮減數(shù)據(jù)庫規(guī)模，然后利用按位與運(yùn)算提高頻繁項(xiàng)集統(tǒng)計(jì)的速度，克服了傳統(tǒng)Apriori算法重復(fù)掃描數(shù)據(jù)庫的缺陷，提高了算法的執(zhí)行效率。同時(shí)對(duì)Apriori算法與MC_Apriori算法進(jìn)行了時(shí)間性能比較，仿真結(jié)果表明在一定的支持度范圍內(nèi)，MC_Apriori算法比Apriori算法更具時(shí)效性。最后，植入異常數(shù)據(jù)，與規(guī)則庫中的關(guān)聯(lián)規(guī)則進(jìn)行規(guī)則匹配，找出錯(cuò)誤數(shù)據(jù)率達(dá)93.3%。