1、自從德國(guó)的Wille教授提出了形式概念分析以來(lái)，作為形式概念分析的核心數(shù)據(jù)結(jié)構(gòu)，概念格已經(jīng)引起了人們的廣泛關(guān)注，并且已經(jīng)在知識(shí)發(fā)現(xiàn)、軟件工程、信息檢索等諸多領(lǐng)域得到了廣泛的應(yīng)用。其中，概念格的構(gòu)造是其應(yīng)用的前提?？墒怯捎诟拍罡褡陨淼耐陚湫?，構(gòu)造概念格的時(shí)間、空間復(fù)雜度一直是影響形式概念分析應(yīng)用的主要障礙。研究采用新的方法和手段來(lái)構(gòu)造概念格，就成為概念格研究的主要內(nèi)容之一。 隨著網(wǎng)絡(luò)技術(shù)特別是Internet技術(shù)的飛速發(fā)展，數(shù)據(jù)分

2、布式存儲(chǔ)與并行處理的需求越來(lái)越迫切。針對(duì)這些復(fù)雜的問(wèn)題都包含著大量子問(wèn)題的基本特點(diǎn)，再結(jié)合人類已經(jīng)積累的分析問(wèn)題與解決問(wèn)題的方法與經(jīng)驗(yàn)，可以應(yīng)用一定的并行算法，將這些復(fù)雜問(wèn)題分為既有相對(duì)的相互獨(dú)立性又有一定聯(lián)系的若干子問(wèn)題，然后將這些子問(wèn)題分別分給若干臺(tái)處理器，使得這些處理器能夠同時(shí)地解決這些子問(wèn)題。在各處理器同時(shí)解決這些子問(wèn)題的過(guò)程中，采用一定的策略對(duì)這些并行的過(guò)程進(jìn)行控制，協(xié)調(diào)它們的停止與運(yùn)行；然后將這些子問(wèn)題所得到的結(jié)果進(jìn)行整合與

3、處理，得到問(wèn)題的最終解。通過(guò)這樣的處理，可以提高解決問(wèn)題的效率，縮小解決問(wèn)題的時(shí)間。 本文主要就此領(lǐng)域的相關(guān)問(wèn)題展開系列研究，主要工作如下：隨著處理的形式背景的逐漸增大，概念格的構(gòu)造復(fù)雜度將呈指數(shù)增長(zhǎng)。現(xiàn)在已經(jīng)提出的構(gòu)造概念格的算法基本上都是針對(duì)單個(gè)概念格的。采用分而治之的策略是解決這一問(wèn)題的有效途徑之一。我們提出一種對(duì)概念格的分布處理算法，在漸進(jìn)式構(gòu)造概念格算法(如Godin算法)的基礎(chǔ)上，對(duì)形式背景進(jìn)行合理拆分，分別構(gòu)造出部

4、分概念格，對(duì)得到的部分概念格進(jìn)行合并，提出兩種合并的算法。并理論分析證明了構(gòu)造出概念格的完備性和正確性，實(shí)驗(yàn)結(jié)果表明這是一種行之有效的概念格構(gòu)造方法，為降低概念格構(gòu)造的時(shí)間復(fù)雜度提供了一種思路。 利用高性能并行計(jì)算機(jī)的計(jì)算與存儲(chǔ)能力來(lái)構(gòu)造和存儲(chǔ)是有效地解決高復(fù)雜性科學(xué)問(wèn)題的根本途徑。我們提出一種基于消息傳遞機(jī)制的Godin算法并行化方法，分析其迭代過(guò)程中的主要耗時(shí)點(diǎn)，對(duì)其采用并行處理。并行算法中無(wú)法進(jìn)行結(jié)構(gòu)體的直接發(fā)送，我們提出

5、用分治策略的方法，求得結(jié)構(gòu)體數(shù)組的長(zhǎng)度之后，將其轉(zhuǎn)化為字符類型，分別發(fā)送，并將這一思想運(yùn)用到了并行程序的設(shè)計(jì)過(guò)程中，進(jìn)一步提高了算法的并行性。該算法和直接用形式背景來(lái)漸進(jìn)式構(gòu)造概念格的算法相比，其時(shí)間復(fù)雜度會(huì)有顯著改善，性能提高30％-40％左右。 降低概念格構(gòu)造的空間復(fù)雜度，是概念格研究的另一個(gè)重要目標(biāo)，可以結(jié)合用戶興趣度來(lái)實(shí)現(xiàn)概念格的約簡(jiǎn)構(gòu)造，但是目前用戶興趣度的給定中人為因素很明顯。我們提出一種基于信息熵的約簡(jiǎn)概念格構(gòu)造算