姚曉紅，黃恒君

蘭州財經大學 統(tǒng)計學院，蘭州 730020

聚類分析是一種數據劃分的方法，其劃分依據是使得同一簇內的數據具有較高的相似性，或不同簇的數據具有較低的相似性。作為一種經典的多元統(tǒng)計方法，幾十年來，人們對聚類分析的研究持續(xù)關注；作為機器學習和人工智能的無監(jiān)督學習技術，聚類分析在圖像識別、商業(yè)智能和文本分析等方面得到了廣泛的應用。

隨著信息技術的發(fā)展和數據采集、存儲能力的提高，許多學科領域均出現了一些具備連續(xù)特征的數據。例如，股票量價數據、語音數據、可穿戴智能設備監(jiān)測數據、環(huán)境污染監(jiān)測數據等，按照時間密集采集，本質上構成了這種數據類型。若采用泛函分析工具，將數據“連接”成曲線，并將曲線作為一個整體來進行分析，當前文獻中稱為函數型數據分析（functional data analysis，FDA）[1]。具體到聚類任務，則稱為函數型聚類分析，是探索函數型數據的重要工具，近年來引起了學者們廣泛的研究興趣。

目前，函數型數據聚類方法主要分為兩類：一類是原始數據法，該方法從離散數據出發(fā)，未考慮到數據的函數特性（如連續(xù)），本質屬于高維離散數據分析方法[2-3]，本文不展開討論；另一類是投影法，該方法以無限維函數為基礎，以數據擬合為手段，通過尋找包含適當類別信息的子空間并開展聚類研究。投影法的具體算法有很多，既有從統(tǒng)計學視角開展的研究，如稀疏樣品曲線聚類方法[4]、非參數擬合基礎上的K-means 聚類算法[5-6]、基于高斯混合模型的聚類算法[7-8]等；也有從機器學習視角進行的研究，如結合自組織神經網絡的函數型聚類算法[9]、基于懲罰函數的聚類一步法[10]、函數型子空間投影分割聚類算法[11]、基于模態(tài)分解的聚類算法[12]，以及局部稀疏函數型聚類方法[13]等。

事實上，上述提及的函數型數據及聚類方法仍存在一些有待進一步討論的問題：

第一，現實當中，觀測到的多數函數型數據具有取值非負的要求。例如，前面列舉的各種函數型數據實例（股票量價數據等）就是這樣一種情形?，F有的函數型聚類方法由于未能考慮到函數型數據的這種特性，不能確保投影結果的非負性，從而可能影響聚類效果。最近，有研究將非負矩陣分解（non-negative matrix factorization，NMF）技術作為降維手段，引入到函數型數據分析中來[14]，為處理非負函數型數據提供了思路。

第二，倘若采用機器學習的術語，函數型聚類屬于無監(jiān)督學習任務，其優(yōu)勢在于無需分類標簽信息即可開展數據探索研究，避免了人工密集和成本高昂的標簽數據采集過程[15]。然而，正是由于忽略了標簽信息，前述許多函數型聚類方法文獻所報告的聚類結果精度有待進一步提高。事實上，獲取少量的標簽數據通常是可行的，當大量無標簽數據與少量帶標簽數據一起學習時，能夠很大程度地提高聚類精度。這種做法在機器學習領域稱為半監(jiān)督學習，針對非函數型數據已開展了相應的研究。與本文相關的研究有：文獻[16]將概念分解應用到半監(jiān)督學習中；文獻[17]提出了帶有局部坐標約束的半監(jiān)督概念分解算法；文獻[18]通過約束非負矩陣分解（constrained non-negative matrix factorization，CNMF）方法將無監(jiān)督學習拓展為半監(jiān)督學習；文獻[19-20]將CNMF 引入聚類分析中，用以提高聚類性能。

為此，針對以上函數型數據特征及聚類方法特點，本文試圖將CNMF 引入到函數型聚類分析中，討論非負約束情況下的半監(jiān)督函數型聚類方法（semisupervised non-negative functional clustering，SSNFC），旨在充分利用額外信息來提高聚類精度。

