【文章內容簡介】 集）。 ? Iris樣本集是對 3種鳶尾花：剛毛鳶 (yuan)尾花、變色鳶尾花、佛吉尼亞鳶尾花各抽取 50個樣本。屬性是sepal length in cm萼片長度 、 sepal width in cm萼片寬度、 petal length in cm花瓣長度、 petal width in cm花瓣寬度。 2020/9/15 等寬直方圖離散化的應用 54 ?我們現(xiàn)在以花萼長（ sepal length in cm ）屬性為例，來進行連續(xù)型值屬性的離散化。 具體步驟為如下： ?（ 1）對要離散化的屬性的連續(xù)值排序。 ?（ 2）根據(jù)一定的規(guī)則產生候選斷點集，構造初始區(qū)間。 2020/9/15 55 2020/9/15 2020/9/15 數(shù)值 頻數(shù) 數(shù)值 頻數(shù) 數(shù)值 頻數(shù) 數(shù)值 頻數(shù) 數(shù)值 頻數(shù) 1 5 10 8 7 1 3 9 7 5 3 1 4 3 2 1 4 1 6 6 8 1 2 6 6 3 1 5 7 4 4 4 6 6 9 7 1 1 56 2020/9/15 （ 3）按照合并的規(guī)則，合并相鄰的初始區(qū)間。 ? 根據(jù)斯特杰公式有：n=1+=1+≈8 ? 那么， 組距為 d=R/n =()/8= ? 現(xiàn)分組如右： 2020/9/15 分組 頻數(shù) ~ 11 ~ 30 ~ 24 ~ 24 ~ 31 ~7 17 7~ 7 ~ 6 57 2020/9/15 ?（ 4）制定停止標準，使得合并一直進行到符合停止標準為止。 ?（ 5）防止過度擬合。 ? 為防止過度擬合，應使得每個區(qū)間的頻數(shù)大于等于總體單位數(shù)的平方根。 ? 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 進行重新分組：使得每個區(qū)間的頻數(shù)大于 12 2020/9/15 分組 頻數(shù) 賦值 ~ 41 1 ～ 48 2 ~7 48 3 7~ 13 4 60 2020/9/15 聚類 ?聚類算法可以用來將數(shù)據(jù)劃分為群或簇。 ?每一個簇形成概念分層的一個節(jié)點，而所有的節(jié)點在同一個概念層。每一個簇可以進一步分成若干子簇，形成較低的概念層簇也可以聚集在一起，以形成分層結構中較高的概念層。 2020/9/15 61 ?具體方法是： ? 首先，將元組劃分為群或簇，使得在每一個簇中的對象“類似”，但與其他簇中的對象“不類似”。 ? 其次，為這些簇賦值，所有包含在同一個簇中的對象的值相同。 ?注意：這種方法的有效性依賴于數(shù)據(jù)的性質，數(shù)據(jù)必須能夠組織成不同的聚類；另外，它只適用于無監(jiān)督的離散化。 2020/9/15 62 2020/9/15 ? 例如：見 IRIS樣本集，在不考慮類別信息的情況下，現(xiàn)用聚類方法離散化屬性“ sepal length in cm ”。有： 2020/9/15 分組 頻數(shù) 賦值 ~ 46 1 ~ 37 2 ~ 32 3 ~ 35 4 63 2020/9/15 基于熵的離散化方法 ?信息熵的概念 ? 信息論中的熵：是信息的度量單位，是一種 對屬性“不確定性的度量” 。屬性的不確定性越大，把它搞清楚所需要的信息量也就越大，熵也就越大。 ? Shannon公式： 其中， I(A)度量事件 A發(fā)生所提供的信息量，稱之為事件A的自信息， P(A)為事件 A發(fā)生的概率。 2020/9/15 ( ) l og ( )I A p A?? 64 ?如果一個屬性有 N個可能的取值，且它們出現(xiàn)的概率分別為 ，那么這個屬性的信息熵為： ?一個系統(tǒng)越是有序，信息熵就越低。 2020/9/15 65 1l o gNiiiH p p??? ?12, , , Np p p?貪心算法 ?所謂貪心算法是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。 2020/9/15 66 ?例如： 假設有四種硬幣，它們的面值分別為二角五分、一角、五分和一分。現(xiàn)在要找給某顧客六角三分錢。 ? 這時，我們會不假思索地拿出 2個二角五分的硬幣， 1個一角的硬幣和 3個一分的硬幣交給顧客。這種找硬幣方法與其他的找法相比，所拿出的硬幣個數(shù)是最少的。 ? 這里，我們下意識地使用了這樣的找硬幣算法：首先選出一個面值不超過六角三分的最大硬幣，即二角五分；然后從六角三分中減去二角五分，剩下三角八分；再選出一個面值不超過三角八分的最大硬幣，即又一個二角五分，如此一直做下去。 ? 這個找硬幣的方法實際上就是貪心算法。顧名思義，貪心算法總是作出在當前看來是最好的選擇。也就是說貪心算法并不從整體最優(yōu)上加以考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。 2020/9/15 67 ?但是： ?如果硬幣的面值改為一分、五分和一角一分 3種，而要找給顧客的是一角五分錢。還用貪心算法，我們將找給顧客 1個一角一分的硬幣和 4個一分的硬幣。然而 3個五分的硬幣顯然是最好的找法。 ?顯 然貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當廣的許多問題它能產生整體最優(yōu)解。 如，圖的單源最短路徑問題 。 ?在一些情況下，即使貪心算法不能得到整體最優(yōu)解，但其最終結果卻是最優(yōu)解的很好的近似解。 2020/9/15 68 ?基于熵的離散化方法是通過貪心算法搜尋給定數(shù)據(jù)區(qū)間內的具有熵值最小的數(shù)據(jù)點作為斷點。 ?該方法將區(qū)間內的每一個數(shù)值作為候選斷點，計算其熵值，然后從中選出具有最小熵值的數(shù)據(jù)點作為斷點，將區(qū)間一分為二，然后再對得到的區(qū)間遞歸地應用以上方法進行離散化。 ?停止準則是當?shù)玫降拿總€區(qū)間中的類標簽都是一致時，即停止離散化過程；或者達到某個停止標準時，停止。 2020/9/15 69 ?基于熵的離散化方法 2020/9/15 基于熵的離散化方法 2020/9/15 一個給定的樣本分類所需要的信息 某種劃分的期望信息 70 項目 性別 年齡 學生身分 收入 辦卡 1 男 45 否 高 會 2 女 31~45 否 高 會 3 女 20~30 是 低 會 4 男 20 是 低 不會 5 女 20~30 是 中 不會 6 女 20~30 否 中 會 7 女 31~45 否 高 會 8 男 31~45 是 中 不會 9 男 31~45 否 中 會 10 女 20 是 低 會 2020/9/15 Sepallen:(cm) d1 d2 d3 Sepallen:(cm) d1 d2 d3 1 0 0 0 4 2 3 0 0 0 2 2 1 0 0 0 3 6 4 0 0 0 2 5 2 0 0 0 1 4 5 0 0 0 2 0 4 1 1 0 3 5 5 8 2 0 0 1 2 8 1 0 0 1 3 3 1 0 7 0 1 0 1 0 0 0 0 1 5 1 0 0 0 3 2 5 0 0 0 1 0 5 1 0 0 1 2 5 1 0 0 1 1 3 3 0 0 4 0 2 1 0 0 1 6 0 4 2 2020/9/15 舉例： IRIS樣本集的具體步驟 71 2020/9/15 ? 首先，從第一個分割點開始，將屬性值分為兩部分即[,)和 [,]，則分割后新的類別熵為： 2020/9/15 區(qū)間 d1 d2 d3 合計 [,) 1 0 0 1 [,] 49 50 50 149 1212( , 。 ) ( ) ( )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]兩個區(qū)間時，產生的新的類別熵為： 2020/9/15 區(qū)間 d1 d2 d3 合計 [,) 47 11 1 59 [,] 3 39 49 91 1212( , 。 ) ( ) ( )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 ? 對所有的分割點將屬性值分為兩個區(qū)間的新類別熵計算出來，有 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 1 0 5 1 0 0 0 1 2 5 0 0 0 3 0 5 1 0 0 1 2 5 1 0 0 1 1 3 3 0 0 1 0 2 1 0 0 4 0 0 1 74 2020/9/15 ?從上表中可以看到，將屬性值分為 [,)和[,7,9]兩個區(qū)間時，類別熵最小，因此首先把屬性值分為兩大部分。 ?按照上述步驟， 分別再找出區(qū)間 [,)和[,7,9]的二分點，以此類推，逐漸將區(qū)間分割為更小的區(qū)間，直到滿足某個終止條件為止。 2020/9/15 75 2020/9/15 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 1 0 5 1 0 0 0 1 2 5 0 0 0 3 0 5 1 0 0 1 2 5 1 0 0 1 1 3 3 0 0 1 0 2 1 0 0 4 0 0 1 76 2020/9/15 2020/9/15 CHIMERGE算法 77 2020/9/15 2020/9/15 78 Sepallen:(cm) d1 d2 d3 Sepallen:(cm) d1 d2 d3 1 0 0 0 4 2 3 0 0 0 2 2 1 0 0 0 3 6 4 0 0 0 2 5 2 0 0 0 1