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

1、數(shù)據(jù)挖掘算法,Wang Ye 2006.8,一、概念和術(shù)語(yǔ),1.1 數(shù)據(jù)挖掘 / 知識(shí)發(fā)現(xiàn)（1）數(shù)據(jù)挖掘是從存放在數(shù)據(jù)集中的大量數(shù)據(jù)挖掘出有趣知識(shí)的過(guò)程。（2）數(shù)據(jù)挖掘，又稱為數(shù)據(jù)庫(kù)中知識(shí)發(fā)現(xiàn)（Knowledge Discovery in Databases）或知識(shí)發(fā)現(xiàn)，它是一個(gè)從大量數(shù)據(jù)中抽取挖掘出未知的、有價(jià)值的模式或規(guī)律等知識(shí)的非平凡過(guò)程，它與數(shù)據(jù)倉(cāng)庫(kù)有著密切的聯(lián)系。（3）廣義的數(shù)據(jù)挖掘是指知識(shí)發(fā)現(xiàn)的全過(guò)程；狹義的數(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í)過(guò)程也不應(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)通過(guò)執(zhí)行某種過(guò)程而改進(jìn)它處理某一問(wè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àn)維網(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ī)則；決策樹(shù)；范例推理；貝葉斯網(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）星形模式：最常見(jiàn)模型；其中數(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ù)。它通過(guò)沿維的概念分層向上或維歸約來(lái)實(shí)現(xiàn)。（3）下鉆：下鉆是上卷的逆操作。它從某一維度的更低概念層次觀察數(shù)據(jù)方，獲得更詳細(xì)的數(shù)據(jù)。下鉆可以通過(guò)沿維的概念分層向下或引入新的維來(lái)實(shí)現(xiàn)。（4）切片和切塊：切片操作在給定的數(shù)據(jù)方的選擇一個(gè)維的部分屬性，獲得一個(gè)較小的子數(shù)據(jù)方。切塊操作通過(guò)對(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 決策樹(shù)歸約（1）決策樹(shù)歸約構(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)在樹(shù)中的屬性形成歸約后的屬性子集。,2.1-2 粗糙集歸約（1）粗糙集理論在數(shù)學(xué)意義上描述了知識(shí)的不確定性，它的特點(diǎn)是把用于分類的知識(shí)嵌入集合內(nèi)，使分類與知識(shí)聯(lián)系在一起。（2）知識(shí)的粒度、不可分辨關(guān)系、上近似、下近似、邊界等概念見(jià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)可以通過(guò)刪除冗余的（不獨(dú)立的）屬性而獲得，約簡(jiǎn)包含的屬性即為“對(duì)分類有幫助”的屬性。,2.2 數(shù)據(jù)變換2.2-1 歸一化與模糊化有限區(qū)間的歸一化：無(wú)限區(qū)間的歸一化：模糊隸屬度：,2.2-2 核函數(shù)（1）核函數(shù)的基本思想是將在低維

12、特征向量線性不可分的數(shù)據(jù)映射到線性可分的高維特征空間中去。（2）映射可以是顯式的，也可以是隱式的。顯式映射即找到一個(gè)映射關(guān)系f，使高維空間的特征向量f (x)可以被直接計(jì)算出來(lái)。（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ù)線性模型可以用來(lái)近似給定的數(shù)據(jù)。在線性回歸中，用一條直線來(lái)模擬數(shù)據(jù)的生成規(guī)則。多元回歸是線性回歸的擴(kuò)展，涉及多個(gè)預(yù)測(cè)變量。在多項(xiàng)式回歸中，通過(guò)對(duì)變量進(jìn)行變換，可以將非線性模型轉(zhuǎn)換成線性的，然后用最小平方和法求解。,,,,2.3-2 回歸（續(xù)）利用線性回歸可以為連續(xù)取值的函數(shù)建模。廣義線性模型則可以用于對(duì)離散取值變量進(jìn)行回歸建模。在廣義線性模型中，因變量Y 的變化速率是Y

15、 均值的一個(gè)函數(shù)；這一點(diǎn)與線性回歸不同。常見(jià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。這樣，原來(lái)的數(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)度。可以舍棄轉(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ù)原來(lái)的數(shù)據(jù)。,2.3-4 離散小波變換（續(xù)）常用的小波函數(shù)包括Haar系列, Daubechies系列，Moret系列，Sym系列，Meyer系列，Coif系列。,2.3-5 潛在語(yǔ)義分析潛

18、在語(yǔ)義分析將樣本映射到語(yǔ)義概念空間以發(fā)現(xiàn)樣本數(shù)據(jù)之間的潛在語(yǔ)義聯(lián)系。 （1）構(gòu)造“特征-樣本”矩陣，“特征-樣本”矩陣中的每一列是對(duì)應(yīng)于第i個(gè)樣本特征向量； （2）對(duì)該矩陣進(jìn)行奇異值分解(SVD)；（3）用最大的k個(gè)奇異值所對(duì)應(yīng)的“特征-語(yǔ)義”矩陣Uk和“樣本-語(yǔ)義”矩陣Vk以及最大的k個(gè)奇異值重構(gòu)“特征-樣本”矩陣。,下面兩式分別代表在語(yǔ)義空間特征與特征之間的距離和在語(yǔ)義空間樣本與樣本之間的距離,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)分類，信息過(guò)濾，圖像識(shí)別等）（4）聚類分析（5）異常分析（入侵檢測(cè)，金融安全等）（6）趨勢(shì)、演化分析（回歸，序列模式挖掘）,按訓(xùn)練方式，機(jī)器學(xué)習(xí)可分為： （1）有監(jiān)督的學(xué)習(xí)；有訓(xùn)練樣本，學(xué)習(xí)機(jī)通過(guò)學(xué)習(xí)獲得訓(xùn)練樣本包含的知識(shí)，并用其作為判斷測(cè)試樣本的類別的依據(jù)。（2）無(wú)監(jiān)督的學(xué)習(xí)：無(wú)訓(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í)：沒(méi)有訓(xùn)練樣本，但有對(duì)學(xué)習(xí)機(jī)每一步是否更接近目標(biāo)的獎(jiǎng)懲措施。,有監(jiān)督的學(xué)習(xí),半監(jiān)督的學(xué)習(xí),無(wú)監(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è)集合不能通過(guò)測(cè)試，則它的所有超集也都不能通過(guò)相同的測(cè)試。將Apriori性質(zhì)應(yīng)用于算法：下面算法的兩個(gè)主要步過(guò)程由連接和剪枝組成。,3.1 關(guān)聯(lián)規(guī)則挖掘（續(xù)）連接步：為找Lk，通過(guò)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 決策樹(shù)決策樹(shù)學(xué)習(xí)是歸納推理算法。它是一種逼近離散函數(shù)的方法，且對(duì)噪聲數(shù)據(jù)有很好的健壯性。在這種方法中學(xué)習(xí)到的知識(shí)被表示為決策樹(shù)，決策樹(shù)也能再被表示為多個(gè)if-then的規(guī)則，以提高可讀性。

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

27、（1）避免過(guò)度擬合，應(yīng)該適度剪枝；（2）連續(xù)值的離散化；（3）處理缺失值的方法：最常見(jiàn)值、按概率分配；（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í)用的方法，來(lái)從樣例中學(xué)習(xí)值為實(shí)數(shù)、離散或向量的函數(shù)。反向傳播（Back Propagation）這樣的算法使用梯度下降來(lái)調(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ú)立單元，它接受前一層傳來(lái)的數(shù)據(jù)，并將這些數(shù)據(jù)的加權(quán)和輸入非線性作用函數(shù)中，最后將非線性作用函數(shù)的輸出結(jié)果

