王培培 張紅云

(1.同濟大學計算機科學與技術系,上海,201804；2.同濟大學嵌入式系統(tǒng)與服務計算教育部重點實驗室,上海,201804)

引 言

主曲線是第一主成分的非線性推廣[1]，第一主成分是對數(shù)據(jù)集的一維線性最優(yōu)描述。主曲線通過將高維數(shù)據(jù)映射到嵌入在高維空間中的低維流形，以一種新的方式表示數(shù)據(jù)，使數(shù)據(jù)分析任務更容易、更準確。由主曲線定義可知：與傳統(tǒng)方法相比，用主曲線來分析高維的、高度非線性化、非結構化和高度相關性等特點的數(shù)據(jù)能取得較好的效果。自20世紀年代以來在國外取得了較快的發(fā)展。在數(shù)據(jù)主曲線提取方面，Trevor Hastie于1989年首次提出了HS主曲線算法[2]，除了可以較好地描述非線性數(shù)據(jù)外，該主曲線另具有自相合以及無參數(shù)性等優(yōu)點，但其仍存在收斂性、估計偏差和模型偏差等問題；為了改善上述問題，1992年Banfield和Raftery提出了BR主曲線算法[3]，解決了HS主曲線算法在閉主曲線下曲率過大的問題；Tibshirani針對圓形和橢圓形分布數(shù)據(jù)的模型偏差問題引入半參數(shù)方法[4]，重新定義了基于混合模型的主曲線；2000年，Kegl提出PL主曲線算法，引入了有長度約束的主曲線概念[5]。

2002年，Verbeek提出K段主曲線算法，該算法采用逐漸合并局部第一主成分線來構成主曲線[6]。隨著主曲線的不斷發(fā)展與深入應用，學者們發(fā)現(xiàn)現(xiàn)有的主曲線算法因為其以第一主成分線作為初始值，已無法處理具有環(huán)形分布特征、自相交和分叉等特征的復雜數(shù)據(jù)。針對此問題，2001年，Delicado提出通過有序連接定向點來估算主曲線，稱之為D主曲線算法[7]；同年，Verbeek對K段主曲線算法中定義的參數(shù)進行了大量改進，提出了軟K段主曲線算法[8]；2005年，張紅云提出將主曲線運用于字符與指紋識別[9]；同年，Jochen等提出局部主曲線算法，將數(shù)據(jù)局部特征引入主曲線的提取中[10]。以上算法的提出較好地解決了對以上數(shù)據(jù)類型的主曲線提取問題。近些年，主曲線的發(fā)展更是如火如荼。2009年，張軍平等為解決稀疏和不均勻分布數(shù)據(jù)的主曲線提取問題提出了自適應約束K段主曲線算法[11]，隨之又針對具有非恒定分布特征的數(shù)據(jù)，提出了將數(shù)據(jù)的黎曼距離與數(shù)據(jù)的分布密度相結合的主曲線算法[12]；同年，Ozertem與Erdogmus從一個新的角度介紹了主曲線和曲面，根據(jù)梯度和概率密度估計的海森矩陣重新定義主曲線和曲面(Ozertem and Erdogmus principal curve，OEPC)，OEPC算法通過使用基于核密度估計和高斯混合模型的子空間約束均值漂移(Subspace constrained mean shift, SCMS)生成主曲線和主曲面[13]；2013年，張紅云等提出了基于全局結構的主曲線算法來解決自相交和高度分散數(shù)據(jù)的主曲線提取問題[14]，隨之2014年，為了解決大規(guī)模復雜形態(tài)數(shù)據(jù)的主曲線提取問題，他們將主曲線推廣到粒主曲線[15]；2015年，文獻[16] 針對OEPC算法假定提前獲得完整的數(shù)據(jù)集，并且在計算期間不能將新的數(shù)據(jù)點添加到數(shù)據(jù)集的問題，提出了基于SCMS的增量主曲線算法。

