PID參數(shù)調(diào)節(jié)的譜多流形聚類算法研究*

羅養(yǎng)霞，馬 迪，常言說

1.西安財經(jīng)大學(xué) 信息學(xué)院，西安 710100

2.密西根大學(xué) 迪爾伯恩分校 計算機與信息科學(xué)系，美國 迪爾伯恩 48124

3.計算機應(yīng)用與商務(wù)智能研究中心，西安 710100

1 引言

隨著人類社會的發(fā)展，從多個數(shù)據(jù)源得到的多種形態(tài)的數(shù)據(jù)成指數(shù)級爆炸性增長，人們逐漸被數(shù)據(jù)所“淹沒”。這些不斷涌現(xiàn)的數(shù)據(jù)表現(xiàn)出數(shù)據(jù)量大、維數(shù)高、結(jié)構(gòu)混雜以及不為人感知等特點。數(shù)據(jù)的膨脹給數(shù)據(jù)分析和處理帶來了前所未有的困難，而大數(shù)據(jù)分析算法和處理能力的滯后，使得復(fù)雜數(shù)據(jù)閱讀和分析，挖掘和揭示隱藏在復(fù)雜表象下的本質(zhì)特征和內(nèi)在規(guī)律成為挑戰(zhàn)。對數(shù)據(jù)的分析能力沒有得到顯著提高，也使得對數(shù)據(jù)的現(xiàn)實應(yīng)用成為一個瓶頸問題。

流形學(xué)習(xí)（manifold learning）可以從流形的角度把握數(shù)據(jù)的內(nèi)部結(jié)構(gòu)，對離散數(shù)據(jù)集合的分析，探求嵌入在高維數(shù)據(jù)空間中低維流形的不同表現(xiàn)形式，尋求事物產(chǎn)生的內(nèi)在規(guī)律性，得到數(shù)據(jù)所蘊含的與人類認知一致的結(jié)構(gòu)信息。近年來，流形數(shù)據(jù)研究與分析越來越受到重視。

首先，Seung和Lee[1]在Science上發(fā)表的研究認為感知通常是以流形方式存在的，開啟了對流形的探究。目前的流形聚類算法大多數(shù)是針對表面無相交的情況設(shè)計[2-3]，還有一些聚類算法是區(qū)別噪聲數(shù)據(jù)在相交的表面具有不同的維度或密度[4-6]。文獻[7]研究解決相交曲線上的數(shù)據(jù)分析。Souvenir等人[8]研究K-means算法，并改進流形曲面數(shù)據(jù)分析[9-11]。Guo等人[12]提出了使用tabu搜索方式，最小化包含在局部方向的(組合)信息。較好的算法是基于局部主成分分析（principal component analysis，PCA）方法，這方面較成熟的研究[13]是基于細化的多尺度譜方法研究。文獻[14]的研究是基于半監(jiān)督學(xué)習(xí)環(huán)境，其促進了文獻[15-16]的工作研究成果。Di Terlizzi等人[17]研究K-manifolds，通過全局度量將局部分解為a個黎曼乘積。文獻[18]基于流行表面光滑的假設(shè)，關(guān)注非參數(shù)設(shè)置，研究引入曲率約束路徑多曲面交疊區(qū)域數(shù)據(jù)分析。文獻[19-20]研究基于嵌入式標簽改進局部線性嵌入，研究將采樣點分片斷的多類流形聚類建模和避免噪聲。而Jeub等人[21]研究引入模塊化思想，來避免參數(shù)增加，通過一致化的聚類過程提高聚類算法的一般性應(yīng)用價值。

2 PID參數(shù)調(diào)節(jié)

對于五類聚類算法，如K-均值聚類、基于模型的方法、基于密度的聚類、高斯混合聚類、層次聚類方法等，這些算法的聚類結(jié)果依賴于初始值、數(shù)據(jù)維數(shù)、聚類數(shù)目、滑動窗口大小、不同密度閾值點、領(lǐng)域半徑或概率分布等。對于參數(shù)的調(diào)節(jié)如果不當，會嚴重影響聚類算法的適用性，甚至使算法失效。特別是對于多個參數(shù)的調(diào)節(jié)，會降低算法的分類效果和收斂性，部分算法在研究時，考慮非參數(shù)設(shè)置進行約束研究[18]，有的對數(shù)據(jù)特征進行假設(shè)[15]，如約束為低平滑多流形。目前在聚類算法參數(shù)方面研究可分為兩類趨勢：一類是研究不用輸入任何參考的無指導(dǎo)聚類算法[22-23]；另一類研究聚類參數(shù)的自動獲取或自適應(yīng)調(diào)節(jié)[24-25]。

