數(shù)據(jù)挖掘概念與技術(shù)第二章數(shù)據(jù)預(yù)處理的課件

1、數(shù)據(jù)挖掘: 概念與技術(shù) 第二章 數(shù)據(jù)預(yù)處理 2022/8/141數(shù)據(jù)挖掘：概念與技術(shù)第二章： 數(shù)據(jù)預(yù)處理為什么需要數(shù)據(jù)預(yù)處理?描述性數(shù)據(jù)匯總數(shù)據(jù)清理 數(shù)據(jù)集成和變換數(shù)據(jù)歸約數(shù)據(jù)離散化和概念分層產(chǎn)生總結(jié)2022/8/142數(shù)據(jù)挖掘：概念與技術(shù)為什么需要預(yù)處理數(shù)據(jù)？現(xiàn)實(shí)世界的數(shù)據(jù)容易“變臟”不完整: 缺省屬性值,缺少感興趣的屬性, 或者僅僅包含聚集數(shù)據(jù)。e.g., occupation=“ ”噪聲: 包含錯誤數(shù)據(jù)或者離群數(shù)據(jù)e.g., Salary=“-10”不一致: 編碼或名稱有差異的數(shù)據(jù)e.g., Age=“42” Birthday=“03/07/1997”e.g., Was rating “

2、1,2,3”, now rating “A, B, C”2022/8/143數(shù)據(jù)挖掘：概念與技術(shù)為什么數(shù)據(jù)會變臟?不完整的數(shù)據(jù)可能來自收集數(shù)據(jù)時(shí)該數(shù)據(jù)值(屬性)沒有用在收集數(shù)據(jù)和分析數(shù)據(jù)時(shí)的存在不同考慮人員/硬件/軟件故障的噪聲數(shù)據(jù)（不正確的數(shù)值）可能來自儀器設(shè)備產(chǎn)生錯誤數(shù)據(jù)數(shù)據(jù)輸入時(shí)人為錯誤或計(jì)算機(jī)錯誤數(shù)據(jù)傳輸錯誤不一致數(shù)據(jù)可能來自不同的數(shù)據(jù)源違反函數(shù)依賴 (e.g., 修改一些關(guān)聯(lián)數(shù)據(jù)（FK）)重復(fù)元組也需要數(shù)據(jù)清理2022/8/144數(shù)據(jù)挖掘：概念與技術(shù)為什么數(shù)據(jù)預(yù)處理很重要?低質(zhì)量的數(shù)據(jù)導(dǎo)致低質(zhì)量的挖掘結(jié)果高質(zhì)量的決策必須依賴于高質(zhì)量的數(shù)據(jù)e.g., 重復(fù)數(shù)據(jù)和缺失數(shù)據(jù)可能引起不正確，

3、甚至令人誤解的統(tǒng)計(jì)結(jié)果。數(shù)據(jù)倉庫需要集成高質(zhì)量的一致性數(shù)據(jù)數(shù)據(jù)抽取、清理和轉(zhuǎn)換是構(gòu)建數(shù)據(jù)倉庫的主要工作。2022/8/145數(shù)據(jù)挖掘：概念與技術(shù)數(shù)據(jù)質(zhì)量的度量被廣泛接受的數(shù)據(jù)質(zhì)量觀點(diǎn)：精確性完全性一致性合時(shí)性可信性增值性可解釋性可訪問性廣泛分類:內(nèi)在的,上下文關(guān)系的,代表性的,可訪問性的2022/8/146數(shù)據(jù)挖掘：概念與技術(shù)數(shù)據(jù)預(yù)處理的主要任務(wù)數(shù)據(jù)清理填充缺失值,光滑噪聲數(shù)據(jù), 識別和刪除離群值,解決不一致性數(shù)據(jù)集成集成多個(gè)數(shù)據(jù)庫、數(shù)據(jù)立方體或平面文件數(shù)據(jù)轉(zhuǎn)換規(guī)范化和聚集數(shù)據(jù)歸約獲得大量數(shù)據(jù)的簡化表示，但能夠產(chǎn)生同樣的結(jié)果數(shù)據(jù)離散化數(shù)據(jù)歸約的一種，對于數(shù)值數(shù)據(jù)自動產(chǎn)生概念分層非常重要。202

