動態聚類最近鄰法在湖庫藍藻水華預測中的應用

白曉哲, 張慧妍, 王小藝, 王 立, 許繼平, 于家斌

(北京工商大學 計算機與信息工程學院 食品安全大數據技術北京市重點實驗室, 北京 100048)

動態聚類最近鄰法在湖庫藍藻水華預測中的應用

白曉哲, 張慧妍, 王小藝, 王 立, 許繼平, 于家斌

(北京工商大學計算機與信息工程學院食品安全大數據技術北京市重點實驗室,北京100048)

[目的] 探索湖庫藍藻水華的有效預測方法，為水環境污染防治關鍵問題的解決提供科學依據。 [方法] 結合藍藻水華演化中表現出的混沌類隨機特點，提出一種基于有效性函數優化的動態聚類算法，以實現藍藻水華動態、小范圍近鄰優化預測的目的。首先，基于動態聚類算法對監測數據進行典型類的客觀劃分，為后續有效減小搜索空間，提高預測精度奠定基礎；而后采用粒子群算法優化得到各類的最佳近鄰個數，以確定參與回歸建模的觀測值數量；最后依據最近鄰觀測數據建立動態回歸預測模型。 [結果] 采用太湖金墅監測站點2011年葉綠素a濃度測定值進行建模，之后對2012年葉綠素a濃度進行短期預測。新建模型的預測值與實際值運行趨勢一致，且相對誤差為12.02%，而基于傳統聚類線性回歸算法的相對誤差為15.21%，基于BP神經網絡預測算法的相對誤差為19.51%，相空間重構算法的相對誤差為38.42%。 [結論] 算例結果表明該方法的預測精度相對較高，證明了所提優化預測方法的可行性與有效性。

藍藻水華; 動態聚類; 最近鄰法; 預測

文獻參數： 白曉哲, 張慧妍, 王小藝, 等.動態聚類最近鄰法在湖庫藍藻水華預測中的應用[J].水土保持通報，2017,37(4)：161-165.DOI:10.13961/j.cnki.stbctb.2017.04.027； Bai Xiaozhe, Zhang Huiyan, Wang Xiaoyi, et al. Dynamic clustering based on nearest neighbors for predicting of cyanobacteria bloom in lakes and reservoirs[J]. Bulletin of Soil and Water Conservation, 2017,37(4)：161-165.DOI:10.13961/j.cnki.stbctb.2017.04.027

隨著中國工農業的迅猛發展以及城市化進程的加快，水體富營養化問題日益突出。水體富營養化是指水體接納過量的氮、磷等營養性物質，使得水體中藻類以及其他水生生物異常過度繁殖，出現水體溶解氧含量下降，透明度降低，動植物大批死亡，造成水質惡化，使水域生態和水功能受到阻礙和破壞，嚴重的甚至發生水華，給湖泊水環境及其生態系統帶來嚴重后果[1]。水體富營養污染誘發水華暴發是一個多因素耦合、多維度消漲和具有內在強非線性耗散結構的復雜動力學體系[2]。國內學者王海云[3]對三峽庫區支流水華暴發的污染演變效應進行了分析，發現在水域、水文、時間、藻類組成、浮游生物指標等因素上存在著大量的變化不明顯、關系模糊、突變、約束、開放、自組織的混沌非線性行為效應，演變過程軌跡符合非線性行為效應特征；王小藝[4]在對湖庫藍藻水華生成過程進行機理研究的基礎上，對其進行混沌特性判斷，結合復雜網絡的統計特征參數，提出一種新的藍藻水華預測方法。由于混沌理論為具有隨機性、動態性的非線性復雜系統提供了可行的研究途徑，并且已經在一些領域得到應用[5-8]。

目前，有關混沌時間序列的預測方法主要有全局預測法和局域預測法，其基本思路都是根據觀測數據，重構相空間，然后采用適當的建模方法在相空間中找到一個局部線性模型逼近系統動態特性，實現一定時段內的短時預測，但它們有一定的局限性：一是模型階數較低，導致估計精度不高、魯棒性較差；二是需要的基礎知識較多、數據量及計算量較大、不便于理解。本文基于運行工作點局部線性化思想，提出利用有效性函數依據研究對象的數據特征動態劃分典型數據進行聚類，而后基于最近鄰相似原則，通過粒子群算法優化確定參與建模的最佳近鄰數量，最后應用回歸算法構建預測模型，有效地利用了鄰域內的多個歷史信息。最后針對太湖金墅監測站點的葉綠素a濃度實測數據進行研究，結果表明該算法簡潔、有效，具有較好的預測精度。

