基于等式約束的高維數(shù)據(jù)多分類問題的歸一化割改進(jìn)算法

徐止磊 盛夏 潘振寬

（青島大學(xué)計算機(jī)科學(xué)技術(shù)學(xué)院，山東 青島 266071）

1 概述

數(shù)據(jù)分類是數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、模式識別、計算機(jī)視覺等領(lǐng)域的基本問題之一。目標(biāo)是通過標(biāo)簽將一個特定的數(shù)據(jù)集分成不同的部分，且不存在重疊和空集。最近的研究表明利用圖的最小割算法來實(shí)現(xiàn)數(shù)據(jù)分類已被認(rèn)為是一種有效的方法，但必須克服平凡解問題。而這些問題的研究過程與聚類算法的發(fā)展密切相關(guān)[1]。

本文的主要研究是在離散非局部總變差框架下進(jìn)行的。在文獻(xiàn)[3] 中，研究人員構(gòu)建了最小割問題和總變差（TV,Total Variation）[4]問題之間的等價關(guān)系，這已被廣泛地應(yīng)用于半監(jiān)督數(shù)據(jù)分類問題[5]。在分類問題上，TV 的邊界比Tikhonov[6]更清晰。在文獻(xiàn)[7]中，Gilboa 和Osher 提出了用于圖像處理的非局部算子。最近，變分方法已成功用于圖分割問題[8]。在文獻(xiàn) [9] 中，Gilboa 和Osher 將非局部(NL,Non-Local) TV 擴(kuò)展到監(jiān)督分割，其中用戶使用小區(qū)域作為已知信息，并恢復(fù)目標(biāo)類別。在文獻(xiàn)[10，11]中，詳細(xì)介紹了NL-TV 的離散化和其他正則化項，這些工作為NL-TV 在分類和聚類中的應(yīng)用奠定了基礎(chǔ)。

為了避免(1)的中出現(xiàn)的平凡解的問題，研究人員提出了許多平衡切割方法，例如比例分割(RC, Ratio Cut)[3]、奇格分割(CC, Cheeger)[12]和歸一化割(NC, Normalized Cut)[13]。與CC和RC 不同，NC 是基于度的模型，廣泛用于道路提取[14]、聚類[15]和運(yùn)動檢測[16]。在文獻(xiàn)[17]中，研究者對NC 方法做了一個很好的近似法。并且在文獻(xiàn)[18]中，研究者對NC 的迭代計算方法進(jìn)行了優(yōu)化。上述研究工作為NC 方法的發(fā)展做出了不可磨滅的貢獻(xiàn)。多分類NC 模型的原始公式如下：

NC 具有一定程度的平衡約束能力，這是一個不爭的事實(shí)。但我們發(fā)現(xiàn)，當(dāng)數(shù)據(jù)本身的度不平衡時，我們將得到能量泛函極值問題中的平凡解。這個問題可以用一個簡單的極值問題來解釋。例如，當(dāng)a 加b 是一個常數(shù)時，如果想得到1/a+1/b 的最小值,a 和b 的值必須滿足條件：a=b。如果初始時a 不等于b，就會得到一個1/a+1/b 的平凡解。在文獻(xiàn)[20]中，在每類數(shù)據(jù)數(shù)量已知的情況下，通過等式約束的方式解決上述問題。與文獻(xiàn)[20]不同的是，我們使用等式度約束，而不是簡單的數(shù)字。

在本文中，基于上述思路，我們重新設(shè)計了NC 方法，并使用增廣拉格朗日乘子法（ALM, Augmented Lagrange Method）[21]來解決不平衡的二分類和多分類問題。而接下來，為了驗(yàn)證改進(jìn)后的方法是否能夠解決平凡解問題，我們用各種數(shù)據(jù)集做了大量的驗(yàn)證實(shí)驗(yàn)。實(shí)驗(yàn)包括二分類和多分類問題。多分類問題主要使用Mumford-Shah-Potts[13]模型的設(shè)計思路。最后，根據(jù)實(shí)驗(yàn)結(jié)果，本文提出的方法在解決二分類和多分類問題上具有最好的分類精度和約束能力。

