彭 碩，郭 晨，周 松，王 博

基于改進凝聚層次聚類算法的生態(tài)環(huán)境監(jiān)測采樣點優(yōu)選技術(shù)研究

彭 碩1，郭 晨1，*周 松2，王 博1

(1.井岡山大學電子與信息工程學院，江西，吉安 343009；2.井岡山大學商學院，江西，吉安 343009)

隨著經(jīng)濟的快速發(fā)展，我國的生態(tài)環(huán)境面臨著越來越大的壓力，對生態(tài)環(huán)境的監(jiān)測和預(yù)警是維護綠色生態(tài)環(huán)境可持續(xù)發(fā)展的重要措施。獲得最為理想的生態(tài)環(huán)境數(shù)據(jù)是開展生態(tài)監(jiān)測和預(yù)警的前提，而合理的采樣點選擇是生態(tài)環(huán)境監(jiān)測中一個重要環(huán)節(jié)。本文介紹了一種對采樣點進行優(yōu)選的方法，首先利用數(shù)據(jù)預(yù)處理技術(shù)對初始環(huán)境監(jiān)測數(shù)據(jù)進行處理，之后利用基于改進凝聚層次聚類算法對環(huán)境監(jiān)測數(shù)據(jù)進行聚類，最后選出距離聚類中心最近的采樣點作為優(yōu)選采樣點。整個處理技術(shù)簡單有效，對于中小規(guī)模的生態(tài)環(huán)境監(jiān)測采樣點的優(yōu)選具有現(xiàn)實意義。

環(huán)境監(jiān)測；采樣點；數(shù)據(jù)聚類；凝聚層次聚類

0 引言

當前，生態(tài)環(huán)境問題日益突出，對生態(tài)環(huán)境指標的監(jiān)測與預(yù)警是對生態(tài)環(huán)境問題進行調(diào)查和研究的重要手段，而對研究對象的采樣又是進行生態(tài)環(huán)境監(jiān)測和預(yù)警的一個重要環(huán)節(jié)，這個環(huán)節(jié)出現(xiàn)問題或者選擇不當，后續(xù)的分析工作無論多么的精確、無誤，其結(jié)果都是毫無意義的，而由此得出的結(jié)果也將導(dǎo)致對環(huán)境狀態(tài)的誤判。

在生態(tài)環(huán)境監(jiān)測的采樣過程中，如何合理地選擇采樣點是獲得準確而可靠的環(huán)境監(jiān)測數(shù)據(jù)所必須面對的問題。以地下水采樣為例，當前的采樣點選取原則大都是依循水質(zhì)采樣技術(shù)規(guī)程[9]來實施，主要以布設(shè)采樣井和使用現(xiàn)有民用井，在具體的采樣過程中，尤其是針對小范圍生態(tài)環(huán)境監(jiān)測的過程中，往往都是使用現(xiàn)有民用井，采樣人員往往需要在十幾個甚至幾十個候選采樣點里來選擇，而如何選擇最具代表性的采樣點，使得其能反映出該區(qū)域地下水質(zhì)的典型特征，成為了采樣人員的一個困擾。鑒于此，本文采取數(shù)據(jù)挖掘的一些手段對采樣點進行進一步分析和處理，以建立一個更加合理和更具有代表的采樣點。

本文的研究旨在利用基于凝聚層次的聚類算法對符合采樣原則的采樣點進行進一步優(yōu)選，以選取出最具特征性的代表性采樣點，并把該技術(shù)用于景區(qū)村落地下水采樣點的選擇上。整個處理過程簡單有效，對于中小規(guī)模的生態(tài)環(huán)境監(jiān)測采樣點的優(yōu)選具有現(xiàn)實意義。

1 預(yù)備知識

1.1 數(shù)據(jù)聚類

