貴州六盤水師范學(xué)院計算機(jī)科學(xué)與信息技術(shù)系　　胡廣勤　孫國營

關(guān)聯(lián)改進(jìn)算法在煤礦隱患挖掘中的應(yīng)用

貴州六盤水師范學(xué)院計算機(jī)科學(xué)與信息技術(shù)系胡廣勤孫國營

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

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

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

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

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

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

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

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

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

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

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

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

3　 Apriori算法存在的缺陷及改進(jìn)措施

3.1算法缺陷

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

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

3.2算法改進(jìn)

3.2.1改進(jìn)思想

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

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

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

（3）CutOut（Lk）；//對Lk進(jìn)行裁剪

（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進(jìn)行裁剪。下面是CutOut（Lk）的偽代碼：

（1）if（k＞2）Then

（2） for all itemset li∈Lk；

（3）m=count（li）；

（4）if（m＞n）//n是總的事務(wù)屬性項(xiàng)數(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算法評價

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

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

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

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

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

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

表1　煤礦隱患參數(shù)數(shù)據(jù)

表2　預(yù)處理后的數(shù)據(jù)

4.3關(guān)聯(lián)規(guī)則挖掘

4.3.1實(shí)驗(yàn)環(huán)境

進(jìn)行煤礦隱患數(shù)據(jù)挖掘的軟硬件環(huán)境如下：

硬件環(huán)境：處理器為AMDA-10，內(nèi)存為3G，硬盤為250G。

軟件環(huán)境：數(shù)據(jù)庫為SQLServer2008。

采用的編程語言是C#，開發(fā)環(huán)境為Visual Studio2010。

4.3.2挖掘結(jié)果

設(shè)置最小支持度為0.4，最小置信度為0.6，同時，運(yùn)用改進(jìn)后的算法，求得挖掘結(jié)果如表3所示。

4.3.3挖掘結(jié)果分析

從表3中可以看出，運(yùn)用改進(jìn)后的挖掘算法對數(shù)據(jù)倉庫中的數(shù)據(jù)進(jìn)行挖掘，一共挖掘出了六條強(qiáng)關(guān)聯(lián)規(guī)則，總結(jié)如下：

表3　挖掘結(jié)果

將這些強(qiáng)關(guān)聯(lián)規(guī)則轉(zhuǎn)化為瓦斯?jié)舛?、瓦斯壓力、通風(fēng)量以及溫度得到的實(shí)際意義如下：

通過參考礦井內(nèi)隱患參數(shù)數(shù)據(jù)的實(shí)際情況可以看出，利用改進(jìn)后的算法得到的強(qiáng)關(guān)聯(lián)規(guī)則均是符合客觀事實(shí)的，利用挖掘出來的有效信息，可以對礦井安全生產(chǎn)起到較好的指導(dǎo)性作用。

［1］劉雙躍，彭麗.基于Apriori改進(jìn)算法的煤礦隱患關(guān)聯(lián)性分析［J］.內(nèi)蒙古煤炭經(jīng)濟(jì)，2013，10（11）：92-97.

［2］朱翼.基于數(shù)組的Apriori算法的改進(jìn)研究［D］.哈爾濱：哈爾濱師范大學(xué)，2014.

［3］楊國英.泛在網(wǎng)下基于Apriori算法的移動群組的位置預(yù)測［D］.南京：南京郵電大學(xué)，2013.

［4］邵天會.基于改進(jìn)的Apriori算法的Web日志研究［D］.昆明：昆明理工大學(xué)，2013.

［5］馮舸.基于云計算的數(shù)據(jù)挖掘關(guān)聯(lián)算法研究與實(shí)現(xiàn)［D］.成都：成都理工大學(xué)，2013.