一種函數型模糊聚類算法及其應用

楊夢玲

摘要：針對已有模糊聚類算法（FCM）提出一種函數型模糊聚類算法，旨在解決海量數據的模糊聚類問題。為此，在利用B-樣條基底進行曲線擬合、曲線距離度量界定的基礎上，構造模糊聚類算法的目標函數，提出函數型模糊曲線聚類算法。模擬及實例表明：本文曲線聚類算法具有更好的聚類效果。

關鍵詞：曲線擬合;模糊聚類;B-樣條;距離度量

中圖分類號：TP311.1?文獻標志碼：A?文章編號：1008-4657（2019）05-0018-08

0?引言

信息技術的發展，數據來源越來越廣泛。數據采集密集化程度也越來越高。隨之出現一種具有明顯曲線特征的數據類型，如腦電信號數據、基因序列數據、股票分時成交價數據、環境污染物濃度數據等，就具有這樣的特征。相關文獻稱之為函數型數據（Functional Data）[1]。

實際數據采集中，獲取的數據通常為離散數據，無法直接獲取函數型數據。針對離散數據可以通過傳統多元統計方法分析。但是傳統的多元統計方法無法分析數據的函數型特征，同時也需要處理高維問題。因此，基于傳統統計分析方法往往無法取得較好的分析結果。針對函數型數據的曲線特征，人們提出很多分析方法，包括函數型主成分[2]、函數型聚類分析[3]等。這類方法在函數型數據分析中發揮著重要的作用。

從方法角度來看，目前函數型數據分析方法大致分為兩類：一類是原始數據法[4]，原始數據法是一種高維數據分析方法，該類方法直接針對離散樣本點進行聚類。盡管能取得一定結果，但是沒有考慮到數據的函數型特征。因此無法深入挖掘數據的潛在特征且計算成本大。第二類是投影方法[5-6]，通過有限維基底函數逼近曲線，將無限維問題轉化為有限維問題進行分析。根據基底函數系數的處理方式不同，又可將投影方法分為濾波法和自適應法。濾波法將基底函數對應系數設定為固定參數，分曲線擬合和聚類分析兩步展開[6-7]。自適應法是將基底函數對應的系數作為隨機變量處理，將曲線擬合和聚類分析納入一個目標函數，采用類似最大期望（Expectation-Maximization）算法，同時進行優化[8-9]。此外，還有基于距離的聚類方法，如K-means聚類算法和分層聚類算法。這類算法考慮利用特殊距離或構造“曲線距離”等進行聚類，如果距離可以用離散的樣本點形成的曲線構造，則該類算法與原始聚類算法等價，如果聚類可以用有限基底進行逼近，則該類算法與自適應算法等價。

從聚類結果來看，函數型數據分析方法大致可以分為“硬”聚類和“軟”聚類兩種?！坝病本垲悓⒕垲惤Y果分為是（1）和否（0）;“軟”聚類考慮到了聚類的隸屬度問題，將聚類結果分為[0，1]，和硬聚類相比較，能夠獲得更豐富的聚類信息，但是聚類時間冗長[10]。

自1973年Dunn[11]提出了模糊C均值（Fuzzy C-Means，FCM）聚類算法，在聚類、圖象分割、形狀分析、醫療診斷、特征選擇等領域具有廣泛的應用。將函數型數據應用到FCM聚類算法具有重要的實際意義。近些年關于函數型FCM算法的研究很多，如核函數與FCM結合的聚類算法[12]、自適應FCM聚類算法[13]、以及基于投影的FCM聚類算法[14]等，驗證出函數型FCM算法具有較好的聚類效果。還有學者指出[15]，通過子空間聚類，可以在降低數據維度的同時最大化原始空間的聚類信息。

結合函數型數據和降維思想，本文提出一種改進函數型FCM聚類方法，在FCM聚類算法的基礎上利用B-樣條基底逼近原始離散數據，對FCM聚類算法進行改進，并在此基礎上加入投影算子，以達到降低維度的目的。與函數型K-means聚類算法在模擬和實證上進行對比分析，本文改進方法具有較好的聚類效果。

