1、粗糙集理論及其應(yīng)用2022/7/191主要內(nèi)容 粗糙集發(fā)展歷程 粗糙集的基本理論介紹粗糙集對集合理論的擴展 粗糙集的屬性約簡算法研究2022/7/192粗糙集發(fā)展歷程1970s，Pawlak和波蘭科學(xué)院、華沙大學(xué)的一些邏輯學(xué)家，在研究信息系統(tǒng)邏輯特性的基礎(chǔ)上，提出了粗糙集理論的思想。在最初的幾年里，由于大多數(shù)研究論文是用波蘭文發(fā)表的，所以未引起國際計算機界的重視，研究地域僅限于東歐各國。1982年，Pawlak發(fā)表經(jīng)典論文Rough sets，標志著該理論正式誕生。1991年，Pawlak的第一本關(guān)于粗糙集理論的專著Rough sets: theoretical aspects of reas

2、oning about data；2022/7/193粗糙集發(fā)展歷程1992年，Slowinski主編的Intelligence decision support: handbook of applications and advances of rough sets theory的出版，奠定了粗糙集理論的基礎(chǔ)，有力地推動了國際粗糙集理論與應(yīng)用的深入研究。1992年，在波蘭召開了第一屆國際粗糙集理論研討會，有15篇論文發(fā)表在1993年第18卷的 Foundation of computingand decision sciences上。2019年，Pawlak等人在ACM Communicat

3、ions上發(fā)表“Rough sets”，極大地擴大了該理論的國際影響。2022/7/194粗糙集發(fā)展歷程 20192019年，分別在日本、美國、美國、日本召開了第4-7屆粗糙集理論國際研討會。 20192019，中國分別在重慶、蘇州召開第一、二屆粗糙集與軟計算學(xué)術(shù)會議。 2019年至今，每年召開CRSSC。 2019年，在重慶召開粗糙集與軟計算國際研討會。 2019年，在瑞典召開RSCTC國際會議（偶數(shù)年會） 。 2019年，在加拿大召開RSFDGrC國際會議（奇數(shù)年會）。 2019年至今，每年召開RSKT。 2022/7/195主要內(nèi)容 粗糙集發(fā)展歷程 粗糙集的基本理論介紹 粗糙集的屬性約簡

4、算法研究2022/7/196粗糙集的基本理論介紹 1980年，德國數(shù)學(xué)家克萊因在數(shù)學(xué)：確定性的喪失中指出：數(shù)學(xué)也存在不確定性問題。確定問題的研究經(jīng)典的數(shù)學(xué)工具，如集合論不確定問題的研究拓展的數(shù)學(xué)工具，如概率論、模糊集、粗糙集等2022/7/197粗糙集的基本理論介紹不確定性隨機性模糊性不完整性不穩(wěn)定性不一致性主要的特性2022/7/198粗糙集的基本理論介紹隨機性：由于條件不能決定結(jié)果而表現(xiàn)出來的不確定性，反映了因果律的問題。解決隨機性問題的典型數(shù)學(xué)方法是概率論。模糊性：由于概念外延邊界的不清晰而表現(xiàn)出的不確定性，反映了排中律的問題。解決模糊性的典型數(shù)學(xué)方法是模糊集理論。2022/7/199粗

5、糙集的基本理論介紹自然界中大部分事物所呈現(xiàn)的信息都是：不完整的、不精確的、模糊的、含糊不清的經(jīng)典集合論和邏輯方法無法準確的描述和解決這些問題。粗糙集理論的提出，主要是為了描述并處理“含糊”信息2022/7/1910粗糙集的基本理論介紹（1）經(jīng)典集合特點：集合的邊界沒有寬度 每個元素要么屬于S，要么不屬于，具有確定性。2022/7/1911粗糙集的基本理論介紹（2）“含糊”問題的提出1904年，謂詞邏輯創(chuàng)始人G. Frege 首次提出將含糊性歸結(jié)到“邊界線區(qū)域”在論域上存在一些個體，既不能被分到某一子集上，也不能被分到該子集的補集上。2022/7/1912粗糙集的基本理論介紹（3）模糊集合的提出

6、1965年，美國Zadeh教授首次提出個體x與集合S的關(guān)系x以一定的程度屬于S。2022/7/1913粗糙集的基本理論介紹模糊集雖然解決了邊界域元素的“亦此亦彼”的現(xiàn)象，但：未給出計算含糊元素數(shù)目的數(shù)學(xué)公式未給出描述含糊元素隸屬度的形式化方法隸屬度函數(shù)本身不確定2022/7/1914粗糙集的基本理論介紹粗糙集運用集合論中的“等價關(guān)系（不可區(qū)分關(guān)系）”，將邊界線區(qū)域定義為“上相似集”與“下相似集”的差集在“真”、“假”二值之間的“含糊度”可計算給出了含糊元素數(shù)目的計算公式2022/7/1915粗糙集的基本理論介紹邊界線的不確定性模糊集用隸屬度（非精確方法）來描述粗糙集用精確的邊界線（上、下近似集

