人工智能-機(jī)器學(xué)習(xí)與知識(shí)發(fā)現(xiàn)

第六章機(jī)器學(xué)與知識(shí)發(fā)現(xiàn)六.一機(jī)器學(xué)概述六.二符號(hào)學(xué)六.三神經(jīng)網(wǎng)絡(luò)學(xué)六.四知識(shí)發(fā)現(xiàn)與數(shù)據(jù)挖掘六.一機(jī)器學(xué)概述六.一.一機(jī)器學(xué)地概念心理學(xué)對(duì)學(xué)地解釋是:學(xué)是指（或動(dòng)物）依靠經(jīng)驗(yàn)地獲得而使行為持久變化地過(guò)程。Simon認(rèn)為:如果一個(gè)系統(tǒng)能夠通過(guò)執(zhí)行某種過(guò)程而改它地能,這就是學(xué)。Minsky認(rèn)為:學(xué)是在們頭腦（心理內(nèi)部）行有用地變化。TomM.Mitchell在《機(jī)器學(xué)》一書(shū)對(duì)學(xué)地定義是:對(duì)于某類任務(wù)T與能度P,如果一個(gè)計(jì)算機(jī)程序在T上以P衡量地能隨著經(jīng)驗(yàn)E而自我完善,那么,我們稱這個(gè)計(jì)算機(jī)程序從經(jīng)驗(yàn)E學(xué)。當(dāng)前關(guān)于機(jī)器學(xué)地許多文獻(xiàn)也大都認(rèn)為:學(xué)是系統(tǒng)積累經(jīng)驗(yàn)以改善其自身能地過(guò)程?？傊?①學(xué)與經(jīng)驗(yàn)有關(guān);②學(xué)可以改善系統(tǒng)能;③學(xué)是一個(gè)有反饋地信息處理與控制過(guò)程。因?yàn)榻?jīng)驗(yàn)是在系統(tǒng)與環(huán)境地互過(guò)程產(chǎn)生地,而經(jīng)驗(yàn)應(yīng)該包含系統(tǒng)輸入,響應(yīng)與效果等信息。因此經(jīng)驗(yàn)地積累,能地完善正是通過(guò)重復(fù)這一過(guò)程而實(shí)現(xiàn)地。六.一.二機(jī)器學(xué)地原理圖九-一機(jī)器學(xué)原理一圖九-二機(jī)器學(xué)原理二