29、傳遞給后一層。,誤差反向傳播的過(guò)程,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)過(guò)程的最大似然參數(shù)估計(jì)方法，用于解決帶缺失數(shù)據(jù)的參數(shù)估計(jì)問(wèn)題。樣本數(shù)據(jù)分為標(biāo)記樣本和未

32、標(biāo)記樣本，按照統(tǒng)計(jì)的觀點(diǎn)，對(duì)于每一個(gè)樣本的產(chǎn)生，其背后都有一個(gè)模型，即樣本生成模型。樣本生成模型的參數(shù)先由標(biāo)記樣本確定，再通過(guò)標(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)記來(lái)判斷樣本的類

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

35、行處理，其依據(jù)是自然界進(jìn)化和適者生存的原則。遺傳學(xué)習(xí)開(kāi)始如下：創(chuàng)建若干個(gè)由隨機(jī)產(chǎn)生的個(gè)體組成的初始群體。每個(gè)個(gè)體用一個(gè)二進(jìn)位串表示。形成由當(dāng)前群體中最適合的個(gè)體組成新的群體，以及這些規(guī)則的子女。個(gè)體的適合度用某一目標(biāo)函數(shù)來(lái)評(píng)估。子女通過(guò)使用諸如交叉和變異等遺傳操作來(lái)創(chuàng)建。在交叉操作中，來(lái)自個(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：每一步中通過(guò)交叉取代群體成員的比例。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)通過(guò)下面公式計(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ì)象的平均值來(lái)表示。（2）k-medoids算法，在該算法中，每個(gè)簇用接近聚類中心的一個(gè)對(duì)象來(lái)表示。,3.8 聚類分析（續(xù)）常用的相似程度度量 余弦?jiàn)A角：