1 基本原理及算法改進

傳統的單變量混沌時間序列預測是基于Packard等人提出的相空間重構方法[9]，其中關鍵參數的選取存在一定的不確定性與不一致性。

1.1 基于動態聚類的混沌時間序列模型

聚類是一種無監督學習過程。K-means聚類是基于距離的聚類算法，具有算法簡單快速、適于處理大數據集等優點，是聚類分析中使用最為廣泛的算法之一。

目前K-means聚類在應用中存在兩個需要解決的問題：一是最佳聚類數的確定；二是K-means聚類中邊界位置有用信息的處理。這兩個問題的有效處理，對于后續預測精度的提高具有重要意義。為此，本文提出從以下兩個方面對傳統K-means聚類算法進行改進。

1.1.1 建立聚類有效性指標，確定最佳聚類數 構建有效性指標，指標函數取值最優時對應的聚類結果即為最優聚類劃分。研究[10-11]表明，沒有一種有效性指標能夠在任何情況下都具有普遍適用性，目前常用的4種聚類有效性指標為Calinski-Harabasz(CH)指標[12]、Hartigan(Ht)指標[13]、Homogeneity-Separation(HS)指標[14]、Krzanowski-Lai(KL)指標[15]。本文基于前期對葉綠素a濃度預測研究經驗，提出一種新的聚類有效性指標，即用聚類結果分布的自然屬性來評價類內緊密性與類間分離性。

(1)

式中：Dwc(c)——聚類數為c時的類內距離；c——聚類個數;nw——第w(w=1,2,…,c)個子類的樣本數目;xnw,i,xnw,j——含有nw個樣本的子類中第i個樣本和第j個樣本，且i,j=1,2,…,nw。

(2) 類間距離。將兩個聚類中心點之間的歐式距離定義為2個類的類間距離。類間距離公式為:

(2)

式中：Dbc(c)——聚類數為c時的類間距離；cu,cv——第u個聚類中心和第v個聚類中心, 且u,v=1,2,…,c。

(3)

式中：Coq——聚類數為c時的聚類綜合質量；ε,p,q——平衡聚類類內距離與類間距離的權值，一般情況下p,q>0，0<ε<1。為了簡化計算，取p=1，q=1；若類內距離的值較小，而類間距離的值較大，為了避免較大的類間距離對較小的類內距離的削弱作用，可增大類內距離的權值，本文中針對葉綠素a濃度的數據分布特點取ε=0.7。顯然，聚類綜合質量越大，表明聚類劃分效果越好。

1.1.2 確定聚類區域，提高樣本搜索精度 本文提出一種新的確定聚類半徑的方法，用于確定有效聚類區域，可提高類內樣本搜索速度與精度。

聚類半徑公式為：

(4)

式中：Cra——聚類半徑；N——某子類的樣本個數；yd——第d個樣本，且(d=1,2,…,N)；C——聚類中心；Dd——第d個樣本與聚類中心的距離。

迭代過程中需要不斷重新劃定聚類區域，用更新后的聚類半徑分離出邊界點。則此子類邊界點集合為：

Bin={Dd│Dd>Cra}

(5)

總邊界點集合為：

BIN={Bin1,Bin2,…,Binc}

(6)

式中：BIN——總邊界點集合； Binc——第c個子類的邊界點集合。

后續則可依據未知對象所屬的子類與邊界點的集合來確定該未知對象的搜索空間。

1.2 粒子群算法

在確定了最佳聚類劃分后，希望通過采用相似性樣本信息構建模型逼近預測值，在這個過程中選取樣本點的個數是一項較困難的工作。粒子群優化算法(particle swarm optimization, PSO)是由Eberhart與Kennedy[16]根據鳥類捕食行為而發明的一種新的全局優化進化算法。本文采用粒子群算法利用群體中的個體樣本對信息的共享，實現問題求解空間從無序到有序的演化過程，從而獲得最優解。其中，粒子m的第b維速度與位置按如下公式進行更新：

