[科普中國(guó)]-主曲線

主曲線概念是Hastie于1984年提出的。主曲線是通過(guò)數(shù)據(jù)分布“中央”并滿足“自相合”的光滑曲線，其目的是根據(jù)給定的數(shù)據(jù)集合求出一條曲線，使得這條曲線對(duì)給定的數(shù)據(jù)集合是某種意義下的對(duì)偶。形象地說(shuō)，希望能尋找通過(guò)數(shù)據(jù)分布“中央”的曲線，使它能真實(shí)地反映數(shù)據(jù)的形態(tài)，即曲線是數(shù)據(jù)集合的“骨架”，數(shù)據(jù)集合是這個(gè)曲線的“云”。由此可見，主曲線對(duì)數(shù)據(jù)的信息保持性好。

定義假設(shè)隨機(jī)向量 的概率密度為 ，通過(guò)Y數(shù)據(jù)分布中間的一條曲線 ，如果滿足 ，則稱 是Y的一條主曲線其中 是數(shù)據(jù)點(diǎn)y投影到曲線 上s點(diǎn)的值。

由主曲線定義可知：主曲線上每個(gè)點(diǎn)是所有投影至該點(diǎn)的數(shù)據(jù)點(diǎn)的條件均值，它滿足自相合性。主曲線的理論基礎(chǔ)是尋找嵌入高維空間的非歐氏低維流形，也是線性主成分的非線性推廣，它能真實(shí)地反映數(shù)據(jù)的形態(tài)。

算法研究本程序定義了主曲線和確定主曲線的實(shí)際算法。多邊形線算法的基本運(yùn)算法則是首先確定一條直線段，然后在循環(huán)算法中通過(guò)不斷加入新的頂點(diǎn)來(lái)增加線段的數(shù)量。在加入一個(gè)新的頂點(diǎn)以后，所有的頂點(diǎn)位置在一個(gè)內(nèi)部的環(huán)中被更新。在這個(gè)例子中，PL運(yùn)算法則和HS運(yùn)算法則在計(jì)算的復(fù)雜程度和算法的完善程度上作出了比較。4段和15段，由在半圓上任意兩個(gè)坐標(biāo)點(diǎn)加入單獨(dú)的高斯誤差而產(chǎn)生。

PL算法在由NIST19號(hào)專有數(shù)據(jù)庫(kù)產(chǎn)生的單獨(dú)數(shù)據(jù)元構(gòu)成的圖像中得到了測(cè)試。我們發(fā)現(xiàn)PL算法可以有效的找出沒(méi)有環(huán)和分叉的圖像的中間軸。由于中間軸可能是一些曲線連接而成而不是只有一條曲線，所以在這里我們擴(kuò)展了PL算法，找出數(shù)據(jù)元的主曲線。擴(kuò)展了的算法也包含了實(shí)現(xiàn)分段線性骨架的兩個(gè)原則，一種獲取字符圖像近似輪廓的初始化方法和一系列用來(lái)改善由初始化方法獲得的骨架結(jié)構(gòu)質(zhì)量的更改結(jié)構(gòu)工作。為了避免混淆，我們用術(shù)語(yǔ)“骨架”來(lái)表示近似性中間軸的二元圖像，我們把由PL算法產(chǎn)生出的連接曲線看做模板骨架.

應(yīng)用

主曲線以前被用在圖像處理領(lǐng)域。這種圖像用來(lái)描述在衛(wèi)星拍攝下的冰川及其輪廓。其主程序用了一個(gè)閉合的曲線來(lái)估算冰川的輪廓。專家們除去了HS算法中不合適的部分，并且用更完善的粗略估算冰川輪廓的程序來(lái)取代HS算法的初始化步驟。此外，采用數(shù)據(jù)元集合，而不是HS算法所產(chǎn)生的點(diǎn)或線的集合，向中間軸集中的方式來(lái)擴(kuò)展現(xiàn)有的聚合算法。初始化的曲線由SOM算法的一個(gè)變量產(chǎn)生，在SOM算法中相互關(guān)系被定義為字符圖像的一個(gè)最小二叉樹。HS算法用來(lái)使曲線與模板相對(duì)應(yīng)。下一步的要點(diǎn)與SOM算法的更新規(guī)則類似。

利用主曲線實(shí)現(xiàn)分段線性骨架的方法被Mahmoud、Datta和Parui等人所提出。同樣的方法，在SOM算法中用來(lái)最優(yōu)化分段線性骨架的頂點(diǎn)位置。算法在構(gòu)建骨架方面采用“自頂向下”的策略：近似性地從一個(gè)線性拓?fù)涑霭l(fā)，然后逐步加入環(huán)和交叉到骨架中，骨架是由基于SOM算法的當(dāng)前幾何樣式得出的。SOM算法涉及到一個(gè)獲取字符圖像分段線性骨架的運(yùn)算法則。這種運(yùn)算法則以ISODATA算法為基礎(chǔ)，ISODATA算法近似于SOM算法。

目的

