數(shù)據(jù)預處理概述11課件

1、為什么要進行數(shù)據(jù)挖掘?現(xiàn)實世界的數(shù)據(jù)是臟的不完整: 缺乏屬性值，缺乏有意義的屬性，或者只包含了匯總數(shù)據(jù)e.g., occupation=“ ”有噪聲: 包含錯誤的數(shù)據(jù)或異常值e.g., Salary=“-10”不一致: 在代碼或者名字中存在矛盾或不一致e.g., Age=“42” Birthday=“03/07/1997”e.g., Was rating “1,2,3”, now rating “A, B, C”e.g., discrepancy between duplicate records2022/7/191為什么數(shù)據(jù)預處理重要?No quality data, no quality

2、mining results!Quality decisions must be based on quality datae.g., duplicate or missing data may cause incorrect or even misleading statistics.Data warehouse needs consistent integration of quality dataData extraction, cleaning, and transformation comprises the majority of the work of building a da

3、ta warehouse2022/7/192數(shù)據(jù)預處理的主要內容：2022/7/193數(shù)據(jù)預處理的主要內容一、原始數(shù)據(jù)的表述二、數(shù)據(jù)清理三、數(shù)據(jù)變換四、元組的歸約五、屬性的歸約2022/7/192022/7/194數(shù)據(jù)樣本是數(shù)據(jù)挖掘過程的基本組成部分。一、原始數(shù)據(jù)的表述每個樣本都用幾個特征來描述，每個特征有不同類型的值。2022/7/1952022/7/19常見的數(shù)據(jù)類型有：數(shù)值型和分類型。數(shù)值型包括實型變量和整型變量注：具有數(shù)值型值的特征有兩個重要的屬性：其值有順序關系和距離關系。 2022/7/1962022/7/19一個有兩個值的分類型變量:分類型變量的兩個值可以平等或不平等。原則上可以

4、轉化成一個二進制的數(shù)值型變量，這種數(shù)值型變量有兩個值：0或1；而有N值的分類型變量原則上可以轉化成一個二進制的數(shù)值型變量，這種數(shù)值型變量有N個值。2022/7/1972022/7/19例如：如果變量“眼睛顏色”有4個值：黑色、藍色、綠色、褐色。 特征值 編碼 黑色 1000 藍色 0100 綠色 0010 褐色 00012022/7/1982022/7/19變量的分類：連續(xù)型變量和離散型變量。連續(xù)型變量也認為是定量型或是量度型，是指在一定區(qū)間內可以任意取值的變量。離散型變量也叫定性型變量，是指全部可能取到的不相同的值是有限個的變量。注：一種特殊類型的離散型變量是周期變量，例如：星期、月和年中的

5、日期。2022/7/1992022/7/19與時間有關的數(shù)據(jù)分類：靜態(tài)數(shù)據(jù)數(shù)據(jù)不隨時間變化而變化動態(tài)數(shù)據(jù)（時間數(shù)據(jù)）隨時間變化而變化的屬性。注：大多數(shù)數(shù)據(jù)挖掘方法更適用于靜態(tài)數(shù)據(jù)，在對動態(tài)數(shù)據(jù)進行挖掘時要有特殊的考慮和預處理。2022/7/1910二、數(shù)據(jù)清理缺失值的填補2022/7/19對數(shù)據(jù)挖掘的實際應用而言，即使數(shù)據(jù)量很大，具有完整數(shù)據(jù)的案例也非常少，這樣就面臨數(shù)據(jù)的缺失問題。應用數(shù)據(jù)挖掘方法之前如何處理這樣現(xiàn)象，最簡單的辦法是減少數(shù)據(jù)集，去掉所有有缺失值的樣本。如果我們不想扔掉這些有缺失值的樣本，就必須找到它們的缺失值，用什么方法來實現(xiàn)呢？填補缺失值。2022/7/19111、單一填補

6、法（1）均值填補法。均值填補法是根據(jù)與含缺失值的目標屬性相關性高的其它屬性的信息將樣品分為若干組，然后分別計算各組目標屬性的均值，將各組均值作為組內所有缺失項的填補值。均值填補的優(yōu)點是操作簡便，并且可以有效地降低其點估計的偏差。但它的缺點也比較突出：首先，由于同組中的缺失值由同一個值填補，填補結果歪曲了目標屬性的分布；其次，也導致在均值和總量估計中對方差的低估。2022/7/192022/7/1912例：2022/7/1913均值填補：2022/7/1914（2）隨機填補法。隨機填補法是采用某種概率抽樣的方式，從有完整信息的元組中抽取缺失數(shù)據(jù)的填補值的方法。它雖然能夠避免均值填補中填補值過于凝

