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

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

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

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

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