(7)

(8)

這樣，基于動態的局部優化思想，利用粒子群算法分別對劃分后的聚類集合進行最佳鄰居個數優化。最終確定在每類中選取 個最近鄰樣本數據建立回歸模型進行預測應用。

回歸模型為：

Y=βX+E=β0+β1X1+β2X2+…+βkXk+E

(9)

式中：k——粒子群優化得到的最佳鄰居個數；βk——回歸系數；E——隨機誤差。

1.3 模型預測

預測通常分為單步預測和多步預測，假設樣本數為M，以單變量時間序列為研究對象的單步預測是指：利用t時刻前的M個觀測值作為模型的輸入數據，得到第t+1時刻的預測值；多步預測是指利用該M個樣本不僅可以單步預測第t+1時刻的值，也可以預測第t+2，t+3，…,t+T個時刻的值，T——預測步長，即通過已知的樣本集可以外推進行T步預測[17]。

(10)

考慮本文所選水華數據具有混沌屬性，采用間接多步預測可有效利用新信息逼近預測值，故本文應用了間接多步預測法進行葉綠素a濃度預測。

2 實例計算與分析

2.1 研究區概況與數據資料

太湖是中國第3大淡水湖，位于長江三角洲南部，面積2 338 km2，平均水深1.9 m，屬于大型淺水湖泊。它不僅是旅游勝地，也是流域內大中城市的重要水源。近年來，隨著太湖地區經濟的迅速發展，環境保護和治理相對滯后，入湖主要河道和湖區的水質污染日益嚴重，特別是水體的富營養化，已經成為太湖水環境的主要問題。太湖的富營養化不僅制約著湖泊的可持續利用，而且直接影響到人民群眾的身體健康，太湖藍藻大規模爆發的條件短期內難以消除，太湖水華是個需要長期應對的問題，因此，建立水華預測系統，采取有力措施遏制水華迫在眉睫。本文將基于時間序列的優化動態聚類模型應用在具有混沌特性的湖庫藍藻水華表征因子——葉綠素a濃度的預測中。由于已證實藍藻水華演化過程中具有混沌屬性[4]，而混沌系統非常敏感的特性會因為一個微小擾動導致演化軌跡的巨大差異，因此，混沌系統不能進行長期預測；另一方面，混沌系統蘊含著一定的有序規律，軌跡發散但逃逸不出奇異吸引子的約束，這使得短期預測是可行的。基于此特性，本文中預測建模數據采用太湖金墅站點2011年1月至2011年12月每隔4 h采集的2 000組葉綠素a濃度數據，測試數據為2012年1月1日至2012年1月7日40組葉綠素a濃度數據。

2.2 最佳聚類數的確定

基于本文提出的有效性指標對預測建模數據進行優化聚類計算，得到聚類綜合質量最大時對應的最佳聚類數為 。

對相同的數據集，采用上面提到的4種常用聚類有效性指標CH指標、Ht指標、HS指標、KL指標進行仿真試驗，最后得到各個指標關于聚類數的變化曲線(圖1)。CH指標、KL指標、HS指標將指標函數達到最大值時的聚類數作為最佳聚類數，Ht指標將指標函數值小于等于10的最小聚類數作為最佳聚類數。由圖1可得，CH指標得到的最佳聚類數c=7；KL指標得到的最佳聚類數為c=6；HS指標得到的最佳聚類數為c=4；Ht指標得到的最佳聚類數為c=1。

圖1 基于常用有效性指標曲線的聚類結果圖

2.3 模型求解

對聚類劃分的每個子類進行粒子群優化確定最佳近鄰個數。粒子群算法的參數設置為：粒子維數為1維，迭代次數為100次，加速因子設置為2，因為線性權重比常數權重有更好的優化效果，這里采用線性遞減權重；粒子群中的每一個粒子的位置值代表鄰居個數的取值，粒子的變化范圍設置為[10,100]；適應度函數為回歸模型計算值與實際值的誤差。優化結果確定最佳近鄰個數為10。

這表明后續在已確定的典型類中可通過動態選取10個最近鄰數據樣本，建立回歸預測模型。本文采用間接多步預測法進行之后40個時間點葉綠素a濃度預測以考察模型的有效性，得到預測值與實測值的對比圖(圖2)。仿真結果表明基于本文提出的優化動態聚類局部K最近鄰法的預測值與表征水華形成的葉綠素a的實際值的運行趨勢一致，并具有較好的預測精度。

