一種函數(shù)型模糊聚類算法及其應(yīng)用

楊夢玲

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

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

中圖分類號：TP311.1?文獻(xiàn)標(biāo)志碼：A?文章編號：1008-4657（2019）05-0018-08

0?引言

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

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

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

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

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

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

1?改進(jìn)函數(shù)型FCM聚類算法

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

1.1?構(gòu)建B-樣條基底

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

利用計算機(jī)對函數(shù)型FCM算法進(jìn)行編程，直到目標(biāo)函數(shù)（11）達(dá)到最小。算法流程如下：

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?模擬分析與實證

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

2.1?隨機(jī)模擬試驗

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

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

蘭德指數(shù)計算公式如下

其中TP表示應(yīng)該被聚為一類的數(shù)據(jù)被正確聚為一類，TN表示不應(yīng)該被聚在一類的數(shù)據(jù)未被聚為一類，F(xiàn)P表示不應(yīng)該聚在一類的兩類數(shù)據(jù)被聚為一類，F(xiàn)N表示應(yīng)該被聚為一類的數(shù)據(jù)未被聚為一類。

根據(jù)上述描述，得到下表1、2。

表1中，通過兩種聚類方法得到的類別標(biāo)簽與模擬數(shù)據(jù)原始類別標(biāo)簽進(jìn)行對比，發(fā)現(xiàn)本文方法正確分類的個數(shù)多于K-means聚類方法。因此相應(yīng)錯判率低于K-means聚類方法。

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

2.2?應(yīng)用舉例

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

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

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

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

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

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

3?結(jié)論

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

參考文獻(xiàn)：

[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].統(tǒng)計與信息論壇.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]謝維信，劉健莊.硬聚類和模糊聚類的結(jié)合——雙層FCM快速算法[J].模糊系統(tǒng)與數(shù)學(xué).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]林甲祥，吳麗萍，巫建偉，等.基于樣本與特征雙加權(quán)的自適應(yīng)FCM聚類算法[J].黑龍江大學(xué)自然科學(xué)學(xué)報.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，F(xiàn)ull 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]酈少將.基于函數(shù)型聚類的浙江省空氣污染時空特征分析[J].河南教育學(xué)院學(xué)報（自然科學(xué)版）.2018，27（1）：19-24.

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

[23]梁銀雙，劉黎明，盧媛.基于函數(shù)型數(shù)據(jù)聚類的京津冀空氣污染特征分析[J].調(diào)研世界.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.

[責(zé)任編輯：鄭筆耕]