4、2/8/147數(shù)據(jù)挖掘：概念與技術(shù)Chapter 2: Data PreprocessingWhy preprocess the data?描述性數(shù)據(jù)匯總Data cleaning Data integration and transformationData reductionDiscretization and concept hierarchy generationSummary2022/8/148數(shù)據(jù)挖掘：概念與技術(shù)挖掘數(shù)據(jù)的描述性特征（1）動機(jī)更好地理解數(shù)據(jù)分布：中心趨勢，變化和傳播趨勢數(shù)據(jù)的中心趨勢度量均值(mean)、中位數(shù)(median)、眾數(shù)(mode)、中列數(shù)(midran

5、ge)等。數(shù)據(jù)的離中趨勢度量四分位數(shù)(quartiles)、四分位數(shù)極差(interquartile range, IQR)、極差(range)、方差(variance)等。2022/8/149數(shù)據(jù)挖掘：概念與技術(shù)挖掘數(shù)據(jù)的描述性特征（2）數(shù)據(jù)度量類型分布式度量將數(shù)據(jù)集劃分為較小的子集，計(jì)算每個(gè)子集的度量，然后合并計(jì)算結(jié)果而得到原數(shù)據(jù)集的度量值。如sum(), count(), min(), max()等。代數(shù)度量采用多個(gè)分布式度量函數(shù)來導(dǎo)出計(jì)算數(shù)據(jù)集的度量值。如average()=sum()/count() 。整體度量必須對整個(gè)數(shù)據(jù)集計(jì)算的度量，計(jì)算開銷較大，可以尋找近似計(jì)算的方法。2022

6、/8/1410數(shù)據(jù)挖掘：概念與技術(shù)度量數(shù)據(jù)的中心趨勢（1）平均值mean (代數(shù)度量，分布式度量，SQL中AVG():加權(quán)算術(shù)平均:截?cái)嗥骄═rimmed mean）: 去掉極值中值median: (整體度量值)奇數(shù)個(gè)值的中間值, 偶數(shù)個(gè)值的中間兩個(gè)的平均值插值估計(jì) (for 分組分區(qū)間數(shù)據(jù)):2022/8/1411數(shù)據(jù)挖掘：概念與技術(shù)度量數(shù)據(jù)的中心趨勢（2）眾數(shù)Mode集合中出現(xiàn)頻率最高的值單峰的 Unimodal, 雙峰的 bimodal, 三峰的trimodal經(jīng)驗(yàn)公式：中列數(shù)數(shù)據(jù)集中最大和最小值的平均值2022/8/1412數(shù)據(jù)挖掘：概念與技術(shù)度量數(shù)據(jù)的離散程度（1） (數(shù)據(jù)已經(jīng)遞增

7、排序)極差，四分位數(shù), 離群點(diǎn) 與 盒圖極差（range）：最大值與最小值之差四分位數(shù): Q1 (第25個(gè)百分位數(shù)), Q3 (第75個(gè)百分位數(shù))中間四分位數(shù)極差: IQR = Q3 Q1 五數(shù)概括: min, Q1, Median, Q3, max盒圖:盒的端點(diǎn)在四分位數(shù)上使得盒的長度是中間四分位數(shù)極差I(lǐng)QR中位數(shù)用盒內(nèi)的線標(biāo)記盒的另外兩條線（胡須）延伸到最小和最大觀測值離群點(diǎn)單獨(dú)個(gè)別繪出離群點(diǎn):高于Q3或低于Q1的1.5 x IQR2022/8/1413數(shù)據(jù)挖掘：概念與技術(shù)度量數(shù)據(jù)的離散程度（2）方差和標(biāo)準(zhǔn)差 方差: (代數(shù)度量, 可伸縮的計(jì)算)標(biāo)準(zhǔn)差 s (or ) 是方差的平方根 s2

8、 (or 2)2022/8/1414數(shù)據(jù)挖掘：概念與技術(shù)正態(tài)分布曲線的屬性正態(tài)分布曲線從 到 +: 大約包含68%的觀測值 (: mean, : standard deviation)從 2 到 +2:大約包含95%的觀測值 從 3 到 +3:大約包含99.7%的觀測值 2022/8/1415數(shù)據(jù)挖掘：概念與技術(shù)描述數(shù)據(jù)匯總的圖形顯示直方圖：Histogram盒圖: Boxplot分位數(shù)圖：Quantile plot分為數(shù)分為數(shù)圖：Quantile-quantile (q-q) plot散布圖：Scatter plot局部回歸曲線：Loess (local regression) curve2