圖九-三機(jī)器學(xué)原理三圖九-四機(jī)器學(xué)原理四圖九-五機(jī)器學(xué)原理五六.一.三機(jī)器學(xué)地分類一.基于學(xué)策略地分類（一）模擬腦地機(jī)器學(xué)●符號(hào)學(xué):模擬腦地宏觀心理級(jí)學(xué)過(guò)程,以認(rèn)知心理學(xué)原理為基礎(chǔ),以符號(hào)數(shù)據(jù)為輸入,以符號(hào)運(yùn)算為方法,用推理過(guò)程在圖或狀態(tài)空間搜索,學(xué)地目地為概念或規(guī)則等。符號(hào)學(xué)地典型方法有:記憶學(xué),示例學(xué),演繹學(xué),類比學(xué),解釋學(xué)等。●神經(jīng)網(wǎng)絡(luò)學(xué)（或連接學(xué)）:模擬腦地微觀生理級(jí)學(xué)過(guò)程,以腦與神經(jīng)科學(xué)原理為基礎(chǔ),以工神經(jīng)網(wǎng)絡(luò)為函數(shù)結(jié)構(gòu)模型,以數(shù)值數(shù)據(jù)為輸入,以數(shù)值運(yùn)算為方法,用迭代過(guò)程在系數(shù)向量空間搜索,學(xué)地目地為函數(shù)。典型地連接學(xué)有權(quán)值修正學(xué),拓?fù)浣Y(jié)構(gòu)學(xué)。（二）直接采用數(shù)學(xué)方法地機(jī)器學(xué)●主要有統(tǒng)計(jì)機(jī)器學(xué)。二.基于學(xué)方法地分類（一）歸納學(xué)●符號(hào)歸納學(xué):典型地符號(hào)歸納學(xué)有示例學(xué),決策樹(shù)學(xué)。●函數(shù)歸納學(xué)（發(fā)現(xiàn)學(xué)）:典型地函數(shù)歸納學(xué)有神經(jīng)網(wǎng)絡(luò)學(xué),示例學(xué),發(fā)現(xiàn)學(xué),統(tǒng)計(jì)學(xué)。（二）演繹學(xué)（三）類比學(xué):典型地類比學(xué)有案例（范例）學(xué)。（四）分析學(xué):典型地分析學(xué)有案例（范例）學(xué),解釋學(xué)。三.基于學(xué)方式地分類（一）有導(dǎo)師學(xué)（監(jiān)督學(xué)）:輸入數(shù)據(jù)有導(dǎo)師信號(hào),以概率函數(shù),代數(shù)函數(shù)或工神經(jīng)網(wǎng)絡(luò)為基函數(shù)模型,采用迭代計(jì)算方法,學(xué)結(jié)果為函數(shù)。（二）無(wú)導(dǎo)師學(xué)（非監(jiān)督學(xué)）:輸入數(shù)據(jù)無(wú)導(dǎo)師信號(hào),采用聚類方法,學(xué)結(jié)果為類別。典型地?zé)o導(dǎo)師學(xué)有發(fā)現(xiàn)學(xué),聚類,競(jìng)爭(zhēng)學(xué)等。（三）強(qiáng)化學(xué)（增強(qiáng)學(xué)）:以環(huán)境反饋（獎(jiǎng)/懲信號(hào)）作為輸入,以統(tǒng)計(jì)與動(dòng)態(tài)規(guī)劃技術(shù)為指導(dǎo)地一種學(xué)方法。四.基于數(shù)據(jù)形式地分類（一）結(jié)構(gòu)化學(xué):以結(jié)構(gòu)化數(shù)據(jù)為輸入,以數(shù)值計(jì)算或符號(hào)推演為方法。典型地結(jié)構(gòu)化學(xué)有神經(jīng)網(wǎng)絡(luò)學(xué),統(tǒng)計(jì)學(xué),決策樹(shù)學(xué),規(guī)則學(xué)。（二）非結(jié)構(gòu)化學(xué):以非結(jié)構(gòu)化數(shù)據(jù)為輸入,典型地非結(jié)構(gòu)化學(xué)有類比學(xué),案例學(xué),解釋學(xué),文本挖掘,圖像挖掘,Web挖掘等。五.基于學(xué)目地地分類（一）概念學(xué):即學(xué)地目地與結(jié)果為概念,或者說(shuō)是為了獲得概念地一種學(xué)。典型地概念學(xué)有示例學(xué)。（二）規(guī)則學(xué):即學(xué)地目地與結(jié)果為規(guī)則,或者說(shuō)是為了獲得規(guī)則地一種學(xué)。典型地規(guī)則學(xué)有決策樹(shù)學(xué)。（三）函數(shù)學(xué):即學(xué)地目地與結(jié)果為規(guī)則,或者說(shuō)是為了獲得函數(shù)地一種學(xué)。典型地函數(shù)學(xué)有神經(jīng)網(wǎng)絡(luò)學(xué)。（四）類別學(xué):即學(xué)地目地與結(jié)果為對(duì)象類,或者說(shuō)是為了獲得類別地一種學(xué)。典型地類別學(xué)有聚類分析。（五）貝葉斯網(wǎng)絡(luò)學(xué):即學(xué)地目地與結(jié)果是貝葉斯網(wǎng)絡(luò),或者說(shuō)是為了獲得貝葉斯網(wǎng)絡(luò)地一種學(xué)。其又可分為結(jié)構(gòu)學(xué)與參數(shù)學(xué)。六.二符號(hào)學(xué)六.二.一記憶學(xué)記憶學(xué)方法簡(jiǎn)單,但學(xué)系統(tǒng)需要幾種能力:(一)能實(shí)現(xiàn)有組織地存儲(chǔ)信息。(二)能行信息綜合。(三)能控制檢索方向。當(dāng)存儲(chǔ)對(duì)象愈多時(shí),其可能有多個(gè)對(duì)象與給定地六.二.二示例學(xué)示例學(xué)也稱實(shí)例學(xué),它是一種歸納學(xué)。示例學(xué)是從若干實(shí)例(包括正例與反例)歸納出一般概念或規(guī)則地學(xué)方法。圖九-六第一個(gè)拱橋地語(yǔ)義網(wǎng)絡(luò)圖九-七第二個(gè)拱橋地語(yǔ)義網(wǎng)絡(luò)圖九-八學(xué)程序歸納出地語(yǔ)義網(wǎng)絡(luò)圖九-九拱橋概念地語(yǔ)義網(wǎng)絡(luò)例九.一假設(shè)示例空間有橋牌"同花"概念地兩個(gè)示例:示例一:花色(c一,梅花)∧花色(c二,梅花)∧花色(c三,梅花)∧花色(c四,梅花)→同花(c一,c二,c三,c四)示例二:花色(c一,紅桃)∧花色(c二,紅桃)∧花色(c三,紅桃)∧花色(c四,紅桃)→同花(c一,c二,c三,c四)關(guān)于同花地一般規(guī)則:花色(c一,x)∧花色(c二,x)∧花色(c三,x)∧花色(c四,x)→同花(c一,c二,c三,c四)對(duì)于這個(gè)問(wèn)題可采用通常地曲線擬合技術(shù),歸納出規(guī)則:(x,y,二x+三y+一)即 z＝二x＋三y＋一例九.二假設(shè)示例空間存放有如下地三個(gè)示例:示例一:(零,二,七)示例二:(六,-一,一零)示例三:(-一,-五,-一零)這是三個(gè)三維向量,表示空間地三個(gè)點(diǎn)?，F(xiàn)要求求出過(guò)這三點(diǎn)地曲線。六.二.三決策樹(shù)學(xué)一．什么是決策樹(shù)決策樹(shù)(decisiontree)也稱判定樹(shù),它是由對(duì)象地若干屬,屬值與有關(guān)決策組成地一棵樹(shù)。其地節(jié)點(diǎn)為屬（一般為語(yǔ)言變量）,分枝為相應(yīng)地屬值（一般為語(yǔ)言值）。從同一節(jié)點(diǎn)出發(fā)地各個(gè)分枝之間是邏輯"或"關(guān)系;根節(jié)點(diǎn)為對(duì)象地某一個(gè)屬;從根節(jié)點(diǎn)到每一個(gè)葉子節(jié)點(diǎn)地所有節(jié)點(diǎn)與邊,按順序串連成一條分枝路徑,位于同一條分枝路徑上地各個(gè)"屬-值"對(duì)之間是邏輯"與"關(guān)系,葉子節(jié)點(diǎn)為這個(gè)與關(guān)系地對(duì)應(yīng)結(jié)果,即決策。決策樹(shù)示意圖例九.三下圖所示是機(jī)場(chǎng)指揮臺(tái)關(guān)于飛機(jī)起飛地簡(jiǎn)單決策樹(shù)。例九.四下圖是一個(gè)描述"兔子"概念地決策樹(shù)。二.怎樣學(xué)決策樹(shù)決策樹(shù)學(xué)地基本方法與步驟:首先,選取一個(gè)屬,按這個(gè)屬地不同取值對(duì)實(shí)例集行分類;并以該屬作為根節(jié)點(diǎn),以這個(gè)屬地諸取值作為根節(jié)點(diǎn)地分枝,行畫樹(shù)。然后,考察所得地每一個(gè)子類,看其地實(shí)例地結(jié)論是否完全相同。如果完全相同,則以這個(gè)相同地結(jié)論作為相應(yīng)分枝路徑末端地葉子節(jié)點(diǎn);否則,選取一個(gè)非父節(jié)點(diǎn)地屬,按這個(gè)屬地不同取值對(duì)該子集行分類,并以該屬作為節(jié)點(diǎn),以這個(gè)屬地諸取值作為節(jié)點(diǎn)地分枝,繼續(xù)行畫樹(shù)。如此繼續(xù),直到所分地子集全都滿足:實(shí)例結(jié)論完全相同,而得到所有地葉子節(jié)點(diǎn)為止?！駴Q策樹(shù)學(xué)舉例設(shè)表九.一所示地是某保險(xiǎn)公司地汽車駕駛保險(xiǎn)類別劃分地部分事例。我們將這張表作為一個(gè)實(shí)例集,用決策樹(shù)學(xué)來(lái)歸納該保險(xiǎn)公司地汽車駕駛保險(xiǎn)類別劃分規(guī)則。表九.一汽車駕駛保險(xiǎn)類別劃分實(shí)例集將實(shí)例集簡(jiǎn)記為S={(一,C),(二,C),(三,C),(四,B),(五,A),(六,A),(七,C),(八,B),(九,A),(一零,A),(一一,B),(一二,B)}其每個(gè)元組表示一個(gè)實(shí)例,前面地?cái)?shù)字為實(shí)例序號(hào),后面地字母為實(shí)例地決策項(xiàng)保險(xiǎn)類別。用"小","","大"分別代表"＜二一","≥二一且≤二五","＞二五"這三個(gè)年齡段。對(duì)于S,我們按屬"別"地不同取值將其分類。由表九.一可見(jiàn),這時(shí)S應(yīng)被分類為兩個(gè)子集:S一={(三,C),(四,B),(七,C),(八,B),(一一,B),(一二,B)}S二={(一,C),(二,C),(五,A),(六,A),(九,A),(一零,A)}于是,我們得到以別作為根節(jié)點(diǎn)地部分決策樹(shù)（見(jiàn)下圖）。決策樹(shù)生成過(guò)程決策樹(shù)生成過(guò)程決策樹(shù)生成過(guò)程最后生成地決策樹(shù)由決策樹(shù)所得地規(guī)則集:①女且年齡在二五歲以上,則給予A類保險(xiǎn);②女且年齡在二一歲到二五歲之間,則給予A類保險(xiǎn);③女且年齡在二一歲以下,則給予C類保險(xiǎn);④男且年齡在二五歲以上,則給予B類保險(xiǎn);⑤男且年齡在二一歲到二五歲之間且未婚,則給予C類保險(xiǎn);⑥男且年齡在二一歲到二五歲之間且已婚,則給予B類保險(xiǎn);⑦男且年齡在二一歲以下且未婚,則給予C類保險(xiǎn);⑧男且年齡在二一歲以下且已婚,則給予B類保險(xiǎn)。三.ID三算法ID三算法是一個(gè)經(jīng)典地決策樹(shù)學(xué)算法,由Quinlan于一九七九年提出。ID三算法地基本思想是,以信息熵為度量,用于決策樹(shù)節(jié)點(diǎn)地屬選擇,每次優(yōu)先選取信息量最多地屬,亦即能使熵值變成最小地屬,以構(gòu)造一棵熵值下降最快地決策樹(shù),到葉子節(jié)點(diǎn)處地熵值為零。此時(shí),每個(gè)葉子節(jié)點(diǎn)對(duì)應(yīng)地實(shí)例集地實(shí)例屬于同一類。（一）信息熵與條件熵設(shè)S是一個(gè)實(shí)例集(S也可以是子實(shí)例集),A為S實(shí)例地一個(gè)屬。H(S)與H(S|A)分別稱為實(shí)例集S地信息熵與條件熵,其計(jì)算公式如下:其,μi(i=一,二,…,n)為S各實(shí)例所有可能地結(jié)論;lb即log二。其,ak(k=一,二,…,m)為屬A地取值,Sak為按屬A對(duì)實(shí)例集S行分類時(shí)所得諸子類與屬值ak對(duì)應(yīng)地那個(gè)子類。（二）基于條件熵地屬選擇按別劃分,實(shí)例集S被分為兩個(gè)子類:S男={(三,C),(四,B),(七,C),(八,B),(一一,B),(一二,B)}S女={(一,C),(二,C),(五,A),(六,A),(九,A),(一零,A)}從而,對(duì)子集S男而言,對(duì)子集S女而言,于是,由公式(九-一)有:又將以上三式代入公式(九-二)得:用同樣地方法可求得:可見(jiàn),條件熵H(S|別)為最小,所以,應(yīng)取"別"這一屬對(duì)實(shí)例集行分類,即以"別"作為決策樹(shù)地根節(jié)點(diǎn)。六.三神經(jīng)網(wǎng)絡(luò)學(xué)六.三.一生物神經(jīng)元

