基于FP-growth的大壩安全監(jiān)測數(shù)據(jù)挖掘方法

毛寧寧,蘇懷智,高建新

(1. 河海大學(xué)水文水資源與水利工程科學(xué)國家重點實驗室,江蘇 南京 210098; 2. 河海大學(xué)水利水電學(xué)院,江蘇 南京 210098)

數(shù)據(jù)挖掘方法常應(yīng)用于大壩安全監(jiān)測數(shù)據(jù)的分析和處理。工程中常對變形、滲流、應(yīng)力和裂縫開口等大壩安全監(jiān)測資料進(jìn)行整編和分析,挖掘數(shù)據(jù)之間的相關(guān)關(guān)系,以此評估大壩運(yùn)行狀態(tài),防止災(zāi)害發(fā)生[1-2]?；诒O(jiān)測資料和壩工原理的統(tǒng)計模型也可分析其相關(guān)關(guān)系,但實際監(jiān)測資料存在不連續(xù)、精確度低的情況,復(fù)相關(guān)系數(shù)低,且無法對比相似的影響因子或分析多因子耦合作用的影響[3]。

近年來,學(xué)者們對大壩安全監(jiān)測數(shù)據(jù)挖掘方法展開了研究。蘇振華等[4]采用關(guān)聯(lián)分析方法對溫度數(shù)據(jù)進(jìn)行深度挖掘,確定了溪洛渡大壩施工過程中冷卻通水的最高溫度。張海燕[5]基于關(guān)聯(lián)規(guī)則決策樹法進(jìn)行了大壩安全監(jiān)測數(shù)據(jù)挖掘,并利用上下游水位、降雨量、溫度等數(shù)據(jù)對壩頂沉降進(jìn)行預(yù)測。王偉等[6]將大壩安全監(jiān)控統(tǒng)計模型的求解轉(zhuǎn)換為多目標(biāo)函數(shù)的優(yōu)化,利用混合蛙跳算法同步確定調(diào)整系數(shù)和回歸系數(shù),建立基于混合蛙跳算法的混凝土壩加權(quán)變形預(yù)模型。FP-growth算法是Apriori算法的延伸,阮志毅[7]將FP-Growth算法和空間多尺度剖分進(jìn)行結(jié)合,提出一種頻繁項集的精確挖掘算法。顧軍華等[8]提出一種新的基于Spark的并行FP-Growth算法—BFPG,以提高算法的執(zhí)行效率。劉沖等[9]提出的占用內(nèi)存少、能滿足大型數(shù)據(jù)庫挖掘需求的改進(jìn)的FP-growth算法,使挖掘速度大大提高,適合于大型數(shù)據(jù)庫的關(guān)聯(lián)規(guī)則挖掘算法。

在大壩安全監(jiān)測數(shù)據(jù)中,變形量關(guān)乎大壩狀態(tài)是否穩(wěn)定。大壩變形量受到包括水位因素、溫度因素、時效因素等影響,具有很強(qiáng)的非線性、隨機(jī)性[10-11]。本文基于關(guān)聯(lián)規(guī)則原理,應(yīng)用改進(jìn)的FP-growth算法,依據(jù)大壩安全監(jiān)測數(shù)據(jù),挖掘變形量與其影響因子之間的相關(guān)關(guān)系,分析大壩運(yùn)行性態(tài)。實例結(jié)合梅山水庫的變形和環(huán)境量監(jiān)測資料,利用此方法對數(shù)據(jù)進(jìn)行橫向和縱向的比對,實現(xiàn)對各個影響因子進(jìn)行綜合評價。

1 改進(jìn)的FP-growth算法

1.1 關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘方法之一,涉及2個基本概念:支持度、置信度。

a. 支持度(support):包含M且包含N的元組數(shù)占總元組數(shù)的比例,即項集A和項集B在數(shù)據(jù)庫中同時出現(xiàn)的概率:

(1)

式中:WM∪N為包含M且包含N的元組數(shù);W為總元組數(shù)。

b. 置信度(confidence):包含M且包含N的元組數(shù)占包含M的元組數(shù)的比例,即含有項集M的事件中項集N同時出現(xiàn)的概率:

(2)

式中:WM為包含M的元組數(shù)。

關(guān)聯(lián)規(guī)則即根據(jù)給定的最小支持度Smin和最小置信度Cmin在事務(wù)數(shù)據(jù)庫W中找出的事物相關(guān)關(guān)系[12]。

1.2 改進(jìn)的FP-growth算法

