《分類(lèi)和預(yù)測(cè)》PPT課件.ppt

1,分類(lèi)和預(yù)測(cè),什么是分類(lèi)？什么是預(yù)測(cè) 關(guān)于分類(lèi)和預(yù)測(cè)的一些問(wèn)題 使用決策樹(shù)進(jìn)行分類(lèi) 用Excel來(lái)演示決策樹(shù) 用Matlab演示決策樹(shù),2,分類(lèi) 類(lèi)標(biāo)簽屬性的確定 基于訓(xùn)練集形成一個(gè)模型，訓(xùn)練集中的類(lèi)標(biāo)簽是已知的。使用該模型對(duì)新的數(shù)據(jù)(測(cè)試集)進(jìn)行分類(lèi) 預(yù)測(cè): 對(duì)連續(xù)性字段進(jìn)行建模和預(yù)測(cè)。 典型應(yīng)用 信用評(píng)分 目標(biāo)市場(chǎng)定位 醫(yī)療診斷 治療結(jié)果分析,分類(lèi)和預(yù)測(cè),3,分類(lèi)的兩個(gè)步驟,模型創(chuàng)建: 描述一組預(yù)先確定的類(lèi) 每一條記錄都屬于一個(gè)預(yù)先定義的類(lèi)別，我們使用類(lèi)標(biāo)簽屬性來(lái)標(biāo)識(shí)類(lèi)別。 用于創(chuàng)建模型的數(shù)據(jù)集叫:訓(xùn)練集 模型可以用分類(lèi)規(guī)則，決策樹(shù)，或者數(shù)學(xué)方程的形式來(lái)表達(dá)。 模型使用: 用創(chuàng)建的模型預(yù)測(cè)未來(lái)或者類(lèi)別未知的記錄的類(lèi)別 估計(jì)模型的準(zhǔn)確率 使用創(chuàng)建的模型在一個(gè)測(cè)試集上進(jìn)行預(yù)測(cè)，并將結(jié)果和實(shí)際值進(jìn)行比較 準(zhǔn)確率是測(cè)試集中被正確分類(lèi)的對(duì)象的比率 測(cè)試集和訓(xùn)練集是獨(dú)立的。,4,分類(lèi)過(guò)程(1)：模型創(chuàng)建,訓(xùn)練集,分類(lèi)算法,IF rank = professor OR years 6 THEN tenured = yes,模型,5,分類(lèi)過(guò)程 (2): 使用模型,模型,測(cè)試集,未知數(shù)據(jù),(Jeff, Professor, 4),Tenured?,6,有監(jiān)督和無(wú)監(jiān)督學(xué)習(xí),有監(jiān)督學(xué)習(xí) (分類(lèi)) 訓(xùn)練集是帶有類(lèi)標(biāo)簽的 新的數(shù)據(jù)是基于訓(xùn)練集進(jìn)行分類(lèi)的。 無(wú)監(jiān)督學(xué)習(xí) (聚類(lèi)) 訓(xùn)練集的類(lèi)標(biāo)簽未知。 給定一組測(cè)度(度量)或觀察，然后尋找出訓(xùn)練集中存在類(lèi)別或者聚類(lèi)。,7,分類(lèi)和預(yù)測(cè),什么是分類(lèi)？什么是預(yù)測(cè) 關(guān)于分類(lèi)和預(yù)測(cè)的一些問(wèn)題 使用決策樹(shù)進(jìn)行分類(lèi) 用Excel來(lái)演示決策樹(shù) 用Matlab演示決策樹(shù),8,關(guān)于分類(lèi)和預(yù)測(cè)的一些問(wèn)題 (1): 數(shù)據(jù)準(zhǔn)備,數(shù)據(jù)清洗 對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，消除噪音,處理缺失值。 相關(guān)性分析 (屬性選擇) 去掉不相關(guān)或者冗余的屬性 數(shù)據(jù)轉(zhuǎn)換 規(guī)范化或者對(duì)數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化,9,關(guān)于分類(lèi)和預(yù)測(cè)的問(wèn)題 (2): 評(píng)估分類(lèi)方法,預(yù)測(cè)準(zhǔn)確率 速度 創(chuàng)建速度 使用速度 強(qiáng)壯性 處理噪音和丟失值 伸縮性(規(guī)模化) 對(duì)磁盤(pán)駐留數(shù)據(jù)的處理能力 可解釋性: 對(duì)模型的可理解程度。 規(guī)則好壞的評(píng)價(jià) 決策樹(shù)的大小 分類(lèi)規(guī)則的簡(jiǎn)明性,10,分類(lèi)和預(yù)測(cè),什么是分類(lèi)？什么是預(yù)測(cè) 關(guān)于分類(lèi)和預(yù)測(cè)的一些問(wèn)題 使用決策樹(shù)進(jìn)行分類(lèi) 用Excel來(lái)演示決策樹(shù) 用Matlab演示決策樹(shù),11,使用決策樹(shù)歸納進(jìn)行分類(lèi),決策樹(shù) 一個(gè)類(lèi)似流程圖的樹(shù)結(jié)構(gòu) 內(nèi)部節(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試 每個(gè)分枝表示測(cè)試的結(jié)果 葉子節(jié)點(diǎn)表示類(lèi)或一個(gè)類(lèi)分布 決策樹(shù)生成算法分成兩個(gè)步驟 樹(shù)的創(chuàng)建 初始時(shí)，所有的訓(xùn)練例子都在根節(jié)點(diǎn) 根據(jù)被選屬性,遞歸地對(duì)例子進(jìn)行劃分 樹(shù)的修剪 識(shí)別并去掉那些反映噪音或者異常的分枝 決策樹(shù)使用: 對(duì)未知樣本進(jìn)行分類(lèi) 對(duì)照決策樹(shù)測(cè)試樣本的屬性值,12,訓(xùn)練集,例子源自Quilan的ID3算法,13,輸出: 關(guān)于購(gòu)買(mǎi)電腦的一棵決策樹(shù),age?,overcast,student?,credit rating?,no,yes,excellent,=30,40,no,no,yes,yes,yes,3040,14,決策樹(shù)算法,基本算法（貪心算法） 樹(shù)的建立是自上而下遞歸的分而治之的方法 初始時(shí)，所有的訓(xùn)練例子都在根節(jié)點(diǎn) 屬性都是類(lèi)別字段 (如果是連續(xù)的，將其離散化) 所有例子根據(jù)所選屬性遞歸地進(jìn)行劃分 屬性的選擇是基于一個(gè)啟發(fā)式規(guī)則或者一個(gè)統(tǒng)計(jì)的度量 (如, information gain, 信息增益) 停止劃分的條件 給定節(jié)點(diǎn)的所有樣本都屬于同一個(gè)類(lèi) 沒(méi)有剩余的屬性可以用于進(jìn)一步劃分樣本 分枝沒(méi)有樣本可劃分了,15,屬性選擇的統(tǒng)計(jì)度量,Information gain (ID3/C4.5) 所有屬性都假定為類(lèi)別型屬性 經(jīng)過(guò)修改之后可以適用于連續(xù)型屬性 Gini index (IBM IntelligentMiner) （僅供參考） 所有屬性都假定為連續(xù)型屬性 對(duì)每個(gè)屬性假定存在著幾種可能的拆分值 可能需要利用其他的工具, 如聚類(lèi), 獲得可能的拆分值 可以修改,以適用于類(lèi)別型屬性,16,信息增益,信息增益是一種基于熵的測(cè)度 信息增益可定義如下: 已知: 被分好類(lèi)的一組例子E(或稱樣本) E的一個(gè)劃分P= E1, ., En ig(E,P)=entropy(E)- i=1,.,nentropy(Ei)*|Ei|/|E|,17,信息理論中的Shannon熵,一般不確定性問(wèn)題所包含“不確定”(uncertainty) 的程度可以用數(shù)學(xué)來(lái)定量地描述嗎? 信息理論:Shannon熵, 1940年代末 硬幣反正面的不確定性 均勻 不均勻 數(shù)學(xué)描述,18,Shannon熵的數(shù)學(xué)描述,假設(shè)樣本空間 (Sample space) X 有 n 的基本事件 (events)，其基本事件 wi 的概率為 pi, i=1,2,n。我們記之為 。 ,i=1,2,n 表示不確定性,19,不確定性函數(shù)應(yīng)滿足的條件,(i)對(duì)于固定的n, H是(p1,p2,pn)的連續(xù)函數(shù) (ii)對(duì)于pi=1/n, H應(yīng)是n的單調(diào)遞增函數(shù) (iii)若某一試驗(yàn)分解成多個(gè)相繼的試驗(yàn)，則原先的 H 值應(yīng)為相應(yīng)的各個(gè) H 值的加權(quán)和 (weighted sum)。,20,圖示,21,Shannon熵,定理：滿足條件(i)、(ii)和(iii)的函數(shù) H 恰好具有形式 其中 K 為某個(gè)固定正常數(shù)。 Shannon熵: 由公式 定義的數(shù),稱為對(duì)應(yīng)于樣本空間(X, p1,p2,pn)的熵,22,信息增益(Information Gain),原來(lái)的不確定性 知道x之后的不確定性 信息增益: 原來(lái)-知道x之后的,23,信息增益(Information Gain),選擇屬性的標(biāo)準(zhǔn)：選擇具有最高信息增益(Information Gain)的屬性 假設(shè)有兩個(gè)類(lèi), P 和 N 假設(shè)集合S中含有p個(gè)類(lèi)別為P的樣本,n個(gè)類(lèi)別為N的樣本 將S中一個(gè)已知樣本進(jìn)行分類(lèi)所需要的期望信息定義為:,24,信息增益在決策樹(shù)中的使用,假設(shè)使用屬性A將把集合S劃分成 V份 S1, S2 , , Sv 如果 Si 中包含 pi 個(gè)類(lèi)別為 P的樣本, ni 個(gè)類(lèi)別為 N,的樣本。那么熵就是 (entropy), 在A上進(jìn)行分枝所獲得的編碼信息為:,25,使用信息增益進(jìn)行屬性選擇,Class P: buys_computer = “yes” Class N: buys_computer = “no” I(p, n) = I(9, 5) =0.940 Compute the entropy for age:,Hence Similarly,26,例子(1),27,例子(2),28,例子(3),29,Gini Index (IBM IntelligentMiner),集合T包含N個(gè)類(lèi)別的記錄，那么其Gini指標(biāo)就是 pj 類(lèi)別j出現(xiàn)的頻率 如果集合T分成兩部分 N1 and N2 。那么這個(gè)分割的Gini就是 具有最小Ginisplit 的屬性就被選擇用來(lái)拆分節(jié)點(diǎn)(對(duì)于每個(gè)屬性都要列舉所有可能拆分點(diǎn)).,30,生成決策樹(shù)的基本算法(1),算法 Generate_decision_tree(samples, attribute_list) 輸入: 訓(xùn)練樣本 samples, 由離散值屬性表示;候選屬性的集合attribute_list. 輸出:一棵決策樹(shù) 算法: (1) 創(chuàng)建節(jié)點(diǎn)N; (2) 如果samples都屬于同一個(gè)類(lèi)C那么 (3)返回N作為葉節(jié)點(diǎn), 以類(lèi)C標(biāo)記; (4)如果attribute_list為空則 (5)返回N作為葉節(jié)點(diǎn), 將該葉節(jié)點(diǎn)標(biāo)識(shí)為samples中最普遍的類(lèi),31,生成決策樹(shù)的基本算法(2),(6) 選擇attribute_list中具有最高信息增益的屬性test_attribute; (7)標(biāo)記節(jié)點(diǎn)N為test_attribute; (8)對(duì)于每個(gè)test_attribute中的已知值ai (9)由節(jié)點(diǎn)N長(zhǎng)出一個(gè)條件為test_attribute=ai的分枝; (10)設(shè)si是Samples中test_attribute=ai的樣本集合; (11)如果si為空則 (12)加上一個(gè)樹(shù)葉, 標(biāo)記為samples中最普遍的類(lèi); (13)否則 加上一個(gè)由Generate_decision_tree(si,attribute_list-test_attribute)返回的節(jié)點(diǎn);,32,從樹(shù)中生成分類(lèi)規(guī)則,用 IF-THEN 這種形式來(lái)表示規(guī)則 對(duì)從根到葉節(jié)點(diǎn)的每條路徑創(chuàng)建一條規(guī)則 沿著一條路徑的每個(gè)屬性值對(duì)構(gòu)成“并”連接 葉子節(jié)點(diǎn)中的類(lèi)別就是所預(yù)測(cè)的類(lèi) 規(guī)則更容易被人們理解 例子 IF age = “40” AND credit_rating = “excellent” THEN buys_computer = “yes” IF age = “=30” AND credit_rating = “fair” THEN buys_computer = “no”,33,在分類(lèi)中避免過(guò)度適應(yīng)(Overfit),所生成的樹(shù)可能會(huì)過(guò)度適應(yīng)于訓(xùn)練數(shù)據(jù) 太多的分支, 有些可能反映的是訓(xùn)練數(shù)據(jù)中的異常或噪音 在進(jìn)行預(yù)測(cè)的時(shí)候準(zhǔn)確率比較差 兩種方法避免過(guò)度適應(yīng) 預(yù)修剪: 難點(diǎn)：選擇一個(gè)域值比較困難 后修剪: 先生成完整的樹(shù)，然后進(jìn)行修剪 使用另外一個(gè)的一個(gè)測(cè)試集來(lái)決定哪個(gè)樹(shù)最好,34,分類(lèi)和預(yù)測(cè),什么是分類(lèi)？什么是預(yù)測(cè) 關(guān)于分類(lèi)和預(yù)測(cè)的一些問(wèn)題 使用決策樹(shù)進(jìn)行分類(lèi) 用Excel來(lái)演示決策樹(shù) 用Matlab演示決策樹(shù),35,分類(lèi)和預(yù)測(cè),什么是分類(lèi)？什么是預(yù)測(cè) 關(guān)于分類(lèi)和預(yù)測(cè)的一些問(wèn)題 使用決策樹(shù)進(jìn)行分類(lèi) 用Excel來(lái)演示決策樹(shù) 用Matlab演示決策樹(shù),36,用Matlab演示決策樹(shù),數(shù)據(jù)集說(shuō)明 Iris plant data: (150條記錄) 屬性信息: 1. sepal length in cm: 萼片的長(zhǎng)度(厘米) 2. sepal width in cm: 萼片的寬度(厘米) 3. petal length in cm: 花瓣的長(zhǎng)度(厘米) 4. petal width in cm:花瓣的寬度(厘米) 5. class: - Iris Setosa: 蝴蝶花(鳶尾)長(zhǎng)有剛毛的 - Iris Versicolour:雜色 - Iris Virginica:純色 共有數(shù)據(jù):150條, 4個(gè)輸入屬性,都是數(shù)值型的,一個(gè)輸出屬性(分類(lèi)屬性)是標(biāo)稱型(類(lèi)別型),37,寫(xiě)在后面的知識(shí)介紹網(wǎng)絡(luò)蜘蛛與搜索引擎的基本原理,搜索引擎的工作原理 搜集信息 網(wǎng)絡(luò)蜘蛛 整理信息 接受查詢,38,網(wǎng)絡(luò)蜘蛛原理,Web spider 互聯(lián)網(wǎng)-網(wǎng) 蜘蛛-爬 抓取多少呢？ 容量最大的搜索引擎也不過(guò)是抓取了整個(gè)網(wǎng)頁(yè)數(shù)量的40%左右 為什么？ 抓取技術(shù)？還是容量？,39,網(wǎng)絡(luò)蜘蛛原理,Web spider 抓取網(wǎng)頁(yè)策略 深度優(yōu)先 廣度優(yōu)先 網(wǎng)站與網(wǎng)絡(luò)蜘蛛 會(huì)不會(huì)引起服務(wù)器負(fù)擔(dān)過(guò)重？ 抓那些不抓那些？ 如何向網(wǎng)站表明自己的身份？ GoogleBot, BaiDuSpider, Inktomi Slu