圖2 基于動態聚類算法的預測結果對比圖

2.4 模型評價與分析

為了評價本模型的精度與所提有效性指標的有效性，針對同一數據集，分別采用相空間重構算法、基于BP神經網絡的預測算法、基于傳統聚類的回歸算法對葉綠素a濃度進行對比預測，評價指標采用平均相對誤差和最大相對誤差。

相對誤差的計算公式為：

(11)

式中：erz——相對誤差； Acvz——第z組葉綠素a濃度實際值； Pcvz——第z組葉綠素a濃度預測值；

平均相對誤差的計算公式為：

(12)

式中：erav——平均相對誤差； g——預測長度。

最大相對誤差的計算公式為：

ermax=max(│erz│)

(13)

式中：ermax——最大相對誤差。

基于不同算法的預測值與實測值的對比圖(圖3)，預測誤差詳見表1。

由圖3和表1可得，與相空間重構算法、基于BP神經網絡預測算法和基于傳統聚類的回歸算法等相比，本文的預測方法精度相對較高；同時基于各種有效性指標的預測結果也驗證了本文所提有效性指標——聚類綜合質量的合理性與有效性。雖然采用HS指標得到的最佳聚類數與本文提出的聚類有效性指標結果相同，但是其計算方法難于理解、評估性和通用性不強，而本文提出的有效性指標計算方便、容易理解，具有很強的實用性與普適性。

圖3 預測模型結果對比

預測方法 平均相對誤差最大相對誤差相空間重構算法0.38421.1000BP神經網絡算法0.19510.4736傳統聚類線性回歸算法0.15210.5863動態聚類線性回歸算法(基于Ht指標)0.14520.3957動態聚類線性回歸算法(基于KL指標)0.12650.4753動態聚類線性回歸算法(基于CH指標)0.13090.6370動態聚類線性回歸算法(基于聚類綜合質量)0.12020.3867

3 結 論

在考慮藍藻水華表征因素葉綠素a濃度具有混沌特性的基礎上，借鑒非線性系統局部動態建模的思想，提出一種基于聚類質量的有效性函數優化的動態聚類算法。其中優化動態聚類局部K最近鄰方法中提出的有效性函數與一般常用的有效性函數相比能較好地劃分葉綠素a濃度時間序列的典型類，高效地精簡了建模與搜索范圍；同時，采用粒子群算法優化確定類內的最近鄰個數為后續非線性時間序列在典型區域內利用最近鄰樣本逼近預測值問題奠定了基礎；最終基于太湖金墅站點葉綠素a濃度的預測分析結果表明，所提方法有效提高了具有混沌屬性的葉綠素a濃度的非線性預測趨勢與精度，且計算簡便、可行性好，為非線性預測問題提供了很好的思路。

[1]GubelitYI,BerezinaNA.Thecausesandconsequencesofalgalblooms:TheCladophoraglomeratabloomandtheNevaEstuary(EasternBalticSea)[J].MarinePollutionBulletin, 2010,61(4/6):183-188.

[2] 陳蘭蓀.非線性生物動力系統[M].北京:科學出版社,1993.

[3] 王海云.三峽庫區水華暴發演變的非線性行為效應研究[J].人民長江,2010,41(19):48-51.

[4] 王小藝.基于復雜網絡的城市湖庫藻類水華混沌時間序列預測方法:中國,201510128961.5[P].2015-03-24.

[5] 王一頡.多元混沌時間序列相關性分析及預測方法研究[D].遼寧 大連:大連理工大學,2008.

[6] 呂金虎.混沌時間序列分析及其應用[M].湖北 武漢:武漢大學出版社,2002.

[7]ZhangLichao,KongLiang,HanXiaodong,etal.Structuralclasspredictionofproteinusingnovelfeatureextractionmethodfromchaosgamerepresentationofpredictedsecondarystructure[J].JournalofTheoreticalBiology, 2016,400：1-10.

[8]YounesianD,NorouziH.ChaospredictioninnonlinearviscoelasticplatessubjectedtosubsonicflowandexternalloadusingextendedMelnikov’smethod[J].NonlinearDynamics, 2016,84(3):1163-1179.