7、集以及容易扭曲目標屬性分布的弱點，使得填補值的分布與真值分布更為接近。但它卻增大了估計量的方差，并且穩(wěn)定性不夠。2022/7/192022/7/1915（3）熱卡填補法。熱卡填補法（hot deck imputation）是規(guī)定一個或多個排序屬性，按其觀察值大小對全部觀察單位排序，如果選擇的是兩個以上的屬性，排序按屬性的入選順序依次進行。排序屬性值完全相同的觀察單位稱為匹配，缺失值就用與之匹配的觀察單位的屬性值來填補。如果有多例相匹配，可取第一例或隨機取其一。如果沒有相匹配的，可以每次減少一個排序屬性，再找相匹配的元組。如果直到最后一個排序屬性，還沒有找到相匹配的，則需要重新規(guī)定排序屬性。20

8、22/7/192022/7/1916（4）回歸填補法?；貧w填補法是指在現(xiàn)有觀察值基礎上，以含有缺失值的目標屬性為因變量，以與目標屬性相關性高的其它屬性為自變量，建立最小二乘回歸模型或判別模型，以估計缺失值。注意：以上幾種方法都存在扭曲樣本分布的問題，如均值填補會降低屬性之間的相關關系，回歸填補則會人為地加大變量之間的相關關系等。2022/7/192022/7/1917例：2022/7/19182022/7/19（二）異常值（孤立點）探測在大型數(shù)據(jù)集中，通常存在著不遵循數(shù)據(jù)模型的普遍行為的樣本，這些樣本和其他殘余部分數(shù)據(jù)有很大不同或不一致，叫做異常點。異常點可能是由測量誤差造成的，也可能是數(shù)據(jù)故

9、有的可變性結果。例如：在檢測銀行交易中的信用卡欺詐行為時，異常點是可能揭示欺詐行為的典型例子。2022/7/19192022/7/19異常值的探測方法第一，一維樣本異常點的檢測方法例如：如果所給的數(shù)據(jù)集用20個不同的值描述年齡特征： 3, 56, 23, 39, 156, 52, 41, 22, 9,28, 139, 31, 55, 20, -67, 37, 11, 55, 45, 37 均值=39.9; 標準差=45.65閾值=均值2標準差那么，所有在-54.1, 131.2區(qū)間以外的數(shù)據(jù)都是潛在的異常點。根據(jù)實際可以把區(qū)間縮減到0, 131.2，由這個標準發(fā)現(xiàn)3個異常點：156, 139,