9、022/8/1416數(shù)據(jù)挖掘：概念與技術(shù)直方圖分析頻率直方圖 概括給定屬性分布的圖形方法根據(jù)某一數(shù)據(jù)屬性將數(shù)據(jù)分布劃分為不相交的子集或桶。每個(gè)桶的寬度一致桶的高度等于桶中的值的計(jì)數(shù)或相對頻率2022/8/1417數(shù)據(jù)挖掘：概念與技術(shù)分位數(shù)圖：Quantile Plot觀察單變量數(shù)據(jù)分布的簡單有效方法顯示給定屬性的所有數(shù)據(jù) (允許用戶評估總體情況和不尋常的出現(xiàn)情況)繪出分位數(shù)信息對于按遞增排序的數(shù)據(jù)xi ，每個(gè)觀測值xi 與一個(gè)百分?jǐn)?shù)fi 配對，使得數(shù)據(jù)的fi %的數(shù)據(jù)小于或等于xi Q10.25分為數(shù)； Q20. 5分為數(shù)； Q30.75分為數(shù)；2022/8/1418數(shù)據(jù)挖掘：概念與技術(shù)分為數(shù)

10、分為數(shù)圖：Quantile-Quantile (Q-Q) Plot對著另一個(gè)對應(yīng)的分為數(shù)圖，繪制一個(gè)單變量分布的分為數(shù)可以觀察從一個(gè)分布到另一個(gè)分布是否有位移強(qiáng)有力的數(shù)據(jù)可視化工具2022/8/1419數(shù)據(jù)挖掘：概念與技術(shù)散布圖：Scatter plot確定兩個(gè)屬性值之間是否有聯(lián)系、模式或趨勢的圖形化方法每個(gè)值對視為一個(gè)代數(shù)坐標(biāo)對，作為一個(gè)點(diǎn)畫在平面上。觀察雙變量的方法，觀察點(diǎn)的簇和離群點(diǎn)，考察相關(guān)聯(lián)系的可能性。2022/8/1420數(shù)據(jù)挖掘：概念與技術(shù)正相關(guān)和負(fù)相關(guān)數(shù)據(jù)2022/8/1421數(shù)據(jù)挖掘：概念與技術(shù) 不相關(guān)數(shù)據(jù)2022/8/1422數(shù)據(jù)挖掘：概念與技術(shù)局部回歸曲線：Loess C

11、urve增加一條光滑曲線到散布圖，以便更好地理解依賴模式兩個(gè)設(shè)置參數(shù)： 光滑參數(shù)，在0.251之間被擬合多項(xiàng)式的次數(shù)， =1，先行擬合； =2，二次擬合2022/8/1423數(shù)據(jù)挖掘：概念與技術(shù)Chapter 2: Data PreprocessingWhy preprocess the data?Descriptive data summarizationData cleaning Data integration and transformationData reductionDiscretization and concept hierarchy generationSummary202

12、2/8/1424數(shù)據(jù)挖掘：概念與技術(shù)數(shù)據(jù)清理重要性“數(shù)據(jù)清理是數(shù)據(jù)倉庫中三個(gè)最大的問題之一”Ralph Kimball“數(shù)據(jù)清理是數(shù)據(jù)倉庫中的第一個(gè)問題”DCI survey數(shù)據(jù)清理的任務(wù)填充缺失值識別離群點(diǎn)和平滑噪聲數(shù)據(jù)糾正不一致的數(shù)據(jù)解決由于數(shù)據(jù)集成而引起的數(shù)據(jù)冗余問題2022/8/1425數(shù)據(jù)挖掘：概念與技術(shù)缺失數(shù)據(jù)數(shù)據(jù)并不是經(jīng)?？捎玫腅.g., 許多元組的一些屬性上沒有記錄值，如銷售數(shù)據(jù)中沒有顧客的收入。缺失值的可能原因設(shè)備故障由于與其它記錄數(shù)據(jù)的不一致而刪除由于誤解而沒有記錄相關(guān)數(shù)據(jù)某些數(shù)據(jù)可能由于當(dāng)時(shí)認(rèn)為不重要而沒有錄入記錄歷史或修改的數(shù)據(jù)被忽略。缺失數(shù)據(jù)需要被推斷出來2022/8

