不完備信息系統(tǒng)中的知識(shí)表示與約簡(jiǎn)算法研究.pdf

1、在自然科學(xué)、社會(huì)科學(xué)和工程技術(shù)的很多領(lǐng)域中，人們都不同程度地要面對(duì)不確定性和不完備信息的處理問(wèn)題。數(shù)據(jù)是信息的載體，由于數(shù)據(jù)采集過(guò)程中各種因素的干擾或數(shù)據(jù)存儲(chǔ)介質(zhì)的損壞等原因，從實(shí)際系統(tǒng)中采集到的數(shù)據(jù)常常不夠精確甚至不夠完整。通過(guò)對(duì)數(shù)據(jù)附加純數(shù)學(xué)上的主觀假設(shè)，或者直接刪除含有缺失數(shù)據(jù)的實(shí)例來(lái)回避這種不確定性，往往會(huì)導(dǎo)致獲得的模型由于先驗(yàn)假設(shè)難以被滿足而失去應(yīng)用意義，或者不能真實(shí)反映現(xiàn)實(shí)系統(tǒng)的特性。
　　粗糙集理論是一種刻劃不完整性

2、和不確定性的數(shù)學(xué)工具，能有效地分析和處理不精確、不一致、不完整等各種不完備信息，并從中發(fā)現(xiàn)隱含的知識(shí)，揭示潛在的規(guī)律。本文主要研究基于粗糙集理論的不完備信息系統(tǒng)框架下的知識(shí)粒度刻畫和知識(shí)獲取問(wèn)題，主要工作與結(jié)論如下:
　　(1)關(guān)于極大相容塊的構(gòu)造。極大相容塊是不完備信息系統(tǒng)的最小知識(shí)單元。盡管基于極大相容塊的粗糙集模型可以更高的精度對(duì)目標(biāo)概念進(jìn)行近似，獲取系統(tǒng)約簡(jiǎn)時(shí)也不改變系統(tǒng)原有的拓?fù)浣Y(jié)構(gòu)，但極大相容塊的構(gòu)造相對(duì)于相似類要復(fù)雜

3、得多。為此，本文通過(guò)定義區(qū)分關(guān)系及其布爾函數(shù)，利用布爾推理技術(shù)實(shí)現(xiàn)了極大相容塊的構(gòu)造和獲取。證明了極大相容塊與構(gòu)造的布爾公式的素蘊(yùn)含存在一一對(duì)應(yīng)關(guān)系，這種基于布爾推理技術(shù)的極大相容塊獲取方法有助于人們對(duì)極大相容塊本質(zhì)的理解和不完備信息系統(tǒng)中的知識(shí)獲取。
　　(2)關(guān)于不完備系統(tǒng)中的約簡(jiǎn)。約簡(jiǎn)是基于粗糙集理論的數(shù)據(jù)降維、壓縮，以及知識(shí)獲取的重要技術(shù)手段。針對(duì)不完備系統(tǒng)，與以往基于相似關(guān)系（相容關(guān)系）不同，本文基于區(qū)分關(guān)系等價(jià)地重新定

4、義了各類約簡(jiǎn)，并構(gòu)造了相應(yīng)的區(qū)分函數(shù)，證明了區(qū)分函數(shù)的素蘊(yùn)涵與約簡(jiǎn)的一一對(duì)應(yīng)關(guān)系，給出了求解各類約簡(jiǎn)的理論方法。
　　(3)關(guān)于約簡(jiǎn)算法。眾所周知，在粗糙集理論中，最優(yōu)約簡(jiǎn)的求解是一個(gè)NP-困難問(wèn)題。導(dǎo)致該問(wèn)題的主要原因是屬性的組合爆炸。高效的約簡(jiǎn)算法是粗糙集理論應(yīng)用于知識(shí)發(fā)現(xiàn)的基礎(chǔ)。為了有效地求解各類約簡(jiǎn)，本文證明了約簡(jiǎn)問(wèn)題等價(jià)于一個(gè)集合的極小覆蓋問(wèn)題，并利用成熟的集合極小覆蓋問(wèn)題求解方法——拉格朗日乘子法實(shí)現(xiàn)約簡(jiǎn)問(wèn)題的求解。這