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

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

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

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

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