版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
數(shù)據(jù)挖掘基礎(chǔ)第一頁(yè),共八十七頁(yè),2022年,8月28日一、概念和術(shù)語(yǔ)1.1數(shù)據(jù)挖掘/知識(shí)發(fā)現(xiàn)(1)數(shù)據(jù)挖掘是從存放在數(shù)據(jù)集中的大量數(shù)據(jù)挖掘出有趣知識(shí)的過(guò)程。(2)數(shù)據(jù)挖掘,又稱(chēng)為數(shù)據(jù)庫(kù)中知識(shí)發(fā)現(xiàn)(KnowledgeDiscoveryinDatabases)或知識(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ù)挖掘是指統(tǒng)計(jì)分析、機(jī)器學(xué)習(xí)等發(fā)現(xiàn)數(shù)據(jù)模式的智能方法,即偏重于模型和算法。(4)數(shù)據(jù)庫(kù)查詢(xún)系統(tǒng)和專(zhuān)家系統(tǒng)不是數(shù)據(jù)挖掘!在小規(guī)模數(shù)據(jù)上的統(tǒng)計(jì)分析和機(jī)器學(xué)習(xí)過(guò)程也不應(yīng)算作數(shù)據(jù)挖掘。第二頁(yè),共八十七頁(yè),2022年,8月28日1.2機(jī)器學(xué)習(xí)(1)對(duì)于某類(lèi)任務(wù)T和性能度量P,如果一個(gè)計(jì)算機(jī)程序在T上以P衡量的性能隨著經(jīng)驗(yàn)E而自我完善,那么這個(gè)計(jì)算機(jī)程序被稱(chēng)為在從經(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)題的能力。第三頁(yè),共八十七頁(yè),2022年,8月28日1.3數(shù)據(jù)挖掘的對(duì)象(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ò)信息)第四頁(yè),共八十七頁(yè),2022年,8月28日1.4數(shù)據(jù)挖掘的步驟(1)數(shù)據(jù)清理(消除噪音或不一致數(shù)據(jù),補(bǔ)缺);(2)數(shù)據(jù)集成(多種數(shù)據(jù)源可以組合在一起);(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ù))。第五頁(yè),共八十七頁(yè),2022年,8月28日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)性分析;模糊集;粗糙集)(3)機(jī)器學(xué)習(xí)(聚類(lèi)分析;關(guān)聯(lián)規(guī)則;決策樹(shù);范例推理;貝葉斯網(wǎng)絡(luò);神經(jīng)網(wǎng)絡(luò);支持向量機(jī);遺傳算法)(4)可視化:將數(shù)據(jù)、知識(shí)和規(guī)則轉(zhuǎn)化為圖形表現(xiàn)的形式。第六頁(yè),共八十七頁(yè),2022年,8月28日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)。(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ǔ)全部或部分單元中的度量。第七頁(yè),共八十七頁(yè),2022年,8月28日1.7數(shù)據(jù)倉(cāng)庫(kù)的模型(1)星形模式:最常見(jiàn)模型;其中數(shù)據(jù)倉(cāng)庫(kù)包括一個(gè)大的、包含大批數(shù)據(jù)、不含冗余的中心表(事實(shí)表);一組小的附屬表(維表),每維一個(gè)。(2)雪花模式:雪花模式是星型模式的變種,其中某些維表是規(guī)范化的,因而把數(shù)據(jù)進(jìn)一步分解到附加的表中。(3)星系模式:多個(gè)事實(shí)表共享維表。這種模式可以看作星形模式集,因此稱(chēng)為星系模式,或事實(shí)星座。第八頁(yè),共八十七頁(yè),2022年,8月28日1.8典型的OLAP操作(1)OLAP是一種多維數(shù)據(jù)分析技術(shù)。包括匯總、合并和聚集等功能,以及從不同的角度觀察信息的能力。(2)上卷:從某一維度的更高概念層次觀察數(shù)據(jù)方,獲得更概要的數(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)中的某些維度由行改為列,或由列改為行。第九頁(yè),共八十七頁(yè),2022年,8月28日二、數(shù)據(jù)準(zhǔn)備現(xiàn)實(shí)世界的數(shù)據(jù)是不完整的(有些感興趣的屬性缺少屬性值,或僅包含聚集數(shù)據(jù)),含噪音的(包含錯(cuò)誤,或存在偏離期望的異常值),不一致的(例如,用于商品分類(lèi)的部門(mén)編碼存在差異)。需要數(shù)據(jù)清理、數(shù)據(jù)集成、數(shù)據(jù)選擇、數(shù)據(jù)變換等技術(shù)對(duì)數(shù)據(jù)進(jìn)行處理。第十頁(yè),共八十七頁(yè),2022年,8月28日2.1維歸約/特征提取2.1-1決策樹(shù)歸約(1)決策樹(shù)歸約構(gòu)造一個(gè)類(lèi)似于流程圖的結(jié)構(gòu):其每個(gè)非葉子結(jié)點(diǎn)表示一個(gè)屬性上的測(cè)試,每個(gè)分枝對(duì)應(yīng)于測(cè)試的一個(gè)輸出;每個(gè)葉子結(jié)點(diǎn)表示一個(gè)決策類(lèi)。(2)在每個(gè)結(jié)點(diǎn),算法選擇“當(dāng)前對(duì)分類(lèi)最有幫助”的屬性,出現(xiàn)在樹(shù)中的屬性形成歸約后的屬性子集。第十一頁(yè),共八十七頁(yè),2022年,8月28日2.1-2粗糙集歸約(1)粗糙集理論在數(shù)學(xué)意義上描述了知識(shí)的不確定性,它的特點(diǎn)是把用于分類(lèi)的知識(shí)嵌入集合內(nèi),使分類(lèi)與知識(shí)聯(lián)系在一起。(2)知識(shí)的粒度、不可分辨關(guān)系、上近似、下近似、邊界等概念見(jiàn)下圖。第十二頁(yè),共八十七頁(yè),2022年,8月28日2.1-2粗糙集歸約(續(xù))(3)令Q代表屬性的集合。q∈Q是一個(gè)屬性,如果IND(Q?q)=IND(Q),則q在S中不是獨(dú)立的;否則稱(chēng)q在S中是獨(dú)立的。(4)若集合滿(mǎn)足IND(R)=IND(Q)且R中的每一個(gè)屬性都是獨(dú)立的,則R被稱(chēng)為Q的一個(gè)“約簡(jiǎn)”,記作R=RED(Q)。(5)約簡(jiǎn)可以通過(guò)刪除冗余的(不獨(dú)立的)屬性而獲得,約簡(jiǎn)包含的屬性即為“對(duì)分類(lèi)有幫助”的屬性。第十三頁(yè),共八十七頁(yè),2022年,8月28日2.2數(shù)據(jù)變換2.2-1歸一化與模糊化有限區(qū)間的歸一化:無(wú)限區(qū)間的歸一化:模糊隸屬度:第十四頁(yè),共八十七頁(yè),2022年,8月28日2.2-2核函數(shù)(1)核函數(shù)的基本思想是將在低維特征向量線(xiàn)性不可分的數(shù)據(jù)映射到線(xiàn)性可分的高維特征空間中去。(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í),即符合Mercer條件,它才能成為核函數(shù)。第十五頁(yè),共八十七頁(yè),2022年,8月28日2.2-2核函數(shù)(續(xù))多項(xiàng)式函數(shù):
高斯(RBF)函數(shù):
多層感知機(jī)函數(shù):低維空間向量映射到高維空間向量舉例:
第十六頁(yè),共八十七頁(yè),2022年,8月28日2.3數(shù)據(jù)壓縮2.3-1離散化離散化的用途:(1)適應(yīng)某些僅接受離散值的算法;(2)減小數(shù)據(jù)的尺度。離散化的方法包括幾下幾種。(1)等距分割;(2)聚類(lèi)分割;(3)直方圖分割;(4)基于熵的分割;(5)基于自然屬性的分割。第十七頁(yè),共八十七頁(yè),2022年,8月28日2.3-2回歸回歸和對(duì)數(shù)線(xiàn)性模型可以用來(lái)近似給定的數(shù)據(jù)。在線(xiàn)性回歸中,用一條直線(xiàn)來(lái)模擬數(shù)據(jù)的生成規(guī)則。多元回歸是線(xiàn)性回歸的擴(kuò)展,涉及多個(gè)預(yù)測(cè)變量。在多項(xiàng)式回歸中,通過(guò)對(duì)變量進(jìn)行變換,可以將非線(xiàn)性模型轉(zhuǎn)換成線(xiàn)性的,然后用最小平方和法求解。第十八頁(yè),共八十七頁(yè),2022年,8月28日2.3-2回歸(續(xù))利用線(xiàn)性回歸可以為連續(xù)取值的函數(shù)建模。廣義線(xiàn)性模型則可以用于對(duì)離散取值變量進(jìn)行回歸建模。在廣義線(xiàn)性模型中,因變量Y的變化速率是Y均值的一個(gè)函數(shù);這一點(diǎn)與線(xiàn)性回歸不同。常見(jiàn)的廣義線(xiàn)性模型有:對(duì)數(shù)回歸和泊松回歸。對(duì)數(shù)回歸模型是利用一些事件發(fā)生的概率作為自變量所建立的線(xiàn)性回歸模型。泊松回歸模型主要是描述數(shù)據(jù)出現(xiàn)次數(shù)的模型,因?yàn)樗鼈兂31憩F(xiàn)為泊松分布。第十九頁(yè),共八十七頁(yè),2022年,8月28日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ū)間。(2)PCA計(jì)算c個(gè)規(guī)范正交向量,作為歸一化輸入數(shù)據(jù)的基。這些是單位向量,每一個(gè)都垂直于另一個(gè):稱(chēng)為主成分。輸入數(shù)據(jù)是主要成分的線(xiàn)性組合。(3)對(duì)主成分按“意義”或強(qiáng)度降序排列,選擇部分主成分充當(dāng)數(shù)據(jù)的一組新坐標(biāo)軸。第二十頁(yè),共八十七頁(yè),2022年,8月28日2.3-4離散小波變換(DWT)離散小波變換是一種線(xiàn)性信號(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ù)。保留所有大于用戶(hù)指定閾值的小波系數(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ù)。第二十一頁(yè),共八十七頁(yè),2022年,8月28日2.3-4離散小波變換(續(xù))常用的小波函數(shù)包括Haar系列,Daubechies系列,Moret系列,Sym系列,Meyer系列,Coif系列。第二十二頁(yè),共八十七頁(yè),2022年,8月28日2.3-5潛在語(yǔ)義分析潛在語(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ǔ)義空間樣本與樣本之間的距離第二十三頁(yè),共八十七頁(yè),2022年,8月28日2.3-6聚類(lèi)分析聚類(lèi)技術(shù)將數(shù)據(jù)元組視為對(duì)象。它將對(duì)象劃分為聚類(lèi),使在一個(gè)聚類(lèi)中的對(duì)象“類(lèi)似”,但與其它聚類(lèi)中的對(duì)象“不類(lèi)似”。通常,類(lèi)似性基于距離,用對(duì)象在空間中的“接近”程度定義。聚類(lèi)的“質(zhì)量”可以用“直徑”表示;而直徑是一個(gè)聚類(lèi)中兩個(gè)任意對(duì)象的最大距離。質(zhì)心距離是聚類(lèi)質(zhì)量的另一種度量,它定義為由聚類(lèi)質(zhì)心(表示“平均對(duì)象”,或聚類(lèi)空間中的平均點(diǎn))到每個(gè)聚類(lèi)對(duì)象的平均距離。第二十四頁(yè),共八十七頁(yè),2022年,8月28日2.3-6聚類(lèi)分析(續(xù))k-means算法k-medoids算法第二十五頁(yè),共八十七頁(yè),2022年,8月28日三、數(shù)據(jù)挖掘算法數(shù)據(jù)挖掘算法按挖掘目的可分為:(1)概念描述(總結(jié),對(duì)比等)(2)關(guān)聯(lián)規(guī)則分析(3)分類(lèi)與預(yù)測(cè)(信息自動(dòng)分類(lèi),信息過(guò)濾,圖像識(shí)別等)(4)聚類(lèi)分析(5)異常分析(入侵檢測(cè),金融安全等)(6)趨勢(shì)、演化分析(回歸,序列模式挖掘)第二十六頁(yè),共八十七頁(yè),2022年,8月28日按訓(xùn)練方式,機(jī)器學(xué)習(xí)可分為:
(1)有監(jiān)督的學(xué)習(xí);有訓(xùn)練樣本,學(xué)習(xí)機(jī)通過(guò)學(xué)習(xí)獲得訓(xùn)練樣本包含的知識(shí),并用其作為判斷測(cè)試樣本的類(lèi)別的依據(jù)。(2)無(wú)監(jiān)督的學(xué)習(xí):無(wú)訓(xùn)練樣本,僅根據(jù)測(cè)試樣本的在特征空間分布情況判斷其類(lèi)別。(3)半監(jiān)督的學(xué)習(xí):有少量訓(xùn)練樣本,學(xué)習(xí)機(jī)以從訓(xùn)練樣本獲得的知識(shí)為基礎(chǔ),結(jié)合測(cè)試樣本的分布情況逐步修正已有知識(shí),并判斷測(cè)試樣本的類(lèi)別。(4)強(qiáng)化學(xué)習(xí):沒(méi)有訓(xùn)練樣本,但有對(duì)學(xué)習(xí)機(jī)每一步是否更接近目標(biāo)的獎(jiǎng)懲措施。第二十七頁(yè),共八十七頁(yè),2022年,8月28日有監(jiān)督的學(xué)習(xí)半監(jiān)督的學(xué)習(xí)無(wú)監(jiān)督的學(xué)習(xí)第二十八頁(yè),共八十七頁(yè),2022年,8月28日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è)任務(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)。即support(A
B)=P(A
B)
confidence(A
B)=P(B|A)第二十九頁(yè),共八十七頁(yè),2022年,8月28日3.1關(guān)聯(lián)規(guī)則挖掘(續(xù))Apriori性質(zhì):頻繁項(xiàng)集的所有非空子集都必須也是頻繁的。Apriori性質(zhì)基于如下觀察:根據(jù)定義,如果項(xiàng)集I不滿(mǎn)足最小支持度閾值s,則I不是頻繁的,即P(I)<s。如果項(xiàng)A添加到I,則結(jié)果項(xiàng)集(即I
A)不可能比I更頻繁出現(xiàn)。因此,I
A也不是頻繁的,即P(I
A)<s。該性質(zhì)表明如果一個(gè)集合不能通過(guò)測(cè)試,則它的所有超集也都不能通過(guò)相同的測(cè)試。將Apriori性質(zhì)應(yīng)用于算法:下面算法的兩個(gè)主要步過(guò)程由連接和剪枝組成。第三十頁(yè),共八十七頁(yè),2022年,8月28日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可能很大,這樣所涉及的計(jì)算量就很大。根據(jù)Apriori性質(zhì)如果一個(gè)候選k-項(xiàng)集的(k-1)-子集不在Lk-1中,則該候選也不可能是頻繁的,從而可以由Ck中刪除。Apriori性質(zhì)(逆反描述):任何非頻繁的(k-1)-項(xiàng)集都不是可能是頻繁k-項(xiàng)集的子集。第三十一頁(yè),共八十七頁(yè),2022年,8月28日3.2決策樹(shù)決策樹(shù)學(xué)習(xí)是歸納推理算法。它是一種逼近離散函數(shù)的方法,且對(duì)噪聲數(shù)據(jù)有很好的健壯性。在這種方法中學(xué)習(xí)到的知識(shí)被表示為決策樹(shù),決策樹(shù)也能再被表示為多個(gè)if-then的規(guī)則,以提高可讀性。基本決策樹(shù)算法就是一個(gè)貪心算法。它采用自上而下、分而制之的遞歸方式來(lái)構(gòu)造一個(gè)決策樹(shù)通常,決策樹(shù)是一種自頂向下增長(zhǎng)樹(shù)的貪婪算法,在每個(gè)結(jié)點(diǎn)選取能最好地分類(lèi)樣例的屬性。繼續(xù)這個(gè)過(guò)程直到這棵樹(shù)能完美分類(lèi)訓(xùn)練樣例,或所有的屬性都使用過(guò)了。“信息增益”用于衡量屬性的價(jià)值。熵(entropy)是一種度量信息增益的指標(biāo),它描述了樣本的純度(purity)。下面是熵的定義:Entropy=-∑Pilog2Pi第三十二頁(yè),共八十七頁(yè),2022年,8月28日3.2決策樹(shù)(續(xù))注意點(diǎn):(1)避免過(guò)度擬合,應(yīng)該適度剪枝;(2)連續(xù)值的離散化;(3)處理缺失值的方法:最常見(jiàn)值、按概率分配;(4)處理權(quán)重不同的屬性常用實(shí)現(xiàn)算法:CART、ID3、ASSISTANT、C4.5第三十三頁(yè),共八十七頁(yè),2022年,8月28日3.3人工神經(jīng)網(wǎng)絡(luò)人工神經(jīng)網(wǎng)絡(luò)(ArtificialNeuralNetworks)提供了一種普遍而且實(shí)用的方法,來(lái)從樣例中學(xué)習(xí)值為實(shí)數(shù)、離散或向量的函數(shù)。反向傳播(BackPropagation)這樣的算法使用梯度下降來(lái)調(diào)節(jié)網(wǎng)絡(luò)參數(shù)以最佳擬合由輸入/輸出對(duì)組成的訓(xùn)練集合。BP網(wǎng)絡(luò)的學(xué)習(xí)方法和目標(biāo):對(duì)網(wǎng)絡(luò)的連接權(quán)值進(jìn)行調(diào)整,使得對(duì)任一輸入都能得到所期望的輸出。第三十四頁(yè),共八十七頁(yè),2022年,8月28日常用的非線(xiàn)性作用函數(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)和輸入非線(xiàn)性作用函數(shù)中,最后將非線(xiàn)性作用函數(shù)的輸出結(jié)果傳遞給后一層。第三十五頁(yè),共八十七頁(yè),2022年,8月28日誤差反向傳播的過(guò)程第三十六頁(yè),共八十七頁(yè),2022年,8月28日3.3人工神經(jīng)網(wǎng)絡(luò)(續(xù))自適應(yīng)共振理論模型(ART)——聚類(lèi)連續(xù)/離散Hopfield神經(jīng)網(wǎng)絡(luò)——求近似最優(yōu)解,識(shí)別與分類(lèi)雙向聯(lián)想記憶模型(BAM)——識(shí)別玻爾茲曼機(jī)(BM)——求最優(yōu)解腦中盒模型(BSB)——識(shí)別與分類(lèi)自組織映射模型(SOM)——識(shí)別與分類(lèi)對(duì)向傳播網(wǎng)絡(luò)模型(CPN)——識(shí)別與分類(lèi)小腦模型(CMAC)——快速識(shí)別第三十七頁(yè),共八十七頁(yè),2022年,8月28日3.4樸素貝葉斯(NaiveBayes)分類(lèi)器樸素貝葉斯分類(lèi)器是一種基于貝葉斯理論的分類(lèi)器。它的特點(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是蘋(píng)果,則P(H|X)反映當(dāng)我們看到X是紅色并是圓的時(shí),我們對(duì)X是蘋(píng)果的確信程度。第三十八頁(yè),共八十七頁(yè),2022年,8月28日樸素貝葉斯分類(lèi)能夠奏效的前提是,P(X|H)相對(duì)比較容易計(jì)算。假定X表示紅色和圓的,H表示假定X是蘋(píng)果;則P(X|H)表示已知蘋(píng)果,它既紅又圓的概率。第三十九頁(yè),共八十七頁(yè),2022年,8月28日3.5期望最大化(EM)期望最大化(EM)方法和樸素貝葉斯方法有著共同的理論基礎(chǔ)。期望最大化是一種基于循環(huán)過(guò)程的最大似然參數(shù)估計(jì)方法,用于解決帶缺失數(shù)據(jù)的參數(shù)估計(jì)問(wèn)題。樣本數(shù)據(jù)分為標(biāo)記樣本和未標(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)整。第四十頁(yè),共八十七頁(yè),2022年,8月28日3.5期望最大化(續(xù))如果參數(shù)適當(dāng),EM算法能得到較好的分類(lèi)結(jié)果,但計(jì)算速度相對(duì)較慢。其具體的步驟如下:一、初始參數(shù)估計(jì),將未標(biāo)記的樣本按樸素貝葉斯分類(lèi)方法進(jìn)行類(lèi)標(biāo)注。二、反復(fù)迭代E步驟和M步驟,直到收斂。三、E步驟:對(duì)于每個(gè)未標(biāo)記的樣本,按下式計(jì)算類(lèi)標(biāo)記的期望值。四、M步驟:利用E步驟計(jì)算出的期望值,按下式用已標(biāo)記樣本和未標(biāo)記樣本重新估計(jì)新的分類(lèi)器參數(shù)。第四十一頁(yè),共八十七頁(yè),2022年,8月28日3.6K-最近鄰分類(lèi)K-近鄰(K-NN)分類(lèi)是基于范例的分類(lèi)方法,它的基本思想是:給定待分類(lèi)樣本后,考慮在訓(xùn)練樣本集中與該待分類(lèi)樣本距離最近(最相似)的K個(gè)樣本,根據(jù)這K個(gè)樣本中大多數(shù)樣本所屬的類(lèi)別判定待分類(lèi)樣本的類(lèi)別。它的特例是1-NN,即分類(lèi)時(shí)選出待分類(lèi)樣本的最近鄰,并以此最近鄰的類(lèi)標(biāo)記來(lái)判斷樣本的類(lèi)。K-NN算法的優(yōu)點(diǎn)在于它有較高的精確程度,研究表明,K-NN的分類(lèi)效果要明顯好于樸素貝葉斯分類(lèi)、決策樹(shù)分類(lèi)。第四十二頁(yè),共八十七頁(yè),2022年,8月28日3.6K-最近鄰分類(lèi)(續(xù))最近鄰分類(lèi)的算法步驟如下:一、以向量空間模型的形式描述各訓(xùn)練樣本。二、在全部訓(xùn)練樣本集中選出與待分類(lèi)樣本最相似的K個(gè)樣本。K值的確定目前沒(méi)有很好的方法,一般采用先定一個(gè)100左右的初始值,然后再調(diào)整。三、將待分類(lèi)樣本標(biāo)記為其K個(gè)鄰居中所屬最多的那個(gè)類(lèi)別中。第四十三頁(yè),共八十七頁(yè),2022年,8月28日3.7遺傳算法遺傳算法易于并行處理,其依據(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)。第四十四頁(yè),共八十七頁(yè),2022年,8月28日3.7遺傳算法(續(xù))Fitness:適應(yīng)度評(píng)分函數(shù),為給定假設(shè)賦予一個(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:第四十五頁(yè),共八十七頁(yè),2022年,8月28日3.7遺傳算法(續(xù))選擇:用概率方法選擇P的(1-r)p個(gè)成員加入PS。從P中選擇假設(shè)hi的概率P(hi)通過(guò)下面公式計(jì)算:交叉:根據(jù)上面給出的P(hi),從P中按概率選擇rp/2對(duì)假設(shè)。對(duì)于每一對(duì)假設(shè)<h1,h2>應(yīng)用交叉算子產(chǎn)生兩個(gè)后代。把所有的后代加入PS。變異:使用均勻的概率從PS中選擇m百分比的成員。對(duì)于選出的每個(gè)成員,在它的表示中隨機(jī)選擇一個(gè)位取反。更新:PPS。評(píng)估:對(duì)于P中的每一個(gè)h計(jì)算Fitness(h)從P中返回適應(yīng)度最高的假設(shè)。第四十六頁(yè),共八十七頁(yè),2022年,8月28日3.8聚類(lèi)分析為達(dá)到全局最優(yōu),基于劃分的聚類(lèi)會(huì)要求窮舉所有可能的劃分。聚類(lèi)技術(shù)將數(shù)據(jù)元組視為對(duì)象。它將對(duì)象劃分為群或聚類(lèi),使得在一個(gè)聚類(lèi)中的對(duì)象“類(lèi)似”,但與其它聚類(lèi)中的對(duì)象“不類(lèi)似”。絕大多數(shù)應(yīng)用采用了以下兩個(gè)比較流行的基于劃分的方法,這些基于劃分的聚類(lèi)方法對(duì)在中小規(guī)模的數(shù)據(jù)庫(kù)中發(fā)現(xiàn)球狀簇很適用。(1)k-means算法,在該算法中,每個(gè)簇用該簇中對(duì)象的平均值來(lái)表示。(2)k-medoids算法,在該算法中,每個(gè)簇用接近聚類(lèi)中心的一個(gè)對(duì)象來(lái)表示。第四十七頁(yè),共八十七頁(yè),2022年,8月28日3.8聚類(lèi)分析(續(xù))常用的相似程度度量余弦?jiàn)A角:Dice系數(shù):Jaccard系數(shù):第四十八頁(yè),共八十七頁(yè),2022年,8月28日3.8聚類(lèi)分析(續(xù))基于層次的方法:層次的方法對(duì)給定數(shù)據(jù)集合進(jìn)行層次的分解。根據(jù)層次的分解如何形成,層次的方法可以被分為凝聚或分裂方法。(Chameleon,CURE,BIRCH)基于密度的方法:只要臨近區(qū)域的密度超過(guò)某個(gè)閾值,就繼續(xù)聚類(lèi)。避免僅生成球狀聚類(lèi)。(DBSCAN,OPTICS,DENCLUE)基于網(wǎng)格的方法:基于網(wǎng)格的方法把對(duì)象空間量化為有限數(shù)目的單元,所有的聚類(lèi)操作都在這個(gè)量化的空間上進(jìn)行。這種方法的主要優(yōu)點(diǎn)是它的處理速度很快。(STING,CLIQUE,WaveCluster)基于模型的方法:為每個(gè)簇假設(shè)一個(gè)模型,發(fā)現(xiàn)數(shù)據(jù)對(duì)模型的最好匹配。(COBWEB,CLASSIT,AutoClass)第四十九頁(yè),共八十七頁(yè),2022年,8月28日3.9隱馬爾可夫模型對(duì)于一個(gè)隨機(jī)事件,有一個(gè)觀察值序列:O1,...,OT。該事件隱含著一個(gè)狀態(tài)序列:X1,...,XT假設(shè)1:馬爾可夫性,P(Xi|Xi-1…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=P(Xt+1=Qj|Xt=Qi):轉(zhuǎn)移概率;B={bik},bik=P(Ot=Vk|Xt=Qi):輸出概率;π={πi},πi=P(X1=Qi):初始狀態(tài)分布。第五十頁(yè),共八十七頁(yè),2022年,8月28日3.9隱馬爾可夫模型(續(xù))令λ={A,B,π}為給定HMM的參數(shù),令σ=O1,...,OT
為觀察值序列,隱馬爾可夫模型的三個(gè)基本問(wèn)題:評(píng)估問(wèn)題:對(duì)于給定模型,求某個(gè)觀察值序列的概率P(σ|λ)。向前/向后算法:定義向前/向后變量。采用動(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算法。第五十一頁(yè),共八十七頁(yè),2022年,8月28日3.9隱馬爾可夫模型(續(xù))向前/向后算法:定義向前/向后變量:初始化:遞歸:終結(jié):第五十二頁(yè),共八十七頁(yè),2022年,8月28日3.9隱馬爾可夫模型(續(xù))Viterbi算法初始化:遞歸:終結(jié):求S序列:第五十三頁(yè),共八十七頁(yè),2022年,8月28日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,繼續(xù)第2步工作
第五十四頁(yè),共八十七頁(yè),2022年,8月28日3.10支持向量機(jī)支持向量機(jī)基本模型是針對(duì)線(xiàn)性可分情況下的最優(yōu)分界面提出的。在這一條件下,正類(lèi)和反類(lèi)訓(xùn)練樣本可用超平面完全正確地分開(kāi)。設(shè)線(xiàn)性可分樣本集合為(xi,yi),i=1,…,n;x∈Rd,y∈{+1,-1}是類(lèi)別標(biāo)記。支持向量機(jī)工作的機(jī)理可描述為:尋找一個(gè)超平面w·x+b=0,該平面把兩類(lèi)訓(xùn)練樣本點(diǎn)完全正確地分開(kāi),即滿(mǎn)足 且 ;同時(shí)滿(mǎn)足兩類(lèi)訓(xùn)練點(diǎn)到此超平面的最近距離之和,即“間隔”
(Margin),達(dá)到最大。滿(mǎn)足上述條件的分界面就是最優(yōu)分界面,經(jīng)過(guò)兩類(lèi)樣本中距離最優(yōu)分類(lèi)面最近的點(diǎn),且平行于最優(yōu)分界面的超平面H1、H2(邊界超平面)上的訓(xùn)練樣本稱(chēng)為支持向量,即圖中帶圈的點(diǎn)。第五十五頁(yè),共八十七頁(yè),2022年,8月28日3.10支持向量機(jī)(續(xù))根據(jù)最近距離之和最大以及正確分離兩類(lèi)樣本這兩個(gè)條件,可以構(gòu)造約束極值問(wèn)題:見(jiàn)(1)式。通過(guò)拉格朗日乘數(shù)法并引入拉格朗日乘數(shù),該約束極值問(wèn)題就可以轉(zhuǎn)化成一個(gè)求解較為簡(jiǎn)單的對(duì)偶問(wèn)題,通過(guò)尋求該對(duì)偶問(wèn)題的最優(yōu)解,就可以得到原問(wèn)題的最優(yōu)解。構(gòu)造分類(lèi)器判決函數(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ù)屬于正類(lèi)還是反類(lèi)。(1)(2)第五十六頁(yè),共八十七頁(yè),2022年,8月28日3.10支持向量機(jī)(續(xù))由于噪聲或其他因素的影響,兩類(lèi)數(shù)據(jù)可能有少數(shù)的融合或交叉。引入松弛變量x使得分類(lèi)器在訓(xùn)練后仍可以存在一些錯(cuò)分樣本,不但要使兩類(lèi)樣本之間的間隔盡量大,同時(shí)還要使錯(cuò)分的樣本的松弛變量之和盡可能的小,即其中,x為松弛變量,滿(mǎn)足xi≥0;C為大于零的折衷因子,它調(diào)和了間隔距離和錯(cuò)分樣本數(shù)之間的關(guān)系,C趨近于無(wú)窮大時(shí)即為線(xiàn)性可分的形式。為了提高支持向量機(jī)的推廣能力,C通常取為較大的數(shù)。
第五十七頁(yè),共八十七頁(yè),2022年,8月28日3.10支持向量機(jī)(續(xù))解決線(xiàn)性不可分?jǐn)?shù)據(jù)問(wèn)題的方法是將低維空間的線(xiàn)性不可分?jǐn)?shù)據(jù)映射到高維的線(xiàn)性可分空間中。支持向量機(jī)通過(guò)非線(xiàn)性映射f
(x)把數(shù)據(jù)由低維空間向高維空間映射,在高維空間為低維數(shù)據(jù)構(gòu)造線(xiàn)性分離超平面。該分離超平面對(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)行。第五十八頁(yè),共八十七頁(yè),2022年,8月28日3.10支持向量機(jī)(續(xù))統(tǒng)計(jì)學(xué)習(xí)理論認(rèn)為:學(xué)習(xí)機(jī)誤判未知數(shù)據(jù)類(lèi)別的實(shí)際風(fēng)險(xiǎn)與學(xué)習(xí)機(jī)的訓(xùn)練誤差并不完全一致,對(duì)于兩類(lèi)分類(lèi)問(wèn)題,實(shí)際風(fēng)險(xiǎn)與學(xué)習(xí)機(jī)的訓(xùn)練誤差之間至少以1-h
的概率(0<h
<1)滿(mǎn)足下式:
根據(jù)統(tǒng)計(jì)學(xué)習(xí)的理論,對(duì)于兩類(lèi)分類(lèi)的支持向量機(jī),在線(xiàn)性可分的情況下,它的推廣誤差的上界(以1-d
的概率(0<d
<1)保證)為:其中,m是連續(xù)分類(lèi)正確的樣本數(shù);g=1/||w||,是間隔距離的一半;R是一個(gè)特征空間球的半徑,它將全部樣本包含在其中。第五十九頁(yè),共八十七頁(yè),2022年,8月28日3.11關(guān)系學(xué)習(xí)關(guān)系學(xué)習(xí)所涉及的問(wèn)題比傳統(tǒng)機(jī)器學(xué)習(xí)中涉及到的問(wèn)題高一個(gè)層次。該類(lèi)問(wèn)題的假設(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è)肯定文字的子句。有三種類(lèi)型的Horn子句:?jiǎn)我辉樱ㄊ聦?shí));一個(gè)蘊(yùn)涵(規(guī)則);一個(gè)否定文字的集合(目標(biāo))。第六十頁(yè),共八十七頁(yè),2022年,8月28日3.11關(guān)系學(xué)習(xí)(續(xù))歸納邏輯編程(InductiveLogicProgramming,ILP)是處理關(guān)系學(xué)習(xí)領(lǐng)域問(wèn)題的重要方法。它是歸納學(xué)習(xí)和邏輯程序結(jié)合的產(chǎn)物。ILP用于一階邏輯的概念學(xué)習(xí)和邏輯程序的合成。ILP系統(tǒng)處理分類(lèi)任務(wù)時(shí)主要采用兩種方式:覆蓋方法和分治方法。子句空間由形如:H←L1,L2,…Lm
的一階子句構(gòu)成。θ-包容關(guān)系:假設(shè)c和c’是兩個(gè)程序子句,子句cθ-包容子句c’,如果存在一個(gè)替換θ使得cθ?c’基于ILP的常用方法有:Progol、FOIL、TLIDE、ICL第六十一頁(yè),共八十七頁(yè),2022年,8月28日四、模型上的模型4.1裝袋/提升給定s個(gè)樣本的集合S。裝袋(Bagging)過(guò)程如下。對(duì)于迭代t(t=1,2,...,T),訓(xùn)練集St采用放回選樣,由原始樣本集S選取。由于使用放回選樣,S的某些樣本可能不在St中,而其它的可能出現(xiàn)多次。由每個(gè)訓(xùn)練集St學(xué)習(xí),得到一個(gè)分類(lèi)法Ct。為對(duì)一個(gè)未知的樣本X分類(lèi),每個(gè)分類(lèi)法Ct返回它的類(lèi)預(yù)測(cè),算作一票。裝袋的分類(lèi)法C*統(tǒng)計(jì)得票,并將得票最高的類(lèi)賦予X。通過(guò)取得票的平均值,裝袋也可以用于連續(xù)值的預(yù)測(cè)。第六十二頁(yè),共八十七頁(yè),2022年,8月28日4.1裝袋/提升(續(xù))提升(Boosting)過(guò)程如下:每個(gè)訓(xùn)練樣本賦予一個(gè)權(quán),并學(xué)習(xí)得到一系列分類(lèi)法。對(duì)于迭代t(t=1,2,...,T),學(xué)習(xí)得到分類(lèi)法Ct后,更新權(quán),使得隨后的分類(lèi)法Ct+1“更關(guān)注”Ct的分類(lèi)錯(cuò)誤。最終的提升分類(lèi)法C*組合每個(gè)分類(lèi)法的表決,這里每個(gè)分類(lèi)法的表決是其準(zhǔn)確率的函數(shù)。通過(guò)取得票的平均值,提升算法也可以擴(kuò)充到連續(xù)值預(yù)測(cè)。第六十三頁(yè),共八十七頁(yè),2022年,8月28日4.2共同訓(xùn)練(Co-Training)共同訓(xùn)練算法用兩個(gè)不同的“視圖”(即特征集合)來(lái)描述文本的特征。基本思路:每個(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ù),直到滿(mǎn)足一定的條件為止。該算法中所用到的兩個(gè)視圖需要滿(mǎn)足以下兩個(gè)條件:首先,每個(gè)特征集合對(duì)文本分類(lèi)學(xué)習(xí)來(lái)說(shuō)都是充分的;其次,在給定類(lèi)別標(biāo)記的條件下,兩個(gè)特征集合相互獨(dú)立。第六十四頁(yè),共八十七頁(yè),2022年,8月28日4.3主動(dòng)學(xué)習(xí)/被動(dòng)學(xué)習(xí)主動(dòng)學(xué)習(xí)在學(xué)習(xí)過(guò)程中可以根據(jù)學(xué)習(xí)進(jìn)程,選擇最有利于分類(lèi)器性能的樣本來(lái)進(jìn)一步訓(xùn)練分類(lèi)器,它能有效地減少評(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ò)程中,分類(lèi)器主動(dòng)地選擇對(duì)其“最有幫助”的一組子樣本進(jìn)行學(xué)習(xí),而不是被動(dòng)地接受訓(xùn)練集?!白钣袔椭钡臉颖局傅氖菍?duì)當(dāng)前分類(lèi)器來(lái)說(shuō),歸屬最不確定的樣本。即當(dāng)前分類(lèi)器最難以區(qū)分的樣本。通常情況下,主動(dòng)學(xué)習(xí)的計(jì)算復(fù)雜度比一般的監(jiān)督學(xué)習(xí)過(guò)程要顯著得低。第六十五頁(yè),共八十七頁(yè),2022年,8月28日4.3主動(dòng)學(xué)習(xí)/被動(dòng)學(xué)習(xí)(續(xù))初始狀態(tài)下,候選樣本集中所有的樣本都未帶類(lèi)別標(biāo)注,根據(jù)先驗(yàn)知識(shí)或者隨機(jī)地從候選樣本集中選擇少量樣本并標(biāo)注它們的類(lèi)別,構(gòu)造初始訓(xùn)練樣本集,確保初始訓(xùn)練樣本集中至少包含有一個(gè)正例樣本和一個(gè)負(fù)例樣本。在上述初始訓(xùn)練樣本集上訓(xùn)練一個(gè)分類(lèi)器,并采用某種針對(duì)該分類(lèi)器采樣算法,從候選樣本集中選擇最有利于提高分類(lèi)器性能的樣本,手工標(biāo)注其類(lèi)別并加入訓(xùn)練樣本集,再重新訓(xùn)練分類(lèi)器。重復(fù)以上過(guò)程,直到候選樣本集為空或達(dá)到某種要求。主動(dòng)學(xué)習(xí)是一個(gè)循環(huán)反復(fù)的過(guò)程。第六十六頁(yè),共八十七頁(yè),2022年,8月28日在主動(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í)方法又可以被分為兩大類(lèi):其一是不確定取樣方法;另一是委員會(huì)咨詢(xún)方法。第六十七頁(yè),共八十七頁(yè),2022年,8月28日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è)試集樣本所攜帶的分類(lèi)信息,通過(guò)迭代逐步轉(zhuǎn)移到了最終的分類(lèi)器中去。由于測(cè)試樣本易于獲得、數(shù)量較多,直推式學(xué)習(xí)機(jī)能夠更好地描述整體樣本空間上的數(shù)據(jù)分布特性,使測(cè)試樣本的分類(lèi)結(jié)果更為準(zhǔn)確。第六十八頁(yè),共八十七頁(yè),2022年,8月28日4.4直推式學(xué)習(xí)(續(xù))在多數(shù)情況下,人們只對(duì)測(cè)試文本的分類(lèi)結(jié)果感興趣,這時(shí)就沒(méi)有必要非得尋求具有良好泛化能力的規(guī)則,而只要求分類(lèi)器能對(duì)這些特定的文本做出正確分類(lèi)即可。它在目前已知標(biāo)簽樣本十分緊缺,而未知標(biāo)簽樣本易于獲得的條件下,有著非常重要的現(xiàn)實(shí)意義。第六十九頁(yè),共八十七頁(yè),2022年,8月28日4.5廣義EM算法EM算法可用于許多問(wèn)題框架,其中需要估計(jì)一組描述基準(zhǔn)概率分布的參數(shù)θ,只給定了由此分布產(chǎn)生的全部數(shù)據(jù)中能觀察到的一部分。一般地,令X=<x1,…,xm>代表在同樣的實(shí)例中未觀察到的數(shù)據(jù),并令Y=X∪Z代表全體數(shù)據(jù)。注意到未觀察到的Z可被看作隨機(jī)變量,它的概率分布依賴(lài)于未知參數(shù)θ和已知數(shù)據(jù)X。類(lèi)似地,Y是一隨機(jī)變量,因?yàn)樗怯呻S機(jī)變量Z來(lái)定義的。在EM算法的一般形式中,用h來(lái)代表參數(shù)θ的假設(shè)值,而h′代表在EM的每次迭代中修改的假設(shè)。第七十頁(yè),共八十七頁(yè),2022年,8月28日4.5廣義EM算法(續(xù))EM算法通過(guò)搜尋使E[lnP(Y|h′)]最大的h′來(lái)尋找極大似然假設(shè)h′。此期望值是在Y所遵循的概率分布上計(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的可能值上取平均,并以相應(yīng)的概率為權(quán)值。第七十一頁(yè),共八十七頁(yè),2022年,8月28日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′:第七十二頁(yè),共八十七頁(yè),2022年,8月28日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)(Reward)和狀態(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)。第七十三頁(yè),共八十七頁(yè),2022年,8月28日4.6強(qiáng)化學(xué)習(xí)(續(xù))馬爾可夫過(guò)程是四元組
M=<S,A,T,R>。其中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’)表示狀態(tài)s下執(zhí)行行動(dòng)a到達(dá)狀態(tài)s’
的概率,且滿(mǎn)足∑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)。第七十四頁(yè),共八十七頁(yè),2022年,8月28日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),而不僅僅是即時(shí)回報(bào)。而長(zhǎng)遠(yuǎn)回報(bào)必須經(jīng)過(guò)一定時(shí)間的延遲之后才可以獲得。有終任務(wù)和持續(xù)任務(wù)可以統(tǒng)一起來(lái),他們的長(zhǎng)期回報(bào)是或第七十五頁(yè),共八十七頁(yè),2022年,8月28日4.6強(qiáng)化學(xué)習(xí)(續(xù))Agent與環(huán)境交互的學(xué)習(xí)中選擇行動(dòng)的方法稱(chēng)為策略π:S×A
[0,1],π(s,a)表示在狀態(tài)s下選擇行動(dòng)a的概率。策略的一個(gè)退化形式為π:SA,稱(chēng)為確定性策略,表示在狀態(tài)s下行動(dòng)a的執(zhí)行概率為1,其它行動(dòng)均為0。Q學(xué)習(xí)是最常用的強(qiáng)化學(xué)習(xí)技術(shù)。值函數(shù)Q函數(shù)第七十六頁(yè),共八十七頁(yè),2022年,8月28日4.6強(qiáng)化學(xué)習(xí)(續(xù))學(xué)習(xí)的目的是找到一個(gè)最優(yōu)策略。設(shè)有策略π和π’,若對(duì)所有狀態(tài)s∈S都有Vπ(s)≥Vπ’(s)
,則稱(chēng)策略π比策略π’好。這樣就總存在一個(gè)策略,它比其它所有策略都好,稱(chēng)為最優(yōu)策略π*。若最優(yōu)策略對(duì)應(yīng)的狀態(tài)評(píng)價(jià)函數(shù)記為V*,則對(duì)所有狀態(tài)s∈S,有V*(s)=maxVπ(s)。對(duì)所有狀態(tài)s∈S,所有行動(dòng)a∈A(s),有Q*(s)=maxQπ(s)。第七十七頁(yè),共八十七頁(yè),2022年,8月28日4.6強(qiáng)化學(xué)習(xí)(續(xù))三種計(jì)算“值函數(shù)”
Vπ(s)方法:動(dòng)態(tài)規(guī)劃法:已知環(huán)境模型T和R,每步進(jìn)行迭代。MonteCarlo法:沒(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ù)完成。第七十八頁(yè),共八十七頁(yè),2022年,8月28日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)講,由于其只能確定自身Agent的行為動(dòng)作,因此體現(xiàn)出一種行為動(dòng)作上的“部分感知”,從而產(chǎn)生出另一種形式的非標(biāo)準(zhǔn)馬爾可夫環(huán)境。多Agent強(qiáng)化學(xué)習(xí)的技術(shù)包括:合作多Agent強(qiáng)化學(xué)習(xí)(適用于分布、同構(gòu)、合作環(huán)境);基于
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 景德鎮(zhèn)藝術(shù)職業(yè)大學(xué)《配合物化學(xué)》2023-2024學(xué)年第一學(xué)期期末試卷
- 遼寧大學(xué)《嵌入式技術(shù)》2023-2024學(xué)年第一學(xué)期期末試卷
- 江蘇海事職業(yè)技術(shù)學(xué)院《口腔科學(xué)》2023-2024學(xué)年第一學(xué)期期末試卷
- 黑龍江工程學(xué)院昆侖旅游學(xué)院《建筑施工組織》2023-2024學(xué)年第一學(xué)期期末試卷
- 重慶三峽職業(yè)學(xué)院《食品儀器分析原子吸收測(cè)定水中鈣(標(biāo)準(zhǔn)曲線(xiàn)法)》2023-2024學(xué)年第一學(xué)期期末試卷
- 浙江越秀外國(guó)語(yǔ)學(xué)院《漆畫(huà)表現(xiàn)灰料新語(yǔ)言》2023-2024學(xué)年第一學(xué)期期末試卷
- 浙江海洋大學(xué)《GIS氣象應(yīng)用與開(kāi)發(fā)》2023-2024學(xué)年第一學(xué)期期末試卷
- 中國(guó)計(jì)量大學(xué)《生物信息學(xué)入門(mén)(雙語(yǔ))》2023-2024學(xué)年第一學(xué)期期末試卷
- 中央財(cái)經(jīng)大學(xué)《工程建筑制圖》2023-2024學(xué)年第一學(xué)期期末試卷
- 小學(xué)德育工作的管理制度
- 浙江寧波鄞州區(qū)市級(jí)名校2025屆中考生物全真模擬試卷含解析
- 電子招投標(biāo)平臺(tái)搭建與運(yùn)維服務(wù)合同
- IATF16949基礎(chǔ)知識(shí)培訓(xùn)教材
- 食品研發(fā)調(diào)研報(bào)告范文
- 2024-2030年國(guó)家甲級(jí)資質(zhì):中國(guó)干熱巖型地?zé)豳Y源融資商業(yè)計(jì)劃書(shū)
- 2024-2030年中國(guó)MVR蒸汽機(jī)械行業(yè)競(jìng)爭(zhēng)格局及投資發(fā)展前景分析報(bào)告
- 食材配送服務(wù)方案投標(biāo)文件(技術(shù)方案)
- 中國(guó)慢性阻塞性肺疾病基層診療指南(2024年)解讀
- 二零二四年度贈(zèng)與合同:關(guān)于藝術(shù)品捐贈(zèng)的贈(zèng)與合同
- 2023年高考真題-化學(xué)(福建卷) 含解析
- 纏繞膜項(xiàng)目實(shí)施方案
評(píng)論
0/150
提交評(píng)論