1?改進函數型FCM聚類算法

該部分從以下三個方面進行闡述：第一，利用B-樣條基底近似原始數據，在一定假設條件下對擬合曲線進行截斷，從而將觀測到的原始離散數據生成為函數型數據。第二，基于上述基于距離的聚類算法，定義曲線之間的“距離”，并通過楚列斯基分解（Cholesky Decomposition）得到適用于本文非正交基函數的曲線距離，將曲線距離轉化為傳統歐氏距離。第三，將構造的距離作為曲線親疏的度量，構建函數型FCM聚類算法目標函數，實現函數型FCM聚類。

1.1?構建B-樣條基底

經過上述轉化，將曲線聚類問題轉化為利用計算特征向量的問題，利用降維及模糊聚類方法完成聚類。

利用計算機對函數型FCM算法進行編程，直到目標函數（11）達到最小。算法流程如下：

Input：xkk=1，2，…，N，u，m max iterate

Initialize：randomly choose initialvii=1，2，…，c

Forj≠i

Repeat

Use （12） fix U to solve V

Use（13）fix V to solve U

Until convergence.

2?模擬分析與實證

為驗證聚類效果，在這一部分對本文算法進行模擬和實證分析。并與函數型K-means聚類算法進行比較。其中模擬部分為帶有標簽的數據，評價指標選擇錯判率和蘭德指數（Rand Index），實例部分為無標簽數據集，評價指標選擇戴維森堡丁指數（Davies-Bouldin Index）。比較結果表明本文算法在聚類精確度方面優于后者聚類算法。

2.1?隨機模擬試驗

利用R軟件rnorm（）函數生成均值和方差分別為（1，1）、（2，2）、（3，3）、（4，4）的4類高斯分布數據，每一類產生600組服從對應均值和方差的隨機數，共計600*4個數據。為避免生成隨機數數值大小相近，數據生成過程中統一為每一類數據乘以倍數3并分別為每一類加上常數5、7、9、11。同時考慮到數據的簡潔性，在編程過程中對數據取整。數據生成后利用構造的B-樣條基底，將離散數據點轉化為曲線，構造的曲線距離及提出的算法進行聚類分析?？紤]到模擬數據來自4類不同參數下生成的數據，為便于比較，在利用本文算法進行聚類時聚為4類且設定數據的區間長度為12。分別利用本文算法和K-means聚類算法進行聚類分析，如圖1所示。

圖1中橫坐標表示設定的聚類區間長度為[0，12]，縱坐標表示模擬數據數值，每一類具有不同的顏色和形狀。圖1（a）、（b）表示兩種聚類算法的類中心曲線，圖1（c）、（d）表示聚類曲線。圖1聚類結果表明：不同類別數據存在一定差異，這種差異來自整體水平即均值以及類別數據波動性即方差。圖1（a）、（b）不同的類中心曲線以及（c）、（d）聚類曲線不同顏色曲線的分布情況來看，本文算法具有較好的類別區分型能。不同顏色的曲線差異較為明顯。進一步，為便于比較聚類效果，在生成數據過程中對每一類數據加入類別標簽。與原始類別進行比較，計算兩種方法的錯判率（錯誤分類個數/總個數*100%）和蘭德指數[20]。

蘭德指數計算公式如下

其中TP表示應該被聚為一類的數據被正確聚為一類，TN表示不應該被聚在一類的數據未被聚為一類，FP表示不應該聚在一類的兩類數據被聚為一類，FN表示應該被聚為一類的數據未被聚為一類。

根據上述描述，得到下表1、2。

表1中，通過兩種聚類方法得到的類別標簽與模擬數據原始類別標簽進行對比，發現本文方法正確分類的個數多于K-means聚類方法。因此相應錯判率低于K-means聚類方法。

