陳海輝 周向東 施伯樂

(復(fù)旦大學(xué)計算機科學(xué)技術(shù)學(xué)院 上海 200433)

基于稀疏正則化的高維數(shù)據(jù)可視化分析技術(shù)

陳海輝 周向東 施伯樂

(復(fù)旦大學(xué)計算機科學(xué)技術(shù)學(xué)院 上海 200433)

高維數(shù)據(jù)可視化分析是數(shù)據(jù)分析與可視化領(lǐng)域的研究熱點，傳統(tǒng)的降維方法得到的低維空間往往難以解釋，不利于人們對高維數(shù)據(jù)的可視化分析與探索。提出一種新的可視化解釋器(Explainer)方法，將L1稀疏正則化特征選取引入到高維數(shù)據(jù)的可視化處理過程中，建立起高層語義標簽與少量的關(guān)鍵特征之間的聯(lián)系。通過可視化設(shè)計與實驗驗證了該方法可以有效改善高維數(shù)據(jù)的可視化分析性能。

高維數(shù)據(jù) 特征選取 稀疏學(xué)習(xí) 可視化分析 降維 投影

0 引 言

高維數(shù)據(jù)可視化分析將高維數(shù)據(jù)處理與可視化呈現(xiàn)結(jié)合，如運用數(shù)據(jù)降維技術(shù)，結(jié)合視覺編碼手段進行數(shù)據(jù)分析與探索。近年來高維數(shù)據(jù)可視化分析技術(shù)在實際應(yīng)用中顯示出越來越重要的價值。

