數(shù)據(jù)挖掘算法-enet下載頻道-免費(fèi)軟件下載-綠色軟件下載

1、數(shù)據(jù)挖掘算法,Wang Ye 2006.8,一、概念和術(shù)語,1.1 數(shù)據(jù)挖掘 / 知識(shí)發(fā)現(xiàn)（1）數(shù)據(jù)挖掘是從存放在數(shù)據(jù)集中的大量數(shù)據(jù)挖掘出有趣知識(shí)的過程。（2）數(shù)據(jù)挖掘，又稱為數(shù)據(jù)庫(kù)中知識(shí)發(fā)現(xiàn)（Knowledge Discovery in Databases）或知識(shí)發(fā)現(xiàn)，它是一個(gè)從大量數(shù)據(jù)中抽取挖掘出未知的、有價(jià)值的模式或規(guī)律等知識(shí)的非平凡過程，它與數(shù)據(jù)倉(cāng)庫(kù)有著密切的聯(lián)系。（3）廣義的數(shù)據(jù)挖掘是指知識(shí)發(fā)現(xiàn)的全過程；狹義的數(shù)據(jù)挖掘是

2、指統(tǒng)計(jì)分析、機(jī)器學(xué)習(xí)等發(fā)現(xiàn)數(shù)據(jù)模式的智能方法，即偏重于模型和算法。（4）數(shù)據(jù)庫(kù)查詢系統(tǒng)和專家系統(tǒng)不是數(shù)據(jù)挖掘！在小規(guī)模數(shù)據(jù)上的統(tǒng)計(jì)分析和機(jī)器學(xué)習(xí)過程也不應(yīng)算作數(shù)據(jù)挖掘。,1.2 機(jī)器學(xué)習(xí)（1）對(duì)于某類任務(wù)T和性能度量P，如果一個(gè)計(jì)算機(jī)程序在T上以P衡量的性能隨著經(jīng)驗(yàn)E而自我完善，那么這個(gè)計(jì)算機(jī)程序被稱為在從經(jīng)驗(yàn)E學(xué)習(xí)。（2）機(jī)器學(xué)習(xí)是知識(shí)發(fā)現(xiàn)的一種方法，是指一個(gè)系統(tǒng)通過執(zhí)行某種過程而改進(jìn)它處理某一問題的能力。,1.3 數(shù)據(jù)挖掘的對(duì)

3、象（1）關(guān)系型數(shù)據(jù)庫(kù)、事務(wù)型數(shù)據(jù)庫(kù)、面向?qū)ο蟮臄?shù)據(jù)庫(kù)；（2）數(shù)據(jù)倉(cāng)庫(kù) / 多維數(shù)據(jù)庫(kù)；（3）空間數(shù)據(jù)（如地圖信息）（4）工程數(shù)據(jù)（如建筑、集成電路的信息）（5）文本和多媒體數(shù)據(jù)（如文本、圖象、音頻、視頻數(shù)據(jù)）（6）時(shí)間相關(guān)的數(shù)據(jù)（如歷史數(shù)據(jù)或股票交換數(shù)據(jù)）（7）萬維網(wǎng)（如半結(jié)構(gòu)化的HTML，結(jié)構(gòu)化的XML以及其他網(wǎng)絡(luò)信息）,1.4 數(shù)據(jù)挖掘的步驟（1）數(shù)據(jù)清理（消除噪音或不一致數(shù)據(jù)，補(bǔ)缺）；（2）數(shù)據(jù)集成（多種數(shù)據(jù)源可

4、以組合在一起）；（3）數(shù)據(jù)選擇（從數(shù)據(jù)庫(kù)中提取相關(guān)的數(shù)據(jù)）；（4）數(shù)據(jù)變換（變換成適合挖掘的形式）；（5）數(shù)據(jù)挖掘（使用智能方法提取數(shù)據(jù)模式）；（6）模式評(píng)估（識(shí)別提供知識(shí)的真正有趣模式）；（7）知識(shí)表示（可視化和知識(shí)表示技術(shù)）。,1.5 支持?jǐn)?shù)據(jù)挖掘的關(guān)鍵技術(shù)（1）數(shù)據(jù)庫(kù) / 數(shù)據(jù)倉(cāng)庫(kù) / OLAP（2）數(shù)學(xué) / 統(tǒng)計(jì)（回歸分析：多元回歸、自回歸；判別分析：Bayes判別、Fisher判別、非參數(shù)判別；主成分分析、相關(guān)性

5、分析；模糊集；粗糙集）（3）機(jī)器學(xué)習(xí)（聚類分析；關(guān)聯(lián)規(guī)則；決策樹；范例推理；貝葉斯網(wǎng)絡(luò)；神經(jīng)網(wǎng)絡(luò)；支持向量機(jī)；遺傳算法）（4）可視化：將數(shù)據(jù)、知識(shí)和規(guī)則轉(zhuǎn)化為圖形表現(xiàn)的形式。,1.6 數(shù)據(jù)倉(cāng)庫(kù)（1）數(shù)據(jù)倉(cāng)庫(kù)是一個(gè)面向主題的、集成的、隨時(shí)間變化的、非易失性數(shù)據(jù)的集合，用于支持管理人員的決策。（2）數(shù)據(jù)倉(cāng)庫(kù)是一種多個(gè)異種數(shù)據(jù)源在單個(gè)站點(diǎn)以統(tǒng)一的模式組織的存儲(chǔ)，以支持管理決策。數(shù)據(jù)倉(cāng)庫(kù)技術(shù)包括數(shù)據(jù)清理、數(shù)據(jù)集成和聯(lián)機(jī)分析處理（OLAP

6、）。（3）數(shù)據(jù)倉(cāng)庫(kù)的邏輯結(jié)構(gòu)是多維數(shù)據(jù)庫(kù)。數(shù)據(jù)倉(cāng)庫(kù)的實(shí)際物理結(jié)構(gòu)可以是關(guān)系數(shù)據(jù)存儲(chǔ)或多維數(shù)據(jù)方（Cube）。（4）數(shù)據(jù)方是由維度（Dimension）和度量（Measure）定義的一種數(shù)據(jù)集，度量存放在由維度索引的數(shù)據(jù)方單元中。維度對(duì)應(yīng)于模式中的屬性組，度量對(duì)應(yīng)于與主題相關(guān)的事實(shí)數(shù)據(jù)。數(shù)據(jù)方的物化是指預(yù)計(jì)算并存儲(chǔ)全部或部分單元中的度量。,1.7 數(shù)據(jù)倉(cāng)庫(kù)的模型（1）星形模式：最常見模型；其中數(shù)據(jù)倉(cāng)庫(kù)包括一個(gè)大的、包含大批數(shù)據(jù)、不含

7、冗余的中心表（事實(shí)表）；一組小的附屬表（維表），每維一個(gè)。（2）雪花模式：雪花模式是星型模式的變種，其中某些維表是規(guī)范化的，因而把數(shù)據(jù)進(jìn)一步分解到附加的表中。（3）星系模式：多個(gè)事實(shí)表共享維表。這種模式可以看作星形模式集，因此稱為星系模式，或事實(shí)星座。,1.8 典型的OLAP操作（1）OLAP是一種多維數(shù)據(jù)分析技術(shù)。包括匯總、合并和聚集等功能，以及從不同的角度觀察信息的能力。（2）上卷：從某一維度的更高概念層次觀察數(shù)據(jù)方，獲得更

