【文章內(nèi)容簡介】 包含與T；上近似：D和T的交集為非空；無關(guān)：D和T的交集為空。對下近似建立確定性的規(guī)則，對上近似建立不確定性的規(guī)則(包含可信度)，對無關(guān)情況則不存在規(guī)則。 數(shù)據(jù)挖掘與知識發(fā)現(xiàn)談到數(shù)據(jù)挖掘，必須提到另外一個名詞：數(shù)據(jù)庫中的知識發(fā)現(xiàn)（Knowledge Discovery in Database, KDD）。1989年8月在美國底特律召開的第十一屆國際人工智能聯(lián)合會議的專題討論會議上首次出現(xiàn)KDD這個術(shù)語。隨后的幾十年，開展了數(shù)次KDD專題討論會，匯集來自各個領(lǐng)域的研究人員和應(yīng)用開發(fā)者，集中討論數(shù)據(jù)統(tǒng)計、海量數(shù)據(jù)分析算法、知識表示、知識運用等問題。關(guān)于KDD與Data Mining 的關(guān)系，有許多不同的看法。我們可以從這些不同的觀點中了解數(shù)據(jù)挖掘的技術(shù)含義。 把KDD看成數(shù)據(jù)挖掘的一個特例既然數(shù)據(jù)挖掘系統(tǒng)可以在事務(wù)數(shù)據(jù)庫、文本數(shù)據(jù)、空間數(shù)據(jù)庫、數(shù)據(jù)倉庫、關(guān)系型數(shù)據(jù)庫等數(shù)據(jù)挖掘知識，那么數(shù)據(jù)庫中的KDD就是屬于數(shù)據(jù)挖掘的一個特例[17]。這是早期比較流行的觀點，在許多文獻(xiàn)可以看到這種說法。因此，從這個方面理解，我們把從數(shù)據(jù)庫等存儲方式中挖掘有用知識的過程稱為數(shù)據(jù)挖掘。這種說法是為了強(qiáng)調(diào)說明數(shù)據(jù)挖掘在數(shù)據(jù)庫等數(shù)據(jù)形式上的多樣化。 數(shù)據(jù)挖掘存在于KDD過程中為了達(dá)成共識，在《知識發(fā)現(xiàn)與數(shù)據(jù)進(jìn)展》中，F(xiàn)AYYD等知名學(xué)者對Data Mining與KDD的給出了全新定義以便將兩者區(qū)分開來。（1）在Data Mining時知識發(fā)現(xiàn)在可接受的計算效率限制內(nèi)通過一定的算法生成特定模式的一個步驟。（2）KDD是從信息數(shù)據(jù)庫中識別可理解的、潛在有用的、新穎的、有效的模式的過程。人們一般認(rèn)為KDD是由三個階段組成：數(shù)據(jù)預(yù)備；數(shù)據(jù)挖掘；最終解釋與表達(dá)。我們可以清楚的明白知識庫或者用戶可以與數(shù)據(jù)挖掘進(jìn)行交互。 這種觀點得到大多數(shù)學(xué)家認(rèn)同，它是具有的合理性的。我們雖然可以從數(shù)據(jù)倉庫等源數(shù)據(jù)中進(jìn)行知識挖掘，但是這些源數(shù)據(jù)和數(shù)據(jù)庫技術(shù)都是有相關(guān)的。因此知識發(fā)現(xiàn)具有一個更廣義的定義，它包括模式生成、數(shù)據(jù)選擇、數(shù)據(jù)集成、數(shù)據(jù)挖掘、數(shù)據(jù)轉(zhuǎn)換、數(shù)據(jù)清洗及評估等一系列步驟。這樣，我們把一些基本功能構(gòu)建的系統(tǒng)化協(xié)同工作系統(tǒng)看作是知識發(fā)現(xiàn)，而這個系統(tǒng)中的一個關(guān)鍵的部分則是數(shù)據(jù)挖掘。將數(shù)據(jù)挖掘作為知識發(fā)現(xiàn)的關(guān)鍵步驟來看待，可以使我們更輕松容易的進(jìn)行重點研究，有效地解決問題。 數(shù)據(jù)挖掘系統(tǒng)的結(jié)構(gòu)示意圖 數(shù)據(jù)挖掘與知識發(fā)現(xiàn)相近似有許多人認(rèn)為，知識發(fā)現(xiàn)與數(shù)據(jù)挖掘只是名字的不一樣，其實它們的含義是一樣[18]。實際上，在當(dāng)前的許多文獻(xiàn)資料中，人們?nèi)匀徊粎^(qū)分地使用這兩個術(shù)語。一些人說，數(shù)據(jù)挖掘在數(shù)據(jù)庫界更流行，而知識發(fā)現(xiàn)在人工智能界使用率更高。所以，數(shù)據(jù)挖掘有狹義和廣義的定義。從狹義的觀點上來看，我們可以定義從一定形式的數(shù)據(jù)源中檢測知識的過程稱為數(shù)據(jù)挖掘。所以數(shù)據(jù)挖掘的概念雖然在不同的技術(shù)層面上進(jìn)行理解，但是它的要點還是在數(shù)據(jù)源中挖掘知識。接著我們從廣義的觀點來看，從大型數(shù)據(jù)源（可能是不確定性的、有噪聲的、不完全的等存儲形式）中，挖掘隱藏在數(shù)據(jù)背后不無人知的，卻對人們非常有用的信息知識的過程稱為數(shù)據(jù)挖掘。所以也有人稱數(shù)據(jù)挖掘為知識挖掘。. . . . .第3章 粗糙集理論粗糙集理論的觀點是“知識（人的智能）就是一種對對象進(jìn)行分類的能力”，這里的“對象”是指我們所能言及的任何事物，比如時間、抽象概念、過程、狀態(tài)和事物等，也就是說，我們稱論域為知識必須與具體或抽象世界的特定語境相關(guān)的各種分類模式聯(lián)系在一起，論域一般是一個非空的有限集合。 粗糙集理論的基本概念 信息集在粗糙集理論中，信息系統(tǒng)A中每個個體u∈U用一個信息集（information set）表示InfA（u）={（a，a（u））：a∈A}，對應(yīng)著數(shù)據(jù)表A中元素u所在的行。兩個個體u，w可能有相同的信息集InfA（u）= InfA（w），在這種情況下我們稱這兩個個體是A不分明的（Aindiscernible），關(guān)系IND（A）={(u,w): InfA（u）= InfA（w）}稱為A不分明關(guān)系（不可區(qū)分關(guān)系，不可分辨關(guān)系）（Aindiscernibility relation），它是一個等價關(guān)系。符號[u]A表示關(guān)系ind（A）中包含u的等價類。對任何的B∈A也可以定義不分明的概念。B信息集定義為InfB（u）={（a，a（u））：a∈B}；B不分明關(guān)系定義為ind（B）={(u,w): InfB（u）= InfB（w）}，由B不分明關(guān)系中的等價類形成B可定義集。集合A中的屬性定義全域U中的概念。一個概念X∈U稱為A可定義的，是指對于每個u∈U，或者[u]A∈X或者[u]A∈U\X。也就是說，概念X是A可定義的相當(dāng)僅當(dāng)X是等價類的并，即X=U{[u]A：u∈X}，A可定義的集合有下面屬性：他們在集合論意義上的并集，交集和補(bǔ)集都是A可定義的，也就是說，A可定義的集合形成一個域。根據(jù)信息集的定義，我們接下來就要對粗糙集理論的重要思想，上近似、下近似和邊界值進(jìn)行講解。 集合的上近似，下近似與邊界值粗糙集理論是基于傳統(tǒng)的集合理論衍生出，它把知識分類嵌套到集合內(nèi)，作為集合組成的一部分。根據(jù)傳統(tǒng)的方法來判斷一個對象a 是否屬于集合X，我們可以分成3種情況:對象a 可能屬于也可能不屬于集合X；對象a 肯定不屬于集X；對象a 肯定屬于集合X。 粗糙集的粗略圖通過我們所掌握的關(guān)于論域的知識進(jìn)行集合的劃分，這種劃分不是絕對的是相對的。有一個非空的有限集合U，我們稱之為論域，I 為U 中的一個等價類關(guān)系，即關(guān)于U 的知識，則二元對 K = (U，I ) 稱之為集合U的一個近似空間。假設(shè)X為集合U 的一個子集，x 為集合U 中的一個對象，所有與x 不可區(qū)分的對象所組成的一個集合設(shè)為I (x )，也就是說，該等效類是由x 決定的，我們也可以理解為I (x ) 中的每個對象都與對象x 有同樣的特征屬性。對于每個子集XU和一個等價關(guān)系I ∈IND (K)，都可以定義兩個子集。集合X 關(guān)于I ： (3. 1)完全屬于集合X的對象組成的集合，我們稱為下近似，有時也稱之為X 的正區(qū)，記作POS (X )。同樣的，由肯定不屬于X 的對象組成的集合稱為X 的負(fù)區(qū)，記作N EG (X )。 集合X 關(guān)于I ： (3. 2)所有與X 相交且非空的等價類I (x ) 的并集就是I* (X )，也就是那些可能屬于集合X 的對象所組成的最小的集合。顯然，I* (X ) + N EG (X ) = 論域U。 集合X ： (3. 3)BND (X ) 為集合X 的上近似與下近似之差。如果BND (X ) 是空集，則稱X 關(guān)于I 是清晰的(crisp )；反之如果BND (X ) 不是空集，則稱集合X 為關(guān)于I 的粗糙集( rough set)。 粗糙集理論的優(yōu)點粗糙集方法的簡單實用性是令人驚奇的，它能在創(chuàng)立后的不長時間內(nèi)得到迅速應(yīng)用是因為具有以下特點：(1) 粗糙集是以分類為主并以不可分辨關(guān)系為基礎(chǔ)，而模糊集則是基于元素對集合的隸屬程度大小，強(qiáng)調(diào)集合自己本身的含混性。(2) 粗糙集也是一個使用便捷的數(shù)據(jù)分析方法。它可以求得知識的最小表示而且能保留關(guān)鍵信息的，只需對數(shù)據(jù)進(jìn)行化簡；能揭示概念間的簡單模式，判斷數(shù)據(jù)與數(shù)據(jù)間的依賴關(guān)系；最終從數(shù)據(jù)中挖掘其規(guī)則知識。(3) 粗糙集是不要先了解知識的。處理不確定信息的常用方法是概率統(tǒng)計和模糊集方法，但這些方法都是要先了解數(shù)據(jù)信息或知識等，如概率分布和模糊隸屬函數(shù)等，其實這些數(shù)據(jù)并不是那么容易可以獲得的。而粗糙集分析方法不需要任何先驗信息，利用數(shù)據(jù)本身就可以推理和決策了。 屬性約簡在實際問題中，我們常常遇到數(shù)據(jù)約簡[19]的問題——在保持決策表的基本性質(zhì)的前提下刪除冗余的數(shù)據(jù)，運用Rough Set理論進(jìn)行數(shù)據(jù)約簡是在保持決策屬性和條件屬性之間的依賴關(guān)系不發(fā)生變化的前提下對決策表進(jìn)行簡化，包括屬性約簡和屬性值約簡。前者是在原始決策表上，刪除冗余屬性，使得決策規(guī)則更簡潔，有更高的適應(yīng)性；后者是在前者的基礎(chǔ)上，在決策規(guī)則中刪除冗余的條件屬性，得到不含冗余屬性的決策規(guī)則。而本文則主要是使用到屬性約簡。 屬性依賴?決策系統(tǒng)是一個三元組Ad=（U，A，d），其中（U，A）是信息系統(tǒng)，d是決策屬性，d：U→Vd，d A。當(dāng)ind（A）ind（nhcuj7d3）時，決策屬性d和條件屬性集A之間的關(guān)系可以用函數(shù)依賴A nhcuj7d3來表示；當(dāng)ind（A）ind（d）不成立時，將個體集限制在集合POSA（d）={u∈U | [u]A∈[u]d}上時，函數(shù)依賴A nhcuj7d3還是成立。??通常決策屬性是有一定的依賴度（依賴度的取值范圍為[0，1]），而不一定是完全依賴條件屬性。： () 屬性約簡在IS系統(tǒng)（U，A）中，屬性集合A中的子屬性都是對U有一定的分類能力，但是A（或它的子集BA）的分類能力可能與它的子集相同，也就是說A中可能有些屬性是冗余的。下面我們就要討論這個問題。(1) 如果屬性a∈B滿足ind（B）=ind（B{a}），則稱a是可約去的；否則稱a是不可約去的。(2) 如果任意a∈B都是B中部可約去的，則稱屬性集B是獨立的，否則B是相關(guān)的。(3) 如果B`B是獨立的，且ind（B`）=ind（B），則稱B`為B的一個約簡。因此，一個約簡是保持劃分的屬性集合。也就是說，一個約簡是指能使的論域中的元素在分類相同的情況下屬性集合的最小子集，分類的冗余屬性是不屬于約簡的。(4) 我們把B中所有不可約去的屬性稱為B的核（core），記為core（B）。()式中，red（B）是B的所有約簡族。因為核是所有約簡的交集，它包含在每個約簡當(dāng)中，刪除核中的任何屬性都會影響劃分，所以，從某種意義上說，核是最重要的屬性子集。?在決策系統(tǒng)Ad=（U，A，d）中，如果我們給定一個依賴B d（其中BA），d可能不依賴整個集合B，而僅僅依賴B的子集B`，我們往往對這個子集感興趣。為解決這個問題，我們需要定義相對約簡（relative reduct）。(5) 如果屬性a∈B滿足POSB（d）=POS（B{a}）（d），則稱屬性a∈B在B中是d可約去的；否則稱a∈B在B中是d不可約去的。(6) 如果屬性集B中所有的屬性都是d不可約去的，則稱B是d獨立的。(7) 如果B`∈B是d獨立的且滿足POSB（d）=POSB`（d），則稱B`是一個B的d約簡。(8) 我們把B中d不可約去的屬性稱為B的d核，：()式中，redd（B）是B的d約簡。如果ind（d）=ind（B），那么相對約簡就退化為前面的普通約簡了，所以我們下面只在決策系統(tǒng)中討論相對約簡。在決策系統(tǒng)Ad=（U，A，d）中。屬性a∈C的重要性是將該屬性刪去后對決策影響的度量，：()可以簡單表示為σ(a)。顯然0≤σ(a) ≤1，σ(a)越大屬性a越重要。 信息熵信息熵(Information Entropy)[20]是在數(shù)學(xué)上非常抽象的一個概念，在這里不妨把信息熵看成一種特定信息的出現(xiàn)概率也可以理解為離散隨機(jī)事件的出現(xiàn)概率。如果一個系統(tǒng)是有序的，信息熵就較低；反之，如果一個系統(tǒng)是混亂無章的，信息熵就高。信息熵也可以看成是一個系統(tǒng)有序化程度的尺度。 根據(jù)著名學(xué)者Bennett對Demon的解釋[21]，信息的銷毀我們認(rèn)為是一個不可逆過程，所以銷毀信息完全符合熱力學(xué)的第2定律。而信息的產(chǎn)生，則是為引入負(fù)熵的一個過程。常言道，當(dāng)一種信息被傳播得更廣泛的時候，則表明它出現(xiàn)概率更高，也可以說，該信息被關(guān)注的程度更高。那么我們認(rèn)為，從信息被傳播的情況來看，信息熵也可以表示為一個信息的價值。這樣我們通過信息熵來衡量信息價值高低的。 知識粒度 基于粗糙集理論的知識粒度表示粗糙集理論把知識看作是對論域的劃分，從而使知識具有了顆粒性。一般稱知識對應(yīng)的劃分模式為知識粒度或信息粒度，簡稱為粒度。知識具有粒度的，知識是通過等價關(guān)系的等價類來表示顆粒狀結(jié)構(gòu)。之所以會有知識表示的粗糙性就是因為知識的這種顆粒狀。與其他的方法（如模糊集方法、統(tǒng)計方法）相比，粗糙集方法都是以顆粒狀的知識為主要特征來進(jìn)行知識的處理，嘗試從數(shù)據(jù)的結(jié)構(gòu)下手，挖掘更多對我們有用的知識。目前，粗糙集理論已廣泛應(yīng)用于過程控制、故障診斷、模式識別、機(jī)器學(xué)習(xí)及關(guān)系數(shù)據(jù)庫中的知識獲取等各種應(yīng)用領(lǐng)域。在此對粗