13、/1426數(shù)據(jù)挖掘：概念與技術(shù)如何處理缺失值？忽略元組：缺失類標(biāo)號時(shí)忽略該元組 (對于分類挖掘當(dāng)每個(gè)屬性缺少值的百分比變化很大時(shí)，性能特別差。人工填寫缺失值：費(fèi)時(shí)乏味，甚至不可行。自動填值方法：用全局常量填寫： e.g., “unknown”, 可能被認(rèn)為一個(gè)新類?! 用屬性的平均值填寫用與給定元組屬同一類的所有樣本的屬性均值填寫: smarter！使用最可能的值填寫：基于推理的方法，如回歸、貝葉斯、回歸樹方法2022/8/1427數(shù)據(jù)挖掘：概念與技術(shù)噪聲數(shù)據(jù)噪聲:被測量數(shù)據(jù)的隨機(jī)誤差或方差不正確的屬性值可能由于：有故障的數(shù)據(jù)采集設(shè)備數(shù)據(jù)錄入問題數(shù)據(jù)傳輸問題技術(shù)限制，如數(shù)據(jù)傳輸?shù)耐骄彌_區(qū)的大

14、小限制不一致的命名約定需要數(shù)據(jù)清理的其他數(shù)據(jù)問題重復(fù)數(shù)據(jù)不完備數(shù)據(jù)不一致數(shù)據(jù)2022/8/1428數(shù)據(jù)挖掘：概念與技術(shù)如何處理噪聲數(shù)據(jù)?分箱（Binning）先排序，然后分箱（等頻）箱均值光滑，箱中位數(shù)光滑，箱邊界值光滑。回歸（regression）通過回歸函數(shù)擬合數(shù)據(jù)來光滑數(shù)據(jù)聚類（Clustering）檢測并刪除離群點(diǎn)計(jì)算機(jī)與人工檢測相結(jié)合檢測可疑值，并由人工確認(rèn)，如離群點(diǎn)檢測。2022/8/1429數(shù)據(jù)挖掘：概念與技術(shù)簡單的離散化方法：分箱等寬分割(distance)將變化范圍均分為N個(gè)間隔。若A和B分別為屬性值的最小和最大值，則間隔寬度為： W = (B A)/N.最簡單直接的方法，但

15、容易受離群點(diǎn)的影響。傾斜數(shù)據(jù)不能很好地處理等深分割 (frequency)將變化范圍分為N個(gè)間隔，每個(gè)間隔內(nèi)包含相同的樣本數(shù)。具有很好的數(shù)據(jù)伸縮性。2022/8/1430數(shù)據(jù)挖掘：概念與技術(shù)分箱方法舉例已經(jīng)排序的價(jià)格數(shù)據(jù)：4, 8, 9, 15, 21, 21, 24, 25, 26, 28, 29, 34* 等頻（等深）分箱: - Bin 1： 4, 8, 9, 15 - Bin 2：21, 21, 24, 25 - Bin 3：26, 28, 29, 34* 箱均值光滑 - Bin 1 ： 9, 9, 9, 9 - Bin 2 ： 23, 23, 23, 23 - Bin 3 ： 29,

16、29, 29, 29* 箱邊界光滑: - Bin 1 ： 4, 4, 4, 15 - Bin 2 ： 21, 21, 25, 25 - Bin 3 ： 26, 26, 26, 342022/8/1431數(shù)據(jù)挖掘：概念與技術(shù)回歸xyy = x + 1X1Y1Y12022/8/1432數(shù)據(jù)挖掘：概念與技術(shù)聚類分析2022/8/1433數(shù)據(jù)挖掘：概念與技術(shù)數(shù)據(jù)清理作為一個(gè)過程數(shù)據(jù)偏差檢測使用元數(shù)據(jù) (e.g., domain, range, dependency, distribution)檢查字段過載，新屬性擠占了未使用的部分。 檢查唯一性規(guī)則、連續(xù)性規(guī)則和空值規(guī)則。使用商業(yè)工具進(jìn)行偏差檢測數(shù)據(jù)清

17、洗工具: 使用簡單的域知識 檢測和修改錯誤數(shù)據(jù)審計(jì)工具: 通過分析數(shù)據(jù)發(fā)現(xiàn)規(guī)則和聯(lián)系以及檢測違反這些條件的數(shù)據(jù)來發(fā)現(xiàn)偏差 (e.g., 相關(guān)或聚類來發(fā)現(xiàn)離群點(diǎn))數(shù)據(jù)遷移與集成數(shù)據(jù)遷移工具: 允許說明變換ETL (Extraction/Transformation/Loading) 工具: 允許用戶通過圖形用戶界面說明變換數(shù)據(jù)集成的兩個(gè)過程迭代和交互 (e.g., Potters Wheels，數(shù)據(jù)清理工具，)2022/8/1434數(shù)據(jù)挖掘：概念與技術(shù)Chapter 2: Data PreprocessingWhy preprocess the data?Data cleaning Data i