隨著高速計算機和互聯(lián)網商業(yè)化的飛速發(fā)展，存儲在數(shù)據(jù)庫中的海量數(shù)據(jù)的分布形式越來越多樣，這導致用傳統(tǒng)的主曲線分析算法來處理這些數(shù)據(jù)不能給出理想的結果。針對海量復雜數(shù)據(jù)，2017年胡作梁和張紅云提出了基于MapReduce框架的分布式軟K段主曲線算法(Distributed soft K-segments principal curve, DisSKPC)[17]，大大提升了主曲線對復雜數(shù)據(jù)的處理速度。但對于不同類別的數(shù)據(jù)類簇相互包含的復雜數(shù)據(jù)，現(xiàn)有的軟K段主曲線算法仍無法較好地處理，因此迫切需要新理論、新方法來解決該類復雜數(shù)據(jù)的主曲線學習問題，而粒計算是研究如何模擬人類思維，采用多層次、多粒度的思維方式、問題求解方法來解決復雜問題的有效工具。因此，本文研究將粒計算引入復雜數(shù)據(jù)的主曲線學習中，探索多粒度主曲線學習方法。

本文針對傳統(tǒng)主曲線學習在處理復雜性數(shù)據(jù)中存在的問題和困難，探索采用粒計算的粒化策略，根據(jù)數(shù)據(jù)相似性、近似性和功能性來實現(xiàn)對數(shù)據(jù)的?；鸱趾蛿?shù)據(jù)轉換，形成數(shù)據(jù)片段(即局部數(shù)據(jù))；基于主曲線理論和方法，對每類局部數(shù)據(jù)提取主曲線；采用從局部到全局的，自底向上的策略進行多粒度主曲線提取，最終形成數(shù)據(jù)完整的主曲線分布。

1 相關工作

1.1 主曲線定義

主曲線是第一主成分的非線性推廣，在1988年由Trevor Hastie首次提出，他將主曲線定義成一條通過數(shù)據(jù)云或者分布“中間”且滿足自相合的光滑曲線。

HSPC定義 如果光滑曲線f(λ)滿足：

(1)f(λ)不自相交；

(2) 在任何有界Rd子集內；f(λ)是有限長度的；

(3)f(λ)是自相合的，即f(λ)=E(X|λf(x)=λ),則稱f(λ)為X的一條主曲線。其中λf(x)為數(shù)據(jù)點x投影到曲線f(λ)上λ點的值，即

Verbeek認為HS主曲線算法及其改進算法(如BR主曲線，T主曲線和多邊形主曲線算法等)存在一個共同的問題，即把數(shù)據(jù)的第一主成分作為初始化線，沒有考慮數(shù)據(jù)的局部結構特點。因此，當數(shù)據(jù)分布在彎曲度較大或相交曲線周圍時，以上算法給出的最終主曲線分布并不能正確反映數(shù)據(jù)的真實拓撲結構。而軟K段主曲線算法能克服“局部模型”的缺點，可以較好地提取出分布在彎曲度很大或相交曲線周圍的數(shù)據(jù)的主曲線，因此許多學者將該算法應用于指紋和字符識別[18-20]。由于通常k≤n，所以算法的總時間復雜度為O(kn2)，因需要預先存儲兩兩點之間的距離(對稱矩陣，如果使用稀疏矩陣存儲，可以節(jié)省一半的存儲空間)，所以總的空間復雜為O(n2)，其中k為擬合的線段數(shù)，n為數(shù)據(jù)總數(shù)。

隨著信息技術的高速發(fā)展，數(shù)據(jù)收集和數(shù)據(jù)存儲技術的快速進步使得各行各業(yè)積累了海量復雜的數(shù)據(jù)，單純依靠軟K段主曲線算法也難以很好地解決現(xiàn)存的一些復雜數(shù)據(jù)的主曲線提取問題。本文考慮引入粒計算的?；枷?，完成復雜數(shù)據(jù)的預處理工作。

1.2 粒 化

?；抢弥付ǖ牧；呗詫碗s數(shù)據(jù)?；癁樾畔⒘５囊粋€過程，為粒計算的基本問題之一。根據(jù)不同信息特征和用戶需求目標，采用不同的信息?；椒?。常用的粒化方法有基于二元關系的?；?、基于聚類的?；⒒诩禂?shù)據(jù)的?；突谌笔?shù)據(jù)的粒化等[21]。