1 模型構建

本章討論非負半監(jiān)督函數型聚類模型的構建。通常，函數形式的數據不能直接觀測，至多能獲取具備曲線特征的離散采樣點。因此，函數型數據的聚類投影法通常包含曲線擬合和聚類兩個要素。本章將這兩個要素合并，融入約束非負矩陣分解技術，構建了一個將曲線擬合和函數型聚類過程相統(tǒng)一的非負約束半監(jiān)督函數型聚類模型。

1.1 曲線擬合

假定N維函數向量X(t)=[x1(t),x2(t),…,xN(t)]′為定義在連續(xù)集T 上的獨立同分布函數型數據樣本，xi(t)(i=1,2,…,N)是T 上的實值曲線。記yij為曲線xi(t)上帶有噪音的第j(j=1,2,…,mi)個離散觀測值，則yij可以由以下模型生成：

其中，tij表示yij的觀測點，εij表示觀測隨機誤差。

在實際中，式（1）中的曲線xi(t)通常假定由某個既定空間的一組基底函數線性表示：

其中，φi(t)=[φi1(t),φi2(t),…,φid(t)]′為給定的基底函數，αi=[ai1,ai2,…,aid]′為相應的系數向量。若每條曲線采用相同的基底函數擬合，且對應的離散采樣點位置相同，即mi=m(i=1,2,…,N)，則結合式（2）的基底表示，式（1）可以表示為矩陣形式：

其中，Y=(yij)m×N為離散點構成的數據矩陣，E=(εij)m×N為隨機誤差矩陣，為基矩陣，A=[α1,α2,…,αN]d×N是待估參數構成的系數矩陣。

對于式（3），最小化目標函數

可求得系數矩陣A。其中，||·||F為矩陣的Frobenius范數，Pen為懲罰項，λ為懲罰參數。具體估計方法有回歸樣條（λ=0）、樣條平滑（λ≠0）等[21]。

1.2 聚類過程

根據前面曲線擬合的假定，各條曲線之間的差異信息完全取決于矩陣A。因此，許多函數型聚類方法[6,13,22-23]分為兩個步驟，即在曲線擬合的基礎上，采用常規(guī)的聚類算法（如K-means）對系數矩陣A進行聚類。

鑒于本文處理非負函數型數據的目的，受文獻[14]啟示，本文首先討論基于非負矩陣分解（NMF）的聚類過程。NMF 是一種數據降維技術，即將非負矩陣近似分解為兩個低秩非負矩陣的乘積[24]：

其中，非負矩陣是指元素均大于0 的矩陣；Ud×K≥0為基矩陣；VN×K≥0 為系數矩陣。式（5）可以通過優(yōu)化問題[25]進行求解。

除了降維功能外，NMF 的另一個重要性質是具有聚類特性，分解得到的低秩矩陣V能夠近似體現聚類標簽信息[26]。因此針對系數矩陣A的聚類，可以轉化為對矩陣V進行一次常規(guī)的聚類（如K-means）[27]，即可得到原始曲線xi(t)(i=1,2,…,N)的聚類結果。將曲線擬合（式（4））與降維、聚類過程（式（5））統(tǒng)一在一個目標函數中，得到如下優(yōu)化問題：

事實上，NMF 技術已經為處理具有非負特性的函數型數據提供了工具，然而在式（6）中，并未考慮到數據的標簽信息，本質上屬于無監(jiān)督學習。而實際上，在數據采集過程中，獲取少量數據的標簽信息是可行的，當大量無標簽數據與少量帶標簽數據一起學習時，能夠很大程度地提高聚類精度。

1.3 非負約束半監(jiān)督函數型聚類模型

為充分利用數據的標簽信息，本文引入CNMF[18]技術，將數據的標簽信息融入函數型聚類過程中，從而將無監(jiān)督學習擴展為半監(jiān)督學習。為此，首先構造數據的標簽矩陣：