高維數(shù)據(jù)可視化分析中常用的數(shù)據(jù)降維方法，如主成分分析法[1]等將N維高維數(shù)據(jù)點投射到新生成的K維空間中(K<

本文在解釋器技術(shù)的基礎(chǔ)上，提出一種新的針對層次化高維數(shù)據(jù)可視化分析的方法。我們使用基于L1稀疏正則化的層次分類器進行模型訓(xùn)練，實現(xiàn)數(shù)據(jù)特征的自動選取(即降維處理)。通過參數(shù)調(diào)節(jié)模型的稀疏性，可以得到不同的特征組合，以及相應(yīng)的解釋器(投影函數(shù))，從而建立起多方位的從高維特征到低維特征、低維特征到高層語義之間的聯(lián)系，克服了直接從高維特征到語義空間映射的可視化困難。在兩個通用的可視化數(shù)據(jù)集上進行了可視化設(shè)計與實驗，驗證了本文提出的方法可以有效改進傳統(tǒng)解釋器投影技術(shù)的可視化分析性能。特別是在平行坐標圖和散點圖等常用的高維數(shù)據(jù)可視化技術(shù)中，本文提出的方法表現(xiàn)出更好的數(shù)據(jù)分離能力，改進了高維數(shù)據(jù)可視化分析的效果

1 相關(guān)工作

高維數(shù)據(jù)可視化分析通常由數(shù)據(jù)降維算法和可視化編碼方法組合而成。投影追蹤算法[2]將高維數(shù)據(jù)投影到低維子空間上，并通過極小化投影指標函數(shù)，尋找出反映原高維數(shù)據(jù)的結(jié)構(gòu)特征的投影，提高低維空間上數(shù)據(jù)可視化分析的性能。文獻[3-4]對投影追蹤算法進行改進，將投影指標函數(shù)應(yīng)用到特征變量上，并運用交互式可視化方法從不同視角進行數(shù)據(jù)分析與探索。文獻[5]將投影追蹤技術(shù)應(yīng)用到散點圖矩陣可視化上，使得在單一空間內(nèi)可以展示更多的散點圖。上述工作將高維數(shù)據(jù)變換投影到低維空間的過程中，往往缺乏與用戶知識的結(jié)合，基本上可以視為非監(jiān)督學(xué)習(xí)類型的高維數(shù)據(jù)可視化技術(shù)。

近年來，將用戶知識融入高維數(shù)據(jù)的可視化分析的研究越來越多，文獻[6-7]中用戶驅(qū)動式的降維算法如PPCA(Probabilistic PCA)、 GTM(Generative Topographic Mapping)根據(jù)用戶定義的視角和條件，調(diào)節(jié)參數(shù)產(chǎn)生各種投影函數(shù)，方便用戶進行問題驅(qū)動的數(shù)據(jù)探索與分析。文獻[8]提出LAMP算法，通過引入正交投影理論，將用戶知識引入到投影函數(shù)學(xué)習(xí)的過程中。LAMP算法有效地將兩個不相關(guān)的高維數(shù)據(jù)集在同一可視化平面展示，用以探索不同來源數(shù)據(jù)之間的潛在聯(lián)系。這些投影函數(shù)往往都是用來組織數(shù)據(jù)的分布，并不能解釋特征與變量之間的聯(lián)系。

文獻[9]中通過為高維數(shù)據(jù)打上標簽，并學(xué)習(xí)得到相應(yīng)的投影函數(shù)，用以解釋特征與變量之間的聯(lián)系。文獻[10]在高維數(shù)據(jù)處理過程中使用sugiyama算法減少折線稠密交叉情況，用以解決高維數(shù)據(jù)平行坐標圖可視化時常見折線聚集的問題。文獻[11]中提出的解釋器技術(shù)采用監(jiān)督學(xué)習(xí)方法對有關(guān)分類器進行學(xué)習(xí)，把獲得的線性分類函數(shù)作為從特征空間到語義空間的投影工具(也稱為解釋器)。通過對待分析數(shù)據(jù)進行投影(或解釋)，實現(xiàn)數(shù)據(jù)的分析與理解。但是對高維數(shù)據(jù)的分析，仍然是從高維特征空間到語義空間的映射，無法克服高維數(shù)據(jù)本身引起的“維災(zāi)問題”。

2 模 型

2.1 解釋器技術(shù)

解釋器技術(shù)[11]利用用戶知識來提高數(shù)據(jù)可視化分析的性能。即根據(jù)用戶對數(shù)據(jù)進行語義標注，采用有監(jiān)督學(xué)習(xí)技術(shù)，對線性分類器進行訓(xùn)練：

f(x)=w·x+b

(1)

式(1)中線性分類器f(x)被看作連接高層語義與底層特征之間的投影函數(shù)，稱為解釋器。

根據(jù)用戶知識得到的解釋器可以用來重新組織數(shù)據(jù)，并與可視化編碼相結(jié)合實現(xiàn)數(shù)據(jù)的可視化分析和探索。在文獻[11]的基礎(chǔ)上，文獻[12]引入解釋器技術(shù)學(xué)習(xí)包含用戶知識的投影函數(shù)，應(yīng)用到氣候模型的可視化分析領(lǐng)域。文獻[13]把解釋器作為交互式投影方法，隨著用戶視角改變，交互式探索高維數(shù)據(jù)在用戶語義空間的分布特性。

但是，利用傳統(tǒng)的解釋器技術(shù)對高維數(shù)據(jù)的分析，仍然面臨高維數(shù)引起的“維災(zāi)問題”，應(yīng)用到平行坐標圖，散點圖等常見可視化方法中，不同類別數(shù)據(jù)之間遮擋情況嚴重，耦合與分離效果較差，影響可視化效果。因此，本文基于L1稀疏正則化分類技術(shù)，提出一種對高維層次數(shù)據(jù)可視化分析的新方法，即通過數(shù)據(jù)特征自動選取建立起低維特征空間與語義空間的聯(lián)系，使高維數(shù)據(jù)可視化分析獲得更好的效果。

2.2 基于L1正則化的層次分類器模型

圖1 城市的層次類標簽結(jié)構(gòu)

層次化數(shù)據(jù)集是一種常見的數(shù)據(jù)分析對象，圖1是關(guān)于世界各國城市數(shù)據(jù)集的語義標簽層次結(jié)構(gòu)[11，16]。層次數(shù)據(jù)集一般使用樹結(jié)構(gòu)進行描述：令A(yù)(i)和S(i)分別代表標簽結(jié)構(gòu)樹上節(jié)點i的祖先節(jié)點和兄弟節(jié)點集合，并且令A(yù)+(i)=A(i)∪i。令X∈Rd為輸入數(shù)據(jù)集的特征空間，維數(shù)是d。Y={1,2,…，m}為層次樹上除了根節(jié)點0以的其他節(jié)點對應(yīng)的標簽編號。每一個層次標簽對應(yīng)唯一的編號。

本文采取的對高維層次數(shù)據(jù)可視化分析方法主要包括：基于L1正則化的層次分類器模型的訓(xùn)練；可視化分析設(shè)計兩個部分。本節(jié)主要介紹層次分類技術(shù)；可視化設(shè)計在實驗部分詳細介紹。

(2)

式(2)中R(w)是正則化項，用以防止訓(xùn)練得到的模型過擬合。{ξk},?k∈{1,2，…,N}是損失因子中的松弛變量。參數(shù)C1用以控制正則化項和損失項的平衡。

(3)

式(3)中R(w)采用混合的正則化方法[15]，第一項使用L1稀疏化方法對模型的參數(shù)進行約束，這樣既能增加層次分類的判別區(qū)分能力，又能夠同時學(xué)習(xí)出一組稀疏的真正有貢獻的特征組合。在后續(xù)的層次數(shù)據(jù)可視化分析和探索中，幫助學(xué)習(xí)語義標簽與對應(yīng)特征組合之間的關(guān)聯(lián)。C2可以用來控制稀疏化的程度。第二項和第三項是層次分類的正交正則化約束，使得不同層次和兄弟節(jié)點分類器使用各自特有的特征組合，提高分類性能。關(guān)于模型的參數(shù)估計，本文采用文獻[14-15]給出的正則對偶式平均RDA(Regularized Dual Averaging)方法。

3 可視化實驗

3.1 可視化分析案例

本文以城市數(shù)據(jù)集[16]和UCI汽車數(shù)據(jù)集[17]為案例進行可視化探索的實驗與對比分析。城市數(shù)據(jù)集包含4層數(shù)據(jù):城市、國家、地區(qū)和大洲，數(shù)據(jù)維度45維。汽車數(shù)據(jù)集包含2層數(shù)據(jù)：汽車類型和汽車品牌，數(shù)據(jù)維度26維。

可視化實驗分為兩部分：

1) 本文設(shè)計的解釋器-特征選擇圖幫助可視化探索數(shù)據(jù)語義標簽與顯著特征的關(guān)系。