數(shù)據(jù)聚類（Data Clustering）是把待處理的數(shù)據(jù)集分割成互不相交的多個類或者簇（Cluster），這種分割出來的類是事前未知的類，各個簇之間的相異度需要保持較大，而類內(nèi)部的相異度要求維持較小[8]。數(shù)據(jù)聚類可以把數(shù)據(jù)集中的數(shù)據(jù)進行識別，最終得出多個濃密和稀疏的數(shù)據(jù)區(qū)域，從而得到數(shù)據(jù)集中各種數(shù)據(jù)的總體分布情況，以及各個屬性間的有趣關(guān)聯(lián)[1]。

當前在數(shù)據(jù)挖掘領(lǐng)域中的數(shù)據(jù)聚類分為如下幾種方法：劃分法、層次法、基于密度的方法、基于網(wǎng)格的方法和基于模型的方法[3]。上述的5種方法在具體的應(yīng)用過程上都存在著不同程度的限制和約束條件，有的是無法對整個數(shù)據(jù)集的數(shù)據(jù)動向進行準確的定位，有的是無法對冗余數(shù)據(jù)屬性和數(shù)據(jù)對象進行清理，或者是需要有前提的簇數(shù)或者既定的分類閾值。

本文研究的數(shù)據(jù)集具有生態(tài)環(huán)境的特點，所以本文基于此特點對基于凝聚層次的聚類算法進行改進，使得算法更加適用于生態(tài)環(huán)境監(jiān)測數(shù)據(jù)集的處理，從而達到更好的聚類和優(yōu)選效果。

1.2 凝聚層次聚類方法

在層次法中，聚類劃分是通過層次來進行的，不需要在初始輸入指定要分成的簇數(shù)。層次聚類方法分為自底向上和自頂向下兩種情況進行，根據(jù)這兩種情況，層次的聚類方法可以進一步分為凝聚型和分裂型層次聚類[2]。

凝聚型層次聚類方法是層次方法中使用最為廣泛的一種方法[5]，凝聚型層次聚類是一種自底向上的聚類方法，這種方法首先是將每一個數(shù)據(jù)對象認定為一個初始簇，然后根據(jù)一些選定的規(guī)則對初始簇進行一步一步的合并，使得初始簇變得越來越大，直到所有的數(shù)據(jù)對象都包含在一個簇中，或者滿足某個設(shè)定的終結(jié)條件[6]。初始簇之間的合并規(guī)則有4種，包括：單鏈接、全鏈接、平均鏈接和重心法[6]。

有關(guān)距離的計算常用的有三種，分別是：歐幾里得距離、曼哈坦距離和明考斯基距離。最常用的是歐幾里得距離，它的定義如下：

其中對象=(x1,x2,…,x)，

(x1,x2,…,x)有p個屬性。

2 基于改進凝聚層次聚類的采樣點優(yōu)選技術(shù)

基于改進凝聚層次聚類的采樣點優(yōu)選技術(shù)是利用凝聚層次聚類同時結(jié)合生態(tài)環(huán)境監(jiān)測數(shù)據(jù)的特點對環(huán)境監(jiān)測的采樣點進行優(yōu)選的技術(shù)。本技術(shù)首先使用數(shù)據(jù)標準化技術(shù)對初始生態(tài)環(huán)境監(jiān)測數(shù)據(jù)樣本集進行標準化處理，以建立起具有獨立性并且屬性權(quán)重適當?shù)臉藴驶攘繑?shù)據(jù)矩陣，然后通過改進的凝聚層次聚類算法計算出結(jié)果簇的數(shù)目和簇中心，最后通過計算各個結(jié)果簇中最靠近簇中心的樣本點來最終確定優(yōu)選采樣點的位置，處理過程如圖1所示。

圖1 基于改進凝聚層次聚類的采樣點優(yōu)選技術(shù)流程圖

2.1 初始生態(tài)環(huán)境監(jiān)測數(shù)據(jù)集的標準化

環(huán)境監(jiān)測數(shù)據(jù)集的標準處理過程的第一步是要對環(huán)境監(jiān)測數(shù)據(jù)庫進行預(yù)處理，預(yù)處理過程包括對特征變量的選擇和提取以及標準化處理。

