關聯(lián)改進算法在煤礦隱患挖掘中的應用

2016-09-28 02:19:44貴州六盤水師范學院計算機科學與信息技術系胡廣勤孫國營

河北農(nóng)機 2016年5期

貴州六盤水師范學院計算機科學與信息技術系　　胡廣勤　孫國營

貴州六盤水師范學院計算機科學與信息技術系胡廣勤孫國營

我國煤礦事故頻發(fā)，煤礦安全生產(chǎn)形勢嚴峻，為了能夠根據(jù)煤礦隱患參數(shù)數(shù)據(jù)挖掘有效信息，指導煤礦安全生產(chǎn)，根據(jù)關聯(lián)算法中常用的Apriori算法在時間效率上的不足，提出改進算法，并通過實驗驗證了改進算法的合理性，然后通過改進算法挖掘煤礦安全隱患數(shù)據(jù)，得到強關聯(lián)規(guī)則，對煤礦安全生產(chǎn)起到較好的促進作用。

煤礦事故；隱患參數(shù)；關聯(lián)算法；Apriori算法；改進算法；強關聯(lián)規(guī)則

1　我國煤炭安全生產(chǎn)綜述

煤炭行業(yè)關系國計民生，是影響我國經(jīng)濟運行的基礎產(chǎn)業(yè)［1］。然而，我國煤礦安全事故頻發(fā)，每年因為煤礦事故死亡的人數(shù)排在世界前列［2］。煤礦安全生產(chǎn)事故中最常見的是瓦斯問題導致的瓦斯爆炸等事故，而礦井內(nèi)的瓦斯?jié)舛?、瓦斯壓力、通風量以及溫度等因素都有可能導致瓦斯事故的發(fā)生，煤礦安全監(jiān)測系統(tǒng)能夠?qū)崟r地監(jiān)測這些參數(shù)信息，而這些參數(shù)信息之間也是會相互影響的，通過關聯(lián)算法挖掘瓦斯?jié)舛?、瓦斯壓力、通風量以及溫度之間隱含的關聯(lián)知識，可以對煤礦安全生產(chǎn)起到較好的指導性作用［3］。

2　關聯(lián)算法綜述

2.1關聯(lián)規(guī)則概念

設I=｛i1，i2，i3，i4，…，ip｝是由p個不同項目組成的集合，對于一個給定的事務數(shù)據(jù)庫DB，假設事物集合O由很多具有唯一標示的事務Oid組合而成，每一條包含于事物集合O的事務Oid所處理的項目集都和I上的一個子集相互對應，就被稱為項集Io，也叫作模式Io。如果同時滿足事務o∈O以及模式XI的條件，那么就稱X包含于事務O。

對于模式X，若X中包含q個項目，記為|X|=q（1≤q≤p），那么，我們就稱X為q-模式，也稱X的長度為q。例如下面的項集X=｛i1，i2，i3，i4，i5，i6｝就是一個6-項集。

包含X的事務在事務數(shù)據(jù)庫DB中占的百分比數(shù)被稱為模式X在事務數(shù)據(jù)庫中的支持數(shù)，記為X.s；事務數(shù)據(jù)庫DB中含有模式X事務Oid的數(shù)目被稱為模式X在事務數(shù)據(jù)庫中的支持數(shù)，記為X.c。

通過用戶提前設定支持度閾值以及置信度閾值的值能夠達到更好地實現(xiàn)關聯(lián)規(guī)則挖掘的目的，如果關聯(lián)規(guī)則能夠達到支持度和置信度均大于預習設定的閾值的要求，那么就把稱為強關聯(lián)規(guī)則。滿足這一條件的支持度閾值叫作最小支持度，記為minsup，滿足這一條件的置信度閾值叫作最小置信度，記為minconf。

2.2關聯(lián)規(guī)則挖掘算法

作為商業(yè)和學術應用范圍最廣的關聯(lián)知識發(fā)現(xiàn)方法，關聯(lián)規(guī)則挖掘算法已經(jīng)被開發(fā)出多種比較成熟的算法，在這些算法中，被應用最廣的是由Agrawal等研究人員提出的Apriori以及隨后其他研究人員提出的Apriori改進算法［4］。成功運用這一算法需要注意兩點問題，也就是兩個閾值的設定：最小支持度（minimumsupport）以及最小可信度（minimumconfidence）。算法挖掘出的最終結(jié)果都是要滿足最先設定的閾值的大小范圍，尤其是一定要小于最小支持度閾值。這個值反應了關聯(lián)算法中的最低可靠度，基于這一層含義，數(shù)據(jù)挖掘系統(tǒng)也可以看成是從設定好的數(shù)據(jù)庫中，運用挖掘算法獲取滿足設定的兩個支持度閾值要求的關聯(lián)規(guī)則［5］。

3　 Apriori算法存在的缺陷及改進措施

3.1算法缺陷

對數(shù)據(jù)進行關聯(lián)規(guī)則挖掘非常有效的手段是采用Apriori算法的頻繁項集方法，但是在實際生產(chǎn)和應用中，這一算法還存在一些不足之處：