10、 -67。2022/7/19202022/7/19第二，基于距離的異常點檢測（二維以上數(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=(X1-X2)2+(Y1-Y2)21/2 取閾值距離為 d=32022/7/1921異常點2022/7/1922根據(jù)所用程序的結果和所給的閾值，可選擇S3和S5作為異常點。2022/7/1923第三：基于分類預測模型的異常值探測異常值的探測也可以認為是一類特殊的分類問題。因為對于一般的分類問題，考慮的是如何將各種類別有效地分開，而在異常值探測中，分

11、類的目標是準確地描述總體的正常行為特征，在此之外大范圍的其它對象被視為異常值。其基本思想是：對總體的特征建立分類模型，形成正常行為的特征庫；然后針對新的數(shù)據(jù)判斷其是否屬于正常行為，從而認定其是否與總體偏離，發(fā)生偏離的即是異常值。根據(jù)所建立的分類器的不同，異常值的探測方法有以下幾種：決策樹分類；貝葉斯分類；神經(jīng)網(wǎng)絡分類；聚類。2022/7/192022/7/1924異常值探測的應用信用卡、保險行業(yè)以及電信用戶欺詐行為的探測。異常值探測對于欺詐行為的發(fā)現(xiàn)，主要是基于這樣的思想：任何人在使用信用卡、投保和電信消費的正常行為都是有一定的規(guī)律的，并且可以通過這些行為產(chǎn)生的信息總結出這些規(guī)律；由于欺詐行為

12、和正常的行為存在嚴重的差異，檢查出這些差異就可以探測出是否存在欺詐發(fā)生。因此可以認為，欺詐行為的發(fā)現(xiàn)過程就是一種異常數(shù)據(jù)的挖掘過程。2022/7/192022/7/1925具體的實現(xiàn)途徑是：利用聚類、神經(jīng)網(wǎng)絡和決策樹等分類方法，通過分析用戶的購買、投?；蛳M習慣，細分客戶，以此分辨出偏離模式的信用卡欺詐行為；然后，推導出合法交易的定義，建立模型；利用模型來分析一個新的交易是合法還是非法。也可以通過六西格瑪探測、聚類等方法，尋找出與正常投保行為有極大差別的不正常行為，即有可能的欺詐行為。除了利用上述技術對異常數(shù)據(jù)進行識別外，還可以通過關聯(lián)規(guī)則的Apriori算法尋找異常數(shù)據(jù)間的隱含模型，從而達到

13、反欺詐的目的。2022/7/192022/7/1926例如：對電信用戶的欺詐行為探測的具體做法是：首先，將目標屬性定為無意欠費客戶和惡意欠費兩類；其次，選擇屬性作為輸入屬性，通常包括服務合同屬性（如服務類型、服務時間、交費類型等）、客戶的基本狀態(tài)（如性別、年齡、收入、婚姻狀況、受教育年限/學歷、職業(yè)、居住地區(qū)等）以及經(jīng)?；蚨ㄆ诟淖兊臄?shù)據(jù)（如每月消費金額、交費紀錄等）；然后，將分類方法用于預先選定的包含客戶欠費狀態(tài)的訓練集中，從而挖掘歸納出規(guī)則集；最后，利用所獲取的規(guī)則，對電信企業(yè)新用戶的繳費情況進行預測分類，從而達到預防欺詐的目的。2022/7/192022/7/1927三、數(shù)據(jù)變換數(shù)據(jù)變換是

14、將數(shù)據(jù)轉換成適合于挖掘的形式。數(shù)據(jù)變換可能涉及到如下內容：數(shù)據(jù)規(guī)范化數(shù)據(jù)平滑數(shù)據(jù)概化2022/7/192022/7/1928為什么要進行標準化？一些數(shù)據(jù)挖掘方法，需要對數(shù)據(jù)進行標準化以獲得最佳的效果。例如，對于分類算法，如涉及神經(jīng)網(wǎng)絡的算法或諸如最臨近分類和聚類的距離度量分類算法，都需要將訓練樣本屬性度量輸入值規(guī)范化，這樣有助于加快學習階段的速度。對于基于距離的方法，規(guī)范化可以幫助防止具有較大初始值域的屬性與具有較小初始值域的屬性相比，權重過大。（一）規(guī)范化（標準化）2022/7/1929小數(shù)縮放移動小數(shù)點，但是要仍然保持原始數(shù)據(jù)的特征。小數(shù)點的移動位數(shù)依賴于X的最大絕對值。典型的縮放是保持數(shù)

15、值在-1和1范圍內，可以用格式描述：1、小數(shù)縮放規(guī)范化是指通過將屬性數(shù)據(jù)按比例縮放，使之落入一個小的特定區(qū)間，如0.0到1.0，對屬性規(guī)范化。2022/7/19302、最小-最大規(guī)范化最小-最大規(guī)范化是對原始數(shù)據(jù)進行線性變換。最小-最大規(guī)范化的格式： 從而將X的值映射到0，1中。2022/7/19313、標準差規(guī)范化（z-score規(guī)范化）標準差規(guī)范化是將某個屬性的值基于其平均值和標準差進行規(guī)范化。標準差規(guī)范化的格式是 其中： 是均值； 是標準差。注意：該方法適用于當屬性X的最大和最小值未知，或孤立點左右了最大-最小規(guī)范化的情況下。2022/7/192022/7/1932為什么要進行數(shù)據(jù)的平滑

