力導向布局算法的數據可視化優化方法

王藝洋，黃 濤

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

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

1 相關技術

1.1 D3.js

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

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

1.2 力導向布局算法

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

力導向布局算法是繪制一般網狀結構的常用方法[14]。該算法以力導向模型作為基礎，利用圖的結構計算圖形的層次，而無需對上下文信息再進行分析處理。力導向繪圖可以用于展示關系圖的結點之間的關系，將結點分布到畫布上的合理位置，比如描述企業之間的關系、社交網絡中的人際關系等[15]。

力導向布局算法中的引力與斥力的計算公式分別如式（1）和（2）所示：

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

式（2）中，d同為節點之間的笛卡爾距離；H為彈簧力的倔強系數；Li為第i層的默認彈簧長度，且Li/Li+1=I，即第i層和第i+1 層的邊長比值為一個固定常數I。

1.3 模擬退火算法原理

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

2 改進的力布局算法

2.1 節點偏差與迭代關系映射

在力導向布局算法中，形成的初始布局里節點位置是隨機分布的，并在不斷的迭代過程中，以一定的速度更新節點坐標，并在引力與斥力的不斷作用下，形成最終的布局效果。在對力導向布局算法的研究中發現，在節點數較少的情況下，迭代停止前，已經達到良好的布局效果；在節點數較多的情況下，迭代停止時還未達到較好的布局效果，因此如果可以動態地調整迭代次數，則對布局效果可以起到優化作用。

文中在遵循布點算法美學標準的基礎上，采用節點偏差作為布局效果的評價參數，將節點偏差與迭代次數形成關系映射，整合到力導向布局算法中，在布局過程中，采用節點偏差值作為退火參數決定迭代的進行。美學標準中最佳分布距離和節點偏差表示分別如式（3）和（4）所示：

式（3）中，Acr 為整個畫布的面積，Nnode表示當前節點數，distance 表示最佳節點距離。

式（4）中，Dx,i和Dx,i+1分別表示當前節點和下一節點的x軸坐標，Dy,i和Dy,i+1分別表示當前節點和下一節點的y軸坐標。

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

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

若此次節點移動后的最小節點偏差優于上次，則接受此次移動；反之則以一定的概率p接受此次移動，且概率p隨著迭代次數的增加逐漸降低。p的值越小，表明如果進行下一次迭代，則出現更小節點偏差值的概率越低。

2.2 改進算法流程描述

改進算法的數據可視化流程如圖1 所示。

圖1 可視化流程圖

輸入：各節點初始位置坐標、畫布面積。

輸出：各節點最終位置坐標、數據布局圖。

1）對輸入的各節點坐標數據進行初步計算，得到初始化布局，根據式（3）得到最佳分布距離；

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

3）每次迭代完成后更新節點的位置，并且根據式（4）得到最小節點偏差；

4）將最小節點偏差代入式（5）中進行迭代概率的計算；

5）當迭代次數達到閾值或式（5）中得到的概率p＜Random(0,1)時，跳出布局算法，得到最終的數據布局圖。迭代次數閾值設為500 次。

3 實驗分析

3.1 布局的美學標準

圖布局就是將當前節點的位置與目標節點通過連線連接起來進行展示。將復雜的數據形成易于觀察的可視化布局并不簡單。清晰可觀的展示數據和圖的結構，并且展示和操作過程流暢，是當前圖的布局算法研究的重心所在。對于這些要求，圖布局有一套美學標準，用來衡量一個圖布局算法的可視化效果優良，具體有四個原則。

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

2）直線原則：邊線應該盡量為直線，避免出現曲線、直線共存的現象，同時單個節點的邊線數盡可能不要超過節點數；

3）對稱性原則：繪制中心節點網絡時，將具有相同結構的子節點圍繞中心節點進行平衡布局；

4）節點集中原則：節點分布不能過于分散，盡量多個節點集中在中心節點附近。

3.2 實驗結果和分析

3.2.1 可視化效果對比

實驗采用D3.js 可視化工具進行數據可視化的實現，為了更加清晰地對可視化效果進行對比，選取的實驗節點數量為500，模擬退火初始溫度T設為畫布邊長的一半。傳統力布局算法和改進算法的可視化效果分別如圖2 和圖3 所示。

圖2 傳統力導向布局算法可視化效果

圖3 改進算法可視化效果

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

3.2.2 最小節點偏差對比

在對不同節點數的情況下，計算改進力布局算法和傳統力布局算法的最小節點偏差值，模擬退火初始溫度T為畫布邊長的一半，對比實驗結果如圖4所示。

圖4 最小節點偏差對比

由圖4 可知，傳統力布局算法和改進力布局算法的最小節點偏差都隨著節點數的增加而降低，并且改進算法的最小節點偏差均小于傳統力布局算法的最小節點偏差，證明了改進算法相比傳統力布局算法的節點偏差更小，更加符合美學標準，也證明了利用節點偏差-迭代次數關系映射來控制數據可視化過程能夠有效提高布局效果。

4 結論

力布局算法的優化方法基于傳統力布局算法的可視化效果問題所在，利用布局算法的美學標準來對節點偏差進行計算，在迭代過程中不斷進行節點偏差的計算，并結合退火公式，使其以一定的概率跳出當前的循環并輸出布局的最優解。經過與傳統力布局算法的對比實驗表明，改進算法的可視化效果有明顯的提升，并且節點偏差值更小，布局更符合美學標準，印證了節點偏差值可以有效反映出可視化布局的效果，利用節點偏差來控制迭代的進行可以對力布局算法進行優化改進。

由于迭代過程中加入了節點偏差的計算和節點初始位置的隨機性，改進算法的執行時間相對來說有所增加且實驗結果可能有所偏差，因此在后續的研究工作中需要對以上不足進行改進。