閉環(huán)自動控制技術(shù)，調(diào)節(jié)器控制規(guī)律為比例-積分-微分控制（proportional-integral-derivative，PID）方式，調(diào)節(jié)方法被廣泛應(yīng)用于非線性和隨時間變化的系統(tǒng)，用于改進神經(jīng)網(wǎng)絡(luò)、免疫算法、蟻群優(yōu)化等研究[26-28]。參數(shù)調(diào)節(jié)的基本原則是由設(shè)定合適的比例、積分和微分三個因素作用，對控制結(jié)果進行優(yōu)化和調(diào)節(jié)，是一種基于反饋的、根據(jù)偏差變化趨勢而響應(yīng)的調(diào)節(jié)方式，可減少結(jié)果的不確定性，具有調(diào)節(jié)速度快，消除余差等優(yōu)點。PID控制的一般原則如式（1）所示：

根據(jù)系統(tǒng)區(qū)域指標設(shè)定函數(shù)，在系統(tǒng)更新迭代時，根據(jù)輸出效果的精度或適應(yīng)度，對參數(shù)大小或慣性權(quán)值進行適應(yīng)性調(diào)整，以達到全局搜索并達到最優(yōu)解。本文以混合流形算法為基礎(chǔ)，研究參數(shù)調(diào)節(jié)，目的使參數(shù)調(diào)節(jié)隨結(jié)果反饋和優(yōu)化，最大程度地避免設(shè)置參數(shù)的隨機性和盲目性，保證聚類算法局部和全局最優(yōu)。

3 參數(shù)約束的譜多流形聚類算法

參數(shù)約束譜聚類算法的主要思想是：研究基于參數(shù)改變的差異函數(shù)譜聚類，通過構(gòu)造相似性矩陣，多個主成分分析器估計局部切空間，并通過參數(shù)傳遞標簽PT_label()來標記參數(shù)，基于PID調(diào)節(jié)和控制模型逼近過程，當逼近局部切空間時，按當前最優(yōu)參數(shù)傳遞作為初始值，以誤差和誤差變化率為輸出，按三維向量調(diào)節(jié)模型參數(shù)，應(yīng)用ZN法（Ziegler-Nichols）向兩邊擴展搜索空間，直到獲得合理結(jié)果。主要步驟包括：（1）構(gòu)造相似性矩陣；（2）參數(shù)計算與求解；（3）參數(shù)傳遞；（4）PID參數(shù)調(diào)節(jié)。

3.1 構(gòu)造相似性矩陣

相似性矩陣構(gòu)造基于下述事實：

（1）在局部每個數(shù)據(jù)點及其鄰近點屬于一個線性流形，但從全局來看可能是位于或近似屬于光滑的非線性流形。

（2）每個數(shù)據(jù)點的局部切空間提供了非線性流形局部幾何結(jié)構(gòu)的優(yōu)良低維線性近似。

（3）不同流形的相交區(qū)域，同一個流形聚類的數(shù)據(jù)點，有相似的局部切空間；不同流形聚類的數(shù)據(jù)點，其切空間是不同的。因此可以利用數(shù)據(jù)點所內(nèi)含的局部幾何結(jié)構(gòu)信息來輔助構(gòu)造更合適的相似性矩陣（affinity matrix，AM）。

只有當兩個數(shù)據(jù)點滿足相互靠近而且具有相似的局部切空間時，才能夠斷定是來自同一個流形聚類?？膳e證的兩個反例是：（1）數(shù)據(jù)點和垂直的仿射子空間上的數(shù)據(jù)點有相似的局部切空間，但它們相互遠離；（2）曲面和垂直仿射子空間的相交區(qū)域附近的點相互靠近，但它們有不同的局部切空間。

