分組加權t-SNE的手寫數(shù)字奇異類樣本聚類方法研究

杜 芬，王 彬，薛 潔，龍雨涵，劉 輝，熊 新

1(昆明理工大學 信息工程與自動化學院，昆明 650500)2(云南警官學院 信息網(wǎng)絡安全學院，昆明 650223)

1 引 言

隨著人機交互和圖像識別技術在生活中的廣泛應用，數(shù)字手寫體的識別問題得到了越來越深入的研究.由于不同文化、不同個體有不同的書寫習慣，即便是同一個人，由于書寫環(huán)境、書寫方式等外界因素的不同，都可能導致書寫結果的不一致，這使得每個手寫體數(shù)字所呈現(xiàn)的特征是多種多樣的.圖1是從MNIST數(shù)字手寫體數(shù)據(jù)庫中選取的手寫體數(shù)字樣本，可以看出雖然相同數(shù)字的主要特征相同，但不同數(shù)字手寫體樣本即便是代表相同數(shù)字，在外形上可能還是存在較大的差異，這類與標準數(shù)字寫法相差較大的手寫體數(shù)字樣本我們稱之為奇異樣本，奇異樣本的識別是手寫體數(shù)字識別中的難點問題.

為了得到更好的識別效果，近年來很多學者采用機器學習的方法對數(shù)字手寫體識別問題展開了深入研究，2012年Ciregan D等人將卷積神經(jīng)網(wǎng)絡(Convolutional Neural Network，CNN)的方法應用于美國郵政服務提供的手寫郵政編碼數(shù)字的識別[1].2013年Dan Z和Xu C提出用反向傳播(BackPropagation，BP)神經(jīng)網(wǎng)絡的方法對手寫體數(shù)字進行特征提取[2]. 2015年J Schmidhuber提出結合卷積神經(jīng)網(wǎng)絡(CNN)和支持向量機(Support Vector Machine，SVM)[3]的混合模型在MNIST數(shù)字數(shù)據(jù)庫中進行手寫體識別[4].周菲菲等采用改進的方向特征提取方法與BP神經(jīng)網(wǎng)絡分類器相結合，提高了數(shù)字手寫體的識別率，同時降低了拒識率[5].許潔等構建了一種基于稀疏保持典型相關分析的特征提取算法，在融合信息的同時還可以過濾冗余信息，提高了手寫體的識別精度[6].采用支持向量機、BP算法、卷積神經(jīng)網(wǎng)絡等方法展開的手寫體數(shù)字識別，其主要思想是通過構建機器學習模型和海量的訓練樣本數(shù)據(jù)，學習更有用的特征，從而提高手寫體數(shù)字預測的準確性.盡管以上研究通過對超大量樣本取得了較高的識別率，但由于奇異樣本在主要特征上的差異，使得此類樣本成為了影響樣本識別率的主要因素，因此本文專門針對提高這類奇異樣本的識別問題展開了研究.

由于上述數(shù)字手寫體奇異樣本的特征與常規(guī)數(shù)字手寫體的樣本差別較大，且時間復雜度高，因此使用機器學習方法難以準確的預測，因此本文擬采用降維的方法提取其主要特征并直接映射到二維空間內(nèi)，通過分類完成數(shù)字手寫體的識別.目前主流的線性高維降維方法如局部線性嵌入(Locally Linear Embedding，LLE)[7，8]、主成成分分析(Principal Component Analysis，PCA)[9，10]等已被應用于數(shù)字手寫體的識別中，1997年Hinton G E等人用PCA方法對手寫數(shù)字圖像流形的建模方法進行研究[11]；2006年Chang H和Yeung D Y對手寫體數(shù)字提出了魯棒局部線性嵌入(RLLE)的方法[12，13]；2015年Phan N H和Bui T T T提出了一種使用PCA、小波變換和神經(jīng)網(wǎng)絡組合的手寫字符識別算法[14].相對于線性降維算法，非線性降維方法能更好地發(fā)掘隱藏在高維數(shù)據(jù)中的流形分布[15]，其中t 分布隨機領域嵌入算法( t-distributed tochastic neighbor embedding，t-SNE)[16]是由G Hinton于2008年根據(jù)2002年Hinton和Rowei所提出的SNE算法[17]進行改進并提出的新算法，并應用于數(shù)字手寫體問題中.

圖1 不同人書寫的手寫體數(shù)字0-9Fig.1 Handwritten numerals 0-9 written by different people