探索不同影響因子在數(shù)據(jù)庫中的重要程度,即是發(fā)現(xiàn)頻繁項集的過程,亦是對關(guān)聯(lián)規(guī)則中“支持度”的應(yīng)用。FP-Growth算法建立在Apriori算法思想的基礎(chǔ)上,在挖掘頻繁模式的算法中應(yīng)用最廣。算法采用一種緊湊的數(shù)據(jù)結(jié)構(gòu)組織構(gòu)成頻繁模式樹(Priority樹),通過壓縮方式存儲數(shù)據(jù)庫中的數(shù)據(jù),并直接從Priority樹中提取頻繁項集[12]。

當(dāng)數(shù)據(jù)庫總量大、事務(wù)集數(shù)目多或頻繁項集的數(shù)目大時,重復(fù)掃描降低了運(yùn)行速度,同時在進(jìn)行數(shù)據(jù)挖掘時難以抓住主次,找到有用的關(guān)聯(lián)規(guī)則。改進(jìn)的FP-growth算法在計算過程中對數(shù)據(jù)庫進(jìn)行剪枝,以提高計算效率。算法具體過程如下:

輸入:事務(wù)數(shù)據(jù)庫W;最小支持度;最小置信度。

步驟1:掃描數(shù)據(jù)庫W,以不小于Smin為條件找出頻繁項集,并得到其出現(xiàn)的次數(shù)計數(shù)m(或支持度),注意區(qū)別于FP-Growth算法,這一步無須產(chǎn)生候選項集。按照支持度遞減排列頻繁項集各項,得到頻繁項集集合L。設(shè)L={Im,Im-1,…,I1}(其中Im的支持度最高,I1的支持度最小)。

步驟2:將支持度小于Smin的項從各事務(wù)中刪除,再次掃描數(shù)據(jù)庫W,按照頻繁項集支持度遞減的次序重新排列各事務(wù)中的項,得到數(shù)據(jù)庫W′。

步驟3:根據(jù)L中的各項的支持度大小,按照以下規(guī)則由小到大依次構(gòu)造各項數(shù)據(jù)庫子集,并利用FP-growth算法分別對其Priority樹分支進(jìn)行約束頻繁項挖掘:掃描數(shù)據(jù)庫W′,從中提取所有包含項Ii(i=m,m-1,…,1)的頻繁項集,然后刪除這些事務(wù)中支持度小于該項的支持度的項集,所得事務(wù)集合便為項Ii的數(shù)據(jù)庫子集Wi;其次利用FP-growth算法對數(shù)據(jù)庫子集W′進(jìn)行頻繁項集挖掘;最后構(gòu)造該項的條件模式基,然后構(gòu)造其條件Priority樹,在該條件Priority樹上挖掘出包含該項的頻繁項集CL,即完成在數(shù)據(jù)庫子集Wi上的約束頻繁項集的挖掘。

步驟4:當(dāng)L中所有的項的約束頻繁項集CL被依次挖掘出來后,合并這些約束頻繁項集,即取這些約束頻繁項集CL的并集,便可得到數(shù)據(jù)庫W的所有頻繁項集,結(jié)束挖掘過程[9,12]。

2 基于改進(jìn)FP-growth算法的大壩運(yùn)行性態(tài)分析方法

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

大壩監(jiān)測數(shù)據(jù)是不連續(xù)且無序的,計算前需對數(shù)據(jù)進(jìn)行預(yù)處理。影響大壩變形的因素眾多,假定因變量Q為某大壩運(yùn)行時期的某處變形量,基于以下自變量建立數(shù)據(jù)模型:水壓因子A、氣溫因子B、水溫因子C、時效因子D[13-15]。

2.1.1異常值處理

實際所得的大壩監(jiān)測數(shù)據(jù)中,有些是連續(xù)的自動化監(jiān)測值,有些是不連續(xù)的人工監(jiān)測值,同時也存在數(shù)據(jù)缺失或數(shù)據(jù)異常的情況,如由于儀器損壞導(dǎo)致某一時間段內(nèi)的測值缺失,或者測水溫或氣溫時,由于某種原因測值在某一時段出現(xiàn)異常等。本算法中采取忽略元組法,舍去自變量缺失或異常時間段內(nèi)的所有數(shù)據(jù)。

2.1.2數(shù)據(jù)集成變換

數(shù)據(jù)集成變換能夠消除不同屬性的數(shù)值因大小不一而造成的計算偏差,將不同量級的數(shù)據(jù)縮放至同一數(shù)值區(qū)間,以便比較和處理。以自變量A為例,假定某特定時間段內(nèi)數(shù)值的最大值A(chǔ)max和最小值A(chǔ)min為規(guī)范值,通過公式:

(3)

將自變量測值A(chǔ)(或者B、C、D)以及因變量Q的測值映射到區(qū)間[0, 1]區(qū)間。

2.1.3數(shù)據(jù)規(guī)約

