王藝洋，黃 濤

（1.武漢郵電科學(xué)研究院研究生院，湖北 武漢 430074；2.武漢眾智數(shù)字技術(shù)有限公司，湖北武漢 430074）

在信息時(shí)代的生產(chǎn)生活中，數(shù)據(jù)可視化技術(shù)在 越來越多的領(lǐng)域有了實(shí)際應(yīng)用場景。數(shù)據(jù)可視化技術(shù)是通過布局算法，將抽象的數(shù)據(jù)變?yōu)閳D像進(jìn)行展示[1]。數(shù)據(jù)之間清晰的關(guān)聯(lián)關(guān)系，可以增強(qiáng)人們在閱讀數(shù)據(jù)時(shí)的觀感?？梢暬夹g(shù)可以幫助人們在互聯(lián)網(wǎng)時(shí)代提升對信息的認(rèn)知程度，結(jié)合人的視覺和學(xué)習(xí)認(rèn)知能力，提高人們對信息的挖掘和分析能力，從而提高信息利用率[2-4]。當(dāng)前各類可視化技術(shù)都取得了一定的進(jìn)展[5-8]，但隨著各類數(shù)據(jù)變得復(fù)雜化和多樣化，可視化算法要考慮更多的影響因素。文中通過研究多種力布局算法的改進(jìn)方法[9-11]，根據(jù)模擬退火原理，擬采用退火公式，對節(jié)點(diǎn)偏差與迭代次數(shù)進(jìn)行關(guān)系映射，在力布局算法的基礎(chǔ)上將兩者的關(guān)系映射融入到節(jié)點(diǎn)位置的布局過程中，實(shí)現(xiàn)對算法的改進(jìn)，提高可視化性能，降低最小節(jié)點(diǎn)偏差。通過與傳統(tǒng)力布局算法的對比進(jìn)行改進(jìn)思想的驗(yàn)證。

1 相關(guān)技術(shù)

1.1 D3.js

D3.js 作為當(dāng)前主流的可視化庫之一，被很多表格插件所使用[12]。D3.js 可以將任意的數(shù)據(jù)綁定到DOM上，然后在DOM 中完成對數(shù)據(jù)驅(qū)動的轉(zhuǎn)換?？梢栽诳梢暬瘞斓幕A(chǔ)上，使用數(shù)組建立一個HTML表格，在網(wǎng)頁中與元素進(jìn)行交互。

將所有功能都涵蓋進(jìn)自身的框架中并不是D3.js的宗旨所在，它解決問題的核心手段是通過將數(shù)據(jù)和DOM 綁定，把數(shù)據(jù)和HTML 結(jié)構(gòu)或者SVG 文檔對應(yīng)起來，利用數(shù)據(jù)驅(qū)動文檔的變化，打破數(shù)據(jù)展現(xiàn)的局限性。D3.js 依靠海量的函數(shù)進(jìn)行數(shù)據(jù)處理和物理計(jì)算，相較于echarts 等其他主流的可視化工具，D3.js 的功能覆蓋更加廣泛，操作DOM 也更加方便，而且D3.js 處理速度很快，大型數(shù)據(jù)集交互與動畫的動態(tài)行為都可以通過D3.js 來實(shí)現(xiàn)。

1.2 力導(dǎo)向布局算法

最早的力導(dǎo)向布局相關(guān)算法在1984 年由Peter Dades 提出，算法以自然界中電子之間的直接互相作用為原理[13]。在力導(dǎo)向布局算法中，各節(jié)點(diǎn)和連線的位置是通過斥力和引力的作用下不斷更新的，在力的作用下節(jié)點(diǎn)經(jīng)過不斷位移之后趨于平衡，節(jié)點(diǎn)位置逐漸穩(wěn)定，不再發(fā)生相對位移，能量隨著位移不斷消耗，最終趨于零，以此使各節(jié)點(diǎn)間達(dá)到一種物理狀態(tài)的平衡。

