【正文】 行的，為使學(xué)習(xí)算法能在一次學(xué)習(xí)循環(huán)中值函數(shù)滿足上式迭代，設(shè)計 TD(λ)算法如右邊所示。其中通過構(gòu)造 e(s)函數(shù)，即可以保證在一次學(xué)習(xí)循環(huán)中值函數(shù)正確更新。 2022/2/15 《人工智能》 79 Q學(xué)習(xí)算法 Q 學(xué)習(xí)算法是由 Watkins 在 1989 年提出的一種無模型強(qiáng)化學(xué)習(xí)算法 。 Q學(xué)習(xí)可以看作一種增量式動態(tài)規(guī)劃，它通過直接優(yōu)化一個可迭代計算的動作值函數(shù) Q(s,a)來找到一個策略 ， 使得期望折扣報酬總和最大，而非 TD算法中的狀態(tài)值 V(s)。 Watkins 定義 Q函數(shù)為在狀態(tài) st下執(zhí)行動作 at ， 且此后按最優(yōu)動作序列執(zhí)行時的折扣累計強(qiáng)化值，即： Q函數(shù)的迭代公式為： (其中 ??[0,1]為學(xué)習(xí)因子 ) ? ?AaasQrasQ tattt ??? ? |),(m a x),( 1?? ?),(),(max),(),( 1 tttattttt asQasQrasQasQ ???? ???2022/2/15 《人工智能》 80 算法在初始過程中初始化每個 Q(s,a)值，然后根據(jù)貪心策略選擇最大的 Q值，再通過迭代式得到實際迭代值，當(dāng)?shù)竭_(dá)目標(biāo)狀態(tài)時此次迭代過程結(jié)束，再繼續(xù)從初始狀態(tài)進(jìn)行迭代，直至學(xué)習(xí)過程結(jié)束。 2022/2/15 《人工智能》 81 知識發(fā)現(xiàn) 近年來， 隨著大型數(shù)據(jù)庫不斷地涌現(xiàn)，如何迅速而準(zhǔn)確地獲得其中有用的信息和知識 , 以預(yù)測模式和發(fā)現(xiàn)趨勢、創(chuàng)建和測試假設(shè)、產(chǎn)生形象化的表示等 , 已成為數(shù)據(jù)庫系統(tǒng)和機(jī)器學(xué)習(xí)中一個關(guān)鍵性的研究課題。 數(shù)據(jù)庫系統(tǒng)雖然提供了對數(shù)據(jù)的管理和分析處理，但無法從中尋找和發(fā)現(xiàn)某些規(guī)律和模式。而人工智能處理方式很難對龐大的數(shù)據(jù)進(jìn)行有效的處理和應(yīng)用。 機(jī)器學(xué)習(xí)能夠通過對數(shù)據(jù)及其關(guān)系的分析，提取出隱含在海量數(shù)據(jù)中的知識。數(shù)據(jù)庫知識發(fā)現(xiàn) (knowledge discovery and database, 簡稱 KDD)技術(shù)就是在這種背景下應(yīng)運(yùn)而生的，我們把 KDD簡稱為知識發(fā)現(xiàn)。 2022/2/15 《人工智能》 82 知識發(fā)現(xiàn)的發(fā)展和定義 知識發(fā)現(xiàn)最早是于 1989年 8月在第 11屆國際人工智能聯(lián)合會議的專題討論會上提出。知識發(fā)現(xiàn)的產(chǎn)生和發(fā)展與數(shù)據(jù)處理的發(fā)展有密切的聯(lián)系。 ? 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ù)集中辨識出有效的、新穎的、潛在有用的、并可被理解的模式的高級處理過程。 對此定義的進(jìn)一步解釋： (1) 數(shù)據(jù)集： 是指一個有關(guān)事實 F的集合，它是用來描述事物有關(guān)方面的信息，是進(jìn)一步發(fā)現(xiàn)知識的原材料。 (2) 新穎： 經(jīng)過知識發(fā)現(xiàn)提取出的模式 E必須是新穎的。通常可以用一個函數(shù) N(E,F)來表示模式的新穎程度。 (3) 潛在有用： 提取出的模式應(yīng)該是有意義的，這可以通過某些函數(shù)的值來衡量。 (4) 可被人理解： 知識發(fā)現(xiàn)的一個目標(biāo)就是將數(shù)據(jù)庫中隱含的模式以容易被人理解的形式表現(xiàn)出來，從而幫助人們更好地了解數(shù)據(jù)庫中所包含的信息。 2022/2/15 《人工智能》 85 (5) 模式： 對于集合 F中的數(shù)據(jù)，可以用語言 L以表達(dá)式 E描述其中某些數(shù)據(jù)的特性。一個表達(dá)式 E所描述的數(shù)據(jù)是 F一個子集 FE，只有當(dāng)表達(dá)式 E比列舉出 FE中所有元素的描述方法更簡單時，才可稱為 E為一個模式。 如：“成績優(yōu)良 ={80,81,82,83,84,85,86,87,88,89}”不是模式；而“ IF 成績 ≥80 and 成績＜ 90 THEN 成績優(yōu)良”可稱為一個模式。 (6) 高級過程： 知識發(fā)現(xiàn)是對數(shù)據(jù)進(jìn)行更深層次處理的過程，而不僅僅是對數(shù)據(jù)進(jìn)行簡單的運(yùn)算或查詢，需要一定程度的智能性和自主性。 2022/2/15 《人工智能》 86 知識發(fā)現(xiàn)的處理過程 Knowledge 原始數(shù)據(jù) 目標(biāo)數(shù)據(jù) 整理后數(shù)據(jù) 變換后數(shù)據(jù) 模式 /模型 知識 數(shù)據(jù) 選擇 數(shù)據(jù) 預(yù)處理 降維 / 轉(zhuǎn)換 數(shù)據(jù) 挖掘 解釋 評價 2022/2/15 《人工智能》 87 數(shù)據(jù)選擇。 一個數(shù)據(jù)倉庫包含了各種數(shù)據(jù) , 所以有必要根據(jù)用戶的需求從中提取與 KDD相關(guān)的數(shù)據(jù)。 數(shù)據(jù)預(yù)處理。 主要是對上述數(shù)據(jù)進(jìn)行再加工，包括消除“噪聲”或去掉無用的數(shù)據(jù)，彌補(bǔ)遺漏數(shù)據(jù)，說明時間序列信息和已知的變化等。 數(shù)據(jù)降維和轉(zhuǎn)換 所謂降維指在考慮了數(shù)據(jù)的不變表示的情況下 , 減少變量的實際數(shù)目。轉(zhuǎn)換包括對數(shù)據(jù)組織、數(shù)據(jù)類型轉(zhuǎn)換、數(shù)據(jù)屬性轉(zhuǎn)換等。 。 根據(jù)用戶要求，確定 KDD的目標(biāo)，利用一種或多種技術(shù)，相繼地挖掘已轉(zhuǎn)換的數(shù)據(jù)，抽取感興趣的信息。 知識評價。 這一過程主要用于對所獲得的知識進(jìn)行價值評定，以決定所得的規(guī)則是否存入基礎(chǔ)知識庫。 2022/2/15 《人工智能》 88 知識發(fā)現(xiàn)的方法 知識發(fā)現(xiàn)的方法有統(tǒng)計方法、機(jī)器學(xué)習(xí)、神經(jīng)計算和可視化方法等。 統(tǒng)計方法 統(tǒng)計方法是從事物的外在數(shù)量上的表現(xiàn)去推斷該事物可能的規(guī)律性。與統(tǒng)計學(xué)有關(guān)的知識發(fā)現(xiàn)方法有： (1) 傳統(tǒng)方法 常見的統(tǒng)計方法有回歸分析、判別分析、聚類分析等。 (2) 模糊集 (3) 支持向量機(jī) 針對兩類分類問題，在高維空間中尋找一個超平面作為兩類的分割，以保證最小的錯誤分類率。 (4) 粗糙集 2022/2/15 《人工智能》 89 機(jī)器學(xué)習(xí)方法 可能用于知識發(fā)現(xiàn)的機(jī)器學(xué)習(xí)方法有： (1) 規(guī)則歸納。 規(guī)則反映數(shù)據(jù)項中某些屬性或數(shù)據(jù)集中某些數(shù)據(jù)項之間的統(tǒng)計相關(guān)性。 (2) 決策樹。 決策樹的每一個非終葉節(jié)點表示所考慮的數(shù)據(jù)項的測試或決策。 (3) 范例推理。 范例推理是直接使用過去的經(jīng)驗或解法來求解給定的問題。 (4) 貝葉斯信念網(wǎng)絡(luò)。 貝葉斯信念網(wǎng)是概率分布的圖表示。 (5) 科學(xué)發(fā)現(xiàn)。 科學(xué)發(fā)現(xiàn)是在實驗環(huán)境下發(fā)現(xiàn)科學(xué)定律。 (6) 遺傳算法。 在求解過程中，通過最好解的選擇和彼此組合，使期望解的集合愈來愈好。 2022/2/15 《人工智能》 90 神經(jīng)網(wǎng)絡(luò)方法 人工神經(jīng)網(wǎng)絡(luò)建立在可以自學(xué)習(xí)的數(shù)學(xué)模型的基礎(chǔ)之上，它可以對大量復(fù)雜的數(shù)據(jù)進(jìn)行分析，并可以完成對人腦或其他計算機(jī)來說極為復(fù)雜的模式抽取及趨勢分析。 可視化方法 可視化（ visualization）就是把數(shù)據(jù)、信息和知識轉(zhuǎn)化為可視的表示形式的過程?？梢暬瘮?shù)據(jù)分析技術(shù)拓寬了傳統(tǒng)的圖表功能，使用戶對數(shù)據(jù)的剖析更清楚。 2022/2/15 《人工智能》 91 數(shù)據(jù)挖掘 數(shù)據(jù)挖掘是知識發(fā)現(xiàn)處理過程的一個核心環(huán)節(jié)，其任務(wù)就是從數(shù)據(jù)中發(fā)現(xiàn)模式。 定義： 數(shù)據(jù)挖掘 (Data miningDM ) 是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中提取隱含在其中的、人們事先不知道的但又是潛在有用的信息和知識的過程。 數(shù)據(jù)挖掘和知識發(fā)現(xiàn)這兩個術(shù)語的內(nèi)涵大致相同。嚴(yán)格地講，知識發(fā)現(xiàn)是從數(shù)據(jù)庫中發(fā)現(xiàn)知識的全部過程，而數(shù)據(jù)挖掘則是此全部過程的一個特定的、關(guān)鍵步驟。 在通常情況下，許多人把數(shù)據(jù)挖掘與知識發(fā)現(xiàn)廣泛地認(rèn)為是同一個概念，一般在科研領(lǐng)域中稱為知識發(fā)現(xiàn)，而在工程領(lǐng)域則稱為數(shù)據(jù)挖掘。 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ī)則。關(guān)聯(lián)分析的目的是找出數(shù)據(jù)庫中隱藏的關(guān)聯(lián)網(wǎng)。在大型數(shù)據(jù)庫中，這種關(guān)聯(lián)規(guī)則是很多的，一般用“支持度”和“可信度”兩個閾值來淘汰那些無用的關(guān)聯(lián)規(guī)則。 ②分類 分類是找出一個類別的概念描述，它代表了這類數(shù)據(jù)的整體信息，即該類的內(nèi)涵描述，一般用規(guī)則或決策樹模式表示。 2022/2/15 《人工智能》 93 ③ 聚類 數(shù)據(jù)庫中的數(shù)據(jù)可分為一系列有意義的子集，或稱為類。在同一類別中，個體之間的距離較小，而不同類別的個體之間的距離偏大。聚類增強(qiáng)了人們對客觀現(xiàn)實的認(rèn)識，即通過聚類建立宏觀概念。 ④ 時序模式 通過時間序列搜索出重復(fù)發(fā)生概率較高的模式。這里強(qiáng)調(diào)時間序列的影響。例如，在所有購買激光打印機(jī)的人中，半年后有 80%的人再購買新硒鼓， 20%的人用舊硒鼓裝碳粉。 2022/2/15 《人工智能》 94 ⑤ 偏差檢測 數(shù)據(jù)庫中的數(shù)據(jù)常有一些異常記錄，從數(shù)據(jù)庫中檢測出這些偏差很有意義。偏差包括很多潛在的知識，如分類中的異常實例、不滿足規(guī)則的特例、觀測結(jié)果與模型預(yù)測值的偏差、量值隨時間的變化等。偏差檢測的基本方法是尋找觀測結(jié)果與參照之間的差別。 ⑥ 預(yù)測 預(yù)測是利用歷史數(shù)據(jù)找出變化規(guī)律，即建立模型，并用此模型來預(yù)測未來數(shù)據(jù)的種類、特征等。 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ù)項 。 數(shù)據(jù)項之間的關(guān)聯(lián)規(guī)則就是根據(jù)一個事務(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ù)由唯一的標(biāo)志 TID標(biāo)識。 對數(shù)據(jù)項集 X ? I ，稱 T 包含 X 當(dāng)且僅當(dāng) X ? T 對任一項集 X ? I ，在事務(wù)集 D中的 支持度 定義為 X在該事務(wù)集中出現(xiàn)的相對頻度，即： %100}|{),s up( ??? D TXTDX2022/2/15 《人工智能》 96 關(guān)聯(lián)規(guī)則 具有形式： X=Y 這里 X ? I , Y ? I ，且 X∩Y =Φ, X 稱為規(guī)則的條件 , Y 稱為規(guī)則的結(jié)果。其意義是：一個事務(wù)中某些項的出現(xiàn) , 可推導(dǎo)出另一些項在同一事務(wù)中也出現(xiàn)。 一條規(guī)則 X=Y的 支持度 定義為：在集合 D 中 同時包含 X 和 Y 的事務(wù)數(shù)量與 D中的 總事務(wù)量之比 ，即： %100}|{),s up ( ????? D TYXTDYX 一條規(guī)則 X=Y的 可信度 定義為：在集合 D 中，包含 X 的事務(wù)中有多大可能性也包含 Y。即： %100),s up ( ),s up (%100}|{ }|{),( ????? ???? DX DYXTXT TYXTDYXc on f2022/2/15 《人