獲取
Pawlak 粗糙集理論及其擴展模型, 是處理不同類型的決策信息系統的不協調性與不完備性, 並由此揭示其數據規律的有力工具. 信息系統知識發現的重要任務是, 揭示條件屬性與決策屬性之間的依賴關係. 對兩者之間的依賴關係的研究主要體現在兩個方面, 一是通過屬性約簡評估條件屬性相對於決策屬性的重要性, 二是計算“if-then”決策規則.在信息系統中, 如果一個對象關於某屬性的屬性值僅表示該對象關於屬性所在的類, 則屬性值確定對象間的不可分辨關係, 從而可建立以等價類為基本知識顆粒的Pawlak 粗糙集模型; 如果屬性值表達對象之間的相似程度(接近程度), 則可以通過定義相容關係, 以相容類或最大相容類為基本知識顆粒, 建立相容關係粗糙集模型[4-9];如果對象的屬性值表達對象之間的優勢關係(偏序關係), 則該系統被稱為序信息系統. 在序決策信息系統中, 對象的條件屬性值確定對象之間的優勢關係(支配關係), 而決策屬性所確定的決策類之間也被賦予優劣關係. 以支配集和被支配集為基本知識顆粒, 提出了基於優勢關係的粗糙集方法(DRSA).
DRSA 以對象的支配集和被支配集為基本知識顆粒, 定義決策類的並的上、下近似, 並由此獲取優勢決策規則(“at least”決策規則和“at most”決策規則).針對各類序決策信息系統, 如不完備序決策信息系統[14-16]、集值序決策信息系統[17]、區間值序決策信息系統以及模糊序決策信息系統等, 提出DRSA 的多種擴展模型, 並在屬性約簡與決策規則獲取方面取得豐碩成果. 這些擴展模型也是以對象的支配集和被支配集為基本知識顆粒, 然而, DRSA 存在以下3 個方面的問題.
1)某些情況下, 支配集和被支配集作為基本知識顆粒顯得太粗. 舉一個特殊的例子: 當信息系統中的對象集關於條件屬性集存在最大(小) 元而該最大(小) 元被指派至最劣(優) 的決策類時, 利用DRSA 得不到任何“at least”(“at most”) 決策規則, 即DRSA 無法處理這類不協調性.
2)DRSA 所得到的“at least”(“at most”) 決策規則,其決策值大(小) 於某特定值, 而不是落於一個有限區間. 它們能將滿足條件的對象指派到不劣(優) 於某個特定決策類的那些決策類中, 但不能指派對象到優於一個特定決策類同時又劣於另外一個特定決策類的那些決策類中; 特別地, 不能把對象指派於一個指定的決策類; 因此, “at least”(“at most”) 決策規則不能直接套用於序信息系統中對象的分類.
3)DRSA 基於這樣一種假設: 序決策信息系統本應滿足優勢關係原理(亦稱系統是協調的), 即條件屬性和決策屬性之間滿足單調性, 亦即, 依條件屬性值為優的對象其決策值亦為優, 只不過由於數據獲取手段的局限性或專家在賦予對象決策值時的躊躇, 導致數據出現不協調性, 使某些條件屬性值為優的對象其決策值反而為劣. 然而, 可以想像, 在很多實際問題中, 條件屬性和決策屬性之間不一定滿足單調性, 而往往滿足分區域的單調性. 例如, 在評估國民經濟運行狀態時, 作為指標之一, 經濟成長率並不是越高越好, 而是要控制其在一個合理的範圍之內; 在評估身體健康狀態時, 血壓並不是越高越好或越低越好, 而是處於一個恰當的範圍為好. DRSA 不能處理這種條件屬性和決策屬性之間滿足分區域單調性的序決策信息系統.為了解決上述問題, 本文以“區間”為基本知識顆粒, 建立一種新的基於優勢關係的粗糙集模型. 這裡, “區間”是一個對象的支配集和另外一個對象的被支配集的交集.
挖掘算法
概述
規則挖掘是數據挖掘的一項重要內容, 傳統的基於粗糙集理論的規則挖掘方法是先求決策信息系粒計算的核心思想是對待求解的問題進行粒化, 在多個粒度空間對問題進行分析和求解, 進而合成原始問題的解, 符合人類從多角度分析問題、求解問題的認知規律, 並受到了研究者的關注.
本文將屬性約簡和屬性值約簡過程合二為一, 以知識粒為單位挖掘規則. 先對決策信息系統分層粒化, 在不同粒度的知識空間下計算粒關係矩陣, 並從中獲取啟發式信息根據啟發式信息確定信息粒的屬性值約簡順序, 在此基礎上去除冗餘屬性,並設定終止條件, 實現決策規則的快速挖掘. 理論分析和UCI 數據集的測試結果表明, 該算法能獲得所有最簡規則.
基於粒計算的最簡決策規則挖掘算法
對決策信息系統挖掘規則的傳統方法是先求屬性約簡, 再逐行提取規則, 中間包含了很多冗餘計算,最後的結果也取決於屬性約簡結果的好壞, 並且隨著樣本集的增大, 算法複雜性將大大增加. 對屬性約簡進行了粒度原理分析並指出, 對決策信息系統進行屬性約簡得到的知識劃分空間是極大近似劃分空間, 但該知識空間的知識粒並不一定是整個知識空間中最 “粗” 的粒. 本文考慮在不同粒度層次的知識空間中挖掘規則. 為便於算法說明, 先給出符號定義.
3.1 符號定義
為了不失一般性, 假設決策信息系統有 個條件屬性, 1 個決策屬性. 為條件屬性 ′ 所含條件屬性的個數, 表征系統的粒度, 1;為粒度下的所有條件屬性 ′, 這樣的條件屬性有 個;為 中某一條件屬性對應的條件粒矩陣; 為決策屬性對應的決策粒矩陣; × 為粒關係矩陣.
3.2 算法描述
基於粒計算的最簡決策規則挖掘算法.輸入: 決策信息系統;輸出: 所有最簡決策規則.
1) 生成決策粒矩陣 並取粒度 = 1.
2) 對 中每一個條件屬性求條件粒矩陣和粒關係矩陣 , 計算 1、 2, 保存相應數據並做以下處理:
① 尋找是否存在 2 = 1. 若存在, 則由性質 3 可知, 對應信息粒可以完全區分某一決策類, 約簡過程中優先考慮, 這樣可以保證在區分能力不變的情況下得到的規則最少, 約簡相應的信息粒得到決策規則,否則轉 ②;
② 若不存在 2 = 1, 則對 1 值的大小進行比較, 1 值越大, 對應信息粒的區分能力越大, 同樣可以保證在區分能力不變的情況下得到的規則最少. 根據 1 值的大小確定信息粒的約簡順序, 通過約簡信息粒得到決策規則, 轉 ③;
算法複雜性分析
算法主要考慮如何提高現有算法的計算效率, 包括如何減少冗餘計算, 如何提高搜尋效率, 如何減少存儲空間.按照啟發式信息 、 對信息粒進行約簡, 同時去掉冗餘屬性, 減少了傳統先約簡屬性再約簡屬性值時的冗餘計算. 在同一粒度空間下進行搜尋時使用啟發式運算元對不同知識空間進行選擇和排序, 提高了搜尋效率. 在最壞的情況下需要搜尋2次, 而在實際情況中, 當數據本身的冗餘性很大時, 搜尋空間要遠遠小於2 ,因為在該算法中加入啟發式信息, 同時設定終止條件, 算法收斂更快. 本文使用的矩陣是布爾稀疏矩陣。
決策規則約簡
概述
基於數據挖掘的KDD技術近來得到人工智慧領域的廣泛關注。粗糙集理論是一種新型的處理模糊和不確定知識的數學工具。粗糙集合理論提供了一整套方法，從數學上嚴格地處理數據分類問題。它是處理具有信息不確定、不精確、不完善系統的數學工具，是一種比較適用的歸納、分類方法。粗糙集合僅僅分析隱藏在數據中事實，並沒有帶入人為的模糊性。是採用精確的數學方法分析不精確係統的一種理想方法。目前已經在知識與數據發現、模式識別與分類、 故障檢測等方面得到了較為成功的套用。在機器學中，基於Rough Set的推理技術也逐漸得到套用。
粗糙集理論雖然是針對不確定性問題提出的，但與模糊集處理問題的方法不同。它不像模糊集那樣需要依賴先驗知識對不確定性的定量描述，而只依賴數據內部的知識，用數據之間的近似來表示知識的不確定性。所以粗糙集理論本身是具有嚴密邏輯基礎的，是精確的。利用粗糙集理論進行數據挖掘，抽取知識規則，最重要的一點就是基於粗糙集的屬性約簡和規則冗餘值約簡。 通過約簡操作，降低屬性的維數，總結出適用於決策支持的知識規則，是粗糙集理論的最重要套用之一。
粗糙集的基本概念
粗糙理論的基本思想是，將資料庫中的屬性分為條件屬性和結論屬性，對資料庫中的實例根據各個屬性不同的屬性值分成相應的子集，然後對條件屬性劃分的子集與結論屬性劃分的子集之間的上下近似關係生成判定規則。知識表達系統是有序對S=<U, C, D, V, f>，其中U 非空有限集合, 稱為全域，C 條件屬性集合，D 是一個決策屬性，A=C ÈD，稱為屬性集合。V是屬性值的集合，f指定U中沒一個對象的屬性值，全域U的元素被稱為對象或者實例。粗糙集之所以描述知識的不確定關係，是基於知識表達中的不可分辨關係的。在知識表達系統中，對於屬性集A 中的任意一個屬性a，如果實例 和記錄 x 對於屬性a的取值相同，我們稱 x 和基於屬性集相等，是不可分辨的。
基於某個屬性集A的所有等價記錄的集合，被定義為等價類。屬於同一等價類的記錄歸為一類，此分類稱為R基於屬性集A的劃分，表示為 U/ ind( R)={ R, R,..., R } ， [ x ] 表示中包含的等價類。當 X Í U ，且 X為 U / ind ( R ) = { R, R ,..., R } 的並時，稱 X是 R可定義的，稱為 R的精確集，否則 X為 R不可定義的，也稱為R的粗糙集。粗糙集可以近似地用上近似和下近似來刻畫。
屬性約簡
為了說明約簡，定義決策屬性對條件屬性的依賴性和屬性的重要性。約簡是原始屬性集的一個最小子集, 並且這個子集具有和整個屬性集同樣的分類能力。對原始的數據表表示的知識系統，可以採用屬性的重要性來進行約簡。當 IMF a ( D ) = 0 時，該屬性對決策屬性分類沒有貢獻，可以省略的。 IMF a ( D ) ¹ 0 ，該屬性就是核中的元素。根據屬性重要性來進行約簡，我們很輕鬆地得到該知識表中的核的構成，但核不是該原始知識表的約簡。如果可省略的屬性不唯一時，通常存在多種約簡形式，這給決策規則提取帶來障礙。並且被證明，最簡單約簡的求解是一個NP問題 。對約簡的簡化獲得，只能採用啟發式規則。利用屬性重要性作為啟發求最小約簡 ，基本算法是，首先得到核作為屬性約簡集的基礎，然後按照屬性的重要程度從大到小逐個加入屬性，直到依賴程度已經與原始屬性集的依賴程度相等為止。最後對新加入的每個屬性, 計算去掉後是否影響依賴係數。如果不影響,則將其刪除。在屬性重要性啟發規則中，每次加入一個一個新屬性要大量計算依賴度，而且最後還要對非核屬性計算依賴度，是很煩瑣的過程。下面討論一種基於分辨矩陣的啟發式規則。
根據分辨矩陣的原理知道， C i, j 在某種程度上代表了約簡。如果約簡與分辨矩陣交集為空，說明對象不能靠約簡將它們區分開來，那么約簡就不是區分所有對象的最小屬性集合。利用約簡與分辨矩陣的交集不為空的原理出發，我們設計了一個啟發規則。如果 Ci, j 只有一個屬性元素，該屬性肯定是約簡中的元素，否則 i , j 不可區分。因此可以類推, 分辨矩陣某項的所含屬性越少, 該項就對分類所起的作用就越大。 而且該項出現得越頻繁, 該項就越重要，該項中的元素更可能是約簡中的元素。採用一個函式來標記屬性的頻度：f ( a ) = f ( a ) + card ( C ) / card ( C i , j ) ， 表示條件屬性數目， card (C i , j ) 表示該分辨矩陣項中屬性個數，f(a ) 為該項某個屬性元素的頻率。該公式考慮了項所含元素的多少的影響，同一元素在不同項中的頻度增加 card (C) / card (Ci, j ) 是不同的。
囚徒困境決策
囚徒困境決策規則
概述
美國決策研究專家黑斯蒂(Hastie，R)認為判斷與決策是人類根據自己的願望和信念選擇行動的過程。決策(decision making)從狹義上說是一個動態過程，是個體運用感知覺、記憶、思維等認知能力，對情境做出選擇，確定策略的過程。廣義的決策則包含判斷與決策兩個部分。博弈論中“囚徒困境”下的決策就是一個很有代表性的例子.
囚徒困境簡介及其傳統策略
囚徒困境也稱社會兩難情境，是博弈論中的經典案例，指兩個嫌疑犯被警察抓到，但警方沒有掌握確切的證據，警察就分別找他們談話：“如果你們都不認罪的話，我們將讓你們都入獄一年；如果一個認罪，另一個不認罪的話，那么我們將判不認罪的那個十年的徒刑，認罪的將無罪釋放；如果兩人都認罪的話，我們將基於你們的誠實把每個人的徒刑降為五年，請你們各自權衡。”在這種情形下，兩個疑犯都將面臨著一個具有決定意義的兩難選擇。
亞當·斯密(Adam Smith)曾提出了理性經濟人的假設，一是經濟人是自私自利的；二是經濟人的行為是理性的，即他們根據處境來判斷自身的利益，追求個人利益儘可能最大化。在一個標準的囚徒困境中，可以用下面這個矩陣來表示：
| 罪犯B | |||
| 認罪 | 不認罪 | ||
| 罪犯A | 認罪 | (5、5) | (0、10) |
| 不認罪 | (10、0) | (1、1) | |
兩個囚犯面臨同樣的選擇——無論同夥選擇什麼，他們最好都選擇認罪。因為，如果同夥不認罪，那么他們就無罪釋放，否則，他們起碼會被判十年徒刑。在一般情況下，假定每個囚徒都是理性的，他們的選擇通常會出現以下兩種可能情形：以A 為例，第一種可能是：B 認罪，這時如果A 也認罪，那么他們都要入獄5 年；如果A 不認罪，則A 將被判十年，B 無罪釋放，兩相比較下，對於A 來說，認罪顯然是最優策略。第二種是：B 不認罪，這時如果A 認罪，那么B 將被判十年，A 將無罪釋放，如果A 也不認罪，那么他們都將被判一年，這種情形下，A 的最優策略也是認罪。由此可見，對雙方而言，每一個囚犯從個人利益出發，不考慮他人，他們都將選擇認罪。但如果雙方都不認罪，那么等待他們的將是一年的牢獄之苦。也就是說，對個人最有利的認罪策略，卻不是集體(A 和B)的最佳策略。
囚徒困境中彰顯的人性特點和理性信任觀
囚徒困境中個人的理性選擇卻是集體的非理性選擇，從人性的角度來看，就會發現其中包含著人性惡的傾向。如果A 是善的，那么會出現兩種情況，第一種情況是A 堅持不認罪也不供出B，B 同樣也是堅持不認罪也不供出A；第二種情況是，A 堅持不認罪，B 認罪。
如果A 是惡的，那么也會出現兩種情況，第一種情況是A 認罪也供出B，而B 不認罪.第二種情況是A 認罪也供出B，B 也認罪且也供出A 。
從善的角度考慮問題，可能得到最好的(1 年)和最糟的(10 年)的處罰結果；從惡的角度考慮，可能得到最好的(0 年)和最糟的(5年)的處罰結果。A、B 雙方都從自己的利益考慮，選擇惡的可能性會更大些。由此從囚徒困境中看到了人性惡的傾向。
在很多情況下，人面對的是一種集體條件下的困境，即博弈的雙方可能是兩大集團或更多的人，相同的博弈者可能會不斷地重複面對相似的困境，“有條件的合作策略”將可能是理性經濟人的最優策略。
重複為博弈產生了新的動力結構。通過重複，博弈者就可能按對手以往的選擇而決定當前的選擇。例如，存在一種所謂的“一觸即發”策略，即“只要你背叛，我隨後將永遠背叛”，當雙方保持背叛的狀態時，就失去了雙方獲益的機會。而如果雙方合作，其前提是雙方的相互信任，就可能爭取到雙方獲益的機會。還存在另一種所謂的“一報還一報”的策略，以合作開始，然後模仿對方上一步選擇的策略。該策略以信任開始，決不首先背叛。時間嵌入性理論表明，今天的行為(合作或背叛)，將影響再次相遇時所做的選擇。信任是使關係更持久、更穩固的最優選擇。
現實生活中的“囚徒困境”及其應對策略
囚徒困境在現實社會中廣泛存在，而且情形要複雜的多。如汽車尾氣與空氣品質的問題。要保持空氣清潔，汽車主人就要對車安裝防污染的過濾裝置，需要自己負擔費用。而理性個體既想享受清潔的空氣，又不願為此付出代價。還有民眾生育觀的多子多福與人口膨脹的問題，上車不排隊擁擠的問題等等。
要想克服重複條件下的囚徒困境，就要從集體成員的主觀條件入手，使成員在新的基礎上做出最優決策，打破原有的納什均衡，建立新的有價值的納什均衡(納什均衡是經濟學家Nash 提出的，若有N 個人參加博弈，那么在給定他人戰略的情況下，在每一個參與人選擇的最優戰略所形成的戰略組合中，沒有任何一個參與人有積極性選擇其他戰略，也沒有任何人有積極性打破這種均衡)。為此可以採取以下措施：
1、利用強化的作用.制定規則或提供獎懲措施，通過正強化的作用，引導決策者改變自己原有的決策偏好，向著有利於集體利益的方向發展，做出對集體而言的最優策略。
2、創造良好的文化氛圍.囚徒困境說到底其實也是一種道德困境，要解決這種道德困境，就要從根本入手，創造良好的文化氛圍，逐步改變全體的道德觀、價值觀、主觀偏好。深刻認識囚徒困境的弊端，充分利用強化手段，在良好的社會文化氛圍中創造人人都能從全局的利益出發，團結合作，使全社會建立起一種新的有利於全體成員的有價值的納什均衡。
