《數(shù)據(jù)挖掘》課程PPT_分類和預(yù)測

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

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

3、被模型分類的測試樣本的百分比n測試集要獨(dú)立于訓(xùn)練樣本集，否則會(huì)出現(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 TENUREDTomAss

4、istant Prof2noMerlisa 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í)（用于分類）q模型的學(xué)習(xí)在被告知每個(gè)訓(xùn)練樣本屬于哪個(gè)類的“指導(dǎo)”下進(jìn)行q新數(shù)據(jù)使用訓(xùn)練數(shù)據(jù)集中得到的規(guī)則進(jìn)行分類n無監(jiān)督學(xué)習(xí)（用于聚類）q每個(gè)訓(xùn)練樣本的類編號是未知的，要學(xué)習(xí)的類集合或數(shù)量也可能是事先未知的q通過一系列的度量、觀察來建立數(shù)據(jù)中的類編號或進(jìn)行聚類數(shù)據(jù)預(yù)測的兩步過程n數(shù)據(jù)預(yù)測也是一個(gè)兩步的過程，類似于前面描述的數(shù)據(jù)分

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

6、換，將所給屬性的所有值按比例進(jìn)行縮放，使其落入一個(gè)較小的指定區(qū)間，例 0.0, 1.0（ANN和設(shè)計(jì)距離的度量方法中常用）n可以將數(shù)據(jù)概化到較高層概念比較分類方法n使用下列標(biāo)準(zhǔn)比較分類和預(yù)測方法q預(yù)測的準(zhǔn)確率：模型正確預(yù)測新數(shù)據(jù)的類編號的能力q速度：產(chǎn)生和使用模型的計(jì)算花銷q健壯性：給定噪聲數(shù)據(jù)或有空缺值的數(shù)據(jù)，模型正確預(yù)測的能力q可伸縮性：對大量數(shù)據(jù)，有效的構(gòu)建分類器或預(yù)測可伸縮性：對大量數(shù)據(jù)，有效的構(gòu)建分類器或預(yù)測器的能力器的能力q可解釋性：學(xué)習(xí)模型提供的理解和洞察的層次用決策樹歸納分類 (1)n什么是決策樹？q類似于流程圖的樹結(jié)構(gòu)q每個(gè)內(nèi)部節(jié)點(diǎn)表示在一個(gè)屬性上的測試q每個(gè)分枝代表一個(gè)測試

7、輸出q每個(gè)樹葉節(jié)點(diǎn)存放一個(gè)類編號age?student?credit rating?noyesfairexcellentyouthseniornonoyesyesyesMiddleaged決策樹：決策樹：Buys_computer用決策樹歸納分類 (2)n使用決策樹分類q給定一個(gè)類標(biāo)號未知的元組X，在決策樹上測試元組的屬性值，跟蹤一條由根到葉節(jié)點(diǎn)的路徑，葉節(jié)點(diǎn)存放該元組的類預(yù)測。q決策樹容易轉(zhuǎn)換為分類規(guī)則n決策樹的生成由兩個(gè)階段組成q決策樹構(gòu)建n使用屬性選擇度量來選擇將元組最好的劃分為不同的類的屬性n遞歸的通過選定的屬性，來劃分樣本 （必須是離散值）q樹剪枝n決策樹建立時(shí)，許多分枝反映的是訓(xùn)練

8、數(shù)據(jù)中的噪聲和離群點(diǎn)點(diǎn)，樹剪枝試圖識別并剪去這種分枝，以提高對未知數(shù)據(jù)分類的準(zhǔn)確性決策樹歸納策略 (1)n輸入q數(shù)據(jù)劃分D是訓(xùn)練元組和對應(yīng)類標(biāo)號的集合qattribute_list,候選屬性的集合qAttribute_selection_method，指定選擇屬性的啟發(fā)性過程算法步驟1.樹以代表訓(xùn)練樣本的單個(gè)節(jié)點(diǎn)（N）開始2.如果樣本都在同一個(gè)類，則該節(jié)點(diǎn)成為樹葉，并用該類標(biāo)記3.否則，算法調(diào)用Attribute_selection_method，選擇能夠最好的將樣本分類的屬性；確定“分裂準(zhǔn)則”，指出“分裂點(diǎn)”或“分裂子集”。決策樹歸納策略 (2)4.對測試屬性每個(gè)已知的值，創(chuàng)建一個(gè)分支，并以