在現(xiàn)有的?；椒ㄖ校垲愃惴ㄊ且环N常用且有效的數(shù)據(jù)?；椒?，它通過有機地聚集數(shù)據(jù)集中的對象，以形成互不相交的數(shù)據(jù)類型。根據(jù)數(shù)據(jù)集的取值類型劃分，目前基于聚類的信息?；椒ㄖ饕芯繑?shù)值型、名義型以及混合型3種數(shù)據(jù)。而本課題著重解決數(shù)值型的復雜數(shù)據(jù)?；瘑栴}。針對數(shù)值型的復雜數(shù)據(jù)，雖然基于聚類的?；椒軌蛱幚聿糠謹?shù)據(jù)集，但對于不同類別的數(shù)據(jù)類簇相互包含的數(shù)值型復雜數(shù)據(jù)的信息?；芯窟€不夠充分。探討這些問題，對于?；惴ǖ难芯烤哂兄匾囊饬x。在過去數(shù)十年里，譜聚類算法在數(shù)據(jù)聚類和圖像分割中展現(xiàn)出明顯的優(yōu)勢。2002年， Hagen和Kahng[22]提出基于譜圖劃分理論的譜聚類方法，后因Ng等[23]對其理論基礎的完善，使之成為目前數(shù)據(jù)挖掘領域最常用的聚類算法之一。該算法的主要思想是以譜圖理論為基礎，通過對數(shù)據(jù)樣本的相似性矩陣進行特征分解，將高維數(shù)據(jù)映射到低維特征向量空間，然后在特征向量空間中對數(shù)據(jù)點進行聚類。與其他分類方法相比，譜聚類因其高維數(shù)據(jù)空間向低維特征向量空間映射的特性，使之能在避免“維度災難”的前提下處理非凸樣本空間，并且保證全局最優(yōu)收斂。

本文著眼于處理復雜性數(shù)值數(shù)據(jù)，合理選擇粒計算中的譜聚類?；惴?，對數(shù)據(jù)進行預處理，并針對每個粒數(shù)據(jù)提取主曲線，提出了一種新的數(shù)據(jù)處理方法。該方法能夠從理論上完善數(shù)據(jù)處理中復雜性數(shù)據(jù)的表示以及分析等問題的研究，并在實際應用中擴展主曲線的應用領域，推動主曲線理論在數(shù)據(jù)挖掘、機器學習和知識發(fā)現(xiàn)領域的發(fā)展。

2 基于粒計算的復雜數(shù)據(jù)多粒度主曲線提取算法

2.1 基于TNN的譜聚類算法

Chen等[24]提出利用t最近鄰方法(T-nearest neighbor,TNN)構建相似度矩陣S，從而避免了處理復雜數(shù)據(jù)時稠密相似度矩陣的存儲問題，更減少了算法運行時所需的時間、空間以及計算的復雜度，可見基于TNN的譜聚類算法在處理復雜數(shù)據(jù)上具有很大優(yōu)勢。其主要算法流程為：

(1)構造稀疏相似性矩陣。針對每個數(shù)據(jù)樣本點xi，計算其與其他每一個樣本點的相似性距離并插入大小為t的最大堆Hi中，然后得到與xi最相似的t個樣本點，作為稀疏相似性矩陣S的第i行。相似性距離計算方式如式(1)，其中，σ是一個控制Sij隨xi和xj之間距離變化速度的縮放因子。

(1)

L=I-D-1/2SD-1/2

(2)

(3)選取Laplacian矩陣的前k個最大特征值，將數(shù)據(jù)映射到低維特征向量空間。

(4)在低維特征向量空間中對數(shù)據(jù)點使用K-means聚類算法進行聚類。

2.2 軟K段主曲線算法

Verbeek采用局部主成分方法得到k條線段的方法重新定義了軟K段主曲線算法，并依據(jù)光滑性連接k條線段形成最終的主曲線，其與數(shù)據(jù)間距離均方差較小，能夠更真實地反映數(shù)據(jù)的原始分布形態(tài)。其算法流程為:

(1)初始化。輸入數(shù)據(jù)樣本點；計算第一主成分線；輸入k_max。

(2)插入一條新的線段。如果k>k_max，則流程結束。否則，計算點xq，求出點xq的Voronoi域，Voronoi域為

Vq={x∈X|‖x-xq‖≤mind(x,sj),j=1,2,…,k}

(3)

計算Vq的第一主成分線，新插入線段為3σ，第一主成分線的方差為σ2。k=k+1，令sk為新插入線段，sk的Voronoi域為Vk=Φ。