8、概要的數(shù)據(jù)。它通過沿維的概念分層向上或維歸約來實(shí)現(xiàn)。（3）下鉆：下鉆是上卷的逆操作。它從某一維度的更低概念層次觀察數(shù)據(jù)方，獲得更詳細(xì)的數(shù)據(jù)。下鉆可以通過沿維的概念分層向下或引入新的維來實(shí)現(xiàn)。（4）切片和切塊：切片操作在給定的數(shù)據(jù)方的選擇一個(gè)維的部分屬性，獲得一個(gè)較小的子數(shù)據(jù)方。切塊操作通過對(duì)選擇兩個(gè)或多個(gè)維的部分屬性，獲得一個(gè)較小的子數(shù)據(jù)方。（5）轉(zhuǎn)軸：是一種改變數(shù)據(jù)方二維展現(xiàn)形式的操作。它將數(shù)據(jù)方的二維展現(xiàn)中的某些維度由行改為列

9、，或由列改為行。,二、數(shù)據(jù)準(zhǔn)備,現(xiàn)實(shí)世界的數(shù)據(jù)是不完整的（有些感興趣的屬性缺少屬性值，或僅包含聚集數(shù)據(jù)），含噪音的（包含錯(cuò)誤，或存在偏離期望的異常值），不一致的（例如，用于商品分類的部門編碼存在差異）。需要數(shù)據(jù)清理、數(shù)據(jù)集成、數(shù)據(jù)選擇、數(shù)據(jù)變換等技術(shù)對(duì)數(shù)據(jù)進(jìn)行處理。,2.1 維歸約 / 特征提取2.1-1 決策樹歸約（1）決策樹歸約構(gòu)造一個(gè)類似于流程圖的結(jié)構(gòu)：其每個(gè)非葉子結(jié)點(diǎn)表示一個(gè)屬性上的測(cè)試，每個(gè)分枝對(duì)應(yīng)于測(cè)試的一個(gè)輸出；每個(gè)

10、葉子結(jié)點(diǎn)表示一個(gè)決策類。（2）在每個(gè)結(jié)點(diǎn)，算法選擇“當(dāng)前對(duì)分類最有幫助”的屬性，出現(xiàn)在樹中的屬性形成歸約后的屬性子集。,2.1-2 粗糙集歸約（1）粗糙集理論在數(shù)學(xué)意義上描述了知識(shí)的不確定性，它的特點(diǎn)是把用于分類的知識(shí)嵌入集合內(nèi)，使分類與知識(shí)聯(lián)系在一起。（2）知識(shí)的粒度、不可分辨關(guān)系、上近似、下近似、邊界等概念見下圖。,2.1-2 粗糙集歸約（續(xù)）（3）令Q代表屬性的集合 。q∈Q是一個(gè)屬性，如果IND(Q?q) = IND(Q

11、)，則q在S中不是獨(dú)立的；否則稱q在S中是獨(dú)立的。（4）若集合滿足IND(R) = IND(Q)且R中的每一個(gè)屬性都是獨(dú)立的，則R被稱為Q的一個(gè)“約簡(jiǎn)”，記作R = RED(Q)。（5）約簡(jiǎn)可以通過刪除冗余的（不獨(dú)立的）屬性而獲得，約簡(jiǎn)包含的屬性即為“對(duì)分類有幫助”的屬性。,2.2 數(shù)據(jù)變換2.2-1 歸一化與模糊化有限區(qū)間的歸一化：無限區(qū)間的歸一化：模糊隸屬度：,2.2-2 核函數(shù)（1）核函數(shù)的基本思想是將在低維

12、特征向量線性不可分的數(shù)據(jù)映射到線性可分的高維特征空間中去。（2）映射可以是顯式的，也可以是隱式的。顯式映射即找到一個(gè)映射關(guān)系f，使高維空間的特征向量f (x)可以被直接計(jì)算出來。（3）隱式映射，即引入一個(gè)核函數(shù)進(jìn)行整體處理，就避免了對(duì)的直接求f (x)的計(jì)算困難。核函數(shù)即某高維特征空間中向量的內(nèi)積，是核矩陣中的一個(gè)元素。（4）并不是所有的實(shí)值函數(shù)f (x)都可以作為空間映射的核函數(shù)，只有f (x)是某一特征空間的內(nèi)積時(shí)，即符合M

13、ercer條件，它才能成為核函數(shù)。,,,2.2-2 核函數(shù)（續(xù)）多項(xiàng)式函數(shù)： 高斯（RBF）函數(shù)： 多層感知機(jī)函數(shù)：低維空間向量映射到高維空間向量舉例：,,2.3 數(shù)據(jù)壓縮2.3-1 離散化離散化的用途：（1）適應(yīng)某些僅接受離散值的算法；（2）減小數(shù)據(jù)的尺度。離散化的方法包括幾下幾種。（1）等距分割；（2）聚類分割；（3）直方圖分割；（4）基于熵的分割；

14、（5）基于自然屬性的分割。,2.3-2 回歸回歸和對(duì)數(shù)線性模型可以用來近似給定的數(shù)據(jù)。在線性回歸中，用一條直線來模擬數(shù)據(jù)的生成規(guī)則。多元回歸是線性回歸的擴(kuò)展，涉及多個(gè)預(yù)測(cè)變量。在多項(xiàng)式回歸中，通過對(duì)變量進(jìn)行變換，可以將非線性模型轉(zhuǎn)換成線性的，然后用最小平方和法求解。,,,,2.3-2 回歸（續(xù)）利用線性回歸可以為連續(xù)取值的函數(shù)建模。廣義線性模型則可以用于對(duì)離散取值變量進(jìn)行回歸建模。在廣義線性模型中，因變量Y 的變化速率是Y

15、 均值的一個(gè)函數(shù)；這一點(diǎn)與線性回歸不同。常見的廣義線性模型有：對(duì)數(shù)回歸和泊松回歸。對(duì)數(shù)回歸模型是利用一些事件發(fā)生的概率作為自變量所建立的線性回歸模型。泊松回歸模型主要是描述數(shù)據(jù)出現(xiàn)次數(shù)的模型，因?yàn)樗鼈兂３１憩F(xiàn)為泊松分布。,2.3-3 主成分分析（PCA）PCA算法搜索c個(gè)最能代表數(shù)據(jù)的k-維正交向量；這里c ? k。這樣，原來的數(shù)據(jù)投影到一個(gè)較小的空間，導(dǎo)致數(shù)據(jù)壓縮。步驟如下： （1）對(duì)輸入數(shù)據(jù)歸一化，使得每個(gè)屬性都落入相同的區(qū)

16、間。（2）PCA計(jì)算c個(gè)規(guī)范正交向量，作為歸一化輸入數(shù)據(jù)的基。這些是單位向量，每一個(gè)都垂直于另一個(gè)：稱為主成分。輸入數(shù)據(jù)是主要成分的線性組合。（3）對(duì)主成分按“意義”或強(qiáng)度降序排列，選擇部分主成分充當(dāng)數(shù)據(jù)的一組新坐標(biāo)軸 。,2.3-4 離散小波變換（DWT）離散小波變換是一種線性信號(hào)處理技術(shù)。該技術(shù)方法可以將一個(gè)數(shù)據(jù)向量轉(zhuǎn)換為另一個(gè)數(shù)據(jù)向量（為小波相關(guān)系數(shù)）；且兩個(gè)向量具有相同長(zhǎng)度?？梢陨釛夀D(zhuǎn)換后的數(shù)據(jù)向量中的一些小波相關(guān)系數(shù)。