39、 Dice系數(shù)：Jaccard系數(shù)：,3.8 聚類分析（續(xù)）基于層次的方法：層次的方法對(duì)給定數(shù)據(jù)集合進(jìn)行層次的分解。根據(jù)層次的分解如何形成，層次的方法可以被分為凝聚或分裂方法。 （Chameleon ，CURE，BIRCH） 基于密度的方法：只要臨近區(qū)域的密度超過(guò)某個(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è)基本問(wèn)題： 評(píng)估問(wèn)題：對(duì)于給定模型，求某個(gè)觀察值序列的概率P(σ|λ) 。向

43、前/向后算法：定義向前/向后變量。采用動(dòng)態(tài)規(guī)劃算法，復(fù)雜度O(N2T)解碼問(wèn)題：對(duì)于給定模型和觀察值序列，求可能性最大的狀態(tài)序列。Viterbi算法：采用動(dòng)態(tài)規(guī)劃算法，復(fù)雜度O(N2T)學(xué)習(xí)問(wèn)題：對(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，說(shuō)明訓(xùn)練已經(jīng)達(dá)到預(yù)期效果， 算法結(jié)束。4. 否則，令l0 ＝ l

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

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

47、問(wèn)題就可以轉(zhuǎn)化成一個(gè)求解較為簡(jiǎn)單的對(duì)偶問(wèn)題，通過(guò)尋求該對(duì)偶問(wèn)題的最優(yōu)解，就可以得到原問(wèn)題的最優(yōu)解。構(gòu)造分類器判決函數(shù)：見(jiàn)（2）式。（2）式中，sgn(.)是取符號(hào)函數(shù)，產(chǎn)生+1或-1兩種結(jié)果。當(dāng)測(cè)試無(wú)標(biāo)記的測(cè)試數(shù)據(jù)時(shí)，根據(jù)上式的計(jì)算結(jié)果就可判斷無(wú)標(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趨近于無(wú)窮大時(shí)即為線性可分的形式。為了提高支持向量機(jī)的推廣能力，C通常取為較大的數(shù)。,3.10 支持向量機(jī)（續(xù)）解決線性不可分?jǐn)?shù)據(jù)問(wèn)題的方法是將低維空間的線性不可分?jǐn)?shù)據(jù)映射到高維的線性可分空間中。支持向量機(jī)通過(guò)非線性映射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ì)于兩類分類問(wèn)題，實(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í)所涉及的問(wèn)題比傳統(tǒng)機(jī)器學(xué)習(xí)中涉及到的問(wèn)題高一個(gè)層次。該類問(wèn)題的假