t-SNE算法是用高斯核函數(shù)計算高維聯(lián)合概率，得到高維相似度距離，通過t-分布核函數(shù)定義低維空間內(nèi)嵌入樣本的相似度，并用梯度下降法的方法進行KL散度( kullback- leibler divergence，KL)的尋優(yōu)計算，從而找到原高維空間和嵌入低維空間內(nèi)盡可能相近的聯(lián)合概率分布.由于高維空間內(nèi)變量間的復雜非線性關系，這種單純使用歐式距離來衡量樣本相似性的方法并不能如實反映樣本在高維空間真實的分布情況.為了使樣本的主要特征能更好地保留下來，降低高維空間的信息在降維后的損失，可以對歐式距離進行分組加權處理.2013年Singha J等人對印度語言識別使用特征值進行加權歐幾里德距離分類進行研究[18]；2014年Liu H C等人使用模糊混合加權歐氏距離進行失效模式和效應的分析[19]；2017年詹威威等人提出了自適應加權t-SNE算法應用在腦網(wǎng)絡狀態(tài)觀測矩陣降維中[20].

文中以提高數(shù)字手寫體中的奇異樣本識別率為主要目標，提出了一種分組加權歐式距離的t-SNE算法，該算法通過分析手寫體數(shù)字在高維空間中分布緊密關系的不同，將其分組加權，并構建新的高斯核函數(shù)計算其高維聯(lián)合概率以及高維條件相似度距離，從而得到新的低維映射關系.基于MNIST公開測試數(shù)據(jù)庫中奇異樣本的實驗結果顯示，本文算法比t-SNE算法獲得了更好的聚類效果，且查全率(Recall Rate)平均可提高4%，查準率(Precision)平均可提高3.3%，為奇異樣本手寫體數(shù)字的識別問題提供了一種新的解決方案.

2 分組加權t-SNE手寫體數(shù)字降維算法

2.1 基本原理

t-SNE算法是將高維空間中樣本對之間的歐氏距離轉化為高維聯(lián)合條件概率，同時計算低維空間內(nèi)樣本對的聯(lián)合概率，并用KL散度構建目標函數(shù)，通過梯度下降法求取低維表達最優(yōu)解.

在傳統(tǒng)的t-SNE算法中，歐式距離表征兩個空間向量之間的累積差異，并沒有考慮對應單個元素之間差異的影響.如果直接將歐式距離用于特征向量之間的相似性度量，其度量精度存在較大的誤差，因為它忽略了特征向量中對應數(shù)字手寫體元素之間相似性的影響[21].本文擬采用一種分組加權的t-SNE(Grouped Weighted t-SNE，GW t-SNE)改進算法，該算法首先計算奇異樣本在高維空間內(nèi)的歐式距離，然后根據(jù)數(shù)據(jù)在高維中距離的不同遠近關系進行分組，不同的分組采用不同的加權系數(shù)，使距離近的更近，遠的更遠，不近不遠的保持不變.根據(jù)上述加權策略后，得到新的高維相似度距離度量方法并計算高維聯(lián)合概率，再計算其低維聯(lián)合概率，通過梯度下降的方法得到最小化的KL散度，并將其映射在二維空間內(nèi).

圖2 Fig.2

該算法的原理如圖2所示，其中圖2(a)為t-SNE的相似度計算方法，無論樣本之間相似程度多高，都是采用相同的歐式距離度量方法，該原理并不能反映出高維空間中樣本分布的遠近特征和相似關系的不同.而采用分組加權t-SNE算法的原理圖見圖2(b)，由于對不同的歐式距離樣本對采用了不同的加權處理，使得在高維空間內(nèi)距離較近的樣本對的相似程度變得更高，距離較遠的樣本對的相似程度變得更低，而不近不遠距離內(nèi)的樣本對相似程度保持不變，這使得其特征更加分明.

2.2 分組加權t-SNE降維算法的實現(xiàn)過程

本文算法首先計算出xi、xj在高維空間中的歐氏距離d(xi，xj)，并對這個歐式距離進行歸一化處理，根據(jù)其距離分布特征進行分組，按照不同的距離特征進行合適的權重選取，進行加權，從而得到加權歐氏距離 d*(xi，xj).在使用分組加權t-SNE算法降維時，將加權歐氏距離替換歐氏距離，計算xi、xj在高維空間中的聯(lián)合概率pij；得到y(tǒng)i、yj的低維空間聯(lián)合概率qij；并用KL散度構建目標函數(shù)，通過梯度下降法求取數(shù)字手寫體的低維表達最優(yōu)解.

