數(shù)據(jù)挖掘08分類和預(yù)測ppt課件

1、分類和預(yù)測分類 VS. 預(yù)測n分類和預(yù)測是兩種數(shù)據(jù)分析方式，用于提取描畫重要數(shù)據(jù)類或預(yù)測未來的數(shù)據(jù)趨勢 的模型n分類：n預(yù)測類對象的分類標(biāo)號或離散值n根據(jù)訓(xùn)練數(shù)據(jù)集和類標(biāo)號屬性，構(gòu)建模型來分類現(xiàn)有數(shù)據(jù)，并用來分類新數(shù)據(jù)n預(yù)測：n建立延續(xù)函數(shù)值模型n比如預(yù)測空缺值，或者預(yù)測顧客在計算機(jī)設(shè)備上的破費n典型運用n欺詐檢測、市場定位、性能預(yù)測、醫(yī)療診斷分類和預(yù)測-例如n分類n銀行貸款員需求分析數(shù)據(jù)，來弄清哪些貸款懇求者是平安的，哪些是有風(fēng)險的將貸款懇求者分為“平安和“有風(fēng)險兩類n我們需求構(gòu)造一個分類器來預(yù)測類屬編號，比如預(yù)測顧客屬類n預(yù)測n銀行貸款員需求預(yù)測貸給某個顧客多少錢是平安的n構(gòu)造一個預(yù)測器，

2、預(yù)測一個延續(xù)值函數(shù)或有序值，常用方法是回歸分析數(shù)據(jù)分類一個兩步過程 (1)n第一步，也成為學(xué)習(xí)步，目的是建立描畫預(yù)先定義的數(shù)據(jù)類或概念集的分類器n分類算法經(jīng)過分析或從訓(xùn)練集“學(xué)習(xí)來構(gòu)造分類器。n訓(xùn)練集由數(shù)據(jù)庫元組用n維屬性向量表示和他們相對應(yīng)的類編號組成；假定每個元組屬于一個預(yù)定義的類n訓(xùn)練元組：訓(xùn)練數(shù)據(jù)集中的單個元組n學(xué)習(xí)模型可以用分類規(guī)那么、決策樹或數(shù)學(xué)公式的方式提供數(shù)據(jù)分類一個兩步過程 (2)n第二步，運用模型，對未來的或未知的對象進(jìn)展分類n首先評價模型的預(yù)測準(zhǔn)確率n對每個測試樣本，將知的類標(biāo)號和該樣本的學(xué)習(xí)模型類預(yù)測比較n模型在給定測試集上的準(zhǔn)確率是正確被模型分類的測試樣本的百分比n測

3、試集要獨立于訓(xùn)練樣本集，否那么會出現(xiàn)“過分?jǐn)M合的情況第一步建立模型訓(xùn)練數(shù)據(jù)集NAME RANKYEARS TENUREDMikeAssistant Prof3noMaryAssistant Prof7yesBill Professor2yesJimAssociate Prof7yesDaveAssistant Prof6noAnneAssociate Prof3no分類算法IF rank = professorOR years 6THEN tenured = yes 分類規(guī)那么第二步用模型進(jìn)展分類分類規(guī)那么測試集NAMERANKYEARS TENUREDTomAssistant Prof2no

4、Merlisa Associate Prof7noGeorge Professor5yesJoseph Assistant Prof7yes未知數(shù)據(jù)(Jeff, Professor, 4)Tenured?監(jiān)視學(xué)習(xí) VS. 無監(jiān)視學(xué)習(xí)n監(jiān)視學(xué)習(xí)用于分類n模型的學(xué)習(xí)在被告知每個訓(xùn)練樣本屬于哪個類的“指點下進(jìn)展n新數(shù)據(jù)運用訓(xùn)練數(shù)據(jù)集中得到的規(guī)那么進(jìn)展分類n無監(jiān)視學(xué)習(xí)用于聚類n每個訓(xùn)練樣本的類編號是未知的，要學(xué)習(xí)的類集合或數(shù)量也能夠是事先未知的n經(jīng)過一系列的度量、察看來建立數(shù)據(jù)中的類編號或進(jìn)展聚類數(shù)據(jù)預(yù)測的兩步過程n數(shù)據(jù)預(yù)測也是一個兩步的過程，類似于前面描畫的數(shù)據(jù)分類n對于預(yù)測，沒有“類標(biāo)號屬性n要預(yù)

