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

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

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

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

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