一種適用于大氣污染數據聚類的距離度量

張忠帥，陳 梅，楊鵬飛

(蘭州交通大學 電子與信息工程學院，蘭州 730070)

近些年，由于人口的不斷增長和生產技術的持續發展，環境污染日益嚴重，空氣質量不斷下降，嚴重影響了公眾健康.為此，研究者在大氣污染源識別、污染物的遠程傳輸途徑以及制定和實施有效的控制和緩解策略等方面開展了大量的研究工作.空氣污染數據測量值并不是一個值或者具有單一的屬性，而是由不同類型的污染物元素組成的，所以采集的污染物數據集通常是多維數據集，同時包含了大量的異常值，因此，在對污染物溯源分析、傳播路徑研究時，需要綜合考慮這些因素，而污染物數據的多維性、空間的復雜分布、異常點的干擾等影響了這些研究的結果準確性[1].聚類分析按照數據點間的相似性進行分類,使得相似的數據點自然地被劃分到同一個簇，不相似的數據點被劃分到不同簇.聚類分析有利于更準確地分析區域間的污染特征，揭示不同地區間污染的相似性與關聯性，明晰污染特征[2].

作為數據挖掘中的一種重要技術，聚類是大氣污染分析中一個強有力的工具[3]，常用的算法有k-Means[4-5]，k-Medoids[6]以及DBSCAN(density-based spatial clustering of applications with noise)[7]等.文獻[8]使用SOM(self organizing maps)和k-Means分析了氣象條件與幾種空氣污染物之間的關系；文獻[9]使用k-Means算法分析了不同空氣污染排放源特征；文獻[10]在空氣污染監測網絡中，使用一種基于k-Medoids算法的分區方法來檢測信息冗余；文獻[11]采用分布式實現的k-Means對不同位置空氣污染模式進行了研究；文獻[12]利用DBSCAN算法和Convex-Hull技術，構建了一種新的技術來預測未來幾天的天氣，該預測方法旨在減輕空氣污染對人們生活的影響；文獻[13]對大氣污染的空氣輸送軌跡進行聚類分析模擬研究,給污染物來源和輸送途徑的研究提供新方法,進一步為大氣污染防控和污染監測站點的合理配置提供科學依據；文獻[14]使用SOM算法，在給定的區域發現健康和不健康地區，并揭示了空氣污染模式，有助于及時采取必要的預防措施，進一步控制污染.

在聚類算法中，根據數據特征選擇合適的相似性方法對獲得精確的聚類結果至關重要.常見的相似性計算方法有歐氏距離、曼哈頓距離和余弦相似度等，但是這些傳統相似性度量方法具有一定的局限性，比如應用最廣泛的歐氏距離，并不適用于維數較大的數據.而大氣污染數據通常由多個污染元素組成，從而屬性較多，每個數據點具有較高的維數，對這種情況通常的處理方式是對高維度數據集進行降維處理.但對于大氣污染抽樣數據集，進行降維處理會丟失污染信息，使一些污染元素特征模糊，導致聚類結果不準確.而且大氣污染抽樣數據集中同一個數據點的不同元素間的數量級差別通常非常大，比如，在同一時刻元素Si的濃度為15.211 μg/m3，元素As的濃度為0.002 μg/m3，在這種情況下，如果使用常用的歐氏距離，元素As假如有很明顯的相對濃度變化，即它攜帶了很明顯的污染特征，但由于元素Si、As的濃度之間的數量級相差懸殊，即使Si的相對濃度稍有變化，它對歐氏距離的貢獻也會遠大于As.這時，最常用的手段是對數據進行標準化處理，但標準化處理不可避免地會造成數據污染特征損失.為了提高對大氣污染物數據聚類的準確性，本文根據大氣污染物數據的特點，提出了一種新的距離度量方法.在該方法中，首先分別獲得兩點在每一維下的兩個值，求得這兩個值的較大值和較小值的差值與較大值的比值；然后將兩點在所有維度下的比值的最大值定義為這兩點間的距離.如果兩個點的大氣污染抽樣數據距離(air pollution data distance，簡稱PD距離)小意味著兩點污染程度處于同一水平，否則表示兩個點之間某種污染物的濃度急劇變化，即發生了某種元素的嚴重污染.

1 相似性度量方法

1.1 傳統相似性度量方法

常用的度量數據點之間相似性的函數包括三個距離函數和兩個相似性函數.首先，將大氣污染采樣數據集表示如下：

Dp={x1,x2,…,xn},

(1)

其中:n為數據集D中數據點的數量；p為每個數據點的屬性數量.

