【正文】 2020/9/15 ? 集合 T包含 N個(gè)類別的記錄，那么其 Gini指標(biāo)就是 ? 如果集合 T分成兩部分 N1 和 N2。通過(guò)刪除節(jié)點(diǎn)的分枝，剪掉葉節(jié)點(diǎn)。 ?如何處理過(guò)度擬合呢？對(duì)決策樹(shù)進(jìn)行修剪。 二、決策 樹(shù) (Decision Tree) （一） 決策樹(shù)的結(jié)構(gòu) 124 根部節(jié)點(diǎn) (root node) 中間節(jié)點(diǎn) (nonleaf node) (代表測(cè)試的條件 ) 分支 (branches) (代表測(cè)試的結(jié)果 ) 葉節(jié)點(diǎn) (leaf node) (代表分類后所獲得 的分類標(biāo)記 ) 2020/9/15 2020/9/15 125 （二）決策樹(shù)的形成 例： 126 ? 根部節(jié)點(diǎn) ? 中間節(jié)點(diǎn) ? 停止分支 ？ 2020/9/15 （三） ID3算法 (,) 127 2020/9/15 ?Quinlan(1979)提出，以 Shannon(1949)的信息論為依據(jù)。 2020/9/15 2020/9/15 122 ?速度 ：指產(chǎn)生和使用模型的計(jì)算花費(fèi)。 ? 選用 2020年各地區(qū)城鎮(zhèn)居民家庭人均全年消費(fèi)性支出樣本集對(duì)逐步向前的屬性子集選擇方法進(jìn)行模擬。 ?這種評(píng)價(jià)標(biāo)準(zhǔn)以函數(shù)的形式表示出來(lái)就是評(píng)價(jià)函數(shù)。 ?這種算法的不足是：在算法中雖然考慮了所選屬性與已入選屬性之間的相關(guān)性，但卻未考慮未入選屬性之間的統(tǒng)計(jì)相關(guān)性，并且一旦某個(gè)屬性已入選，即使由于后加入的屬性使它變?yōu)槎嘤?，也無(wú)法再剔除。 2020/9/15 93 2020/9/15 ?屬性子集的選擇方法一般有兩個(gè)組成部分： ? 一是高效率的屬性子集搜索策略，即在允許的時(shí)間內(nèi)，用以找出最小的、最能描述類別的屬性組合的搜索方法； ? 二是確定評(píng)價(jià)函數(shù)，是衡量屬性組合是否最優(yōu)的標(biāo)準(zhǔn)。 ?因子的方差貢獻(xiàn)和方差貢獻(xiàn)率是衡量因子重要性的關(guān)鍵指標(biāo)。 2020/9/15 87 2020/9/15 主成分分析（因子分析） ?主成分分析和因子分析都是多元統(tǒng)計(jì)分析中的一種常用方法，是數(shù)學(xué)上處理降維的一種方法。 85 2020/9/15 五、屬性的歸約 ? 屬性的歸約包括兩類方法：屬性的提取和屬性子集的選擇。 ) ( ) ( )1 1 1 14 9 49 49 50 50 50 50( l og 0 0) ( l og l og l og )15 0 1 1 15 0 14 9 14 9 14 9 14 9 14 9 14 90. 47 39 20 97SSE X T S En t S En t SSS??? ? ? ? ? ? ? ??72 2020/9/15 ? 以此類推，如把屬性值分為 [,)和 [,7,9]兩個(gè)區(qū)間時(shí)，產(chǎn)生的新的類別熵為： 2020/9/15 區(qū)間 d1 d2 d3 合計(jì) [,) 47 11 1 59 [,] 3 39 49 91 1212( , 。然而 3個(gè)五分的硬幣顯然是最好的找法。 ? 這時(shí)，我們會(huì)不假思索地拿出 2個(gè)二角五分的硬幣， 1個(gè)一角的硬幣和 3個(gè)一分的硬幣交給顧客。有： 2020/9/15 分組 頻數(shù) 賦值 ~ 46 1 ~ 37 2 ~ 32 3 ~ 35 4 63 2020/9/15 基于熵的離散化方法 ?信息熵的概念 ? 信息論中的熵：是信息的度量單位，是一種 對(duì)屬性“不確定性的度量” 。 ? 為防止過(guò)度擬合，應(yīng)使得每個(gè)區(qū)間的頻數(shù)大于等于總體單位數(shù)的平方根。 ? Iris樣本集是對(duì) 3種鳶尾花：剛毛鳶 (yuan)尾花、變色鳶尾花、佛吉尼亞鳶尾花各抽取 50個(gè)樣本。 ? 離散化后的不一致性數(shù)目至少應(yīng)該比在離散化前原始數(shù)據(jù)的不一致性數(shù)目少，且不一致性數(shù)目越少越好。 ?（ 2）根據(jù)一定的規(guī)則產(chǎn)生候選斷點(diǎn)集，構(gòu)造初始區(qū)間。 ? 無(wú)監(jiān)督的方法的缺陷在于它對(duì)分布不均勻的數(shù)據(jù)不適用，對(duì)異常點(diǎn)比較敏感。 ?離散化后可以達(dá)到歸約元祖的目的。箱中每一個(gè)值被最近的邊界值替換。如果給定特征的值的集合是 平滑后的集合是 }{}{?s m o ot h e dX2020/9/15 分箱 ?分箱方法是通過(guò)考察“鄰居”來(lái)平滑存儲(chǔ)數(shù)據(jù)的值。 ? 標(biāo)準(zhǔn)差規(guī)范化的格式是 其中： 是均值； 是標(biāo)準(zhǔn)差。 ? 對(duì)于基于距離的方法，規(guī)范化可以幫助防止具有較大初始值域的屬性與具有較小初始值域的屬性相比，權(quán)重過(guò)大。因此可以認(rèn)為，欺詐行為的發(fā)現(xiàn)過(guò)程就是一種異常數(shù)據(jù)的挖掘過(guò)程。根據(jù)實(shí)際可以把區(qū)間縮減到 [0, ]，由這個(gè)標(biāo)準(zhǔn)發(fā)現(xiàn) 3個(gè)異常點(diǎn)： 156, 139, 67。 ?回歸填補(bǔ)法是指在現(xiàn)有觀察值基礎(chǔ)上，以含有缺失值的目標(biāo)屬性為因變量，以與目標(biāo)屬性相關(guān)性高的其它屬性為自變量，建立最小二乘回歸模型或判別模型，以估計(jì)缺失值。但它卻增大了估計(jì)量的方差，并且穩(wěn)定性不夠。 ?如果我們不想扔掉這些有缺失值的樣本，就必須找到它們的缺失值，用什么方法來(lái)實(shí)現(xiàn)呢？ ? 填補(bǔ)缺失值。 特征值 編碼 黑色 1000 藍(lán)色 0100 綠色 0010 褐色 0001 9 2020/9/15 2020/9/15 變量 的分類： 連續(xù)型變量和離散型變量 。2020/9/15 第二章 數(shù)據(jù)預(yù)處理 2020/9/15 1 為什么要進(jìn)行數(shù)據(jù)挖掘 ? ?現(xiàn)實(shí)世界的數(shù)據(jù)是臟的 ? 不完整 : 缺乏屬性值，缺乏有意義的屬性，或者只包含了匯總數(shù)據(jù) ?., occupation=“ ” ? 有噪聲 : 包含錯(cuò)誤的數(shù)據(jù)或異常值 ?., Salary=“ 10” ? 不一致 : 在代碼或者名字中存在矛盾或不一致 ?., Age=“42” Birthday=“03/07/1997” ?., Was rating “1,2,3”, now rating “A, B, C” ?., discrepancy between duplicate records 2020/9/15 2 為什么數(shù)據(jù)預(yù)處理重要 ? ? No quality data, no quality mining results! ? Quality decisions must be based on quality data ?., duplicate or missing data may cause incorrect or even misleading statistics. ? Data warehouse needs consistent integration of quality data ? Data extraction, cleaning, and transformation prises the majority of the work of building a data warehouse 2020/9/15 3 2020/9/15 4 數(shù)據(jù)預(yù)處理的主要內(nèi)容： 2020/9/15 數(shù)據(jù)預(yù)處理的主要內(nèi)容 ?一、原始數(shù)據(jù)的表述 ?二、數(shù)據(jù)清理 ?三、數(shù)據(jù)變換 ?四、元組的歸約 ?五、屬性的歸約 2020/9/15 5 數(shù)據(jù)樣本是數(shù)據(jù)挖掘過(guò)程的基本組成部分。 ?連續(xù)型變量 也認(rèn)為是定量型或是量度 型，是指 在一定區(qū)間內(nèi)可以任意取值的變量。 12 2020/9/15 單一填補(bǔ)法 （ 1）均值填補(bǔ)法。 2020/9/15 16 2020/9/15 （ 3）熱卡填補(bǔ)法。 ?注意：以上幾種方法都存在扭曲樣本分布的問(wèn)題，如均值填補(bǔ)會(huì)降低屬性之間的相關(guān)關(guān)系，回歸填補(bǔ)則會(huì)人為地加大變量之間的相關(guān)關(guān)系等。 21 2020/9/15 2020/9/15 第二，基于距離的異常點(diǎn)檢測(cè)（二維以上數(shù)據(jù)） ?例如 ：數(shù)據(jù)集為： S={S1,S2,S3,S4,S5,S6,S7}＝ {(2,4),(3,2),(1,1),(4,3),(1,6),(5,3),(4,2)} 歐氏 距離 d=[(X1X2)2+(Y1Y2)2]1/2 取閾值距離為 d=3 22 異常點(diǎn) 2020/9/15 23 ?根據(jù)所用程序的結(jié)果和所給的閾值，可選擇 S3和 S5作為異常點(diǎn)。 2020/9/15 26 2020/9/15 ?具體的實(shí)現(xiàn)途徑是：利用聚類、神經(jīng)網(wǎng)絡(luò)和決策樹(shù)等分類方法，通過(guò)分析用戶的購(gòu)買(mǎi)、投?；蛳M(fèi)習(xí)慣，細(xì)分客戶，以此分辨出偏離模式的信用卡欺詐行為；然后，推導(dǎo)出合法交易的定義，建立模型；利用模型來(lái)分析一個(gè)新的交易是合法還是非法。 2020/9/15 30 （ 一）規(guī)范化（標(biāo)準(zhǔn)化） kii XX 10/??? 小數(shù) 縮放移動(dòng)小數(shù)點(diǎn)，但是要仍然保持原始數(shù)據(jù)的特征 。 ? 注意：該方法適用于當(dāng)屬性 X的最大和最小值未知，或孤立點(diǎn)左右了最大 最小規(guī)范化的情況下。存儲(chǔ)的值被分布到一些“桶”或“箱”中。 回歸 x y y = x + 1 X1 Y1 Y1’ 2020/9/15 40 通過(guò)自然劃分分段 ? 345規(guī)則可以將數(shù)值數(shù)據(jù)劃分成相對(duì)一致和“自然”區(qū)間。 2020/9/15 45 ?連續(xù)屬性的離散化就是將數(shù)值屬性的值域劃分為若干子區(qū)間，每個(gè)區(qū)間對(duì)應(yīng)一個(gè)離散值。 2020/9/15 47 有監(jiān)督離散化和無(wú)監(jiān)督離散化 動(dòng)態(tài)和靜態(tài)離散化 ?動(dòng)態(tài)離散化方法是在建立分類模型的同時(shí)對(duì)連續(xù)特征進(jìn)行離散化，例如， 。 ?（ 3）按照合并的規(guī)則，合并相鄰的初始區(qū)間。 ? （ 3）預(yù)測(cè)精確度。屬性是sepal length in cm萼片長(zhǎng)度 、 sepal width in cm萼片寬度、 petal length in cm花瓣長(zhǎng)度、 petal width in cm花瓣寬度。 ? sqrt(150)≈12 2020/9/15 58 2020/9/15 59 分組 頻數(shù) ~ 11 ~ 30 ~ 24 ~ 24 ~ 31 ~7 17 7~ 7 ~ 6 2020/9/15 進(jìn)行重新分組：使得每個(gè)區(qū)間的頻數(shù)大于 12 2020/9/15 分組 頻數(shù) 賦值 ~ 41 1 ～ 48 2 ~7 48 3 7~ 13 4 60 2020/9/15 聚類 ?聚類算法可以用來(lái)將數(shù)據(jù)劃分為群或簇。屬性的不確定性越大，把它搞清楚所需要的信息量也就越大，熵也就越大。這種找硬幣方法與其他的找法相比，所拿出的硬幣個(gè)數(shù)是最少的。 ?顯 然貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣的許多問(wèn)題它能產(chǎn)生整體最優(yōu)解。 ) ( ) ( )59 47 47 11 11 1 1( l og l og l og )150 59 59 59 59 59 5991 3 3 39 39 49 49( l og l og l og )150 91 91 91 91 91 91SSE X T S Ent S Ent SSS??? ? ? ?? ? ? ??73 2020/9/15 ? 對(duì)所有的分割點(diǎn)將屬性值分為兩個(gè)區(qū)間的新類別熵計(jì)算出來(lái)，有 2020/9/15 d1 d2 d3 新的類別熵 d1 d2 d3 新的類別熵 1 0 0 6 0 4 2 3 0 0 0 4 2 1 0 0 0 2 2 4 0 0 0 3 6 2 0 0 0 2 5 5 0 0 0 1 4 4 1 1 0 2 0 5 8 2 0 0 3 5 8 1 0 0 1 2 3 1 0 0 1 3 1 0 0 7 0