應用粗糙計算（簡體書）

《應用粗糙計算》系統總結了作者近幾年在粗糙集理論、模型、算法和應用方面的研究成果，以分類決策中人們普遍使用的若干一致性假設為主線，論述了等價關係、鄰域關係、模糊關係以及優勢關係下的粒化和近似問題，進而分析了各種關係誘導出來的近似空間的不確定性度量問題。本書的特點是理論分析、算法設計和實際應用相結合，將粗糙集理論應用於模式識別、機器學習和數據挖掘的算法設計，形成了特徵依賴性分析、特徵選擇、屬性約簡、樣本約簡以及規則學習等算法。
《應用粗糙計算》補充了集合論的基礎知識，自成體系，既可作為應用數學和信息科學的高年級本科生和研究生的教材，也可作為決策科學和信息科學領域的研究人員與工程人員的參考書。·

《應用粗糙計算》注重從實際應用中抽象理論問題，進而基于理論模型開發實用的學習算法，從而將理論和應用緊密結合起來。
全書共分七章，第1章綜述粗糙集研究的現狀和存在的問題；第2章介紹集合論和模糊集合論的基本知識；第3～6章分別介紹經典粗糙集模型、鄰域粗糙集模型、模糊粗糙集模型、優勢關系粗糙集模型及其應用，建立了六類一致性假設的數學模型；第7章給出這六類一致性假設的信息熵模型。本書由胡清華，于達仁著。

《信息科學技術學術著作叢書》序
前言
第1章 緒論
1.1 複雜數據的知識發現
1.2 混合數據分類建模的不確定性分析
1.2.1 數據類型及其信息結構分析
1.2.2 混合數據分類的不確定性分析
1.3 基於粗糙集的分類不確定性刻畫
1.3.1 粗糙計算模型的發展
1.3.2 粗糙計算算法設計現狀
1.3.3 現有粗糙集模型處理混合數據存在的問題
1.4 對當前若干粗糙計算觀點的評述
1.4.1 粗糙計算中分類能力定義的評述
1.4.2 粒計算、詞計算與粗糙計算的多樣性

第2章 集合論基礎
2.1 集合
2.2 模糊集

第3章 Pswlak粗糙集模型
3.1 粗糙集理論的基本概念
3.2 約簡和相對約簡
3.3 基於粗糙集的分類建模
3.3.1 屬性約簡
3.3.2 規則提取
3.3.3 分類決策

第4章 度量空間分類學習的鄰域粗糙集模型
4.1 基於鄰域粒化的混合數據分析模型
4.1.1 鄰域粗糙集
4.1.2 鄰域決策系統
4.1.3 關於鄰域粗糙集的理解
4.1.4 基於鄰域模型的多粒度可分性分析
4.2 基於鄰域粗糙集的邊界樣本選擇
4.3 基於鄰域粗糙集的混合數據屬性約簡
4.3.1 算法設計
4.3.2 測試分析
4.4 基於鄰域一致性分析的屬性約簡
4.4.1 鄰域依賴度指標存在的問題
4.4.2 鄰域一致性指標及特性分析
4.4.3 算法設計
4.4.4 測試分析
4.5 基於鄰域覆蓋約簡的分類規則學習

第5章 模糊分類學習的模糊粗糙集模型
5.1 模糊算子
5.2 模糊粗糙集
5.3 基於核函數的模糊粗糙逼近
5.3.1 模糊粗糙集與核學習機器的潛在聯繫
5.3.2 核模糊粗糙集模型
5.3.3 基於核的分類逼近
5.4 基於核模糊逼近的屬性依賴性分析
5.5 核模糊粗糙集與ReliefF算法的關係
5.6 魯棒的軟模糊粗糙集模型
5.7 基於核模糊逼近的混合數據屬性約簡
5.7.1 算法設計
5.7.2 測試分析
5.8 基於核模糊逼近的樣本加權採樣
5.8.1 KNN中樣本選擇研究現狀
5.8.2 FAIR-KNN算法設計
5.8.3 實驗分析