傳統(tǒng)的歐氏距離計算表達式為：

(1)

在加權t-SNE算法中，通過高維目標函數(shù)的輸入，可以得到其高斯核函數(shù)d(xi，xj)，它為兩特征向量數(shù)據(jù)xi和xj之間的距離，即為歐氏距離.想進行加權，則先對高維樣本空間的歐氏距離做歸一化處理，得到矩陣m：

(2)

當dij=dmin時，m取最小值為0；當dij=dmax時，m取最大值為1.由式(1) 可以知道，加權的歐氏距離可以表示為：

(3)

其中，α表示每個距離分類的權重.

本文目前研究中將距離分為三類，近距離，較近距離和遠距離，并對其進行加權，使得近距離越近，遠距離越遠，中間距離不變，從而得到加權距離d*=α·d.此時樣本高維相似性條件概率pi|j和pj|i變?yōu)椋?/p>

(4)

其中，δi是以數(shù)字手寫體數(shù)據(jù)點xi為中心的高斯函數(shù)的矢量方差.

高維聯(lián)合概率pij為：

(5)

低維映射聯(lián)合概率為qij：

(6)

該方法最終優(yōu)化目標定義為：通過最小化高維樣本相似度P和低維樣本相似度Q之間的KL散度得到最優(yōu)結果.梯度下降的求導如公式(7)、公式(8)所示：

(7)

(8)

分組加權t-SNE算法流程圖見圖3，先設置總迭代次數(shù)M，另當前迭代次數(shù)為m，輸入N個1*784的手寫體數(shù)字樣本向量，按上文步驟完成映射并將結果輸出到低維空間內(nèi).

分組加權t-SNE算法運用加權歐氏距離來計算樣本之間的相似度，可以反映出不同樣本在高維空間內(nèi)分布的遠近程度，對高維降維數(shù)據(jù)中更好地保留其重要特征能起到更好地效果，由此使得高維相似度高的同類數(shù)據(jù)距離更近，相似度低的不同類數(shù)據(jù)距離更遠，可以使低維空間的映射結果更加如實地反應在高維空間內(nèi)的相似程度.

圖3 分組加權t-SNE算法的流程圖Fig.3 Flow chart of GW t-SNE algorithm

3 實驗及結果分析

3.1 手寫體數(shù)字奇異樣本庫的構建

根據(jù)MNIST手寫體庫，選擇n個特征特異難以識別的手寫體數(shù)字圖片組成實驗樣本庫，每一個圖片是28*28大小的bmp圖片，將其轉換為n*784的高維矩陣，并將這些灰度圖進行二值化處理，最終形成由0和1構成的n*784的矩陣，這就是要進行降維的高維數(shù)據(jù)，具體過程如圖4所示.

圖4 手寫體數(shù)字奇異樣本庫的構建方法Fig.4 Construction method of handwritten digital singular sample library

3.2 實驗設計

首先，對選擇的手寫體樣本使用t-SNE算法進行降維及可視化，圖5為2500個奇異樣本數(shù)據(jù)經(jīng)過t-SNE算法進行降維并映射到二維坐標的降維結果，從圖中可以看出相對于其它數(shù)字，由于數(shù)字4和數(shù)字9的外形相似，因此在映射過程中出現(xiàn)了較多的重合，數(shù)字3、5、8的分布也較為緊密，這給手寫字數(shù)字的識別帶來了困難，同時也是出現(xiàn)誤判的主要原因.因此下文將分組加權t-SNE的手寫體數(shù)字降維算法分別用于手寫體數(shù)字4、9以及手寫體3、5、8的降維和聚類，通過使用t-SNE和分組加權t-SNE算法后的降維效果來展開對比和分析.

圖5 奇異手寫體數(shù)字0-9進行t-SNE算法降維結果Fig.5 Singular handwritten numeral 0-9 performs t-SNE dimensionality reduction results

3.2.1 降維及可視化實驗

首先選擇手寫體數(shù)字4和9為一組，為了更深入的對比結果，根據(jù)樣本數(shù)的不同，分別構建了奇異樣本數(shù)為2000個和4000個的兩個樣本集.對兩個樣本集里不同的手寫體數(shù)字奇異樣本4和9分別使用t-SNE算法進行降維，再使用本文的分組加權t-SNE算法進行降維，并實現(xiàn)二維空間內(nèi)的可視化，通過二維可視化圖從聚類結果上進行對比分析.