16、？一個數(shù)值型的特征可能包含許多不同的值。對許多數(shù)據(jù)挖掘技術來說，這些值之間小小的區(qū)別并不重要，但可能會降低挖掘方法的性能并影響最終的結果。因此，對變量的值進行平滑處理很重要。（二）數(shù)據(jù)平滑(離散化)2022/7/19332022/7/19數(shù)據(jù)平滑：是指去掉數(shù)據(jù)中的噪聲。這種技術包括分箱技術、聚類和回歸。例如：進行圓整處理。如果給定特征的值的集合是平滑后的集合是2022/7/19341、分箱分箱方法是通過考察“鄰居”來平滑存儲數(shù)據(jù)的值。存儲的值被分布到一些“桶”或“箱”中。由于分箱方法參考的是相鄰的值，因此，它進行的是局部平滑。分箱方法有以下幾種：按箱平均值平滑按箱中值平滑按箱邊值平滑。2022

17、/7/192022/7/1935例如：某產(chǎn)品的價格排序后的數(shù)據(jù)為：4、8、15、21、21、24、25、28、34。首先，將上述數(shù)據(jù)劃分為等深的箱： 箱1：4、8、15 箱2：21、21、24 箱3：25、28、34（1）按箱中值平滑： 箱1：8、8、8 箱2：21、21、21 箱3：28、28、282022/7/192022/7/1936排序后的數(shù)據(jù)為：4、8、15、21、21、24、25、28、34。 箱1：4、8、15 箱2：21、21、24 箱3：25、28、34（2）按箱平均值平滑： 箱1：9、9、9 箱2：22、22、22 箱3：29、29、292022/7/192022/7/19

18、37排序后的數(shù)據(jù)為：4、8、15、21、21、24、25、28、34。 箱1：4、8、15 箱2：21、21、24 箱3：25、28、34（3）按箱邊界值平滑： 箱1：4、4、15 箱2：21、21、24 箱3：25、25、34對于按箱邊值平滑來說，箱中的最大和最小值被視為箱邊界。箱中每一個值被最近的邊界值替換。2022/7/19382、回歸xyy = x + 1X1Y1Y12022/7/19393、通過自然劃分分段3-4-5規(guī)則可以將數(shù)值數(shù)據(jù)劃分成相對一致和“自然”區(qū)間。如果一個區(qū)間在最高有效位上包含3, 6, 7或9個不同的值，則將該區(qū)間劃分為3個區(qū)間（對于3、6和9劃分為3個等寬區(qū)間；對

19、于7，按2-3-2分組，劃分為3個區(qū)間）；如果最高有效位上包含2, 4或8個不同的值，則將區(qū)間劃分為4個等寬區(qū)間；如果最高有效位上包含1, 5或10個不同的值，則將區(qū)間劃分為5個等寬區(qū)間.2022/7/1940Example(-$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 - $5, 000)($2,000 - $3

20、,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) Maxcount(-$1,000 - $2,000)(-

21、$1,000 - 0)(0 -$ 1,000)Step 3:($1,000 - $2,000)2022/7/1941為什么要進行數(shù)據(jù)概化？數(shù)據(jù)庫通常存放有大量的細節(jié)數(shù)據(jù)，但我們通常希望看到的是以簡潔的、更一般的描述形式來觀察數(shù)據(jù)的特點。例如：對于一個銷售經(jīng)理來說，面對顧客數(shù)據(jù)庫，他可能不想考察每個顧客的事務，而更愿意概化到高層的數(shù)據(jù)，比如說，根據(jù)地區(qū)按顧客的分組匯總，來觀察每組顧客的購買頻率和顧客的收入，以此來分析區(qū)域差異。（三）數(shù)據(jù)概化2022/7/1942數(shù)據(jù)概化：是一個過程，它將大的任務相關的數(shù)據(jù)集從較低的概念層抽象到較高的概念層。使用概念分層，用高層次概念替換低層次“原始”數(shù)據(jù)。例如，

22、分類的屬性，“street”，可以概化為較高層的概念，如“city”或“country”；再如，“年齡”可以概化為“青年”、“中年”和“老年”等。2022/7/192022/7/1943四、元組的歸約為什么要進行離散化？在機器學習和數(shù)據(jù)挖掘中，已經(jīng)發(fā)展了處理離散型數(shù)據(jù)的很多算法，如決策樹、關聯(lián)規(guī)則及基于粗糙集理論的許多方法，而這些算法對于連續(xù)型數(shù)據(jù)卻不適用；另外，有些算法即使能處理連續(xù)型數(shù)據(jù)，挖掘和學習也沒有處理離散型數(shù)據(jù)有用和有效。離散化后可以達到歸約元祖的目的。2022/7/192022/7/1944連續(xù)屬性的離散化就是將數(shù)值屬性的值域劃分為若干子區(qū)間，每個區(qū)間對應一個離散值。離散化方法依