17、保留所有大于用戶指定閾值的小波系數(shù)，而將其它小波系數(shù)置為0，以幫助提高數(shù)據(jù)處理的運(yùn)算效率。這一技術(shù)方法可以在保留數(shù)據(jù)主要特征情況下除去數(shù)據(jù)中的噪聲，因此該方法可以有效地進(jìn)行數(shù)據(jù)清洗。給定一組小波相關(guān)系數(shù)，利用離散小波變換的逆運(yùn)算還可以近似恢復(fù)原來的數(shù)據(jù)。,2.3-4 離散小波變換（續(xù)）常用的小波函數(shù)包括Haar系列, Daubechies系列，Moret系列，Sym系列，Meyer系列，Coif系列。,2.3-5 潛在語義分析潛

18、在語義分析將樣本映射到語義概念空間以發(fā)現(xiàn)樣本數(shù)據(jù)之間的潛在語義聯(lián)系。 （1）構(gòu)造“特征-樣本”矩陣，“特征-樣本”矩陣中的每一列是對(duì)應(yīng)于第i個(gè)樣本特征向量； （2）對(duì)該矩陣進(jìn)行奇異值分解(SVD)；（3）用最大的k個(gè)奇異值所對(duì)應(yīng)的“特征-語義”矩陣Uk和“樣本-語義”矩陣Vk以及最大的k個(gè)奇異值重構(gòu)“特征-樣本”矩陣。,下面兩式分別代表在語義空間特征與特征之間的距離和在語義空間樣本與樣本之間的距離,2.3-6 聚類分析聚類技術(shù)

19、將數(shù)據(jù)元組視為對(duì)象。它將對(duì)象劃分為聚類，使在一個(gè)聚類中的對(duì)象“類似”，但與其它聚類中的對(duì)象“不類似”。通常，類似性基于距離，用對(duì)象在空間中的“接近”程度定義。聚類的“質(zhì)量”可以用“直徑”表示；而直徑是一個(gè)聚類中兩個(gè)任意對(duì)象的最大距離。質(zhì)心距離是聚類質(zhì)量的另一種度量，它定義為由聚類質(zhì)心（表示“平均對(duì)象”，或聚類空間中的平均點(diǎn)）到每個(gè)聚類對(duì)象的平均距離。,2.3-6 聚類分析（續(xù)）,k-means算法,k-medoids算法,三、數(shù)據(jù)挖

20、掘算法,數(shù)據(jù)挖掘算法按挖掘目的可分為：（1）概念描述（總結(jié)，對(duì)比等）（2）關(guān)聯(lián)規(guī)則分析（3）分類與預(yù)測(cè) （信息自動(dòng)分類，信息過濾，圖像識(shí)別等）（4）聚類分析（5）異常分析（入侵檢測(cè)，金融安全等）（6）趨勢(shì)、演化分析（回歸，序列模式挖掘）,按訓(xùn)練方式，機(jī)器學(xué)習(xí)可分為： （1）有監(jiān)督的學(xué)習(xí)；有訓(xùn)練樣本，學(xué)習(xí)機(jī)通過學(xué)習(xí)獲得訓(xùn)練樣本包含的知識(shí)，并用其作為判斷測(cè)試樣本的類別的依據(jù)。（2）無監(jiān)督的學(xué)習(xí)：無訓(xùn)練樣本，僅根

21、據(jù)測(cè)試樣本的在特征空間分布情況判斷其類別。（3）半監(jiān)督的學(xué)習(xí)：有少量訓(xùn)練樣本，學(xué)習(xí)機(jī)以從訓(xùn)練樣本獲得的知識(shí)為基礎(chǔ)，結(jié)合測(cè)試樣本的分布情況逐步修正已有知識(shí)，并判斷測(cè)試樣本的類別。（4）強(qiáng)化學(xué)習(xí)：沒有訓(xùn)練樣本，但有對(duì)學(xué)習(xí)機(jī)每一步是否更接近目標(biāo)的獎(jiǎng)懲措施。,有監(jiān)督的學(xué)習(xí),半監(jiān)督的學(xué)習(xí),無監(jiān)督的學(xué)習(xí),3.1 關(guān)聯(lián)規(guī)則挖掘關(guān)聯(lián)規(guī)則挖掘發(fā)現(xiàn)大量數(shù)據(jù)中項(xiàng)集之間有趣的關(guān)聯(lián)或相關(guān)聯(lián)系。設(shè)I = { i1 , i2 ,..., im }是項(xiàng)的集合。設(shè)

22、任務(wù)相關(guān)的數(shù)據(jù)D是數(shù)據(jù)庫(kù)事務(wù)的集合，其中每個(gè)事務(wù)T是項(xiàng)的集合，使得T ? I。設(shè)A是一個(gè)項(xiàng)集，事務(wù)T包含A當(dāng)且僅當(dāng)A ? T。關(guān)聯(lián)規(guī)則是形如A ? B的蘊(yùn)涵式，其中A ? I，B ? I，并且A ? B = ?。規(guī)則A ? B在事務(wù)集D中成立，具有支持度s，其中s是D中事務(wù)包含A ? B的百分比。即，P(A ? B)。規(guī)則A ? B在事務(wù)集D中具有置信度c，如果D中包含A的事務(wù)同時(shí)也包含B的百分比是c。這是條件概率P(B|A)。即s

23、upport (A ? B ) = P(A ? B) confidence (A ? B ) = P(B|A),3.1 關(guān)聯(lián)規(guī)則挖掘（續(xù)）Apriori性質(zhì)：頻繁項(xiàng)集的所有非空子集都必須也是頻繁的。Apriori性質(zhì)基于如下觀察：根據(jù)定義，如果項(xiàng)集I不滿足最小支持度閾值s，則I不是頻繁的，即P(I) < s。如果項(xiàng)A添加到I，則結(jié)果項(xiàng)集（即I ? A）不可能比I更頻繁出現(xiàn)。因此，I ? A也不是頻繁的，即P(I ? A)

24、< s。該性質(zhì)表明如果一個(gè)集合不能通過測(cè)試，則它的所有超集也都不能通過相同的測(cè)試。將Apriori性質(zhì)應(yīng)用于算法：下面算法的兩個(gè)主要步過程由連接和剪枝組成。,3.1 關(guān)聯(lián)規(guī)則挖掘（續(xù)）連接步：為找Lk，通過Lk - 1與自己連接產(chǎn)生候選k-項(xiàng)集的集合。該候選項(xiàng)集的集合記作Ck。 Ck是Lk的超集。掃描數(shù)據(jù)庫(kù)，確定Ck中每個(gè)候選的計(jì)數(shù)，將令計(jì)數(shù)值不小于最小支持度計(jì)數(shù)的（頻繁的）所有候選加入Lk。剪枝步：但Ck可能很大，這樣所