[9] 韓敏,史志偉,郭偉.儲備池狀態空間重構與混沌時間序列預測[J].物理學報,2007,56(1):43-50.

[10] 周世兵.聚類分析中的最佳聚類數確定方法研究及應用[D].江蘇 無錫:江南大學,2011.

[11] 王開軍,李健,張軍英,等.聚類分析中類數估計方法的試驗比較[J].計算機工程,2008,34(9):198-199.

[12]CalinskiRB,HarabaszJ.Adendritemethodforclusteranalysis[J].CommunicationsinStatistics, 1974,3(1):1-27.

[13]HartiganJA,WongMA.AlgorithmAS136:AK-MeansClusteringAlgorithm[J].AppliedStatistics, 1979,28(1):100-108.

[14]ChenG,JaradatSA,BanerjeeN,etal.EvaluationandcomparisonofclusteringalgorithmsinanalyzingEScellgeneexpressiondata[J].StatisticaSinica, 2002,12(1):241-262.

[15]KrzanowskiWJ,LaiYT.Acriterionfordeterminingthenumberofgroupsinadatasetusingsum-of-squaresclustering[J].Biometrics, 1988,44(1):23-34.

[16] 姚德倉,宋松柏.設計洪水頻率曲線的粒子群優化適線法研究[J].水土保持通報,2007,27(6):112-115.

[17] 殷禮勝,何怡剛,董學平,等.交通流量VNNTF神經網絡模型多步預測研究[J].自動化學報,2014,40(9):2066-2072.

[18] 謝景新.非線性多步預測與優化方法及其在水文預報中的應用[D].遼寧 大連:大連理工大學,2006.

Dynamic Clustering Based on Nearest Neighbors for Predicting of Cyanobacteria Bloom in Lakes and Reservoirs

BAI Xiaozhe, ZHANG Huiyan, WANG Xiaoyi, WANG Li, XU Jiping, YU Jiabin

(Beijing Key Laboratory of Big Data Technology for Food Safety, College of Computer and Information Engineering, Beijing Technology and Business University, Beijing 100048, China)

[Objective] It is one of the key basic issue in the prevention and control of water environment by exploring effective prediction methods about cyanobacteria bloom in lakes and reservoirs. [Methods] Combined with the class random characteristic showed in the chaotic evolution of cyanobacteria bloom, this paper proposed a dynamic clustering algorithm based on the optimization of validity functions to achieve the optimal cluster number of cyanobacteria bloom and small-scale neighborhood optimal prediction. First of all, monitoring data were classified objectively by the proposed dynamic clustering algorithm to reduce effectively the search space and to improve the prediction accuracy. Then the optimal number of neighbors for all kinds was obtained using the particle swarm optimization algorithm, which was used to determine the number of participating in the local regressive algorithm. Finally, a dynamic regressive prediction model was established. [Results] The model established using the concentration data of chlorophyll a at the Jinshu monitoring site of Taihu Lake in 2011 was used to model and predict short-term variation of it in 2012. The predicted value of the model was consistent with the actual trend and the relative error was 12.02%, and was smaller than the ones predicted by other models, such as linear regression algorithm based on traditional clustering, BP neural network , and phase space reconstruction algorithm, whose relative errors were 15.21%, 19.51% and 38.42%. [Conclusion] Numerical results showed that the prediction accuracy of this method was relatively high, hence the feasibility and effectiveness of the optimization prediction method proposed were proved.

cyanobacteriabloom;dynamicclustering;nearestneighbormethod;prediction

B

： 1000-288X(2017)04-0161-05

： TP14， X524

2016-10-22

：2016-11-08

北京市屬高校創新能力提升計劃項目“北京河湖水環境監測與智能管理物聯網應用平臺”(PXM2014_014213_000033)； 北京市教委科技重點項目(KZ201510011011)； 北京市屬高校青年拔尖人才培育計劃(CIT&TCD201404031)

白曉哲(1993—),女(漢族),河北省邢臺市人,碩士研究生,研究方向為藍藻水華預測。E-mail:15031269259@163.com。

張慧妍(1973—),女(漢族),黑龍江省齊齊哈爾市人,博士,副教授,主要從事水質監測、數據建模、分類與預測方面的研究。E-mail:zhanghuiyan369@126.com。