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

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

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（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）確定對(duì)數(shù)似然

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

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

（3）迭代計(jì)算

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其中，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)]。三個(gè)參數(shù)組成自適應(yīng)優(yōu)化函數(shù)X(K,M,γ)，構(gòu)成一個(gè)三維行向量，應(yīng)用ZN法獲得參數(shù)，并向兩邊擴(kuò)展搜索空間。

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

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

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

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

具體過(guò)程如算法2所示。

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

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

3.輸出聚類(lèi)錯(cuò)誤、錯(cuò)誤率和聚類(lèi)精度；

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

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

6.End if

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

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

4 分析與實(shí)驗(yàn)比較

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

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

（1）計(jì)算相似性矩陣

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

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

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

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

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

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

4.2 實(shí)驗(yàn)結(jié)果對(duì)比

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

4.3 聚類(lèi)精確性及復(fù)雜度對(duì)比

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

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

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

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

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

4.4 真實(shí)數(shù)據(jù)中的實(shí)驗(yàn)分析

為了驗(yàn)證算法在真實(shí)數(shù)據(jù)中的可用性，選擇四類(lèi)數(shù)據(jù)集分別為：（a）Caltech101數(shù)據(jù)集的一個(gè)子集；（b）Yale Face數(shù)據(jù)集 B 的一個(gè)子集；（c）2-維圖像COIL-20數(shù)據(jù)集；（d）3-維運(yùn)動(dòng)分割數(shù)據(jù)庫(kù)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ù)集進(jìn)行重復(fù)實(shí)驗(yàn)，獲得平均聚類(lèi)精度、平均時(shí)間如圖2、圖3所示。

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

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

Fig.2 Comparison of average accuracy of different algorithms圖2 不同算法的平均聚類(lèi)精度實(shí)驗(yàn)對(duì)比

Fig.3 Comparison of average time of different algorithms圖3 不同算法的平均時(shí)間實(shí)驗(yàn)對(duì)比

5 總結(jié)

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

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