基于reduct理論的數(shù)據(jù)描述.pdf

1、數(shù)據(jù)描述是一類特殊的數(shù)據(jù)挖掘任務(wù):根據(jù)用戶需求,將定義在符號(hào)域上的信息系統(tǒng)(數(shù)據(jù)集合)約簡(jiǎn)為人可閱讀的具有不同簡(jiǎn)潔程度的文本,同時(shí),對(duì)約簡(jiǎn)過(guò)程中產(chǎn)生的例外進(jìn)行分析.這個(gè)任務(wù)與認(rèn)知心理學(xué)的"規(guī)則+例外"原理一致,它有三個(gè)要點(diǎn):(1)根據(jù)用戶需求獲得解答;(2)不同簡(jiǎn)潔程度的文本;(3)例外分析.該文使用粗糙集理論中的reduct理論作為工具,形式化的闡述數(shù)據(jù)描述任務(wù),并解決相應(yīng)的計(jì)算問(wèn)題.直接使用正區(qū)域與邊緣區(qū)域描述規(guī)則與例外不符合人的認(rèn)

2、知,為了準(zhǔn)確刻畫"規(guī)則+例外"模型,該文將其修改為認(rèn)知正區(qū)域與認(rèn)知邊緣區(qū)域.由于正區(qū)域是reduct理論的基礎(chǔ),并且對(duì)給定信息系統(tǒng)唯一,而認(rèn)知正區(qū)域不滿足唯一性條件,因此,我們重新定義與證明了基于正區(qū)域定義的所有概念與性質(zhì).用戶通常希望給定需求下描述盡量簡(jiǎn)潔,我們用基于認(rèn)知正區(qū)域的reduct定義文本粒子,作為數(shù)據(jù)集合的簡(jiǎn)潔描述.傳統(tǒng)粗糙集理論的研究一般不關(guān)心邊緣區(qū)域的結(jié)構(gòu),而"例外"與邊緣區(qū)域密切相關(guān).因此,我們?cè)敿?xì)的研究了邊緣區(qū)域的

3、結(jié)構(gòu)與性質(zhì),以了解"例外"空間的結(jié)構(gòu),為例外分析奠定基礎(chǔ).為了有效鑒別例外,我們?cè)O(shè)計(jì)了一種特殊的差別矩陣來(lái)分析邊緣區(qū)域的結(jié)構(gòu)和例外的形成過(guò)程,并提出基于core屬性的例外鑒別方法.Core與reduct是Reduct理論中的兩個(gè)基本概念.Core有一個(gè)重要性質(zhì):如果一個(gè)屬性是core屬性,從信息系統(tǒng)中刪除這個(gè)屬性,必然導(dǎo)致邊緣區(qū)域的改變.這個(gè)性質(zhì)是計(jì)算例外的基礎(chǔ).此外,reduct與core之間存在一種特殊的關(guān)系:基于給定信息系統(tǒng)的re

4、duct構(gòu)成的新信息系統(tǒng),其中所有屬性均為core屬性.這暗示著,如果我們能夠計(jì)算出信息系統(tǒng)的reduct,那么從這個(gè)reduct中逐步刪除屬性,即可生成不同簡(jiǎn)潔程度的文本與派生例外.對(duì)大規(guī)模數(shù)據(jù)構(gòu)成的信息系統(tǒng),使用該方法進(jìn)行數(shù)據(jù)描述的先決條件是尋找快速的可以根據(jù)需求計(jì)算reduct的算法.該文在分析前人算法的基礎(chǔ)上,發(fā)現(xiàn)計(jì)算reduct空間的中間表示是影響算法效率的關(guān)鍵,為此,提出了一種樣本個(gè)數(shù)呈線性的計(jì)算reduct的樹表示算法,并

5、且,在這種表示下,計(jì)算reduct理論的其他概念同樣有效.我們證明,這個(gè)算法對(duì)reduct完備,且與基于屬性序reduct算法等價(jià).該論文的主要成果是:1.基于樹表示的reduct、core等基本概念的快速計(jì)算方法,其復(fù)雜性與樣本個(gè)數(shù)呈線性關(guān)系.2.提出"認(rèn)知正區(qū)域"與"認(rèn)知邊緣區(qū)域"以刻畫"規(guī)則+例外"模型,并證明了其性質(zhì).3.對(duì)邊緣區(qū)域進(jìn)行了詳細(xì)分析,證明其性質(zhì),并設(shè)計(jì)一種特殊的差別矩陣分析邊緣區(qū)域的結(jié)構(gòu)和例外產(chǎn)生的原因.4.提出基