基于平行坐標(biāo)的高維數(shù)據(jù)可視化算法研究

徐旸

摘要：由于大數(shù)據(jù)時(shí)代的多維數(shù)據(jù)的普及，多維數(shù)據(jù)的可視化和可視化分析對(duì)于數(shù)據(jù)模式的發(fā)現(xiàn)至關(guān)重要。平行坐標(biāo)圖主要用于對(duì)同一組的不同屬性進(jìn)行可視化分析?？梢暬嗑S高維數(shù)據(jù)的常用方法是使用平行坐標(biāo)圖。但是，這些方法由于邊的重疊導(dǎo)致視覺(jué)混淆從而無(wú)法有效地表達(dá)數(shù)據(jù)信息和檢測(cè)模式。該文設(shè)計(jì)了一個(gè)高維數(shù)據(jù)可視化算法，基于邊捆綁的平行坐標(biāo)圖，并對(duì)其進(jìn)行重新排列，有效地提高了高維數(shù)據(jù)的理解和視覺(jué)分析能力。

關(guān)鍵詞：高維；平行坐標(biāo)圖；視覺(jué)混淆；可視化

中圖分類(lèi)號(hào)：TP31 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）09-0017-03

Abstract： Due to the popularity of multidimensional data in the era of big data， the visualization and visual analysis of multidimensional data is crucial for the discovery of data patterns. The parallel coordinates are mainly used to visualize the different attributes of the same group. A common way to visualize multidimensional high-dimensional data is to use parallel coordinates. However， these methods cant effectively express the data information and the detection mode due to the visual confusion caused by the overlap of the edges. In this paper， a high-dimensional data visualization algorithm is designed， which is based on the side-bound parallel coordinates and rearranges them. It effectively improves the ability of high-dimensional data understanding and visual analysis.

Key words： High-dimensional；parallel coordinates plot；visual clutter；visualization

近些年來(lái)，隨著科學(xué)信息技術(shù)的發(fā)展，系統(tǒng)的存儲(chǔ)容量和運(yùn)算能力都有了突破性的提高，數(shù)據(jù)的采集和存儲(chǔ)變得越來(lái)越方便，在包括工業(yè)，金融業(yè)，制造業(yè)互聯(lián)網(wǎng)等各個(gè)領(lǐng)域產(chǎn)生了大量的數(shù)據(jù)。這些數(shù)據(jù)往往擁有很多個(gè)屬性，被稱(chēng)為多維數(shù)據(jù)。這些多維數(shù)據(jù)需要數(shù)據(jù)展示分析方法將其進(jìn)行數(shù)據(jù)可視化，普通情況下，多維數(shù)據(jù)的分析是在二維的屏幕空間內(nèi)進(jìn)行的，因此，大量的多維數(shù)據(jù)如何映射到普通的二維屏幕空間是研究的重點(diǎn)。

在20世紀(jì)80年代中期和90年代初期，Insellber等[1]提出了一種多維數(shù)據(jù)可視化技術(shù)，稱(chēng)為平行坐標(biāo)技術(shù)，該技術(shù)也是后來(lái)研究和應(yīng)用最為廣泛的多維數(shù)據(jù)可視化技術(shù)。在該方法中，每個(gè)高維數(shù)據(jù)對(duì)象被映射為相互平行的屬性軸上，并根據(jù)每條屬性的屬性值將相鄰2個(gè)屬性軸建立連接關(guān)系，邊是連接N個(gè)數(shù)據(jù)點(diǎn)的折線。

該項(xiàng)技術(shù)存在幾個(gè)缺陷。例如，當(dāng)數(shù)據(jù)規(guī)模較大時(shí)，平行坐標(biāo)中的邊的數(shù)量增多，各邊之間形成大量的重疊，這會(huì)造成視覺(jué)上的混淆，而這種混亂將會(huì)進(jìn)一步造成數(shù)據(jù)分析人員對(duì)數(shù)據(jù)判斷的干擾，使完成集合內(nèi)部和集合之間的任務(wù)分析變得困難。為了解決這個(gè)問(wèn)題，在基于平行坐標(biāo)技術(shù)的基礎(chǔ)上，提出一種新的多維數(shù)據(jù)可視化算法，去改進(jìn)缺陷。

1 相關(guān)工作