2) 常見高維數(shù)據(jù)分析的可視化效果對比：在平行坐標圖和散點圖對比使用本文方法和解釋器方法的可視化效果。

3.2 解釋器-特征選擇圖

本文設(shè)計了如圖2所示的解釋器-特征選擇圖。該圖形展示了不同的北美洲投影函數(shù)與相應(yīng)的特征組合之間的關(guān)系。通過調(diào)節(jié)L1懲罰項參數(shù)，可以得到6組北美洲投影函數(shù)和與之對應(yīng)的特征組合。用平行坐標圖中的不同垂直軸線，代表了不同的北美洲投影函數(shù)。北美洲的城市(圖中深色折線)與非北美洲城市(圖中淺色折線)分別用6個投影函數(shù)在平行坐標圖上作投影映射。

圖2 解釋器-特征選擇圖

圖2以熱力圖的形式展示投影函數(shù)與其對應(yīng)的顯著特征。每一列方格代表不同的特征組合，與上方的軸線(即投影函數(shù))對應(yīng)。每一行代表一種特征。熱力圖中方格顏色深淺代表該特征的顯著性。熱力圖右邊用直方圖統(tǒng)計每一種特征的平均顯著性。

圖2中每條軸線上深色折線基本都在淺色折線的上方。在北美洲投影函數(shù)下，北美洲的城市對比于非北美軸的城市，往往具有更高的投影值，證明了本文將L1稀疏化方法引入分類器學(xué)習(xí)的有效性。

