【文章內(nèi)容簡(jiǎn)介】 系的交集）也是一種等價(jià)關(guān)系，記為，稱為P上的不可分辨關(guān)系。其中，為所有與不可分辨的對(duì)象所在的集合，即，中的每個(gè)對(duì)象都與有同樣的屬性。在分類知識(shí)中，基本等價(jià)類為其最小模塊。設(shè)基本等價(jià)類為，由U中得到，它是將U中的不可辯分關(guān)系(P)分成相互之間不可相交的子集，即。由于描述中對(duì)象的屬性都是相同的，所以之間是不可分割的。令和為兩個(gè)知識(shí)庫(kù)，若，也就是說時(shí)，則說明是等價(jià)的，即。它的涵義是：將化分的基本等價(jià)類的一樣的，描述的對(duì)象的概念也是一樣的。換而言之，知識(shí)等價(jià)類就是用不同的描述方式來描述同一的相同事實(shí)。比如說，首先令要被分類的對(duì)象的集合為，再令已經(jīng)分類后的結(jié)果放在屬性集中，若分類的結(jié)果無誤的話，則可以說和的等價(jià)類是一致的，即用劃分的等價(jià)類與用描述的分類結(jié)果。 信息系統(tǒng)四元組被稱為粗糙集理論中的一個(gè)知識(shí)系統(tǒng)，或者也可以稱為屬性—值系統(tǒng)。它是對(duì)客觀事物的一種描述。U為論域，且,用來表示，A是表示屬性的集合，且,可來表示，V為屬性值域集，是的值域，→V，是一個(gè)信息函數(shù)，它為每個(gè)對(duì)象的每個(gè)屬性賦予一個(gè)信息值，即。設(shè)為一個(gè)知識(shí)表達(dá)系統(tǒng)，且，稱為條件屬性集，為決策屬性集且和都可用以下兩個(gè)集合來表示：，故決策系統(tǒng)也可用信息系統(tǒng)來表示，即用來表示。例如，設(shè)F的論域。其屬性為其中是條件屬性集，為決策屬性集。各屬性值域均為:，F(xiàn)的信息表可用下圖表示，信息表中所有對(duì)象的全部信息都可以直接通過該表來查看，每一行就代表一個(gè)對(duì)象的全部信息，其中：行為對(duì)象，列為屬性。表31 信息表的一個(gè)示例Uabcd012012011010210111000010 可辨識(shí)矩陣和可辨識(shí)函數(shù) 可辨識(shí)矩陣 令為信息系統(tǒng)，其中，論域?yàn)椋ǎ?，條件屬性集合為，決策屬性為，將在屬性上的值記錄到中，為矩陣中第行與第列所對(duì)應(yīng)的元素。則用下面集合來表示可辨識(shí)矩陣： （31）其中。該矩陣可解釋為，第一行所描述的意思是其對(duì)應(yīng)的元素值不是同一個(gè)屬性值的集合；第二行當(dāng)所對(duì)應(yīng)的元素值是0的時(shí)候代表其決策值是相同的；第三行所對(duì)應(yīng)的元素值是，即其屬性值是一樣的，而決策值不是一樣的，此種情況說明該記錄為沖突的。 可辨識(shí)函數(shù)可辨識(shí)函數(shù)是由可辨識(shí)矩陣得來的。先起的每個(gè)屬性，再起所有的（）。通過吸收率把可辨識(shí)函數(shù)簡(jiǎn)化為標(biāo)準(zhǔn)式，此時(shí)，所有質(zhì)蘊(yùn)含式中的屬性涵蓋了信息系統(tǒng)內(nèi)所有約簡(jiǎn)的集合。對(duì)于把上述方法，其命名為屬性約簡(jiǎn)的基本方法，通過運(yùn)用該方法可以將所有的屬性約簡(jiǎn)求出來，不過這種方法有一點(diǎn)不足之處，它往往只能將較小的數(shù)據(jù)集進(jìn)行無誤的約簡(jiǎn)，較大的則不可以。 知識(shí)的化簡(jiǎn)在粗糙集理論里，在一個(gè)論域中，如果存在很多的知識(shí)是多余的，是不起決定性作用的，運(yùn)算時(shí)可以將這些多余的知識(shí)從論域中刪除，這樣做非但不能影響到最后的結(jié)果，而且還簡(jiǎn)化了結(jié)果。令為一簇等價(jià)關(guān)系，如果存在關(guān)系，稱是能忽略的，相反則是不能忽略的。同樣的，分類的關(guān)系與其近似，給定一個(gè)屬性集合，若在集合中有一些屬性特征有無均可，刪除它們對(duì)了解認(rèn)識(shí)這個(gè)屬性集合沒有收到影響，其等價(jià)關(guān)系依然不變。這就產(chǎn)生了獨(dú)立的知識(shí)，它說明該集合里任一屬性都是有用的。定義：若存在，如果是獨(dú)立的，滿足，則表示為，并把稱為的一個(gè)約簡(jiǎn)。定義：一簇等價(jià)關(guān)系的約簡(jiǎn)可能不止一個(gè)，將所有進(jìn)行約簡(jiǎn)后的集合相交定義為的核，用來表示：。在知識(shí)庫(kù)中，是一個(gè)非常重要的必不可少的屬性集，中所有約簡(jiǎn)后的且是共同的等價(jià)關(guān)系都包含其中。知識(shí)的依賴性問題，即一類知識(shí)可不可以推出另一類相關(guān)知識(shí)，具體將其定義為如下：令為一個(gè)知識(shí)基，滿足 (1) 往往當(dāng)，知識(shí)依賴于，記為； (2) 當(dāng)且，知識(shí)和等價(jià)，記為； (3) 當(dāng)與都不存在時(shí)，和為獨(dú)立的。其中表示的基本等價(jià)類可以用的基本等價(jià)類的組合來表示。 決策表對(duì)于前面提到的知識(shí)，可以用決策表來描述其表示方法，它對(duì)于描述知識(shí)是非常重要的。表中首先給了條件屬性，結(jié)果為決策屬性，一些問題都可用它來表達(dá)。對(duì)于一個(gè)知識(shí)表達(dá)系統(tǒng)，在中所有對(duì)象構(gòu)成的集合稱為，為描述對(duì)象的屬性集合，、分別被稱為條件和決策屬性集，既有條件屬性又有決策屬性的知識(shí)表達(dá)系統(tǒng)可用決策表進(jìn)行描述，記為，簡(jiǎn)寫為決策表。不可分辨關(guān)系稱為條件類， 稱為決策類。另外，該表處理都是離散型數(shù)據(jù)。若數(shù)據(jù)為連續(xù)型，需先將其變?yōu)殡x散型。 決策表的約簡(jiǎn) 屬性約簡(jiǎn)屬性的最佳約簡(jiǎn)的求取是約簡(jiǎn)的最終目標(biāo)。其定義的標(biāo)準(zhǔn)：在保證原有信息數(shù)量的基礎(chǔ)上，通過約簡(jiǎn)使屬性為最少，或者決策規(guī)則最優(yōu)，或者總的數(shù)據(jù)約簡(jiǎn)量為最大。在信息系統(tǒng)中，每一個(gè)對(duì)象就是系統(tǒng)中條件屬性的屬性值。然而，中的某些屬性可能是冗余的，因?yàn)樗麄儾荒芙o中的對(duì)象提供任何附加信息。首先將設(shè)為條件屬性的非空子集，若有子集,存在關(guān)系，那就稱為屬性的依賴集，若不是，則為獨(dú)立集。如果是獨(dú)立集，且存在關(guān)系，則稱是的約簡(jiǎn)，從上述得知，的約簡(jiǎn)是條件屬性的最大獨(dú)立集。將的全部約簡(jiǎn)簇設(shè)為。對(duì)于屬性，如果滿足關(guān)系，則稱a為中不可省略的，相反，稱a為中可省略的。中所有不可省略屬性集的集合稱為的核，換而言之，的所有約簡(jiǎn)簇包含了的核，且存在關(guān)系：。 屬性約簡(jiǎn)方法1. Pwalawk約簡(jiǎn)方法首先介紹一下Pwalawk的約簡(jiǎn)方法，對(duì)于該方法，可以對(duì)其進(jìn)行如下約簡(jiǎn)，在決策表中，任意一個(gè)條件屬性，稱之為，將對(duì)其約簡(jiǎn)，至條件屬性集合不能再約簡(jiǎn)：對(duì)于一個(gè)決策屬性，若要被刪除后使得不影響其結(jié)果，這就說明該屬性是可以被刪除的。相反，若刪除后會(huì)影響結(jié)果，則說明其是不能被刪除的決策屬性。相對(duì)決策屬性是必要的。2. 基于可辨識(shí)矩陣的啟發(fā)式算法利用可辨識(shí)矩陣能夠?qū)傩赃M(jìn)行約簡(jiǎn)?；诖?，通過可辨識(shí)矩陣演繹出不少啟發(fā)式約簡(jiǎn)算法。該類方法首先需要獲得可辨識(shí)矩陣，然后通過其求出屬性核，利用某種啟發(fā)式規(guī)則將屬性加入屬性核，滿足條件后最終結(jié)束?，F(xiàn)今國(guó)內(nèi)國(guó)外有很多優(yōu)秀的啟發(fā)式算法，利用核的概念作為起始點(diǎn)來進(jìn)行約簡(jiǎn)，將其落實(shí)為最小的約簡(jiǎn)。該方法的啟發(fā)規(guī)則是利用屬性的重要性，它的過程是這樣的，將其按重要性劃分，按其大小順序進(jìn)行排列，依次加入屬性，直到結(jié)束，下一步要依次觀察各個(gè)屬性，若刪除后對(duì)其約簡(jiǎn)結(jié)果是否產(chǎn)生影響，不影響，則刪除。3. 遺傳算法適值函數(shù)和表示方法是用來區(qū)分利用各種遺傳算法來計(jì)算簡(jiǎn)約的兩個(gè)方面?，F(xiàn)介紹的這個(gè)遺傳算法，它是眾多方法中較為有代表性的方法:每個(gè)位串代表可辨識(shí)矩陣的一項(xiàng)，若該屬性存在，則某位是1，否則不存在。也就是說每一個(gè)位串是一個(gè)約簡(jiǎn)的候選。該適值函數(shù)為如下定義: （32）說明如下：表示屬性集合的長(zhǎng)度，中1的個(gè)數(shù)為。是能區(qū)分的對(duì)象組合的個(gè)數(shù)。是對(duì)象的個(gè)數(shù)。在初始化時(shí)，可以將核或者必要的屬性加入，來加速算法的收斂速度。該函數(shù)前部分是想讓的長(zhǎng)度盡可能的小。后部分想讓該算法可以區(qū)分的對(duì)象盡可能多。4. 擴(kuò)展法則約簡(jiǎn)算法“強(qiáng)等價(jià)”這個(gè)概念發(fā)展為擴(kuò)展法則，它可以將可辨識(shí)函數(shù)快速簡(jiǎn)化。如果兩個(gè)屬性在可辨識(shí)函數(shù)中同時(shí)出現(xiàn)或不出現(xiàn)，則稱之為局部強(qiáng)等價(jià)，當(dāng)兩個(gè)屬性滿足上述條件，就可將之化簡(jiǎn)為一個(gè)屬性。該算法不但可以處理較大的數(shù)據(jù)集而且它的約簡(jiǎn)速度較其它算法快很多。 屬性值約簡(jiǎn)屬性值約簡(jiǎn)是通過對(duì)決策表中所列舉的信息進(jìn)行逐行檢查，將所有冗余信息刪除，其前提是刪去后不得妨礙決策表的規(guī)則表達(dá)，這個(gè)過程就是屬性值的約簡(jiǎn)過程。經(jīng)過屬性約簡(jiǎn)后，就可以得到?jīng)Q策表的屬性約簡(jiǎn)結(jié)果，接下來對(duì)屬性約簡(jiǎn)結(jié)果進(jìn)行屬性值的約簡(jiǎn)，就可以得到?jīng)Q策表的最小約簡(jiǎn)，得出最終的決策規(guī)則。 屬性值約簡(jiǎn)算法原始決策表經(jīng)過屬性約簡(jiǎn)后會(huì)得到一個(gè)新的決策表，對(duì)于這個(gè)新的決策表，將其中的一個(gè)樣本對(duì)應(yīng)生產(chǎn)一條決策規(guī)則。如此一來，約簡(jiǎn)后的決策表就成了一個(gè)規(guī)則集合。對(duì)于這個(gè)規(guī)則集合，普遍采用以下屬性值約簡(jiǎn)算法來進(jìn)行簡(jiǎn)化：對(duì)于規(guī)則集合中的某條規(guī)則，在不考慮其某一條件屬性的前提下，該規(guī)則不會(huì)與集合中其他規(guī)則發(fā)生任何沖突，那么將認(rèn)定為可以刪除該規(guī)則所包含的這一條件屬性。同理，當(dāng)刪除掉規(guī)則集合中所有的冗余條件屬性，就能得到條件屬性數(shù)目最少的規(guī)則集合。設(shè)約簡(jiǎn)后的決策表有個(gè)樣本，個(gè)條件屬性。屬性值約簡(jiǎn)算法的具體過程為：刪除決策表的第行第列屬性值，將該決策規(guī)則剩余的個(gè)條件屬性與其余個(gè)樣本的對(duì)應(yīng)條件屬性進(jìn)行比較。如果條件屬性不同，即，表示該被刪除的條件屬性是冗余的，用*代替。如果條件屬性相同，即，再看決策屬性是否相同，即是否等于，等于表示該被刪除的條件屬性是冗余的，用*代替，反之就表示不是冗余的，保留該屬性值。具體流程如圖31。圖31 決策表屬性值約簡(jiǎn)流程圖 本章小結(jié)本章主要介紹了粗糙集的基本理論知識(shí)，粗糙集理論的應(yīng)用過程首先是構(gòu)造知識(shí)的決策表。然后對(duì)所構(gòu)建的決策表在不損失原有信息的前提下進(jìn)行屬性約簡(jiǎn)，最終得到屬性的最佳約簡(jiǎn)決策表。粗糙集理論中，約簡(jiǎn)算法有很多，每種算法都有每種算法的優(yōu)缺點(diǎn)和適用范圍，到現(xiàn)今為止，沒有一種方法是最優(yōu)的，也沒有一種方法是最差的。所以這一直是眾多學(xué)者研究的內(nèi)容。第4章 Petri網(wǎng)的基本理論1962年，Carl 。當(dāng)時(shí)，他運(yùn)用該理論對(duì)計(jì)算機(jī)系統(tǒng)事件之間因果關(guān)系進(jìn)行了描述。半個(gè)世紀(jì)以來，Petri網(wǎng)經(jīng)過不斷的豐富和發(fā)展，已經(jīng)日益完善。經(jīng)過一批批的學(xué)者和工程技術(shù)人員對(duì)Petri網(wǎng)的研究，Petri網(wǎng)在計(jì)算機(jī)、通信、自動(dòng)化、電力等很多領(lǐng)域得到了應(yīng)用廣泛。這些研究主要內(nèi)容如下：（1）針對(duì)Petri網(wǎng)模型的行為特性和分析方法進(jìn)行系統(tǒng)的研究；（2）為了提升Petri網(wǎng)模型的表達(dá)能力，對(duì)基本的Petri網(wǎng)進(jìn)行擴(kuò)展的研究。如：著色Petri網(wǎng)，賦時(shí)Petri網(wǎng)等；（3）為了使Petri網(wǎng)成為一種適用范圍廣的高效工具，將其從計(jì)算機(jī)系統(tǒng)融入到其他領(lǐng)域的研究（4）為了解決Petri網(wǎng)模型應(yīng)用在大型復(fù)雜系統(tǒng)中存在狀態(tài)空間組合爆炸的問題，對(duì)Petri網(wǎng)模型的簡(jiǎn)化進(jìn)行的研究；（5）為方便Petri網(wǎng)模型的設(shè)計(jì)與分析，進(jìn)行軟件開發(fā)的研究。Petri網(wǎng)之所以備受學(xué)者和技術(shù)人員的關(guān)注，主要原因是它采用可視化圖形描述離散事件系統(tǒng)的靜態(tài)結(jié)構(gòu)及動(dòng)態(tài)行為，易于理解。同時(shí)因?yàn)镻etri網(wǎng)能夠描述離散事件系統(tǒng)的結(jié)構(gòu)，所以它不單可以抓住系統(tǒng)中事件的先后和異同步等特征，還可以反映系統(tǒng)的沖突、互斥以及系統(tǒng)不確定和鎖死的情況。 Petri網(wǎng)的定義對(duì)于一個(gè)離散事件系統(tǒng)，它的基本Petri網(wǎng)模型所包含的結(jié)構(gòu)元素為：庫(kù)所（，用圓圈 表示）、變遷（，用豎線 或者小矩形 表示）及有向弧（用帶箭頭的線表示）。庫(kù)所描述離散事件系統(tǒng)可能的狀態(tài)，變遷代表離散事件系統(tǒng)中可能事件，局部狀態(tài)與可能事件之間通過有向弧來建立聯(lián)系。庫(kù)所中包含托肯（）的數(shù)目是對(duì)于系統(tǒng)的狀態(tài)的描述。在Petri網(wǎng)模型中，用包含在庫(kù)所中的實(shí)心圓點(diǎn)（）表示托肯，其作用是描述它所在庫(kù)所的動(dòng)態(tài)情況。假如庫(kù)所中包含一個(gè)托肯，則表示該庫(kù)所實(shí)現(xiàn)一次，也就是該局部狀態(tài)滿足條件或結(jié)果是真；假如庫(kù)所中沒有托肯，則表示庫(kù)所沒有實(shí)現(xiàn)，也就是該局部狀態(tài)不滿足條件或結(jié)果是假。離散事件系統(tǒng)中滿足事件的發(fā)生條件是該事件發(fā)生的前提，這一過程也叫做Petri網(wǎng)模型變遷的使能（）。對(duì)于Petri網(wǎng)模型里的某個(gè)變遷，把全部朝向它的弧所連接的庫(kù)所稱為它的輸入庫(kù)所，把全部從它開始的弧所連接的庫(kù)所稱為它的輸出庫(kù)所。一個(gè)輸入庫(kù)所就是由變遷代表的事件的一個(gè)發(fā)生條件。一個(gè)事件的發(fā)生有時(shí)要多次滿足同一個(gè)條件，此時(shí)用弧的權(quán)值進(jìn)行表示。只要某個(gè)變遷的全部輸入庫(kù)所包含的托肯總數(shù)不小于連接這些庫(kù)與該變遷的弧的權(quán)值，該變遷就會(huì)被使能。被使能的變遷觸發(fā)后，在消耗全部輸入庫(kù)所中一部分托肯的同時(shí)，還將在每一個(gè)輸出庫(kù)所中產(chǎn)生一部分托肯，這部分托肯的數(shù)量就是連接變遷和該輸出庫(kù)所的弧的權(quán)。Petri網(wǎng)中變遷被使能與狀態(tài)轉(zhuǎn)換都只在局部發(fā)生。正是這種局部狀態(tài)轉(zhuǎn)換的存在，才使Petri網(wǎng)模型可以對(duì)并行與分布事件的離散事件系統(tǒng)加以描述。 Petri網(wǎng)的結(jié)構(gòu)定義為一個(gè)由四元組描述的有向圖。其中：（1）是庫(kù)所的全部集合，為庫(kù)所的數(shù)目（）；（2）是變遷的全部集合，為變遷的數(shù)目（）；（3）；（4）定義為從到弧的權(quán)（）的集合，是輸入函數(shù)，是非負(fù)整數(shù)集合；（5）定義為從到弧的權(quán)的集合，是輸入函數(shù)。在表示Petri網(wǎng)結(jié)構(gòu)的有向圖中，若從到的輸入函數(shù)為，則記為，在從到的有向弧旁標(biāo)注，若從到的輸出函數(shù)為，則記為，在到的有向弧旁標(biāo)注。當(dāng)時(shí)，則不必標(biāo)注。當(dāng)或者時(shí)，不必畫弧。和均可用的非負(fù)整數(shù)矩陣來表示，關(guān)聯(lián)矩陣就是與的差。也就是： （41）以一個(gè)Petri網(wǎng)結(jié)構(gòu)為例，：，；，；，；，；，則該網(wǎng)絡(luò)的結(jié)構(gòu)圖形如圖41所示。圖41 Petri網(wǎng)的結(jié)構(gòu)圖形示例該P(yáng)etri網(wǎng)輸入輸出函數(shù)的矩陣表示形式如下： 因此可求得該網(wǎng)絡(luò)的關(guān)聯(lián)矩陣為： Petri網(wǎng)的標(biāo)識(shí)定義為用五元組進(jìn)行表示。即：。其中：（1），為Petri網(wǎng)的結(jié)構(gòu)。（2）是一個(gè)列向量，第個(gè)庫(kù)所包含的托肯數(shù)目就是第個(gè)元素的取值，該向量定義為Petri網(wǎng)的標(biāo)識(shí)。各個(gè)庫(kù)所的初始狀態(tài)用初始標(biāo)識(shí)進(jìn)行表示。在圖41中，根據(jù)各個(gè)庫(kù)所包含的托肯數(shù)目，可以得出，其中。 Petri網(wǎng)的運(yùn)行規(guī)則在Petri網(wǎng)的理論中，變遷用來描述整個(gè)離散事件系統(tǒng)中的一個(gè)事件。如果該事件滿足了前提條件后發(fā)生了，則它被使能（）。變遷使能所要滿足的前提條件用的輸入庫(kù)所表示，是的全部輸入庫(kù)所的集合。一個(gè)變遷的使能要求實(shí)現(xiàn)局部前提狀態(tài)的次數(shù)用該變遷的輸入函數(shù)定義，而局部前提狀態(tài)的實(shí)現(xiàn)情況是通過庫(kù)所中存在的托肯個(gè)數(shù)來反映的，因此，的使能與它的輸入函數(shù)和輸入庫(kù)所包含的托肯個(gè)數(shù)都有關(guān)系。 當(dāng)且僅當(dāng)：，變遷在標(biāo)識(shí)下使能。在圖41中，由于， ，變遷被使能。而，由于，變遷不使能。在Petri網(wǎng)所描述的離散時(shí)間系統(tǒng)內(nèi)，描述事件的發(fā)生是通過使能的變遷的觸發(fā)（點(diǎn)火）來實(shí)現(xiàn)的。使能的變遷觸發(fā)過程發(fā)生在滿足前提條件后，這也將耗費(fèi)掉這些前提狀態(tài)。與此同時(shí)，該過程還會(huì)使得與該變遷相連的庫(kù)所狀態(tài)發(fā)生改變。消耗前提狀態(tài)的過程通過移去輸入庫(kù)所包含的托肯來表示，移除掉的托肯個(gè)數(shù)由輸入函數(shù)確定；產(chǎn)生的結(jié)果狀態(tài)利用增加