《數(shù)據(jù)挖掘》課程PPT-分類(lèi)和預(yù)測(cè)資料.ppt

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

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

3、分類(lèi)的測(cè)試樣本的百分比 測(cè)試集要獨(dú)立于訓(xùn)練樣本集，否則會(huì)出現(xiàn)“過(guò)分?jǐn)M合”的情況,第一步建立模型,訓(xùn)練數(shù) 據(jù)集,分類(lèi)算法,IF rank = professor OR years 6 THEN tenured = yes,分類(lèi)規(guī)則,第二步用模型進(jìn)行分類(lèi),分類(lèi)規(guī)則,測(cè)試集,未知數(shù)據(jù),(Jeff, Professor, 4),Tenured?,監(jiān)督學(xué)習(xí) VS. 無(wú)監(jiān)督學(xué)習(xí),監(jiān)督學(xué)習(xí)（用于分類(lèi)） 模型的學(xué)習(xí)在被告知每個(gè)訓(xùn)練樣本屬于哪個(gè)類(lèi)的“指導(dǎo)”下進(jìn)行 新數(shù)據(jù)使用訓(xùn)練數(shù)據(jù)集中得到的規(guī)則進(jìn)行分類(lèi) 無(wú)監(jiān)督學(xué)習(xí)（用于聚類(lèi)） 每個(gè)訓(xùn)練樣本的類(lèi)編號(hào)是未知的，要學(xué)習(xí)的類(lèi)集合或數(shù)量也可能是事先未知的 通過(guò)一系列的度

4、量、觀察來(lái)建立數(shù)據(jù)中的類(lèi)編號(hào)或進(jìn)行聚類(lèi),數(shù)據(jù)預(yù)測(cè)的兩步過(guò)程,數(shù)據(jù)預(yù)測(cè)也是一個(gè)兩步的過(guò)程，類(lèi)似于前面描述的數(shù)據(jù)分類(lèi) 對(duì)于預(yù)測(cè)，沒(méi)有“類(lèi)標(biāo)號(hào)屬性” 要預(yù)測(cè)的屬性是連續(xù)值，而不是離散值，該屬性可簡(jiǎn)稱(chēng)“預(yù)測(cè)屬性” E.g. 銀行貸款員需要預(yù)測(cè)貸給某個(gè)顧客多少錢(qián)是安全的 預(yù)測(cè)器可以看作一個(gè)映射或函數(shù)y=f(X) 其中X是輸入；y是輸出，是一個(gè)連續(xù)或有序的值 與分類(lèi)類(lèi)似，準(zhǔn)確率的預(yù)測(cè)，也要使用單獨(dú)的測(cè)試集,準(zhǔn)備分類(lèi)和預(yù)測(cè)的數(shù)據(jù),通過(guò)對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，可以提高分類(lèi)和預(yù)測(cè)過(guò)程的準(zhǔn)確性、有效性和可伸縮性 數(shù)據(jù)清理 消除或減少噪聲，處理空缺值，從而減少學(xué)習(xí)時(shí)的混亂 相關(guān)分析 數(shù)據(jù)中的有些屬性可能與當(dāng)前任務(wù)不相關(guān)；

5、也有些屬性可能是冗余的；刪除這些屬性可以加快學(xué)習(xí)步驟，使學(xué)習(xí)結(jié)果更精確 數(shù)據(jù)變換與歸約 數(shù)據(jù)可以通過(guò)規(guī)范化進(jìn)行變換，將所給屬性的所有值按比例進(jìn)行縮放，使其落入一個(gè)較小的指定區(qū)間，例 0.0, 1.0（ANN和設(shè)計(jì)距離的度量方法中常用） 可以將數(shù)據(jù)概化到較高層概念,比較分類(lèi)方法,使用下列標(biāo)準(zhǔn)比較分類(lèi)和預(yù)測(cè)方法 預(yù)測(cè)的準(zhǔn)確率：模型正確預(yù)測(cè)新數(shù)據(jù)的類(lèi)編號(hào)的能力 速度：產(chǎn)生和使用模型的計(jì)算花銷(xiāo) 健壯性：給定噪聲數(shù)據(jù)或有空缺值的數(shù)據(jù)，模型正確預(yù)測(cè)的能力 可伸縮性：對(duì)大量數(shù)據(jù)，有效的構(gòu)建分類(lèi)器或預(yù)測(cè)器的能力 可解釋性：學(xué)習(xí)模型提供的理解和洞察的層次,用決策樹(shù)歸納分類(lèi) (1),什么是決策樹(shù)？ 類(lèi)似于流程圖的

