【正文】 即： %100),s up ( ),s up (%100}|{ }|{),( ????? ???? DX DYXTXT TYXTDYXc on f2022/2/15 《人工智。其意義是：一個事務(wù)中某些項的出現(xiàn) , 可推導(dǎo)出另一些項在同一事務(wù)中也出現(xiàn)。挖掘關(guān)聯(lián)規(guī)則的問題描述如下 : 令 I= {i1, i2, ?, im }是所有項目（數(shù)據(jù)項）集， D是全體事務(wù)的集合（數(shù)據(jù)庫），事務(wù) T 是 I 的一個子集 T ?I ，每個事務(wù)由唯一的標志 TID標識。 2022/2/15 《人工智能》 95 關(guān)聯(lián)規(guī)則挖掘 關(guān)聯(lián)規(guī)則是描述數(shù)據(jù)庫中數(shù)據(jù)項之間存在的潛在關(guān)系的規(guī)則 ，形式為 ： A1∧ A2∧ . . . ∧ Am = B1∧ B2∧ … ∧ Bn 其中 ， A i、 Bj是數(shù)據(jù)庫中 的數(shù)據(jù)項 。偏差檢測的基本方法是尋找觀測結(jié)果與參照之間的差別。 2022/2/15 《人工智能》 94 ⑤ 偏差檢測 數(shù)據(jù)庫中的數(shù)據(jù)常有一些異常記錄，從數(shù)據(jù)庫中檢測出這些偏差很有意義。這里強調(diào)時間序列的影響。聚類增強了人們對客觀現(xiàn)實的認識，即通過聚類建立宏觀概念。 2022/2/15 《人工智能》 93 ③ 聚類 數(shù)據(jù)庫中的數(shù)據(jù)可分為一系列有意義的子集，或稱為類。在大型數(shù)據(jù)庫中，這種關(guān)聯(lián)規(guī)則是很多的，一般用“支持度”和“可信度”兩個閾值來淘汰那些無用的關(guān)聯(lián)規(guī)則。 2022/2/15 《人工智能》 92 數(shù)據(jù)挖掘的類型 數(shù)據(jù)挖掘按其功能劃分主要包括以下幾類 ： ①關(guān)聯(lián)分析 若兩個或多個數(shù)據(jù)項的取值重復(fù)出現(xiàn)且概率很高時，它就存在著某種關(guān)聯(lián)，可以建立起這些數(shù)據(jù)項的關(guān)聯(lián)規(guī)則。嚴格地講，知識發(fā)現(xiàn)是從數(shù)據(jù)庫中發(fā)現(xiàn)知識的全部過程，而數(shù)據(jù)挖掘則是此全部過程的一個特定的、關(guān)鍵步驟。 定義： 數(shù)據(jù)挖掘 (Data miningDM ) 是從大量的、不完全的、有噪聲的、模糊的、隨機的數(shù)據(jù)中提取隱含在其中的、人們事先不知道的但又是潛在有用的信息和知識的過程?？梢暬瘮?shù)據(jù)分析技術(shù)拓寬了傳統(tǒng)的圖表功能，使用戶對數(shù)據(jù)的剖析更清楚。 2022/2/15 《人工智能》 90 神經(jīng)網(wǎng)絡(luò)方法 人工神經(jīng)網(wǎng)絡(luò)建立在可以自學習的數(shù)學模型的基礎(chǔ)之上，它可以對大量復(fù)雜的數(shù)據(jù)進行分析，并可以完成對人腦或其他計算機來說極為復(fù)雜的模式抽取及趨勢分析。 (6) 遺傳算法。 (5) 科學發(fā)現(xiàn)。 (4) 貝葉斯信念網(wǎng)絡(luò)。 (3) 范例推理。 (2) 決策樹。 (4) 粗糙集 2022/2/15 《人工智能》 89 機器學習方法 可能用于知識發(fā)現(xiàn)的機器學習方法有： (1) 規(guī)則歸納。與統(tǒng)計學有關(guān)的知識發(fā)現(xiàn)方法有： (1) 傳統(tǒng)方法 常見的統(tǒng)計方法有回歸分析、判別分析、聚類分析等。 2022/2/15 《人工智能》 88 知識發(fā)現(xiàn)的方法 知識發(fā)現(xiàn)的方法有統(tǒng)計方法、機器學習、神經(jīng)計算和可視化方法等。 知識評價。 。 數(shù)據(jù)降維和轉(zhuǎn)換 所謂降維指在考慮了數(shù)據(jù)的不變表示的情況下 , 減少變量的實際數(shù)目。 數(shù)據(jù)預(yù)處理。 2022/2/15 《人工智能》 86 知識發(fā)現(xiàn)的處理過程 Knowledge 原始數(shù)據(jù) 目標數(shù)據(jù) 整理后數(shù)據(jù) 變換后數(shù)據(jù) 模式 /模型 知識 數(shù)據(jù) 選擇 數(shù)據(jù) 預(yù)處理 降維 / 轉(zhuǎn)換 數(shù)據(jù) 挖掘 解釋 評價 2022/2/15 《人工智能》 87 數(shù)據(jù)選擇。 如：“成績優(yōu)良 ={80,81,82,83,84,85,86,87,88,89}”不是模式；而“ IF 成績 ≥80 and 成績＜ 90 THEN 成績優(yōu)良”可稱為一個模式。 2022/2/15 《人工智能》 85 (5) 模式： 對于集合 F中的數(shù)據(jù)，可以用語言 L以表達式 E描述其中某些數(shù)據(jù)的特性。 (3) 潛在有用： 提取出的模式應(yīng)該是有意義的，這可以通過某些函數(shù)的值來衡量。 (2) 新穎： 經(jīng)過知識發(fā)現(xiàn)提取出的模式 E必須是新穎的。 ? 1960s: Data collection, database creation, IMS and work DBMS. ? 1970s: Relational data model, relational DBMS implementation. ? 1980s: RDBMS, advanced data models (extendedrelational, OO, deductive, etc.) and applicationoriented DBMS (spatial, scientific, engineering, etc). ? 1990s: Data mining and data warehousing, multimedia databases, and Web technology. 2022/2/15 《人工智能》 83 ? 1989 IJCAI Workshop on KDD ? Knowledge Discovery in Databases (G. PiatetskyShapiro and W. Frawley, eds., 1991) ? 19911994 Workshops on KDD ? Advances in Knowledge Discovery and Data Mining (U. Fayyad, G. PiatetskyShapiro, P. Smyth, and R. Uthurusamy, eds., 1996) ? 19951998 AAAI Int. Conf. on KDD and DM (KDD’9598) ? Journal of Data Mining and Knowledge Discovery (1997) ? 1998 ACM SIGKDD ? 1999 SIGKDD’99 Conf. Important dates of data mining 2022/2/15 《人工智能》 84 定義： KDD是從大量數(shù)據(jù)集中辨識出有效的、新穎的、潛在有用的、并可被理解的模式的高級處理過程。 2022/2/15 《人工智能》 82 知識發(fā)現(xiàn)的發(fā)展和定義 知識發(fā)現(xiàn)最早是于 1989年 8月在第 11屆國際人工智能聯(lián)合會議的專題討論會上提出。 機器學習能夠通過對數(shù)據(jù)及其關(guān)系的分析，提取出隱含在海量數(shù)據(jù)中的知識。 數(shù)據(jù)庫系統(tǒng)雖然提供了對數(shù)據(jù)的管理和分析處理，但無法從中尋找和發(fā)現(xiàn)某些規(guī)律和模式。 Watkins 定義 Q函數(shù)為在狀態(tài) st下執(zhí)行動作 at ， 且此后按最優(yōu)動作序列執(zhí)行時的折扣累計強化值，即： Q函數(shù)的迭代公式為： (其中 ??[0,1]為學習因子 ) ? ?AaasQrasQ tattt ??? ? |),(m a x),( 1?? ?),(),(max),(),( 1 tttattttt asQasQrasQasQ ???? ???2022/2/15 《人工智能》 80 算法在初始過程中初始化每個 Q(s,a)值，然后根據(jù)貪心策略選擇最大的 Q值，再通過迭代式得到實際迭代值，當?shù)竭_目標狀態(tài)時此次迭代過程結(jié)束，再繼續(xù)從初始狀態(tài)進行迭代，直至學習過程結(jié)束。 2022/2/15 《人工智能》 79 Q學習算法 Q 學習算法是由 Watkins 在 1989 年提出的一種無模型強化學習算法 。 2022/2/15 《人工智能》 77 stst + 1rt + 1st + 2λ rt + 1st + 3λ2rt + 2? ?st + TλT 1rt + T 那么值函數(shù)迭代為： ? ? ? ? ? ?t t t tV s V s R V s? ?? ? ?????2022/2/15 《人工智能》 78 由于強化學習算法中值函數(shù)的更新是在每一學習步進行的，為使學習算法能在一次學習循環(huán)中值函數(shù)滿足上式迭代，設(shè)計 TD(λ)算法如右邊所示。因此，我們考慮：能否在值函數(shù)更新中，不僅僅依賴當前狀態(tài)的瞬時獎賞值，也可以利用下一狀態(tài)的瞬時獎賞值，一直到終結(jié)狀態(tài)？ 為此，構(gòu)造一個新的 λ返回函數(shù) Rt′： 211 2 3 Tt t t t t TR r r r r? ? ? ?? ? ? ?? ? ? ? ? ? 其中假定系統(tǒng)在此次學習循環(huán)中第 T步后進入終結(jié)狀態(tài)。 TD (?)算法的收斂速度有很大程度上的提高。 TD (0) 算法如式： ? ?)()()()( 11 ttttt sVsVrsVsV ???? ?? ?? 與 MC算法相比 ，上式中用回報的估計值 rt+1+?V(st+1)代替了實際回報值 Rt。 最簡單的算法為一步 TD 算法，即 TD (0) 算法，是一種自適應(yīng)的策略迭代算法。控制過程采用貪心搜索策略。 對 s 的值函數(shù)的更新有兩種方法： (1) first visit MC 將回報賦予第一次訪問的 s； (2) every visit MC 將每次訪問 s 到 t 的回報平均后賦予 s。當環(huán)境狀態(tài)為終止狀態(tài)時，將得到積累回報賦予開始狀態(tài) s 的值函數(shù) V。 如部分有關(guān)狀態(tài)序列、動作行為集以及同環(huán)境交互產(chǎn)生的獎賞值的信息。 2022/2/15 《人工智能》 72 強化學習算法 到目前為止，研究者們提出了很多強化學習算法，近年來對強化學習算法的研究已由算法本身逐漸轉(zhuǎn)向研究經(jīng)典算法在各種復(fù)雜環(huán)境中的應(yīng)用，較有影響的強化學習算法有 TD 算法， Q 學習算法， Sarsa算法，Dyan 算法， R 學習算法， H 學習等，還有一些改進算法，如滯后更新多步 Q學習算法等。 ? ?11()()( ) m a x ( ) ,m a x ( )t t t ta A saass ssa A ssV s E r V s s s a aP R V s????????????? ? ? ?????? ??? 由于強化學習中， P函數(shù)和 R函數(shù)未知，系統(tǒng)無法直接求解上面的值函數(shù)。因此在 π策略下，系統(tǒng)在 s狀態(tài)下的值函數(shù)由下式定義，其反映了如果系統(tǒng)遵循 π策略，所能獲得的期望的累計獎賞折扣和。 1132211 ????? ?????? tttttt RrrrrrR ??? ?? ?? ??????????????a sassasstttttsVRPassssVrEssREsV)(),(}|)({}|{)( 11???????? 由于環(huán)境是不確定的，系統(tǒng)在某個策略 π指導(dǎo)下的每一次學習循環(huán)中所得到的 Rt有可能是不同的。但由于在選擇行為策略過程中，要考慮到環(huán)境模型的不確定性和目標的長遠性，因此在策略和瞬時獎賞之間構(gòu)造值函數(shù)（即狀態(tài)的效用函數(shù)），用于策略的選擇。 而強化學習著重研究在 P函數(shù)和 R函數(shù)未知的情況下，系統(tǒng)如何學習最優(yōu)行為策略。 2022/2/15 《人工智能》 69 馬氏決策過程的本質(zhì)是：當前狀態(tài)向下一狀態(tài)轉(zhuǎn)移的概率和獎賞值只取決于當前狀態(tài)和選擇的動作，而與歷史狀態(tài)和歷史動作無關(guān)。包含一個環(huán)境狀態(tài)集 S，系統(tǒng)行為集合 A，獎賞函數(shù) R： S A→ ? 和狀態(tài)轉(zhuǎn)移函數(shù) P：S A→PD(S) 。下面首先給出馬氏決策過程的形式化定義。這和生理學中的條件反射原理是接近的。 ???????022110iii rrrr ??? ?2022/2/15 《人工智能》 68 強化學習技術(shù)的 基本原理 是：如果系統(tǒng)某個動作導(dǎo)致環(huán)境正的獎賞，那么系統(tǒng)以后產(chǎn)生這個動作的趨勢便會加強。 agent 獲得的總獎賞值為 : 其中 ∈ [0,1] 為折扣因子。 強化學習的結(jié)構(gòu) Agent 環(huán)境 狀態(tài) s 獎賞 r 動作 a 2022/2/15 《人工智能》 67 強化學習模型由以下部分組成： 強化學習模型 ? 一個離散的狀態(tài)集 S ={ s0 , s1 , s2 , ?, sn }； ? 動作集 A={ a0 , a1 , a2 , ?, an} ； ? 一個強化值集 r ∈ R； ? agent 和環(huán)境交互的狀態(tài) — 動作序列 (si,ai) → ri，表示 agent 在狀態(tài) si 下執(zhí)行動作 ai 獲得的立即獎賞值 ri。選擇的動作不僅影響立即強化值而且還影響下一時刻的狀態(tài)及最終強化