23、據(jù)不同的標準主要有以下幾種劃分：有監(jiān)督和無監(jiān)督、動態(tài)和靜態(tài)、全局和局部、自頂向下和自底向上等。2022/7/1945按照離散化過程中是否考慮類別信息，可以將離散化算法分為有監(jiān)督算法和無監(jiān)督算法。有監(jiān)督算法是其輸入樣本集中除了待離散化的數(shù)值屬性外，還有一個或多個離散型的類別屬性。這種算法在離散化時，將類別信息作為參考。無監(jiān)督離散化是在離散化過程中不考慮類別信息的方法，其輸入樣本集中僅含有待離散化的屬性。早期的等寬、等頻的離散化方法是無監(jiān)督方法的典型代表。無監(jiān)督的方法的缺陷在于它對分布不均勻的數(shù)據(jù)不適用，對異常點比較敏感。2022/7/191、有監(jiān)督離散化和無監(jiān)督離散化2022/7/19462、動

24、態(tài)和靜態(tài)離散化動態(tài)離散化方法是在建立分類模型的同時對連續(xù)特征進行離散化，例如，C4.5算法。在靜態(tài)離散化方法中，離散化是先于分類任務進行的。2022/7/1947自頂向下的方法是離散化開始于空的分割點（分裂點）列表，通過“分裂”區(qū)間增加新的分割點到列表中的離散化過程。自底向上是開始于屬性的全部連續(xù)值作為分割點的完全列表，以通過“合并”區(qū)間來移除它們中的一部分作為離散化的過程。2022/7/193、自頂向下和自底向上2022/7/19484、局部和全局離散化局部離散化方法是僅對每一個屬性的屬性值進行劃分，如等寬區(qū)間法、等頻區(qū)間法和最大熵法等。全局離散化則是考慮全部條件屬性的屬性值進行劃分的方法，

25、如全局聚類分析方法。2022/7/1949（二）典型離散化的過程一個局部單個屬性的離散化過程主要由以下四步組成（自底向上）：（1）對要離散化的屬性的連續(xù)值排序。（2）根據(jù)一定的規(guī)則產(chǎn)生候選斷點集，構造初始區(qū)間。（3）按照合并的規(guī)則，合并相鄰的初始區(qū)間。（4）制定停止標準，使得合并一直進行到符合停止標準為止。2022/7/192022/7/1950（三）離散化方法的評價（1）區(qū)間的總數(shù)。這是對模型簡潔性的要求。理論上來說，離散得到的區(qū)間數(shù)越少越好，便于理解；但區(qū)間數(shù)的減少另一方面也會導致數(shù)據(jù)的可理解性變差。（2）由離散化引起的不一致性的數(shù)目。所謂不一致性是指當兩個樣本所有的條件屬性取值相同而類別

26、屬性的取值不同時，就稱這兩個樣本是不一致的。離散化后的不一致性數(shù)目至少應該比在離散化前原始數(shù)據(jù)的不一致性數(shù)目少，且不一致性數(shù)目越少越好。（3）預測精確度。根據(jù)訓練樣本集預測新樣本類別的準確率即是預測精確度，預測精確度越高，當然就說明此離散化方法越好。2022/7/192022/7/19511、直方圖方法直方圖方法是將要離散化的變量值從小到大排序，然后對這些數(shù)值進行分組，最后，對這些進行賦值。依據(jù)分組的方式該方法又可以分為等寬和等頻兩種。等寬是指所分組是等距式分組。等頻是指所有的分組的次數(shù)是相等的。2022/7/19（四）具體的離散化方法2022/7/1952采用Iris樣本集進行統(tǒng)計模擬（數(shù)據(jù)