表2中，將模擬數據量從600不斷增加到2 400，檢驗兩種聚類算法聚類效果的蘭德指數逐漸提高。通過兩種算法的對比，本文算法的蘭德指數相較于函數型K-means有所提升。

2.2?應用舉例

空氣質量與人們的生活息息相關，近幾年關于空氣質量方面的研究也很多，包括省市縣空氣質量污染聚類問題[21]，也包括珠三角、京津冀地區空氣污染與相關因素的分析[22-23]等。本文數據采用蘭州市NO2濃度（μg·m-3）小時數據，因蘭州地理位置較為特殊，地處黃土高原、青藏高原和蒙古高原三大高原的交匯地帶，兩邊地勢高，中間地勢低，且氣候干燥，植被覆蓋少等原因使得蘭州市空氣質量問題十分嚴重[24]。因此，準確分析蘭州市空氣質量問題具有十分重要的實際意義。

實證數據來自蘭州市鐵路設計院站點采集的NO2小時濃度數據，采集時間為2013年6月1日～10月14日。除刪去66個缺失值外共得到128*24個NO2小時濃度數據。基于B-樣條基底擬合原始離散數據點，構造函數型曲線。利用R軟件進行編程，實現曲線的聚類分析。由于實例數據為無標簽數據。為檢驗兩種聚類算法的聚類效果，本文引入無類別標簽的戴維森堡丁指數[25]（Davies-Bouldin Index）作為評價指標，該指數計算公式如下

其中C-i和C-j表示任意i類和j類的類內平均距離。wi和wj表示i類和j類的類中心。DB越小意味著類內距離越小且類間距離越大?？紤]類別個數為3、4、5、6類的情形下，戴維森保丁指數的變化情況。如下表3所示：

表3中，隨著類別個數的增加，戴維森保丁指數在逐漸下降，說明類別個數的增加會使得類內間距越小且類間間距越大。表明不同類的聚類曲線差異性越大，類別區分度越發明顯。綜合比較兩種聚類算法，本文算法在實例應用中聚類效果相比于K-means聚類算法較好。

進一步，分別畫出本文算法與函數型K-means算法的類中心曲線以及聚類效果曲線。兩種算法均采用相同的B-樣條基底和節點設計。得到兩類聚類結果?？紤]論文篇幅，僅對4類聚類效果進行展示，如圖2所示。

與圖1類似，圖2中橫坐標表示時間，縱坐標表示實例數據數值。每一類具有不同的顏色和形狀，從圖2（a）、（b）類中心聚類結果表明，本文算法中不同類別的類中心曲線未出現類中心曲線交叉的情形。說明本文算法具有較好的類別區分性能。圖2（c）、（d）中顯示一天中在6：00-10：00和17：00-21：00兩個區間段內NO2濃度逐漸上升并達到頂峰，這與實際中早高峰和晚高峰的情況相吻合，且夜間21：00-次日5：00仍存在較高濃度，這種明顯的趨勢為政府污染治理提供一定依據，如錯峰出行等。

3?結論

聚類分析是函數型數據探索分析的重要部分，函數型曲線聚類方法在現今數據密集化程度不斷提高的時代值得探討?；贔CM聚類算法，提出一種函數型FCM聚類算法。在構建B-樣條基底、定義曲線距離之后，對本文算法進行理論推導，并利用R語言對算法進行實現。為驗證本文模型的聚類效果，在模擬和實例部分與函數型K-means聚類算法進行比較，模擬和實例結果表明，本文的曲線聚類算法有助于提高聚類效果。與此同時，實例的應用對蘭州市空氣質量監測的預測以及污染物來源分析也有一定輔助作用。

參考文獻：

[1]Ramsay J O.When the Data are Functions[J].Psychometrika.1982，47（4）：379-396.

[2]Ramsay J O，Silverman B W.Functional Data Analysis[M].2ed.New York：Springer，2005：1-18.

[3]Ferraty F，Vieu P.Nonparametric Functional Data Analysis：Theory and Practice[M].New York：Springer，2006：11-18.