平行坐標(biāo)技術(shù)是高維數(shù)據(jù)可視化的常用方法。但是，當(dāng)數(shù)據(jù)實(shí)例的數(shù)量很大時(shí)，平行坐標(biāo)技術(shù)可能由于重疊繪制而變得混亂。現(xiàn)在有很多研究來(lái)減少視覺(jué)混亂。Heinrichetal[2]等使用平行坐標(biāo)圖的捆綁技術(shù)。他們的研究目的是比較捆綁平行坐標(biāo)和原始平行坐標(biāo)圖之間數(shù)據(jù)集線性相關(guān)的識(shí)別效率。有些方法需要通過(guò)操縱軸來(lái)重新排序。這些方法可以揭示隱藏的模式。有些方法通過(guò)渲染曲線來(lái)增強(qiáng)平行坐標(biāo)圖。這種方法有效地減少了由于繪圖造成的混亂。Edward J. Wegman等[3]使用數(shù)據(jù)集的聚類(lèi)。McDonell[4]等將傳統(tǒng)的邊捆綁算法用于平行坐標(biāo)，使用貝塞爾曲線來(lái)代替原有的折線，并通過(guò)調(diào)整控制點(diǎn)的位置來(lái)調(diào)整曲線彎度，進(jìn)而調(diào)整邊捆綁強(qiáng)度。Heinrich B J，Stasko J和Weiskopf D[5]評(píng)估了用于捆綁識(shí)別的平行坐標(biāo)圖。這也是減少視覺(jué)混淆的常用技術(shù)。Palmas[6]等首先使用高斯核密度估計(jì)來(lái)對(duì)平行坐標(biāo)每個(gè)屬性軸上的數(shù)據(jù)點(diǎn)單獨(dú)聚類(lèi)，在邊捆綁之前為每個(gè)屬性軸添加虛擬綁定軸；然后結(jié)合原始數(shù)據(jù)集將相鄰2個(gè)屬性軸上的群集連接，在渲染時(shí)使用多邊形來(lái)代替相鄰2個(gè)虛擬綁定軸之間的連接關(guān)系。Telea A和Ersoy O[7]使用基于圖像的邊緣捆綁算法。雖然這些邊緣捆綁算法以不同方式計(jì)算曲線邊緣，但是它們使得一些邊緣圖案更明顯，從而減少了視覺(jué)混淆。Wang J[8]使用平行坐標(biāo)圖中嵌入的多分辨率氣象數(shù)據(jù)集分析數(shù)據(jù)參數(shù)，有效地分析了多分辨率多屬性之間的相關(guān)性，但在多維高維可視化時(shí)可能存在不必要的遮擋數(shù)據(jù)。Zhou等[9]將平行坐標(biāo)假設(shè)為一個(gè)物理能量系統(tǒng)，邊與邊之間有相互作用力，并且邊在其他邊的作用力下可彎曲，邊的彎曲程度由其在能量系統(tǒng)中所受其他邊的合力決定。該算法在最大限度地減少邊的曲率的同時(shí)，最大化邊與相鄰邊之間的平行度， 最終達(dá)到邊捆綁的效果，從而緩解視覺(jué)混淆。在本文中，我們使用一種基于中值的重排算法，用于綁定平行坐標(biāo)圖，以減少高維數(shù)據(jù)中多個(gè)集合中的視覺(jué)雜波。

2 算法實(shí)現(xiàn)研究

2.1捆綁平行坐標(biāo)圖的設(shè)計(jì)

在平行坐標(biāo)圖中，每個(gè)高維數(shù)據(jù)都被繪制成一條多段線并被映射為相互平行的屬性軸上，并根據(jù)每條屬性的屬性值將相鄰2個(gè)屬性軸建立連接關(guān)系，這樣形成連接N個(gè)數(shù)據(jù)點(diǎn)的折線，稱(chēng)為邊。通常，所有邊都在相鄰的軸之間交叉。邊的整體分布特征可以反應(yīng)數(shù)據(jù)集相鄰屬性之間的關(guān)系。為了進(jìn)一步比較組件關(guān)系，在原始的平行坐標(biāo)圖的相鄰屬性軸之間添加束點(diǎn)。從而反映了組件分配。從水平，垂直和彎曲程度三個(gè)方面來(lái)構(gòu)造邊捆綁的平行坐標(biāo)圖。

在水平方向上：定義軸[Xi]和[ Xi+1 ]為原始平行坐標(biāo)的相鄰屬性軸，軸的高度為h和寬度w。對(duì)于一個(gè)集合，點(diǎn)[Mx0，y0]，其中[x0]是相鄰軸的中線的橫坐標(biāo)，[y0]是垂直方向中線的[n+1]平分線，其中n是集。