27、來源：加州大學UCI Machine Learning 的數(shù)據(jù)庫中Iris樣本集）。Iris樣本集是對3種鳶尾花：剛毛鳶(yuan)尾花、變色鳶尾花、佛吉尼亞鳶尾花各抽取50個樣本。屬性是sepal length in cm萼片長度、sepal width in cm萼片寬度、petal length in cm花瓣長度、petal width in cm花瓣寬度。2022/7/19等寬直方圖離散化的應用2022/7/1953我們現(xiàn)在以花萼長（ sepal length in cm ）屬性為例，來進行連續(xù)型值屬性的離散化。具體步驟為如下：（1）對要離散化的屬性的連續(xù)值排序。（2）根據(jù)一定的規(guī)則

28、產(chǎn)生候選斷點集，構造初始區(qū)間。2022/7/19542022/7/192022/7/1955（3）按照合并的規(guī)則，合并相鄰的初始區(qū)間。根據(jù)斯特杰公式有：n=1+3.3lgN=1+3.3lg1508那么，組距為 d=R/n =(7.9-4.3)/8=0.45現(xiàn)分組如右：2022/7/192022/7/1956（4）制定停止標準，使得合并一直進行到符合停止標準為止。（5）防止過度擬合。為防止過度擬合，應使得每個區(qū)間的頻數(shù)大于等于總體單位數(shù)的平方根。sqrt(150)122022/7/192022/7/19572022/7/1958進行重新分組：使得每個區(qū)間的頻數(shù)大于122022/7/192022/

29、7/19592、聚類聚類算法可以用來將數(shù)據(jù)劃分為群或簇。每一個簇形成概念分層的一個節(jié)點，而所有的節(jié)點在同一個概念層。每一個簇可以進一步分成若干子簇，形成較低的概念層簇也可以聚集在一起，以形成分層結構中較高的概念層。2022/7/192022/7/1960具體方法是：首先，將元組劃分為群或簇，使得在每一個簇中的對象“類似”，但與其他簇中的對象“不類似”。其次，為這些簇賦值，所有包含在同一個簇中的對象的值相同。注意：這種方法的有效性依賴于數(shù)據(jù)的性質，數(shù)據(jù)必須能夠組織成不同的聚類；另外，它只適用于無監(jiān)督的離散化。2022/7/1961例如：見IRIS樣本集，在不考慮類別信息的情況下，現(xiàn)用聚類方法離散

30、化屬性“sepal length in cm ”。有：2022/7/192022/7/19623、基于熵的離散化方法信息熵的概念信息論中的熵：是信息的度量單位，是一種 對屬性“不確定性的度量”。屬性的不確定性越大，把它搞清楚所需要的信息量也就越大，熵也就越大。Shannon公式： 其中，I(A)度量事件A發(fā)生所提供的信息量，稱之為事件A的自信息，P(A)為事件A發(fā)生的概率。2022/7/192022/7/1963如果一個屬性有N個可能的取值，且它們出現(xiàn)的概率分別為 ，那么這個屬性的信息熵為：一個系統(tǒng)越是有序，信息熵就越低。2022/7/1964貪心算法所謂貪心算法是指，在對問題求解時，總是做出

31、在當前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。2022/7/1965例如：假設有四種硬幣，它們的面值分別為二角五分、一角、五分和一分?，F(xiàn)在要找給某顧客六角三分錢。這時，我們會不假思索地拿出2個二角五分的硬幣，1個一角的硬幣和3個一分的硬幣交給顧客。這種找硬幣方法與其他的找法相比，所拿出的硬幣個數(shù)是最少的。這里，我們下意識地使用了這樣的找硬幣算法：首先選出一個面值不超過六角三分的最大硬幣，即二角五分；然后從六角三分中減去二角五分，剩下三角八分；再選出一個面值不超過三角八分的最大硬幣，即又一個二角五分，如此一直做下去。這個找硬幣的方法實際上就是貪

32、心算法。顧名思義，貪心算法總是作出在當前看來是最好的選擇。也就是說貪心算法并不從整體最優(yōu)上加以考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。2022/7/1966但是：如果硬幣的面值改為一分、五分和一角一分3種，而要找給顧客的是一角五分錢。還用貪心算法，我們將找給顧客1個一角一分的硬幣和4個一分的硬幣。然而3個五分的硬幣顯然是最好的找法。顯然貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當廣的許多問題它能產(chǎn)生整體最優(yōu)解。如，圖的單源最短路徑問題。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，但其最終結果卻是最優(yōu)解的很好的近似解。2022/7/1967基于熵的離散化方法是通過貪心算法