主曲線算法的目的是找出與字符圖像相對(duì)應(yīng)的光滑的分段線性曲線。這些曲線在某個(gè)頂點(diǎn)彼此連接，因而在字符圖像的中心平面范圍內(nèi)形成一個(gè)歐幾里德曲線。一個(gè)歐幾里德曲線G（V，S）在空間中由變量V和S確定，

主曲線算法從一個(gè)基于傳統(tǒng)稀釋方法的初始化工作開始。初始曲線找出字符圖像的近似拓?fù)浣Y(jié)構(gòu)，然而,它不是平滑的，而且它通常包含許多假的分叉和不適合的結(jié)構(gòu)元素。為了解決這兩個(gè)問(wèn)題，在前兩步中間增加了更改結(jié)構(gòu)的步驟，使得主曲線算法更加有效。在更改結(jié)構(gòu)步驟中，我們運(yùn)用一些操作手段來(lái)調(diào)整曲線骨架結(jié)構(gòu)的不完整的地方。算法建立在最小能量函數(shù)的基礎(chǔ)之上。

研究動(dòng)機(jī)與意義

自1904年Spearman提出線性主成分分析方法以來(lái)，由于這種方法簡(jiǎn)單且便于使用，至今還是數(shù)據(jù)統(tǒng)計(jì)分析的重要工具之一。線性主成分分析的原理是將數(shù)據(jù)集合投影到一個(gè)矢量，使得投影的均方差最大，由此，將這個(gè)矢量稱為數(shù)據(jù)集合的第一主成分。正是這個(gè)考慮，在均方差的意義下，這個(gè)方法有兩個(gè)重要的優(yōu)點(diǎn)：其一，數(shù)據(jù)集合可以使用一個(gè)矢量來(lái)描述，從而達(dá)到減小信息描述長(zhǎng)度的目的，其二，計(jì)算第一以及依次主成分，可以變換為求解基于數(shù)據(jù)自相關(guān)矩陣的特征值方程。另外，第一與依次主成分矢量保持正交關(guān)系，這意味著，與主成分矢量平行的矢量具有與主成分相同的性質(zhì)。正是這兩個(gè)原因，加上在統(tǒng)計(jì)上以均方差為保證，主成分分析得到廣泛的應(yīng)用。 由于信息描述長(zhǎng)度與信息保持性之間存在矛盾，相對(duì)較長(zhǎng)的信息描述長(zhǎng)度，較短描述長(zhǎng)度的信息描述是以損失信息保持性為代價(jià)的，而主成分分析的本質(zhì)是一種在均方差意義下的統(tǒng)計(jì)平均。盡管它可以獲得較短的信息描述長(zhǎng)度，但是，信息保持性的代價(jià)相當(dāng)大，由于信息保持性是對(duì)數(shù)據(jù)分布的規(guī)律性認(rèn)識(shí)，因此，對(duì)某些問(wèn)題，這個(gè)代價(jià)可接受的，但是，另外一些問(wèn)題，可能就不能接受了。例如，對(duì)原始語(yǔ)音信號(hào)的分析，單純的主成分分析就不一定有效。 顯然，這沒(méi)有一個(gè)一般性的答案，這取決于所需解決問(wèn)題的需求。

目前，盡管在主曲線的研究中，還存在著大量的數(shù)學(xué)問(wèn)題，但是，由于其暗示的廣泛應(yīng)用前景，已引起計(jì)算機(jī)科學(xué)家的關(guān)注，現(xiàn)在應(yīng)用方面已有大量的報(bào)道，如線性對(duì)撞機(jī)中對(duì)電子束運(yùn)行軌跡的控制、圖像處理中辨識(shí)冰原輪廓、手寫體的主曲線模板化、語(yǔ)音識(shí)別中對(duì)聲音數(shù)據(jù)的約簡(jiǎn)建模和數(shù)據(jù)可聽化、生態(tài)學(xué)中尋找種群的有序分布及過(guò)程監(jiān)控。同時(shí)，在認(rèn)知領(lǐng)域Seung提出感知以流形方式存在，并在神經(jīng)生理學(xué)上發(fā)現(xiàn)整個(gè)神經(jīng)細(xì)胞群的觸發(fā)率可以由少量的變量組成的函數(shù)來(lái)描述，如眼的角度和頭的方向，這隱含了神經(jīng)元群體活動(dòng)性是由其內(nèi)在的低維結(jié)構(gòu)所控制。主曲線本身是流形的一維形式。

原理、發(fā)展脈絡(luò)以及應(yīng)用為了說(shuō)明主曲線的原理、發(fā)展脈絡(luò)以及應(yīng)用，首先介紹其原始動(dòng)機(jī)是必要的1。Hastie在他關(guān)于主曲線的開創(chuàng)性論文中描述了其研究動(dòng)機(jī)，Hastie認(rèn)為主曲線與非線性回歸方法的發(fā)展上具有對(duì)稱性，分別是線性主成分分析與線性回歸分析的非線性推廣模型，Hastie寫到：類似于線性回歸方法的非線性推廣，使用光滑曲線代替線性主成分總結(jié)數(shù)據(jù)，以求出對(duì)稱變量之間的曲線，這樣的曲線從數(shù)據(jù)的中部光滑地通過(guò)，且不限制于對(duì)數(shù)據(jù)的光滑線性平均，甚至不限制于數(shù)據(jù)的中部是直線，只希望使得數(shù)據(jù)點(diǎn)集合到曲線的正交距離最小。這個(gè)陳述清晰地指出了他的研究與主成分分析和回歸分析的區(qū)別，并給出了建模的統(tǒng)計(jì)目標(biāo)。同時(shí)，從這個(gè)陳述中也可以看出，基于直線的主成分分析只是主曲線的一個(gè)特例。因此，主曲線的提出，可以理解為基于線性的主成分分析方法向更精確描述實(shí)際世界的非線性分析方法的推廣。 應(yīng)該指出的是，目前，“向非線性”推廣是數(shù)據(jù)統(tǒng)計(jì)分析的研究主流，但是，存在著不同的技術(shù)路線。

分類最典型的研究大致可以分為兩類：

其一，根據(jù)統(tǒng)計(jì)學(xué)習(xí)理論中的核技術(shù)，將數(shù)據(jù)集合映射到特征空間，然后，在特征空間計(jì)算數(shù)據(jù)集合的主成分，稱為核主成分分析(KPCA)，這個(gè)技術(shù)路線的本質(zhì)還是線性主成分分析。

其二，從數(shù)據(jù)本身的分布出發(fā)，希望找到能最好描述數(shù)據(jù)內(nèi)在結(jié)構(gòu)的概率分布模型，如生成式拓?fù)溆成?Generative Topographic Mapping,縮寫為GTM)，矢量量化(VQ)及主曲線，以及流形擬合等。提出“主曲線的研究與回歸分析有何區(qū)別”是自然的，兩者的動(dòng)機(jī)都是企望求出一個(gè)函數(shù)代替數(shù)據(jù)集合，但是，兩者有本質(zhì)的差別：其一，一般地說(shuō)，回歸分析是假設(shè)數(shù)據(jù)集合的變量有因果關(guān)系，換句話說(shuō)，數(shù)據(jù)的變量可以表示為一個(gè)因果關(guān)系的函數(shù)，有些是自變量，有些則是因變量。其二，回歸分析一般需要給定一個(gè)數(shù)學(xué)基函數(shù)，回歸分析是根據(jù)數(shù)據(jù)集合中變量的因果關(guān)系，計(jì)算這個(gè)數(shù)學(xué)基函數(shù)待定的參數(shù)。這與主曲線的研究動(dòng)機(jī)完全不同。對(duì)于前者，主曲線的研究目標(biāo)是解決數(shù)據(jù)變量沒(méi)有必然因果關(guān)系的問(wèn)題，更重要的是后者，認(rèn)為事先假定數(shù)據(jù)服從某種分布(如正態(tài)分布)的方法(這與給定數(shù)學(xué)基函數(shù)，根據(jù)數(shù)據(jù)確定參數(shù)的方法類似)，對(duì)某些未知世界的解釋是不合理的，因?yàn)檫@個(gè)假設(shè)可能是錯(cuò)誤的，為了保證數(shù)據(jù)分析不是假設(shè)在一個(gè)錯(cuò)誤結(jié)構(gòu)下，主曲線的研究強(qiáng)調(diào)非參數(shù)分析。

當(dāng)然，這并不是完全否定了參數(shù)法這一經(jīng)典方法，事實(shí)上，參數(shù)法在先驗(yàn)知識(shí)明確時(shí)存在相當(dāng)大的好處。總之，根據(jù)上述討論的動(dòng)機(jī)，主曲線是尋找一種幾何上直觀、理論上完備、就解決的問(wèn)題而言，這個(gè)方法與主成分分析一致，但是，主曲線的目標(biāo)不是僅僅尋找一個(gè)數(shù)據(jù)集合的脊梁骨，而是希望獲得數(shù)據(jù)集合的骨架。數(shù)據(jù)集合的脊梁骨可以使用線性的方法解決，但骨架就需要借助非線性方法了。應(yīng)該強(qiáng)調(diào)的是，主曲線繼承了主成分分析的眾多思想，它是主成分分析的非線性推廣。另外，盡管這個(gè)方法似乎與回歸分析的目標(biāo)類似，都是試圖獲得對(duì)數(shù)據(jù)集合信息長(zhǎng)度更短的表示，但是，這個(gè)方法與回歸分析完全不同，最大的差別是它不是事先給定一個(gè)基函數(shù)(或假定一個(gè)分布)，從而將問(wèn)題變換為參數(shù)估計(jì)問(wèn)題，而是一種非參數(shù)的方法。

本詞條內(nèi)容貢獻(xiàn)者為:

劉軍 - 副研究員 - 中國(guó)科學(xué)院工程熱物理研究所