18、ntegration and transformationData reductionDiscretization and concept hierarchy generationSummary2022/8/1435數(shù)據(jù)挖掘：概念與技術(shù)數(shù)據(jù)集成數(shù)據(jù)集成：合并來自多個(gè)數(shù)據(jù)存儲的數(shù)據(jù)模式集成: e.g., A.cust-id B.cust-#從不同的源數(shù)據(jù)集成元數(shù)據(jù)實(shí)體識別問題： e.g., Bill Clinton = William Clinton檢測并解決數(shù)據(jù)值沖突對于同一實(shí)體, 不同數(shù)據(jù)源中的屬性值是不相同的可能原因：不同表示方法，不同尺度2022/8/1436數(shù)據(jù)挖掘：概念與技術(shù)處理數(shù)據(jù)

19、集成中的冗余多個(gè)數(shù)據(jù)集成時(shí)冗余數(shù)據(jù)可能發(fā)生于：對象識別: 同一屬性或?qū)ο笤诓煌瑪?shù)據(jù)庫中可能有不同的名字。派生數(shù)據(jù)： e.g., annual revenue相關(guān)分析可能檢測到屬性冗余細(xì)致集成多源數(shù)據(jù)可以減少或避免冗余和不一致性，從而提高數(shù)據(jù)挖掘的速度和質(zhì)量2022/8/1437數(shù)據(jù)挖掘：概念與技術(shù)相關(guān)分析 (數(shù)值數(shù)據(jù))相關(guān)系數(shù) (also called Pearsons product moment coefficient)where n is the number of tuples, and are the respective means of A and B, A and B are

20、the respective standard deviation of A and B, and (AB) is the sum of the AB cross-product.If rA,B 0, A and B 正相關(guān) The higher, the stronger correlation.rA,B = 0: 獨(dú)立; rA,B 0: 負(fù)相關(guān)2022/8/1438數(shù)據(jù)挖掘：概念與技術(shù)相關(guān)性分析 (分類數(shù)據(jù))2 (卡方) 檢驗(yàn)：相依表2 越大, 變量越可能相關(guān)對2貢獻(xiàn)最大的單元是其實(shí)際計(jì)數(shù)值與期望計(jì)數(shù)值很不相同的單元。相關(guān)性并不意味因果關(guān)系醫(yī)院數(shù)與盜車數(shù)是相關(guān)的，不意味一個(gè)因素導(dǎo)致另一個(gè)因

21、素。由于第三變量:人口2022/8/1439數(shù)據(jù)挖掘：概念與技術(shù)卡方計(jì)算例子2 (chi-square) calculation (numbers in parenthesis are expected counts calculated based on the data distribution in the two categories)It shows that like_science_fiction and play_chess are correlated in the groupPlay chessNot play chessSum (row)Like science fict

22、ion250(90)200(360)450Not like science fiction50(210)1000(840)1050Sum(col.)300120015002022/8/1440數(shù)據(jù)挖掘：概念與技術(shù)數(shù)據(jù)轉(zhuǎn)換平滑: 去掉數(shù)據(jù)中的噪聲聚集: 匯總，構(gòu)造數(shù)據(jù)立方體數(shù)據(jù)泛化: 概念分層（向上提升）規(guī)范化: 將屬性按比例縮放,變換到指定的范圍最小最大規(guī)范化z-score 規(guī)范化（零均值規(guī)范化）小數(shù)定標(biāo)規(guī)范化屬性構(gòu)造（特征構(gòu)造）：從給定的屬性集中構(gòu)造新的屬性2022/8/1441數(shù)據(jù)挖掘：概念與技術(shù)數(shù)據(jù)轉(zhuǎn)化：規(guī)范化最小-最大規(guī)范化: to new_minA, new_maxAEx. 將收入范

23、圍 $12,000到$98,000 規(guī)范到 0.0, 1.0. 則 $73,000 將映射為 Z-score 規(guī)范化 (: mean, : standard deviation):Ex. Let = 54,000, = 16,000. Then小數(shù)定標(biāo)規(guī)范法j 是使得 Max(|) 1的最小整數(shù)2022/8/1442數(shù)據(jù)挖掘：概念與技術(shù)Chapter 2: Data PreprocessingWhy preprocess the data?Data cleaning Data integration and transformationData reductionDiscretization

