概念格建格算法的研究.pdf

1、當(dāng)今，社會(huì)已經(jīng)進(jìn)入了網(wǎng)絡(luò)信息時(shí)代，計(jì)算機(jī)與網(wǎng)絡(luò)信息技術(shù)的飛速發(fā)展使得各個(gè)領(lǐng)域的數(shù)據(jù)和信息急劇增加 (信息爆炸)，同時(shí)人類的參與使數(shù)據(jù)與信息系統(tǒng)中的不確定性更加顯著。如何有效地實(shí)現(xiàn)對(duì)數(shù)據(jù)的分析和處理，如何快速地從數(shù)據(jù)中提取出隱含的知識(shí)，長(zhǎng)期以來(lái)一直是人工智能領(lǐng)域的研究熱點(diǎn)。在此背景下誕生的知識(shí)發(fā)現(xiàn) KDD (Knowledge Discovery in Databases) 和數(shù)據(jù)挖掘 DM (Data Mining) 給人們提供了一種新

2、的認(rèn)識(shí)數(shù)據(jù)和理解數(shù)據(jù)的智能手段。 在DM和KDD諸多方法中，粗糙集理論的明顯優(yōu)勢(shì)在于不需要任何預(yù)備的或額外的有關(guān)數(shù)據(jù)信息。而概念格 ，以其完備的結(jié)構(gòu)和堅(jiān)實(shí)的理論基礎(chǔ)成為數(shù)據(jù)挖掘過(guò)程中的主要模型之一。由于概念格的完備性原因，使得尋找一種時(shí)間復(fù)雜度比現(xiàn)有算法優(yōu)秀很多的概念格構(gòu)造算法變得幾乎不可能，因此如何比較快速地從海量的形式背景中構(gòu)造概念格仍然是目前形式概念分析領(lǐng)域研究的一個(gè)重點(diǎn)和難點(diǎn)。 本文首先從方法及應(yīng)用等方面論述了知

3、識(shí)發(fā)現(xiàn)和數(shù)據(jù)挖掘的發(fā)展?fàn)顩r，重點(diǎn)介紹了粗糙集理論和形式概念分析理論在KDD中的應(yīng)用。在粗糙集理論及形式概念分析理論的基礎(chǔ)上，闡述二者之間的聯(lián)系。 接著重點(diǎn)討論了概念格的建格算法。這一章節(jié)分為兩個(gè)部分，前半部分分析了串行建格算法的原理以及一些經(jīng)典的概念格構(gòu)造算法，并提出了一種新的基于邊緣概念的建格算法。這種算法與其它傳統(tǒng)串行算法相比，最大特點(diǎn)在于邊緣概念的提出。求出邊緣概念以后，將不再依賴形式背景便可以分層構(gòu)建概念格，并且同時(shí)生成

4、概念格所對(duì)應(yīng)的Hasse圖。這一章的后半部分主要論述了適合并行計(jì)算的并行算法。隨著高性能并行計(jì)算技術(shù)的發(fā)展和成熟，利用并行計(jì)算存儲(chǔ)能力改善算法在時(shí)間和空間上的性能為解決概念格構(gòu)造問(wèn)題提供了一條新的途徑。本文分析經(jīng)典的ParallelNextClosure 算法，并改進(jìn)了多概念格合并算法。改進(jìn)的概念格橫向合并算法對(duì)于除了同類概念以外的其它特殊概念也有相應(yīng)的處理方法，從而提高了概念格橫向合并的效率。 本文的最后對(duì)并行構(gòu)造概念格的模型