力導(dǎo)向布局算法是繪制一般網(wǎng)狀結(jié)構(gòu)的常用方法[14]。該算法以力導(dǎo)向模型作為基礎(chǔ)，利用圖的結(jié)構(gòu)計(jì)算圖形的層次，而無需對上下文信息再進(jìn)行分析處理。力導(dǎo)向繪圖可以用于展示關(guān)系圖的結(jié)點(diǎn)之間的關(guān)系，將結(jié)點(diǎn)分布到畫布上的合理位置，比如描述企業(yè)之間的關(guān)系、社交網(wǎng)絡(luò)中的人際關(guān)系等[15]。

力導(dǎo)向布局算法中的引力與斥力的計(jì)算公式分別如式（1）和（2）所示：

式（1）中，d為兩節(jié)點(diǎn)之間的笛卡爾距離；K是調(diào)節(jié)全局節(jié)點(diǎn)之間的斥力常量；符號“-”表示斥力的表征方向。

式（2）中，d同為節(jié)點(diǎn)之間的笛卡爾距離；H為彈簧力的倔強(qiáng)系數(shù)；Li為第i層的默認(rèn)彈簧長度，且Li/Li+1=I，即第i層和第i+1 層的邊長比值為一個固定常數(shù)I。

1.3 模擬退火算法原理

模擬退火算法由Metropolis 提出，1983年，S.Kirkpatrick 等人為了進(jìn)行組合優(yōu)化將其引入到計(jì)算機(jī)領(lǐng)域。模擬退火算法是基于Monte-Carlo 迭代求解策略的一種隨機(jī)尋優(yōu)算法[16]。其思想理論來自于物理學(xué)中的退火過程，先將固體加溫至充分高，接著令其徐徐冷卻，在加溫過程中，固體內(nèi)部粒子的內(nèi)能會升高，并進(jìn)行無序運(yùn)動，而在冷卻過程中內(nèi)能減少，粒子運(yùn)動趨于有序，最后當(dāng)溫度變?yōu)槠胶鈶B(tài)時(shí)達(dá)到基態(tài)，此時(shí)內(nèi)能最小。模擬退火算法就是從一個初始的高溫出發(fā)，隨著溫度參數(shù)的下降，利用概率突降特性尋找函數(shù)的最優(yōu)解。文中利用模擬退火的概率性突跳尋求最優(yōu)解的思想，在力布局算法迭代過程中引入退火公式，使節(jié)點(diǎn)偏差跳出局部最優(yōu)，從而尋找全局最優(yōu)節(jié)點(diǎn)偏差。

2 改進(jìn)的力布局算法

2.1 節(jié)點(diǎn)偏差與迭代關(guān)系映射

在力導(dǎo)向布局算法中，形成的初始布局里節(jié)點(diǎn)位置是隨機(jī)分布的，并在不斷的迭代過程中，以一定的速度更新節(jié)點(diǎn)坐標(biāo)，并在引力與斥力的不斷作用下，形成最終的布局效果。在對力導(dǎo)向布局算法的研究中發(fā)現(xiàn)，在節(jié)點(diǎn)數(shù)較少的情況下，迭代停止前，已經(jīng)達(dá)到良好的布局效果；在節(jié)點(diǎn)數(shù)較多的情況下，迭代停止時(shí)還未達(dá)到較好的布局效果，因此如果可以動態(tài)地調(diào)整迭代次數(shù)，則對布局效果可以起到優(yōu)化作用。

文中在遵循布點(diǎn)算法美學(xué)標(biāo)準(zhǔn)的基礎(chǔ)上，采用節(jié)點(diǎn)偏差作為布局效果的評價(jià)參數(shù)，將節(jié)點(diǎn)偏差與迭代次數(shù)形成關(guān)系映射，整合到力導(dǎo)向布局算法中，在布局過程中，采用節(jié)點(diǎn)偏差值作為退火參數(shù)決定迭代的進(jìn)行。美學(xué)標(biāo)準(zhǔn)中最佳分布距離和節(jié)點(diǎn)偏差表示分別如式（3）和（4）所示：

式（3）中，Acr 為整個畫布的面積，Nnode表示當(dāng)前節(jié)點(diǎn)數(shù)，distance 表示最佳節(jié)點(diǎn)距離。

式（4）中，Dx,i和Dx,i+1分別表示當(dāng)前節(jié)點(diǎn)和下一節(jié)點(diǎn)的x軸坐標(biāo)，Dy,i和Dy,i+1分別表示當(dāng)前節(jié)點(diǎn)和下一節(jié)點(diǎn)的y軸坐標(biāo)。