9、此劃分元組5.算法使用同樣的過程，遞歸的形成每個(gè)劃分上的元組決策樹。一旦一個(gè)屬性出現(xiàn)在一個(gè)節(jié)點(diǎn)上，就不在該節(jié)點(diǎn)的任何子節(jié)點(diǎn)上出現(xiàn)6.遞歸劃分步驟停止的條件劃分D（在N節(jié)點(diǎn)提供）的所有元組屬于同一類沒有剩余屬性可以用來進(jìn)一步劃分元組使用多數(shù)表決沒有剩余的樣本給定分支沒有元組，則以D中多數(shù)類創(chuàng)建一個(gè)樹葉屬性選擇度量n屬性選擇度量是一種選擇分裂準(zhǔn)則，將給定類標(biāo)號的訓(xùn)練元組最好的進(jìn)行劃分的方法q理想情況，每個(gè)劃分都是“純”的，即落在給定劃分內(nèi)的元組都屬于相同的類q屬性選擇度量又稱為分裂準(zhǔn)則n常用的屬性選擇度量q信息增益q增益率qGini指標(biāo)信息增益 (1)nS是一個(gè)訓(xùn)練樣本訓(xùn)練樣本的集合，該樣本中每個(gè)

10、集合的類編號類編號已知。每個(gè)樣本為一個(gè)元組元組。有個(gè)屬性用來判定某個(gè)訓(xùn)練樣本的類編號n假設(shè)S中有m個(gè)類，總共s個(gè)訓(xùn)練樣本，每個(gè)類Ci有si個(gè)樣本(i1,2,3.m)，那么任意一個(gè)樣本屬于類Ci的概率是si / s，那么用來分類一個(gè)給定樣本的期望信息期望信息是：sssssssInfoimiim2121log),.,(信息增益 (2)n一個(gè)有v個(gè)值的屬性Aa1,a2,.,av可以將S分成v個(gè)子集S1,S2,.,Sv，其中Sj包含S中屬性A上的值為aj的樣本。假設(shè)Sj包含類Ci的sij個(gè)樣本。根據(jù)A的這種劃分的期望信息稱為A的熵熵nA上該劃分的獲得的信息增益定義為：n具有高信息增益的屬性，是給定集合

11、中具有高區(qū)分度的屬性。所以可以通過計(jì)算S中樣本的每個(gè)屬性的信息增益，來得到一個(gè)屬性的相關(guān)性的排序。),.,(.)(111mjjvjmjjssIsssAE)(),.,()(21AEsssIAGainmageincomestudentcredit_ratingbuys_computeryouthhighnofairnoyouthhighnoexcellentnomiddle_agedhighnofairyesseniormediumnofairyesseniorlowyesfairyesseniorlowyesexcellentnomiddle_agedlowyesexcellentyesyout

12、hmediumnofairnoyouthlowyesfairyesseniormediumyesfairyesyouthmediumyesexcellentyesmiddle_agedmediumnoexcellentyesmiddle_agedhighyesfairyesseniormediumnoexcellentno判定歸納樹算法示例 (1)n對于上述數(shù)據(jù)，可以略過步驟1，2n步驟3，計(jì)算基于熵的度量信息增益，作為樣本劃分的根據(jù)qGain(age)=0.246qGain(income)=0.029qGain(student)=0.151qGain(credit_rating)=0.048

13、n然后，對測試屬性每個(gè)已知的值，創(chuàng)建一個(gè)分支，并以此劃分樣本，得到第一次劃分判定歸納樹算法示例 (2)判定歸納樹算法示例 (3)age?overcaststudent?credit rating?noyesfairexcellentyouthseniornonoyesyesyesMiddle aged防止分類中的過分適應(yīng)n產(chǎn)生的決策樹會(huì)出現(xiàn)過分適應(yīng)數(shù)據(jù)的問題q由于數(shù)據(jù)中的噪聲和孤立點(diǎn)，許多分枝反應(yīng)的是訓(xùn)練數(shù)據(jù)中的異常q對新樣本的判定很不精確n防止過分適應(yīng)的兩種方法q先剪枝：通過提前停止樹的構(gòu)造如果在一個(gè)節(jié)點(diǎn)劃分樣本將導(dǎo)致低于預(yù)定義臨界值的分裂（e.g. 使用信息增益度量）n選擇一個(gè)合適的臨界值

14、往往很困難q后剪枝：由“完全生長”的樹剪去分枝對于樹中的每個(gè)非樹葉節(jié)點(diǎn)，計(jì)算該節(jié)點(diǎn)上的子樹被剪枝可能出現(xiàn)的期望錯(cuò)誤率n使用一個(gè)獨(dú)立的測試集來評估每顆樹的準(zhǔn)確率，就能得到具有最小期望錯(cuò)誤率的決策樹由決策樹提取分類規(guī)則n可以提取決策樹表示的知識，并以IF-THEN形式的分類規(guī)則表示n對從根到樹葉的每條路徑創(chuàng)建一個(gè)規(guī)則n沿著給定路徑上的每個(gè)屬性-值對形成規(guī)則前件（IF部分）的一個(gè)合取項(xiàng)n葉節(jié)點(diǎn)包含類預(yù)測，形成規(guī)則后件（THEN部分）nIF-THEN規(guī)則易于理解，尤其樹很大時(shí)n示例：nIF age = “youth” AND student = “no” THEN buys_computer = “n

15、o”nIF age = “youth” AND student = “yes” THEN buys_computer = “yes”nIF age = “middle_aged” THEN buys_computer = “yes”nIF age = “senior” AND credit_rating = “excellent” THEN buys_computer = “yes”nIF age = “senior” AND credit_rating = “fair” THEN buys_computer = “no”可伸縮性與決策歸納樹n分類挖掘是一個(gè)在統(tǒng)計(jì)學(xué)和機(jī)器學(xué)習(xí)的領(lǐng)域也被廣為研究

16、的問題，并提出了很多算法，但是這些算法都是內(nèi)存駐留的n可伸縮性問題：要求以合理的速度對數(shù)以百萬要求以合理的速度對數(shù)以百萬計(jì)的樣本和數(shù)以百計(jì)的屬性的進(jìn)行分類挖掘計(jì)的樣本和數(shù)以百計(jì)的屬性的進(jìn)行分類挖掘n由大型數(shù)據(jù)庫構(gòu)造決策樹q首先將樣本劃分為子集，每個(gè)子集可以放在內(nèi)存中q然后由每個(gè)自己構(gòu)造一顆決策樹q輸出的分類法將每個(gè)子集的分類法組合在一起q（其他方法包括SLIQ, SPRINT,RainForest等等）貝葉斯分類n貝葉斯分類利用統(tǒng)計(jì)學(xué)中的貝葉斯定理，來預(yù)測類成員的概率，即給定一個(gè)樣本，計(jì)算該樣本屬于一個(gè)特定的類的概率。n樸素貝葉斯分類：假設(shè)每個(gè)屬性之間都是相互獨(dú)立的，并且每個(gè)屬性對非類問題產(chǎn)生

17、的影響都是一樣的。)()()|()|(DPhPhDPDhP后向傳播分類n后向傳播是一種神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法；神經(jīng)網(wǎng)絡(luò)是一組連接的輸入/輸出單元，每個(gè)連接都與一個(gè)權(quán)相連。在學(xué)習(xí)階段，通過調(diào)整神經(jīng)網(wǎng)絡(luò)的權(quán)，使得能夠預(yù)測輸入樣本的正確標(biāo)號來學(xué)習(xí)。n優(yōu)點(diǎn)q預(yù)測精度總的來說較高q健壯性好，訓(xùn)練樣本中包含錯(cuò)誤時(shí)也可正常工作q輸出可能是離散值、連續(xù)值或者是離散或量化屬性的向量值q對目標(biāo)進(jìn)行分類較快n缺點(diǎn)q訓(xùn)練（學(xué)習(xí)）時(shí)間長q蘊(yùn)涵在學(xué)習(xí)的權(quán)中的符號含義很難理解q很難根專業(yè)領(lǐng)域知識相整合SVM支持向量機(jī)n使用一種非線性的映射，將原訓(xùn)練數(shù)據(jù)映射到較高的維n一個(gè)數(shù)據(jù)被認(rèn)為是p維向量，數(shù)據(jù)在這個(gè)p維向量空間中被分為兩類；

18、SVM的目的是找到一個(gè)p-1維的超平面，來劃分p維向量空間的數(shù)據(jù)q在新的維上，它搜索線性最佳分離超平面 (即將一類的元組與其他類分離的“決策邊界”)。n使用一個(gè)適當(dāng)?shù)膶ψ銐蚋呔S的非線性映射，兩類的數(shù)據(jù)總可以被超平面分開。nSVM 使用支持向量（“基本”訓(xùn)練元組）和邊緣（由支持向量定義）發(fā)現(xiàn)該超平面。SVM-特點(diǎn)和應(yīng)用n特點(diǎn): 訓(xùn)練時(shí)間非常長，但對復(fù)雜的非線性決策邊界的建模能力是高度準(zhǔn)確的（使用最大邊緣）q可以用來預(yù)測和分類n應(yīng)用: q手寫數(shù)字識別，對象識別，語音識別, 以及基準(zhǔn)時(shí)間序列預(yù)測檢驗(yàn)SVM一般原理支持向量小邊緣大邊緣April 4, 2022Data Mining: Concepts