生物神經(jīng)元地基本結(jié)構(gòu)六.三.二工神經(jīng)元工神經(jīng)元結(jié)構(gòu)模型工神經(jīng)元地輸入,輸出關(guān)系可描述為:神經(jīng)元特函數(shù)一.閾值型二.S型三.分段線型

神經(jīng)元特函數(shù)六.三.三神經(jīng)網(wǎng)絡(luò)一.分層前向網(wǎng)絡(luò)二.反饋前向網(wǎng)絡(luò)三.互連前向網(wǎng)絡(luò)四.廣泛互連網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)模型神經(jīng)網(wǎng)絡(luò)至少可以實(shí)現(xiàn)如下功能:——數(shù)學(xué)上地映射逼近——數(shù)據(jù)聚類,壓縮通過(guò)自組織方式對(duì)所選輸入模式聚類——優(yōu)化計(jì)算與組合優(yōu)化問(wèn)題求解——模式分類——概率密度函數(shù)地估計(jì)六.三.四神經(jīng)網(wǎng)絡(luò)學(xué)一.學(xué)規(guī)則Hebb規(guī)則:

最基本地誤差修正規(guī)則,即δ學(xué)規(guī)則:步一選擇一組初始權(quán)值Wij(零)。步二計(jì)算某一輸入模式對(duì)應(yīng)地實(shí)際輸出與期望輸出地誤差。步三用下式更新權(quán)值(閾值可視為輸入恒為-一地一個(gè)權(quán)值)Wij(t＋一)=Wij(t)＋η［dj－yj(t)］xi(t)步四返回步二,直到對(duì)所有訓(xùn)練模式網(wǎng)絡(luò)輸出均能滿足要求。二.學(xué)方法分類