24、and concept hierarchy generationSummary2022/8/1443數(shù)據(jù)挖掘：概念與技術(shù)數(shù)據(jù)歸約策略為什么需要數(shù)據(jù)歸約?Tb級的數(shù)據(jù)倉庫在完整的數(shù)據(jù)集上進(jìn)行復(fù)雜的數(shù)據(jù)分析或挖掘非常耗時(shí)數(shù)據(jù)歸約 在更小的數(shù)據(jù)量上獲得歸約表示，但產(chǎn)生相同或近似的結(jié)果數(shù)據(jù)歸約策略數(shù)據(jù)立方體聚集:屬性子集選擇 e.g., 去除不重要的屬性數(shù)據(jù)壓縮：使用編碼機(jī)制減少數(shù)據(jù)集的規(guī)模數(shù)值歸約 e.g., 將數(shù)據(jù)擬合成模型離散化和概念分層產(chǎn)生2022/8/1444數(shù)據(jù)挖掘：概念與技術(shù)數(shù)據(jù)立方體聚集基本立方體 (base cuboid)：最低抽象層創(chuàng)建的立方體對應(yīng)于感興趣的個(gè)體實(shí)體，E.g., 顧

25、客頂點(diǎn)立方體（apex cuboid）：最高層抽象的立方體。E.g.,所有商品類型，所有分店三年的總銷售額。多層次聚集進(jìn)一步減少數(shù)據(jù)量參考合適的層級用最小但足夠的立方體實(shí)現(xiàn)給定任務(wù)2022/8/1445數(shù)據(jù)挖掘：概念與技術(shù)屬性子集選擇特征選擇 (i.e., 屬性子集選擇):目標(biāo)：找出最小屬性集，使數(shù)據(jù)類的概率分布盡可能地接近使用所有屬性得到的原分布減少了出現(xiàn)在發(fā)現(xiàn)模式的屬性數(shù)目，使得模式更易于理解最好和最差屬性使用統(tǒng)計(jì)顯著性檢驗(yàn)來確定。對于d個(gè)特征，存在2d 個(gè)可能的子集啟發(fā)式方法 (由于與選擇組合成指數(shù)關(guān)系):逐步向前選擇逐步向后刪除向前選擇與向后刪除結(jié)合決策樹歸納2022/8/1446數(shù)據(jù)

26、挖掘：概念與技術(shù)啟發(fā)式屬性子集選擇的例子2022/8/1447數(shù)據(jù)挖掘：概念與技術(shù)數(shù)據(jù)壓縮字符串壓縮有一些很好的理論和算法無損壓縮但只允許有限的數(shù)據(jù)操作視頻/音頻壓縮有損壓縮有時(shí)小的片段可以在不整體重構(gòu)的情況下重構(gòu)2022/8/1448數(shù)據(jù)挖掘：概念與技術(shù)數(shù)據(jù)壓縮原始數(shù)據(jù)壓縮數(shù)據(jù)無損壓縮近似的原始數(shù)據(jù) 有損壓縮2022/8/1449數(shù)據(jù)挖掘：概念與技術(shù)維度壓縮:小波變換 離散小波變換 (DWT):線性信號處理，多分辨率分析近似壓縮數(shù)據(jù)：僅保存一小部分最強(qiáng)的小波系數(shù)與離散傅立葉變換近似 (DFT), 但有損壓縮更好，小波空間局部性相當(dāng)好，有助于保留局部細(xì)節(jié)。方法:長度L必須是2的整數(shù)次冪 (必要

27、時(shí)添0補(bǔ)充)每次變換涉及兩個(gè)函數(shù):平滑函數(shù), 加權(quán)差分函數(shù)遞歸作用于上一步的結(jié)果數(shù)據(jù)集, 導(dǎo)致兩個(gè)長度為 L/2的數(shù)據(jù)集 Haar2Daubechie42022/8/1450數(shù)據(jù)挖掘：概念與技術(shù)基于DWT的圖像壓縮Image Low Pass High Pass Low Pass High PassLow Pass High Pass2022/8/1451數(shù)據(jù)挖掘：概念與技術(shù)搜索k個(gè)最能代表數(shù)據(jù)的n維正交向量，將原來的數(shù)據(jù)投影到一個(gè)小得多的空間。通過創(chuàng)建一個(gè)替換的、更小的變量集組合屬性的基本要素。 步驟輸入數(shù)據(jù)規(guī)范化:每個(gè)屬性都落入相同的區(qū)間計(jì)算k個(gè)正交向量輸入數(shù)據(jù)是主成份的線性組合對主成份按