5、測的屬性是延續(xù)值，而不是離散值，該屬性可簡稱“預(yù)測屬性nE.g. 銀行貸款員需求預(yù)測貸給某個顧客多少錢是平安的n預(yù)測器可以看作一個映射或函數(shù)y=f(X)n其中X是輸入；y是輸出，是一個延續(xù)或有序的值n與分類類似，準(zhǔn)確率的預(yù)測，也要運用單獨的測試集預(yù)備分類和預(yù)測的數(shù)據(jù)n經(jīng)過對數(shù)據(jù)進(jìn)展預(yù)處置，可以提高分類和預(yù)測過程的準(zhǔn)確性、有效性和可伸縮性n數(shù)據(jù)清理n消除或減少噪聲，處置空缺值，從而減少學(xué)習(xí)時的混亂n相關(guān)分析n數(shù)據(jù)中的有些屬性能夠與當(dāng)前義務(wù)不相關(guān)；也有些屬性能夠是冗余的；刪除這些屬性可以加快學(xué)習(xí)步驟，使學(xué)習(xí)結(jié)果更準(zhǔn)確n數(shù)據(jù)變換與歸約n數(shù)據(jù)可以經(jīng)過規(guī)范化進(jìn)展變換，將所給屬性的一切值按比例進(jìn)展縮放，使

6、其落入一個較小的指定區(qū)間，例 0.0, 1.0ANN和設(shè)計間隔的度量方法中常用n可以將數(shù)據(jù)概化到較高層概念比較分類方法n運用以下規(guī)范比較分類和預(yù)測方法n預(yù)測的準(zhǔn)確率：模型正確預(yù)測新數(shù)據(jù)的類編號的才干n速度：產(chǎn)生和運用模型的計算花銷n強(qiáng)壯性：給定噪聲數(shù)據(jù)或有空缺值的數(shù)據(jù)，模型正確預(yù)測的才干n可伸縮性：對大量數(shù)據(jù)，有效的構(gòu)建分類器或預(yù)測器的才干n可解釋性：學(xué)習(xí)模型提供的了解和洞察的層次用決策樹歸納分類 (1)n什么是決策樹？n類似于流程圖的樹構(gòu)造n每個內(nèi)部節(jié)點表示在一個屬性上的測試n每個分枝代表一個測試輸出n每個樹葉節(jié)點存放一個類編號age?student?credit rating?noyesf

7、airexcellentyouthseniornonoyesyesyesMiddleaged決策樹：決策樹：Buys_computer用決策樹歸納分類 (2)n運用決策樹分類n給定一個類標(biāo)號未知的元組X，在決策樹上測試元組的屬性值，跟蹤一條由根到葉節(jié)點的途徑，葉節(jié)點存放該元組的類預(yù)測。n決策樹容易轉(zhuǎn)換為分類規(guī)那么n決策樹的生成由兩個階段組成n決策樹構(gòu)建n運用屬性選擇度量來選擇將元組最好的劃分為不同的類的屬性n遞歸的經(jīng)過選定的屬性，來劃分樣本 必需是離散值n樹剪枝n決策樹建立時，許多分枝反映的是訓(xùn)練數(shù)據(jù)中的噪聲和離群點點，樹剪枝試圖識別并剪去這種分枝，以提高對未知數(shù)據(jù)分類的準(zhǔn)確性決策樹歸納戰(zhàn)略

8、(1)n輸入n數(shù)據(jù)劃分D是訓(xùn)練元組和對應(yīng)類標(biāo)號的集合nattribute_list,候選屬性的集合nAttribute_selection_method，指定選擇屬性的啟發(fā)性過程n算法步驟n樹以代表訓(xùn)練樣本的單個節(jié)點N開場n假設(shè)樣本都在同一個類，那么該節(jié)點成為樹葉，并用該類標(biāo)志n否那么，算法調(diào)用Attribute_selection_method，選擇可以最好的將樣本分類的屬性；確定“分裂準(zhǔn)那么，指出“分裂點或“分裂子集。決策樹歸納戰(zhàn)略 (2)n對測試屬性每個知的值，創(chuàng)建一個分支，并以此劃分元組n算法運用同樣的過程，遞歸的構(gòu)成每個劃分上的元組決策樹。一旦一個屬性出如今一個節(jié)點上，就不在該節(jié)點的

9、任何子節(jié)點上出現(xiàn)n遞歸劃分步驟停頓的條件n劃分D在N節(jié)點提供的一切元組屬于同一類n沒有剩余屬性可以用來進(jìn)一步劃分元組運用多數(shù)表決n沒有剩余的樣本n給定分支沒有元組，那么以D中多數(shù)類創(chuàng)建一個樹葉屬性選擇度量n屬性選擇度量是一種選擇分裂準(zhǔn)那么，將給定類標(biāo)號的訓(xùn)練元組最好的進(jìn)展劃分的方法n理想情況，每個劃分都是“純的，即落在給定劃分內(nèi)的元組都屬于一樣的類n屬性選擇度量又稱為分裂準(zhǔn)那么n常用的屬性選擇度量n信息增益n增益率nGini目的信息增益 (1)nS是一個訓(xùn)練樣本的集合，該樣本中每個集合的類編號知。每個樣本為一個元組。有個屬性用來斷定某個訓(xùn)練樣本的類編號n假設(shè)S中有m個類，總共s個訓(xùn)練樣本，每個

