數(shù)據(jù)倉庫與決策支持系統(tǒng),主講：魯明羽,大連海事大學信息科學技術學院 研究方向：智能數(shù)據(jù)分析與數(shù)據(jù)挖掘 電 話：13889576531 Email：lumingyu,第二章 決策推理與決策支持系統(tǒng),本章內容,人腦決策推理初探 電腦推理方法介紹 DSS中的決策過程 知識與知識表示方法,1. 人腦決策推理初探,推理（inference）：是由已知事實通過一定邏輯手段獲得未知事實的過程。 兩種主要的推理方法：演繹(deductive inference)和歸納(inductive inference),圖4.1 推理模型圖,1. 人腦決策推理初探,（1）演繹推理 演繹推理是從一般到特殊的推理，其中的已知事實部分一般為一般性的規(guī)則，而其未知部分則為個體事實。,圖4.2 演繹推理模型,1. 人腦決策推理初探,演繹推理是一種常用的推理方法，例如：數(shù)學中采用的基本方法，初等幾何中由公理推導定理的方法。 專家系統(tǒng)中也經常采用演繹推理，例如醫(yī)學診斷專家系統(tǒng)。 兩種演繹推理方法： （1）三段論推理法 （2）反證法,1. 人腦決策推理初探,（2）歸納推理 歸納推理與演繹推理相反，是從特殊到一般的推理，其中的已知事實部分一般為大量個體事實，而其未知部分則為推導出的一般性規(guī)則。,圖4.5 歸納推理模型,1. 人腦決策推理初探,歸納推理也是一種常用的推理方法，例如現(xiàn)實生活中的一些諺語，就是通過人們通過對生活中的大量事實進行總結歸納后得出的。 歸納推理得到的一般性規(guī)則，又可以用于演繹推理，指導我們的行為和決策。 （圖4.7 歸納-演繹推理過程） 數(shù)據(jù)挖掘就是采用了這個原理。,1. 人腦決策推理初探,（3）聯(lián)想和類比 從一些已知事實或知識，通過聯(lián)想，推出其他類似事物的知識。 （4）綜合與分析 根據(jù)對事物的宏觀（整體）知識推斷其微觀（局部）知識的方法稱為“分析”； 從事物的微觀（局部）知識推出其宏觀（整體）知識的方法稱為“綜合”。,1. 人腦決策推理初探,（5）預測 根據(jù)事物的過去和現(xiàn)在知識，來推斷未來的知識，或者從事物局部空間的知識，推斷其局部以外的情況。 （6）假設與驗證 根據(jù)經驗作出假設，然后用邏輯推理或實踐檢驗的方法獲得新的知識。有時會否定假設或部分修正假設，然后再作驗證，也可稱為“試探推理法”。,2. 電腦推理方法介紹,電腦推理一般是模仿人腦的推理方式和過程，通過編制軟件完成。 2.1 電腦的演繹推理方法 （1）規(guī)則模型表示 一般性規(guī)則有兩種表示方法： 數(shù)學方法 人工智能方法,2. 電腦推理方法介紹,（2）基于數(shù)學模型的演繹推理 數(shù)學方法中一般采用數(shù)學模型，例如數(shù)學表達式、方程式等。 基于數(shù)學模型的演繹推理實際上是數(shù)學推演方法，一般將一些常用的演算方法作為固定算法，編程實現(xiàn)后存入方法庫中，例如最小二乘法、線性規(guī)則、回歸分析等。 數(shù)學建模和推理時則調用方法庫中算法。,2. 電腦推理方法介紹,（3）基于邏輯模型的演繹推理 人工智能常用的知識表示方法包括謂詞邏輯、語義網絡、Petri網、框架表示等。 其中最常見的是謂詞邏輯表示法，即將規(guī)則表示為一組數(shù)理邏輯中的一階謂詞邏輯的合法公式，采用一階謂詞的推理方法，以實現(xiàn)演繹推理。該推理過程實際上是一種定理證明過程，其規(guī)則一般為公理，而結果為個體事實，即推導出的定理。,2. 電腦推理方法介紹,20世紀60年代，美國科學家Robinson證明，存在一種統(tǒng)一的、固定的證明過程，對于所有的一階謂詞邏輯中的定理證明都基本有效，這就是所謂的謂詞邏輯的自動定理證明。 利用上述成果，可以將定理證明過程用一種統(tǒng)一算法表示并編程實現(xiàn)，從而使運用人工智能方法進行演繹推理可以用一種統(tǒng)一的程序或過程來實現(xiàn)。 用此方法所實現(xiàn)的軟件系統(tǒng)稱為推理引擎（inference engine）。,2. 電腦推理方法介紹,2.2 電腦的歸納推理方法 主要有兩種：驗證型歸納和探索型歸納。 （1）驗證型歸納 首先對于推理結果產生一些假設（模型）； 設計一個試驗環(huán)境，并置入設想模型； 啟動試驗過程，用大量個體事實做測試，通過人機交互將得到的結果與原設想做比較 如果結果不符，修改試驗，反復上述過程,2. 電腦推理方法介紹,（2）探索型歸納 沒有明確的假設模型，只有大致的目標，一般采用數(shù)據(jù)挖掘技術實現(xiàn)，主要方法有： 關聯(lián)分析(association)：挖掘出潛藏在客體間的內在相互聯(lián)系； 分類(classifier)：對待分類的客體集合進行分析，找出每個分類的特征； 聚類分析(clustering)：對一組客體按某種規(guī)則聚為若干類。,3. DSS中的決策過程,在DSS中，除了決策推理部分之外，還有數(shù)據(jù)倉庫部分。二者相結合，構成了一個完整的決策過程。 3.1 DSS中的演繹型決策過程 在DSS中，演繹型決策過程是由演繹中的一般性規(guī)則與數(shù)據(jù)倉庫中的數(shù)據(jù)共同作為推理前提，通過演繹推理，最終得到個體事實數(shù)據(jù)作為結論。,3. DSS中的決策過程,基于不同推理模型，DSS的演繹型決策過程有不同的形式。,圖4.9 DSS中演繹型決策過程示意圖,3. DSS中的決策過程,圖4.10 DSS中基于數(shù)學模型的演繹型決策過程示意圖,基于數(shù)學模型的演繹型決策過程 數(shù)據(jù)倉庫數(shù)據(jù)作為數(shù)學模型中的參數(shù)輸入，而演繹推理則是通過方法庫中方法調用方式實現(xiàn)。,3. DSS中的決策過程,基于邏輯模型的演繹型決策過程 數(shù)據(jù)倉庫數(shù)據(jù)作為假設前提輸入，而演繹推理則是用推理引擎實現(xiàn)。,圖4.11 DSS中基于邏輯模型的演繹型決策過程示意圖,3. DSS中的決策過程,3.2 DSS中的歸納型決策過程 在DSS中，歸納型決策過程是由數(shù)據(jù)倉庫中的數(shù)據(jù)作為大量個體事實輸入，經歸納推理而得到一般性原則。,3. DSS中的決策過程,（1） 驗證型歸納的決策過程 其歸納推理部分即為數(shù)據(jù)實驗室的人-機交互試驗，簡稱數(shù)據(jù)實驗室試驗。 OLAP是DSS常用的驗證型歸納推理。,圖4.13 DSS中驗證型歸納決策過程示意圖,數(shù)據(jù) （數(shù)據(jù)倉庫）,一般性規(guī)則,數(shù)據(jù)實驗室 試驗,3. DSS中的決策過程,（2） 探索型歸納的決策過程 其歸納推理部分即為各種類型算法調用。 數(shù)據(jù)挖掘是DSS常用的探索型歸納推理。,圖4.14 DSS中探索型歸納決策過程示意圖,數(shù)據(jù) （數(shù)據(jù)倉庫）,一般性規(guī)則,算法調用,3. DSS中的決策過程,3.3 包含推理的DSS總體結構圖 DSS主要由數(shù)據(jù)倉庫與決策推理兩部分組成，加上結果展示模塊，構成了完整的決策過程。如圖4.15所示。,4. 知識與知識表示方法,知識庫：存放各種規(guī)則、因果關系和決策人員的經驗等 推理機：綜合運用知識庫、數(shù)據(jù)庫和定量計算的結果，進行推理和問題求解。,DSS能夠有效支持單純用定量方法無法很好解決的半/非結構化問題的求解，主要依靠知識庫和推理機的運用。,4.1 基本概念,數(shù)據(jù)：客觀事物的屬性、數(shù)量、位置及其相互關系等的抽象表示 例如：,二元組：（面粉，白色） 三元組： (中國，亞洲，在東面) (+, 8, 5): 今年8歲的孩子5年后的年齡 五元組： (+, X, Y, Z): X+Y=Z,4.1 基本概念,信息：數(shù)據(jù)所表示的含義（語義），是對數(shù)據(jù)的解釋。 一般可用一組描述詞及其值來表示： （描述詞1：值，描述詞2：值，）,例： （時間：2006.10.1, 地點：大連地區(qū)，天氣：晴朗，程度：十分）,4.1 基本概念,知識：以各種科學方式將多個信息關聯(lián)在一起形成的信息結構。 原子事實：不與任何其他信息發(fā)生關聯(lián)的單獨信息，是知識的一個特例。,例： “他是軍人”、“他穿軍裝”均為原子事實； 而“如果他是軍人，則他穿軍裝”是一條常識性知識。 另外，“如果某地重度異常，則有鋁礦”是一條知識，但是不正確。,4.1 基本概念,知識的正確型類型： 正確，錯誤，部分正確，未知真假 知識的關聯(lián)形式多種多樣，可以是分層次的，即可以把知識解釋為一種分層次關聯(lián)的信息結構 可以用BNF形式定義知識,4.1 基本概念,知識:=| | | | :=|(的一個序列） := (的一個序列） :=,4.1 基本概念,知識的分類 事實：指人類對于客觀事物屬性的值或狀態(tài)的描述，不包含任何變量，可以用一個值為真的命題陳述，或者用一種狀態(tài)的描述來表達。 例如：,大海是藍色的 我今年18歲 今天很熱,4.1 基本概念,規(guī)則：指可以分為前提（條件）和結論兩個部分，用以表達因果關系的知識。 一般形式為：如果A，則B A-B 可以用三段論推理形成一條推理鏈。,4.1 基本概念,規(guī)律：規(guī)則知識可分為帶變量和不帶變量兩種形式。將帶變量的規(guī)則稱為規(guī)律。 規(guī)律中的變量一旦被實例化為一個具體的值，則規(guī)律就變成了一條不帶變量的規(guī)則 一條規(guī)律通過變量實例化，可以派生出許多規(guī)則。因此，在這種意義上規(guī)律表示了一類知識，比規(guī)則更寬泛。,4.1 基本概念,知識的屬性 真實性：應為經過實踐檢驗的或者可用邏輯推理證明真?zhèn)蔚?相對性：在一定的條件和環(huán)境內有效 不完全性：許多知識是部分正確的 模糊性：許多知識不是完全精確的,4.1 基本概念,可表示性：可用某種方式加以描述 符號，圖形，形態(tài)，等等 可存儲性：可存儲于人類大腦中，可以記錄在書本上，也可以存儲在電腦中。 可傳遞性：知識可通過某種媒體進行傳遞。 可處理性：知識可以利用各種方法和工具進行處理，從一種形式轉變?yōu)榱硪环N形式。,4.2 知識表示方法,4.2.1 一階謂詞邏輯 一階謂詞演算是一種形式語言，可用來表示各種“事實”，對知識表示和推理非常重要，在人工智能、知識工程等領域有重要作用。也可以作為知識庫系統(tǒng)的推理基礎。,4.2 知識表示方法,4.2.1.1 一階謂詞邏輯符號集及其知識表示 常量符號：用大寫字母A、B、C、D等表示 變量符號：用小寫字母x、y、z等表示 函數(shù)符號：用小寫字母f、g、h等表示 謂詞符號：用大寫字母P、Q、R等表示 邏輯符號： 否定 合取 析取 限定量詞： 存在量詞 全稱量詞,4.2 知識表示方法,邏輯表達式構成用語的定義 項（iterm） 變量和常量 若t1, t2, , tn為項，則f(t1,t2,tn)為函數(shù) 原子邏輯式 若以p為謂詞符號，t1, t2, , tn為項，則謂詞符號對于項的作用為：p(t1,t2,tn)是函數(shù),4.2 知識表示方法,謂詞演算語言-邏輯表達式的幾個實例 WRITE(STUDENT,PAPER) WRITE(x, y) WRITE(STUDENT,COMPUTER-CHESS) (x) WRITE(x,COMPUTER-CHESS) MARRIEDfather(JOHN),mother(JOHN) LIVES(JOHN,HOUSE) COLOR(HOUSE,YELLOW) OWNS(JOHN,CAR) = COLOR(CAR,GREEN),4.2 知識表示方法,4.2.2 語義網絡表示 1. 語義：是指語義學的符號和表達式同它所描述的對象之間的關系。 2. 語義網絡：以網絡形式表示人類知識構造的一種圖形工具，是一種有向圖。,語義網絡既可以作為人類聯(lián)想記憶的心理學模型，又可作為計算機內部知識表達的一種形式。 它既能表達事實性知識，也可以表達事實之間的聯(lián)系。,4.2 知識表示方法,3. 語義網絡中的符號 節(jié)點：語義網絡所描述的各種對象，表示各種事物、概念、屬性及知識實體，有標識，并且可以是一個語義子網絡，形成分層描述。 有向邊（?。罕硎舅B接的語義對象之間存在的某種語義聯(lián)系（關系），也有標識。 無向邊（短線）：語義網絡中的節(jié)點一般采用具有若干屬性的元組或框架來表示，由節(jié)點引出的帶標識的短線（無向邊）表示各個屬性值,4.2 知識表示方法,由上圖可以看出，由于語義網絡中的下層節(jié)點可以繼承、補充或修改其上層節(jié)點的屬性值，因此能較好地表示對象之間的繼承和變異等概念，適于表示推理、聯(lián)想、歸納等邏輯概念，可根據(jù)其表示的知識來回答各種問題，驗證各種事實（定理），乃至模仿人腦的邏輯思維，演繹或歸納出圖中沒有直接表示出來的新知識。,4.2 知識表示方法,4. 語義網絡的形式描述 一個語義網絡SN可形式化地描述為： SN= N, E 其中，N 是一個以元組或框架表示的節(jié)點的有限集，節(jié)點上的元組或框架描述該節(jié)點的各種屬性值， E是連接N 中節(jié)點的帶標識的有向邊的集合，有向邊上的標識描述該有向邊所代表的語義聯(lián)系。,4.2 知識表示方法,語義網絡語法結構BNF描述 :=|Merge(, := :=(, ) :=:屬性值 := | ,4.2 知識表示方法,5. 常用的語義聯(lián)系 ISA聯(lián)系：“是一個（只，條，種,）聯(lián)系” “A ISA B”表示A是B的一個特例，B是比A更抽象的一個概念。 ISA聯(lián)系在語義上可以表達很廣泛的聯(lián)系： 子集/超集關系 廣義化/特殊化 - 抽象化/具體化,4.2 知識表示方法,概念包含關系 槽(slot)值的限制關系。例如：大象的軀體是一個1.3米長的圓柱體。 集合及其特征類的關系。 集合及其元素間的關系 謂詞關系。例如：A是一個紅球-紅色（A）,4.2 知識表示方法,5. 常用的語義聯(lián)系 Subset-of/Superset-of聯(lián)系：A是B的子集/超集 AKO聯(lián)系：A kingd of聯(lián)系，例如：企鵝AKO鳥，因此“企鵝”可以繼承“鳥”的“有翼”屬性值，也有權更改“鳥”的“能飛”屬性值。 A-Member-of/A-Element-of聯(lián)系 A-Part-of聯(lián)系 Composed-of聯(lián)系,4.2 知識表示方法,5. 常用的語義聯(lián)系 Have聯(lián)系 Before/After/At聯(lián)系：時間關系 Located-At/On/Under/聯(lián)系：位置關系 Similar-To聯(lián)系：相似或相近關系 Infer聯(lián)系：前提與結論間的推理關系 Possible-Reson聯(lián)系：是Infer聯(lián)系的反聯(lián)系,4.2 知識表示方法,4.2.3 產生式規(guī)則,產生式規(guī)則是由邏輯學家Post于上世紀40年代提出的，主要通過對符號串作替換運算（稱為Post運算）進行推理，已被運用于很多領域，例如：表示形式語言的語法，描述程序設計語言的編譯方法，或者用于各種推理系統(tǒng)的形式描述。 在產生式規(guī)則系統(tǒng)中，論域知識分為兩部分： （1）事實：各種靜態(tài)知識，如事物、事件和它們之間的關系。 （2）產生式規(guī)則：推理過程。,4.2 知識表示方法,由于這類推理系統(tǒng)的知識庫中主要存儲的是規(guī)則，因此又成為基于規(guī)則的系統(tǒng)（Rule-based system）,1、產生式規(guī)則的定義 一個產生式規(guī)則的一般形式為：PQ 其中，Q表示一組前提或狀態(tài)，P表示若干結論或動作，其含義是：如果前提Q滿足，則可推出結論P（或應該執(zhí)行動作P）。,4.2 知識表示方法,在產生式系統(tǒng)中，一般利用一個解釋程序，以匹配-執(zhí)行的方式運用產生式規(guī)則知識。即：當右部Q能與一個已證結論集合（它最初由用戶或系統(tǒng)所提供的全部事實構成）中的某個元素匹配（包括可能需要進行變量替換后才能匹配），則可運用該產生式，或推出結論P，并將其納入已證結論集，或者執(zhí)行P所代表的動作等。 如此循環(huán)往復地運用由一組產生式規(guī)則所表示的知識，以求得最終的結論，或解答問題，或證明定理。,4.2 知識表示方法,2、產生式的形式化描述及語義 :=, := :=空|, :=空|, :=| :=(, ) :=(, ),4.2 知識表示方法,3、產生式規(guī)則應用舉例 35-55歲的人稱為中年人 中年人是老練而細心的 老練而細心并且有駕駛技術的人不會出交通事故 吳連生43歲并且有駕駛技術 吳夫人37歲,問題：吳連生會出交通事故嗎？,4.2 知識表示方法,首先將上述知識用產生式表示： 中年人(x) 年齡(x,y), 小于等于(y, 55), 大于等于(y, 35) 老練(x) 中年人(x) 細心(x) 中年人(x) 不會出交通事故(x) 老練(x), 細心(x),有駕駛技術(x) 年齡(吳連生，43歲) 有駕駛技術(吳連生) 年齡(吳夫人，37歲) ,4.2 知識表示方法,推理過程如下： 中年人(吳連生) 年齡(吳連生，43歲), 小于等于(43, 55), 大于等于(43, 35) 老練(吳連生) 中年人(吳連生) 細心(吳連生) 中年人(吳連生) 不會出交通事故(吳連生) 老練(吳連生), 細心(吳連生), 有駕駛技術(吳連生),問題：吳夫人會出交通事故嗎？,4.2 知識表示方法,4.2.4 框架理論,框架理論是由美國著名人工智能專家Minsky于上世紀70年代初期提出的。他從心理學的證據(jù)出發(fā)，認為人們在日常的認知活動中使用了大量從以前經驗中獲取并經過整理的知識。這種知識往往以一種類似于框架結構的形式寄存于人腦中。,當人們面臨新的情況，或者對問題的看法有重要變化時，總是從自己的記憶中尋找一個合適的框架，然后根據(jù)實際情況對其細節(jié)加以修改和補充，形成他對所觀察到的事物的認識和處理方法。,4.2 知識表示方法,框架理論提供了一種知識組織結構，其中新的知識將用從過去經驗獲得的概念來解釋，使人們能夠利用已有經驗處理新的問題，引起對有關事物的注意、回憶和推理，比較符合人們的思維習慣，因此，它是一種理想的結構化知識表示方法。,框架是一種表示定型狀態(tài)的有層次的數(shù)據(jù)結構，其頂層是固定的，表示某個固定的概念、對象或事件，其下層由一些稱為槽(Slot)的結構組成。每個槽可按實際情況用一定類型的實例或數(shù)據(jù)所填充（也稱賦值，所填充的內容稱為槽值）。下層的槽可以是一個能夠進一步分層的子框架。,4.2 知識表示方法,相互關聯(lián)的框架連接起來構成框架系統(tǒng)，或稱框架網絡。不同的框架網絡通過信息檢索網絡，由可組成更大的網絡，代表一塊完整的知識模塊,1、框架理論的運用 （廣義）匹配：尋找一個其槽值與已知項目a, b, z一致的框架 讓步：當無法尋找到一個與給定項目完全匹配的框架時，則可重新尋找新的框架，或者做出一些讓步，接受一個相近的框架 相似網絡：相似框架按照相似度用指針相連，形成一個檢索網絡。,4.2 知識表示方法,2、框架的形式化描述及語義 := :=框架名 :=| (, ) := :=約束, 框架名:= 約束:=,4.2 知識表示方法,:=, := :=| :=| | | :=| :=|,| ,4.2 知識表示方法,3、框架系統(tǒng)的預定義槽 ISA槽 Subclass/Superclas槽 AKO槽 Instance槽 Part-of槽 Have槽 Before/After/At槽,4.2 知識表示方法,3、框架系統(tǒng)的預定義槽 Locate-At/-On/-Under/-Inside/-Outside槽 Similar-To槽 Near-to槽 Infer槽 Possible-Reson槽 Classification槽 ,