[4]Bouveyron C，Brunet-Saumard C.Model-based Clustering of High-dimensional Data：A Review[J].Computational Statistics & Data Analysis.2014，71（1）：52-78.

[5]Abraham C，Cornillon P A，Matzner-Lber E，et al.Unsupervised Curve Clustering Using B-splines[J].Scandinavian Journal of Statistics.2003，30（3）：581-595.

[6]黃恒君.基于B-樣條基底展開的曲線聚類方法[J].統計與信息論壇.2013，28（9）：3-8.

[7]Kayano M，Dozono K，Konishi S.Functional Cluster Analysis Via Orthonormalized Gaussian Basis Expansions and Its Application[J].Journal of Classification.2010，27（2）：211-230.

[8]Jacques J，Preda C.Funclust：A Curves Clustering Method Using Functional Random Variables Density Approximation[J].Neurocomputing.2013，112（10）：164-171.

[9]Jacques J，Preda C.Model-based Clustering for Multivariate Functional Data[J].Computational Statistics & Data Analysis.2014，71（3）：92-106.

[10]謝維信，劉健莊.硬聚類和模糊聚類的結合——雙層FCM快速算法[J].模糊系統與數學.1992（2）：77-85.

[11]Dunn J C.A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-separated Clusters[J].Journal of Cybernetics.1973，3（3）：32-57.

[12]Sridevi P.Identification of Suitable Membership and Kernel Function for FCM Based FSVM Classifier Model[J].Cluster Computing，2018（6）：1-10.

[13]林甲祥，吳麗萍，巫建偉，等.基于樣本與特征雙加權的自適應FCM聚類算法[J].黑龍江大學自然科學學報.2018，35（2）：244-252.

[14]Kiani M，Andreu-Perez J，Papageorgiou E I.Improved Estimation of Effective Brain Connectivity in Functional Neuroimaging through Higher Order Fuzzy Cognitive Maps[C]//2017 IEEE International Conference on Fuzzy Systems （FUZZ-IEEE）.IEEE，2017：1-6.

[15]Bezdek J C，Ehrlich R，Full W.FCM：The Fuzzy C-means Clustering Algorithm[J].Computers & Geosciences.1984，10（2）：191-203.

[16]Yamamoto M.Clustering of Functional Data in a Low-dimensional Subspace[J].Advances in Data Analysis & Classification.2012，6（3）：219-247.

[17]Rice J A，Silverman B W.Estimating the Mean and Covariance Structure Nonparametrically When the Data are Curves[J].Journal of the Royal Statistical Society.1991，53（1）：233-243.

[18]De Leeuw J，Young F W，Takane Y.Additive Structure in Qualitative Data：An Alternating Least Squares Method with Optimal Scaling Features[J].Psychometrika，1976，41（4）：471-503.

[19]Birman M S，Solomjak M Z.Spectral Theory of Self-adjoint Operators in Hilbert Space[M].New York，NY，USA：D.Reidel Publishing Co.，Inc.，1986：18-59.

[20]Jain A K，Dubes R C.Algorithms for Clustering Data[J].Technometrics.1988，32（2）：227-229.

[21]酈少將.基于函數型聚類的浙江省空氣污染時空特征分析[J].河南教育學院學報（自然科學版）.2018，27（1）：19-24.

[22]周學思，廖志恒，王萌，等.2013—2016年珠海地區臭氧濃度特征及其與氣象因素的關系[J].環境科學學報.2019，39（1）：143-153.

[23]梁銀雙，劉黎明，盧媛.基于函數型數據聚類的京津冀空氣污染特征分析[J].調研世界.2017（5）：43.

[24]祁斌，王式功，劉宇，等.蘭州市空氣污染氣象條件綜合分析[J].陜西氣象.2001（6）：27-30.

[25]Davies D L，Bouldin D W.A Cluster Separation Measure[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1979（2）：224-227.

[責任編輯：鄭筆耕]