概念格Hasse圖布局算法研究.pdf

1、概念格理論又稱為形式概念分析，用于概念的發(fā)現(xiàn)、排序和顯示。它作為一種用于數(shù)據(jù)組織和數(shù)據(jù)分析的形式化工具，在理論研究和實際應(yīng)用上都具有重要意義，已經(jīng)在多個領(lǐng)域獲得了成功的應(yīng)用。概念格作為形式概念分析中核心的數(shù)據(jù)結(jié)構(gòu)，本質(zhì)上描述了對象和特征之間的聯(lián)系，表明了概念之間的泛化和特化關(guān)系，其 Hasse圖則實現(xiàn)了對數(shù)據(jù)的可視化。而Hasse圖中概念結(jié)點的布局算法對概念格的可讀性、圖顯示的時間效率有著不可忽略的影響。
　　本文在研究了概念格

2、Hasse圖的經(jīng)典布局算法后，重點分析了使用回溯查找法的附加線圖布局算法，指出其中效率低下的原因，提出了直接賦值附加線圖布局算法DAAL。直接賦值附加線圖法摒棄了傳統(tǒng)的回溯查找法，采用直接賦值，間接使用概念矢量和的方法，有效地減少了給屬性集尋求矢量集的過程，提高了概念格布局的效率；而其中使用的相關(guān)概念相鄰的思想也使概念格的可讀性得到提高。本文同時提出了一種新的概念格布局優(yōu)化策略：基于線性交換的概念格Hasse圖二次布局。在移動概念結(jié)點位

3、置時，只有相鄰兩層的邊交換情況會受到直接影響，算法根據(jù)這一點對分層結(jié)構(gòu)的概念格進(jìn)行隔層取概念，獲得一層的概念后，線性交換概念結(jié)點位置，并計算交換前后相鄰兩層邊的交叉數(shù)，根據(jù)邊交叉數(shù)的變化來決定結(jié)點的位置。該二次布局算法使得概念格 Hasse圖能夠處于邊交叉數(shù)較少的狀態(tài)下，使其可讀性得到了較大提升。
　　通過在相同數(shù)據(jù)下進(jìn)行的布局算法與優(yōu)化策略的實驗，可以證明本文所提出的直接賦值附加線圖布局算法相比于傳統(tǒng)的附加線圖布局算法在時間與“