其中，N為樣本量；l為帶標簽信息的樣本點個數；Cl×c是指標矩陣，當樣本點xi（i=1,2,…,l）屬于類Cj（j=1,2,…,c，c≤K）時，cij=1，否則cij=0；O是零矩陣；IN-l是N-l階單位矩陣。例如，當l=5 時，表示樣本中帶有標簽信息的樣本點有5 個，分別記為x1、x2、x3、x4、x5，剩余N-5 個樣本點沒有標簽信息。若x1屬于第一類，x2、x3屬于第二類，x4、x5屬于第三類，則相應的標簽矩陣為：

為了將數據的標簽信息融入聚類分析中，引入輔助矩陣Z，使：

顯然，由非負約束條件V≥0 可知，輔助矩陣Z也是非負的，即Z≥0。

將式（7）代入式（5），可得：

即實現了CNMF。式（8）給出了函數型數據的低維表示，具體地，乘積矩陣LZ的行向量對應于樣本點的低維表示。同時，CNMF 能夠保證具有相同標簽的樣本點在低維空間中也屬于同一類。顯然，式（8）將標準的NMF 擴展為半監(jiān)督學習。相應地，式（6）的優(yōu)化問題可進一步表述為：

最后，鑒于稀疏性表示有助于提高聚類性能[28]，而l2,1范數正則化是實現稀疏特征選擇的有效方法之一。因此，取式（9）中的懲罰項Pen=||LZ||2,1，由于標簽矩陣L是常量矩陣，懲罰項可進一步簡化為||Z||2,1。

綜上所述，將曲線擬合和聚類過程統(tǒng)一在一個目標函數中，即得到本文提出的非負約束半監(jiān)督函數型聚類模型（SSNFC）：

2 求解算法

本章首先給出模型的求解過程及算法，接著證明算法的收斂性，并進行時間復雜度分析。

2.1 求解過程

由于目標函數（式（10））對于參數U、Z來講并非是一個聯合凸優(yōu)化問題，很難求到全局最優(yōu)解。但對于U（Z固定）或Z（U固定）來講，均是凸優(yōu)化問題。因此，本文依據非負矩陣分解的乘性迭代更新算法[25]，提出了模型的參數求解算法。具體地，固定其中一個變量Z（U），通過式（10）求解另一個變量U（Z）。

令Θ、Γ分別為非負約束條件U≥0 和Z≥0 的拉格朗日乘子，則相應的拉格朗日函數為：

得到U、Z更新規(guī)則分別為：

根據式（11）和式（12）可交替迭代更新參數U、Z，實現優(yōu)化問題（目標函數式（10））的求解，即實現非負半監(jiān)督函數型聚類算法（SSNFC）。

算法1非負半監(jiān)督函數型聚類算法（SSNFC）

輸入：數據矩陣Y、基矩陣Φ、懲罰參數λ和類別數K。

1.構造數據的標簽矩陣L

2.初始化U0、Z0

3.fort=1,2,…,最大更新迭代次數

4.固定Zt-1，根據式（11）更新Ut-1

5.固定Ut，根據式（12）更新Zt-1

6.if 式（10）收斂

7. break

8.end if

9.end for

輸出：U、Z和簇劃分C={c1,c2,…,cK}。

在該算法中，需要說明：

（1）對于矩陣U、Z的初始化，可采用0～1 之間的均勻隨機數填充。

（2）對于迭代的終止條件，包括兩方面：一是式（10）收斂，即同時滿足條件||Ut-Ut-1||∞≤ε0，||Zt-Zt-1||∞≤ε0和，其中ε0和ε1為很小的正數；二是達到預先設定的最大迭代次數。

2.2 算法收斂性

顯然，目標函數（式（10））的下界大于等于0，因此，只需證明目標函數（式（10））在更新規(guī)則（式（11）和式（12））下是非增的，即：

定理目標函數OF在更新規(guī)則（式（11）和式（12））下是非增的，當且僅當U、Z是穩(wěn)定點時目標函數值在更新規(guī)則下保持不變。