基于以上考慮，在構(gòu)造相似性矩陣時，既要考慮數(shù)據(jù)點局部切空間之間的距離相似性LSij（local similarity，LS），又要考慮數(shù)據(jù)點局部切空間之間的結(jié)構(gòu)相似性SSij?（structural similarity，SS），這兩個相似性融合在一起來決定最后的矩陣相似性：

為了使得構(gòu)造出的相似性矩陣具有前面分析中所期望的性質(zhì)，需要構(gòu)造函數(shù)f，使其關(guān)于局部切空間相似性LSij單調(diào)遞減，同時關(guān)于兩個切空間的結(jié)構(gòu)相似性SSij單調(diào)遞增。為了細化構(gòu)造過程，區(qū)分流形相疊情況，對兩數(shù)據(jù)點xi和xj的K近鄰情況進行區(qū)分。關(guān)于函數(shù)f,LSij和SSij?詳細求解如下所示。

對于數(shù)據(jù)點xi和xj構(gòu)造近鄰圖，Knn（）表示xi或xj的K個近鄰數(shù)據(jù)點，局部相似性LSij定義如下：

兩個數(shù)據(jù)點xi和xj的局部切空間分別為Θi和Θj，則它們之間的結(jié)構(gòu)相似性SSij?定義如下：

對于式（4）中0≤θ1≤…≤θd≤π/2是兩個切空間Θi和Θj之間的主角度，遞歸定義為：

上述方法不同的是，當含有噪聲數(shù)據(jù)或流形相疊時，調(diào)節(jié)參數(shù)被細化，減小收斂和逼近速度，以得到更好的性能。3.2節(jié)將討論如何計算與求解，遞進地逼近局部切空間。

3.2 參數(shù)計算與求解

（1）確定x的邊際分布函數(shù)

其中，uk是數(shù)據(jù)的均值向量，潛在變量y和噪聲εk分別是高斯分布y～N(0,I)和εk～N(0,σ2kI)，在此模型下的聯(lián)合密度函數(shù)為：

其中,X=(x1,x2,…,xk+1)T。

（2）確定對數(shù)似然

在逼近訓(xùn)練時，需要確定πk、uk和Σk模型參數(shù)，為了防止數(shù)據(jù)過小而造成浮點數(shù)下溢情況，利用EM（expectation maximization）算法最大化觀測數(shù)據(jù)的對數(shù)似然來計算。

由于在對數(shù)函數(shù)里面又有加和，無法直接應(yīng)用求導(dǎo)解方程來獲得最大值。因此利用從GMM（Gaussian mixture model）中隨機選點的辦法：分成兩步逼近，實際上類似于K-means的兩步。

（3）迭代計算

估計數(shù)據(jù)由每個數(shù)據(jù)樣本生成的概率來計算，如式（11）所示。

注意對于每個數(shù)據(jù)xi來說是生成的概率，而不是被選中的概率。由于要估計uk和Σk的值，采用迭代法，取上一次迭代的值作為初始值。

（4）參數(shù)值求解

由于每個數(shù)據(jù)樣本符合標準高斯分布，因此按照下式得到參數(shù)值。

通過估計出每個數(shù)據(jù)點的局部切空間后，計算得到相似性矩陣后，重復(fù)迭代前面兩步，直到似然函數(shù)的值收斂為止。

3.3 基于標簽的參數(shù)傳遞

最大對數(shù)似然GMM如何能獲得全局最優(yōu)解，若從局部最優(yōu)達到全局最優(yōu)，將是最好的建模。但實踐中由于GMM和K-means的迭代求解方法都有EM相似，其受初值影響較大，因此也有和K-means同樣的問題，即如何保障全局最優(yōu)。參數(shù)值如果調(diào)整不好，就有可能得到很差的結(jié)果，同時GMM計算工作量要遠大于K-means，增加了算法的復(fù)雜度。

為了對算法有效控制，增強其在含噪聲數(shù)據(jù)時的魯棒性，從局部最優(yōu)收斂達到全局最優(yōu)。同時，為了減少GMM計算工作量，引入數(shù)據(jù)點的label（），用參數(shù)傳遞標簽PT_label(xt)記錄K-means最優(yōu)參數(shù)，然后將其作為初值傳遞給GMM再進行細致迭代。