25、涉及的計(jì)算量就很大。根據(jù)Apriori性質(zhì)如果一個(gè)候選k-項(xiàng)集的(k-1)-子集不在Lk-1中，則該候選也不可能是頻繁的，從而可以由Ck中刪除。Apriori性質(zhì)(逆反描述)：任何非頻繁的(k-1)-項(xiàng)集都不是可能是頻繁k-項(xiàng)集的子集。,3.2 決策樹決策樹學(xué)習(xí)是歸納推理算法。它是一種逼近離散函數(shù)的方法，且對(duì)噪聲數(shù)據(jù)有很好的健壯性。在這種方法中學(xué)習(xí)到的知識(shí)被表示為決策樹，決策樹也能再被表示為多個(gè)if-then的規(guī)則，以提高可讀性。

26、基本決策樹算法就是一個(gè)貪心算法。它采用自上而下、分而制之的遞歸方式來構(gòu)造一個(gè)決策樹通常，決策樹是一種自頂向下增長(zhǎng)樹的貪婪算法，在每個(gè)結(jié)點(diǎn)選取能最好地分類樣例的屬性。繼續(xù)這個(gè)過程直到這棵樹能完美分類訓(xùn)練樣例，或所有的屬性都使用過了?！靶畔⒃鲆妗?用于衡量屬性的價(jià)值。熵（entropy）是一種度量信息增益的指標(biāo)，它描述了樣本的純度（purity）。下面是熵的定義：Entropy = -∑Pilog2Pi,3.2 決策樹（續(xù)）注意點(diǎn)：

27、（1）避免過度擬合，應(yīng)該適度剪枝；（2）連續(xù)值的離散化；（3）處理缺失值的方法：最常見值、按概率分配；（4）處理權(quán)重不同的屬性常用實(shí)現(xiàn)算法：CART、ID3、ASSISTANT、C4.5,3.3 人工神經(jīng)網(wǎng)絡(luò)人工神經(jīng)網(wǎng)絡(luò)（Artificial Neural Networks）提供了一種普遍而且實(shí)用的方法，來從樣例中學(xué)習(xí)值為實(shí)數(shù)、離散或向量的函數(shù)。反向傳播（Back Propagation）這樣的算法使用梯度下降來調(diào)節(jié)網(wǎng)絡(luò)參數(shù)以最

28、佳擬合由輸入/輸出對(duì)組成的訓(xùn)練集合。BP網(wǎng)絡(luò)的學(xué)習(xí)方法和目標(biāo)：對(duì)網(wǎng)絡(luò)的連接權(quán)值進(jìn)行調(diào)整，使得對(duì)任一輸入都能得到所期望的輸出。,常用的非線性作用函數(shù)是Sigmoid函數(shù)，即f (x)=1/(1+ e-x)。在神經(jīng)網(wǎng)絡(luò)模型中，大量神經(jīng)元節(jié)點(diǎn)按一定體系結(jié)構(gòu)連接成網(wǎng)狀。神經(jīng)網(wǎng)絡(luò)一般都具有輸入層，隱層和輸出層。,每個(gè)神經(jīng)元都是一個(gè)結(jié)構(gòu)相似的獨(dú)立單元，它接受前一層傳來的數(shù)據(jù)，并將這些數(shù)據(jù)的加權(quán)和輸入非線性作用函數(shù)中，最后將非線性作用函數(shù)的輸出結(jié)果

29、傳遞給后一層。,誤差反向傳播的過程,3.3 人工神經(jīng)網(wǎng)絡(luò)（續(xù)）自適應(yīng)共振理論模型(ART) ——聚類連續(xù)/離散Hopfield神經(jīng)網(wǎng)絡(luò)——求近似最優(yōu)解，識(shí)別與分類雙向聯(lián)想記憶模型 (BAM) ——識(shí)別玻爾茲曼機(jī)(BM) ——求最優(yōu)解腦中盒模型(BSB) ——識(shí)別與分類自組織映射模型(SOM) ——識(shí)別與分類對(duì)向傳播網(wǎng)絡(luò)模型(CPN) ——識(shí)別與分類小腦模型(CMAC) ——快速識(shí)別,3.4 樸素貝葉斯（Naive Ba

30、yes）分類器樸素貝葉斯分類器是一種基于貝葉斯理論的分類器。它的特點(diǎn)是以概率形式表達(dá)所有形式的不確定，學(xué)習(xí)和推理都由概率規(guī)則實(shí)現(xiàn)，學(xué)習(xí)的結(jié)果可以解釋為對(duì)不同可能的信任程度。 P(H)是先驗(yàn)概率，或H的先驗(yàn)概率。P(H|X)是后驗(yàn)概率，或條件X下，H的后驗(yàn)概率。后驗(yàn)概率P(H|X)比先驗(yàn)概率P(H)基于更多的信息。P(H)是獨(dú)立于X的。假定數(shù)據(jù)樣本世界由水果組成，用它們的顏色和形狀描述。假定X表示紅色和圓的，H表示假定X是蘋果

31、，則P(H|X)反映當(dāng)我們看到X是紅色并是圓的時(shí)，我們對(duì)X是蘋果的確信程度。,,,,,,樸素貝葉斯分類能夠奏效的前提是，P(X|H) 相對(duì)比較容易計(jì)算。假定X表示紅色和圓的，H表示假定X是蘋果；則P(X|H)表示已知蘋果，它既紅又圓的概率。,3.5 期望最大化（EM）期望最大化（EM）方法和樸素貝葉斯方法有著共同的理論基礎(chǔ)。期望最大化是一種基于循環(huán)過程的最大似然參數(shù)估計(jì)方法，用于解決帶缺失數(shù)據(jù)的參數(shù)估計(jì)問題。樣本數(shù)據(jù)分為標(biāo)記樣本和未

32、標(biāo)記樣本，按照統(tǒng)計(jì)的觀點(diǎn)，對(duì)于每一個(gè)樣本的產(chǎn)生，其背后都有一個(gè)模型，即樣本生成模型。樣本生成模型的參數(shù)先由標(biāo)記樣本確定，再通過標(biāo)記樣本和利用當(dāng)前模型判斷標(biāo)記的未標(biāo)記樣本共同調(diào)整。,3.5 期望最大化（續(xù)）如果參數(shù)適當(dāng)，EM 算法能得到較好的分類結(jié)果，但計(jì)算速度相對(duì)較慢。其具體的步驟如下：一、初始參數(shù)估計(jì)，將未標(biāo)記的樣本按樸素貝葉斯分類方法進(jìn)行類標(biāo)注。二、反復(fù)迭代E步驟和M步驟，直到收斂。三、E步驟：對(duì)于每個(gè)未標(biāo)記的樣本，按下式計(jì)

33、算類標(biāo)記的期望值。四、M步驟：利用E步驟計(jì)算出的期望值，按下式用已標(biāo)記樣本和未標(biāo)記樣本重新估計(jì)新的分類器參數(shù)。,,3.6 K-最近鄰分類K-近鄰（K-NN）分類是基于范例的分類方法，它的基本思想是：給定待分類樣本后，考慮在訓(xùn)練樣本集中與該待分類樣本距離最近（最相似）的K 個(gè)樣本，根據(jù)這K 個(gè)樣本中大多數(shù)樣本所屬的類別判定待分類樣本的類別。它的特例是1- NN，即分類時(shí)選出待分類樣本的最近鄰，并以此最近鄰的類標(biāo)記來判斷樣本的類