定理保證了算法的收斂性，從而得到局部最優(yōu)解。為了證明定理，首先介紹輔助函數的定義和引理[25]，然后構造輔助函數，并證明定理，即證明算法的收斂性。

定義若G(x,xt)滿足條件

G(x,xt)≥F(x)，G(x,x)=F(x)

則稱G(x,xt)是F(x)的輔助函數。

引理若G(x,xt)是F(x)的輔助函數，則F(x)在更新規(guī)則

下是非增的。

證明由輔助函數的定義知，需要證明F(xt+1)≤G(xt+1,xt)≤G(xt,xt)≤F(xt)。顯然，當xt是G(x,xt)的局部極小值時，有F(xt+1)=F(xt)。若F(x)可導，且在xt的小鄰域內連續(xù)，即?F(xt)=0，則通過式（13）的迭代更新，可得到收斂于F(x)局部極小值xmin=arg minxF(x)的序列：

即引理得證。

由引理可知，通過尋找恰當的輔助函數，能夠證明目標函數（式（10））在更新規(guī)則（式（11）和式（12））下是非增的。因此，下面首先構造輔助函數，然后證明定理。

命題1令F′是函數F的一階導函數，則

是函數Fuij(u)的輔助函數，其中Fuij(u)是目標函數OF中關于uij的部分。

式（14）和式（15）分別是構造的輔助函數，由此可進一步證明定理，證明過程如下：

2.3 時間復雜度分析

本文進一步討論SSNFC 的計算復雜度。按照本文使用的符號，N是總樣本量，m是特征數量，d是基底個數，l是帶標簽數據的樣本點個數，c是帶標簽數據的類別數，K是聚類數。注意，SSNFC 實際包括兩個過程：一是投影，即曲線擬合Y=ΦA，因迭代更新前只計算一次，所以其計算復雜度可忽略不計；二是CNMF。

顯然，在該算法中，標簽矩陣L是一個常量矩陣，每一行只有一個元素為1，其余元素均為0，因此矩陣乘積LZ的計算復雜度為O((c+N-l)K)，且每次迭代過程中只計算一次。計算復雜度主要在于U和Z的更新迭代過程中，具體如下：

在U的更新過程中，每次更新進行了(c+N-l)K+dmN+3dNK+d2K+d2m次加法運算，(c+N-l)K+dmN+3dNK+d2K+d2m+dK次乘積運算，dK次除法運算，共進行了2(c+N-l)K+2dmN+6dNK+2d2K+2d2m+2dK次運算。

在Z的更新過程中，每次更新進行了(c+Nl)Nm+3(c+N-l)md+(c+N-l)K+3(c+N-l)dK+NK次加法運算，NK+(c+N-l)Nm+3(c+N-l)md+3(c+Nl)K+3(c+N-l)dK次乘積運算，2(c+N-l)K次除法運算，共進行了2(c+N-l)Nm+2NK+6(c+N-l)md+6(c+N-l)K+6(c+N-l)dK次運算。

綜上所述，若不計投影過程，每次迭代過程的計算復雜度為O(mNK)，記t為迭代次數，則進行t次迭代更新的計算復雜度為O(tmNK)。

3 模擬及實例驗證

為了說明本文提出的SSNFC 方法的有效性，下面采用隨機模擬數據和實例數據，將SSNFC 與無監(jiān)督函數型聚類方法（TA 方法[22]、FCOF 方法[10]和FNMF（functional nonnegative matrix factorization）方 法[14]）進行比較，以聚類純度（Purity）、聚類精度（Accuracy）和蘭德指數（Rand index，RI）為聚類效果的評價準則。其中，TA 是函數型聚類兩步法，FCOF 是函數型聚類一步法，FNMF 是基于非負矩陣分解的函數型聚類方法。數據模擬及算法比較通過R語言實現。實驗的計算機環(huán)境為：Intel?CoreTMi7-8700K CPU 3.7 GHz，內存16 GB，Windows10 64 位操作系統(tǒng)。

3.1 數據

3.1.1 模擬數據

