Reduct理論

前言

Pawlak研究Rough Sets的原始動(dòng)機(jī)是針對(duì)數(shù)據(jù)集合（決策表），找到一種介于嚴(yán)格統(tǒng)計(jì)學(xué)和隨意經(jīng)驗(yàn)之間的能夠更好地描述知識(shí)不確定性的嚴(yán)謹(jǐn)方法。然而，由于基于Rough Sets描述知識(shí)不確定性的度量Roughness只與給定的決策表相關(guān)，因此，Roughness能否真實(shí)描述決策表相對(duì)應(yīng)的問(wèn)題世界，取決于給定的決策表對(duì)于問(wèn)題世界的概括程度。在以泛化為目標(biāo)的統(tǒng)計(jì)機(jī)器學(xué)習(xí)中，如果樣本集是由對(duì)問(wèn)題世界的有限次觀測(cè)構(gòu)成的，那么，該樣本集同樣需要滿(mǎn)足一個(gè)表示“概括程度”的條件：樣本集合與問(wèn)題世界同分布，這是討論泛化問(wèn)題的基礎(chǔ)。Rough Sets中的Roughness與統(tǒng)計(jì)學(xué)的概率定義在形式上有些相似，但是，兩者的本質(zhì)有所不同，這一點(diǎn)，我們?cè)诒緯?shū)的第1章中作了說(shuō)明。這種本質(zhì)上的不同導(dǎo)致我們無(wú)法從Roughness進(jìn)一步推廣并且定義類(lèi)似于統(tǒng)計(jì)學(xué)中分布這樣的概念，這意味著，Rough Sets不具備從有限觀測(cè)（給定數(shù)據(jù)集合）推測(cè)問(wèn)題世界的理論基礎(chǔ)。另外，由于Roughness來(lái)源于給定的數(shù)據(jù)集合，因此，這個(gè)不確定度量取決于且僅僅取決于給定的數(shù)據(jù)集合。這一點(diǎn)與模糊集等依賴(lài)主觀經(jīng)驗(yàn)的不確定描述方法也不相同。這些原因，使得Roughness是否是問(wèn)題世界的真實(shí)描述，不得不依賴(lài)于給定數(shù)據(jù)集合對(duì)問(wèn)題世界的概括程度。更進(jìn)一步，考慮到Roughness所依據(jù)的基礎(chǔ)——等價(jià)關(guān)系對(duì)數(shù)據(jù)集合的限制——符號(hào)集合，那么把從給定決策表獲得的Roughness作為描述問(wèn)題世界知識(shí)不確定性的度量，其可信度就更存在疑問(wèn)了。這是本書(shū)為什么沒(méi)有像大多數(shù)有關(guān)論著那樣以Rough Sets為題的原因所在。

內(nèi)容概要

本書(shū)系統(tǒng)介紹了基于用戶(hù)需求的Reduct理論。主要內(nèi)容包括Reduct理論、Reduct典型算法、用戶(hù)需求描述、基于用戶(hù)需求的Reduct理論、 Reduct與特征選擇、數(shù)據(jù)描述的“規(guī)則+例外”模型以及基于邊緣區(qū)域的例外分析等。其中數(shù)據(jù)描述的“規(guī)則+例外”模型源自認(rèn)知科學(xué)，不僅與數(shù)據(jù)挖掘密切相關(guān)，而且與用戶(hù)需求密切相關(guān)。    本書(shū)適合從事機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、人工智能、信息處理研究和應(yīng)用的科技人員學(xué)習(xí)參考。

書(shū)籍目錄