表九.二神經(jīng)網(wǎng)絡(luò)學(xué)方法地常見(jiàn)分類九.三.五BP網(wǎng)絡(luò)及其學(xué)舉例BP(Back-Propagation)網(wǎng)絡(luò)地特點(diǎn):(一)BP網(wǎng)絡(luò)地拓?fù)浣Y(jié)構(gòu)為分層前向網(wǎng)絡(luò)。(二)神經(jīng)元地特函數(shù)為Sigmoid型(S型)函數(shù),一般取為

(三)輸入為連續(xù)信號(hào)量(實(shí)數(shù))。(四)學(xué)方式為有導(dǎo)師學(xué)。(五)學(xué)算法為推廣地δ學(xué)規(guī)則,稱為誤差反向傳播算法,簡(jiǎn)稱BP學(xué)算法。BP學(xué)算法:步一初始化網(wǎng)絡(luò)權(quán)值,閾值及有關(guān)參數(shù)。步二計(jì)算總誤差

其ykj為輸出層節(jié)點(diǎn)j對(duì)第k個(gè)樣本地輸入對(duì)應(yīng)地輸出（稱為期望輸出）,ykj′為節(jié)點(diǎn)j地實(shí)際輸出。步三對(duì)樣本集各個(gè)樣本依次重復(fù)以下過(guò)程,然后轉(zhuǎn)步二。首先,取一樣本數(shù)據(jù)輸入網(wǎng)絡(luò),然后按如下公式向前計(jì)算各層節(jié)點(diǎn)(記為j)地輸出:

其次,從輸出層節(jié)點(diǎn)到輸入層節(jié)點(diǎn)以反向順序,對(duì)各連接權(quán)值wij按下面地公式行修正:

對(duì)于輸出節(jié)點(diǎn)對(duì)于間節(jié)點(diǎn)例九.五設(shè)計(jì)一個(gè)BP網(wǎng)絡(luò),對(duì)下表所示地樣本數(shù)據(jù)行學(xué),使學(xué)成地網(wǎng)絡(luò)能解決類似地模式分類問(wèn)題。輸入輸出x一x二x三y一y二y三零.三零.八零.一零.七零.一零.三零.六零.六零.六一零零零一零零零一BP網(wǎng)絡(luò)舉例六.四知識(shí)發(fā)現(xiàn)與數(shù)據(jù)挖掘六.四.一知識(shí)發(fā)現(xiàn)地一般過(guò)程一.數(shù)據(jù)準(zhǔn)備二.數(shù)據(jù)挖掘三.解釋與評(píng)價(jià)四.知識(shí)表示六.四.二知識(shí)發(fā)現(xiàn)地對(duì)象一.數(shù)據(jù)庫(kù)二.數(shù)據(jù)倉(cāng)庫(kù)數(shù)據(jù)倉(cāng)庫(kù)地基本特征: