基于E-t-SNE的混合屬性數據降維可視化方法

魏世超，李 歆，張宜弛，周曉鋒，李 帥

1.中國科學院 沈陽自動化研究所，沈陽110016

2.中國科學院大學，北京100049

3.中國科學院 網絡化控制系統重點實驗室，沈陽110016

4.中國科學院 機器人與智能制造創新研究院，沈陽110016

1 引言

現實生活中的大量數據通常包含可能對決策者有用的隱藏模式，但這些數據通常維度較高。例如，在入侵檢測、欺詐檢測、醫療分析領域[1]的數據，通常包含數百維。模式識別、圖像處理[2]領域的數據通常包含上千個特征。現實數據高維特性的存在帶來了計算成本增加、維度災難[3]等問題，不利于對數據的理解分析。解決數據高維特性問題的一種方法是降維，即尋求減少數據特征數量的技術。

眾多研究者提出了多種降維技術。一種是基于特征選擇的方法，根據一些標準選擇原始特征的子集[4]。Danubianu 等人[5]提出了一種應用相關性的篩選器來尋找相關特征的特征選擇方法。另一種降維技術是基于特征變換的方法，通過指定的變換函數將高維數據映射到低維空間。與特征選擇方法不同，生成的特征集不是原始特征的子集，而是根據原始特征新創建的。目前基于特征變換的降維方法主要有主成分分析（PCA）[6]、局部線性嵌入（LLE）[7]、等距映射（Isomap）[8]、局部切空間排列（LTSA）[9]、隨機近鄰嵌入（t-SNE）[10]、拉普拉斯特征映射（LE）[11]等。這些方法已經被應用于多個領域。Jamieson等人[12]將拉普拉斯特征映射和t-SNE應用于計算機提取的乳腺癌特征空間中，對醫學圖像映射進行分類和可視化檢查。Garces等人[13]運用t-SNE將不同風格的剪切畫可視化。Liu等人[14]采用LLE對腫瘤基因表達數據進行降維。

以往研究的不足之處在于研究都是在數值數據的背景下進行的。然而大多數真實世界的數據集同時包含分類屬性和數值屬性。例如，信用系統的數據包括年齡、年薪、儲蓄金額等數值屬性，以及教育背景、職業、婚姻狀況等分類屬性[15]。許多知識發現算法并不能處理混合類型數據。這些算法只分析數值或分類數據，并通過將一種類型的數據轉換為另一種類型的數據來解決這一缺陷。對于只處理數值型數據的算法，獨熱編碼（One-Hot Encoding）是一種普遍采用的方法，它將每個分類值轉換為二進制向量。然而這種方法有幾個顯著的缺點。首先，轉換后的數據增加了維度，計算成本也隨之增加，其次將分類屬性轉換為二進制向量，未考慮屬性間的相互關系，造成數據語義丟失，影響后續的分類聚類等算法的精度和性能。