參照文獻[7]，本文采用三角函數和多項式函數的線性組合隨機模擬生成一個數據集。具體生成公式如下：

其中，U是服從正態(tài)分布N(1,1) 的隨機變量；ε(t)～N(0,1)是白噪聲；k分別取1、3 和5，表示生成3 類數據；t∈[1,21]，共取1 001個等距的離散點，即t=1,1.02,1.04,…,21。每類隨機生成50 條曲線，如圖1 所示。

Fig.1 Simulation data圖1 隨機模擬數據

3.1.2 Growth 數據

Growth 數據集（來自R 擴展包fda）包含54 名女孩和39 名男孩1～18 歲之間31 個階段的身高數據。樣本及類別標簽如圖2 所示，其中橫坐標表示年齡，縱坐標表示身高，不同顏色和線型代表不同性別。

3.1.3 TIMIT 語音數據

選取TIMIT（Texas Instruments and Massachusetts Institute of Technology）語音數據庫（http://web.mir.edu/course/6/6.863/share/nltk_lite/）中名為“SA1”的語音數據。該庫是由麻省理工學院、斯坦福研究所和德州儀器共同設計完成的，收集了美國不同方言讀出給定句子時的語音數據，被廣泛應用于語音識別研究領域。本文選用其中經過數字信號處理后的音素數據和對應的音素類別標簽。具體地，“SA1”語音中包含“sh”“dcl”“iy”“aa”和“ao”五個音素，其中“sh”表示“she”，“dcl”表示“dark”，“iy”表示“she”中的元音，“aa”表示“dark”中的元音，“ao”表示“water”中的第一個元音。原始數據的一個樣本示例及類別標簽如圖3所示，其中橫坐標表示頻率，縱坐標表示經對數周期圖法處理的音頻數據值，不同線型代表音素類別。

Fig.2 Growth data圖2 Growth 數據

Fig.3 TIMIT speech data圖3 TIMIT 語音數據

3.2 評價準則

本文采用聚類純度（Purity）、聚類精度（Accuracy）和蘭德指數（RI）來評價聚類效果，定義如下：

其中，N為樣本量，K為類別數；Purity(Ω,C)表示聚類純度，Ω={w1,w2,…,wK} 表示真實類別，wj(j=1,2,…,K)為第j類，C={c1,c2,…,cK}表示實際聚類結果，ck(k=1,2,…,K)為第k個聚類簇；Accuracy表示聚類精度；Ncor為正確聚類的樣本點個數；RI表示蘭德指數；a表示在真實類別與實際聚類結果中都屬于同一類的元素對數；b表示在真實類別與實際聚類結果中都不屬于同一類的元素對數；為數據集中兩兩可以組成的對數。上述三種聚類評價指標取值均介于0 到1 之間，值越大，則聚類效果越好。

3.3 參數設置

在進行聚類時，SSNFC算法參數設定如下：（1）采用三次等距節(jié)點B-樣條基底擬合曲線，通過基底數量控制曲線平滑程度，3 組數據的基底數量分別設置為20、20、23；（2）隨機模擬數據包含3 類數據，取聚類數K=3，Growth 數據中性別包含男、女，取聚類數K=2，TIMIT 語音數據中包含5 種不同的音素，取聚類數K=5；（3）數據的標簽矩陣L依據樣本所含標簽信息的多少確定；（4）懲罰參數λ依據聚類效果確定，聚類評價指標值越大，說明聚類效果越好。

在參數設定基本一致的基礎上，利用隨機模擬數據、Growth 數據和TIMIT 語音數據，將SSNFC 方法和TA 方法、FCOF 方法和FNMF 方法的聚類性能進行比較。

3.4 評價結果

為了消除初始化對聚類結果的影響，每個實驗重復進行100 次，用評價指標的均值來衡量聚類性能。

首先，分別取λ={0.01,0.10,1.00,10.00,100.00}，在隨機模擬數據、Growth 數據（隨機抽樣，樣本量為90，其中女孩51 人，男孩39 人）和TIMIT 語音數據中均加入10%的標簽信息進行聚類，采用聚類純度（黑色實線）、聚類精度（紅色虛線）和蘭德指數（藍色虛線）來評價聚類效果，結果如圖4 所示。