34、。K-NN算法的優(yōu)點(diǎn)在于它有較高的精確程度，研究表明，K-NN的分類效果要明顯好于樸素貝葉斯分類、決策樹分類。,3.6 K-最近鄰分類（續(xù)）最近鄰分類的算法步驟如下：一、以向量空間模型的形式描述各訓(xùn)練樣本。二、在全部訓(xùn)練樣本集中選出與待分類樣本最相似的K個(gè)樣本。K值的確定目前沒有很好的方法，一般采用先定一個(gè)100左右的初始值，然后再調(diào)整。三、將待分類樣本標(biāo)記為其K個(gè)鄰居中所屬最多的那個(gè)類別中。,3.7 遺傳算法遺傳算法易于并

35、行處理，其依據(jù)是自然界進(jìn)化和適者生存的原則。遺傳學(xué)習(xí)開始如下：創(chuàng)建若干個(gè)由隨機(jī)產(chǎn)生的個(gè)體組成的初始群體。每個(gè)個(gè)體用一個(gè)二進(jìn)位串表示。形成由當(dāng)前群體中最適合的個(gè)體組成新的群體，以及這些規(guī)則的子女。個(gè)體的適合度用某一目標(biāo)函數(shù)來評(píng)估。子女通過使用諸如交叉和變異等遺傳操作來創(chuàng)建。在交叉操作中，來自個(gè)體對(duì)的子串交換，形成新的個(gè)體對(duì)。在變異操作中，個(gè)體中隨機(jī)選擇的位被反轉(zhuǎn)。,3.7 遺傳算法（續(xù)）Fitness：適應(yīng)度評(píng)分函數(shù)，為給定假設(shè)賦予

36、一個(gè)評(píng)估得分。Fitness_threshold：指定終止判據(jù)的閾值。p：群體中包含的假設(shè)數(shù)量。r：每一步中通過交叉取代群體成員的比例。m：變異率。初始化群體：P?隨機(jī)產(chǎn)生的p個(gè)假設(shè)評(píng)估：對(duì)于P中的每一個(gè)h，計(jì)算Fitness(h)當(dāng)[Fitness(h)]<Fitness_threshold，做：產(chǎn)生新的一代PS：,3.7 遺傳算法（續(xù)）選擇：用概率方法選擇P的(1-r)p個(gè)成員加入PS。從P中選擇假設(shè)hi的概率P

37、(hi)通過下面公式計(jì)算：交叉：根據(jù)上面給出的P(hi)，從P中按概率選擇r?p/2對(duì)假設(shè)。對(duì)于每一對(duì)假設(shè)應(yīng)用交叉算子產(chǎn)生兩個(gè)后代。把所有的后代加入PS。變異：使用均勻的概率從PS中選擇m百分比的成員。對(duì)于選出的每個(gè)成員，在它的表示中隨機(jī)選擇一個(gè)位取反。更新：P?PS。評(píng)估：對(duì)于P中的每一個(gè)h計(jì)算Fitness(h)從P中返回適應(yīng)度最高的假設(shè)。,3.8 聚類分析為達(dá)到全局最優(yōu)，基于劃分的聚類會(huì)要求窮舉所有可能的劃分。聚類技術(shù)

38、將數(shù)據(jù)元組視為對(duì)象。它將對(duì)象劃分為群或聚類，使得在一個(gè)聚類中的對(duì)象“類似”，但與其它聚類中的對(duì)象“不類似”。絕大多數(shù)應(yīng)用采用了以下兩個(gè)比較流行的基于劃分的方法，這些基于劃分的聚類方法對(duì)在中小規(guī)模的數(shù)據(jù)庫(kù)中發(fā)現(xiàn)球狀簇很適用。（1）k-means算法，在該算法中，每個(gè)簇用該簇中對(duì)象的平均值來表示。（2）k-medoids算法，在該算法中，每個(gè)簇用接近聚類中心的一個(gè)對(duì)象來表示。,3.8 聚類分析（續(xù)）常用的相似程度度量 余弦夾角：

39、 Dice系數(shù)：Jaccard系數(shù)：,3.8 聚類分析（續(xù)）基于層次的方法：層次的方法對(duì)給定數(shù)據(jù)集合進(jìn)行層次的分解。根據(jù)層次的分解如何形成，層次的方法可以被分為凝聚或分裂方法。 （Chameleon ，CURE，BIRCH） 基于密度的方法：只要臨近區(qū)域的密度超過某個(gè)閾值，就繼續(xù)聚類。避免僅生成球狀聚類。（DBSCAN，OPTICS，DENCLUE）基于網(wǎng)格的方法：基于網(wǎng)格的方法把對(duì)象空間量化為

40、有限數(shù)目的單元，所有的聚類操作都在這個(gè)量化的空間上進(jìn)行。這種方法的主要優(yōu)點(diǎn)是它的處理速度很快。（STING，CLIQUE，WaveCluster）基于模型的方法：為每個(gè)簇假設(shè)一個(gè)模型，發(fā)現(xiàn)數(shù)據(jù)對(duì)模型的最好匹配。（COBWEB，CLASSIT，AutoClass）,3.9 隱馬爾可夫模型對(duì)于一個(gè)隨機(jī)事件，有一個(gè)觀察值序列：O1, ..., OT。該事件隱含著一個(gè)狀態(tài)序列：X1, ..., XT假設(shè)1：馬爾可夫性，P(Xi| Xi-1

41、…X1) = P(Xi| Xi-1)假設(shè)2：不動(dòng)性，P(Xi+1| Xi) = P(Xj+1| Xj)，對(duì)任意i,j成立假設(shè)3：輸出獨(dú)立性，P(O1,..., OT | X1,..., XT) = ΠP(Ot | Xt) 一個(gè)隱馬爾可夫模型是一個(gè)五元組：(ΩX, ΩO, A, B, π)其中：ΩX = {Q1,..., QN}：狀態(tài)的有限集合；ΩO = {V1,..., VM}：觀察值的有限集合；A = {aij}，aij

42、= P(Xt+1 = Qj |Xt = Qi)：轉(zhuǎn)移概率；B = {bik}，bik = P(Ot = Vk | Xt = Qi)：輸出概率；π = {πi}，πi = P(X1 = Qi)：初始狀態(tài)分布。,3.9 隱馬爾可夫模型（續(xù)）令 λ = {A, B,π} 為給定HMM的參數(shù)，令 σ = O1,...,OT 為觀察值序列，隱馬爾可夫模型的三個(gè)基本問題： 評(píng)估問題：對(duì)于給定模型，求某個(gè)觀察值序列的概率P(σ|λ) 。向

43、前/向后算法：定義向前/向后變量。采用動(dòng)態(tài)規(guī)劃算法，復(fù)雜度O(N2T)解碼問題：對(duì)于給定模型和觀察值序列，求可能性最大的狀態(tài)序列。Viterbi算法：采用動(dòng)態(tài)規(guī)劃算法，復(fù)雜度O(N2T)學(xué)習(xí)問題：對(duì)于給定的一個(gè)觀察值序列，調(diào)整參數(shù)λ，使得觀察值出現(xiàn)的概率P(σ|λ)最大。向前EM算法的一個(gè)特例，帶隱變量的最大似然估計(jì)。Baum-Welch算法。,3.9 隱馬爾可夫模型（續(xù)）向前/向后算法：定義向前/向后變量：初始化：遞歸：

