第五講Modeler分類預(yù)測(cè)：決策樹算法(二)

1、分類預(yù)測(cè)：決策樹算法(二)分類回歸樹 分類回歸樹（Classification And Regression Tree，CART）是由美國斯坦福大學(xué)和加州大學(xué)伯克利分校的Breiman等人于1984年提的 分類樹和回歸樹 CART輸入變量和輸出變量可以是分類型也可以是數(shù)值型，C5.0中的輸出變量只能是定類型 CART只能建立2叉樹，而C5.0可以建立多叉樹 CART以Gini系數(shù)和方差為基礎(chǔ)選擇最佳分組變量和分割點(diǎn)，而C5.0則是以信息增益率 CART依據(jù)檢驗(yàn)樣本集進(jìn)行剪枝，而C5.0只依據(jù)訓(xùn)練樣本集通過近似正態(tài)分布進(jìn)行剪枝樹生長(zhǎng)：分類樹的生長(zhǎng) 數(shù)值型輸入變量： 找到使輸出變量“異質(zhì)性”下降最

2、大的分割點(diǎn) 異質(zhì)性測(cè)度： Clementine中 測(cè)度異質(zhì)性下降： kjtjptG12)|(1)()()()()(llrrtGNNtGNNtGtGjjtjtjptpNNtjptptjptjp),()(,),(,)(),()|(,歸一化概率 分類型輸入變量： 將多類別合并成“超類” Gini系數(shù)策略 Twoing策略：找到使合并形成的左右子結(jié)點(diǎn)（兩個(gè)超類）中分布差異足夠大的合并點(diǎn)s，即： Ordered策略：適用于定序型（Order Set型）輸入變量，限定只有兩個(gè)連續(xù)的別類才可合并成超類2| )|()|(|),(jrlrltjptjpppts樹生長(zhǎng)：分類樹的生長(zhǎng) 找到使輸出變量“異質(zhì)性”下降最

3、大的分割點(diǎn)或“超類” 異質(zhì)性測(cè)度： 測(cè)度異質(zhì)性下降：NiityyNtR12)(11)()()()()(llrrtRNNtRNNtRtR樹生長(zhǎng)：回歸樹的生長(zhǎng)分類回歸樹的剪枝 預(yù)剪枝 決策樹最大深度 樹中父結(jié)點(diǎn)和子結(jié)點(diǎn)所包含的最少樣本量或比例 樹結(jié)點(diǎn)中輸出變量的最小異質(zhì)性減少量 后剪枝：最小代價(jià)復(fù)雜性剪枝法(Minimal Cost Complexity Pruning，MCCP) 精度（或誤差）和復(fù)雜度之間的權(quán)衡 葉結(jié)點(diǎn)的個(gè)數(shù)反映復(fù)雜程度，誤差看作代價(jià) 決策樹T的代價(jià)復(fù)雜度定義為： |)()(TTRTR在檢驗(yàn)樣本集上的分類誤差葉結(jié)點(diǎn)個(gè)數(shù)復(fù)雜度系數(shù)，每增加一個(gè)葉結(jié)點(diǎn)所帶來的復(fù)雜度分類回歸樹的剪枝|

4、)()(tttTTRTR)()(tRtR保留子樹1|)()(ttTTRtRa)()(tTRtR1|)()(ttTTRtRa剪掉子樹1|)()(ttTTRtRa1|)()(tiTTRtR越小，越有把握剪掉子樹。可決策應(yīng)首先剪掉那棵子樹分類回歸樹的剪枝tTt 令0,逐漸增大，直到 CART的后剪枝過程：（兩個(gè)階段） 第一，產(chǎn)生子樹序列，分別表示為T1，T2，T3，Tk CART產(chǎn)生子樹序列的過程： 首先，對(duì)于最大樹T1，令=0； 然后，按照上述方法計(jì)算代價(jià)復(fù)雜度，并逐步增加直到有一個(gè)子樹可以被剪掉，得到子樹T2； 重復(fù)上述步驟，直到?jīng)Q策樹只剩下一個(gè)根結(jié)點(diǎn)； 最后得到子樹序列T1，T2，T3，Tk以