33、搜尋給定數(shù)據(jù)區(qū)間內的具有熵值最小的數(shù)據(jù)點作為斷點。該方法將區(qū)間內的每一個數(shù)值作為候選斷點，計算其熵值，然后從中選出具有最小熵值的數(shù)據(jù)點作為斷點，將區(qū)間一分為二，然后再對得到的區(qū)間遞歸地應用以上方法進行離散化。停止準則是當?shù)玫降拿總€區(qū)間中的類標簽都是一致時，即停止離散化過程；或者達到某個停止標準時，停止?；陟氐碾x散化方法2022/7/1968基于熵的離散化方法2022/7/19一個給定的樣本分類所需要的信息某種劃分的期望信息2022/7/19692022/7/19舉例：iris樣本集的具體步驟 2022/7/1970首先，從第一個分割點開始，將屬性值分為兩部分即4.3,4.4)和4.4,7.9

34、，則分割后新的類別熵為： 2022/7/192022/7/1971以此類推，如把屬性值分為4.3,5.6)和5.6,7,9兩個區(qū)間時，產(chǎn)生的新的類別熵為：2022/7/192022/7/1972對所有的分割點將屬性值分為兩個區(qū)間的新類別熵計算出來，有2022/7/192022/7/1973從上表中可以看到，將屬性值分為4.3,5.6)和5.6,7,9兩個區(qū)間時，類別熵最小，因此首先把屬性值分為兩大部分。按照上述步驟， 分別再找出區(qū)間 4.3,5.6)和5.6,7,9的二分點，以此類推，逐漸將區(qū)間分割為更小的區(qū)間，直到滿足某個終止條件為止。2022/7/192022/7/19742022/7/1

35、92022/7/19752022/7/194、chimerge算法2022/7/19762022/7/192022/7/19772022/7/192022/7/19782022/7/192022/7/1979應用采用Iris樣本集進行統(tǒng)計模擬?，F(xiàn)在以花萼長（ sepal length in cm ）屬性為例，來進行連續(xù)型值屬性的離散化。2022/7/192022/7/19802022/7/192022/7/1981具體步驟：（1）觀察各區(qū)間，先將類分布完全相同的區(qū)間進行合并。2022/7/192022/7/19822022/7/19（2）考察4.3,4.9)與4.9,5)，看其是否能夠合并？兩

36、區(qū)間的卡方統(tǒng)計量和為5.87，大于臨界值，因此兩區(qū)間不能合并。表1：兩區(qū)間的列聯(lián)表表2：計算各項的eij表3：兩區(qū)間的卡方統(tǒng)計量值2022/7/19832022/7/19（3）繼續(xù)考察區(qū)間4.9,5)與5.0,5.3) ，看其是否能夠合并，直到所有的區(qū)間卡方統(tǒng)計量大于閥值為止。2022/7/1984五、屬性的歸約屬性的歸約包括兩類方法：屬性的提取和屬性子集的選擇。（一）屬性的提取屬性的提取是通過映射（或變換）的方法，將高維的屬性空間壓縮為低維的屬性空間，即將原始屬性變換為較少的新屬性。此時，“較少的新屬性”是原始屬性的某種線性組合，也可以稱為“二次屬性”。2022/7/192022/7/198

37、5屬性提取的最大的優(yōu)點在于：這樣的線性組合比屬性選擇中的最優(yōu)子集有更好的判別能力。但相應的問題是，這樣的線性組合的實際意義卻不明顯，有時難以解釋。到目前為止，對屬性提取的研究主要是從線性和非線性的數(shù)據(jù)變換角度進行的。用的比較多的線性數(shù)據(jù)變換方法是：主成分分析、因子分析、判別分析、聚類分析、多維標度、投影尋蹤以及小波變換等。非線性的數(shù)據(jù)變換，主要是基于自組織映射的屬性抽取方法、基于核的主成分分析和基于核的判別分析方法等。2022/7/192022/7/19861、主成分分析（因子分析）主成分分析和因子分析都是多元統(tǒng)計分析中的一種常用方法，是數(shù)學上處理降維的一種方法。主成分分析的基本思想：設法將原