28、重要性或強(qiáng)度降序排列去掉較弱的成分（即方差較?。﹣須w約數(shù)據(jù)的規(guī)模，使用最強(qiáng)的主成份應(yīng)當(dāng)能夠非常近似的原始數(shù)據(jù)。僅能處理數(shù)值型數(shù)據(jù)當(dāng)維數(shù)維度壓縮: 主成份分析 (PCA)2022/8/1452數(shù)據(jù)挖掘：概念與技術(shù)X1X2Y1Y2主成分分析2022/8/1453數(shù)據(jù)挖掘：概念與技術(shù)數(shù)值歸約通過選擇替代的、較小的數(shù)據(jù)表現(xiàn)形式來減少數(shù)據(jù)量參數(shù)方法使用模型估計(jì)數(shù)據(jù)，只需存放模型參數(shù)，而不是實(shí)際數(shù)據(jù)。例子：回歸模型，對數(shù)線性模型非參數(shù)方法不要假設(shè)模型直方圖，聚類，抽樣2022/8/1454數(shù)據(jù)挖掘：概念與技術(shù)數(shù)據(jù)歸約 (1): 回歸和對數(shù)線性模型線性回歸: 對數(shù)據(jù)擬合成直線模型常用最小二乘方法求解斜率和截

29、距系數(shù)多元回歸: 允許響應(yīng)變量建模為多個(gè)預(yù)測變量的線性函數(shù)。對數(shù)線性模型: 近似離散的多維概率分布。2022/8/1455數(shù)據(jù)挖掘：概念與技術(shù)回歸分析: Y = w X + b兩個(gè)回歸系數(shù), w 和 b, 對 Y1, Y2, , X1, X2, .通過最小二乘計(jì)算多元回歸: Y = b0 + b1 X1 + b2 X2.對數(shù)線性模型:概率: p(a, b, c, d) = ab acad bcd回歸分析和對數(shù)線性模型2022/8/1456數(shù)據(jù)挖掘：概念與技術(shù)數(shù)據(jù)歸約方法 (2): 直方圖將數(shù)據(jù)劃分為桶，并存儲每桶的平均值劃分規(guī)則:等寬: 每桶范圍相同等頻 (or 等深)：每桶個(gè)數(shù)相同V-最優(yōu)具

30、有最小方差的直方圖MaxDiff: 桶的邊界是具有1 最大差（相鄰值之間的差）的對， 為桶數(shù)2022/8/1457數(shù)據(jù)挖掘：概念與技術(shù)數(shù)據(jù)歸約方法 (3): 聚類將數(shù)據(jù)劃分為簇或群，使得簇中對象相似，而與其他簇中對象相異，僅存儲簇的表示相似性基于距離函數(shù)，用對象在空中的接近程度。能夠提供分層聚類，并存儲在多維索引樹中。第七章講聚類。2022/8/1458數(shù)據(jù)挖掘：概念與技術(shù)數(shù)據(jù)歸約方法 (4): 抽樣抽樣: 用小樣本表示整個(gè)數(shù)據(jù)集 得到樣本的開銷正比于樣本集的大小，而不是數(shù)據(jù)集的大小抽樣的復(fù)雜性子線性與數(shù)據(jù)的大小無放回簡單隨機(jī)抽樣有放回簡單隨機(jī)抽樣聚類抽樣分層抽樣2022/8/1459數(shù)據(jù)挖掘

31、：概念與技術(shù)抽樣: 有/無放回SRSWOR(simple random sample without replacement)SRSWRRaw Data2022/8/1460數(shù)據(jù)挖掘：概念與技術(shù)抽樣: 聚簇或分層抽樣Raw Data Cluster/Stratified Sample2022/8/1461數(shù)據(jù)挖掘：概念與技術(shù)Chapter 2: Data PreprocessingWhy preprocess the data?Data cleaning Data integration and transformationData reductionDiscretization and co

32、ncept hierarchy generationSummary2022/8/1462數(shù)據(jù)挖掘：概念與技術(shù)離散化三類屬性:名義的 values from an unordered set, e.g., color, profession次序的 values from an ordered set, e.g., military or academic rank 連續(xù)的 real numbers, e.g., integer or real numbers離散化: 將連續(xù)屬性范圍分割為間隔一些分類算法僅接受分類屬性減少數(shù)據(jù)為進(jìn)一步分析作準(zhǔn)備2022/8/1463數(shù)據(jù)挖掘：概念與技術(shù)離散化和概念