傳遞時將K-means所得的聚類中心（cluster center）傳遞給GMM函數(shù)，GMM所得的結(jié)果P(xt)不僅是數(shù)據(jù)點參數(shù)標記PT_label(xt)，同時包含了數(shù)據(jù)點標記為每個PT_label的概率。再通過估計出每個數(shù)據(jù)點的局部切空間和計算得到相似性矩陣得到聚類結(jié)果，基本過程見算法1。

算法1基于參數(shù)傳遞的譜多流形聚類（spectral multi-manifold clustering_parameter transfer，SMMC_PT）

輸入：數(shù)據(jù)集X，子空間個數(shù)N，局部化模型數(shù)M,K-鄰近個數(shù)K。

1.將數(shù)據(jù)集X劃分為i類；

2.訓(xùn)練N個i維的局部線性模型來逼近潛在的流形數(shù)據(jù)；

3.初始化i=0，當i≤n時，重復(fù)如下步驟：

①對于每一點xi，若xi∈PT_label(xt),t∈[1,i],選擇k個最鄰近的點組成集合Knn(xi)；

②根據(jù)式（3）計算任意兩點之間的相似度LSij；

③利用式（4）計算兩個局部切空間之間的結(jié)構(gòu)相似性SSij；

④根據(jù)式（16）確定xi的局部切空間Θi；

⑤PT_label(xt)中將調(diào)整后的最優(yōu)值進行傳遞；

⑥由以上數(shù)據(jù)得到調(diào)整之后的相似性矩陣AMij；

⑦更新調(diào)整過程i=i+1，更新PT_label(xi)為PT_label(xt)；

5.從更新的對角矩陣和相似矩陣計算廣義特征矩陣(DM-AM)x=λDMx，并計算前k個特征值對應(yīng)的特征向量x1,x2,…,xk；

6.利用K-means將 {u1,u2,…,uk}∈?N×K的行向量分組為k個聚類。

輸出：數(shù)據(jù)集X對應(yīng)的聚類結(jié)果。

但這僅僅是參考區(qū)間范圍，針對一般的數(shù)據(jù)集而言，需要進一步改進參數(shù)值隨精度、誤差的優(yōu)化調(diào)整。

3.4 基于PID參數(shù)調(diào)節(jié)

由于多流形上存在噪聲時，數(shù)據(jù)點并不是精確地位于某一個具體流形上，會影響聚類劃分和流形學(xué)習(xí)，為了減少算法對噪聲的敏感性，達到更快收斂，減少參數(shù)調(diào)節(jié)的盲目性，應(yīng)用基于反饋的PID參數(shù)調(diào)節(jié)。該方法的調(diào)節(jié)參數(shù)基本思想是，按當前參數(shù)傳遞作為初始值，以誤差和誤差變化率為輸出，按三維向量調(diào)節(jié)模型參數(shù)，應(yīng)用ZN法向兩邊擴展搜索空間，直到獲得合理結(jié)果，變換后的調(diào)節(jié)函數(shù)如下計算。

其中，u(t)=u(t-1)+Δu(t)，而 Δu(t)=K(e(t)-e(t-1))+Me(t)+γ[e(t)-2e(t-1)+e(t-2)]。三個參數(shù)組成自適應(yīng)優(yōu)化函數(shù)X(K,M,γ)，構(gòu)成一個三維行向量，應(yīng)用ZN法獲得參數(shù)，并向兩邊擴展搜索空間。

式中，K?、M?、γ?為整定值，α、β為擴展系數(shù)，控制原則如下：

（1）當誤差較大時，為了使聚類過程有更好的全局跟蹤性能，取較大的K與較小的M，同時為了避免系統(tǒng)響應(yīng)超調(diào)，通常取γ=8。

（2）當誤差和誤差變化率中等大小時，K應(yīng)取得小些，M的取值受系統(tǒng)的影響較大，就取得小一些，γ的取值應(yīng)適當。

（3）當誤差較小時，為了使系統(tǒng)具有較好的穩(wěn)定性，K和M均應(yīng)取得大些，為了防止系統(tǒng)受干擾振蕩，當誤差變化率較大時，M可取得小一些；當誤差變化率較小時，M可取大一些。

具體過程如算法2所示。