第1章  概述  1.1  Rough的含義  1.2  Reduct  1.3  Reduct 計(jì)算  1.4  用戶(hù)需求描述  1.5  次屬性定理  1.6  基于用戶(hù)需求的最優(yōu)Reduct計(jì)算  1.7  規(guī)則+例外  1.8  符號(hào)機(jī)器學(xué)習(xí)  1.9  特征選擇  1.10  小結(jié)第2章  Reduct理論與計(jì)算  2.1  引言    2.1.1  初等范疇與基本范疇    2.1.2  集合的近似    2.1.3  信息系統(tǒng)的知識(shí)表示    2.1.4  信息系統(tǒng)的屬性約簡(jiǎn)    2.1.5  信息系統(tǒng)的范疇約簡(jiǎn)    2.1.6  決策表的知識(shí)表示    2.1.7  決策表的屬性約簡(jiǎn)    2.1.8  決策表的范疇約簡(jiǎn)    2.1.9  決策表約簡(jiǎn)  2.2  差別矩陣原理    2.2.1  信息系統(tǒng)的差別矩陣    2.2.2  決策表的差別矩陣  2.3  Reduct計(jì)算    2.3.1  基于屬性獨(dú)立性的約簡(jiǎn)算法    2.3.2  基于正區(qū)域的約簡(jiǎn)算法    2.3.3  基于互信息的約簡(jiǎn)算法（MIBARK算法）    2.3.4  基于差別矩陣原理的約簡(jiǎn)算法    2.3.5  基于先驗(yàn)知識(shí)的約簡(jiǎn)算法  2.4  小結(jié)第3章  用戶(hù)需求描述  3.1  屬性的用戶(hù)偏好    3.1.1  屬性的定量評(píng)價(jià)描述    3.1.2  屬性的定性評(píng)價(jià)描述  3.2  屬性定量評(píng)價(jià)與定性評(píng)價(jià)之間的關(guān)系  3.3  屬性子集的用戶(hù)偏好    3.3.1  基本性質(zhì)    3.3.2  屬性子集的定量評(píng)價(jià)    3.3.3  屬性子集的定性評(píng)價(jià)  3.4  Reduct的用戶(hù)偏好  3.5  小結(jié)第4章  基于差別矩陣的屬性序Reduct算法  4.1  屬性序  4.2  屬性序Reduct算法及性質(zhì)    4.2.1  基本概念    4.2.2  屬性序Reduct算法    4.2.3  算法解的完備性及唯一性  4.3  基于自由屬性的屬性序Reduct算法    4.3.1  基本概念    4.3.2  基于自由屬性的Reduct算法    4.3.3  算法解的完備性  4.4  基于差別矩陣初等運(yùn)算的屬性序Reduct算法    4.4.1  差別矩陣的初等運(yùn)算    4.4.2  基于初等運(yùn)算的Reduct算法    4.4.3  基于初等運(yùn)算的屬性序Reduct算法    4.4.4  基于條件偏好關(guān)系的屬性序Reduct算法  4.5  小結(jié)第5章  基于屬性?值樹(shù)的屬性序Reduct算法  5.1  基本屬性?值樹(shù)及生成算法    5.1.1  初等范疇和基本范疇    5.1.2  樹(shù)結(jié)構(gòu)    5.1.3  基本屬性?值樹(shù)    5.1.4  基本屬性?值樹(shù)的生成算法  5.2  完全屬性?值樹(shù)  5.3  正區(qū)域的屬性?值樹(shù)表示    5.3.1  屬性?值樹(shù)表示下正區(qū)域的定義與性質(zhì)    5.3.2  屬性?值樹(shù)表示下正區(qū)域  5.4  封閉屬性?值樹(shù)    5.4.1  死子樹(shù)與活子樹(shù)    5.4.2  封閉屬性?值樹(shù)表示  5.5  Core屬性的屬性?值樹(shù)表示    5.5.1  屬性?值樹(shù)表示下Core屬性的定義與性質(zhì)    5.5.2  屬性?值樹(shù)表示下Core的計(jì)算  5.6  Reduct的屬性?值樹(shù)表示    5.6.1  Reduct的計(jì)算方法    5.6.2  Reduct算法的完備性  5.7  屬性值?Core與屬性值?Reduct的屬性?值樹(shù)表示    5.7.1  屬性值?Core的屬性?值樹(shù)表示    5.7.2  屬性值?Reduct的屬性?值樹(shù)表示  5.8  屬性序Reduct算法與屬性?值樹(shù)Reduct算法的等價(jià)性  5.9  關(guān)于樹(shù)結(jié)構(gòu)的討論  5.10  小結(jié)第6章  屬性序空間與Reduct空間之間的關(guān)系  6.1  滿(mǎn)足用戶(hù)偏好最優(yōu)Reduct的計(jì)算復(fù)雜度  6.2  屬性序偶與屬性序Reduct算法的形式化描述    6.2.1  基本概念    6.2.2  屬性序Reduct算法的形式化描述    6.2.3  屬性序偶的性質(zhì)  6.3  鄰近屬性序偶Reduct的基本判定    6.3.1  差別元素聚合命題    6.3.2  等價(jià)類(lèi)分解命題    6.3.3  鄰近屬性序偶基本判定定理  6.4  鄰近屬性序偶Reduct判定規(guī)則    6.4.1  無(wú)條件判別規(guī)則    6.4.2  子區(qū)間判別規(guī)則    6.4.3  單向與雙向判別規(guī)則  6.5  小結(jié)第7章  次屬性原理及屬性?值樹(shù)次屬性算法  7.1  次屬性    7.1.1  基本概念    7.1.2  次屬性原理    7.1.3  次屬性定理  7.2  屬性?值樹(shù)次屬性算法及算法的完備性    7.2.1  差別矩陣與屬性?值樹(shù)表示    7.2.2  屬性?值樹(shù)次屬性算法    7.2.3  屬性?值樹(shù)次屬性算法的完備性  7.3  小結(jié)第8章  任意屬性序偶Reduct判定  8.1  屬性序之間的關(guān)系及屬性移動(dòng)基本規(guī)則  8.2  次屬性變化規(guī)律  8.3  任意屬性序偶Reduct是否相同的判定問(wèn)題    8.3.1  任意屬性序偶Reduct基本判定    8.3.2  任意屬性序偶Reduct判定  8.4  屬性范序與屬性序偶Reduct判定    8.4.1  基本概念    8.4.2  基于屬性范序的屬性序偶Reduct判定  8.5  小結(jié)第9章  基于用戶(hù)偏好最優(yōu)Reduct計(jì)算  9.1  滿(mǎn)足用戶(hù)偏好的最優(yōu)Reduct  9.2  次屬性定理與最優(yōu)Reduct計(jì)算    9.2.1  最優(yōu)Reduct的定量描述    9.2.2  次屬性定理與搜索策略    9.2.3  最優(yōu)Reduct逼近算法    9.2.4  算法復(fù)雜性分析  9.3  小結(jié)第10章  特征選擇與Reduct計(jì)算  10.1  特征選擇概述    10.1.1  最優(yōu)特征子集的搜索問(wèn)題    10.1.2  特征和特征子集評(píng)價(jià)問(wèn)題    10.1.3  特征子集的產(chǎn)生方式    10.1.4  特征選擇和學(xué)習(xí)算法之間的關(guān)系    10.1.5  特征選擇和特定應(yīng)用之間的關(guān)系  10.2  Reduct與特征選擇之間的關(guān)系    10.2.1  基本概念    10.2.2  Reduct的搜索與評(píng)價(jià)問(wèn)題    10.2.3  Reduct的產(chǎn)生方式以及與學(xué)習(xí)算法之間的關(guān)系    10.2.4  基于刪除策略的Reduct計(jì)算    10.2.5  基于添加+刪除搜索策略的Reduct計(jì)算    10.2.6  基于添加策略的Reduct計(jì)算  10.3  小結(jié)第11章  數(shù)據(jù)描述的“規(guī)則+例外”模型  11.1  認(rèn)知心理學(xué)關(guān)于概念的研究    11.1.1  概念結(jié)構(gòu)的假說(shuō)    11.1.2  概念形成  11.2  規(guī)則歸納    11.2.1  基本搜索策略    11.2.2  樣例與規(guī)則相結(jié)合的方法    11.2.3  常用歸納算法    11.2.4  規(guī)則歸納小結(jié)  11.3  粒度與粒計(jì)算    11.3.1  粒度    11.3.2  粒計(jì)算  11.4  例外分析    11.4.1  例外與“Outlier”    11.4.2  例外分析的應(yīng)用    11.4.3  基于建模的例外分析方法    11.4.4  基于模式的例外分析方法    11.4.5  關(guān)于例外分析的討論  11.5  規(guī)則+例外模型    11.5.1  脊椎動(dòng)物世界——一個(gè)例子    11.5.2  “規(guī)則＋例外”模型研究  11.6  正區(qū)域和邊緣區(qū)域擴(kuò)展研究    11.6.1  正區(qū)域    11.6.2  認(rèn)知正區(qū)域與認(rèn)知邊緣區(qū)域  11.7  文本粒度與文本粒子    11.7.1  文本粒度    11.7.2  文本粒子  11.8  小結(jié)第12章  邊緣區(qū)域與例外分析  12.1  邊緣區(qū)域（BR）的結(jié)構(gòu)研究    12.1.1  例子    12.1.2  BR的結(jié)構(gòu)    12.1.3  “活的”與“死的”CPOS——關(guān)于邊緣區(qū)域的進(jìn)一步討論  12.2  基于BR的差別矩陣研究    12.2.1  BR的差別矩陣    12.2.2  合并問(wèn)題    12.2.3  CPOS的死活問(wèn)題  12.3  基于CPR的Reduct計(jì)算  12.4  Core屬性與例外鑒別    12.4.1  Core屬性    12.4.2  Core屬性的性質(zhì)    12.4.3  差別矩陣中Core的分布  12.5  基于差別矩陣的例外鑒別    12.5.1  從PRAS中鑒別例外    12.5.2  從正區(qū)域的PR中鑒別例外    12.5.3  例子和討論  12.6  基于概念結(jié)構(gòu)的例外鑒別    12.6.1  例——基于原型的方法    12.6.2  例——基于異類(lèi)之間相似度的方法  12.7  小結(jié)參考文獻(xiàn)算法索引