數(shù)據(jù)規(guī)約可將復(fù)雜的數(shù)據(jù)庫簡化,分析和挖掘也能接近和保持原數(shù)據(jù)的完整性,并產(chǎn)生相同的分析結(jié)果[12]。

a. 采用離散化對數(shù)據(jù)進(jìn)行規(guī)約:將給定的連續(xù)屬性值分區(qū),采用式(4)將4個自變量A、B、C、D變換后的值再映射到區(qū)間[0, 10]區(qū)間:

A″=10A′-Q′

(4)

式中:A″的大小反映了自變量與因變量的離散程度。

b. 通過將屬性值域劃分為區(qū)間,用區(qū)間的標(biāo)記替代實際的數(shù)據(jù)集:由“等距分箱”思想在某一時段對A″、B″、C″、D″取整數(shù),數(shù)值相同的分為一類,則A可得到A0～A9不同項,B、C、D同理。選取某時段的數(shù)據(jù),按照上述步驟進(jìn)行數(shù)據(jù)預(yù)處理,每個時段即可得到集合{Ax、Bx、Cx、Dx},其中x為1～10的整數(shù),由此生成數(shù)據(jù)庫K。

2.2 基于改進(jìn)FP-growth算法的大壩安全監(jiān)測數(shù)據(jù)挖掘步驟

具體挖掘流程見圖1,步驟如下。

圖1 改進(jìn)的FP-growth算法流程

步驟1:參考大壩安全監(jiān)測的資料,輸入合適的最小支持度、最小置信度,將已預(yù)處理的大壩監(jiān)測數(shù)據(jù)庫K生成txt文件,導(dǎo)入改進(jìn)FP-growth算法Python程序。

步驟2:利用Python程序?qū)?shù)據(jù)庫K進(jìn)行掃描,根據(jù)不同監(jiān)測數(shù)據(jù)與支持度的對比結(jié)果進(jìn)行剪枝,得到新的數(shù)據(jù)庫K′,這一過程剪去出現(xiàn)幾率小于置信度的項集以及相關(guān)分支,即部分異常的數(shù)據(jù)。例如在實例中,由于讀數(shù)誤差造成的與平均值偏差較遠(yuǎn)的水壓項A9、A8等在此步驟中被剪去。

步驟3:利用Python程序?qū)?shù)據(jù)庫K′進(jìn)行掃描,構(gòu)造Priority樹。

步驟4:對Priority樹進(jìn)行關(guān)聯(lián)規(guī)則分析運(yùn)算,挖掘大壩監(jiān)測數(shù)據(jù)庫K′中頻繁項集以及強(qiáng)關(guān)聯(lián)規(guī)則。

從3個角度對運(yùn)算結(jié)果進(jìn)行分析論證:分析{Ax}、{Bx}、{Cx}、{Dx}的支持度,得出監(jiān)測數(shù)據(jù)與單個環(huán)境量之間的關(guān)系;分析含{Ax,Bx}、{Ax,Cx}、{Ax,Dx}、{Bx,Cx}、{Bx,Dx}、{Cx,Dx}、{Ax,Bx,Cx}、{Ax,Bx,Dx}、{Ax,Cx,Dx}、{Ax,Bx,Cx,Dx}的支持度,得出監(jiān)測數(shù)據(jù)與2個環(huán)境量耦合作用下的關(guān)系;分析含{Ax,Bx,Cx}、{Ax,Bx,Dx}、{Ax,Cx,Dx}、{Ax,Bx,Cx,Dx}的支持度,得出監(jiān)測數(shù)據(jù)與3個環(huán)境量耦合作用下的關(guān)系。

3 工程實例

梅山水庫位于淮河支流史河上游的安徽省金寨縣境內(nèi),流域面積1 970 km2,于1954年3月動工,1956年4月竣工,是一座以防洪為主、結(jié)合灌溉、發(fā)電、航運(yùn)、水產(chǎn)養(yǎng)殖等效益的多年運(yùn)行的老壩。選取梅山水庫2012—2014年間3組環(huán)境量監(jiān)測資料(上游水位、平均氣溫、平均水溫)以及位于壩頂?shù)腜L2測點(如圖2)在大壩橫截面方向(即上下游方向,簡稱X方向)的測值為基本資料進(jìn)行分析。梅山大壩壩體水平位移監(jiān)測采用垂線法,其測點的具體布置見圖2。

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

現(xiàn)有資料中測點PL2在X方向上的位移測讀頻率為一周一測,其余環(huán)境量測值為一天一測。其中上游水位缺少2012年3月22日—2012年4月4日2周的測值,PL2測點的位移監(jiān)測數(shù)據(jù)缺少2013年9月26日和2014年3月27日2次測值。將相關(guān)時間段內(nèi)的所有數(shù)據(jù)剔除,取余下時段中上游水位、平均氣溫、平均水溫一周測值的平均值與當(dāng)周的位移測值,過程線見圖3和圖4。