算法2基于PID的參數(shù)調(diào)節(jié)方法（spectral multimanifold clustering_proportional-integral-derivative，SMMC_PID）

輸入：原始數(shù)據(jù)集X

3.輸出聚類錯誤、錯誤率和聚類精度；

4.If在PID參數(shù)調(diào)節(jié)控制中出現(xiàn)合理的聚類精度，聚類誤差以及變化率在閾值范圍內(nèi)，輸出參數(shù)和聚類結(jié)果。

5.Else ZN法擴展搜索空間，重新設(shè)定K，進行下一次M的選擇，直到找到合理的結(jié)果，輸出設(shè)定的參數(shù)。

6.End if

7.While沒有找到合理的分類結(jié)果調(diào)節(jié)γ，重復(fù)上面的過程。

輸出:原始數(shù)據(jù)的聚類結(jié)果。

4 分析與實驗比較

4.1 算法復(fù)雜度分析

SMMC_PID算法復(fù)雜度分為計算相似性矩陣AMij，參數(shù)計算和求解，以及參數(shù)調(diào)節(jié)三個主要過程。假設(shè)數(shù)據(jù)維數(shù)為D，近鄰點數(shù)為K，有N個切空間，通過M個局部分析器進行求解。

（1）計算相似性矩陣

對于任意兩個數(shù)據(jù)點的局部切空間分別為Θi和Θj，在遞歸求解局部切空間相似性時，復(fù)雜度為O(N2Dd2)；搜索每個數(shù)據(jù)點的近鄰點的復(fù)雜度為O((D+K)N2)。對AMij利用譜方法將數(shù)據(jù)投影到k維嵌入空間，并在該空間中利用K-means將數(shù)據(jù)分組為k個聚類，其中廣義特征分析的復(fù)雜度為O((N+k)N2),則復(fù)雜度之和為O(N3+(Dd2+D+K+k)N2)。

（2）參數(shù)計算和求解過程

由于計算過程包括確定x的邊際分布函數(shù)，確定對數(shù)似然，迭代計算和參數(shù)傳遞，因此N個局部切空間，應(yīng)用M個分析器進行學(xué)習(xí)時，應(yīng)用PT_label（t）將模型參數(shù)傳遞來優(yōu)化初始化值，這個過程的復(fù)雜度為O(N(n+dm)MD)，其中n和m分別為K-means和EM過程收斂所需的迭代步數(shù)，這里由于PT_label參數(shù)傳遞使t?n。而K-means在k維投影數(shù)據(jù)上的復(fù)雜度為O(Nk2q)（q為該過程中K-means收斂所需的迭代步數(shù)），則此過程的復(fù)雜度合計為O(N((n+dm)MD+k2q))。

（3）PID參數(shù)調(diào)節(jié)復(fù)雜度

在多次蒙特卡洛重復(fù)過程和標記，涉及對K、M的調(diào)節(jié)，這個過程的復(fù)雜度為O(N2+N(M+K)+t)，其中t為迭代次數(shù)。

因此，算法SMMC_PID的復(fù)雜度為三者之和，又由于K-means和EM過程收斂所需的迭代步數(shù)通常較低，并且d＜D，K?N，k?N，因此這三者之和可以化簡為O(N3+N2D+ND)，因此SMMC_PID復(fù)雜度主要由數(shù)據(jù)點數(shù)N和數(shù)據(jù)維數(shù)D來決定。

4.2 實驗結(jié)果對比

根據(jù)上面敘述的規(guī)則和算法過程，對不同數(shù)據(jù)類型進行實驗和對比，如圖1所示。顯示了應(yīng)用PID參數(shù)調(diào)節(jié)前（左圖）、后（右圖）譜多流形聚類分類結(jié)果性能，從多個實驗結(jié)果可以看出，基于PID反饋式聚類參數(shù)約束機制能顯著提高聚類性能。

4.3 聚類精確性及復(fù)雜度對比

從精確性和復(fù)雜度方面對算法進行比較，這里聚類精確性（clustering accuracy）指所有可能分類中的最大分類精度，度量標準依據(jù)以下公式：

Fig.1 Comparison of optimal clustering performance of different datasets圖1 不同數(shù)據(jù)集最優(yōu)聚類性能對比