(4)構造優(yōu)化。將k條線段當做哈密頓回路問題求解，并進行優(yōu)化，得到一條通過各個端點的最優(yōu)曲線。計算目標函數(shù)OF是否最小，如果OF最小，則程序結束，否則返回第(2)步。

2.3 基于譜聚類的軟K段主曲線算法

本算法將基于TNN的譜聚類算法和軟K段算法有效地融合，提出了一種新的基于粒計算的復雜數(shù)據(jù)多粒度主曲線提取算法(T-nearest-neighbors spectral clustering and soft K-segmeuts,TNNSC_SK)，并且作了以下改進：(1)對譜聚類算法在第(2)步提出拐點估計方法來自動確定粒的個數(shù)，有效避免了自定義粒子數(shù)目時引起的“錯誤傳播”；(2)對軟K段主曲線算法在第(3)步做了改進，原軟K段主曲線算法是基于把所有主曲線Hamilton路徑算法全部相連，但對于一些復雜數(shù)據(jù)，所有線段完全連接是不合適的，因此這里設定第(3)步中的條件以刪除假邊；(3)原軟K段主曲線算法選擇目標函數(shù)OF達到最小作為主曲線構造過程的終止條件。但是在構造多粒度全局主曲線時，單純的選擇這些條件，容易使最終的主曲線產生過擬合現(xiàn)象，改進的算法在第(4)步中消除部分過擬合的線段，使最終形成多粒度全局主曲線更符合數(shù)據(jù)的原始分布形態(tài)。

TNNSC_SK：基于譜聚類的軟K段主曲線算法偽碼可描述為

(1)輸入：數(shù)據(jù)點xi

(2)輸出：數(shù)據(jù)點的主曲線連接矩陣及段的端點等

(3)函數(shù)：gen_nn_distance(ThreeCircles,num_neighbors, block_size, 0)

計算相似度矩陣；

輸出相似度矩陣文件：NN_sym_distance.mat

(4)函數(shù)：sc1(A, sigma, num_clusters)

譜聚類；

輸出聚類的標簽矩陣：cluster_labels

(5)函數(shù)：k_seg_soft(X,k_max,alpha,lambda,INT_PLOT)

軟K段主曲線算法；

輸出主曲線的連接矩陣及段的端點等：[edges,vertices,of,y,mm,mm2]

步驟可詳細描述為：

(1)利用譜聚類進行數(shù)據(jù)特征提取。輸入所有數(shù)據(jù)點xi，計算其到所有數(shù)據(jù)點的距離,即

(4)

利用相似度函數(shù)公式(5)得到數(shù)據(jù)集的相似度矩陣，其中選擇參數(shù)σi[25]，σi=‖xi-xit‖，xi t為通過排序xi的t/2鄰域到xi的鄰居的距離。

(5)

計算Laplacian矩陣，選取Laplacian矩陣的前k個最大的特征值，得到特征向量v1,v2,…,vk，構造矩陣V=[v1,v2,…,vk]∈Rk×k。

(2)利用拐點的除斜率確定粒的數(shù)目?；诳焖偎阉骱兔芏确宓木垲愃惴?Clustering by fast search and find of density peaks，CFSFDP)[26]是2014年發(fā)表在Science雜志上的一種聚類算法，該算法為每個樣本點引入兩個屬性局部密度ρi和距離δi?；贑FSFDP算法提出的兩個屬性值引入一個新的變量γi，稱為決策屬性，其計算公式為

γi=ρi*δi

(6)

通過相鄰數(shù)據(jù)的決策屬性相減的方式獲得減斜率，再把相鄰減斜率相除得到除斜率，這里把除斜率比左右相鄰點都大的點所在的序號作為拐點，也就是最后的聚類數(shù)目cluster_num。最后將cluster_num作為聚類的個數(shù)傳入k-means方法，輸出樣本的粒化標簽向量cluster_labels。