對于數據集中任意兩個點xi(1≤i≤n)∈Dp，xj(1≤j≤n)∈Dp,

xi={xi1,xi2,…,xip},

(2)

xj={xj1,xj2,…,xjp}.

(3)

其中:xi(1≤i≤n)∈Dp是p維上第i個數據點;xj(1≤j≤n)∈Dp是p維上第j個數據點;xik(1≤i≤n,1≤k≤p)∈Dp是一個非負的數值，表示點i在第k維的屬性值.

常用的距離函數和相似性函數有：

1) 歐氏距離(Euclidean metric,簡寫為EUC).歐氏距離是常見的距離計算方式，用于各種聚類算法，它用來計算兩點之間的最短距離，其表達式為

(4)

2) 曼哈頓(或城市街區)距離(Manhattan distance,簡寫為MH).計算的距離是兩點之間對應分量的差值之和，其表達式為

(5)

3) 切比雪夫距離(Chebyshev distance,簡寫為CB).它取兩點任意一維之間的最大距離值，其表達式為

(6)

4) 余弦相似性(Cosine similarity,簡寫為CON).余弦相似性是內積空間中兩個向量之間相似性的度量，度量的是它們夾角的余弦值，其表達式為

(7)

5) 皮爾遜相關系數(Pearson correlation coefficient,簡寫為PEAR).該函數是用于度量兩個向量xi和xj之間的相關性，其表達式為

(8)

1.2 PD距離度量

1.2.1 大氣污染抽樣數據特點

在對特定領域的數據進行聚類分析時，為得到更好的結果，需要分析樣本數據的特征以及基本性質.對于大氣污染抽樣數據，有以下特性：

1) 大氣污染抽樣數據點都包含同樣的污染特征或屬性，每個屬性的類型通常都是數值型的.這些屬性都是污染物排放量的一個組成部分，因此兩個大氣污染物的數據點是否相似取決于這兩個數據點的每一維屬性.當且僅當所有屬性都相似時，兩個污染物數據點才是相似的.

2) 大氣污染抽樣數據通常包含了很多種污染元素濃度或污染指標情況，數據屬性較多，因此每個數據點的維數都較高.

3) 由于大氣中顆粒物濃度差異較大，尤其在遭遇極端天氣情況下，大氣污染抽樣數據集中不同元素的污染物濃度有時會相差好幾個數量級.

1.2.2 PD距離

本節將詳細描述適用于大氣污染數據聚類的PD距離度量.

定義1對于Dp中的兩個點xi和xj，xik，xjk分別為點xi和xj在第k維的值.定義higher()函數，若xik≥xjk，則higher(xik,xjk)=xik；若xik

定義2對于Dp中的兩個點xi和xj，xik，xjk分別為點xi和xj在第k維的值.定義lower()函數，若xik≤xjk，則lower(xik,xjk)=xik；若xik>xjk，則lower(xik,xjk)=xjk.

對于每一維度，設xi,xj∈Dp，則

(9)

其中：higher(xik,xjk)=xik為xik，xjk中較大值；lower(xik,xjk)=xik為xik，xjk中較小值.

同時，考慮到較強的空氣污染可以導致數據某一維的數據值急劇增大，而急劇增大的數據正好可以反應出當前污染特征.比如：硝酸根和硫酸根離子的濃度急劇增大意味著酸雨污染.由此，本文定義xi和xj間的PD距離如下：

(10)

PD距離滿足以下性質：

1) 反應了污染物濃度變化特征.使用PD距離度量不用對數據集進行降維或標準化處理，保留了數據集的全部信息，在式(9)中，通過higher(xik,xjk)-lower(xik,xjk)，刻畫了大氣污染數據集中第k維上某污染元素濃度的變化，可以很好地反應出數據集中污染濃度變化特征.

2) 對稱點之間距離相等，即PD(xi,xj)=PD(xj,xi).對于一對點xi,xj∈Dp，xi到xj的距離等于xj到xi的距離.

3) 消除了維數的影響.如式(9)所示，PD距離的大小取決于一對點(xi,xj)在相同維度下，較大值與較小值的差與較大值的比值.從式(9)中可以看出，兩點之間PD距離的大小與其它維度無關，因此，它可以消除數據的維數對聚類結果的影響.

4) 消除數量級的影響.在大氣污染抽樣數據集中，不同污染物濃度的數量級可能差別很大.比如：某日某地區沙塵暴天氣，空氣質量指數中PM10的指數遠高于其他污染指數，各指數間數量級相差很大.如果使用常見的距離度量，其他污染物指數的變化就會被掩蓋；而在PD距離中，通過higher(xik,xjk)-lower(xik,xjk)與higher(xik,xjk)作商，可以消除不同污染物濃度值之間數量級的影響，從而降低大氣污染抽樣數據集中每一維上數據數量級不同對聚類結果的影響.因此，PD距離度量適用于大氣污染抽樣數據集聚類分析中的距離計算.