44、終結(jié)：,,3.9 隱馬爾可夫模型（續(xù)）Viterbi算法初始化：遞歸：終結(jié)：求S序列：,3.9 隱馬爾可夫模型（續(xù)）Baum-Welch算法主要步驟：1. 初始模型（待訓(xùn)練模型） l0,2. 基于l0 以及觀察值序列s，訓(xùn)練新模型 l；3. 如果 log P(X|l) - log(P(X|l0) < Delta，說明訓(xùn)練已經(jīng)達(dá)到預(yù)期效果， 算法結(jié)束。4. 否則，令l0 ＝ l

45、，繼續(xù)第2步工作,3.10 支持向量機(jī)支持向量機(jī)基本模型是針對(duì)線性可分情況下的最優(yōu)分界面提出的。在這一條件下，正類和反類訓(xùn)練樣本可用超平面完全正確地分開。設(shè)線性可分樣本集合為( xi , yi )，i = 1,…, n；x∈Rd，y∈{+1,-1}是類別標(biāo)記。支持向量機(jī)工作的機(jī)理可描述為：尋找一個(gè)超平面w·x + b = 0，該平面把兩類訓(xùn)練樣本點(diǎn)完全正確地分開，即滿足 且

46、；同時(shí)滿足兩類訓(xùn)練點(diǎn)到此超平面的最近距離之和，即“間隔” (Margin)，達(dá)到最大。滿足上述條件的分界面就是最優(yōu)分界面，經(jīng)過兩類樣本中距離最優(yōu)分類面最近的點(diǎn)，且平行于最優(yōu)分界面的超平面H1、H2（邊界超平面）上的訓(xùn)練樣本稱為支持向量，即圖中帶圈的點(diǎn)。,,,3.10 支持向量機(jī)（續(xù)）根據(jù)最近距離之和最大以及正確分離兩類樣本這兩個(gè)條件，可以構(gòu)造約束極值問題：見（1）式。通過拉格朗日乘數(shù)法并引入拉格朗日乘數(shù)，該約束極值

47、問題就可以轉(zhuǎn)化成一個(gè)求解較為簡(jiǎn)單的對(duì)偶問題，通過尋求該對(duì)偶問題的最優(yōu)解，就可以得到原問題的最優(yōu)解。構(gòu)造分類器判決函數(shù)：見（2）式。（2）式中，sgn(.)是取符號(hào)函數(shù)，產(chǎn)生+1或-1兩種結(jié)果。當(dāng)測(cè)試無標(biāo)記的測(cè)試數(shù)據(jù)時(shí)，根據(jù)上式的計(jì)算結(jié)果就可判斷無標(biāo)記測(cè)試數(shù)據(jù)屬于正類還是反類。,（1）,（2）,3.10 支持向量機(jī)（續(xù)）由于噪聲或其他因素的影響，兩類數(shù)據(jù)可能有少數(shù)的融合或交叉。引入松弛變量x使得分類器在訓(xùn)練后仍可以存在一些錯(cuò)分樣本，不

48、但要使兩類樣本之間的間隔盡量大，同時(shí)還要使錯(cuò)分的樣本的松弛變量之和盡可能的小，即,其中，x為松弛變量，滿足xi≥0；C為大于零的折衷因子，它調(diào)和了間隔距離和錯(cuò)分樣本數(shù)之間的關(guān)系，C趨近于無窮大時(shí)即為線性可分的形式。為了提高支持向量機(jī)的推廣能力，C通常取為較大的數(shù)。,3.10 支持向量機(jī)（續(xù)）解決線性不可分?jǐn)?shù)據(jù)問題的方法是將低維空間的線性不可分?jǐn)?shù)據(jù)映射到高維的線性可分空間中。支持向量機(jī)通過非線性映射f (x)把數(shù)據(jù)由低維空間向高維空間

49、映射，在高維空間為低維數(shù)據(jù)構(gòu)造線性分離超平面。該分離超平面對(duì)應(yīng)著原特征空間上的一個(gè)分割超曲面。在高維特征空間上所有涉及f (x)的計(jì)算及判決函數(shù)都以f (x)的內(nèi)積形式出現(xiàn)，因而可以引入一個(gè)核函數(shù)進(jìn)行整體處理從而避免了對(duì)f (x)的直接計(jì)算，使所有的計(jì)算仍在原空間進(jìn)行。,3.10 支持向量機(jī)（續(xù)）統(tǒng)計(jì)學(xué)習(xí)理論認(rèn)為：學(xué)習(xí)機(jī)誤判未知數(shù)據(jù)類別的實(shí)際風(fēng)險(xiǎn)與學(xué)習(xí)機(jī)的訓(xùn)練誤差并不完全一致，對(duì)于兩類分類問題，實(shí)際風(fēng)險(xiǎn)與學(xué)習(xí)機(jī)的訓(xùn)練誤差

50、之間至少以1-h 的概率（0< h <1）滿足下式： 根據(jù)統(tǒng)計(jì)學(xué)習(xí)的理論，對(duì)于兩類分類的支持向量機(jī)，在線性可分的情況下，它的推廣誤差的上界（以1-d 的概率（0< d <1）保證）為：其中，m是連續(xù)分類正確的樣本數(shù)；g =1/ ||w||，是間隔距離的一半；R是一個(gè)特征空間球的半徑，它將全部樣本包含在其中。,,3.11 關(guān)系學(xué)習(xí)關(guān)系學(xué)習(xí)所涉及的問題比傳統(tǒng)機(jī)器學(xué)習(xí)中涉及到的問題高一個(gè)層次。該類問題的假

51、設(shè)空間龐大，結(jié)構(gòu)復(fù)雜；需要加入領(lǐng)域知識(shí)反映問題的內(nèi)在結(jié)構(gòu)。關(guān)系學(xué)習(xí)中知識(shí)的表示：原子；析取、合取、蘊(yùn)含、非；驗(yàn)證、等價(jià)、涵蘊(yùn)等。句子由上述元素組成。一階Horn子句：僅包含一個(gè)肯定文字的子句。有三種類型的Horn子句：?jiǎn)我辉樱ㄊ聦?shí)）；一個(gè)蘊(yùn)涵（規(guī)則）；一個(gè)否定文字的集合（目標(biāo)）。,3.11 關(guān)系學(xué)習(xí)（續(xù)）歸納邏輯編程(Inductive Logic Programming, ILP)是處理關(guān)系學(xué)習(xí)領(lǐng)域問題的重要方法。它是歸納學(xué)

52、習(xí)和邏輯程序結(jié)合的產(chǎn)物。ILP用于一階邏輯的概念學(xué)習(xí)和邏輯程序的合成。ILP 系統(tǒng)處理分類任務(wù)時(shí)主要采用兩種方式：覆蓋方法和分治方法。子句空間由形如：H←L1,L2,…Lm 的一階子句構(gòu)成。θ-包容關(guān)系：假設(shè)c和c’是兩個(gè)程序子句，子句c θ-包容子句c’,如果存在一個(gè)替換θ使得cθ?c’基于ILP的常用方法有：Progol、FOIL、TLIDE、ICL,四、模型上的模型,4.1 裝袋 / 提升給定s個(gè)樣本的集合S。裝袋（Ba