33、分層離散化 通過將屬性范圍分割為區(qū)間值減少數(shù)據(jù)值區(qū)間標(biāo)記可以替代實(shí)際值監(jiān)督和非監(jiān)督的離散化分裂 (top-down) vs. 合并 (bottom-up)可以迭代離散化概念分層形式通過高層概念替換較低層概念來迭代減少哦數(shù)據(jù)2022/8/1464數(shù)據(jù)挖掘：概念與技術(shù)數(shù)值數(shù)據(jù)的離散化和概念分層產(chǎn)生典型方法:所有方法都可以遞歸使用。分箱 (covered above)Top-down split, unsupervised, 直方圖分析 (covered above)Top-down split, unsupervised聚類分析 (covered above)Either top-down spl

34、it or bottom-up merge, unsupervised基于熵的離散化: supervised, top-down split基于 2 分析的區(qū)間合并: unsupervised, bottom-up merge根據(jù)直觀劃分離散化: top-down split, unsupervised2022/8/1465數(shù)據(jù)挖掘：概念與技術(shù)基于熵的離散化Given a set of samples S, if S is partitioned into two intervals S1 and S2 using boundary T, the information gain after

35、partitioning isEntropy is calculated based on class distribution of the samples in the set. Given m classes, the entropy of S1 iswhere pi is the probability of class i in S1The boundary that minimizes the entropy function over all possible boundaries is selected as a binary discretizationThe process

36、 is recursively applied to partitions obtained until some stopping criterion is metSuch a boundary may reduce data size and improve classification accuracy2022/8/1466數(shù)據(jù)挖掘：概念與技術(shù)基于 2 分析的區(qū)間合并Merging-based (bottom-up) vs. splitting-based methodsMerge: Find the best neighboring intervals and merge them t

37、o form larger intervals recursivelyChiMerge Kerber AAAI 1992, See also Liu et al. DMKD 2002Initially, each distinct value of a numerical attr. A is considered to be one interval2 tests are performed for every pair of adjacent intervalsAdjacent intervals with the least 2 values are merged together, s

38、ince low 2 values for a pair indicate similar class distributionsThis merge process proceeds recursively until a predefined stopping criterion is met (such as significance level, max-interval, max inconsistency, etc.) 2022/8/1467數(shù)據(jù)挖掘：概念與技術(shù)根據(jù)直觀劃分離散化A simply 3-4-5 rule can be used to segment numeric d

39、ata into relatively uniform, “natural” intervals.If an interval covers 3, 6, 7 or 9 distinct values at the most significant digit, partition the range into 3 equi-width intervalsIf it covers 2, 4, or 8 distinct values at the most significant digit, partition the range into 4 intervalsIf it covers 1,

40、 5, or 10 distinct values at the most significant digit, partition the range into 5 intervals2022/8/1468數(shù)據(jù)挖掘：概念與技術(shù)Example of 3-4-5 Rule(-$400 -$5,000)(-$400 - 0)(-$400 - -$300)(-$300 - -$200)(-$200 - -$100)(-$100 - 0)(0 - $1,000)(0 - $200)($200 - $400)($400 - $600)($600 - $800)($800 - $1,000)($2,000

41、 - $5, 000)($2,000 - $3,000)($3,000 - $4,000)($4,000 - $5,000)($1,000 - $2, 000)($1,000 - $1,200)($1,200 - $1,400)($1,400 - $1,600)($1,600 - $1,800)($1,800 - $2,000) msd=1,000Low=-$1,000High=$2,000Step 2:Step 4:Step 1: -$351-$159profit $1,838 $4,700 Min Low (i.e, 5%-tile) High(i.e, 95%-0 tile) Maxco

42、unt(-$1,000 - $2,000)(-$1,000 - 0)(0 -$ 1,000)Step 3:($1,000 - $2,000)2022/8/1469數(shù)據(jù)挖掘：概念與技術(shù)分類數(shù)據(jù)的概念分層產(chǎn)生Specification of a partial/total ordering of attributes explicitly at the schema level by users or expertsstreet city state countrySpecification of a hierarchy for a set of values by explicit data groupingUrbana, Champaign, Chicago Illinois