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

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

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

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