通過解釋器-特征選擇圖，發(fā)現(xiàn)北美洲城市中最顯著的特征，主要是醫(yī)療衛(wèi)生水平、犯罪率等。這樣就可以發(fā)現(xiàn)高層語義標簽與特征之間的潛在關(guān)系，用戶可以重點觀察這些特征進一步分析數(shù)據(jù)。

表1為將本文方法應(yīng)到城市數(shù)據(jù)集，根據(jù)解釋器-特征選擇圖分析得出的各個大洲的最具有顯著性的特征組合。根據(jù)表1中得到的所有8個特征，繪制出圖3所示城市數(shù)據(jù)集的平行坐標圖?？梢园l(fā)現(xiàn)，非洲城市(深線)和亞洲城市(淺色)在各個特征上的表現(xiàn)的模式具有顯著的區(qū)分度和離散度，可以非常方便地對不同城市(折線)進行觀測與分析。原始45維的數(shù)據(jù)集在這8個維度就可以得到很顯著的區(qū)分性，證明了解釋器-特征選擇圖可以方便高維數(shù)據(jù)的可視化分析。

表1 大洲的特征組合

表2為將本文方法應(yīng)到汽車數(shù)據(jù)集，根據(jù)解釋器-特征選擇圖分析得出的各個汽車類型的最具有顯著性的特征組合。

圖3 城市數(shù)據(jù)集的平行坐標圖

表2 汽車類型的特征組合

3.3 改進的解釋器投影效果

本節(jié)對比本文方法與解釋器方法投影效果，分別應(yīng)用L1稀疏正則化方法和解釋器方法得到“非洲”語義標簽對應(yīng)的投影函數(shù)。經(jīng)過投影變換，將城市數(shù)據(jù)投影到非洲軸上。

圖4 本文方法與解釋器方法投影效果對比

如圖4所示，在非洲解釋器上投影值排名前10%的城市的分布，可以發(fā)現(xiàn)本文方法中非洲城市主要分布在非洲軸的上部分，不是非洲的城市主要分布在軸下方，而解釋器方法中非洲城市分布在非洲軸的中上部分，明顯本文方法投影效果比解釋器方法更好，對于提高投影的準確性具有顯著作用。

3.4 改進的平行坐標圖效果

如圖5所示，同樣以非洲與亞洲兩個軸線為例，分別應(yīng)用本文方法和解釋器方法作平行坐標圖。通過對數(shù)據(jù)作篩選，取在非洲軸投影值最高的10%的數(shù)據(jù)。可以發(fā)現(xiàn)右圖中，數(shù)據(jù)折線很明顯聚集在一起(b)，并不利于發(fā)現(xiàn)這一系列數(shù)據(jù)在其他軸線上的分布特性。而我們使用稀疏化方法(a)中，數(shù)據(jù)折線相對離散，分離效果明顯，便于對數(shù)據(jù)單獨分析和可視化展示。引入L1稀疏化特征選擇方法，表現(xiàn)出了更好的數(shù)據(jù)分離能力，對于平行坐標圖的數(shù)據(jù)線條聚集問題有明顯改進。

圖5 平行坐標圖折線分散效果對比

3.5 改進的散點圖效果

由于散點圖平面較小，當數(shù)據(jù)數(shù)量很高時，數(shù)據(jù)點聚集現(xiàn)象就會變得很嚴重，極大影響可視化圖形的閱讀性。因此，可視化數(shù)據(jù)點之間的聚集與離散性指標Silhouette (Silh)系數(shù)[18]通常用來評價散點圖可視化效果。式(4)中,ax代表點x與同類別的其它點之間距離的平均值，bx代表點x與所有其它類別的點的距離的最小值。Silh的值的范圍在-1到 1之間，Silh值越大代表更好的內(nèi)聚性和分離性。

(4)