本文在第2 節(jié)中首先提出了圖的非局部算子。第3 節(jié)主要闡述了算法設(shè)計并解決了能量泛函。在第4 節(jié)，進(jìn)行大量實(shí)驗(yàn)來驗(yàn)證本文提出的方法的效果。在第5 節(jié)中給出了相應(yīng)的結(jié)論。

2 圖的非局部總變差

在本節(jié)中，我們介紹了一些關(guān)于離散非局部算子[10]的基本定義，其用于無向加權(quán)圖上的數(shù)據(jù)二分類問題。為了處理這個問題，讓數(shù)據(jù)集V 被分為v1和v2，并引入一個二分類標(biāo)簽函數(shù)u（x）來劃分它們，即：

（10）和（11）的解決方案可以解決圖的二分類和多分類問題，但不能達(dá)到平衡的數(shù)據(jù)分類結(jié)果。為了達(dá)到平衡分類，我們將（10）和（11）用原始的NC 算法和改進(jìn)的NC 算法來實(shí)現(xiàn)，這有助于進(jìn)一步研究數(shù)據(jù)分類問題。

3 改進(jìn)的歸一化割模型

本節(jié)分為兩個小節(jié)，分別用來介紹二分類和多分類NC改進(jìn)模型。改進(jìn)后的模型用ALM方法求解，并給出了詳細(xì)的求解過程和算法來有助于更好地理解模型。

3.1 二分類問題的歸一化割改進(jìn)模型（MNC-T）

為了總結(jié)第3.1 節(jié)中介紹的算法，我們列出了算法1 的偽代碼：

?

3.2 多分類問題的歸一化割改進(jìn)模型(MNC-M)

通過3.1 的介紹，在本小節(jié)中，我們直接介紹改進(jìn)的多分類NC 模型。

對（24a）采用標(biāo)準(zhǔn)變分法，我們得到u 上的歐拉- 拉格朗日方程為

為了總結(jié)第3.2 節(jié)中介紹的算法，我們列出了算法2 的偽代碼：

?

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

在本節(jié)中，我們使用五個不同的數(shù)據(jù)集來分析第3 節(jié)中不同算法的性能。這些算法分別是無約束最小切割（UMC,Unconstrained Minimum Cut）、歸一化割（NC, Normalized Cut）和改進(jìn)的歸一化割（MNC, Modified Normalized Cut）。首先將介紹這些算法的參數(shù)，之后詳細(xì)分析了不同約束條件下的算法性能。我們設(shè)定程序的結(jié)束條件如下：

其中Ek+1是第（k+1）步的能量泛函，Ek是第k 步的對應(yīng)泛函。η 是一個小的正數(shù)，用于收斂。當(dāng)此條件得到滿足時，程序終止。

在實(shí)驗(yàn)中，基于一臺3.3GHz 的Inter Core i5 Quad 計算機(jī)上，我們使用了五個數(shù)據(jù)集：two-moons, three-moons,four-moons，手寫數(shù)字3&8 和手寫數(shù)字4&9。手寫數(shù)字是由紐約大學(xué)Courant 研究所生成的，由70000 個手寫數(shù)字（0-9）的圖像組成。Two-moons, three-moons 和four-moons 是合成數(shù)據(jù)集。我們使用9 個最近鄰來構(gòu)建單向圖，并基于第9 個最近鄰進(jìn)行歸一化，即k 最近鄰方法。對于保真項，我們在two-moons, three-moons, four-moons 中每類選擇50 個點(diǎn)，在手寫數(shù)字3 和8 以及手寫數(shù)字4 和9 中每類選擇300 個點(diǎn)。保真項的比例分別為5%、4.3%和4.35%。

我們將介紹不同算法中的參數(shù)。算法1 和算法2 中的參數(shù)是μ，μi=10，μ0，μ0i=10N，其中N 是數(shù)據(jù)點(diǎn)的數(shù)量，k 是類的數(shù)量。表1 中的數(shù)據(jù)是十組實(shí)驗(yàn)的平均值。

表1 不同方法在two-moons 數(shù)據(jù)集上的結(jié)果