5、及它們的代價(jià)復(fù)雜度|)()(tttTTRTR)()(tRtR)()(tTRtR分類回歸樹的剪枝 CART的后剪枝過程： 第二，根據(jù)一定標(biāo)準(zhǔn),在k個(gè)子樹中確定一個(gè)代價(jià)復(fù)雜度最低的子樹)()(min)(kkkoptTRSEmTRTR放大因子Tk預(yù)測(cè)誤差的標(biāo)準(zhǔn)誤 )(1)()(NTRTRTRSEkkk分類回歸樹：示例找到影響客戶流失的重要因素 采用自動(dòng)建模方式 調(diào)整放大因子得到更重要的因素 結(jié)論： 老客戶忠誠度較高、關(guān)注新客戶 年齡、收入變量等是影響客戶流失的重要方面，但并沒有進(jìn)入決策樹，而是作為代理變量存在分類回歸樹：損失矩陣和先驗(yàn)概率 損失矩陣對(duì)分類樹的影響 以損失最小的類別作為預(yù)測(cè)類。計(jì)算各類

6、別的平均錯(cuò)判損失，并考慮先驗(yàn)概率 通過先驗(yàn)概率調(diào)整損失計(jì)算，或?qū)㈠e(cuò)判損失轉(zhuǎn)化為先驗(yàn)概率，對(duì)損失較大的類別給與較高的先驗(yàn)值，以規(guī)避高損失 示例：調(diào)整先驗(yàn)概率為0.6和0.4，對(duì)No的預(yù)測(cè)置信水平提高了)|()|()|(minijitjpjictipjjtjjtjptpNNtjptptjptjp),()(,),(,)(),()|(, 對(duì)于沒有選擇附加服務(wù)的客戶保持和流失成因分析 自行制定分組變量 關(guān)心無線費(fèi)用的影響，可指定無線費(fèi)用為分組變量 查看模型在訓(xùn)練樣本集合和檢驗(yàn)樣本集合上的情況 分類回歸樹：交互建模 模型收益（Gains）評(píng)價(jià)： 模型能否概括某類樣本所蘊(yùn)涵的特征和規(guī)律，在檢驗(yàn)樣本集上有理想

7、的分類預(yù)測(cè)能力。 模型總體收益越高就越有意義，利潤(rùn)（Profit）越高 逐個(gè)結(jié)點(diǎn)的收益評(píng)價(jià)： 選擇類別：如選yes,則評(píng)價(jià)某節(jié)點(diǎn)（規(guī)則）對(duì)客戶流失特征的概括能力 收益、收益(%)、響應(yīng)(%) 索引(%)：提升度分類回歸樹：模型評(píng)價(jià)收益和風(fēng)險(xiǎn))|(/ )|(populationclassPsampleclassPlifttt 逐個(gè)結(jié)點(diǎn)的利潤(rùn)評(píng)價(jià)： 兼顧考慮所以類別，對(duì)節(jié)點(diǎn)總體利潤(rùn)的評(píng)價(jià)分類回歸樹：模型評(píng)價(jià)收益和風(fēng)險(xiǎn)kiiipNN1)(1平均利潤(rùn)：ROI=總利潤(rùn)/總投資 模型整體的收益評(píng)價(jià) 選擇類別：如選yes,則評(píng)價(jià)整個(gè)模型（規(guī)則全體）對(duì)客戶流失特征的概括能力（按預(yù)測(cè)置信度降序排列） 累計(jì)收益圖

8、：理想的收益圖應(yīng)在前期快速達(dá)到較高的累計(jì)收益(%)，然后很快趨于100并平穩(wěn) 累計(jì)響應(yīng)圖：理想的響應(yīng)圖應(yīng)在較高的累計(jì)響應(yīng)(%)上保持一段，然后迅速下降 累計(jì)提升圖：理想的提升圖應(yīng)在較高的累計(jì)提升值上保持較長(zhǎng)一段，然后迅速下降到100% 累計(jì)利潤(rùn)圖、累計(jì)ROI圖分類回歸樹：模型評(píng)價(jià)收益和風(fēng)險(xiǎn) 模型的風(fēng)險(xiǎn)（Risk）評(píng)價(jià)：主要針對(duì)分類樹 混淆矩陣 風(fēng)險(xiǎn)（誤差）估計(jì)和誤差估計(jì)的標(biāo)準(zhǔn)誤 輸出變量為數(shù)值型的建模示例：對(duì)商品挑選時(shí)間的預(yù)測(cè)分類回歸樹：模型評(píng)價(jià)收益和風(fēng)險(xiǎn)CHAID算法 CHAID是卡方自動(dòng)交互診斷器（CHi-squared Automatic Interaction Detector）的英文

9、縮寫，1980年由Kass等人提出 輸入變量和輸出變量可以是分類型也可以是數(shù)值型 CHAID能夠建立多叉樹 從統(tǒng)計(jì)顯著性檢驗(yàn)角度確定當(dāng)前最佳分組變量和分割點(diǎn) 非信息增益率和Gini等 對(duì)數(shù)值型和分型輸入變量采用不同的統(tǒng)計(jì)檢驗(yàn)方法CHAID算法：輸入變量的預(yù)處理 目的：減少輸入變量的取值個(gè)數(shù) 數(shù)值型輸入變量： 首先按分位點(diǎn)分箱，然后根據(jù)統(tǒng)計(jì)檢驗(yàn)結(jié)果，合并對(duì)輸出變量取值沒有顯著影響的組 分類型輸入變量： 通過統(tǒng)計(jì)檢驗(yàn)，在其多個(gè)分類水平中找到對(duì)輸出變量取值影響不顯著的分類并合并它們，形成“超類”CHAID算法：輸入變量的預(yù)處理 合并組和形成超類的方法： 輸出變量為數(shù)值型：方差分析（輸出變量為觀測(cè)變量

10、） 輸入變量為數(shù)值型時(shí)：將經(jīng)過初始分組后的輸入變量作為控制變量。多重比較檢驗(yàn)，合并輸入變量的組別 輸入變量為分類型時(shí)：輸入變量作為控制變量。多重比較檢驗(yàn)，形成“超類” 輸出變量為分定類型： ChiMerge方法 輸入變量為數(shù)值型時(shí)：利用經(jīng)過初始分組后的輸入變量，合并組 輸入變量為分類型時(shí)：直接利用輸入變量，形成“超類”CHAID算法：輸入變量的預(yù)處理 ChiMerge舉例原始12條數(shù)據(jù)(數(shù)值變量X，分類變量Y，且按X升序排序)X1378911233739454659Y121112212111K=1K=2合計(jì)7.5,8.51018.5,9.5101合計(jì)202K=1K=2合計(jì)2,7.52137.5

11、,10202合計(jì)415K=1K=2合計(jì)2,10.041510,42134合計(jì)549x2=0.02.706(閾值=0.1) x2=0.834x2=2.72以X的中間值(2,5,7.5,8.5,1045.5,52.5)為初始組限CHAID算法：樹生長(zhǎng) 最佳分組變量的選擇 對(duì)于經(jīng)過預(yù)處理的輸入變量，計(jì)算與輸出變量相關(guān)性檢驗(yàn)的統(tǒng)計(jì)量的概率-P值 數(shù)值型輸出變量，采用F統(tǒng)計(jì)量 分類型輸出變量采用卡方或似然比卡方 最佳分割點(diǎn)的確定 CHAID方法不再重新確定分割點(diǎn)，自動(dòng)將分組變量的各個(gè)類別作為樹分枝，形成多叉樹 Exhaustive CHAID算法 Exhaustive CHAID算法 CHAID的改進(jìn)算

12、法，由Biggs、de Ville等人在1991年提出 計(jì)算檢驗(yàn)統(tǒng)計(jì)量的概率-P值時(shí)，繼續(xù)合并輸入變量分組，直到形成兩個(gè)組或兩個(gè)“超類”為止 CHAID的剪枝：預(yù)剪枝 CHAID的示例QUEST算法 QUEST算法是快速無偏有效統(tǒng)計(jì)樹（Quick Unbiased Efficient Statistical Tree）的英文縮寫，Loh和Shih在1997年提出的一種比較新的2叉樹建立方法 輸入變量可以是分類型也可是數(shù)值型，輸出變量為分類型變量 用于建立2叉樹 最佳分組變量和分割點(diǎn)的確定方式吸納了許多統(tǒng)計(jì)學(xué)的經(jīng)典方法QUEST算法：樹生長(zhǎng) 確定當(dāng)前最佳分組變量 最佳分組變量和分割點(diǎn)的確定方式吸

13、納了許多統(tǒng)計(jì)學(xué)的經(jīng)典方法 直接采用卡方檢驗(yàn)或F檢驗(yàn)的方法，分別檢驗(yàn)各輸入變量與輸出變量的相關(guān)性 選擇檢驗(yàn)統(tǒng)計(jì)量概率-P最小，且小于顯著性水平的輸入作為當(dāng)前的最佳分組變量QUEST算法：樹生長(zhǎng) 確定當(dāng)前最佳分組變量 如果最小的統(tǒng)計(jì)量概率-P尚不小于顯著性水平： 卡方檢驗(yàn)表明，所有輸入變量與輸出變量的相關(guān)性都不顯著，樹結(jié)點(diǎn)無法繼續(xù)分枝 F檢驗(yàn)檢驗(yàn)表明，在顯著性水平下，輸出變量不同類別水平下，輸入變量分布不存在顯著 利用LeveneF方法進(jìn)行方差齊性檢驗(yàn)，選擇方差齊性最不顯著的變量作為當(dāng)前最佳分組變量；如果檢驗(yàn)結(jié)果是所有輸入變量各分組下分布的方差均齊性，則樹結(jié)點(diǎn)無法繼續(xù)分枝QUEST算法：樹生長(zhǎng) 輸

14、出變量的預(yù)處理：輸出變量合并為2個(gè)“超類” 分別計(jì)算輸出變量多個(gè)類別水平下，輸入變量的均值向量； 如果輸出變量多個(gè)類別水平下的各均值向量均相等，則將權(quán)重最大的（即樣本量最多）的組作為一組，其余的各組合并為另一組，形成2個(gè)“超類”； 如果輸出變量多個(gè)類別水平下的各均值向量不相等，利用K-Means方法，形成2個(gè)“超類”。 QUEST算法：樹生長(zhǎng) 確定當(dāng)前最佳分割點(diǎn) 由于只能建立2叉樹，因此在確定分割點(diǎn)時(shí)，需將數(shù)值型輸入變量分成2組，將分類型輸入變量合并成2個(gè)“超類” 對(duì)于數(shù)值型分組變量：利用二次判別分析（quadratic discriminant analysis, QDA）確定分割點(diǎn) 計(jì)算輸

15、出變量?jī)深悇e（或超類）下分組變量的均值和方差 如果 ，則分割值為d為小方差組調(diào)整后的均值 )1 ()1 (1211xxxxd當(dāng)1210QUEST算法：樹生長(zhǎng) 確定當(dāng)前最佳分割點(diǎn) 由于只能建立2叉樹，因此在確定分割點(diǎn)時(shí)，需將數(shù)值型輸入變量分成2組，將定類型輸入變量合并成2個(gè)“超類” 對(duì)于分類型分組變量：采用上述相同方法確定分割點(diǎn) 要將分類型分組變量轉(zhuǎn)化為數(shù)值型，記為 將當(dāng)前最佳分組變量的m個(gè)類別轉(zhuǎn)換成啞變量 利用Fisher判別方法，建立關(guān)于輸出變量的若干個(gè)判別函數(shù)，并取第一個(gè)典型判別函數(shù)；計(jì)算各樣本的第一判別函數(shù)值作為值 QUEST的剪枝：同分類回歸樹 QUEST的示例決策樹模型的評(píng)價(jià) 評(píng)價(jià)指標(biāo)：誤差、收益率、提升度 Analysis結(jié)點(diǎn) Evaluation結(jié)點(diǎn)決策樹算法的說明 第一，決策樹算法在處理不同類型數(shù)據(jù)時(shí)的優(yōu)勢(shì)和劣勢(shì) 數(shù)值型的優(yōu)