19、 and Techniques31SVM當(dāng)數(shù)據(jù)是線性可分的時(shí)候m設(shè)給定的數(shù)據(jù)集 D 為 (X1, y1), , (X|D|, y|D|), 其中Xi是訓(xùn)練元組，具有相關(guān)聯(lián)的類標(biāo)號yi?？梢援嫵鰺o限多條分離直線（或超平面）將類+1的元組與類-1的元組分開，我們想找出“最好的”那一條 (對先前未見到的元組具有最小分類誤差的那一條）。SVM 要搜索具有最大邊緣的超平面，即最大邊緣超平面最大邊緣超平面 (MMH)其他分類方法nk-最臨近分類q給定一個(gè)未知樣本，k-最臨近分類法搜索模式空間，找出最接近未知樣本的k個(gè)訓(xùn)練樣本；然后使用k個(gè)最臨近者中最公共的類來預(yù)測當(dāng)前樣本的類標(biāo)號n基于案例的推理q樣本或案例使用復(fù)雜的符號表示，對于新案例，先檢測是否存在同樣的訓(xùn)練案例；如果找不到，則搜索類似的訓(xùn)練案例n遺傳算法q結(jié)合生物進(jìn)化思想的算法n粗糙集方法n模糊集方法q允許在分類規(guī)則中定義“模糊的”臨界值或邊界什么是預(yù)測？n預(yù)測是構(gòu)造和使用模型評估無樣本類，或評估給定樣本可能具有的屬性或值空間。n預(yù)測和分類的異同n相同點(diǎn)q兩者都需要構(gòu)建模型q都用模型來估計(jì)未知值n預(yù)測當(dāng)中主要的估計(jì)方法是回歸分析q線性回歸和多元回歸q非線性回歸n不同點(diǎn)q分類法主要是用來預(yù)測類標(biāo)號（分類屬性值）q預(yù)測法主要是用來估計(jì)連續(xù)值（量化屬性值）線性回歸、多元回歸和