53、gging）過程如下。對(duì)于迭代t ( t = 1, 2,..., T )，訓(xùn)練集St采用放回選樣，由原始樣本集S選取。由于使用放回選樣，S的某些樣本可能不在St中，而其它的可能出現(xiàn)多次。由每個(gè)訓(xùn)練集St學(xué)習(xí)，得到一個(gè)分類法Ct。為對(duì)一個(gè)未知的樣本X分類，每個(gè)分類法Ct返回它的類預(yù)測(cè)，算作一票。裝袋的分類法C*統(tǒng)計(jì)得票，并將得票最高的類賦予X。通過取得票的平均值，裝袋也可以用于連續(xù)值的預(yù)測(cè)。,4.1 裝袋 / 提升（續(xù)）提升（Bo

54、osting）過程如下：每個(gè)訓(xùn)練樣本賦予一個(gè)權(quán)，并學(xué)習(xí)得到一系列分類法。對(duì)于迭代t ( t = 1, 2,..., T )，學(xué)習(xí)得到分類法Ct后，更新權(quán)，使得隨后的分類法Ct+1“更關(guān)注”Ct的分類錯(cuò)誤。最終的提升分類法C*組合每個(gè)分類法的表決，這里每個(gè)分類法的表決是其準(zhǔn)確率的函數(shù)。通過取得票的平均值，提升算法也可以擴(kuò)充到連續(xù)值預(yù)測(cè)。,4.2 共同訓(xùn)練（Co-Training）共同訓(xùn)練算法用兩個(gè)不同的“視圖”（即特征集合）來描述

55、文本的特征?；舅悸罚好總€(gè)視圖對(duì)應(yīng)一個(gè)學(xué)習(xí)機(jī)，而每個(gè)學(xué)習(xí)機(jī)都根據(jù)自身已學(xué)到的規(guī)律來標(biāo)記“最有把握”的無標(biāo)記樣本，然后將這個(gè)（或這幾個(gè)）新標(biāo)記的樣本加入訓(xùn)練樣本，并擴(kuò)展后的訓(xùn)練樣本提供給另一個(gè)學(xué)習(xí)機(jī)進(jìn)行學(xué)習(xí)。如此反復(fù)，直到滿足一定的條件為止。該算法中所用到的兩個(gè)視圖需要滿足以下兩個(gè)條件：首先，每個(gè)特征集合對(duì)文本分類學(xué)習(xí)來說都是充分的；其次，在給定類別標(biāo)記的條件下，兩個(gè)特征集合相互獨(dú)立。,4.3 主動(dòng)學(xué)習(xí) / 被動(dòng)學(xué)習(xí)主動(dòng)學(xué)習(xí)在學(xué)習(xí)過

56、程中可以根據(jù)學(xué)習(xí)進(jìn)程，選擇最有利于分類器性能的樣本來進(jìn)一步訓(xùn)練分類器，它能有效地減少評(píng)價(jià)樣本的數(shù)量；被動(dòng)學(xué)習(xí)只是隨機(jī)地選擇訓(xùn)練樣本，被動(dòng)地接受這些樣本的信息進(jìn)行學(xué)習(xí)。主動(dòng)學(xué)習(xí)是實(shí)現(xiàn)監(jiān)督學(xué)習(xí)過程的一個(gè)有效的方法。在主動(dòng)學(xué)習(xí)過程中，分類器主動(dòng)地選擇對(duì)其“最有幫助”的一組子樣本進(jìn)行學(xué)習(xí)，而不是被動(dòng)地接受訓(xùn)練集?！白钣袔椭钡臉颖局傅氖菍?duì)當(dāng)前分類器來說，歸屬最不確定的樣本。即當(dāng)前分類器最難以區(qū)分的樣本。通常情況下，主動(dòng)學(xué)習(xí)的計(jì)算復(fù)雜度比一

57、般的監(jiān)督學(xué)習(xí)過程要顯著得低。,4.3 主動(dòng)學(xué)習(xí) / 被動(dòng)學(xué)習(xí)（續(xù)）初始狀態(tài)下，候選樣本集中所有的樣本都未帶類別標(biāo)注，根據(jù)先驗(yàn)知識(shí)或者隨機(jī)地從候選樣本集中選擇少量樣本并標(biāo)注它們的類別，構(gòu)造初始訓(xùn)練樣本集，確保初始訓(xùn)練樣本集中至少包含有一個(gè)正例樣本和一個(gè)負(fù)例樣本。在上述初始訓(xùn)練樣本集上訓(xùn)練一個(gè)分類器，并采用某種針對(duì)該分類器采樣算法，從候選樣本集中選擇最有利于提高分類器性能的樣本，手工標(biāo)注其類別并加入訓(xùn)練樣本集，再重新訓(xùn)練分類器。重復(fù)以

58、上過程，直到候選樣本集為空或達(dá)到某種要求。主動(dòng)學(xué)習(xí)是一個(gè)循環(huán)反復(fù)的過程。,在主動(dòng)學(xué)習(xí)的模型中，全部數(shù)據(jù)被分為兩部分，一部分是帶標(biāo)簽的樣本集X，另一部分是無標(biāo)簽的樣本集U。主動(dòng)學(xué)習(xí)的模型還包括了一個(gè)在帶標(biāo)簽的樣本集X上訓(xùn)練的學(xué)習(xí)機(jī)L和一個(gè)決策模塊q。決策模塊q用來決定U中的哪一些樣本應(yīng)該被選出標(biāo)記標(biāo)簽，并加入帶標(biāo)簽的樣本集X。更新后的X將在下一個(gè)輪次被用于訓(xùn)練學(xué)習(xí)機(jī)L。主動(dòng)學(xué)習(xí)的框架模型如圖。,根據(jù)決策模塊q的不同工作機(jī)理，主動(dòng)學(xué)習(xí)方法又

59、可以被分為兩大類：其一是不確定取樣方法；另一是委員會(huì)咨詢方法。,4.4 直推式學(xué)習(xí)直推式學(xué)習(xí)的思想來源于前面提到的機(jī)器學(xué)習(xí)的困境：一方面獲取已知標(biāo)簽的樣本代價(jià)高昂；另一方面獲取無標(biāo)簽的樣本要相對(duì)容易得多。直推式學(xué)習(xí)的學(xué)習(xí)過程恰恰可以將大量無標(biāo)簽的測(cè)試集樣本所攜帶的分類信息，通過迭代逐步轉(zhuǎn)移到了最終的分類器中去。由于測(cè)試樣本易于獲得、數(shù)量較多，直推式學(xué)習(xí)機(jī)能夠更好地描述整體樣本空間上的數(shù)據(jù)分布特性，使測(cè)試樣本的分類結(jié)果更為準(zhǔn)確。,4