章節(jié)摘錄

插圖：Rough在Rough Sets中的含義可以解釋為一種Rough度量，用于表示知識(shí)的不確定程度。目前存在多種關(guān)于Rough度量的描述方法，這里僅就Pawlak給出的原始描述方法進(jìn)行討論，其他描述方法大同小異。首先考慮Pawlak對(duì)于矛盾對(duì)象的描述： 如果決策表中兩個(gè)對(duì)象關(guān)于條件屬性集合中所有屬性的值完全相同，但關(guān)于決策屬性集合中有些屬性的值不同，則稱(chēng)這兩個(gè)對(duì)象是矛盾的。例如，對(duì)于兩個(gè)記錄在案的病例，如果病人的癥狀都是發(fā)燒、咳嗽，但醫(yī)生的最后診斷分別為感冒和肺炎，那么這兩個(gè)病例是一對(duì)有矛盾的對(duì)象。其中，兩個(gè)病例表示兩個(gè)對(duì)象，“發(fā)燒”和“咳嗽”是兩個(gè)條件屬性，“疾病”是決策屬性，“感冒”和“肺炎”是對(duì)象關(guān)于決策屬性的屬性值。顯然，這個(gè)例子中的兩個(gè)對(duì)象關(guān)于條件屬性“發(fā)燒”和“咳嗽”的屬性值完全相同，即這兩個(gè)對(duì)象都以“是”作為它們關(guān)于條件屬性“發(fā)燒”和“咳嗽”的屬性值，但是，它們關(guān)于決策屬性的屬性值不同，因此，這兩個(gè)病例是矛盾的對(duì)象。Pawlak對(duì)于矛盾對(duì)象的刻畫(huà)采用了嚴(yán)格的數(shù)學(xué)形式。在給出矛盾對(duì)象的定義之前，首先引入了上、下近似兩個(gè)概念盡管用“矛盾對(duì)象集合”（即，用表示知識(shí)的Rough程度）描述知識(shí)的不確定性，具有直觀的優(yōu)點(diǎn)，但是，對(duì)于與“知識(shí)（規(guī)則）”相關(guān)的正區(qū)域的描述，則不得不基于“矛盾對(duì)象集合”來(lái)間接定義。我們猜測(cè)，作為數(shù)學(xué)家的Pawlak大概不喜歡這種使用次重要概念間接描述更重要概念的方式，也不喜歡在定義階段就將兩個(gè)概念相互聯(lián)系，由此，他引進(jìn)了上下近似的概念，從而，可以分別獨(dú)立地定義正區(qū)域和邊緣區(qū)域。，然后基于這兩個(gè)概念，決策表的論域被劃分為兩個(gè)部分，分別稱(chēng)為正區(qū)域（positive region）和邊緣區(qū)域（boundary region），并且正區(qū)域和邊緣區(qū)域滿(mǎn)足： （1）正區(qū)域和邊緣區(qū)域的交集為空集； （2）正區(qū)域和邊緣區(qū)域的并集為論域。其中只有邊緣區(qū)域與矛盾對(duì)象的描述有關(guān)。為了便于讀者理解Pawlak關(guān)于矛盾對(duì)象的描述思想，在這一章，我們采用直觀的方法對(duì)兩個(gè)區(qū)域進(jìn)行刻畫(huà)，精確的定義參見(jiàn)本書(shū)第2章。

編輯推薦

《Reduct理論》：中國(guó)計(jì)算機(jī)學(xué)會(huì)學(xué)術(shù)著作叢書(shū)

圖書(shū)封面

評(píng)論、評(píng)分、閱讀與下載

---

    Reduct理論 PDF格式下載

---