特征變量的提取和選擇主要是針對某些特定的屬性和屬性集合之間存在著的某種程度的相關(guān)性而進行的，處理后的環(huán)境監(jiān)測數(shù)據(jù)集中只包含一些相互獨立的特征屬性。

同時由于初始生態(tài)環(huán)境監(jiān)測數(shù)據(jù)集中各屬性的取值范圍和單位不同，直接影響到屬性之間的權(quán)重比例，導(dǎo)致對最終結(jié)果產(chǎn)生影響。因此，要對數(shù)據(jù)集進行標準化。初始生態(tài)環(huán)境監(jiān)測數(shù)據(jù)集的標準化是要給所有的屬性一個合理的權(quán)重，在屬性性質(zhì)一致的時候通常取相同的權(quán)重，但是在一些重要屬性上需要合理地提高其權(quán)重比例。

由于初始生態(tài)環(huán)境監(jiān)測數(shù)據(jù)集在剔除屬性相關(guān)性之后數(shù)據(jù)屬性上具有相同性，所以視為具有相同權(quán)重，這種情況下只需要將原來的度量值轉(zhuǎn)換為無單位的值即可。初始生態(tài)環(huán)境監(jiān)測數(shù)據(jù)集需要經(jīng)過以下3個步驟的變換之后轉(zhuǎn)換成標準化數(shù)據(jù)集合，如圖2所示。

圖2 數(shù)據(jù)集的標準化流程圖

2.1.1 初始生態(tài)環(huán)境監(jiān)測數(shù)據(jù)集

2.1.2 計算屬性的平均絕對偏差

2.1.3 計算屬性的標準化度量值

2.1.4 標準化度量數(shù)據(jù)矩陣

2.2 基于改進凝聚層次聚類算法的生態(tài)環(huán)境監(jiān)測采樣點優(yōu)選技術(shù)

本文在對初始環(huán)境監(jiān)測數(shù)據(jù)集進行標準化處理之后，使用改進的凝聚層次算法來對標準化數(shù)據(jù)集進行聚類。在選擇凝聚層次算法的具體類型時，考慮到單鏈接算法計算較為簡單有效，因此本文對單鏈接法的凝聚層次聚類算法進行改進，再把算法應(yīng)用于標準化度量后的監(jiān)測數(shù)據(jù)矩陣。

算法假設(shè)有個對象，表示為1,2,…,I這個對象需要進行數(shù)據(jù)聚類，本文提出的基于改進凝聚層次聚類算法描述如下：

Input:個對象的特征相異度矩陣Output：簇數(shù)及最靠近簇中心的數(shù)據(jù)對象 Step1:把每一個對象當成一個初始簇，即Ci={Ii}(i=1,2,…,n)，這樣初始就有n個簇；Step2: 將對象中相異度值Sij按升序進行排序，并組成一個三元組，其中。由于環(huán)境監(jiān)測誤差的存在，且相異度高于平均值是難以在同一個簇中出現(xiàn)，所以算法需要去除三元組中相異度最大的40%的三元組，這些三元組將不參與合并操作。Step3:把三元組中最小的兩個類進行合并，合并之后的新簇記為簇，其中初始等于1。Step4:合并三元組順序中下一組對象組，合并需要考慮以下四種情況：Case a:如果和都沒有新簇中出現(xiàn)，那么合并組成新類，自增 1；Case b:如果和都出現(xiàn)在同一個新簇中則跳轉(zhuǎn)到到Step5；Case c:如果和其中一個已被合并到某一新簇，則將另一個也合并到該新簇中；Case d:如果它們已分別被合并到兩個不同的新簇，則將它們所在的那兩個類合并成一個新簇，自增 1；Step5:取有序表中的下一個三元組，重復(fù)Step 4，直至結(jié)束。Step6:采用重心法計算出各個采樣點新簇的中心點位置，然后以歐幾里得距離為度量方法，計算出離采樣點新簇中心點最近的采樣點，并輸出該采樣點作為最終的優(yōu)選采樣點。