接著在MNIST手寫體庫中選擇易混淆的奇異手寫體樣本3、5、8為實驗數(shù)據(jù)，同樣構建2000個和4000個的不同樣本集進行降維可視化映射.分別使用t-SNE算法和本文的分組加權t-SNE算法進行降維和可視化聚類.

需要說明的是由于t-SNE降維算法是將每個點通過梯度下降法進行低維映射，因為在這個過程中有隨機量，所以每一次的降維結果分布會有不同，其二維坐標沒有真實意義，只是用于代表映射后這些樣本的相似程度.

3.2.2 實驗結果的評價指標

除了可視化結果對比之外，本文還將通過查全率和查準率[22]兩個評價指標對實驗結果進行評價.

表1 分類結果混淆矩陣Table1 Confusion matrix of classification results

查準率P=發(fā)現(xiàn)的正確的映射個數(shù)/發(fā)現(xiàn)的所有映射個數(shù)，見公式(9)：

(9)

查全率R=發(fā)現(xiàn)的正確的映射個數(shù)/存在的映射數(shù)，如公式(10)：

(10)

為了能準確的對比其降維效果，選擇相同的數(shù)據(jù)樣本集，分別使用t-SNE算法和本文給出的分組加權t-SNE算法對其進行降維處理，使用相同的方法分別計算它的查全率和查準率.指標計算思想如下：首先分別計算出每個數(shù)字進行t-SNE降維后映射在二維空間上坐標的中心坐標，并以其中心坐標為圓心規(guī)定相同半徑進行畫圓，在此圓范圍內(nèi)，計算其評價指標.其次計算同一數(shù)據(jù)樣本進行加權t-SNE算法降維，再用同樣的方法計算映射后二維空間上的中心坐標，保持同組樣本中相同數(shù)字的半徑與t-SNE算法相同，并計算改進后算法的評價指標.

圖6 數(shù)字手寫體分組加權t-SNE降維算法實驗過程圖Fig.6 Digital handwritten GW t-SNE dimension reduction algorithm experimental process chart

由于查全率和查準率是一對矛盾的度量，一般來說，查全率越高查準率越低，查準率越高查全率越低.因此在進行實驗結果驗證時，要綜合分析兩個指標以確定降維方法的效果.需要說明的是在使用非線性降維的方法衡量樣本的聚類效果時，由于樣本映射到二維的點分布并不是固定的，分布也是不均勻的，計算查全率和查準率時并非直接固定其點的坐標，而是固定其相同的面積，因此在查全率和查準率上達不到均為90%的效果.此外由于本文的實驗數(shù)據(jù)是奇異樣本庫，因此與使用機器學習算法對標準手寫體數(shù)字樣本庫所得到的查全率與查準率的指標結果有所區(qū)別.圖6為數(shù)字手寫體分組加權t-SNE降維算法實驗過程圖.

3.3 實驗結果對比及分析

3.3.1 可視化的對比及分析

圖7是相同數(shù)字4、9在不同數(shù)據(jù)樣本中分別進行t-SNE和分組加權t-SNE算法中的降維可視化圖.

圖7 數(shù)字4、9進行t-SNE和分組加權t-SNE算法的降維可視化結果Fig.7 Dimensionality reduction visualization results of t-SNE and GW t-SNE algorithm are carried out in figures 4 and 9

圖7(a)為2000個4、9數(shù)據(jù)樣本集在t-SNE算法中的降維效果，通過圖可以清晰地看到，相同數(shù)字映射點之間間距大，圖7(b)經(jīng)過分組加權t-SNE算法降維后，發(fā)現(xiàn)相同數(shù)據(jù)點之間聯(lián)系更加緊密，而不同數(shù)據(jù)點之間相對分散.

圖7(c)是4000個數(shù)據(jù)樣本集在t-SNE算法中的降維效果，數(shù)字4、9在可視化圖中有交叉，說明數(shù)字4、9在此方法下無法清晰地分為兩類.但在圖7(d)的分組加權t-SNE算法可視化圖中，手寫體4、9雖仍有交叉部分，但可以清晰地分為兩類，在二維可視化圖中本文算法明顯優(yōu)于t-SNE算法.

圖8是數(shù)字3、5、8在不同數(shù)據(jù)樣本中分別進行t-SNE和分組加權t-SNE算法中的降維可視化圖.

