數(shù)據(jù)挖掘分類和預(yù)測

數(shù)據(jù)挖掘分類和預(yù)測第一頁，共三十六頁，編輯于2023年，星期六分類VS.預(yù)測分類和預(yù)測是兩種數(shù)據(jù)分析形式，用于提取描述重要數(shù)據(jù)類或預(yù)測未來的數(shù)據(jù)趨勢的模型分類：預(yù)測類對象的分類標號（或離散值）根據(jù)訓練數(shù)據(jù)集和類標號屬性，構(gòu)建模型來分類現(xiàn)有數(shù)據(jù)，并用來分類新數(shù)據(jù)預(yù)測：建立連續(xù)函數(shù)值模型比如預(yù)測空缺值，或者預(yù)測顧客在計算機設(shè)備上的花費典型應(yīng)用欺詐檢測、市場定位、性能預(yù)測、醫(yī)療診斷第二頁，共三十六頁，編輯于2023年，星期六分類和預(yù)測---示例分類銀行貸款員需要分析數(shù)據(jù)，來弄清哪些貸款申請者是安全的，哪些是有風險的（將貸款申請者分為“安全”和“有風險”兩類）我們需要構(gòu)造一個分類器來預(yù)測類屬編號，比如預(yù)測顧客屬類預(yù)測銀行貸款員需要預(yù)測貸給某個顧客多少錢是安全的構(gòu)造一個預(yù)測器，預(yù)測一個連續(xù)值函數(shù)或有序值，常用方法是回歸分析第三頁，共三十六頁，編輯于2023年，星期六數(shù)據(jù)分類——一個兩步過程(1)第一步，也成為學習步，目標是建立描述預(yù)先定義的數(shù)據(jù)類或概念集的分類器分類算法通過分析或從訓練集“學習”來構(gòu)造分類器。訓練集由數(shù)據(jù)庫元組（用n維屬性向量表示）和他們相對應(yīng)的類編號組成；假定每個元組屬于一個預(yù)定義的類訓練元組：訓練數(shù)據(jù)集中的單個元組學習模型可以用分類規(guī)則、決策樹或數(shù)學公式的形式提供第四頁，共三十六頁，編輯于2023年，星期六數(shù)據(jù)分類——一個兩步過程(2)第二步，使用模型，對將來的或未知的對象進行分類首先評估模型的預(yù)測準確率對每個測試樣本，將已知的類標號和該樣本的學習模型類預(yù)測比較模型在給定測試集上的準確率是正確被模型分類的測試樣本的百分比測試集要獨立于訓練樣本集，否則會出現(xiàn)“過分擬合”的情況第五頁，共三十六頁，編輯于2023年，星期六第一步——建立模型訓練數(shù)據(jù)集分類算法IFrank=‘professor’ORyears>6THENtenured=‘yes’分類規(guī)則第六頁，共三十六頁，編輯于2023年，星期六第二步——用模型進行分類分類規(guī)則測試集未知數(shù)據(jù)(Jeff,Professor,4)Tenured?第七頁，共三十六頁，編輯于2023年，星期六監(jiān)督學習VS.無監(jiān)督學習監(jiān)督學習（用于分類）模型的學習在被告知每個訓練樣本屬于哪個類的“指導(dǎo)”下進行新數(shù)據(jù)使用訓練數(shù)據(jù)集中得到的規(guī)則進行分類無監(jiān)督學習（用于聚類）每個訓練樣本的類編號是未知的，要學習的類集合或數(shù)量也可能是事先未知的通過一系列的度量、觀察來建立數(shù)據(jù)中的類編號或進行聚類第八頁，共三十六頁，編輯于2023年，星期六數(shù)據(jù)預(yù)測的兩步過程數(shù)據(jù)預(yù)測也是一個兩步的過程，類似于前面描述的數(shù)據(jù)分類對于預(yù)測，沒有“類標號屬性”要預(yù)測的屬性是連續(xù)值，而不是離散值，該屬性可簡稱“預(yù)測屬性”E.g.銀行貸款員需要預(yù)測貸給某個顧客多少錢是安全的預(yù)測器可以看作一個映射或函數(shù)y=f(X)其中X是輸入；y是輸出，是一個連續(xù)或有序的值與分類類似，準確率的預(yù)測，也要使用單獨的測試集第九頁，共三十六頁，編輯于2023年，星期六準備分類和預(yù)測的數(shù)據(jù)通過對數(shù)據(jù)進行預(yù)處理，可以提高分類和預(yù)測過程的準確性、有效性和可伸縮性數(shù)據(jù)清理消除或減少噪聲，處理空缺值，從而減少學習時的混亂相關(guān)分析數(shù)據(jù)中的有些屬性可能與當前任務(wù)不相關(guān)；也有些屬性可能是冗余的；刪除這些屬性可以加快學習步驟，使學習結(jié)果更精確數(shù)據(jù)變換與歸約數(shù)據(jù)可以通過規(guī)范化進行變換，將所給屬性的所有值按比例進行縮放，使其落入一個較小的指定區(qū)間，例[0.0,1.0]（ANN和設(shè)計距離的度量方法中常用）可以將數(shù)據(jù)概化到較高層概念第十頁，共三十六頁，編輯于2023年，星期六比較分類方法使用下列標準比較分類和預(yù)測方法預(yù)測的準確率：模型正確預(yù)測新數(shù)據(jù)的類編號的能力速度：產(chǎn)生和使用模型的計算花銷健壯性：給定噪聲數(shù)據(jù)或有空缺值的數(shù)據(jù)，模型正確預(yù)測的能力可伸縮性：對大量數(shù)據(jù)，有效的構(gòu)建分類器或預(yù)測器的能力可解釋性：學習模型提供的理解和洞察的層次第十一頁，共三十六頁，編輯于2023年，星期六用決策樹歸納分類(1)什么是決策樹？類似于流程圖的樹結(jié)構(gòu)每個內(nèi)部節(jié)點表示在一個屬性上的測試每個分枝代表一個測試輸出每個樹葉節(jié)點存放一個類編號age?student?creditrating?noyesfairexcellentyouthseniornonoyesyesyesMiddleaged決策樹：Buys_computer第十二頁，共三十六頁，編輯于2023年，星期六用決策樹歸納分類(2)使用決策樹分類給定一個類標號未知的元組X，在決策樹上測試元組的屬性值，跟蹤一條由根到葉節(jié)點的路徑，葉節(jié)點存放該元組的類預(yù)測。決策樹容易轉(zhuǎn)換為分類規(guī)則決策樹的生成由兩個階段組成決策樹構(gòu)建使用屬性選擇度量來選擇將元組最好的劃分為不同的類的屬性遞歸的通過選定的屬性，來劃分樣本（必須是離散值）樹剪枝決策樹建立時，許多分枝反映的是訓練數(shù)據(jù)中的噪聲和離群點點，樹剪枝試圖識別并剪去這種分枝，以提高對未知數(shù)據(jù)分類的準確性第十三頁，共三十六頁，編輯于2023年，星期六決策樹歸納策略(1)輸入數(shù)據(jù)劃分D是訓練元組和對應(yīng)類標號的集合attribute_list,候選屬性的集合Attribute_selection_method，指定選擇屬性的啟發(fā)性過程算法步驟樹以代表訓練樣本的單個節(jié)點（N）開始如果樣本都在同一個類，則該節(jié)點成為樹葉，并用該類標記否則，算法調(diào)用Attribute_selection_method，選擇能夠最好的將樣本分類的屬性；確定“分裂準則”，指出“分裂點”或“分裂子集”。第十四頁，共三十六頁，編輯于2023年，星期六決策樹歸納策略(2)對測試屬性每個已知的值，創(chuàng)建一個分支，并以此劃分元組算法使用同樣的過程，遞歸的形成每個劃分上的元組決策樹。一旦一個屬性出現(xiàn)在一個節(jié)點上，就不在該節(jié)點的任何子節(jié)點上出現(xiàn)遞歸劃分步驟停止的條件劃分D（在N節(jié)點提供）的所有元組屬于同一類沒有剩余屬性可以用來進一步劃分元組——使用多數(shù)表決沒有剩余的樣本給定分支沒有元組，則以D中多數(shù)類創(chuàng)建一個樹葉第十五頁，共三十六頁，編輯于2023年，星期六屬性選擇度量屬性選擇度量是一種選擇分裂準則，將給定類標號的訓練元組最好的進行劃分的方法理想情況，每個劃分都是“純”的，即落在給定劃分內(nèi)的元組都屬于相同的類屬性選擇度量又稱為分裂準則常用的屬性選擇度量信息增益增益率Gini指標第十六頁，共三十六頁，編輯于2023年，星期六信息增益(1)S是一個訓練樣本的集合，該樣本中每個集合的類編號已知。每個樣本為一個元組。有個屬性用來判定某個訓練樣本的類編號假設(shè)S中有m個類，總共s個訓練樣本，每個類Ci有si個樣本(i＝1,2,3...m)，那么任意一個樣本屬于類Ci的概率是si/s，那么用來分類一個給定樣本的期望信息是：第十七頁，共三十六頁，編輯于2023年，星期六信息增益(2)一個有v個值的屬性A{a1,a2,...,av}可以將S分成v個子集{S1,S2,...,Sv}，其中Sj包含S中屬性A上的值為aj的樣本。假設(shè)Sj包含類Ci的sij個樣本。根據(jù)A的這種劃分的期望信息稱為A的熵A上該劃分的獲得的信息增益定義為：具有高信息增益的屬性，是給定集合中具有高區(qū)分度的屬性。所以可以通過計算S中樣本的每個屬性的信息增益，來得到一個屬性的相關(guān)性的排序。第十八頁，共三十六頁，編輯于2023年，星期六ageincomestudentcredit_ratingbuys_computeryouthhighnofairnoyouthhighnoexcellentnomiddle_agedhighnofairyesseniormediumnofairyesseniorlowyesfairyesseniorlowyesexcellentnomiddle_agedlowyesexcellentyesyouthmediumnofairnoyouthlowyesfairyesseniormediumyesfairyesyouthmediumyesexcellentyesmiddle_agedmediumnoexcellentyesmiddle_agedhighyesfairyesseniormediumnoexcellentno第十九頁，共三十六頁，編輯于2023年，星期六判定歸納樹算法示例(1)對于上述數(shù)據(jù)，可以略過步驟1，2步驟3，計算基于熵的度量——信息增益，作為樣本劃分的根據(jù)Gain(age)=0.246Gain(income)=0.029Gain(student)=0.151Gain(credit_rating)=0.048然后，對測試屬性每個已知的值，創(chuàng)建一個分支，并以此劃分樣本，得到第一次劃分第二十頁，共三十六頁，編輯于2023年，星期六判定歸納樹算法示例(2)第二十一頁，共三十六頁，編輯于2023年，星期六判定歸納樹算法示例(3)age?overcaststudent?creditrating?noyesfairexcellentyouthseniornonoyesyesyesMiddleaged第二十二頁，共三十六頁，編輯于2023年，星期六防止分類中的過分適應(yīng)產(chǎn)生的決策樹會出現(xiàn)過分適應(yīng)數(shù)據(jù)的問題由于數(shù)據(jù)中的噪聲和孤立點，許多分枝反應(yīng)的是訓練數(shù)據(jù)中的異常對新樣本的判定很不精確防止過分適應(yīng)的兩種方法先剪枝：通過提前停止樹的構(gòu)造——如果在一個節(jié)點劃分樣本將導(dǎo)致低于預(yù)定義臨界值的分裂（e.g.使用信息增益度量）選擇一個合適的臨界值往往很困難后剪枝：由“完全生長”的樹剪去分枝——對于樹中的每個非樹葉節(jié)點，計算該節(jié)點上的子樹被剪枝可能出現(xiàn)的期望錯誤率使用一個獨立的測試集來評估每顆樹的準確率，就能得到具有最小期望錯誤率的決策樹第二十三頁，共三十六頁，編輯于2023年，星期六由決策樹提取分類規(guī)則可以提取決策樹表示的知識，并以IF-THEN形式的分類規(guī)則表示對從根到樹葉的每條路徑創(chuàng)建一個規(guī)則沿著給定路徑上的每個屬性-值對形成規(guī)則前件（"IF"部分）的一個合取項葉節(jié)點包含類預(yù)測，形成規(guī)則后件（"THEN"部分）IF-THEN規(guī)則易于理解，尤其樹很大時示例：IFage=“youth”ANDstudent=“no”THENbuys_computer=“no”IFage=“youth”ANDstudent=“yes”THENbuys_computer=“yes”IFage=“middle_aged”THENbuys_computer=“yes”IFage=“senior”ANDcredit_rating=“excellent”THENbuys_computer=“yes”IFage=“senior”ANDcredit_rating=“fair”THENbuys_computer=“no”第二十四頁，共三十六頁，編輯于2023年，星期六可伸縮性與決策歸納樹分類挖掘是一個在統(tǒng)計學和機器學習的領(lǐng)域也被廣為研究的問題，并提出了很多算法，但是這些算法都是內(nèi)存駐留的可伸縮性問題：要求以合理的速度對數(shù)以百萬計的樣本和數(shù)以百計的屬性的進行分類挖掘由大型數(shù)據(jù)庫構(gòu)造決策樹首先將樣本劃分為子集，每個子集可以放在內(nèi)存中然后由每個自己構(gòu)造一顆決策樹輸出的分類法將每個子集的分類法組合在一起（其他方法包括SLIQ,SPRINT,RainForest等等）第二十五頁，共三十六頁，編輯于2023年，星期六貝葉斯分類貝葉斯分類利用統(tǒng)計學中的貝葉斯定理，來預(yù)測類成員的概率，即給定一個樣本，計算該樣本屬于一個特定的類的概率。樸素貝葉斯分類：假設(shè)每個屬性之間都是相互獨立的，并且每個屬性對非類問題產(chǎn)生的影響都是一樣的。第二十六頁，共三十六頁，編輯于2023年，星期六后向傳播分類后向傳播是一種神經(jīng)網(wǎng)絡(luò)學習算法；神經(jīng)網(wǎng)絡(luò)是一組連接的輸入/輸出單元，每個連接都與一個權(quán)相連。在學習階段，通過調(diào)整神經(jīng)網(wǎng)絡(luò)的權(quán)，使得能夠預(yù)測輸入樣本的正確標號來學習。優(yōu)點預(yù)測精度總的來說較高健壯性好，訓練樣本中包含錯誤時也可正常工作輸出可能是離散值、連續(xù)值或者是離散或量化屬性的向量值對目標進行分類較快缺點訓練（學習）時間長蘊涵在學習的權(quán)中的符號含義很難理解很難根專業(yè)領(lǐng)域知識相整合第二十七頁，共三十六頁，編輯于2023年，星期六SVM—支持向量機使用一種非線性的映射，將原訓練數(shù)據(jù)映射到較高的維一個數(shù)據(jù)被認為是p維向量，數(shù)據(jù)在這個p維向量空間中被分為兩類；SVM的目的是找到一個p-1維的超平面，來劃分p維向量空間的數(shù)據(jù)在新的維上，它搜索線性最佳分離超平面(即將一類的元組與其他類分離的“決策邊界”)。使用一個適當?shù)膶ψ銐蚋呔S的非線性映射，兩類的數(shù)據(jù)總可以被超平面分開。SVM使用支持向量（“基本”訓練元組）和邊緣（由支持向量定義）發(fā)現(xiàn)該超平面。第二十八頁，共三十六頁，編輯于2023年，星期六SVM---特點和應(yīng)用特點:訓練時間非常長，但對復(fù)雜的非線性決策邊界的建模能力是高度準確的（使用最大邊緣）可以用來預(yù)測和分類應(yīng)用:手寫數(shù)字識別，對象識別，語音識別,以及基準時間序列預(yù)測檢驗第二十九頁，共三十六頁，編輯于2023年，星期六SVM—一般原理支持向量小邊緣大邊緣第三十頁，共三十六頁，編輯于2023年，星期六31May2023DataMining:ConceptsandTechniques31SVM—當數(shù)據(jù)是線性可分的時候m設(shè)給定的數(shù)據(jù)集D為(X1,y1),…,(X|D|,y|D|),其中Xi是訓練元組，具有相關(guān)聯(lián)的類標號yi。可以畫出無限多條分離直線（或超平面）將類+1的元組與類-1的元組分開，我們想找出“最好的”那一條(對先前未見到的元組具有最小分類誤差的那一條）。SVM要搜索具有最大邊緣的超平面，即最大邊緣超平面(MMH)第三十一頁，共三十六頁，編輯于2023年，星期六其他分類方法k-最臨近分類給定一個未知樣本，k-最臨近分類法搜索模式空間，找出最接近未知樣本的k個訓練樣本；然后使用k個最臨近者中最公共的類來預(yù)測當前樣本的類標號基于案例的推理樣本或案例使用復(fù)雜的符號表示，對于新案例，先檢測是否存在同樣的訓練案例；如果找不到，則搜索類似的訓練案例遺傳算法結(jié)合生物進化思想的算法粗糙集方法模糊集方法允許在分類規(guī)則中定義“模糊的”臨界值或邊界第三十二頁，共三十六頁，編輯于2023年，星期六什么是預(yù)測？預(yù)測是構(gòu)造和使用模型評估無樣本類，或評估給定樣本可能具有的屬性或值空間。預(yù)測和分類的異同相同點兩者都需要構(gòu)建模型都用模型來估計未知值預(yù)測當中主要的估計方法是回歸分析線性回歸和多元回歸非線性回歸不同點分類法主要是用來預(yù)測類標號（分類屬性值）預(yù)測法主要是用來估計連續(xù)值（量化屬性值）第三十三頁，共三十六頁，編輯于2023年，星期六線性回歸、多元回歸和非線性回歸線性回歸：Y=+X其中和是回歸系數(shù)，可以根據(jù)給定的數(shù)據(jù)點，通過最小二乘法來求得多元回歸：