算法的輸出是得到簇數(shù)及最靠近簇中心的數(shù)據(jù)對象，算法的聚類結(jié)果可能會存在著某一個采樣點不在任何一個新簇中，這表明該采樣點是一個數(shù)據(jù)孤立點，孤立點出現(xiàn)的原因可能是采樣手段不當而導(dǎo)致與其他采樣點的數(shù)據(jù)存在著較大偏差而不具有代表性。

3 實驗

本文以井岡山區(qū)域景區(qū)村落環(huán)境監(jiān)測示范點——新干縣華城門村的地下水采樣點環(huán)境監(jiān)測數(shù)據(jù)集為例進行實驗。初始采樣點環(huán)境監(jiān)測數(shù)據(jù)包括該示范點區(qū)域的所有地下水井的監(jiān)測數(shù)據(jù)，記為A1到A32，如表1所示。監(jiān)測指標采取的是國標《地下水質(zhì)量標準》[7]。具體包括：pH值、總硬度、硫酸鹽、氯化物、鐵、錳、銅、鋅、揮發(fā)酚、陰離子合成洗滌劑、高錳酸鹽指數(shù)、硝酸鹽、亞硝酸鹽、氨氮、氟化物、氰化物、汞、砷、硒、鎘、鉻、鉛以及總大腸菌群，同時加上采樣點名稱、采樣點編號以及經(jīng)度、緯度構(gòu)成一個由27個屬性組成的初始數(shù)據(jù)庫。初始數(shù)據(jù)庫中采樣點名稱和采樣點編號不作為特征屬性使用，也不參與到屬性的優(yōu)選處理過程中。

通過計算，參與屬性優(yōu)選處理的25個屬性平均值見表1，其中經(jīng)度和緯度中的度分秒表示需要統(tǒng)一為以度為單位，保留到小數(shù)點后7位，其中氰化物、汞、鎘和鉻4個屬性的平均值為0，表示這4個屬性沒有超過檢出最低限值。

表1 采樣地點及編號

參與屬性優(yōu)選處理的25個屬性的平均絕對偏差見表2，其中氰化物、汞、鎘和鉻4個屬性的平均絕對偏差仍然為0。

通過計算屬性的平均值和平均絕對偏差值，可以確定氰化物、汞、鎘和鉻這4個屬性在整個數(shù)據(jù)庫中影響力權(quán)值為0，所以在接下來的處理過程中將不進行計算和評價。

表2 初始數(shù)據(jù)庫的屬性平均值

參與屬性優(yōu)選處理的25個屬性的平均絕對偏差見表3，其中氰化物、汞、鎘和鉻4個屬性的平均絕對偏差仍然為0。

通過計算屬性的平均值和平均絕對偏差值，可以確定氰化物、汞、鎘和鉻這4個屬性在整個數(shù)據(jù)庫中影響力權(quán)值為0，所以在接下來的處理過程中將不進行計算和評價。

表3 初始數(shù)據(jù)庫屬性的平均絕對偏差

接下來根據(jù)公式3進行標準化處理和相異度計算,建立起標準化度量數(shù)據(jù)矩陣S和相異度計算，根據(jù)相異度矩陣中的每個值S相異度進行排序建立起三元組l=(c,c,S)，見表4。

表4 相異度矩陣排序三元組

4 結(jié)束語

當前生態(tài)環(huán)境問題日益突出，生態(tài)環(huán)境監(jiān)測與預(yù)警是當前的一個熱點研究領(lǐng)域[10]。本文通過研究生態(tài)環(huán)境采樣點的優(yōu)選技術(shù)，提出了一種基于改進凝聚層次聚類算法的生態(tài)環(huán)境監(jiān)測采樣點優(yōu)選技術(shù)，以技術(shù)手段對采樣點的選取進行合理性的精確定位，從而保障了數(shù)據(jù)的代表性和可靠性。