其中，ti指正確標簽，ci是xi的聚類標簽，δ為脈沖函數(shù)。在考慮錯誤時包括N個局部線性分析器逼近潛在流形的重構(gòu)誤差。復(fù)雜度（complexity）按平均運行時間（以秒計）來進行算法的復(fù)雜度估計。

對比算法的選擇取決于算法特點、代碼的可用性，以及與此算法的相關(guān)性。由于算法GPCA（generalized principal component analysis）、K-planes、LSA（latent semantic analysis）、SCC（spectral curvature clustering）是幾種典型的適用于簡單、線性流形聚類方法，與本文提出的算法相關(guān)性差異較大。本文選擇對比算法時，選擇以下幾種非線性流形聚類算法進行比較：K-means[9]、SC算法[2]、K-manifolds算法[17]、SMMC[15]。分別在圖1（a）～（e）合成數(shù)據(jù)上進行實驗，計算均值和標準差、最高精度，以及運行的平均時間，結(jié)果如表1所示。

實驗中發(fā)現(xiàn)，SMMC_PID算法與同類算法相比，在聚類精度上從可視化圖形和數(shù)值都具有明顯優(yōu)勢。結(jié)果反饋和參數(shù)傳遞約束聚類算法，減少參數(shù)設(shè)置的盲目性，縮短了系統(tǒng)迭代過程，但在運行平均時間消耗方面，優(yōu)勢不突出，分析是由于增加了參數(shù)傳遞和部分計算時間的原因。

4.4 真實數(shù)據(jù)中的實驗分析

為了驗證算法在真實數(shù)據(jù)中的可用性，選擇四類數(shù)據(jù)集分別為：（a）Caltech101數(shù)據(jù)集的一個子集；（b）Yale Face數(shù)據(jù)集 B 的一個子集；（c）2-維圖像COIL-20數(shù)據(jù)集；（d）3-維運動分割數(shù)據(jù)庫Hopking155數(shù)據(jù)集（http://www.vision.caltech.edu/Image_datasets/Caltech101,http://vision.ucsd.edu/～leekc/ExtYale-Database/ExtYaleB.html,http://www.cs.columbia.edu/labs/cave/software/softlib/coil-20,http://www.vision.jhu.edu/data/hopkins155)。

在以上數(shù)據(jù)集進行重復(fù)實驗，獲得平均聚類精度、平均時間如圖2、圖3所示。

在此實驗統(tǒng)計中可以看出，SMMC_PID分類的平均聚類性能優(yōu)于其他同類算法。聚類的復(fù)雜度，除K-manifolds算法總體較高，其他SC、SMMC和SMMC_PID總體接近且偏低。分析認為SMMC_PID算法在參數(shù)控制方面增加了計算量和迭代時間，但由于增加了總體聚類收斂速度，減少系統(tǒng)計算復(fù)雜度。

Table 1 Clustering performance comparison of different algorithms on different datasets(mean±std.,highest accuracy,computation time)表1 不同聚類算法在不同數(shù)據(jù)集聚類性能比較（精度均值±標準差，最佳性能，運行時間）

Fig.2 Comparison of average accuracy of different algorithms圖2 不同算法的平均聚類精度實驗對比

Fig.3 Comparison of average time of different algorithms圖3 不同算法的平均時間實驗對比

5 總結(jié)

參數(shù)調(diào)節(jié)在聚類中是一個難點問題，直接影響著聚類性能。本文研究混合流形聚類參數(shù)調(diào)節(jié)問題，通過構(gòu)造相似性矩陣，多個主成分分析器估計局部切空間，并通過參數(shù)傳遞和PID調(diào)節(jié)，控制模型逼近過程，按三維向量調(diào)節(jié)模型參數(shù)，應(yīng)用ZN法擴展搜索空間，使聚類過程與結(jié)果進行反饋，改進聚類算法的精確性和復(fù)雜度。經(jīng)在合成數(shù)據(jù)和真實數(shù)據(jù)不同類型數(shù)據(jù)特征集進行檢測，可獲得較好的聚類性能。

下一步將整合項目研究工作，結(jié)合動態(tài)嵌入標簽方式[20]，使譜聚類能有效應(yīng)用于較復(fù)雜的實踐環(huán)境分析。