應用Apriori算法處理大量候選項集時會產(chǎn)生巨大的開銷，如果算法產(chǎn)生大量的頻繁1-項集，那么在由頻繁1-項集產(chǎn)生頻繁2-項集時就會產(chǎn)生大量的2-項候選集，由于生成的2-項候選集沒有剪枝，因此要對每一個2-項候選集進行檢驗，另外，頻繁模式的尺寸過大也會導致大量需要檢驗的候選項集的產(chǎn)生。由于根據(jù)候選項集方法所決定的開銷和采用的實現(xiàn)技術無關，因此，在算法會產(chǎn)生大量候選集的情況下，Apriori類的算法運行起來會非常吃力。例如，假設算法得到104個1-頻繁集，根據(jù)Apriori算法，生成的2-頻繁集會超過107個，所有生成的2-頻繁集都需要進行檢驗，這樣就會消耗大量的內(nèi)存，嚴重增加時間消耗量。

3.2算法改進

3.2.1改進思想

在生成候選項集Ck+1之前，判斷Lk中所有項集的數(shù)目m以及總的事務屬性項數(shù)n，如果m＞n，再判斷Lk中所有項出現(xiàn)的次數(shù)是否相同，如果Lk中所有項出現(xiàn)的次數(shù)并不完全相同，獲取Lk中所有項中次數(shù)最小的項的次數(shù)值j，裁剪掉Lk中次數(shù)值為j的項得到Lk’，然后通過Lk’連接Lk’的操作得到Ck+1。改進后的算法的偽代碼為：

（1） L1=｛large 1-itemsets｝；

（2）FOR（k=1；Lk≠Φ；k++）DOBEGIN

（3）CutOut（Lk）；//對Lk進行裁剪

（4）Ck+1=apriori-gen（Lk）；//Ck+1是k個元素的候選集

（5）FOR all transactions t∈DDOBEGIN

（6）Ct=subset（Ck+1，t）；//Ct是所有t包含的候選集元素

（7）FOR all candidates c∈CtDO

（8）c.count++；

（9）END

（10）Lk+1=｛c∈Ck+1|c.count≥minsup_count｝

（11）END

（12）Answer=∪kLk；

上述算法調(diào)用了CutOut（Lk），是為了對Lk進行裁剪。下面是CutOut（Lk）的偽代碼：

（1）if（k＞2）Then

（2） for all itemset li∈Lk；

（3）m=count（li）；

（4）if（m＞n）//n是總的事務屬性項數(shù)

（5）｛

（6）min=count（l1）；

（7）ifexist（count（li）＜min）then

（8）min=count（li）；//得到最小次數(shù)值

（9）｝

（10）delete all ljfromLk（count（lj）=min）；

（11）return Lk’

3.2.2算法評價

通過對改進算法的理論分析和實例介紹，我們能夠看出改進以后的算法在思路上和Apriori算法仍然是一致的，也就是通過循環(huán)掃描數(shù)據(jù)庫獲得支持度不小于給定的最小支持度的頻繁項集，但是，改進算法在生成Ck+1之前，如果Lk中所有項集的數(shù)目大于總的事務屬性項數(shù)，并且Lk中所有項出現(xiàn)的次數(shù)并不完全相同，那么就會對Lk進行一次裁剪，這樣就可以減少候選項集Ck+1中候選項的數(shù)量，大大降低算法的時間消耗量。但是，這一改進算法也有不足之處，那就是在對Lk進行裁剪的過程中是需要消耗一定的時間的，但是就大型數(shù)據(jù)庫來說，這些時間是可以忽略不計的，使用改進的Apriori算法進行關聯(lián)規(guī)則挖掘的效率也是明顯提高的。

4　基于Apriori改進算法的煤礦隱患數(shù)據(jù)挖掘

4.1數(shù)據(jù)獲取

本文根據(jù)某礦2012年1月至2015年1月的煤礦隱患監(jiān)測系統(tǒng)中持續(xù)監(jiān)測的數(shù)據(jù)作為研究對象，選取瓦斯?jié)舛?、瓦斯壓力、通風量以及溫度為研究目標，得到的結(jié)果如表1所示。

4.2數(shù)據(jù)預處理

設定瓦斯?jié)舛?、瓦斯壓力、通風量以及溫度的屬性分別為C、P、V、T。根據(jù)瓦斯?jié)舛鹊闹档那闆r可以將其分為（0-0.16），（0.16-0.32），（0.32-）三組，對應的標志分別為：C1，C2，C3；根據(jù)瓦斯壓力的值的情況可以將其分為（0-8），（8-19），（19-）三組，對應的標志分別為：P1，P2，P3；根據(jù)通風量的值的情況可以將其分為（0-1100），（1100-1300），（1300-）三組，對應的標志分別為：V1，V2，V3；根據(jù)溫度的值的情況可以將其分為（-12），（12-16），（16-）三組，對應的標志分別為：T1，T2，T3。表2為表1中的數(shù)據(jù)經(jīng)過預處理以后的數(shù)據(jù)：