通過計(jì)算可以將得到的所有節(jié)點(diǎn)之間的節(jié)點(diǎn)偏差組成一個節(jié)點(diǎn)偏差集合，即d=(d1,2,d1,3,…,d1,i+1,…,di,i+1)，并得到最小節(jié)點(diǎn)偏差dmin。利用模擬退火算法原理對節(jié)點(diǎn)偏差與迭代次數(shù)進(jìn)行關(guān)系映射，具體公式如式（5）所示：

式（5）中，p表示進(jìn)行迭代的概率，其取值范圍是(0,1)；exp 表示自然指數(shù)；T是模擬退火算法的初始溫度；dmin,new表示當(dāng)次迭代的最小節(jié)點(diǎn)偏差；dmin,old表示上次迭代的最小節(jié)點(diǎn)偏差。

若此次節(jié)點(diǎn)移動后的最小節(jié)點(diǎn)偏差優(yōu)于上次，則接受此次移動；反之則以一定的概率p接受此次移動，且概率p隨著迭代次數(shù)的增加逐漸降低。p的值越小，表明如果進(jìn)行下一次迭代，則出現(xiàn)更小節(jié)點(diǎn)偏差值的概率越低。

2.2 改進(jìn)算法流程描述

改進(jìn)算法的數(shù)據(jù)可視化流程如圖1 所示。

圖1 可視化流程圖

輸入：各節(jié)點(diǎn)初始位置坐標(biāo)、畫布面積。

輸出：各節(jié)點(diǎn)最終位置坐標(biāo)、數(shù)據(jù)布局圖。

1）對輸入的各節(jié)點(diǎn)坐標(biāo)數(shù)據(jù)進(jìn)行初步計(jì)算，得到初始化布局，根據(jù)式（3）得到最佳分布距離；

2）通過力布局算法開始迭代，節(jié)點(diǎn)在引力與斥力的作用下，布局位置開始改變；

3）每次迭代完成后更新節(jié)點(diǎn)的位置，并且根據(jù)式（4）得到最小節(jié)點(diǎn)偏差；

4）將最小節(jié)點(diǎn)偏差代入式（5）中進(jìn)行迭代概率的計(jì)算；

5）當(dāng)?shù)螖?shù)達(dá)到閾值或式（5）中得到的概率p＜Random(0,1)時(shí)，跳出布局算法，得到最終的數(shù)據(jù)布局圖。迭代次數(shù)閾值設(shè)為500 次。

3 實(shí)驗(yàn)分析

3.1 布局的美學(xué)標(biāo)準(zhǔn)

圖布局就是將當(dāng)前節(jié)點(diǎn)的位置與目標(biāo)節(jié)點(diǎn)通過連線連接起來進(jìn)行展示。將復(fù)雜的數(shù)據(jù)形成易于觀察的可視化布局并不簡單。清晰可觀的展示數(shù)據(jù)和圖的結(jié)構(gòu)，并且展示和操作過程流暢，是當(dāng)前圖的布局算法研究的重心所在。對于這些要求，圖布局有一套美學(xué)標(biāo)準(zhǔn)，用來衡量一個圖布局算法的可視化效果優(yōu)良，具體有四個原則。

1）交叉邊線最小原則：過于繁雜的交叉邊線會影響圖的清晰度，繪圖時(shí)應(yīng)盡量減少相互交叉邊的數(shù)量；

2）直線原則：邊線應(yīng)該盡量為直線，避免出現(xiàn)曲線、直線共存的現(xiàn)象，同時(shí)單個節(jié)點(diǎn)的邊線數(shù)盡可能不要超過節(jié)點(diǎn)數(shù)；

3）對稱性原則：繪制中心節(jié)點(diǎn)網(wǎng)絡(luò)時(shí)，將具有相同結(jié)構(gòu)的子節(jié)點(diǎn)圍繞中心節(jié)點(diǎn)進(jìn)行平衡布局；

4）節(jié)點(diǎn)集中原則：節(jié)點(diǎn)分布不能過于分散，盡量多個節(jié)點(diǎn)集中在中心節(jié)點(diǎn)附近。