(3)消除構造Hamilton路徑中的假邊。根據(jù)標簽向量cluster_labels輸入單粒度的數(shù)據(jù)，利用軟K段算法進行單粒度主曲線的提取，產生s1,s2,…，sk線段，然后使用貪婪算法進行Hamilton路徑的構造， 產生連線e1,e2，…,ek-1。雖設有代價函數(shù)C(ei)=s(ei)+λa(ei)，其中ei為連接兩個子圖端點的邊，s(ei)為邊ei的長度，但仍避免不了假邊的出現(xiàn)。因此作以下改進：對e1,e2，…,ek-1檢查ei連接的主干線si，si+1，將si，si+1被ei連接的兩端點的Voronoi域點形成一個點集合，計算域中每個點相對ei邊的Voronoi′域，并計算Voronoi′域內點的數(shù)目/ei線段長度，定義為dei，若dei大于給定的經驗值，則判斷ei為假邊，并從e1,e2,…,ek-1中消除。

(4)構造多粒度全局主曲線。輸入所有粒的s1,s2,…，sk與e1,e2,…,ek-1線段，利用局部到全局的策略完成主曲線的多粒度提取過程，即使當目標函數(shù)OF達到最小，也不能確保最終的主曲線最接近數(shù)據(jù)的原始分布，往往出現(xiàn)過擬合現(xiàn)象。

(7)

據(jù)此提出以下改進：分別計算s1,s2,…，sk中任意兩個線段間的距離。如si，計算其余線段兩端點到該線的投影距離為dsisj，若dsisj小于λσ2(其中λ為自定義參數(shù)，σ2為噪聲方差)，即考慮刪除si與sj中較短的線段。

2.4 算法復雜度分析

在TNNSC_SK算法中，計算Laplacian矩陣的計算開銷較小，kmeans算法以及改進后的軟K段主曲線算法的復雜度變化相對較小，因此這里不再討論。

通過計算所有樣本點之間的相互距離，最后得到與xi最為相似的t個樣本點，在t個樣本點的堆中插入或者刪除1個元素的時間復雜度為O(logt)，因此該步驟的時間復雜度為：O(n2d+n2logt)；該步驟需要維護n個大小為t的樣本堆，因此空間復雜度為：O(nt)。其中n為數(shù)據(jù)總數(shù)，d為數(shù)據(jù)維數(shù)，t為最近鄰數(shù)目。

3 實驗及分析

使用本文提出的TNNSC_SK算法，在2個公開數(shù)據(jù)集(Twomoons，Spiral)和2個人工數(shù)據(jù)集(DisorderThreeCircles，ThreeCircle)上進行了測試。計算機CPU為Intel(R) Xeon(R) CPU E5-2630 v2 @ 2.60 GHz，內存8 GB，操作系統(tǒng)Windows 7，操作軟件為MATLAB R2014a。

3.1 有效性分析

對于4類數(shù)據(jù)集，TNNSC_SK算法的實驗結果如圖1所示，其中不同的顏色代表不同的?；Y果，黑色線段與紅色線段共同組成每個粒的主曲線?？梢?，本文提出的算法能比較完好地擬合出復雜數(shù)據(jù)的分布形態(tài)。

圖1 TNNSC_SK算法在不同數(shù)據(jù)集上的效果圖Fig．1 Effect of TNNSC_SK on different datasets

圖2 SK和TNNSC_SK算法在不同數(shù)據(jù)集上的效果對比圖Fig．2 Effect comparison of SK and TNNSC_SK on different datasets

3.2 對比性分析

通過5組對比實驗來驗證所提算法的可行性。5組實驗分別是在 Twomoons，Spiral，DisorderThreeCircles和ThreeCircles四個數(shù)據(jù)集上對比TNNSC_SK算法和軟K段主曲線算法(SK)算法，結果如圖2所示;以及在Spiral數(shù)據(jù)集上對比TNNSC_SK算法與DisSKPC算法，結果如圖3所示。其中圖2 (a，c，e,g)為SK算法的運行結果，圖2(b,d,f,h)為TNNSC_SK算法的運行結果，不同的顏色代表不同的粒數(shù)據(jù)。從圖2(a,c,e,g)4個圖中都可看出SK算法存在過擬合現(xiàn)象，而且只有主曲線無法區(qū)分復雜數(shù)據(jù)的分布種類。而從圖2(b,d,f,h)可看出，TNNSC_SK算法把復雜數(shù)據(jù)?；啥鄠€粒再分別進行主曲線的提取，有效避免了不同粒之間過擬合線段的產生。

圖3 DisSKPC和TNNSC_SK效果對比圖Fig．3 Effect comparison of DisSKPC and TNNSC_SK

