第6章基於粗糙集（rough set）理論的資料探勘技術
粗糙集理論是由波蘭華沙理工大學數學家於2023年提出的一種資料分析理論，該理論在分類意義下定義了模糊性和不確定性兩個概念。是一種處理不完整資料、不精確知識的表達、學習、歸納等的一種新型數學工具。
粗集理論的重要特點是：不需要任何附加資訊或先驗知識，直接從所需處理的資料本身所提供的資訊出發找出問題的內在規律。
目前，大多數資料探勘工具軟體（如：aq系統、ids系統等）都是基於集合論開發的，其中粗糙集（rs）理論使用最廣，也最有發展前途。
由於rs是研究不精確和不確定知識的一種資料工具，如，知識的含糊性，主要包括：①術語的模糊性，如高矮；②資料的不確定性，如雜訊；③知識自身的不確定性，如規則的前後件間的依賴關係不完全可靠等。所以，它同其它不確定問題理論，如，概率統計理論中的概率分布、模糊理論不能處理不完整資料且需提供隸屬函式這種先驗知識、d-s證據理論中的基本概率賦值等相比，更具實用性。
粗集理論的主要思想：是在保持分類能力不變的前提下，通過知識約簡，匯出問題的決策或分類規則。
目前，rs理論已成功地應用於機器學習、過程控制、模式識別、資料探勘、**、故障診斷、決策分析和人工神經網路等領域，成為其它不確定理論的一種補充，有著不可替代的優越性。
1. 粗糙集理論的基本概念
（1） 知識和知識庫
設為論域，任何子集，稱為中的乙個概念或範疇。規定空集也是乙個概念。中的乙個概念族稱為關於的抽象知識，簡稱知識。
這裡，主要對上能形成劃分的那些知識感興趣。
乙個劃分f定義為：f，其中，
（顯然，乙個劃分就是一條知識）
上的一族劃分稱為關於的乙個知識庫（knowledge base）。
設是上的乙個等價關係，表示r的所有等價類構成的集合，即。表示包含元素的r等價類。
【例如】考慮一組兒童的集合，a=。則具有「相同年齡」關係的等價類如下：
====即乙個知識庫就是乙個關係系統，r是上的一族等價關係。
若等價關係族，且，則也是乙個等價關係（即p中所有等價關係的交集），稱為p上的不可區分關係（indiscernibility）,記為ind(p)，且有
1）則表示與等價關係族p相關的知識，稱為k中關於的p基本知識（p基本集）。為簡單起見，用代替。不可分辯關係概念是rs理論的基礎，它揭示出論域知識的顆粒狀結構。
的等價類稱為知識p的基本概念或基本範疇。
特別的，如果，則稱為k中關於的初等知識。的等價類為知識r的初等概念或初等範疇。
當為一知識庫，定義為k中所有等價關係的族，記作
說明k是由所有基本知識組成的集合）
【例如】一玩具積木的知識表達系統
論域，如果根據某一屬性描述這些積木情況，就可按顏色、形狀和體積分類。換言之，可以定義三個等價關係（即屬性）：顏色、形狀、體積。
按分： ---紅； ---藍； ---黃
按分： ---圓； ---方； ---三角型
按分： ---大； ---小。
由此得三個等價類：
這三個等價類均是由知識庫中的初等概念（初等範疇）構成的。它的基本範疇是初等範疇的交集構成的，如
紅色三角形
藍色方形
黃色三角形
上面是的基本範疇。
紅色大三角形
這是的基本範疇。
紅色或藍色，為的範疇。
注：（1）有些範疇在這個知識庫是無法得到的，如
說明知識庫中不存在藍色圓形，為空範疇。
說明知識庫中不存在紅色方形，為空範疇。
（2）上例容易求出、、和
（3）若乙個知識系統，，給定乙個等價關係簇，且有下列等價類：
試求：，，，
自己思考》
定義： 設和為兩個知識庫，若，即，則稱和（p和q）是等價的，記作（）。（說明和有同樣的基本範疇）
設和為兩個知識庫，當時，稱知識p（知識庫）比知識q（知識庫）更精細，或q比p更粗糙。當p比q更精細時，也稱p為q的特化，q為p的推廣。這就意味著，推廣是將某些範疇組合在一起，而特化則是將範疇分割成更小的單元。
（2）不精確範疇、近似與粗糙集
令，為上的乙個等價關係。當能表達成某些基本範疇的並時，則稱是可定義的；否則不可定義的。
可定義集是論域的子集，它可在知識庫中精確地定義。而的不可定義集不能在這個知識庫中定義。的可定義集也稱為精確集，而的不可定義集也稱為的非精確集或的粗糙集。
當存在等價關係且為精確集時，集合稱為中的精確集；當對於任何，都是粗糙集，則稱為中的粗糙集。
定義：設給定知識庫，對於每個子集和乙個等價關係，定義兩個子集：
分別稱為的下近似（lower approximation）和上近似（upper approximation）。
上下近似也可用下面的等式表達：
----由根據知識判斷肯定屬於的u中元素組成
---由根據知識判斷可能屬於的u中元素組成
集合稱為的邊界域；
稱為的正域；
稱為的負域。
顯然，【示例】應用近似集合的概念，根據粗集的定義，來研究或分析一些人的受教育程度與就業的關係問題。受教育程度與就業的情況如下表所示。
解：由受教育程度與就業情況知識表達資料表知，研究物件：
受教育的人：u=
受教育程度：四種，即等價關係，其中=， =， =， =
就業情況：兩種。
設x為定義有工作的人為一種分類子集，則有工作的人的子集=
則根據粗集的定義，有
劉，趙}
劉，趙，王，馬}
李}王，馬}
所以，根據粗集中、、、的意義，可得受教育程度與就業的情況表達如下：
根據， 規則1： if （大學）or（研究生） then （一定有工作）
根據， 規則2： if （高中、大學）or（研究生） then （可能有工作）
根據，規則3：if （高中） then （可能有、也可能無工作）
根據，規則4：if （小學）then （無工作）
定理1：（1）為可定義集當且僅當
（2）為粗糙集當且僅當
定理2：（1）
2），3）；4）；5）；67）；
定義：當且僅當
當且僅當
這裡，表示根據，肯定地屬於；表示根據，可能屬於。分別稱和為下和上成員關係。說明成員關係依賴於我們的知識，即乙個物件是否屬於乙個集合依賴於我們的知識，並且這不是絕對特性。
由此可以看出，集合（範疇）的不精確性是由於邊界的存在而引起的。集合的邊界域越大，其精確性則越低。一般而言，兩個集合x和y之間的相似程度定義為
當x和y不相交時，s（x，y）=0；當x和y完全相同時，s（x，y）=1。由此，可類似給出x關於r粗糙度。
定義精度：由等價關係定義集合的近似精度為
反映對了解集合的知識的完全程度。
其中，，表示集合的基數。
為的粗糙度。
對於空集，定義粗糙度。
2. 知識約簡
知識約簡是粗糙集理論的核心內容之一。眾所周知，知識庫中的知識（屬性）並不是同等重要的，甚至其中某些知識是冗餘的。
所謂知識約簡，是指在保持知識庫分類能力不變的條件下，刪除其中不相關或不重要的知識。知識約簡中有兩個基本概念：約簡（reduct）和核(core)。
定義：令r為一族等價關係，，如果
則稱為r中不必要的；否則為必要的。
如果每乙個都為r中必要的，則稱r為獨立的；否則稱r為依賴的。
定理：如果r是獨立的，，則p也是獨立的
定義：設，如果q是獨立的，且，則稱
q為p的乙個約簡。
顯然p可以有多種約簡。p中所有必要關係組成的集合稱為p的核，記作core(p)。
核與約簡的關係為
定理：core(p)=∩red(p)，其中red(p)表示p的所有約簡。
由此看出，核這個概念的用處有兩個方面：
● 核可以作為所有約簡的計算基礎，因為核包含在所有約簡之中，並且計算可以直接進行；
● 核可解釋為在知識約簡時它是不能消去的知識特徵集合。
【示例】 設是乙個知識庫，其中，，且
則得關係的等價類為
（注：是通過計算獲得的）
故由計算：
注：是通過計算獲得的）
說明關係為r中必要的。
對於關係，有
故是r中不必要的。
同理，也是r中不必要的，即有
但且有，所以，為獨立的且為r的乙個約簡。同理，也是獨立的且為r的乙個約簡。則乙個核core(r)=.
3. 知識的相對約簡、相對核概念
令p和q為u中的等價關係，q的p正域記為，即
所以，q的p正域是u中所有根據分類的資訊可以準確地劃分到關係q的等價類中去的物件集合。
令p和q為等價關係族，，如果
則稱為p中q不必要的；否則為必要的。為簡單起見，用代替。
資料探勘與知識發現 講稿4決策樹學習技術
第四章決策樹 decision tree 決策樹也是歸納學習中常用的一種知識表示形式，常用於分類。同時，也是發現概念描述空間的一種有效方法。決策樹的主要優點是描述簡單，分類速度快，特別適合大規模的資料處理。教學目的 掌握決策樹學習的概念 重點掌握id3學習演算法以及決策樹的構造 了解目前常用的決策樹...
資料探勘和知識發現的技術 方法及應用
概念基於internet的全球資訊系統的發展使我們擁有了前所未有的豐富資料。大量資訊在給人們帶來方便的同時也帶來了一大堆問題 第一是資訊過量，難以消化 第二是資訊真假難以辨識 第三是資訊保安難以保證 第四是資訊形式不一致，難以統一處理。資料豐富 知識貧乏已經成為乙個典型問題。data mining ...
資料倉儲與資料探勘
頻繁專案集.給定全域性專案集i和資料庫d，d中所有滿足使用者指定的最小支援度 minsupport 的專案集，即大於或等於minsupport的i的非空子集，稱為頻繁專案集 frequent itemsets 或者大專案集 large itemsets 在頻繁專案集中挑選出所有不被其他元素包含的頻繁...