6、樹(shù)結(jié)構(gòu) 每個(gè)內(nèi)部節(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試 每個(gè)分枝代表一個(gè)測(cè)試輸出 每個(gè)樹(shù)葉節(jié)點(diǎn)存放一個(gè)類(lèi)編號(hào),age?,student?,credit rating?,no,yes,fair,excellent,youth,senior,no,no,yes,yes,yes,Middle aged,決策樹(shù)：Buys_computer,用決策樹(shù)歸納分類(lèi) (2),使用決策樹(shù)分類(lèi) 給定一個(gè)類(lèi)標(biāo)號(hào)未知的元組X，在決策樹(shù)上測(cè)試元組的屬性值，跟蹤一條由根到葉節(jié)點(diǎn)的路徑，葉節(jié)點(diǎn)存放該元組的類(lèi)預(yù)測(cè)。 決策樹(shù)容易轉(zhuǎn)換為分類(lèi)規(guī)則 決策樹(shù)的生成由兩個(gè)階段組成 決策樹(shù)構(gòu)建 使用屬性選擇度量來(lái)選擇將元組最好的劃分為不同的類(lèi)的屬性 遞

7、歸的通過(guò)選定的屬性，來(lái)劃分樣本 （必須是離散值） 樹(shù)剪枝 決策樹(shù)建立時(shí)，許多分枝反映的是訓(xùn)練數(shù)據(jù)中的噪聲和離群點(diǎn)點(diǎn)，樹(shù)剪枝試圖識(shí)別并剪去這種分枝，以提高對(duì)未知數(shù)據(jù)分類(lèi)的準(zhǔn)確性,決策樹(shù)歸納策略 (1),輸入 數(shù)據(jù)劃分D是訓(xùn)練元組和對(duì)應(yīng)類(lèi)標(biāo)號(hào)的集合 attribute_list,候選屬性的集合 Attribute_selection_method，指定選擇屬性的啟發(fā)性過(guò)程 算法步驟 樹(shù)以代表訓(xùn)練樣本的單個(gè)節(jié)點(diǎn)（N）開(kāi)始 如果樣本都在同一個(gè)類(lèi)，則該節(jié)點(diǎn)成為樹(shù)葉，并用該類(lèi)標(biāo)記 否則，算法調(diào)用Attribute_selection_method，選擇能夠最好的將樣本分類(lèi)的屬性；確定“分裂準(zhǔn)則”，指出“分

8、裂點(diǎn)”或“分裂子集”。,P189 圖6-3,決策樹(shù)歸納策略 (2),對(duì)測(cè)試屬性每個(gè)已知的值，創(chuàng)建一個(gè)分支，并以此劃分元組 算法使用同樣的過(guò)程，遞歸的形成每個(gè)劃分上的元組決策樹(shù)。一旦一個(gè)屬性出現(xiàn)在一個(gè)節(jié)點(diǎn)上，就不在該節(jié)點(diǎn)的任何子節(jié)點(diǎn)上出現(xiàn) 遞歸劃分步驟停止的條件 劃分D（在N節(jié)點(diǎn)提供）的所有元組屬于同一類(lèi) 沒(méi)有剩余屬性可以用來(lái)進(jìn)一步劃分元組使用多數(shù)表決 沒(méi)有剩余的樣本 給定分支沒(méi)有元組，則以D中多數(shù)類(lèi)創(chuàng)建一個(gè)樹(shù)葉,P189 圖6-3,屬性選擇度量,屬性選擇度量是一種選擇分裂準(zhǔn)則，將給定類(lèi)標(biāo)號(hào)的訓(xùn)練元組最好的進(jìn)行劃分的方法 理想情況，每個(gè)劃分都是“純”的，即落在給定劃分內(nèi)的元組都屬于相同的類(lèi) 屬性

9、選擇度量又稱(chēng)為分裂準(zhǔn)則 常用的屬性選擇度量 信息增益 增益率 Gini指標(biāo),信息增益 (1),S是一個(gè)訓(xùn)練樣本的集合，該樣本中每個(gè)集合的類(lèi)編號(hào)已知。每個(gè)樣本為一個(gè)元組。有個(gè)屬性用來(lái)判定某個(gè)訓(xùn)練樣本的類(lèi)編號(hào) 假設(shè)S中有m個(gè)類(lèi)，總共s個(gè)訓(xùn)練樣本，每個(gè)類(lèi)Ci有si個(gè)樣本(i1,2,3.m)，那么任意一個(gè)樣本屬于類(lèi)Ci的概率是si / s，那么用來(lái)分類(lèi)一個(gè)給定樣本的期望信息是：,信息增益 (2),一個(gè)有v個(gè)值的屬性Aa1,a2,.,av可以將S分成v個(gè)子集S1,S2,.,Sv，其中Sj包含S中屬性A上的值為aj的樣本。假設(shè)Sj包含類(lèi)Ci的sij個(gè)樣本。根據(jù)A的這種劃分的期望信息稱(chēng)為A的熵 A上該劃分的

10、獲得的信息增益定義為： 具有高信息增益的屬性，是給定集合中具有高區(qū)分度的屬性。所以可以通過(guò)計(jì)算S中樣本的每個(gè)屬性的信息增益，來(lái)得到一個(gè)屬性的相關(guān)性的排序。,判定歸納樹(shù)算法示例 (1),對(duì)于上述數(shù)據(jù)，可以略過(guò)步驟1，2 步驟3，計(jì)算基于熵的度量信息增益，作為樣本劃分的根據(jù) Gain(age)=0.246 Gain(income)=0.029 Gain(student)=0.151 Gain(credit_rating)=0.048 然后，對(duì)測(cè)試屬性每個(gè)已知的值，創(chuàng)建一個(gè)分支，并以此劃分樣本，得到第一次劃分,判定歸納樹(shù)算法示例 (2),判定歸納樹(shù)算法示例 (3),age?,overcast,stu

11、dent?,credit rating?,no,yes,fair,excellent,youth,senior,no,no,yes,yes,yes,Middle aged,防止分類(lèi)中的過(guò)分適應(yīng),產(chǎn)生的決策樹(shù)會(huì)出現(xiàn)過(guò)分適應(yīng)數(shù)據(jù)的問(wèn)題 由于數(shù)據(jù)中的噪聲和孤立點(diǎn)，許多分枝反應(yīng)的是訓(xùn)練數(shù)據(jù)中的異常 對(duì)新樣本的判定很不精確 防止過(guò)分適應(yīng)的兩種方法 先剪枝：通過(guò)提前停止樹(shù)的構(gòu)造如果在一個(gè)節(jié)點(diǎn)劃分樣本將導(dǎo)致低于預(yù)定義臨界值的分裂（e.g. 使用信息增益度量） 選擇一個(gè)合適的臨界值往往很困難 后剪枝：由“完全生長(zhǎng)”的樹(shù)剪去分枝對(duì)于樹(shù)中的每個(gè)非樹(shù)葉節(jié)點(diǎn)，計(jì)算該節(jié)點(diǎn)上的子樹(shù)被剪枝可能出現(xiàn)的期望錯(cuò)誤率 使用一個(gè)獨(dú)立

12、的測(cè)試集來(lái)評(píng)估每顆樹(shù)的準(zhǔn)確率，就能得到具有最小期望錯(cuò)誤率的決策樹(shù),由決策樹(shù)提取分類(lèi)規(guī)則,可以提取決策樹(shù)表示的知識(shí)，并以IF-THEN形式的分類(lèi)規(guī)則表示 對(duì)從根到樹(shù)葉的每條路徑創(chuàng)建一個(gè)規(guī)則 沿著給定路徑上的每個(gè)屬性-值對(duì)形成規(guī)則前件（IF部分）的一個(gè)合取項(xiàng) 葉節(jié)點(diǎn)包含類(lèi)預(yù)測(cè)，形成規(guī)則后件（THEN部分） IF-THEN規(guī)則易于理解，尤其樹(shù)很大時(shí) 示例： IF age = “youth” AND student = “no” THEN buys_computer = “no” IF age = “youth” AND student = “yes” THEN buys_computer = “ye

13、s” IF age = “middle_aged” THEN buys_computer = “yes” IF age = “senior” AND credit_rating = “excellent” THEN buys_computer = “yes” IF age = “senior” AND credit_rating = “fair” THEN buys_computer = “no”,可伸縮性與決策歸納樹(shù),分類(lèi)挖掘是一個(gè)在統(tǒng)計(jì)學(xué)和機(jī)器學(xué)習(xí)的領(lǐng)域也被廣為研究的問(wèn)題，并提出了很多算法，但是這些算法都是內(nèi)存駐留的 可伸縮性問(wèn)題：要求以合理的速度對(duì)數(shù)以百萬(wàn)計(jì)的樣本和數(shù)以百計(jì)的屬性的進(jìn)行分

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

15、號(hào)來(lái)學(xué)習(xí)。 優(yōu)點(diǎn) 預(yù)測(cè)精度總的來(lái)說(shuō)較高 健壯性好，訓(xùn)練樣本中包含錯(cuò)誤時(shí)也可正常工作 輸出可能是離散值、連續(xù)值或者是離散或量化屬性的向量值 對(duì)目標(biāo)進(jìn)行分類(lèi)較快 缺點(diǎn) 訓(xùn)練（學(xué)習(xí)）時(shí)間長(zhǎng) 蘊(yùn)涵在學(xué)習(xí)的權(quán)中的符號(hào)含義很難理解 很難根專(zhuān)業(yè)領(lǐng)域知識(shí)相整合,SVM支持向量機(jī),使用一種非線(xiàn)性的映射，將原訓(xùn)練數(shù)據(jù)映射到較高的維 一個(gè)數(shù)據(jù)被認(rèn)為是p維向量，數(shù)據(jù)在這個(gè)p維向量空間中被分為兩類(lèi)；SVM的目的是找到一個(gè)p-1維的超平面，來(lái)劃分p維向量空間的數(shù)據(jù) 在新的維上，它搜索線(xiàn)性最佳分離超平面 (即將一類(lèi)的元組與其他類(lèi)分離的“決策邊界”)。 使用一個(gè)適當(dāng)?shù)膶?duì)足夠高維的非線(xiàn)性映射，兩類(lèi)的數(shù)據(jù)總可以被超平面分開(kāi)。 S