51、設(shè)空間龐大，結(jié)構(gòu)復(fù)雜；需要加入領(lǐng)域知識(shí)反映問(wèn)題的內(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)域問(wèn)題的重要方法。它是歸納學(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）過(guò)程如下。對(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。通過(guò)取得票的平均值，裝袋也可以用于連續(xù)值的預(yù)測(cè)。,4.1 裝袋 / 提升（續(xù)）提升（Bo

54、osting）過(guò)程如下：每個(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ù)。通過(guò)取得票的平均值，提升算法也可以擴(kuò)充到連續(xù)值預(yù)測(cè)。,4.2 共同訓(xùn)練（Co-Training）共同訓(xùn)練算法用兩個(gè)不同的“視圖”（即特征集合）來(lái)描述

55、文本的特征?；舅悸罚好總€(gè)視圖對(duì)應(yīng)一個(gè)學(xué)習(xí)機(jī)，而每個(gè)學(xué)習(xí)機(jī)都根據(jù)自身已學(xué)到的規(guī)律來(lái)標(biāo)記“最有把握”的無(wú)標(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í)來(lái)說(shuō)都是充分的；其次，在給定類別標(biāo)記的條件下，兩個(gè)特征集合相互獨(dú)立。,4.3 主動(dòng)學(xué)習(xí) / 被動(dòng)學(xué)習(xí)主動(dòng)學(xué)習(xí)在學(xué)習(xí)過(guò)

56、程中可以根據(jù)學(xué)習(xí)進(jìn)程，選擇最有利于分類器性能的樣本來(lái)進(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í)過(guò)程的一個(gè)有效的方法。在主動(dòng)學(xué)習(xí)過(guò)程中，分類器主動(dòng)地選擇對(duì)其“最有幫助”的一組子樣本進(jìn)行學(xué)習(xí)，而不是被動(dòng)地接受訓(xùn)練集?！白钣袔椭钡臉颖局傅氖菍?duì)當(dāng)前分類器來(lái)說(shuō)，歸屬最不確定的樣本。即當(dāng)前分類器最難以區(qū)分的樣本。通常情況下，主動(dòng)學(xué)習(xí)的計(jì)算復(fù)雜度比一

57、般的監(jiān)督學(xué)習(xí)過(guò)程要顯著得低。,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、上過(guò)程，直到候選樣本集為空或達(dá)到某種要求。主動(dòng)學(xué)習(xí)是一個(gè)循環(huán)反復(fù)的過(guò)程。,在主動(dòng)學(xué)習(xí)的模型中，全部數(shù)據(jù)被分為兩部分，一部分是帶標(biāo)簽的樣本集X，另一部分是無(wú)標(biāo)簽的樣本集U。主動(dòng)學(xué)習(xí)的模型還包括了一個(gè)在帶標(biāo)簽的樣本集X上訓(xùn)練的學(xué)習(xí)機(jī)L和一個(gè)決策模塊q。決策模塊q用來(lái)決定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í)的思想來(lái)源于前面提到的機(jī)器學(xué)習(xí)的困境：一方面獲取已知標(biāo)簽的樣本代價(jià)高昂；另一方面獲取無(wú)標(biāo)簽的樣本要相對(duì)容易得多。直推式學(xué)習(xí)的學(xué)習(xí)過(guò)程恰恰可以將大量無(wú)標(biāo)簽的測(cè)試集樣本所攜帶的分類信息，通過(guò)迭代逐步轉(zhuǎn)移到了最終的分類器中去。由于測(cè)試樣本易于獲得、數(shù)量較多，直推式學(xué)習(xí)機(jī)能夠更好地描述整體樣本空間上的數(shù)據(jù)分布特性，使測(cè)試樣本的分類結(jié)果更為準(zhǔn)確。,4

60、.4 直推式學(xué)習(xí)（續(xù)）在多數(shù)情況下，人們只對(duì)測(cè)試文本的分類結(jié)果感興趣，這時(shí)就沒(méi)有必要非得尋求具有良好泛化能力的規(guī)則，而只要求分類器能對(duì)這些特定的文本做出正確分類即可。它在目前已知標(biāo)簽樣本十分緊缺，而未知標(biāo)簽樣本易于獲得的條件下，有著非常重要的現(xiàn)實(shí)意義。,4.5 廣義EM算法EM算法可用于許多問(wèn)題框架，其中需要估計(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來(lái)定義的。在EM算法的一般形式中，用h來(lái)代表參數(shù)θ的假設(shè)值，而h´代表在EM的每次迭代中修改的假設(shè)。,4.5 廣義EM算法（續(xù)）EM算法通過(guò)搜尋使E[lnP(Y|h´)]最大的h´來(lái)尋找極大似然假設(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來(lái)估計(jì)Y上的概率分布以計(jì)算Q(h´|h)。步驟2：最大化（M）步驟：將假設(shè)h替換為使Q函數(shù)最大化的假設(shè)h´：,,,4.6 強(qiáng)化學(xué)習(xí)強(qiáng)化學(xué)習(xí)的模型如圖所示通過(guò)Agent與環(huán)境的交互進(jìn)行學(xué)習(xí)。 Agent與環(huán)境的交互接口包括行動(dòng)（Action）、回報(bào)（Re

64、ward）和狀態(tài)（State）。交互過(guò)程可以表述為如下形式： 每一步，Agent根據(jù)策略選擇一個(gè)行動(dòng)執(zhí)行，然后感知下一步狀態(tài)和即時(shí)回報(bào)，通過(guò)經(jīng)驗(yàn)再修改自己的策略。Agent的目標(biāo)就是最大化長(zhǎng)期回報(bào)。,4.6 強(qiáng)化學(xué)習(xí)（續(xù)）馬爾可夫過(guò)程是四元組 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)都沒(méi)有關(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)過(guò)一定時(shí)間的延遲之后才可以獲得。 有終任務(wù)和持續(xù)任務(wù)可以統(tǒng)一起來(lái)，他們的長(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法：沒(méi)有環(huán)境模型，根據(jù)經(jīng)驗(yàn)學(xué)習(xí)。只考慮有終任務(wù)，任務(wù)結(jié)束后對(duì)所有的回報(bào)進(jìn)行平均。時(shí)序差分法：沒(méi)有環(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來(lái)講，由于