概念格的分布并行處理及約簡構(gòu)造研究.pdf

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

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

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

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

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