圖6展示的是學(xué)習(xí)得到的關(guān)于非洲城市和亞洲城市投影函數(shù)后得到散點圖。圖6(a)是解釋器方法得到的散點圖， Silh值為0.203。圖6(b)是應(yīng)用本文方法后得到低維空間的數(shù)據(jù)后，再使用PCA方法得到的散點圖，Silh值為0.287。 圖6(c)和圖6(d)所示為本文方法在稀疏度為0.73、0.83時，Silh值分別為0.403和0.417均高于傳統(tǒng)方法和PCA方法。說明本文方法在數(shù)據(jù)的散點圖可視化時，耦合性和分離性效果表現(xiàn)更好。圖7展示中將本文方法應(yīng)用到汽車數(shù)據(jù)集合中，對比傳統(tǒng)的解釋器方法以及PCA方法，本文方法圖7(c),圖7(d)的Silh分別為0.485和0.513，獲得了更好的結(jié)果。

圖8為本文方法和傳統(tǒng)的PCA方法應(yīng)用到城市數(shù)據(jù)集和汽車數(shù)據(jù)集上的稀疏度-silh值圖?？梢园l(fā)現(xiàn)隨著稀疏度的提高，散點圖的Silh值明顯提高。但特征過于稀疏后，Silh也會明顯下降。對比這兩個數(shù)據(jù)集上的結(jié)果，發(fā)現(xiàn)本文方法相比于PCA方法，獲得的Silh值都更大，可視化效果更好。

因此，本文方法相比解釋器方法和PCA方法，對于多類別的數(shù)據(jù)在二維散點圖展示時，明顯提升數(shù)據(jù)的內(nèi)聚性和分離性，不同類別數(shù)據(jù)點聚集情況明顯減輕，方便了分析人員可視化探索數(shù)據(jù)。

通過可視化實驗中對比效果，可以發(fā)現(xiàn)本文提出的基于高維層次數(shù)據(jù)可視化分析的方法，通過引入L1稀疏化學(xué)習(xí)的過程，不僅便于分析人員可視化探索高維數(shù)據(jù)語義標簽與特征之間的潛在關(guān)系。通過可視化實驗，本文方法對比于解釋器方法和傳統(tǒng)的PCA方法，在平行坐標圖和散點圖上的可視化效果更好，明顯改進了圖形中數(shù)據(jù)的聚集現(xiàn)象，提高數(shù)據(jù)分離效果，方便分析人員對高維數(shù)據(jù)的可視化探索。

圖6 城市數(shù)據(jù)集-散點圖效果對比

圖7 汽車數(shù)據(jù)集-散點圖效果對比

圖8 稀疏度-silh值圖

4 結(jié) 語

本文提出一種針對層次化高維數(shù)據(jù)進行可視化分析和探索的新方法。對層次結(jié)構(gòu)數(shù)據(jù)集采用L1稀疏化分類器進行模型訓(xùn)練，實現(xiàn)語義標簽與之緊密相關(guān)的數(shù)據(jù)特征的自動選取。通過參數(shù)調(diào)節(jié)模型的稀疏性，可以得到不同的特征組合，以及相應(yīng)的高維數(shù)據(jù)解釋器(投影函數(shù))，從而建立起了從高維到低維特征與高層語義之間的聯(lián)系。通過可視化實驗，證明了本文提出的方法可以改進解釋器投影技術(shù)的可視化分析效果，特別是在平行坐標和散點圖等常用的高維數(shù)據(jù)可視化技術(shù)中，本文提出的方法表現(xiàn)出更好的數(shù)據(jù)分離能力，可以有效改進高維數(shù)據(jù)的可視化分析效果。

[1] Jolliffe I T.Principal Component Analysis[J].Springer Berlin, 2010,87(100):41-64.

[2] Friedman J H, Tukey J W. A Projection Pursuit Algorithm for Exploratory Data Analysis[J].Computers IEEE Transactions on, 1974, C-23(9):881-890.

[3] Faith J. Targeted Projection Pursuit for Interactive Exploration of High-Dimensional Data Sets[C]//Information Visualization, 2007. IV’07. 11th International Conference. IEEE, 2007:286-292.

