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

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

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

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

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