2 仿真實驗結果分析

通過在4個經典聚類算法及兩個新聚類算法中切換不同的相似性函數，對比分析PD距離與其它幾個距離及相似度在同一數據集上的聚類性能.使用的數據集包括人工合成大氣污染受體數據集、真實大氣污染受體數據集和蘭州市空氣污染指數數據集.

2.1 對比算法及評價指標和參數分析

2.1.1 對比算法分析

為了評估PD距離的實際性能，對比實驗使用了6種聚類算法，也是大氣污染物分析中較為常見的聚類方法.其中：k-Means，k-Medoids，DBSCAN，OPTICS[15]4個算法是非常經典的聚類算法；MulSim[16]和AnyDBC[17]是近幾年提出的新算法，由相應作者提供代碼.下面對6個對比算法進行簡單分析.

k-Means和k-Medoids這兩個算法是基于劃分的經典算法，k-Medoids算法實質上是對k-Means算法的優化和改進.二者都是先隨機選取中心點，然后將剩余點劃分到離它最近中心點所在的簇；更新簇中心，重復這一過程，直到中心點不再變化.二者的區別是更新簇中心的方式，k-Means更新的簇中心是簇中所有點的平均值，k-Medoids挑選的簇中心是實際樣本點.這兩個算法中，初始中心點的選取對結果影響較大.

DBSCAN和OPTICS這兩個優秀的算法是基于密度的聚類算法.DBSCAN的特性是將出現在特征空間密集區域的“核心點”與被分類為不屬于任何簇的離群值(“噪聲點”)分開.它可以識別具有任意形狀的簇，但如果數據集密度不均勻時，得到的結果較差，且結果受參數影響較大.OPTICS算法可以看作DBSCAN的改進算法，在聚類過程中，首先創建一個存放核心點與其核心距離按可達距離升序排列的所有鄰居點的隊列和一個存放按處理先后順序輸出的數據點的隊列；然后，迭代地搜索核心點及其直接可達點，將可達距離最小的點放到結果序列中，直到所有數據點都被標記；最后生成一個以數據點輸出次序為橫軸，可達距離為縱軸的增廣的簇排序.OPTICS算法可以獲得任意密度下的結果.

MulSim和AnyDBC是近幾年提出的新算法.MulSim定義了一種新的策略，即當且僅當一個點與另一個點相似，且同時與這個點一個或多個最近鄰相似，則將這兩個點劃分在同一簇.這種策略可以發現數據集中任意密度、任意形狀、任意大小的簇.AnyDBC算法的核心是一種主動學習的方法，與經典算法相比，AnyDBC不是對所有的數據點進行搜索查找，而是學習當前數據集的簇結構，選擇一些最理想的對象來進行范圍查詢.因此AnyDBC與DBSCAN相比，它最終執行的查詢范圍要少得多.此外，AnyDBC基于初始簇進行劃分，以減少搜索時間.對于數據量非常大和復雜的數據集，AnyDBC有著出色的表現.

2.1.2 評價指標分析

本文使用的算法評價指標有三個：兩個外部評價方法和一個內部評價方法. 當數據集中簇的真實結構已知時，使用外部評價方法ARI(adjusted rand index)[18]和NMI(normalized mutual information)[19]，ARI取值范圍是[-1,1]，NMI取值范圍是[0,1]，這兩個指標的值越大表示聚類結果與真實結果越接近；當數據集中簇的真實結構未知時，使用內部評價方法DBI(davies-bouldin index)，DBI也稱為戴維森堡丁指數，它的值越小，代表簇內越緊密、簇間越離散，意味著聚類效果越好.

2.1.3 參數分析

圖1、表1和表2分別展示了PD距離與對比的相似性函數分別在3個數據集和6個對比算法下的實驗結果，表中包含了最優聚類結果下的評價指標以及相應的參數值.其中：k-Means，k-Medoids的參數k為簇的個數；DBSCAN的兩個參數ε和MinPts分別為每個點的最小鄰域半徑以及半徑內最小點的個數；OPTICS中k為最近鄰的個數；MulSim中兩個參數為距離閾值k和兩點中某一點的鄰居數m；AnyDBC有兩個參數，分別是最小鄰域半徑r以及半徑內最小點的個數m.

圖1 在人工合成的大氣污染抽樣數據集上的聚類結果Fig.1 Clustering results on the synthetic air pollution datasets