圖8 數(shù)字3、5、8進行t-SNE和分組加權t-SNE算法的降維可視化結果Fig.8 Dimensionality reduction visualization results of t-SNE and GW t-SNE algorithm are carried out for numbers 3，5 and 8

圖8(a)為2000個3、5、8數(shù)據(jù)樣本集在t-SNE算法中的降維效果，通過圖可以清晰地看出，數(shù)字之間有明顯的交叉，且各個點分布稀疏.圖8(b)經(jīng)過分組加權t-SNE算法降維后，發(fā)現(xiàn)相同數(shù)據(jù)點之間聯(lián)系十分緊密，且沒有被其它數(shù)字完全阻隔的現(xiàn)象.

圖8(c)是4000個數(shù)據(jù)樣本集在t-SNE算法中的降維效果，數(shù)字3、5、8在可視化圖中相同數(shù)字分布沒有很緊密，交叉和聚類錯誤的點較多.但在圖8(d)的分組加權t-SNE算法可視化圖中，手寫體3、5、8相同部分聯(lián)系明顯更緊密，且沒有過多的交叉和重疊，因此在降維后二維可視化的聚類結果對比中，可以得出本文算法優(yōu)于t-SNE算法.

3.3.2 評價指標對比及分析

圖9是本文中選取的2000個樣本中每個數(shù)字的評價指標的對比，圖9中(a)、(c)為查全率的對比，(b)、(d)為查準率的對比，圖(a)、(b)為2000個奇異樣本數(shù)據(jù)集，圖(c)、(d)為4000個奇異樣本數(shù)據(jù)集.其中左側表示t-SNE算法計算出的評價指標，右側表示本文算法加權t-SNE計算出的評價指標.

從柱狀圖9中，明顯可以看出分組加權t-SNE算法在查全率和查準率中，比t-SNE算法均有提高.

通過以上幾組數(shù)據(jù)對比可以發(fā)現(xiàn)，二維圖中同類各點分布明顯聚攏，分界線相對明顯，評價指標的查全率和查準率也有所提高.由于t-SNE算法存在隨機變量，無法消除每次降維結果在二維空間內(nèi)的隨機映射現(xiàn)象，因此采取多次計算求平均值的方法，對查全率和查準率進行評價，評價結果表明，同組數(shù)據(jù)多次進行t-SNE和加權t-SNE算法計算后，每組查全率平均有了4%的提高，同時查準率平均也有了3.3%的提高.由于查全率和查準率是互相矛盾的一對變量，但在本文實驗中，兩個數(shù)字的評價指標同時都得到了提高，說明了分組加權t-SNE算法比t-SNE算法的性能更好，因而可以更好的保留數(shù)字手寫體在高維的主要特征.

圖9 4.9.3.5.8在t-SNE和分組加權t-SNE算法中的評價指標的對比Fig.9 Comparison of the evaluation indexes of 4.9.3.5.8 in t-SNE and GW t-SNE algorithms

4 結束語

本文以提高數(shù)字手寫體易混淆奇異樣本的識別率問題為目標，提出了一種分組加權t-SNE的手寫數(shù)字奇異類樣本聚類方法，通過對高維空間中不同歐式距離的樣本對采用不同的分組加權算法計算距離，再根據(jù)新的評價距離計算高維空間中各數(shù)據(jù)樣本對之間的聯(lián)合密度和條件相似度的方法，達到了使高維空間內(nèi)樣本相似度估計更加精確的效果，從而提高了手寫體數(shù)字庫中奇異樣本和易混淆樣本的識別度.

實驗結果顯示，在低維聚類可視化結果圖中，同類的明顯結合更緊密，不同類區(qū)分更明顯.并且使用分組加權的t-SNE算法在奇異手寫體數(shù)字樣本的查全率和查準率上均得到了提升.多次實驗結果統(tǒng)計顯示，加權t-SNE算法的查全率比t-SNE算法查全率平均提高了4%，查準率平均提高了3.3%.由此可見，本文方法對數(shù)字手寫體中奇異樣本在高維中主要特征的保留比普通t-SNE算法要好，因此可以得到更準確的降維效果并提高識別度，從而為手寫體數(shù)字的奇異樣本研究提供了理論和技術基礎.

盡管本文所述方法對奇異手寫體聚類有一定的改善效果，但是使用該方法將高維空間中的樣本映射到低維空間中的效果還有很大的提高空間，并且該方法中高維距離分組和權重的選擇對降維結果也都有一定的影響，下一步的工作也將針對這些因素展開深入研究和優(yōu)化.