第6章 有序分類的優勢關係粗糙集模型
6.1 有序決策表
6.2 優勢關係粗糙集和有序分類
6.3 有序決策表約簡
6.4 模糊優勢關係粗糙集
6.4.1 模糊優勢關係
6.4.2 模糊優勢決策近似
6.5 多類型屬性共存時的有序決策分析模型
6.6 近似質量分析和有序決策約簡
6.7 應用分析

第7章 近似空間的信息度量
7.1 等價關係信息系統的信息度量
7.1.1 信息熵
7.1.2 Pawlak近似空間的信息度量
7.2 鄰域系統的信息度量
7.3 模糊近似空間的信息度量
7.3.1 模糊關係的信息熵及性質
7.3.2 Pawlak近似空間的Shannon熵與模糊熵的關係
7.3.3 模糊近似空間的模糊信息度量
7.4 有序分類的不確定性度量
7.4.1 清晰序關係下的信息度量
7.4.2 模糊優勢關係下的信息度量
7.5 基於信息熵的混合數據約簡方法
7.6 依賴度、一致度和互信息之間的關係
參考文獻·

第1章 緒論
1.1 復雜數據的知識發現
知識是人類認識和改造客觀世界的結果，也是推動人類社會進步的動力。從生產和科學實踐的經驗中發現和提煉一般規律是知識發現的主要途徑。當前，由于信息技術的發展以及大型生產和科研活動的開展，在許多領域，如深空探測、基因分析、社會調查和工業過程監控等領域，出現了容量龐大的數據系統。這些數據蘊涵了豐富的有用信息。如何從海量的數據中獲取有價值的、新穎的知識成為信息學科一個重要的研究課題。
顯然，通過人工分析大規模數據是不現實的，研究利用計算機從海量數據中自動發現知識無論對科學研究還是社會生產生活都具有重要的價值。美國Mjol-sness 和DeCoste 在Science 雜志上系統分析了機器學習和知識發現技術在科學研究各個階段扮演的角色，認為機器學習和知識發現技術能夠在各個方面協助研究人員加速科研進程。自動知識發現技術在信息檢索、圖像理解、文本分類、工業過程監測和故障診斷等領域正在發揮越來越重要的作用。
計算機自動知識發現面臨的主要困難是信息的多樣性、不確定性和不一致性。其中，多樣性表現為數據結構的多樣性和數據值域的多樣性。在工業監控和金融分析等領域存在大量時序數據庫；在天文觀測、資源探測、城市規劃和交通管理等領域存在大量的空間數據庫；在網絡環境中存在海量文本、圖像以及聲像等非結構化數據。數據值域的多樣性則表現為描述對象的屬性的值域是復雜多樣的，可分為名義值、整型值、實數值、模糊值、集值、區間值等。有時部分對象的某些特征的值還是缺失的。大量結構復雜、形式多樣的數據給知識發現帶來了挑戰。本書將集中分析關系型數據庫中多種類型變量共存時的分類知識發現問題。
分類學習是知識發現的一大類任務。在實際應用中，描述分類的屬性往往不是單一類型的，而是多種類型的變量共存的。以美國加州大學機器學習與智能系統研究中心收集的分類學習測試數據（http ：∥archive.ics.uci.edu/ml/index．html）為統計對象，發現無論在物理學、生命科學、醫療診斷領域還是在社會統計、金融分析、信息安全和設備健康監測等領域都存在大量由符號變量和數值變量共同描述的分類任務。
在醫療診斷中，如心律不齊、心臟病、乳腺癌、肝炎、甲狀腺病、皮膚病的自動分類學習都涉及混合數據問題。由匈牙利心臟病研究所Janosi、瑞士蘇黎世醫學院Steinbrunn等收集的4個心臟病數據包含900多個病例的76個特征，這些特征既有如性別、胸部疼痛位置、胸部疼痛類型、是否抽煙等符號屬性，也包含年齡、血壓、血糖濃度、最大心跳數、抽煙史等數值屬性。
在物理學研究領域，由Sterling和Buntine提供的鋼材退火數據集“Annea-ling”記錄了798次退火試驗，每次試驗由5個數值變量和33個離散變量描述，其中部分屬性值沒有記錄，標記為“？”。
在社會統計領域，由Becker從美國1994年人口統計數據中抽取的48854人的年收入調查表中包含5個表示年齡、每周工作時間、資本收益情況等連續變量和9個表示工作類型、受教育程度、婚姻狀況、職業、社會關系、人種、出生國等符號變量。由美國統計局收集，Lane和Kohavi公布的人口收入調查數據集則包含199523人的收入記錄，每人由7個連續變量、33個符號變量描述。
商業領域的信譽卡發放評估和產品營銷數據庫中往往數值屬性和符號屬性共存。例如，德國信譽卡數據集由7個數值屬性，13個定性屬性描述；澳大利亞信譽卡分析數據則采集了6個連續屬性和9個離散變量。
此外，在天文物理研究中的空間天氣預報、地震預報分析、電力設備的故障診斷、股票市場分析等大型復雜決策問題中，所需處理的數據都混合了名義、數值、區間值和模糊值的變量。研究混合數據知識發現的模型和算法無論就知識發現的理論研究，還是許多領域的應用需求都具有重要的價值。
1.2 混合數據分類建模的不確定性分析
分類是人類智能行為的一種主要形式，從大量樣本數據中發現分類知識、建立分類模型是知識發現的一大類任務。分類學習面臨的主要困難是數據樣本中的隨機性、模糊性和不一致性給分類學習帶來的不確定性因素。
1.2.1 數據類型及其信息結構分析
一般而言，給定的分類學習樣本由一個數據矩陣描述。矩陣的一行（aj1，aj2，…，aji，…，ajN，dj）記錄了一個學習樣本，其中aji表示第j個樣本在i個特征上的取值，dj則是第j個樣本的決策。混合分類數據是指屬性的值域以及決策的值域是多種形式的。廣義上講，屬性的值域可以為圖像、聲音、文本、矩陣、時序、數值和字符；狹義上講，屬性的值域為名義型字符、有序型字符、數值量、區間值或者模糊值。本書研究的問題是指描述分類問題的屬性為符號型、數值型、區間值或者模糊型的混合數據。
不同類型的數據中蘊涵了不同的信息結構，表達了樣本之間不同側面的信息。名義變量由若干個狀態表示，這些狀態之間既沒有數量關系，也沒有等級的序關系，如對象的性別、顏色。有序符號變量則由有序的若干等級來表示，變量的各值之間存在全序或者偏序結構，如國民的受教育程度，由符號描述的年齡、身體狀態等。名義變量和有序符號變量有時候統稱為符號變量、離散變量或者定性變量等。數值變量在實數或者實數的一個子集上取值，如描述病人狀態的變量：血壓、血糖濃度、體溫等和描述設備狀態的變量：溫度、流量、壓力、流速等。在某些特殊的場合，人們還會采用區間值和模糊值來描述分類問題，如股票每日的開盤價、收盤價所構成的區間、最低價和最高價構成的區間，每日氣溫的最低溫度和最高溫度構成的區間等。
在分類學習中，當決策的類別為名義變量時，稱之為一般的分類問題。在某些情況下，決策值之間存在序結構，則稱之為有序決策問題或者排序問題，如投稿的決策：錄用、修改和拒稿。
顯然，不同的屬性中蘊涵的信息結構和可以實施的運算是不同的。就單個屬性而言，可以用數軸等價的分析屬性的信息結構，如圖1.1所示。
在名義屬性描述的信息空間中，對象x和對象y要么相等，要么不等，不存在任何過渡的情況，也就是說，樣本的取值不是連續的。在名義屬性空間中，可以定義離散距離函數Δ（x，y）＝1，x≠y0，x＝y在有序離散屬性空間中的對象，不僅可以知道對象x和對象y是否相等，而且還知道x和y的大小關系。在某些情況下，將有序變量按照序結構轉化為一串整數，稱之為整型變量，那么實數域上的某些運算也是有意義的。
在數值屬性上可以實施實數域上的各種數學運算，實數域上的運算也將誘導數值空間的各種結構。首先，實數是有序的，我們可以比較不同對象在某一特征上的大小，因此實數域中的對象可以建立序結構；其次，實數域是連續的，對象之間的距離可以在實數域上取任一值，實數域的連續性使得對象之間存在鄰域結構。由于實數軸的連續性，數軸上的各點的鄰域構成的鄰域簇相互交疊、關聯，形成了實數空間的覆蓋。如果在同一屬性空間上允許不同對象的鄰域大小不同，在不同的維度空間上也采用不同的鄰域大小，那么可以形成多維空間中十分復雜的信息結構。最后，實數域的連續性也導致了信息結構的模糊性，我們說對象x和對象y在某一數值特征上取值相近或者說對象y比對象x要大得多，這種描述都是模糊的，可以在實數空間中建立模糊鄰域和模糊序結構，如圖1.2和圖1.3所示。
圖1.2給出一維實數空間中與對象z近鄰的經典子集和模糊子集。如果采用不對稱模糊鄰域和不同維度上大小不一致的模糊鄰域，那么可以得到形式多樣、結構復雜的鄰域系統。
圖1.3給出一維數值空間中比對象z大的經典子集和遠比對象z大的模糊子集。在圖1.3（b）中對象y遠比z大的隸屬度為1，而對象x遠比z大的隸屬度為0。基于不同的模糊隸屬度函數，可以得到一系列遠比z大的模糊集。
當名義變量、有序變量和數值變量共存于某一分類問題中，那么不同類型變量蘊涵的信息結構的組合就更豐富了。這些信息結構在不同的領域、不同的應用中反映了問題的不同側面，全面理解數據中蘊涵的信息需要構造不同的學習算法以發現混合數據中蘊涵的信息結構。
1.2.2 混合數據分類的不確定性分析
處理不確定性是人的認知和推理的重要能力，也是人工智能、機器學習、知識發現和智能決策所面臨的主要困難。數據的隨機性、信息的不完備性和決策的不一致性是導致這一困難的主要原因。
隨機性是指發生在數據采集、傳輸和存儲過程中的偶然因素引起數據偏離其真實值的現象。在實驗分析和數據錄入過程中，由于記錄或打字錯誤，最終分析的數據中難免會存在錯誤信息。在基于傳感器系統的對象監測中，由于環境的干擾、傳感器分辨精度有限或者傳感器失效，也會在測量的真實值中引入噪聲信息。
由此看來，不僅描述對象的符號信息是不精確的，對象的數值屬性描述也不一定反映對象的真實狀態。由精確數值描述的對象盡管看起來似乎得到了精確描述，但由于數據測量的隨機性使得記錄的數值在一定鄰域內的值都可能是該對象的真值。隨機性是知識發現和分類建模中引起不確定性的重要原因。
信息的不完備性體現在三個方面：其一，由于某種原因，部分對象的某些特征值沒有被測量和記錄，因此在數據矩陣中出現了空缺；其二，描述對象分類的某些重要特征沒有采集和存儲，使得利用現有的特征不足以區分各類對象，從而出現類重疊區域；其三，反映分類模型的某些模式沒有被激發，使得樣本信息不足以完整反演出分類模型。由于分類學習往往是基于現有的樣本信息估計分類模型，因此不考慮第二和第三類信息不完備性。
不一致性是分類建模復雜性的又一重要因素。回想一下人的決策過程，不難發現在面向不同類型屬性描述的決策問題時人采用了不同的一致性分析策略。
對于由名義型屬性描述的分類問題，用戶自然希望特征相同的對象歸屬于相同的決策類別，否則這些對象將不可區分。因此在分類建模時，使用了一個潛在的假設，即條件屬性取值相同的對象，其決策應該相同，否則決策是不一致的，稱為第一決策一致性假設。
當對象由數值屬性描述時，不同的對象獲得完全相同的屬性描述的概率很低，精確的屬性值在決策中將會被自然地泛化到一個區間，而不再以數值進行推理。此時人們將第一分類一致性假設泛化為：數值屬性取值相近的對象，其分類應該相同，否則分類是不一致的。我們稱之為第二決策一致性假設。當數值和符號屬性同時存在時，人們希望符號屬性取值相同，數值屬性取值相近的對象應該被歸于同一類別，否則分類是不一致的，稱之為第三決策一致性假設。
在模糊理論中，不僅需要考察對象的分類是否一致，而且還需要計算對象分類的一致性程度。此時，在考察對象的分類一致性時以對象模糊鄰域內的其他對象為參考，如果模糊鄰域內的對象分類相同則分類是一致的，否則對象分類的不一致性程度由該對象到最近的異類對象的距離決定，距離越大，則分類一致性程度越高，稱之為第四決策一致性假設。
以上四個分類一致性假設都是針對一般的分類問題而言的，面對有序決策問題時，人們使用了另外一個一致性假設：當兩個對象其他屬性完全相同時，如果對象x就屬性a而言比對象y占優，那么x的決策應該至少不比y差，否則決策是不一致的。我們稱之為第五決策一致性假設。舉例而言，當投稿x在論文寫作質量方面與投稿y相當，但x在原創性水平方面比y高，如果投稿x被錄用，那么投稿y自然也應該被錄用，否則違背了論文評判的一致性。
在決策建模中，所面臨的問題往往是不一致的。此時不僅需要知道對象的決策是否是不一致的，而且還需要精確刻畫有序決策中的不一致性程度。當兩個對象其他屬性完全相同時，如果對象x就屬性a而言比對象y占優，但是x的決策比y差，顯然，此時決策是不一致的。不一致的程度由x就屬性a而言比對象y占優的程度決定，占優的程度越大，決策的不一致性也就越大。我們稱此為第六決策一致性假設。
不一致性是分類學習面臨的主要挑戰，大量的學習算法所解決的就是分類不一致情況下的最優決策問題，如貝葉斯最優決策，決策樹葉子節點上樣本類別不一致時的處理，軟間隔支持向量機。
知識發現就是要從隨機的、不完備的和不一致的信息中提煉一般規律。隨機性、不完備性和不一致性是干擾分類學習算法、影響分類建模精度和泛化能力的主要因素，這三類不確定往往同時存在于分類數據中，因此混合數據的知識發現模型必須能夠刻畫和處理數據中的不確定性。
1.3 基于粗糙集的分類不確定性刻畫
從分類不確定分析中可知，不一致信息是分類學習面臨的主要困難，粗糙集理論是描述和處理分類不一致的有效方法。人在認識分類的不一致性時需要考察的是對象的粒子，而不是對象個體。知識是建立在粒化和概念的基礎上的，信息粒化使得人具有在部分精確（隨機性）、部分已知（不完備性）、部分一致的（不一致性）情況下做出合理決策的能力。
粗糙集正是模擬人的思維的這一特點而發展起來的粒計算模型。該理論是波蘭學者Pawlak于20世紀80年代初提出用以刻畫由不精確信息描述的分類問題中不一致性的數學工具。該方法在近十余年里得到迅速發展，成為機器學習領域十分活躍的一個分支，在屬性依賴性分析、特征子集選擇和約簡、分類知識發現等方面取得了成功。