表1 在真實空氣污染采樣數據集上的聚類結果

對于k-Means與k-Medoids算法，當數據集簇數已知時，使用ARI和NMI評價指標，迭代地調整算法各自相應的參數，得到最大的ARI和NMI，確定最優的聚類結果.當數據集簇數k未知時，使用DBI評價指標，迭代地調整算法中各自相應的參數，得到最小的DBI，確定最優的聚類結果.

對于算法DBSCAN，OPTICS，MulSim和AnyDBC，其最優結果都通過對相應的外部評價指標和內部評價指標迭代尋優獲得.

2.2 人工合成大氣污染抽樣數據集實驗分析

2.2.1 數據集介紹

本實驗評估從具有不同特征的人工合成的大氣污染抽樣數據集所得到的聚類結果，數據集來自文獻[20].該數據集形成過程為：每次從8個標準污染源中隨機選擇兩個，改變它們的質量濃度，得到新的源貢獻的中心點；然后根據標準源成分譜，生成800個受體數據點并標記為簇1；接下來重復3次該過程，再生成3組各包含800個受體數據點，并分別標記為簇2、簇3和簇4；最后將4組數據點隨機打亂順序，加入到同一個數據集中，形成共有3 200個帶標簽的數據點的數據集.

2.2.2 結果分析

如圖1所示，圖中展示了PD距離與其他對比相似性函數在人工合成的大氣污染抽樣數據集中6個對比算法下的聚類評價結果，其中包括最優結果的ARI和NMI值.對于每個算法，通過設置相應的輸入參數迭代進行，其最優的聚類結果都由最大的ARI和NMI確定.由于已知數據集共有4個簇，因此k-Means和k-Medoids中參數k的值設為4.圖1中OPTICS算法在余弦距離和皮爾遜相關系數中存在無效值，AnyDBC算法在切比雪夫距離中存在無效值，這是因為這兩種算法都是基于密度的聚類算法，由于數據集的特殊性，在調整參數對ARI和NMI迭代尋優的過程中，始終無法得到有效的密度，導致每一個數據點被劃分為一個單獨的簇，產生了無效的聚類結果.

1) 在k-Means和k-Medoids算法中，使用PD距離的聚類結果最好，ARI和NMI值都為1.000，可以準確地識別出數據集中的真實簇結構，優于其他距離函數下的聚類結果；采用余弦相似度和皮爾遜相關系數的結果分別獲得了第二位和第三位的名次；使用切比雪夫距離和歐氏距離的結果值緊隨其后；在這兩個算法中，使用曼哈頓距離下的聚類結果最差.

2) 在DBSCAN和OPTICS算法中，PD距離下的聚類結果與其他距離及相似度下的聚類結果相比仍為最優.在DBSCAN算法中，使用PD距離得到的ARI和NMI結果值均為1.000；切比雪夫距離和歐氏距離下的結果值排名第二和第三；曼哈頓距離下的聚類結果相較之下為最差.在OPTICS算法中，使用PD距離的聚類結果與切比雪夫距離下的結果一樣，同為最優；其后分別是曼哈頓和歐氏距離下的結果值.

3) 在MulSim和AnyDBC兩個算法中，PD距離下的ARI和NMI值均為1.000.在MulSim算法中，歐氏距離和切比雪夫距離下的結果與PD距離下的結果同為最優；曼哈頓距離和皮爾遜相關系數下的結果分別排第二位和第三位.AnyDBC算法中，PD距離下的結果最優；歐氏距離和切比雪夫距離下的結果值也較好，但次于PD距離.對于曼哈頓距離，通過大量實驗調整參數，聚類結果始終為一個簇，結果值無效.

根據以上分析可得：在該數據集上，6個聚類算法使用PD距離的聚類結果均為最優，而其他距離函數在不同的算法中表現不一致.

2.3 真實空氣污染采樣數據集實驗分析

2.3.1 數據集介紹

2.3.2 結果分析

如表1所列，表中展示了PD距離與其它對比相似度函數在空氣污染真實采樣數據集中6個對比算法下的聚類評價結果.由于數據集為實際采樣中得到，真實簇結構未知，因此使用內部評價指標DBI.DBI的值越小，聚類效果越好.所以對于每個算法，通過設置相應的輸入參數迭代進行，其最優的聚類結果都由最小的DBI確定.在k-Means和k-Medoids算法中，參數的值是評價指標值最好時所對應的參數.觀察表1中數據可得：