在垂直方向上：組間束點(diǎn)沿著兩個(gè)相鄰軸的中心線分布，束點(diǎn)的數(shù)量取決于組的數(shù)量。例如：如果組數(shù)為6，則兩個(gè)相鄰軸之間將出現(xiàn)6個(gè)束點(diǎn)。

在彎曲程度上：用[γ]表示曲線，用來(lái)描述兩個(gè)三次貝塞爾曲線的失真尺度。三次貝塞爾曲線的幾何形狀由四個(gè)控制點(diǎn)決定。開(kāi)始（結(jié)束）控制點(diǎn)由數(shù)據(jù)集的相應(yīng)屬性值確定，結(jié)束（開(kāi)始）控制點(diǎn)由束點(diǎn)確定。中間的另外兩個(gè)控制點(diǎn)由[γ]決定，其中[w1=W/2*γ] ，[0≤γ≤1]。假設(shè)節(jié)點(diǎn)[Px1，y1]，第二控制點(diǎn)坐標(biāo)為[x1+w1，y1]，第三控制點(diǎn)坐標(biāo)為[x0-w1，y0]。

使用上述設(shè)計(jì)，可以繪制捆綁的平行坐標(biāo)圖。數(shù)據(jù)在一維中的集合間分布可能是傾斜的，所以直接的捆綁平行坐標(biāo)圖在不同集合之間產(chǎn)生遮擋。

2.2重新排列集合順序

當(dāng)數(shù)據(jù)規(guī)模較小時(shí)，可以進(jìn)行手動(dòng)過(guò)濾，但是當(dāng)存在多個(gè)集合或者多個(gè)屬性時(shí)，考慮到多個(gè)屬性之間的關(guān)系，手動(dòng)過(guò)濾可能會(huì)遇到很多麻煩。如何重新排列集合的順序，從而有效地減少視覺(jué)冗余，成為亟待解決的問(wèn)題。在本文中，使用一個(gè)基于中值的重排算法來(lái)解決這個(gè)問(wèn)題。

為了更好地理解同一維度的集合分布，使用中心趨勢(shì)來(lái)衡量數(shù)據(jù)分布的中心。由于大部分?jǐn)?shù)據(jù)是非對(duì)稱(chēng)數(shù)據(jù)，因此更好的方法是使用中位數(shù)。中值是與最大值或最小值無(wú)關(guān)的序數(shù)的中間值，它將高一半的數(shù)據(jù)與下半部分分開(kāi)，并有效地反映了集合在屬性中的集中趨勢(shì)。

為了更全面地了解整個(gè)數(shù)據(jù)集中不同集合屬性的集中趨勢(shì)，建立了一個(gè)中值矩陣M。假設(shè)數(shù)據(jù)集中有n*d個(gè)屬性，則第i個(gè)屬性的j屬性的中位數(shù)為[mij]，這反映了數(shù)據(jù)分布的中心趨勢(shì)。計(jì)算整個(gè)數(shù)據(jù)集以獲得中值矩M.

由于不同屬性的范圍不同，為避免影響數(shù)據(jù)分析，數(shù)據(jù)應(yīng)標(biāo)準(zhǔn)化。Min-max標(biāo)準(zhǔn)化是數(shù)據(jù)標(biāo)準(zhǔn)化的常用方法。對(duì)方差的倍數(shù)進(jìn)行縮放，不會(huì)消除方差的影響，能夠有效反映數(shù)據(jù)的原始分布。本文采用Min–max標(biāo)準(zhǔn)化方法對(duì)各屬性的中值矩陣進(jìn)行標(biāo)準(zhǔn)化處理。假設(shè) [minA]和[maxa]分別是屬性A上整個(gè)數(shù)據(jù)集的最小值和最大值。 計(jì)算Min-max標(biāo)準(zhǔn)化

