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

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

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

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

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