形式背景核的有限性研究與算法實現(xiàn).pdf

1、網(wǎng)絡(luò)技術(shù)大大提高了人的生存質(zhì)量和人的素質(zhì)，使人成為社會人、全球人，同時，網(wǎng)絡(luò)的普及也給人們帶來了海量信息，大量信息在給人們帶來方便的同時也帶來了一大堆問題：第一是信息過量，難以消化；第二是信息真假難以辨識；第三是信息安全難以保證；第四是信息形式不一致，難以統(tǒng)一處理。于是人們開始考慮：“如何才能不被信息淹沒，而是從中及時發(fā)現(xiàn)有用的知識、提高信息利用率?” 面對這一挑戰(zhàn)，數(shù)據(jù)挖掘和知識發(fā)現(xiàn)技術(shù)應(yīng)運而生，并顯示出強大的生命力。由于形式

2、概念分析中的概念格具有良好的數(shù)學性質(zhì)、適合批處理和能表示概念之間的關(guān)系等特點，我們認為概念格模型可以用來作為數(shù)據(jù)挖掘的一種非常理想的工具。形式概念分析是從形式背景這一基本的數(shù)據(jù)形式開始的，因此形式背景的規(guī)模是影響概念格構(gòu)造和應(yīng)用的一個重要因素。 為此，本文對形式背景進行了較為全面、系統(tǒng)的研究，提出了形式背景核的概念和相關(guān)的限定性定理。利用形式背景核的有限元素等價地表示一類無限的形式背景，從而達到用核中元素的格快速生成新的概念格的

3、目的。主要的研究內(nèi)容涉及形式背景的提取、切分、約簡和同構(gòu)判定，以及形式背景核的代數(shù)性質(zhì)和形式背景核的構(gòu)造算法等。依據(jù)降低形式背景數(shù)據(jù)量的思想，給出了形式背景切分和約簡的具體算法，并按照對形式背景基的定義，實現(xiàn)了形式背景基的算法，給出了形式背景基性質(zhì)的證明，通過對形式背景核基本算法的研究，給出了形式背景核的改進算法，從而降低了求n階形式背景核的時間復雜度和空間復雜度，提出了n階形式背景核的限定性定理，并給出了證明。本文的目的也就是通過分析

4、概念格的數(shù)學模型、性質(zhì)，對形式背景進行系統(tǒng)的分析探討，為概念格的同構(gòu)構(gòu)造提供理論基礎(chǔ)，從而進一步將概念格應(yīng)用于數(shù)據(jù)挖掘。 本文的主要貢獻如下：(1)提出了n階形式背景核的概念，構(gòu)造了n階形式背景核的基本算法，并對基本算法進行了改進，解決了n階形式背景核構(gòu)造的基本算法的效率低的問題，給出了兩種算法的時間復雜度的對比；同時說明了形式背景核的理論意義及應(yīng)用價值。 (2)提出了形式背景核的限定性定理，通過另一個重要概念——形式背