1) 在k-Means算法和k-Medoids算法中，最好的聚類結果是在使用PD距離時獲得.在k-Means算法中，僅次于最優值的分別是曼哈頓距離和皮爾遜相關系數下的結果值，歐氏距離則在該算法中表現不佳；在k-Medoids算法中，排名第二位和第三位的分別是在余弦相似度和皮爾遜相關系數下的取值.

2) 在DBSCAN算法中，聚類效果最好的是使用PD距離下的結果，排名第二位的是使用切比雪夫距離下的結果，使用曼哈頓距離下的結果和使用歐氏距離下的結果很接近，分別排第三、第四名，效果最差的是使用余弦相似度下的結果；在OPTICS算法中，DBI值最小的是使用PD距離函數的結果，其次分別是使用曼哈頓距離和歐氏距離的結果，使用余弦相似度下的結果最差.

綜合所有結果可知：在真實空氣污染采樣數據集上，使用PD距離函數在絕大多數算法中均能取得較優的聚類結果.

2.4 蘭州市空氣質量指數數據集實驗分析

2.4.1 數據集介紹

本實驗使用蘭州市空氣質量指數數據集來評估PD距離的性能，空氣質量指數數據由蘭州氣象局提供.數據集包含了2001-2011年的蘭州空氣質量指數，每天一個數據，共4 018個數據點，包含了SO2、NO2和PM10三種空氣污染物濃度.

2.4.2 結果分析

如表2所列，表中展示了PD距離與其他對比相似度函數在蘭州市空氣質量指數數據集中6個對比算法下的聚類評價結果，本實驗采用內部評價的方法.由于蘭州市為溫帶大陸性氣候，四季特征分明，每個季節的空氣質量也相差較大，故在k-Means和k-Medoids這兩個算法中將參數k設為4，然后尋找最優值.在OPTICS算法中，采用PD距離在鄰居個數大于2時，算法將數據集劃為一個簇，聚類結果無效；為了消除參數范圍不同帶來的影響，將其他距離函數下的參數也在鄰居小于2的值中尋優.

1) 在k-Means和k-Medoids算法中，6個距離下的DBI值都較高，相比之下，在PD距離下的DBI值最小，聚類效果最好.其中：在k-Means算法中，采用歐氏距離和切比雪夫距離的聚類結果分別排第二和第三位，采用余弦相似度的結果最差；在k-Medoids算法中，采用曼哈頓距離和歐氏距離下的聚類結果較優，使用皮爾遜相關系數的結果最差.

表2 蘭州市空氣質量指數數據集上的聚類結果

2) 在DBSCAN算法中，聚類結果最優的是使用PD距離下的結果，使用切比雪夫距離和曼哈頓距離下的結果雖然不如使用PD距離下的結果，但也表現較優，最差的是使用皮爾遜相關系數下的結果.在OPTICS算法中，使用PD距離得到的DBI值最小，結果最優，其余的結果值相差不大，使用余弦相似度和皮爾遜相關系數不能產生正確的劃分.

3) 在MulSim算法中，使用PD距離的結果明顯優于其他距離函數下的結果.其中：使用余弦相似度的結果排名第二位，使用曼哈頓距離的結果排名第三位，使用皮爾遜相關系數的結果最差.在AnyDBC算法中，使用PD距離的結果值最優，排名第二位和第三位的結果值分別是使用曼哈頓距離函數的結果值和使用歐氏距離函數的結果值.DBI值最大的是使用余弦相似度下的結果值，聚類效果最差.

由以上分析可得：在蘭州市空氣質量指數數據集上，PD距離在6個聚類算法中表現仍為最優，聚類效果最好，性能優于其他傳統距離函數以及相似性函數；歐氏距離函數在k-Means和k-Medoids這兩個算法中表現較優；切比雪夫距離和曼哈頓距離在DBSCAN算法中表現較好；余弦相似度在MulSim算法中結果較好.

3 結論

為了提高對大氣污染抽樣數據聚類的精確性，本文針對大氣污染物數據的特點，提出了一種新的相似性度量——PD距離.PD距離用所有維度的最大值檢測是否發生了某種污染，另外還可以反應大氣污染物濃度變化特征，消除維數以及不同屬性間數量級的差異對聚類結果的影響.為了驗證PD距離的性能，在3個大氣污染抽樣數據集中，將PD距離與其他5個傳統的距離及相似性度量方法分別在6個聚類算法中進行對比.仿真實驗結果表明：使用PD距離得到的聚類結果在6個聚類算法中均優于使用其他傳統距離得到的結果.在下一步的研究中，將基于PD距離提出一種基于密度的大氣污染數據聚類算法，得到更優的聚類結果，并在此基礎上進一步分析大氣污染特征.