由圖4可以看出，針對隨機模擬數據（上）、Growth數據（中）和TIMIT 語音數據（下），超參數λ的取值對聚類效果的影響有所差異，但整體來看，超參數λ取值較小時，不利于提高聚類性能，尤其在隨機模擬數據和Growth 數據上表現得比較明顯。超參數λ的取值大小體現了稀疏性懲罰項的正則化程度，取值越大，說明稀疏性正則化更有助于提高聚類性能。

然后，分別取λ={0.01,0.10,1.00,10.00,100.00}，在隨機模擬數據、Growth 數據和TIMIT 語音數據中依次加入10%、20%、30%、40%、50%的標簽信息進行聚類，結果如圖5 所示。

Fig.4 Variation tendency of clustering effect with hyper-parameter λ圖4 聚類效果隨超參數λ 的變化趨勢

圖5 中，Proportion 表示數據中所含標簽信息的比例，分別取10%、20%、30%、40%和50%?？梢钥闯?，無論是隨機模擬數據（上）、Growth 數據（中），還是TIMIT 語音數據（下），SSNFC 方法的聚類效果與超參數λ的取值和樣本所含標簽信息的多少均有關。不管超參數λ取何值，樣本所含標簽信息越多，聚類效果則越好。而對于超參數λ，與前面的分析有一致的結論。

最后，將半監(jiān)督函數型聚類方法SSNFC 與無監(jiān)督函數型聚類方法（TA 方法、FCOF 方法和FNMF 方法）的聚類效果進行比較，其中SSNFC 方法聚類時，數據中加入了20%的標簽信息。

隨機模擬數據的聚類評價結果如表1 所示。Growth 數據的聚類評價結果如表2 所示。TIMIT 語音數據的聚類評價結果如表3 所示。

Fig.5 Variation tendency of clustering effect with hyper-parameter λ and label information圖5 聚類效果隨超參數λ 和標簽信息的變化趨勢

Table 1 Clustering evaluation results of simulation data表1 隨機模擬數據聚類評價結果

Table 2 Clustering evaluation results of Growth data表2 Growth 數據聚類評價結果

顯然，對于隨機模擬數據、Growth 數據和TIMIT語音數據，不管是聚類純度、聚類精度，還是蘭德指數，半監(jiān)督函數型聚類方法SSNFC 均優(yōu)于其他無監(jiān)督函數型聚類方法，尤其是SSNFC 在Growth 數據上的表現，明顯優(yōu)于其他方法。

4 結束語

本文在半監(jiān)督學習框架下，討論了非負函數型數據的聚類問題。在考慮函數型數據擬合和聚類的同時，也考慮了數據的標簽信息。具體地，通過引入CNMF，將數據的標簽信息融入到函數型聚類過程中，然后將數據擬合、非負約束及聚類過程納入同一個目標函數，構建了一個新的非負約束半監(jiān)督函數型聚類模型，并給出模型的求解算法，同時也討論了算法的收斂性和計算復雜度。模擬和實例驗證結果顯示，該方法有助于提高聚類性能。

然而，在實際中，函數型數據通常會以多元的形式出現，例如個人穿戴式智能設備至少監(jiān)測心率、血壓和運動軌跡，氣象數據一般包括溫度、濕度和風力等指標，空氣質量監(jiān)測數據涉及到二氧化氮、二氧化硫、一氧化碳、臭氧和細微顆粒物等指標。若仍采用一元函數型數據的處理方式選取單項指標進行數據分析，顯然不能達到認識事物全貌的目的。因此，在半監(jiān)督學習框架下，進一步討論針對多元函數型數據的聚類方法，具有十分重要的理論價值和實際意義。另外，對于多元函數型聚類方法，由于各變量對聚類結果的貢獻不盡相同，如何確定權重系數也是進一步關注的問題。