從文獻[17]中得知DisSKPC算法主要針對復雜數(shù)據(jù)的海量問題，如圖3(a)顯示，在處理復雜的單螺旋Spiral數(shù)據(jù)集上該算法效果極佳，能較真實地描繪出數(shù)據(jù)的原始分布形態(tài)；但對于多螺旋Spiral數(shù)據(jù)集，DisSKPC算法處理結果如圖3(b)，可看出存在過擬合及假邊現(xiàn)象，而且無法區(qū)分數(shù)據(jù)的分布種類，TNNSC_SK算法處理結果如圖3(c)，消除了圖3(b)在主曲線提取時的問題，并且主曲線的分布更符合數(shù)據(jù)的真實形態(tài)。

綜上所述，TNNSC_SK算法相比于傳統(tǒng)的SK算法以及SK算法的DisSKPC改進算法，能更好地擬合出復雜數(shù)據(jù)的原始分布形態(tài)。

3.3 目標函數(shù)OF對多粒度主曲線提取時的影響

表1 目標函數(shù)OF值

針對軟K段主曲線算法的結束條件——目標函數(shù)OF對多粒度主曲線提取時的影響，作了如下實驗。如表1以Spiral數(shù)據(jù)集?；蟮囊粋€粒(圖4(a)中的紫色粒)為例，當OF值達到最小值0.164 5時，建議的最大主曲線段數(shù)k_max為8，但當k_max設為8時，在使用本文所提算法對該粒進行主曲線提取的過程中，出現(xiàn)了過擬合現(xiàn)象，如圖4(b)。因此單純依靠目標函數(shù)OF值達到最小作為算法的終止條件是不可靠的。

本文在算法2.3的第(4)步中，對該問題進行了優(yōu)化，以刪除圖4(b)中黑色的過擬合邊，經過實驗達到了圖4(c)的結果，此時OF值為0.201 8，k_max設為7。根據(jù)圖4的效果圖可知，單純依靠目標函數(shù)或k_max作為算法終止條件會導致過擬合現(xiàn)象，而結合本文提出的優(yōu)化算法可以有效地解決該問題。并且根據(jù)2.3中第3步消除假邊的優(yōu)化方法，可以有效地刪除圖4(b)中交叉的兩條紅色假邊。

圖4 TNNSC_SK優(yōu)化對比效果圖Fig．4 Effect optimization of TNNSC_SK

4 結束語

本文針對復雜的數(shù)值數(shù)據(jù)設計并實現(xiàn)了基于粒計算的復雜數(shù)據(jù)多粒度主曲線提取算法，并在確定粒子數(shù)目、消除假邊和過擬合線段上作了優(yōu)化。通過有效性、對比性以及目標函數(shù)OF等多個角度進行了實驗，結果表明本文所提算法在復雜形狀數(shù)據(jù)的主曲線提取上明顯優(yōu)于軟K段算法，能更好地擬合出復雜數(shù)據(jù)的原始分布形態(tài)。但本算法也有待改進的地方，如在構造多粒度全局主曲線時，對于如何處理過擬合邊仍需要討論，這在下一步工作中將進行深入研究。主曲線算法以一種非監(jiān)督的方式揭示數(shù)據(jù)的分布規(guī)律，在機器學習領域有重要地位，而本文提出的方法為處理復雜數(shù)據(jù)提供了一種新的可行且有效的解決方案。

[1] Baldi P, Hornik K. Neural networks and principal component analysis: Learning from examples without local minima [J]. Neural Networks, 1989, 2(1):53-58.

[2] Hastie T, Stuetzle W. Principal curves[J]. Journal of the American Statistical Association, 1989, 84(406):502-516.

[3] Banfield J D, Raftery A E. Ice floe identification in satellite images using mathematical morphology and clustering about principal curves [J]. Journal of the American Statistical Association, 1992, 87(417):7-16.

[4] Tibshirani R. Principal curves revisited [J]. Statistics and Computing, 1992, 2(4):183-190.

[5] Kegl B, Krzyzak A, Linder T, et al. Learning and design of principal curves [J]. Pattern Analysis & Machine Intelligence IEEE Transactions on, 2000, 22(3):281-297.

[6] Verbeek J J, Vlassis N, Se B. A k-segments algorithm for finding principal curves [J]. Pattern Recognition Letters, 2002, 23(8):1009-1017.