3.2 實(shí)驗(yàn)結(jié)果和分析

3.2.1 可視化效果對比

實(shí)驗(yàn)采用D3.js 可視化工具進(jìn)行數(shù)據(jù)可視化的實(shí)現(xiàn)，為了更加清晰地對可視化效果進(jìn)行對比，選取的實(shí)驗(yàn)節(jié)點(diǎn)數(shù)量為500，模擬退火初始溫度T設(shè)為畫布邊長的一半。傳統(tǒng)力布局算法和改進(jìn)算法的可視化效果分別如圖2 和圖3 所示。

圖2 傳統(tǒng)力導(dǎo)向布局算法可視化效果

圖3 改進(jìn)算法可視化效果

由圖2 可以看出，傳統(tǒng)力導(dǎo)向布局效果相近節(jié)點(diǎn)與節(jié)點(diǎn)之間距離過近，沒有完全展開，呈現(xiàn)效果不飽滿，多條連線之間存在相互交叉，節(jié)點(diǎn)與連線布局比較雜亂。而在圖3中，中心節(jié)點(diǎn)與子節(jié)點(diǎn)之間連線指向比較清晰，子節(jié)點(diǎn)排列飽滿，呈對稱分布，相互間隔一定距離。改進(jìn)算法后的布局效果有了明顯的提升，大部分節(jié)點(diǎn)與連線都對稱分布，交叉線有明顯減少，對于各個節(jié)點(diǎn)之間的關(guān)系有了明確直觀的展示，證明了考慮節(jié)點(diǎn)偏差對迭代次數(shù)的影響后，布局效果能夠更加符合數(shù)據(jù)可視化的美學(xué)標(biāo)準(zhǔn)。

3.2.2 最小節(jié)點(diǎn)偏差對比

在對不同節(jié)點(diǎn)數(shù)的情況下，計(jì)算改進(jìn)力布局算法和傳統(tǒng)力布局算法的最小節(jié)點(diǎn)偏差值，模擬退火初始溫度T為畫布邊長的一半，對比實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 最小節(jié)點(diǎn)偏差對比

由圖4 可知，傳統(tǒng)力布局算法和改進(jìn)力布局算法的最小節(jié)點(diǎn)偏差都隨著節(jié)點(diǎn)數(shù)的增加而降低，并且改進(jìn)算法的最小節(jié)點(diǎn)偏差均小于傳統(tǒng)力布局算法的最小節(jié)點(diǎn)偏差，證明了改進(jìn)算法相比傳統(tǒng)力布局算法的節(jié)點(diǎn)偏差更小，更加符合美學(xué)標(biāo)準(zhǔn)，也證明了利用節(jié)點(diǎn)偏差-迭代次數(shù)關(guān)系映射來控制數(shù)據(jù)可視化過程能夠有效提高布局效果。

4 結(jié)論

力布局算法的優(yōu)化方法基于傳統(tǒng)力布局算法的可視化效果問題所在，利用布局算法的美學(xué)標(biāo)準(zhǔn)來對節(jié)點(diǎn)偏差進(jìn)行計(jì)算，在迭代過程中不斷進(jìn)行節(jié)點(diǎn)偏差的計(jì)算，并結(jié)合退火公式，使其以一定的概率跳出當(dāng)前的循環(huán)并輸出布局的最優(yōu)解。經(jīng)過與傳統(tǒng)力布局算法的對比實(shí)驗(yàn)表明，改進(jìn)算法的可視化效果有明顯的提升，并且節(jié)點(diǎn)偏差值更小，布局更符合美學(xué)標(biāo)準(zhǔn)，印證了節(jié)點(diǎn)偏差值可以有效反映出可視化布局的效果，利用節(jié)點(diǎn)偏差來控制迭代的進(jìn)行可以對力布局算法進(jìn)行優(yōu)化改進(jìn)。

由于迭代過程中加入了節(jié)點(diǎn)偏差的計(jì)算和節(jié)點(diǎn)初始位置的隨機(jī)性，改進(jìn)算法的執(zhí)行時(shí)間相對來說有所增加且實(shí)驗(yàn)結(jié)果可能有所偏差，因此在后續(xù)的研究工作中需要對以上不足進(jìn)行改進(jìn)。