60、.4 直推式學(xué)習(xí)（續(xù)）在多數(shù)情況下，人們只對(duì)測(cè)試文本的分類結(jié)果感興趣，這時(shí)就沒有必要非得尋求具有良好泛化能力的規(guī)則，而只要求分類器能對(duì)這些特定的文本做出正確分類即可。它在目前已知標(biāo)簽樣本十分緊缺，而未知標(biāo)簽樣本易于獲得的條件下，有著非常重要的現(xiàn)實(shí)意義。,4.5 廣義EM算法EM算法可用于許多問題框架，其中需要估計(jì)一組描述基準(zhǔn)概率分布的參數(shù)θ，只給定了由此分布產(chǎn)生的全部數(shù)據(jù)中能觀察到的一部分。一般地，令X=代表在同樣的實(shí)例中未觀察

61、到的數(shù)據(jù)，并令Y=X∪Z代表全體數(shù)據(jù)。注意到未觀察到的Z可被看作隨機(jī)變量，它的概率分布依賴于未知參數(shù)θ和已知數(shù)據(jù)X。類似地，Y是一隨機(jī)變量，因?yàn)樗怯呻S機(jī)變量Z來定義的。在EM算法的一般形式中，用h來代表參數(shù)θ的假設(shè)值，而h´代表在EM的每次迭代中修改的假設(shè)。,4.5 廣義EM算法（續(xù)）EM算法通過搜尋使E[lnP(Y|h´)]最大的h´來尋找極大似然假設(shè)h´。此期望值是在Y所遵循的概率分布

62、上計(jì)算，此分布由未知參數(shù)θ確定。首先，P(Y|h´)是給定假設(shè)h´下全部數(shù)據(jù)Y的似然性。其合理性在于我們要尋找一個(gè)h´使該量的某函數(shù)值最大化。其次，使該量的對(duì)數(shù)lnP(Y|h´)最大化也使P(Y|h´)最大化。第三，引入期望值E[lnP(Y|h´)]是因?yàn)槿繑?shù)據(jù)Y本身也是一隨機(jī)變量。已知全部數(shù)據(jù)Y是觀察到的X和未觀察到的Z的合并，我們必須在未觀察到的Z的可能值上取平均，

63、并以相應(yīng)的概率為權(quán)值。,4.5 廣義EM算法（續(xù)）在EM算法的一般形式里，重復(fù)以下兩個(gè)步驟直至收斂。步驟1：估計(jì)（E）步驟：使用當(dāng)前假設(shè)h和觀察到的數(shù)據(jù)X來估計(jì)Y上的概率分布以計(jì)算Q(h´|h)。步驟2：最大化（M）步驟：將假設(shè)h替換為使Q函數(shù)最大化的假設(shè)h´：,,,4.6 強(qiáng)化學(xué)習(xí)強(qiáng)化學(xué)習(xí)的模型如圖所示通過Agent與環(huán)境的交互進(jìn)行學(xué)習(xí)。 Agent與環(huán)境的交互接口包括行動(dòng)（Action）、回報(bào)（Re

64、ward）和狀態(tài)（State）。交互過程可以表述為如下形式： 每一步，Agent根據(jù)策略選擇一個(gè)行動(dòng)執(zhí)行，然后感知下一步狀態(tài)和即時(shí)回報(bào)，通過經(jīng)驗(yàn)再修改自己的策略。Agent的目標(biāo)就是最大化長(zhǎng)期回報(bào)。,4.6 強(qiáng)化學(xué)習(xí)（續(xù)）馬爾可夫過程是四元組 M = 。其中S是狀態(tài)集。A是行動(dòng)集， A(s) 表示狀態(tài)s下可執(zhí)行的行動(dòng)。T = S×A×S? [0，1]是狀態(tài)轉(zhuǎn)換模型， T(s,a,s’)

65、表示狀態(tài)s下執(zhí)行行動(dòng)a到達(dá)狀態(tài)s’ 的概率，且滿足∑s’ T(s,a,s’) = 1 。R = S×A×S? R是即時(shí)回報(bào)函數(shù)， R(s,a,s’)表示狀態(tài)s下執(zhí)行行動(dòng)a到達(dá)狀態(tài)s’ 后可以得到的即時(shí)回報(bào)。,4.6 強(qiáng)化學(xué)習(xí)（續(xù)）轉(zhuǎn)換模型和回報(bào)函數(shù)是環(huán)境的一部分，描述了環(huán)境模型，且只與當(dāng)前狀態(tài)和行動(dòng)有關(guān)，與以前的狀態(tài)和行動(dòng)都沒有關(guān)系，體現(xiàn)了馬爾可夫特性。Agent為了完成任務(wù)，必須知道每個(gè)行動(dòng)的長(zhǎng)遠(yuǎn)回報(bào)，而不僅

66、僅是即時(shí)回報(bào)。而長(zhǎng)遠(yuǎn)回報(bào)必須經(jīng)過一定時(shí)間的延遲之后才可以獲得。 有終任務(wù)和持續(xù)任務(wù)可以統(tǒng)一起來，他們的長(zhǎng)期回報(bào)是 或,,,4.6 強(qiáng)化學(xué)習(xí)（續(xù)）Agent與環(huán)境交互的學(xué)習(xí)中選擇行動(dòng)的方法稱為策略π:S×A? [0, 1]，π(s, a)表示在狀態(tài)s下選擇行動(dòng)a的概率。策略的一個(gè)退化形式為π:S?A，稱為確定性策略，表示在狀態(tài)s下行動(dòng)a的執(zhí)行概率為1，其它行動(dòng)均為0。Q學(xué)習(xí)

67、是最常用的強(qiáng)化學(xué)習(xí)技術(shù)。,,,值函數(shù),Q函數(shù),4.6 強(qiáng)化學(xué)習(xí)（續(xù)）學(xué)習(xí)的目的是找到一個(gè)最優(yōu)策略。設(shè)有策略π和π’，若對(duì)所有狀態(tài)s∈S都有 Vπ(s) ≥ Vπ’(s)  ，則稱策略π比策略π’好。這樣就總存在一個(gè)策略，它比其它所有策略都好，稱為最優(yōu)策略π*。若最優(yōu)策略對(duì)應(yīng)的狀態(tài)評(píng)價(jià)函數(shù)記為V *，則對(duì)所有狀態(tài)s∈S，有V * (s) = max Vπ(s) 。對(duì)所有狀態(tài)s∈S，所有行動(dòng)a∈A(s)，有Q * (s)

68、= max Qπ(s)。,4.6 強(qiáng)化學(xué)習(xí)（續(xù)）三種計(jì)算“值函數(shù)” Vπ(s)方法 ：動(dòng)態(tài)規(guī)劃法：已知環(huán)境模型T和R，每步進(jìn)行迭代 。Monte Carlo法：沒有環(huán)境模型，根據(jù)經(jīng)驗(yàn)學(xué)習(xí)。只考慮有終任務(wù)，任務(wù)結(jié)束后對(duì)所有的回報(bào)進(jìn)行平均。時(shí)序差分法：沒有環(huán)境模型，根據(jù)經(jīng)驗(yàn)學(xué)習(xí)。每步進(jìn)行迭代，不需要等任務(wù)完成。,4.6 強(qiáng)化學(xué)習(xí)（續(xù)）在多Agent系統(tǒng)中，環(huán)境在多個(gè)Agent的聯(lián)合動(dòng)作下進(jìn)行狀態(tài)的遷移。對(duì)于單個(gè)Agent來講，由于