7、）來描述相互補充2022/7/1916粗糙集的基本理論介紹 主要優(yōu)點除數(shù)據(jù)集之外，無需任何先驗知識（或信息）對不確定性的描述與處理相對客觀用于分類，發(fā)現(xiàn)不準確數(shù)據(jù)或噪聲數(shù)據(jù)內(nèi)的結(jié)構(gòu)聯(lián)系【說明】：Bayes理論（先驗分布 ）、證據(jù)理論（隸屬度函數(shù)）等都需要先驗知識，具有很大的主觀性。2022/7/1917粗糙集理論在知識發(fā)現(xiàn)中的作用 在數(shù)據(jù)預(yù)處理過程中，粗糙集理論可以用于對特征更準確的提取 在數(shù)據(jù)準備過程中，利用粗糙集理論的數(shù)據(jù)約簡特性，對數(shù)據(jù)集進行降維操作。 在數(shù)據(jù)挖掘階段，可將粗糙集理論用于分類規(guī)則的發(fā)現(xiàn)。 在解釋與評估過程中，粗糙集理論可用于對所得到的結(jié)果進行統(tǒng)計評估。2022/7/191

8、8粗糙集理論的基本概念“知識”的定義使用等價關(guān)系集R對離散表示的空間U進行劃分，知識就是R對U劃分的結(jié)果?！爸R庫”的形式化定義等價關(guān)系集R中所有可能的關(guān)系對U的劃分表示為：K = (U, R)2022/7/1919粗糙集理論的基本概念“信息系統(tǒng)”的形式化定義S = U, A, V, f，U：對象的有限集A：屬性的有限集，A=CD，C是條件屬性子集，D是決策屬性子集V： ， Vp是屬性P的域f：U A V是總函數(shù)，使得 對每個xi U, q A, 有f(xi, q) Vq一個關(guān)系數(shù)據(jù)庫可看作一個信息系統(tǒng)，其“列”為“屬性”，“行”為“對象”。2022/7/1920粗糙集理論的基本概念 設(shè)PA，

9、 xi, xj U, 定義二元關(guān)系INDP稱為等價關(guān)系： 稱xi, xj在S中關(guān)于屬性集P是等價的，當(dāng)且僅當(dāng)p(xi)=p(xj)對所有的pP 成立，即xi, xj不能用P 中的屬性加以區(qū)別。2022/7/1921等價關(guān)系示例：factweatherroadtimeaccident1mistyicydayyes2foggyicynightyes3mistynot icynightyes4sunnyicydayno5foggynot icyduskyes6mistynot icynightno2022/7/1922等價關(guān)系示例：可知，U = 1, 2, 3, 4, 5, 6R = 2 weath

10、er, road, time, accident 若P = weather, road，則x IND(P) = x INDweather x INProad = 1, 3, 6, 2, 5, 4 1, 2, 4, 3, 5, 6 = 1, 2, 4, 3, 6, 5 2022/7/1923集合的上近似 & 下近似 在信息系統(tǒng)S = U, A, V, f中，設(shè)XU是個體全域上的子集，PA，則X的下和上近似集及邊界區(qū)域分別為： X是XU上必然被分類的那些元素的集合，即包含在X內(nèi)的最大可定義集； X是U上可能被分類的那些元素的集合，即包含X的最小可定義集。，則X是可定義的，否則是不可定義的，即粗糙的

11、若2022/7/1924集合的上近似 & 下近似上、下近似集將論域U劃分成三個區(qū)域：正域、邊界域和負域，其定義如下：BndP(X)是既不能在XU上被分類，又不能在U-X上被分類的那些元素的集合。2022/7/1925集合的上、下近似概念示意圖X2022/7/1926上、下近似關(guān)系舉例： X1 = u | Flu(u) = yes = u2, u3, u6, u7 RX1 = u2, u3 = u2, u3, u6, u7, u5, u8X2 = u | Flu(u) = no = u1, u4, u5, u8RX2 = u1, u4 = u1, u4, u5, u8, u6, u7由R = H

12、eadache, Temp. 劃分出來的等價類有:u1, u2, u3, u4, u5, u7, u6, u8.2022/7/1927近似精度 & 分類質(zhì)量 設(shè)S = U, A, V, f為一信息系統(tǒng)，且XU， PA，則S上X的近似精度為： 注：card(X) 表示集合X中元素個數(shù) 設(shè)S為一信息系統(tǒng)，PA，且令=X1,X2, , Xn是U的一個分類（子集族），其中XiU，則的P-下近似和 P-上近似分別表示為：2022/7/1928近似精度 & 分類質(zhì)量由屬性子集PA確定的分類的分類質(zhì)量為 ： 分類質(zhì)量表示通過屬性子集P正確分類的對象數(shù)與信息系統(tǒng)中所有對象數(shù)的比值。這是評價屬性子集P的重要性的