[4] Seo J, Shneiderman B. A Rank-by-Feature Framework for Interactive Exploration of Multidimensional Data[J].Information Visualization, 2005, 4(2):96-113.

[5] Wilkinson L, Anand A, Grossman R. Graph-theoretic scagnostics[C]//Information Visualization, 2005. INFOVIS 2005. IEEE Symposium on，2005:157-164.

[6] Wang S P, Cao H F, Wei Ping W U. Observation-level interaction with statistical models for visual analytics[C]//Visual Analytics Science and Technology. IEEE, 2011:121-130.

[7] Tejada E, Minghim R, Nonato L G. On improved projection techniques to support visual exploration of multidimensional data sets[J].Information Visualization,2003,2(4):218-231.

[8] Paulo J, Paulovich F V, Danilo C, et al. Local Affine Multidimensional Projection[J].IEEE Transactions on Visualization & Computer Graphics,2011,17(12):2563-2571.

[9] Kandogan E. Just-in-time annotation of clusters, outliers, and trends in point-based data visualizations[C]//Visual Analytics Science and Technology，2012:73-82.

[10] Lu L F, Huang M L, Chen Y W, et al.Clutter Reduction in Multi-dimensional Visualization of Incomplete Data Using Sugiyama Algorithm[C]//International Conference on Information Visualization. IEEE Computer Society, 2012:93-99.

[11] Michael G.Explainers: expert explorations with crafted projections[J].IEEE Transactions on Visualization & Computer Graphics, 2013,19(12):2042-2051.

[12] Jorge P, Aritra D, Yaxing W, et al. Visual Reconciliation of Alternative Similarity Spaces in Climate Modeling[J].IEEE Transactions on Visualization & Computer Graphics, 2014,20(12):1923-1932.

[13] Sedlmair M, Heinzl C, Bruckner S, et al. Visual Parameter Space Analysis: A Conceptual Framework[J].IEEE Transactions on Visualization & Computer Graphics, 2014,20(12):2161-2170.

[14] Zhou D, Xiao L, Wu M.Hierarchical Classification via Orthogonal Transfer[C]//International Conference on Machine Learning，2011:801-808.

[15] 產(chǎn)文. Web社區(qū)問答檢索的關(guān)鍵技術(shù)研究[D].復(fù)旦大學(xué),2014.

[16] Buzzdata. Best City Contest[Z]. 2012.

[17] Bache K, Lichman M. UCI Machine Learning Repository[Z/OL]. Irvine, CA: University of California, School of Information and Computer Science.2013. http://archive.ics.uci.edu/ml.

[18] Tan P N, Steinbach M, Kumar V. Introduction to Data Mining, (First Edition)[M].Addison-Wesley Longman Publishing Co. Inc，2005.

HIGH-DIMENSIONAL DATA VISUALIZATION ANALYSIS TECHNOLOGY BASED ON SPARSE REGULARIZATION

Chen Haihui Zhou Xiangdong Shi Bole

(SchoolofComputerScienceandTechnology,FudanUniversity,Shanghai200433，China)

High-dimensional data visualization analysis is the research hotspot in the field of data analysis and visualization, the traditional low-dimensional dimension reduction method is often difficult to explain, and is not conducive to the visualization of high-dimensional data analysis and exploration. In this paper, a new visual explorer (Explainer) method is proposed to introduce the L1 sparse regularization feature selection into the high-dimensional data visualization process, and establish the relationship between high-level semantic tags and a few key features.The feasibility of the method is verified by visual design and experiment. It can improve the visualization performance of high dimensional data effectively.

high-dimension data Feature selection Sparse learning Visualization analysis Dimension reduction Projection

2016-05-03。國家自然科學(xué)基金項目(61370157)；上海市科技項目(14511107403)；國網(wǎng)科技項目(5209401600 0A)。陳海輝，碩士生，主研領(lǐng)域：數(shù)據(jù)可視化。周向東，教授。施伯樂，教授。

TP3

A

10.3969/j.issn.1000-386x.2017.06.005