A的值[vi]被映射到區(qū)域[0，10]中的[v'i]。中值矩陣根據(jù)每個(gè)屬性進(jìn)行標(biāo)準(zhǔn)化化。 然后得到標(biāo)準(zhǔn)化化的中值矩陣Q.

矩陣Q可以有效地反映不同集合中相同屬性的分布差異。通過(guò)觀察發(fā)現(xiàn)，當(dāng)一個(gè)集合中所有屬性的中值波動(dòng)相對(duì)較大時(shí)，集合間的遮擋比較嚴(yán)重，但當(dāng)波動(dòng)相對(duì)較小時(shí)，集合間的遮擋效果較好。因此，有必要分析所有屬性的集合的波動(dòng)性，然后考慮最少量的視覺(jué)混淆。 在本文中，標(biāo)準(zhǔn)化中位數(shù)用于每個(gè)屬性集合的總和，以定量描述集合在所有屬性上的分布。矩陣S是通過(guò)對(duì)矩陣Q求和得到的。

其中[si]的相對(duì)大小反映了集合i在所有屬性上的總體分布。S中的元素被分類(lèi)以獲得集合的優(yōu)先級(jí)。然后，根據(jù)新的順序繪制一個(gè)新的捆綁平行坐標(biāo)圖。新的捆綁平行坐標(biāo)繪圖有效地減少了視覺(jué)冗余和套間遮擋。

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

為了驗(yàn)證多維可視化算法的有效性，本文進(jìn)行了實(shí)驗(yàn)驗(yàn)證，選取了標(biāo)準(zhǔn)的多維數(shù)據(jù)集。繪制了重排之后的邊捆綁的平行坐標(biāo)圖。重排前后的對(duì)比圖（上圖為重排前，下圖為重排之后）如圖1所示：

并計(jì)算其平均路徑長(zhǎng)度，平均路徑長(zhǎng)度可以用來(lái)衡量平行坐標(biāo)圖中的混淆程度。 計(jì)算公式如下：

重排后的平行坐標(biāo)圖之前和之后的平均路徑長(zhǎng)度的比較如下圖2所示。從平均路徑長(zhǎng)度的比較來(lái)看，重排后的結(jié)果要好于非重新排列的平行坐標(biāo)圖。

4 總結(jié)和展望

在本文中，我們?cè)O(shè)計(jì)了新的高維可視化算法，基于平行坐標(biāo)圖技術(shù)，將基于中值的重排算法應(yīng)用于邊捆綁的平行坐標(biāo)圖，用于多集高維數(shù)據(jù)的可視化和分析。使用該算法，可以更容易地看到多維數(shù)據(jù)的所有屬性的總體分布。通過(guò)將該算法應(yīng)用于仿真數(shù)據(jù)和現(xiàn)實(shí)世界數(shù)據(jù)集，證明了該方法的有效性。今后，我們希望為視察增加視覺(jué)增強(qiáng)元素，以增強(qiáng)視覺(jué)表現(xiàn)力，同時(shí)我們也嘗試在其他領(lǐng)域應(yīng)用視聽(tīng)增強(qiáng)成果。

參考文獻(xiàn)：

[1] Inselberg A. Theplane with parallel coordinates[J]. The Visual Computer， 1985， 1（2）：69-91.

[2] Heinrich J， Luo Y， Kirkpatrick A E， et al. Evaluation of a Bundling Technique for Parallel Coordinates[J]. Energy Conversion & Management， 2011， 88（5）：259-266.

[3] Wegman E J， Luo Q. High Dimensional Clustering Using Parallel Coordinates and the Grand Tour[J]. Studies in Classification Data Analysis & Knowledge Organization， 1996， 28：361--368.

[4] Mcdonnell K T， Mueller K. Illustrative parallel coordinates[J]. Computer Graphics Form， 2008， 27（3）： 1031-1038.

[5] Heinrich B J， Stasko J， Weiskopf D. Eurographics Conference on Visualization （EuroVis） （2012） M. Meyer and T. Weinkauf （Editors） Short Papers The Parallel Coordinates Matrix[J]. 2010.

[6] Palmas G， Bachynskyi M， Oulasvirta A， et al. An edge-bundling layout for interactive parallel coordinates[C] //Proceedings of IEEE Pacific Visualization Symposium. Los Alamitos： IEEE Computer Society Press， 2014： 57-64.

[7] Telea A， Ersoy O. Image-Based Edge Bundles： Simplified Visualization of Large Graphs[J]. Computer Graphics Forum， 2010， 29（3）：843-852.

[8] Wang J， Liu X， Shen H W， et al. Multi-Resolution Climate Ensemble Parameter Analysis with Nested Parallel Coordinates Plots[J]. 2017：81-90.

[9] Zhou H， Yuan X R， Qu H M， et al. Visual clustering in parallel coordinates[J]. Computer Graphics Forum， 2008， 27（3）： 1047-1054.