13、關(guān)鍵指標之一。 2022/7/1929屬性約簡 & “核” 屬性約簡(Attribute Reduction)：在一個信息系統(tǒng)S中，設(shè)是S上的一個分類，經(jīng)約簡后的最小屬性子集具有同原始屬性集相同的分類質(zhì)量，即存在RPQ，使得R() =P() ，稱之為屬性集P的-約簡，記作REDU(P) 。 所有-約簡的交集稱為-核，即CORE(P) = REDU(P)，核是信息系統(tǒng)中一系列最重要的屬性之一。 【說明】：在大多數(shù)情況下，分類是由幾個甚至一個屬性來決定的，而不是由關(guān)系數(shù)據(jù)庫中的所有屬性的微小差異來決定。屬性約簡及核的概念為提取系統(tǒng)中重要屬性及其值提供了有力的數(shù)學(xué)工具，而且這種約簡是本著不破壞原始數(shù)

14、據(jù)集的分類質(zhì)量的，通俗地說，它是完全“保真”的。 2022/7/1930主要內(nèi)容 粗糙集發(fā)展歷程 粗糙集的基本理論介紹 粗糙集的屬性約簡算法研究2022/7/1931利用啟發(fā)式搜索進行屬性約簡幾個概念：正區(qū)域：在信息系統(tǒng)S=(U, CD, V, f)中，設(shè)D*= X1,X2,Xm，屬性子集PC關(guān)于決策屬性D的“正區(qū)域”定義為： P關(guān)于D的正區(qū)域表示那些根據(jù)屬性子集P就能分入正確類別的所有對象。2022/7/1932利用啟發(fā)式搜索進行屬性約簡相關(guān)程度： 條件屬性子集PC與決策屬性D的相關(guān)程度（也稱依賴程度）定義為： 顯然，0 k(P, D) 1。k(P, D)為計算條件屬性子集P與決策屬性D之間

15、的相關(guān)程度提供了非常有力的手段。2022/7/1933利用啟發(fā)式搜索進行屬性約簡有效值： 一個屬性pPC的有效值(significant value)定義為：【說明】：屬性p的有效值越大，說明其對條件屬性與決策屬性之間的影響越大，即其重要性也越大。 2022/7/1934利用啟發(fā)式搜索進行屬性約簡算法步驟： 第1步. a A: 計算鄰域關(guān)系a ; 第2步. 將 賦給red ； 第3步. 對任意aiA-red ， 計算 /此處定義K(D) = 0 第4步. 如果SIG(ak,red,D) 0 ,將red U ak 賦給red ， 返回第3步； 否則，返回red，結(jié)束。觀看演示2022/7/193

16、5利用啟發(fā)式搜索進行屬性約簡2022/7/1936利用啟發(fā)式搜索進行屬性約簡第1步. a A: 計算鄰域關(guān)系a ;在決策表中設(shè)置A=a1,a2,a3,a4,a5,a6,a7,a8,其中C=頭痛，胸口痛，體溫,D=流感那么，就可以設(shè)置C1=頭痛，C2=胸口痛，C3=體溫，所以 A/C1=a1,a2,a3,a4,a5,a6,a7,a8 (頭痛分類）A/C2=a1,a2,a3,a4,a6,a8,a5,a7 （胸口痛分類）A/C3=a1,a4,a2,a5,a7,a3,a6,a8 (體溫分類）2022/7/1937利用啟發(fā)式搜索進行屬性約簡 第2步. 將 賦給red ； 第3步. 對任意aiA-red

17、， 計算 /此處定義K(D) = 0 (A-C3): A/C1,C2=a1,a2,a3,a4,a6,a8,a5,a7(頭疼與胸口疼的分類并集)(A-C2): A/C1,C3=a1,a2,a3,a4,a5,a7,a6,a8(A-C1): A/C2,C3=a1,a4,a2,a5,a7,a3,a6,a8 A/C=a1,a2,a3,a4,a5,a7,a6,a8A/D=a1,a4,a5,a8,a2,a3,a6,a7 Pos _c (D)=a1Ua2Ua3Ua4 /C的正域2022/7/1938利用啟發(fā)式搜索進行屬性約簡 第2步. 將 賦給red ； 第3步. 對任意aiA-red ， 計算 /此處定義K

18、(D) = 0K（C,D）=Pos_c(D)/U=4/8=0.5 /C的依賴程度 (A-C1): A/C2,C3=a1,a4,a2,a5,a7,a3,a6,a8A/D=a1,a4,a5,a8,a2,a3,a6,a7Pos_(c-c1)D=a1,a2,a4!=Pos_c(D)K（C-C1,D）=Pos_c-c1(D)/U=3/8 /C-C1的依賴程度 SGF(c1,C,D)= K（C,D）- K（C-C1,D）=1/8 /C1的有效值2022/7/1939利用啟發(fā)式搜索進行屬性約簡第4步. 如果SIG(ak,red,D) 0 ,將red U ak 賦給red ， 返回第3步；SGF(c1,C,D)= K（C,D）- K（C-C1,D）=1/8 0/C1的有效值將c1加入到red集合中red=c1(A-C2): A/C1