本文主要針對t-SNE 算法不能處理混合數據的缺點，提出一種E-t-SNE 算法擴展其對混合屬性數據的處理能力。該算法引入信息熵的概念，考慮不同分類屬性值對距離計算過程中不同的貢獻程度，然后采用與數值屬性加權結合的方式，構造混合屬性數據的距離矩陣。為了驗證該算法處理混合屬性數據的有效性，采用k 近鄰(kNN,k-Nearest Neighbor）[16]分類算法驗證降維后數據的分類精度優于其他距離度量方案。此外，將混合屬性數據投影到低維空間進行可視化，證明了該算法對混合數據集的可視化展示更符合人們對數據的直觀理解。

2 相關定義

2.1 t分布隨機近鄰嵌入算法

高維數據降維可視化處理是將維數大于3 的數據轉換為2 維或者3 維，降維后的數據能夠在低維空間可視化展示并可以用于后續的機器學習算法。Hinton 及Roweis[17]于2002 年提出了一種隨機近鄰嵌入（SNE）降維方法。由于SNE 方法的價值方程優化困難并且存在低維數據擁擠問題，因此Maaten 及Hinton 于2008 年在SNE 的基礎上提出基于t 分布的隨機近鄰嵌入方法（t-SNE）。t-SNE的思想是在低維空間中采用重尾t分布構造一個概率分布，使其在高維空間中構造的概率分布相似。在概率分布中，相似的數據點被選中的概率較高，不相似的數據點被選中的概率較低。高維空間中，點j相對于點i的概率分布定義為：

其中，σ 是以xi為中心的高斯函數的方差，由二進制搜索算法確定。設高維空間中的聯合概率pij為對稱條件概率，即

其中，n是數據點的個數。對于高維數據xi和xj在低維空間中的映射yi和yj，采用自由度為1 的t 分布表示低維聯合概率分布，即

為保證低維空間映射點之間的聯合概率分布qij較好地模擬高維空間數據點之間的聯合概率分布pij，采用梯度下降法最小化所有數據點的KL 散度（Kullback-Leibler divergences）得到低維空間最佳模擬點。目標函數C 和梯度下降法優化的定義如下：

為了加速優化過程，避免陷入較差的局部最小值，在梯度中加入一個動量項：

2.2 獨熱編碼

獨熱編碼（One-Hot Encoding）是機器學習算法中處理分類屬性數據的常用方法。由于很多現實世界中的數據集不總是連續的數值型數據，在應用回歸、分類、聚類等機器學習算法時，數據集中包含的分類型數據無法直接進行距離和相似度計算。獨熱編碼將具有k 個不同值域的分類屬性轉換為一組k 個二進制屬性，每個二進制屬性都對應于k個分類值中的一個。

然而這種對分類屬性數據的處理方式缺點顯著。首先轉換后的數據大大增加了數據維度，計算成本增加。其次，將分類屬性轉換為二進制向量，未考慮屬性間的相互關系，造成數據語義丟失，影響后續的分類聚類等算法的精度和性能。

2.3 k 近鄰分類算法

k 近鄰(kNN,k-Nearest Neighbor）分類算法是最常用的分類算法之一，被應用于數據挖掘、模式識別等多個領域。算法采用k 個最近鄰居的類標簽來確定未知點的類標簽，即k 個最近鄰文本中大多數屬于某個類別，則樣本也屬于這個類別，故k 值的選取至關重要。如果k 值偏小，會提高噪聲的干擾；如果k 值偏大，并且測試樣本中屬于訓練集中包含數據較少的類，則會增加噪聲，降低分類準確性。

3 E-t-SNE混合屬性數據降維可視化方法

觀察式（1）可以發現，t-SNE算法將高維數據點間的歐式距離轉換為表示相似性的條件概率[18]，常用的空間距離計算方法歐式距離并不適合處理分類型數據。本文采用一種新的距離計算方法，分別構建數值型數據的距離矩陣和分類型數據距離矩陣，然后將兩個矩陣融合得到混合數據的距離矩陣，輸入t-SNE 算法進行降維并可視化。

3.1 距離矩陣度量

關于混合屬性數據的公式符號描述如下[19]：X={ x1, x2,…,xn} 表示N 個混合數據對象的數據集，對于 每 一 個 xi(1 ≤i ≤n),混 合 型 數 據 集 xi代 表M(M=Mn+Mc)個屬性其中表示Mn個數值型數據，表示Mc個分類型數據。表示數值部分的第k 個屬性，表示分類部分的第k 個屬性。第k 列分類屬性的定義域表示為表示分類屬性的個數。

3.1.1 數值型數據的距離矩陣

D(n)是一個n×n(n=N)的矩陣，對角線上元素全是0，表示數據點自身與自身的距離，表示和之間的距離，

3.1.2 分類型數據的距離矩陣

傳統的定義分類屬性數據之間距離的方式是建立在每個分類屬性權重相同的情況下，數據相同距離為0，不同距離為1。本文表示為公式如下：

這種定義分類屬性數據的方法忽略了不同分布的不同屬性值對距離計算時貢獻度的差異。因此，為了考慮貢獻度的差異，為分類屬性加入權重wk，公式（9）可修改為：

顯然wk是分類屬性的權重，它表示對分類屬性距離計算時的貢獻程度。這里

然后討論每個分類屬性權重wk的計算方式，本文引入信息熵的概念計算權重[20]。由信息熵的性質可知，信息熵可以作為一個系統復雜程度的度量，如果系統越復雜，出現不同情況的種類越多，那么他的信息熵就越大，反之一個系統越簡單，出現情況種類越少，信息熵越小。同理，如果數據集中分類型數據的定義域中ak,t種類越多，分布越不均勻，則的信息熵越大，即對距離的計算貢獻程度越高，權重越大。因此的信息熵可表示為：

這里p(ak,t)是分類屬性中ak,t的概率：

其中，rk為中分類值的數量。因此，數據集中分類屬性對距離計算時貢獻程度可用權重wk表示：

將式（14）代入式（10）中，得到分類屬性數據的距離計算公式：

2.依規處理國際稅收協定與國內稅法的對接關系。雙邊或多邊稅收協定屬于國際法的范疇。雙邊稅收協定是由締約國雙方政府談判后達成的，經過各自國家的立法程序后生效的，因此對于締約國政府具有法律上的約束力。

D(c)是一個n×n(n=N)的矩陣，對角線上元素全是0，表示數據點自身與自身的距離表示和之間的距離，

3.1.3 混合型數據的距離矩陣

根據以上內容可以發現，對于混合型數據集的距離計算采用數值型和分類型分別計算的方法。數值型數據點直接采用歐式距離進行度量，分類型數據點引入信息熵的概念，將不同分類屬性對距離計算的貢獻程度量化成權重，用權重與分類值之間距離相乘的方法構造出分類屬性數據點之間的距離。

最后將計算出來的數值型數據點之間的距離與分類型數據點之間的距離相加，得到混合屬性數據點之間的距離dij(xi,xj)，表示為：

3.2 算法實現

E-t-SNE算法流程如圖1所示。

圖1 E-t-SNE算法流程

E-t-SNE 算法描述如下所示，其中迭代次數T 太小容易導致優化過程不完全，太大增加算法執行時間，本文設置為1 000；較大的動量項可以使優化過程避免陷入較差的局部最優，根據經驗，當迭代次數T ＜250 時，動量項α(T)=0.5，當T ≥250時，α(T)=0.8；學習率η初值為100，每次迭代結束根據自適應學習率機制進行更新；維數m 設置為2[21]。

算法1E-t-SNE算法

（1）分別根據式（7）和式（15）構建數值型數據距離矩陣D(n)和分類型數據距離矩陣D(c)；根據公式（17）構建混合數據距離矩陣D；

（2）分別根據式（1）和（2）計算pj|i和pij；

（3）初始解Y(0)={ y1, y2,…,yn} 采樣與正態分N(0,10-4I)

（4）for t=1 to T

①根據式（3）計算qij；

②根據式（5）計算梯度；

③根據式（6）計算Y(t)；

（5）得到低維數據表示Y(T)={ y1, y2,…,yn}。

輸出：混合數據集在低維空間的數據表示。

4 實驗分析

4.1 實驗數據集和評價方法

為了驗證E-t-SNE 算法的有效性，本文選用UCI 機器學習知識庫中的4個真實混合數據集：Credit Approval、Australian Credit Approval、Heart、Adult。數據集Credit Approval 包含2 個類，6 個數值屬性和8 個分類屬性，共653條數據；數據集Australian Credit Approval包含2個類，6個數值屬性和9個分類屬性，共690條數據；數據集Heart 包含2 個類，7 個數值屬性和6 個分類屬性，共270條數據；數據集Adult包含2個類，3個數值屬性和3個分類屬性，共1 100 條數據。表1 列出了4 個數據集數據量，數值屬性個數，分類屬性個數以及類的個數。

表1 混合型數據集的詳細信息

為了評價E-t-SNE 算法的性能，本文使用了4 個真實混合數據集。由于不知道數據在高維空間中的結構，所以無法通過對比高維和低維空間投影映射的方法來直接的評估性能。E-t-SNE算法本身是一種混合數據降維可視化算法，按照理論，降維以后的數據應該保留了原始高維空間中數據集的分類特征。因此，可以對混合數據集降維之后的數據進行評價，驗證此降維可視化算法對后續數據分析的影響。本文采用k 近鄰(kNN)分類算法，將降維以后的數據中80%用做訓練集，20%做測試集，通過對測試數據分類準確度的比較，對本文E-t-SNE 算法和獨熱編碼方式、余弦距離度量方法進行了評價。

4.2 實驗結果分析

為驗證E-t-SNE 算法的有效性，本文采用多種距離計算方法構建混合數據集的距離矩陣，并與本文算法對比。其中獨熱編碼方式是將分類屬性轉換為k 個二進制屬性構建距離矩陣；余弦距離方法是將混合屬性數據轉換為向量，通過計算向量間夾角的余弦值構建距離矩陣。原始的t-SNE 算法不能直接處理混合數據集，但是本文將混合數據集不做處理直接輸入t-SNE 算法，作為對比降維以后分類準確率的基準，以凸顯本文算法的有效性。

文獻[10]指出，t-SNE 算法的性能對困惑度Perp 變化較為敏感。根據Perp 的定義，若Perp 太小，則低維嵌入點孤立，看不到低維空間中的聚簇效果；若Perp太大，則所有低維嵌入點聚集成一個簇，無法辨析數據的真實結構。因此，本文以代價函數KL(P||Q)的值在0.05～0.35之間為依據，經過多次實驗，對4個混合數據集Credit Approval、Australian Credit Approval、Heart、Adult 的困惑度Perp分別設定為50、50、20、100。

文獻[16]指出，kNN分類算法中k 的選擇至關重要，為避免k 值選取不當對實驗結果準確新造成的干擾，本文選取多個k 值作為參數，每個k 值分別進行5次實驗取平均值。

從表2可以看出，k 取不同值時，算法t-SNE、余弦距離、One-Hot 編碼、E-t-SNE 在Credit Approval 數據集上的分類準確率分別是0.682 0、0.746 9、0.814 2、0.861 3。通過比較可以發現，E-t-SNE 比其他3 種算法在準確率上分別提高了17.93%、11.44%、4.71%。因此E-t-SNE 算法性能更好。

表2 Credit Approval數據集實驗結果

為了更加直觀地反應降維以后的數據分布情況，證明E-t-SNE 算法在可視化方面的優勢，本文結合低維空間可視化視圖作為一種最直觀的評價方法。

圖2 展示了Credit Approval 數據集在低維空間中的映射視圖（類標簽只用于染色，不同的顏色表示不同的類）。其中（a）采用獨熱編碼方式計算混合數據集數據點之間的距離降維后得到的視圖；（b）采用余弦距離方式計算混合數據集數據點之間的距離降維后得到的視圖；圖（c）采用E-t-SNE算法處理混合數據集降維后得到的視圖。通過觀察圖2 可以發現，（a）和（b）中兩個類的數據點混淆在一起，沒有很好的分離，在低維空間中不能明顯地發現數據集的類別情況；而（c）則可以直觀的發現數據集中存在兩個類。

圖2 Credit Approval數據集二維空間可視化

從表3 可以看出，k 取不同值時，算法t-SNE、余弦距離、One-Hot編碼、E-t-SNE在Australian Credit Approval數據集上的分類準確率分別是0.702 8、0.717 5、0.800 6、0.844 2。通過比較可以發現，E-t-SNE 比其他三種算法在準確率上分別提高了14.14%、12.67%、4.36%。因此E-t-SNE算法性能更好。

表3 Australian Credit Approval數據集實驗結果

圖3 展示了Australian Credit Approval 數據集在低維空間中的映射視圖。其中（a）采用獨熱編碼方式計算混合數據集數據點之間的距離降維后得到的視圖；（b）采用余弦距離方式計算混合數據集數據點之間的距離降維后得到的視圖；圖（c）采用E-t-SNE算法處理混合數據集降維后得到的視圖。通過觀察圖3 可以發現，（a）中兩個類的數據點混淆在一起；（b）中數據點分布松散無明顯規律；（c）中兩個類別區分明顯。

圖3 Australian Credit Approval數據集二維空間可視化

從表4可以看出，k 取不同值時，算法t-SNE、余弦距離、One-Hot 編碼、E-t-SNE 在Heart 數據集上的分類準確率分別是0.678 6、0.689 6、0.756 0、0.795 8。通過比較可以發現，E-t-SNE 比其他兩種算法在準確率上分別提高了11.72%、10.62%、7.74%。因此E-t-SNE算法性能更好。

表4 Heart數據集實驗結果

圖4 展示了Heart 數據集在低維空間中的映射視圖。其中（a）采用獨熱編碼方式計算混合數據集數據點之間的距離降維后得到的視圖；（b）采用余弦距離方式計算混合數據集數據點之間的距離降維后得到的視圖；圖（c）采用E-t-SNE 算法處理混合數據集降維后得到的視圖。通過觀察圖4 可以發現，（a）中兩個類的數據點分散，很難發現數據集中的隱藏模式。（b）中可以大體發現有兩個類別，但類內數據點沒有很好地區分；（c）中兩個類之間區分明顯。

圖4 Heart數據集二維空間可視化視圖

從表5可以看出，k 取不同值時，算法t-SNE、余弦距離、One-Hot 編碼、E-t-SNE 在Adult 數據集上的分類準確率分別是0.737 0、0.740 8、0.753 4、0.791 0。通過比較可以發現，E-t-SNE 比其他兩種算法在準確率上分別提高了5.40%、4.93%、3.76%。因此E-t-SNE 算法性能更好。

表5 Adult數據集實驗結果

圖5 展示了Adult 數據集在低維空間中的映射視圖。其中（a）采用獨熱編碼方式計算混合數據集數據點之間的距離降維后得到的視圖；（b）采用余弦距離方式計算混合數據集數據點之間的距離降維后得到的視圖；圖（c）采用E-t-SNE 算法處理混合數據集降維后得到的視圖。通過觀察圖5 可以發現，（a）、（b）兩個類的數據點混淆在一起，不能很好地區分類與類之間的關系。（c）中兩個類之間雖有混淆重疊，但類間區分明顯。

圖5 Adult數據集二維空間可視化

圖6 匯總了E-t-SNE 算法和對比算法在4 個UCI 數據集上的分類準確度。由圖6 可以看出，將選取的4 個混合屬性數據集用不同的距離度量方法降維到二維平面后，用kNN 做分類處理，E-t-SNE 算法具有較高的分類準確性。

圖6 E-t-SNE算法與其他算法分類準確率對比

以上實驗證明了E-t-SNE 算法在對混合數據降維方面有更大的優勢。由于引入了信息熵概念，考慮了不同的分類型屬性對距離計算時的不同貢獻度，使得降維以后的數據更多地保留了數據在高維空間的結構分布，使其在后續的分類算法中獲得了更高的準確度。

5 結束語

本文總結了現有的降維可視化算法的原理及特點，指出它們不能有效地處理混合屬性數據的缺點。在t-SNE 算法的基礎上提出了一種擴展的E-t-SNE 算法，使其能處理混合型數據集。該方法引入信息熵的概念度量混合屬性數據點之間的距離，相比于傳統的將分類型數據轉換成0/1的獨熱編碼方式和將分類型數據轉換成向量的余弦距離計算方法，該方法既能處理混合型數據，又不增加數據維度，并且將不同類標簽的數據映射到低維空間，有利于更好地理解和發現高維空間數據的結構。通過實驗發現，經過E-t-SNE 降維后的混合類型數據集，在后續的數據分析算法中表現出比獨熱編碼方式更高的準確率，證明了E-t-SNE算法的有效性。

E-t-SNE算法能有效地對混合類型數據集進行降維可視化操作。但并沒有考慮算法的復雜度和執行時間問題。當數據量太大時，復雜的矩陣運算會占用大量內存和消耗大量的時間。在后續的研究工作中，將考慮算法的復雜度問題，優化求解過程，縮短求解時間。