10、類Ci有si個樣本(i1,2,3.m)，那么恣意一個樣本屬于類Ci的概率是si / s，那么用來分類一個給定樣本的期望信息是：sssssssInfoimiim2121log),.,(信息增益 (2)n一個有v個值的屬性Aa1,a2,.,av可以將S分成v個子集S1,S2,.,Sv，其中Sj包含S中屬性A上的值為aj的樣本。假設(shè)Sj包含類Ci的sij個樣本。根據(jù)A的這種劃分的期望信息稱為A的熵nA上該劃分的獲得的信息增益定義為：n具有高信息增益的屬性，是給定集合中具有高區(qū)分度的屬性。所以可以經(jīng)過計算S中樣本的每個屬性的信息增益，來得到一個屬性的相關(guān)性的排序。),.,(.)(111mjjvjmjj

11、ssIsssAE)(),.,()(21AEsssIAGainmageincomestudentcredit_ratingbuys_computeryouthhighnofairnoyouthhighnoexcellentnomiddle_agedhighnofairyesseniormediumnofairyesseniorlowyesfairyesseniorlowyesexcellentnomiddle_agedlowyesexcellentyesyouthmediumnofairnoyouthlowyesfairyesseniormediumyesfairyesyouthmediumye

12、sexcellentyesmiddle_agedmediumnoexcellentyesmiddle_agedhighyesfairyesseniormediumnoexcellentno斷定歸納樹算法例如 (1)n對于上述數(shù)據(jù)，可以略過步驟1，2n步驟3，計算基于熵的度量信息增益，作為樣本劃分的根據(jù)nGain(age)=0.246nGain(income)=0.029nGain(student)=0.151nGain(credit_rating)=0.048n然后，對測試屬性每個知的值，創(chuàng)建一個分支，并以此劃分樣本，得到第一次劃分?jǐn)喽w納樹算法例如 (2)斷定歸納樹算法例如 (3)age?o

13、vercaststudent?credit rating?noyesfairexcellentyouthseniornonoyesyesyesMiddle aged防止分類中的過分順應(yīng)n產(chǎn)生的決策樹會出現(xiàn)過分順應(yīng)數(shù)據(jù)的問題n由于數(shù)據(jù)中的噪聲和孤立點，許多分枝反響的是訓(xùn)練數(shù)據(jù)中的異常n對新樣本的斷定很不準(zhǔn)確n防止過分順應(yīng)的兩種方法n先剪枝：經(jīng)過提早停頓樹的構(gòu)造假設(shè)在一個節(jié)點劃分樣本將導(dǎo)致低于預(yù)定義臨界值的分裂e.g. 運用信息增益度量n選擇一個適宜的臨界值往往很困難n后剪枝：由“完全生長的樹剪去分枝對于樹中的每個非樹葉節(jié)點，計算該節(jié)點上的子樹被剪枝能夠出現(xiàn)的期望錯誤率n運用一個獨立的測試集來評價

14、每顆樹的準(zhǔn)確率，就能得到具有最小期望錯誤率的決策樹由決策樹提取分類規(guī)那么n可以提取決策樹表示的知識，并以IF-THEN方式的分類規(guī)那么表示n對從根到樹葉的每條途徑創(chuàng)建一個規(guī)那么n沿著給定途徑上的每個屬性-值對構(gòu)成規(guī)那么前件IF部分的一個合取項n葉節(jié)點包含類預(yù)測，構(gòu)成規(guī)那么后件THEN部分nIF-THEN規(guī)那么易于了解，尤其樹很大時n例如：nIF age = “youth AND student = “no THEN buys_computer = “nonIF age = “youth AND student = “yes THEN buys_computer = “yesnIF age =

15、“middle_aged THEN buys_computer = “yesnIF age = “senior AND credit_rating = “excellent THEN buys_computer = “yesnIF age = “senior AND credit_rating = “fair THEN buys_computer = “no可伸縮性與決策歸納樹n分類發(fā)掘是一個在統(tǒng)計學(xué)和機(jī)器學(xué)習(xí)的領(lǐng)域也被廣為研討的問題，并提出了很多算法，但是這些算法都是內(nèi)存駐留的n可伸縮性問題：要求以合理的速度對數(shù)以百萬計的樣本和數(shù)以百計的屬性的進(jìn)展分類發(fā)掘n由大型數(shù)據(jù)庫構(gòu)造決策樹n首先將樣本

