Reduct理論

前言

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

內(nèi)容概要

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

書籍目錄

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

章節(jié)摘錄

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

編輯推薦

《Reduct理論》：中國計算機學會學術著作叢書

圖書封面

評論、評分、閱讀與下載

---

    Reduct理論 PDF格式下載

---