3.2 數(shù)據(jù)集成變換與規(guī)約

按照前述步驟對數(shù)據(jù)進(jìn)行數(shù)據(jù)預(yù)處理,得到數(shù)據(jù)集K,部分結(jié)果見表1(全部數(shù)據(jù)共153組)。表1中下標(biāo)0～9表示各個自變量與因變量的離散程度。數(shù)字越小,表示此自變量與因變量有關(guān)的可能性較大;數(shù)字越大,表示自變量與因變量有關(guān)的可能性較小。

3.3 數(shù)據(jù)集掃描與剪枝

將數(shù)據(jù)集K生成txt文件,導(dǎo)入Python中,經(jīng)過查閱相關(guān)資料和多次試驗,選取Smin=0.9,Cmin=0.1,對數(shù)據(jù)集K進(jìn)行剪枝,生成新的書庫的K′。此時數(shù)據(jù)集K中的項目,如A5～A9、B3～B9、C3～C9被剪去,得到最終的事務(wù)集K′,部分結(jié)果見表2(全部數(shù)據(jù)共153組)。

3.4 構(gòu)建Priority樹

由事務(wù)集K′帶入Python中運(yùn)行算法,把A、B、C、D作為項,生成Priority樹,根據(jù)計算結(jié)果繪制的Priority樹見圖5。

圖2 梅山水庫水平位移正倒垂線(自動化和人工)測點布置

圖3 梅山水庫PL2測點位移與溫度過程線

圖4 梅山水庫PL2測點位移與上游水位過程線

Priority樹將上游水位、平均氣溫、平均水溫、時效4組復(fù)雜的數(shù)據(jù)與位移之間的關(guān)系梳理的簡明清晰。由Priority樹可知,B為Priority樹的主枝干,且B的計數(shù)比C多,說明與大壩變形量關(guān)系最密切的是B平均氣溫因子,其次是C平均水溫因子。再次,Priority樹中A上游水位因子與D時效因子計數(shù)相當(dāng),說明與B和C相比,其與位移之間的關(guān)系較不密切。

表2 梅山水庫數(shù)據(jù)集K′(部分)

圖5 梅山水庫運(yùn)算結(jié)果Priority樹

3.5 頻繁項集及其支持度

得到Priority樹之后,利用python程序計算各個項集的支持度,得到的所有項集及其支持度見表3。

由表3可知,在含有2個因子的項集中,頻繁項集{B，C}支持度為82%,其次是頻繁項集{A，B}支持度為78%,再次之是頻繁項集{C，D}支持度為70%,說明當(dāng)2項因子耦合作用的情況下,氣溫因子和水溫因子的耦合作用,是導(dǎo)致大壩變形的主要原因,而氣溫因子和上游水位交互作用,以及水溫因子與時效因子交互作用對大壩變形也有很大的影響。同樣,不經(jīng)過頻率分析,通過對Priority樹枝干進(jìn)行分析(即圖5中數(shù)字比)也可得到上述結(jié)論。在含有3個因子的項集中,頻繁項集{A，B，D}的支持度為84%,比率最高;其次,頻繁項集{A，B，C}的支持度為71%;再次,頻繁項集{B，C，D}的支持度為69%。說明3項因子耦合作用的情況下,上游水位因子、氣溫因子和時效因子的耦合作用,對大壩變形的影響最大,而上游水位因子、氣溫因子和水溫因子交互作用,以及氣溫因子、水溫因子與時效因子交互作用對大壩變形也有影響。

表3 挖掘數(shù)據(jù)庫W′所得到的項集

4 結(jié) 語

a. 關(guān)聯(lián)規(guī)則挖掘大壩安全監(jiān)測數(shù)據(jù)時,對監(jiān)測資料的完整性要求較低,并且可以比較同類的影響因子重要程度,如比較“氣溫因子”與“水溫因子”的重要程度,也可將不同因子耦合作用的情況進(jìn)行對比。以上通過統(tǒng)計模型則很難實現(xiàn)。

b. 改進(jìn)的FP-growth算法新穎、思路清晰、結(jié)果簡約、實用性高,可通過多種編程軟件來實現(xiàn)。利用改進(jìn)的FP-growth算法挖掘大壩變形監(jiān)測數(shù)據(jù)庫,能夠很好地建立大壩變形量和影響因子之間的相關(guān)關(guān)系,得出簡明結(jié)論。實例表明,改進(jìn)后的FP-growth算法為大壩安全監(jiān)測數(shù)據(jù)挖掘提供了一條良好的思路。