[7] Delicado P. Another look at principal curves and surfaces [J]. Journal of Multivariate Analysis, 2001, 77(1):84-116.

[8] Verbeek J J, Vlassis N A, Kr?se B J A. A soft k-segments algorithm for principal curves[M]. Berlin, Heidelberg:Springer, 2001:450-456.

[9] 張紅云. 基于主曲線的脫機手寫字符識別的研究 [D]. 上海:同濟大學, 2005.

Zhang Hongyun. Research on off-line handwritten digit recognition based on principal curves [D]. Shanghai: Tongji University, 2005.

[10] Einbeck J, Tutz G, Evers L. Local principal curves [J]. Statistics and Computing, 2005, 15(4):301-313.

[11] Zhang J, Chen D, Kruger U. Adaptive constraint k-segment principal curves for intelligent transportation systems[J]. IEEE Transactions on Intelligent Transportation Systems, 2009, 9(4):666-677.

[12] Zhang J, Wang X, Kruger U, et al. Principal curve algorithms for partitioning high-dimensional data spaces [J]. IEEE Transactions on Neural Networks, 2011, 22(3):367-380.

[13] Ozertem U, Erdogmus D. Locally defined principal curves and surfaces [J]. Journal of Machine Learning Research, 2011, 12(4):1249-1286.

[14] Zhang H, Pedrycz W, Miao D, et al. A global structure-based algorithm for detecting the principal graph from complex data [J].Pattern Recognition, 2013, 46(6):1638-1647.

[15] Zhang H, Pedrycz W, Miao D, et al. From principal curves to granular principal curves [J]. IEEE Transactions on Cybernetics, 2014, 44(6):748-760.

[16] Ghassabeh Y A, Rudzicz F. Incremental algorithm for finding principal curves [J]. IET Signal Processing, 2015, 9(7):521-528.

[17] 胡作梁, 張紅云. 基于MapReduce框架的分布式軟K段主曲線算法[J].數(shù)據(jù)采集與處理, 2017, 32(3):507-515.

Hu Zuoliang, Zhang Hongyun. Distributed soft k-segments algorithm for principal curves based on mapreduce[J]. Journal of Data Acquisition and Processing, 2017, 32(3):507-515.

[18] 張紅云, 苗奪謙, 傅文杰. 基于改進的GPL主曲線算法的指紋特征分析與提取[J]. 模式識別與人工智能, 2007, 20(6):763-769.

Zhang Hongyun, Miao Duoqian, Fu Wenjie. Analysis and extraction of fingerprint minutiae based on improved GPL principal curve algorithm[J]. Pattern Recognition and Artificial Intelligence, 2007, 20(6):763-769.

[19] Yang M, Liao Z W. The skeletonization research of low-quality Chinese characters based on principal curves [C] // Machine Learning and Cybernetics, 2009 International Conference. Baoding, China: Institute of Electrical and Electronics Engineers, 2009:3238-3241.

[20] 焦娜. 改進的軟K段主曲線算法及其在指紋骨架提取中的應用[J]. 數(shù)據(jù)采集與處理, 2015, 30(5):1070-1077.

Jiao Na. Improved soft K-segments algorithm for principal curves and its applications on fingerprint skeletonization extraction [J]. Journal of Data Acquisition and Processing, 2015, 30(5):1070-1077.

[21] 錢宇華. 復雜數(shù)據(jù)的?；瘷C理與數(shù)據(jù)建模[D]. 太原：山西大學, 2011.

Qian Yuhua. Granulation mechanism and data modeling of complex data[D]. Taiyuan: Shanxi University, 2011.

[22] Hagen L, Kahng A B. New spectral methods for ratio cut partitioning and clustering [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2002, 11(9):1074-1085.

[23] Ng A Y, Jordan M I, Weiss Y. On spectral clustering: Analysis and an algorithm [J]. Proceedings of Advances in Neural Information Processing Systems, 2002, 14:849-856.

[24] Chen W Y, Song Y, Bai H, et al. Parallel spectral clustering in distributed systems [J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2011, 33(3):568-586.

[25] Zelnik-Manor L. Self-tuning spectral clustering [J]. Advances in Neural Information Processing Systems, 2004, 17:1601-1608.

[26] Rodriguez A, Laio A. Clustering by fast search and find of density peaks [J]. Science, 2014, 344(6191):1492-1496.