16、劃分為子集，每個子集可以放在內(nèi)存中n然后由每個本人構(gòu)造一顆決策樹n輸出的分類法將每個子集的分類法組合在一同n其他方法包括SLIQ, SPRINT,RainForest等等貝葉斯分類n貝葉斯分類利用統(tǒng)計學(xué)中的貝葉斯定理，來預(yù)測類成員的概率，即給定一個樣本，計算該樣本屬于一個特定的類的概率。n樸素貝葉斯分類：假設(shè)每個屬性之間都是相互獨立的，并且每個屬性對非類問題產(chǎn)生的影響都是一樣的。)()()|()|(DPhPhDPDhP后向傳播分類n后向傳播是一種神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法；神經(jīng)網(wǎng)絡(luò)是一組銜接的輸入/輸出單元，每個銜接都與一個權(quán)相連。在學(xué)習(xí)階段，經(jīng)過調(diào)整神經(jīng)網(wǎng)絡(luò)的權(quán)，使得可以預(yù)測輸入樣本的正確標(biāo)號來學(xué)習(xí)。

17、n優(yōu)點n預(yù)測精度總的來說較高n強(qiáng)壯性好，訓(xùn)練樣本中包含錯誤時也可正常任務(wù)n輸出能夠是離散值、延續(xù)值或者是離散或量化屬性的向量值n對目的進(jìn)展分類較快n缺陷n訓(xùn)練學(xué)習(xí)時間長n蘊涵在學(xué)習(xí)的權(quán)中的符號含義很難了解n很難根專業(yè)領(lǐng)域知識相整合SVM支持向量機(jī)n運用一種非線性的映射，將原訓(xùn)練數(shù)據(jù)映射到較高的維n一個數(shù)據(jù)被以為是p維向量，數(shù)據(jù)在這個p維向量空間中被分為兩類；SVM的目的是找到一個p-1維的超平面，來劃分p維向量空間的數(shù)據(jù)n在新的維上，它搜索線性最正確分別超平面 (即將一類的元組與其他類分別的“決策邊境)。n運用一個適當(dāng)?shù)膶ψ銐蚋呔S的非線性映射，兩類的數(shù)據(jù)總可以被超平面分開。nSVM 運用支持向

18、量“根本訓(xùn)練元組和邊緣由支持向量定義發(fā)現(xiàn)該超平面。SVM-特點和運用n特點: 訓(xùn)練時間非常長，但對復(fù)雜的非線性決策邊境的建模才干是高度準(zhǔn)確的運用最大邊緣n可以用來預(yù)測和分類n運用: n手寫數(shù)字識別，對象識別，語音識別, 以及基準(zhǔn)時間序列預(yù)測檢驗SVM普通原理支持向量小邊緣大邊緣November 25, 2021Data Mining: Concepts and Techniques31SVM當(dāng)數(shù)據(jù)是線性可分的時候m設(shè)給定的數(shù)據(jù)集 D 為 (X1, y1), , (X|D|, y|D|), 其中Xi是訓(xùn)練元組，具有相關(guān)聯(lián)的類標(biāo)號yi。可以畫出無限多條分別直線或超平面將類+1的元組與類-1的元組分

19、開，我們想找出“最好的那一條 (對先前未見到的元組具有最小分類誤差的那一條。SVM 要搜索具有最大邊緣的超平面，即最大邊緣超平面 (MMH)其他分類方法nk-最臨近分類n給定一個未知樣本，k-最臨近分類法搜索方式空間，找出最接近未知樣本的k個訓(xùn)練樣本；然后運用k個最臨近者中最公共的類來預(yù)測當(dāng)前樣本的類標(biāo)號n基于案例的推理n樣本或案例運用復(fù)雜的符號表示，對于新案例，先檢測能否存在同樣的訓(xùn)練案例；假設(shè)找不到，那么搜索類似的訓(xùn)練案例n遺傳算法n結(jié)合生物進(jìn)化思想的算法n粗糙集方法n模糊集方法n允許在分類規(guī)那么中定義“模糊的臨界值或邊境什么是預(yù)測？n預(yù)測是構(gòu)造和運用模型評價無樣本類，或評價給定樣本能夠具有的屬性或值空間。n預(yù)測和分類的異同n一樣點n兩者都需求構(gòu)建模型n都用模型來估計未知值n預(yù)測當(dāng)中主要的估計方法是回歸分析n線性回歸和多元回歸n非線性回歸n不同點n分類法主要是用來預(yù)測類標(biāo)號分類屬性值n預(yù)測法主要是用來估計延續(xù)值量化屬性值線性回歸、多元回歸和非線性回歸n線性回