陶漢　李星

摘要：在這個(gè)大數(shù)據(jù)時(shí)代，我們時(shí)常與數(shù)據(jù)打著交道。通常我們可以用一個(gè)向量來(lái)表示一個(gè)數(shù)據(jù)樣本，數(shù)據(jù)的維度就是向量的維度。比如我們常見(jiàn)的二維數(shù)據(jù)、三維數(shù)據(jù)可以直觀地可視化。有的數(shù)據(jù)維度非常高，比如描述人臉、聲音等的數(shù)據(jù)樣本它們的維度就通常高達(dá)上百。通過(guò)簡(jiǎn)單的歐式聚類(lèi)來(lái)進(jìn)行數(shù)據(jù)樣本的分類(lèi)，在低緯度數(shù)據(jù)樣本中大多有良好的分類(lèi)結(jié)果。但是在高維數(shù)據(jù)的分類(lèi)問(wèn)題中，基于歐式距離的分類(lèi)方法通常都會(huì)失效。所以針對(duì)高緯度數(shù)據(jù)的分類(lèi)提出一種簡(jiǎn)單有效的方法是具有一定意義的。該文的創(chuàng)新點(diǎn)在于：針對(duì)不同維度數(shù)據(jù)的子空間分類(lèi)以及多流形分類(lèi)問(wèn)題， 該文提出了“種子生長(zhǎng)模型”較好地解決了該問(wèn)題。 該模型在通過(guò)模擬種子的非線性傳播與生長(zhǎng)的同時(shí)，加以生長(zhǎng)規(guī)則的限制， 使得與種子具有較高相似性的樣本被不斷地歸類(lèi)，其他的樣本點(diǎn)逐漸成為新的 種子，種子再不斷更新與生長(zhǎng)，最終完成分類(lèi)。該模型具有較強(qiáng)的一般性與適 應(yīng)性，能夠較好地解決不同維度樣本的子空間分類(lèi)與多流形分類(lèi)問(wèn)題。

關(guān)鍵詞：數(shù)據(jù)分類(lèi)；高維數(shù)據(jù)；生長(zhǎng)算法

中圖分類(lèi)號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）05-0005-02

1 研究背景

數(shù)據(jù)的分析和處理方法成為了諸多問(wèn)題成功解決的關(guān)鍵。高緯度的數(shù)據(jù)分類(lèi)不能簡(jiǎn)單地用基于歐式距離分類(lèi)。常見(jiàn)的方法已經(jīng)有的是譜聚類(lèi)方法、各種基于流型學(xué)習(xí)的方法，它們大多對(duì)于高緯度的數(shù)據(jù)分類(lèi)有著較好的結(jié)果。本文從數(shù)據(jù)樣本中數(shù)據(jù)本身的相似性出發(fā)，從“區(qū)域生長(zhǎng)算法”中得到啟發(fā)，提出一種“種子生長(zhǎng)算法”來(lái)實(shí)現(xiàn)高緯度數(shù)據(jù)樣本的分類(lèi)。傳統(tǒng)的生長(zhǎng)算法的思路大致是以下幾步：

1）初始化開(kāi)始，找到第1個(gè)還沒(méi)有歸屬的像素， 并且設(shè)該像素為（x0， y0）；

2）迭代開(kāi)始，以（x0， y0）為中心， 考慮（x0， y0）的8鄰域像素（x， y）如果（x0， y0）滿(mǎn)足生長(zhǎng)準(zhǔn)則， 將（x， y）與（x0， y0）合并（在同一區(qū)域內(nèi)）， 同時(shí)將（x， y）壓入堆棧；

3）從堆棧中取出一個(gè)像素，把它當(dāng)做（x0， y0）返回到步驟2；

4）當(dāng)堆棧為空時(shí)！返回到步驟1；

5）重復(fù)步驟1-4直到圖像中的每個(gè)點(diǎn)都有歸屬時(shí)。生長(zhǎng)結(jié)束。

傳統(tǒng)生長(zhǎng)算法的規(guī)則主要關(guān)鍵是種子的選取和相似度判定準(zhǔn)則的設(shè)計(jì)，其中種子可以人工隨機(jī)選取也可以通過(guò)一些具體問(wèn)題具體分析的方法來(lái)選取，相似度主要是灰度值或者其他打分函數(shù)，同時(shí)閾值的選取也會(huì)影響最終分類(lèi)的結(jié)果，所以說(shuō)最后還有一個(gè)調(diào)參的過(guò)程。

數(shù)據(jù)與方法：

本算法的基本思路是在數(shù)據(jù)集中，選出起始點(diǎn)，從該點(diǎn)開(kāi)始模擬種子生長(zhǎng)過(guò)程。算法不斷地將相似點(diǎn)歸為一類(lèi)，最終完成所有的數(shù)據(jù)點(diǎn)分類(lèi)。下圖是算法概要：

在初始化階段，本算法第一步是選取一個(gè)邊緣點(diǎn)作為初始點(diǎn)（稱(chēng)為種子點(diǎn)S0），其余的點(diǎn)是未分類(lèi)點(diǎn)集合。在未分類(lèi)點(diǎn)中，選出一個(gè)最近的點(diǎn)作為初始的下一個(gè)種子候選點(diǎn)Sc。S0與Sc構(gòu)成的向量稱(chēng)為中心向量。這是初始步驟。最為關(guān)鍵的是迭代步驟，對(duì)于當(dāng)前的種子點(diǎn)來(lái)說(shuō)，點(diǎn)分為已分類(lèi)、未分類(lèi)、已淘汰。只要一個(gè)新的未分類(lèi)點(diǎn)納入已分類(lèi)中，當(dāng)前就會(huì)形成一個(gè)種子向量，即由新分類(lèi)點(diǎn)與新的種子點(diǎn)形成的向量。該算法的核心內(nèi)容就是比較種子向量與中心向量的相似度來(lái)判定候選點(diǎn)是否應(yīng)該分類(lèi)。根據(jù)具體問(wèn)題具體分析，本文的相似度評(píng)價(jià)指標(biāo)采取了向量夾角、向量距離或者法向量，如圖所示。等到迭代結(jié)束之后，所有點(diǎn)的狀態(tài)分為已分類(lèi)、已淘汰時(shí)，迭代結(jié)束。意味著所有已分類(lèi)點(diǎn)與初始的種子點(diǎn)被分為一類(lèi)。特別注意的是，此處應(yīng)選取邊緣點(diǎn)作為初始種子，以控制種子生長(zhǎng)方向，使得種子能夠在 該流形上有規(guī)律地生長(zhǎng)。最后不斷進(jìn)行迭代，直到完成所有的分類(lèi)點(diǎn)。圖2是算法的流程：

本文將該算法運(yùn)用到了三維立體數(shù)據(jù)、多維人臉數(shù)據(jù)中。實(shí)驗(yàn)結(jié)果表明，該算法簡(jiǎn)單有效，有著良好的分類(lèi)結(jié)果。

2 實(shí)驗(yàn)結(jié)果

下圖分別是三維立體數(shù)據(jù)與多維人臉數(shù)據(jù)的分類(lèi)結(jié)果：

如圖所示，本算法對(duì)一個(gè)三維的立體梯臺(tái)進(jìn)行了準(zhǔn)確地分類(lèi)。通過(guò)運(yùn)用上述的算法，成功地將梯臺(tái)的上頂、下頂、區(qū)別進(jìn)行分類(lèi)。在驗(yàn)證的過(guò)程中，我們也使用了二維直線、二維曲線的數(shù)據(jù)集。最終結(jié)果都表明有良好的分類(lèi)結(jié)果。

人臉數(shù)據(jù)的每一個(gè)樣本是描述像素的高維數(shù)據(jù)，它不能直接顯示在三維坐標(biāo)軸中。同樣運(yùn)用上訴算法，采用了中心向量與種子向量法向量的考量標(biāo)準(zhǔn)，分類(lèi)結(jié)果準(zhǔn)確。

3 結(jié)論與展望

針對(duì)高維數(shù)據(jù)分類(lèi)問(wèn)題，本文提出了一種簡(jiǎn)單有效的算法，通過(guò)給定樣本集U的不同特點(diǎn)，修改種子生長(zhǎng)規(guī)則以及調(diào)整模型參數(shù)，增強(qiáng)模型對(duì)數(shù)據(jù)的適應(yīng)性，對(duì)大部分問(wèn)題，均得到了較好的分類(lèi)結(jié)果?？偟膩?lái)說(shuō)該模型具有優(yōu)點(diǎn)：1）能適應(yīng)低維度數(shù)據(jù)和高維度數(shù)據(jù)；2）能適應(yīng)不同密度的樣本數(shù)據(jù)；3）對(duì)某些問(wèn)題如人臉識(shí)別，軌跡特征有較好效果 待改進(jìn)之處：1）不能解決過(guò)于復(fù)雜的數(shù)據(jù)集；2）后處理過(guò)程可以再更為優(yōu)化。

參考文獻(xiàn)：

[1] 劉向陽(yáng).多流形數(shù)據(jù)建模及其應(yīng)用[D].上海：上海交通大學(xué)，2011.

[2] 談超.增量流形學(xué)習(xí)方法研究[D].上海：同濟(jì)大學(xué)，2014.

[3] 申中華，潘永惠，王士同.有監(jiān)督的局部保留投影降維算法， 2008，21（2）：233-234.

[4] Liu G， Lin Z， Yan S， et al. Robust recovery of subspace structures by low-rank representation. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2013， 35（1）：171–184.

[5] Elhamifar E， Vidal R. Sparse subspace clustering： Algorithm， theory， and applications. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2013，35（11）：2765–2781.

[6] Wang Y， Jiang Y， Zhou Z. Spectral clustering on multiple manifolds. IEEE Transactions on Neural Networks， 22（7）：1149–1161， 2011.

[7] Cheng B， Liu G， Wang J， et al. Multi-task low rank affinity pursuit for image segmentation， ICCV， 2011.