一種基于深度優(yōu)先的概念格并行構(gòu)造模型.pdf

1、形式概念分析是一種對(duì)數(shù)據(jù)進(jìn)行分析的工具，概念格是形式概念分析理論中的核心數(shù)據(jù)結(jié)構(gòu)。近年來(lái)，它已在知識(shí)發(fā)現(xiàn)、軟件工程、機(jī)器學(xué)習(xí)、信息檢索等領(lǐng)域得到了廣泛的應(yīng)用。 在概念格的應(yīng)用過程中，造格算法具有很重要的地位。概念格所具有的完備性一方面使得格的構(gòu)造不受數(shù)據(jù)或?qū)傩耘帕写涡蚝蜆?gòu)造方法的影響，最終的形式是唯一的，這是其主要優(yōu)點(diǎn)；但另一方面，正是由于概念格是一種完全格，使得對(duì)于適當(dāng)大小的數(shù)據(jù)，它所對(duì)應(yīng)的格結(jié)構(gòu)也是非常龐大的。因此，單純的依

2、靠改進(jìn)算法本身來(lái)大幅度提高格的構(gòu)造效率已變得幾乎不可能。如何較快的從幾乎是海量數(shù)據(jù)的形式背景中構(gòu)造概念格仍然是目前形式概念分析領(lǐng)域研究的一個(gè)重點(diǎn)和難點(diǎn)。 隨著近年來(lái)高性能并行計(jì)算技術(shù)的成熟和高性能并行計(jì)算機(jī)費(fèi)用的降低，為解決概念格應(yīng)用中的這一問題提供了一個(gè)新的思路，即利用并行計(jì)算機(jī)的計(jì)算與存儲(chǔ)能力進(jìn)行分布式并行造格。 為此，本文在已有的各種概念格構(gòu)造算法或模型的基礎(chǔ)上，重點(diǎn)對(duì)概念格的并行構(gòu)造進(jìn)行了研究。通過對(duì)格的構(gòu)造過程

3、的分析，發(fā)現(xiàn)在插入對(duì)象時(shí)將其內(nèi)涵以深度優(yōu)先的方式從下而上的與原格中節(jié)點(diǎn)做交集，根據(jù)交的結(jié)果進(jìn)而采取相應(yīng)的動(dòng)作；另外，在做交集的過程中，對(duì)滿足一定條件的節(jié)點(diǎn)設(shè)置標(biāo)志位，可以降低新增對(duì)象時(shí)節(jié)點(diǎn)的比較次數(shù)，從而降低造格的時(shí)間復(fù)雜度。在此基礎(chǔ)上，設(shè)計(jì)并實(shí)現(xiàn)了一種基于深度優(yōu)先的概念格漸進(jìn)式構(gòu)造算法(簡(jiǎn)稱AICACLBDF)。之后，將該構(gòu)造算法并行化，得到一個(gè)基于深度優(yōu)先的概念格并行構(gòu)造模型。 實(shí)驗(yàn)證明，本文提出的基于深度優(yōu)先的概念格構(gòu)造算

4、法和并行構(gòu)造模型是有效的，在時(shí)間復(fù)雜性上優(yōu)于傳統(tǒng)的漸進(jìn)式造格算法Godin，有效的提高了造格的效率，尤其是當(dāng)新增對(duì)象(新增節(jié)點(diǎn))的內(nèi)涵與原格特征域的交集(相似率)較小時(shí)，算法的優(yōu)越性更加明顯。 本文的主要貢獻(xiàn)如下： 1、設(shè)計(jì)并實(shí)現(xiàn)了基于深度優(yōu)先的概念格漸進(jìn)式構(gòu)造算法，對(duì)算法進(jìn)行了性能分析，在實(shí)驗(yàn)的基礎(chǔ)上，將其與傳統(tǒng)的漸進(jìn)式造格算法Godin算法進(jìn)行比較。 2、設(shè)計(jì)了一種基于深度優(yōu)先的概念格并行構(gòu)造模型，對(duì)該并行構(gòu)