38、始屬性重新組合成一組新的互相無關的幾個綜合屬性，同時根據(jù)需要從中選取少數(shù)幾個綜合屬性來盡可能多地反映原來指標的信息。綜合指標的選取使用的是方差最大法。2022/7/192022/7/19872、因子分析因子分析的基本思想：通過變量（或樣本）的相關系數(shù)矩陣內部結構的研究，找出能控制所有變量的少數(shù)幾個因子去描述多個變量之間的相關關系；然后，根據(jù)相關性的大小把變量分組，使得同組內的變量之間相關性較高，但不同組之間相關性較低。2022/7/1988主成分分析和因子分析的對比2022/7/19主成分分析因子分析由因子的線性組合來解釋變量2022/7/1989主成份分析和因子分析的優(yōu)點因子（主成份）之間的

39、線性相關關系不顯著。主成份參與數(shù)據(jù)建模能夠有效地解決變量多重共線性等分析應用帶來的問題。因子能夠反映原有變量的絕大部分信息。因子的方差貢獻和方差貢獻率是衡量因子重要性的關鍵指標。該值越高，說明相應因子的重要性越高。aij因子載荷反映了某i個變量在第j因子上的相對重要性。因子得分是因子分析的最終體現(xiàn)。在后續(xù)的分析中可以用因子變量代替原有變量進行建模，或者利用因子變量對樣本分類、評價或排序等研究。2022/7/19903、聚類分析K均值聚類分析 K均值法是麥奎因（MacQueen，1967）提出的，這種算法的基本思想是將每一個樣品分配給最近中心（均值）的類中.具體的算法至少包括以下三個步驟：1將所

40、有的樣品分成K個初始類；2通過歐氏距離將某個樣品劃入離中心最近的類中，并對獲得樣品與失去樣品的類，重新計算中心坐標；3重復步驟2，直到所有的樣品都不能再分配時為止。2022/7/1991（二）屬性子集的選擇屬性子集的選擇是通過刪除不相關的屬性來減少數(shù)據(jù)量。屬性子集選擇的目標是找出最小屬性集，使得數(shù)據(jù)類的概率分布盡可能地接近使用所有屬性的原分布。2022/7/192022/7/1992屬性子集的選擇方法一般有兩個組成部分：一是高效率的屬性子集搜索策略，即在允許的時間內，用以找出最小的、最能描述類別的屬性組合的搜索方法；二是確定評價函數(shù)，是衡量屬性組合是否最優(yōu)的標準。屬性子集的選擇一般分兩步進行：

41、首先，產(chǎn)生屬性子集；然后，對子集進行評價，如果滿足停止條件則停止，否則重復前述兩步直到條件滿足為止。2022/7/19通過該標準，要能夠衡量哪組屬性子集的分類效果最好，即使得數(shù)據(jù)類的概率分布盡可能地接近使用所有屬性的原分布；或者能夠衡量哪組屬性子集的分類效果最好，即最能夠代表全部的屬性集合對樣本的劃分。2022/7/19931、搜索策略按照搜索屬性形成屬性子集的方式，搜索策略可以分為：窮舉法、啟發(fā)式和隨機搜索。啟發(fā)式搜索即貪心算法?；镜膯l(fā)式屬性選擇算法主要有：逐步向前選擇（SFS）、逐步向后選擇（SBG ）以及向前選擇和向后刪除相結合的方法等。2022/7/192022/7/1994（1）

42、逐步向前選擇逐步向前選擇方法是一種自下而上的搜索方法，它是由空屬性集開始，依次從未入選的屬性中選擇一個屬性，使它與已入選的屬性組合在一起時所得的評價函數(shù)達到最大值（或最小值，依評價函數(shù)選取的不同，取最大或最小值），直到評價函數(shù)的值不再增加（或減小）時為止，亦或者達到指定的屬性數(shù)為止。2022/7/1995能夠衡量哪組屬性子集的分類效果最好，最能夠代表全部的屬性集合對樣本的劃分。2022/7/1995這種算法的不足是：在算法中雖然考慮了所選屬性與已入選屬性之間的相關性，但卻未考慮未入選屬性之間的統(tǒng)計相關性，并且一旦某個屬性已入選，即使由于后加入的屬性使它變?yōu)槎嘤啵矡o法再剔除。2022/7/1996