16、VM 使用支持向量（“基本”訓(xùn)練元組）和邊緣（由支持向量定義）發(fā)現(xiàn)該超平面。,SVM-特點(diǎn)和應(yīng)用,特點(diǎn): 訓(xùn)練時(shí)間非常長(zhǎng)，但對(duì)復(fù)雜的非線(xiàn)性決策邊界的建模能力是高度準(zhǔn)確的（使用最大邊緣） 可以用來(lái)預(yù)測(cè)和分類(lèi) 應(yīng)用: 手寫(xiě)數(shù)字識(shí)別，對(duì)象識(shí)別，語(yǔ)音識(shí)別, 以及基準(zhǔn)時(shí)間序列預(yù)測(cè)檢驗(yàn),SVM一般原理,August 9, 2020,Data Mining: Concepts and Techniques,31,SVM當(dāng)數(shù)據(jù)是線(xiàn)性可分的時(shí)候,m,設(shè)給定的數(shù)據(jù)集 D 為 (X1, y1), , (X|D|, y|D|), 其中Xi是訓(xùn)練元組，具有相關(guān)聯(lián)的類(lèi)標(biāo)號(hào)yi。 可以畫(huà)出無(wú)限多條分離直線(xiàn)（或超平面）將類(lèi)+

17、1的元組與類(lèi)-1的元組分開(kāi)，我們想找出“最好的”那一條 (對(duì)先前未見(jiàn)到的元組具有最小分類(lèi)誤差的那一條）。 SVM 要搜索具有最大邊緣的超平面，即最大邊緣超平面 (MMH),其他分類(lèi)方法,k-最臨近分類(lèi) 給定一個(gè)未知樣本，k-最臨近分類(lèi)法搜索模式空間，找出最接近未知樣本的k個(gè)訓(xùn)練樣本；然后使用k個(gè)最臨近者中最公共的類(lèi)來(lái)預(yù)測(cè)當(dāng)前樣本的類(lèi)標(biāo)號(hào) 基于案例的推理 樣本或案例使用復(fù)雜的符號(hào)表示，對(duì)于新案例，先檢測(cè)是否存在同樣的訓(xùn)練案例；如果找不到，則搜索類(lèi)似的訓(xùn)練案例 遺傳算法 結(jié)合生物進(jìn)化思想的算法 粗糙集方法 模糊集方法 允許在分類(lèi)規(guī)則中定義“模糊的”臨界值或邊界,什么是預(yù)測(cè)？,預(yù)測(cè)是構(gòu)造和使用模型評(píng)

18、估無(wú)樣本類(lèi)，或評(píng)估給定樣本可能具有的屬性或值空間。 預(yù)測(cè)和分類(lèi)的異同 相同點(diǎn) 兩者都需要構(gòu)建模型 都用模型來(lái)估計(jì)未知值 預(yù)測(cè)當(dāng)中主要的估計(jì)方法是回歸分析 線(xiàn)性回歸和多元回歸 非線(xiàn)性回歸 不同點(diǎn) 分類(lèi)法主要是用來(lái)預(yù)測(cè)類(lèi)標(biāo)號(hào)（分類(lèi)屬性值） 預(yù)測(cè)法主要是用來(lái)估計(jì)連續(xù)值（量化屬性值）,線(xiàn)性回歸、多元回歸和非線(xiàn)性回歸,線(xiàn)性回歸：Y = + X 其中和是回歸系數(shù)，可以根據(jù)給定的數(shù)據(jù)點(diǎn)，通過(guò)最小二乘法來(lái)求得 多元回歸：Y = + 1X1 + 2 X2 線(xiàn)性回歸的擴(kuò)展，設(shè)計(jì)多個(gè)預(yù)測(cè)變量，可以用最小二乘法求得上式中的，1 和2 非線(xiàn)性回歸：Y = + 1X1 + 2 X22+ 3 X33 對(duì)不呈線(xiàn)性依賴(lài)的數(shù)據(jù)建模 使用多項(xiàng)式回歸建模方法，然后進(jìn)行變量變換，將非線(xiàn)性模型轉(zhuǎn)換為線(xiàn)性模型，然后用最小二乘法求解,評(píng)估分類(lèi)法的準(zhǔn)確性,導(dǎo)出分類(lèi)法后，再使用訓(xùn)練數(shù)據(jù)評(píng)估分類(lèi)法，可能錯(cuò)誤的導(dǎo)致樂(lè)觀的估計(jì) 保持方法 給定數(shù)據(jù)隨機(jī)劃分為兩個(gè)集合：訓(xùn)練集(2/3)和測(cè)試集(1/3) 訓(xùn)練集導(dǎo)出分類(lèi)法，測(cè)試集對(duì)其準(zhǔn)確性進(jìn)行評(píng)估 隨機(jī)子選樣：保持方法的一個(gè)變形，將保持方法重復(fù)k次，然后取準(zhǔn)確率的平均值 k-折交叉確