[1] 馮治宇.網(wǎng)格采樣—聚類分析在優(yōu)化環(huán)境監(jiān)測點中的應(yīng)用[J].環(huán)境工程,2003,21(2): 55-58.

[2] 李娜,鐘誠.基于劃分和凝聚層次聚類的無監(jiān)督異常檢測[J].計算機工程,2008,34(2): 120-123.

[3] 尉景輝,何丕廉,孫越恒.基于K-Means 的文本層次聚類算法研究[J].計算機應(yīng)用,2005,25(10): 2323-2324.

[4] Han J,Kamber M.數(shù)據(jù)挖掘概念與技術(shù)[M].范明,孟小峰譯.北京:機械工業(yè)出版社,2004.

[5] 王洋,涂登彪,安明遠,等.層次凝聚聚類算法的動態(tài)分析與準則函數(shù)設(shè)計[J].高技術(shù)通訊,2013,22(11): 1169- 1175.

[6] 陳亞平，吳陳.FCM聚類算法與改進層次聚類算法的結(jié)合[J].科學技術(shù)與工程,2009(17): 5008-5011.

[7] GB/T14848-93.地下水質(zhì)量標準[S].1993

[8] 冷明,孫凌宇,郁松年.無向賦權(quán)圖剖分優(yōu)化問題的研究進展[J].井岡山大學學報:自然科學版,2010,31(1):82-90

[9] SL187-96.水質(zhì)采樣技術(shù)規(guī)程[S].1996.

[10] 王博,萬春,周松,等.基于模糊數(shù)學的景區(qū)村落生態(tài)環(huán)境評價技術(shù)研究[J].井岡山大學學報:自然科學版, 2014,35(3):59-63.

RESEARCH ON SELECTION OF PREFERRED ECOLOGICAL ENVIRONMENT MONITORING SAMPLING POINT BASED ON AN IMPROVED HIERARCHICAL AGGLOMERATIVE CLUSTERING ALGORITHM

PENG Shuo1，GUO Chen1，*ZHOU Song2， WANG Bo1

(1. School of Electronic Information and Engineering,Jinggangshan University,Ji’an, Jiangxi 343009,China;2.School of Business, Jinggangshan University, Ji’an, Jiangxi 343009, China)

With the rapid development of economy in our country, ecological environment is becoming more and more stressful.Environmental monitoring and early warning on the environment are important aspects to maintain the ecological green and sustainable development. In order to get the most optimal ecological environment data under limited conditions,we should carry out a reasonable selection of a preferred sampling point. Therefore, the selection of a preferred environmental monitoring sampling point is an importantpart of ecologicalenvironmental monitoring. Initial environment monitored data is processed first by usinga series of data preprocessing techniques. Therefore, environment monitored data is clustered by using a clustering algorithm based on improved agglomerative hierarchy. Finally, a sampling pointclosest tothe cluster center is selected as a preferred sampling point. The whole processis simple and effective and has arealistic significance for selecting a preferred sampling point during a small and medium scale ecological environment monitoring.

environmental monitoring; sampling point; data clustering; hierarchical agglomerative clustering

X830.1

A

10.3969/j.issn.1674-8085.2014.06.011

1674-8085(2014)06-0048-06

2014-05-11；

2014-09-15

國家科技支撐計劃項目(2012BAC11B03)；江西省科技支撐計劃項目(20123BBG70221)

彭 碩(1982-)，男，江西吉安人，講師，碩士，主要從事計算智能，數(shù)據(jù)挖掘等研究(E-mail: pengshuo@jgsu.edu.cn);

郭 晨(1979-)，男，江西泰和人，副教授，博士生，主要從事算法優(yōu)化研究(E-mail: 519670255@qq.cm);

*周 松(1964-)，男，江西吉安人，教授，主要從事環(huán)境監(jiān)測，科技管理等研究(E-mail: zhousong@jgsu.edu.cn);

王 博(1980-)，男，江西吉安人，講師，碩士，主要從事神經(jīng)網(wǎng)絡(luò)計算研究(E-mail:ganjgszs307@163.com).