在圖1 中，我們給出了初始化圖片和不同算法對two-moons 數(shù)據(jù)集的結(jié)果。這些方法的結(jié)果只是在邊界上略有不同，而這些微小的差異是很難描述的。所以我們用表1的數(shù)據(jù)來分析不同的方法。在表1 中，錯誤率最低的是MNC，錯誤率為1.25%。在這三種方法中，NC 和MNC 在正確率方面有良好的表現(xiàn)。關(guān)于不同方法的約束能力，1000 和1000 是二分類的數(shù)量，而最接近的解的數(shù)量是MNC 的結(jié)果。在表1 中，1001 和999 是MNC 的結(jié)果，它是這些方法中表現(xiàn)最好的。UMC 的性能比NC 和MNC 差一點(diǎn)。

圖1 不同方法在two-moons 數(shù)據(jù)集上的表現(xiàn)

在圖2 中，我們給出了手寫數(shù)字3&8 數(shù)據(jù)集的初始化圖片和不同方法的結(jié)果。我們用表2 的數(shù)據(jù)來分析不同的算法。在表2 中，錯誤率最低的是MNC，其錯誤率為1.3246%。關(guān)于不同方法的約束能力，7141 和6825 是二分類的數(shù)量，而最接近的解的數(shù)量是MNC 的結(jié)果。在表2 中，7138 和6828 是MNC 的結(jié)果，它是這些分類方法中表現(xiàn)最好的。但UMC 的錯誤率和約束力是最差的。與NC 相比，改進(jìn)后的模型在約束能力和分類正確率方面有更好的表現(xiàn)。

圖2 不同方法在手寫數(shù)字3&8 數(shù)據(jù)集上的表現(xiàn)

表2 不同方法在手寫數(shù)字3&8 數(shù)據(jù)集上的結(jié)果

在圖3 中，我們給出了手寫數(shù)字4 和9 數(shù)據(jù)集的解決方案圖片、初始化圖片和不同方法的結(jié)果。在表3 中，錯誤率最低的是MNC，其錯誤率為1.4802%。在表3 中，6822 和6960是MNC 的結(jié)果，它是這些分類方法中性能最好的。UMC 的約束能力比NC 差一點(diǎn)。但與MNC 相比，UMC 和NC 的約束能力明顯較差。

圖3 不同方法在手寫數(shù)字4&9 數(shù)據(jù)集上的表現(xiàn)

表3 不同方法在手寫數(shù)字4&9 數(shù)據(jù)集上的結(jié)果

表4 不同的保真度集合大小產(chǎn)生不同的錯誤率。（我們使用two-moons 數(shù)據(jù)集作為合成數(shù)據(jù)集的一個代表）。

表4 不同保真度集合大小的two-moons 數(shù)據(jù)集

為了比較保真度集大小對分類錯誤率的影響，我們選擇了兩個典型的數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)集。在表4 中，我們可以看到，當(dāng)保真度集規(guī)模很小時，UMC 和NC 不能實(shí)現(xiàn)正確的分類，而MNC 可以做得很好。這是MNC 的一個重要優(yōu)勢，即當(dāng)保真度集規(guī)模較小時，它可以準(zhǔn)確地實(shí)現(xiàn)分類。

為了進(jìn)一步研究改進(jìn)的NC 模型在多分類問題中的性能，我們選擇three-moons 數(shù)據(jù)集作為驗(yàn)證數(shù)據(jù)集。圖4 是使用three-moons 數(shù)據(jù)集的不同方法的結(jié)果。從表5 可以清楚地看出，MNC 在約束能力和分類精度上都有所提高。根據(jù)表中數(shù)據(jù)和上述分析，我們可以得出結(jié)論，MNC 在多分類問題中的優(yōu)勢與在二分類問題中的優(yōu)勢相同。

表5 不同方法在three-moons 數(shù)據(jù)集上的結(jié)果

圖4 不同方法在three-moons 數(shù)據(jù)集上的表現(xiàn)

5 結(jié)論

通過實(shí)驗(yàn)我們可以得出如下結(jié)論。在平衡約束能力方面，MNC 優(yōu)于NC 和UMC，并且在分類精度方面，MNC 的分類精度同樣更高。在保真度集規(guī)模很小的情況下，MNC 可以實(shí)現(xiàn)分類，并獲得較好的分類準(zhǔn)確率，而NC 和UMC 不能實(shí)現(xiàn)分類或分類錯誤率太高。在解決二分類和多分類問題的過程中都可以體現(xiàn)出上述MNC 的優(yōu)點(diǎn)。