1、數據挖掘與生物醫學應用作業 姓名：楊帆 學號： B110903141. 請用分箱方法對向量3, 6, 7, 15, 11, 40, 33, 20, 30進行清除噪聲處理。要求是分別使用等深度和等寬度分割，然后再分別使用均值、中值和邊界平滑。答：等深度分割： 分類一：3 6 7 分類二：11 15 20 分類三：30 33 40 均值平滑: 5 5 5 15 15 15 34 34 34 中值平滑: 6 6 6 15 15 15 33 33 33 邊界平滑: 3 7 7 11 11 20 30 30 40 等寬度分割： 分類一：3 6 7 11 3 ,14 分類二： 15 20 15 ,26 分

2、類三：30 33 40 27 ,40 均值平滑： 7 7 7 7 18 18 34 34 34 中值平滑： 7 7 7 7 18 18 33 33 33 邊界平滑： 3 3 3 14 15 15 27 27 40 2. 用直方圖表示價格向量1, 1, 5, 5, 5, 6, 6, 8, 8, 10, 10, 10, 12, 13, 13, 14, 15, 16, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 18, 20, 20, 22, 22, 23, 23, 25, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 3

3、0, 30, 30。答： 3. 請用表一所示數據作為訓練數據，給出構建分類預測模型的步驟。用表二所示數據作為測試數據，給出預測每個人是否為終身教授(Tenured)的步驟。表一表二答：分為兩步：一，構建基于訓練數據的模型； 在測試樣本數據時，我們以樣本的Years和Rank兩個屬相值為評判標準，來獲得訓練模型。在上述的實驗中，我們對表一進行訓練，得出模型的訓練標準為Rank屬性為Professor或者Years屬性值大于6時，我們判斷該目標的Tenured為Yes，否則，為No 二，使用構建模型預測目標的類型或特征值。 將表二中的數據帶入訓練模型，通過判斷其Rank和Years屬性是否符合判斷

4、標準，斷定其Tenured屬性。 則結果：Tom Rank屬性不是Professor且Years屬性為2，故其Tenured屬性為No； Merlisa Rank屬性不是Professor但Years屬性為7，故其Tenured屬性為Yes； George Rank屬性是Professor故其Tenured屬性為Yes； Joseph Rank屬性不是Professor但Years屬性為7，故其Tenured屬性為Yes；4. 請用年齡、是否為學生以及信用等級為屬性構建一棵決策樹，用于判斷能否批準客戶的信用卡申請。答：決策樹(Decision Tree）是在已知各種情況發生概率的基礎上，通過構

5、成決策樹來求取凈現值的期望值大于等于零的概率，評價項目風險，判斷其可行性的決策分析方法，是直觀運用概率分析的一種圖解法。由于這種決策分支畫成圖形很像一棵樹的枝干，故稱決策樹。在本題中，我們對一個目標的年齡、是否為學生以及信用等級來作為判斷標準進行評判。在這三個屬性中，很明顯年齡屬性可以包含其余兩個屬性，因此我們將其作為決策樹的根節點。對于大部分人小于30歲的一般為學生或者剛畢業，要對其進行是否學生的評判。30到40歲的人一般都有工作，默認其有能力申請信用卡。而大于40歲的人一般都已經建立了自己的信用等級，可以根據這個判斷能否申請信用卡。具體的決策樹如下：年齡 ? >40 <3030

6、-40信用等級 ?學生?是 否是優良一般否否否 否 5. 請查閱相關文獻后給出決策樹發展歷史上有哪些重要的決策樹算法？并簡要描述其基本原理，并給出相關文獻的出處。答：（一）：第一個關于決策樹的算法 E. B. Hunt, J. Marin, and P. T. Stones book “Experiments in Induction” published by Academic Press in 1966原理：從一個空的決策樹出發，通過添加新的判定節點來完善 原有的決策樹，直到新的決策樹能夠正確地將訓練實例分類為止。它從一組無次序、無規則的元組中推理出決策樹表示形式的分類規則。它采用自頂向下

7、的遞歸方式，在決策樹的內部結點進行屬性值的比較，并根據不同的屬性值從該結點向下分支，葉結點是要學習劃分的類。從根到葉結點的一條路徑就對應著一條合取規則，整個決策樹就對應著一組析取表達式規則。（二）：第一個引起廣泛關注的決策樹算法 - ID3原理：ID3采用貪心方法，其中決策樹以自頂向下遞歸的分治方式構造。大多數決策樹歸納算法都沿用這種自頂向下的方法，從訓練元組集和它們的相關聯的類標號開始構造決策樹。隨著樹的構建，訓練集遞歸地劃分成較小的子集。ID3算法中關鍵的一步是屬性選擇度量，即選擇分裂準則。其中的三種度量方法分別是信息增益、增益率和Gini指標。（示例算法選擇了第一種方法）。當獲取信息時，

8、將不確定的內容轉為確定的內容，因此信息伴著不確定性。出處：J. R. Quinlans paper in a book “Expert Systems in the Micro Electronic Age” edited by D. Michie, published by Edinburgh University Press in 1979（三）：最流行的決策樹算法 - C4.5原理：C4.5決策樹能夠根據決策樹生成一系列規則集,我們可以把一顆決策樹看成一系列規則的組合。一個規則對應著從根節點到葉子節點的路徑，該規則的條件是路徑上的條件，結果是葉子節點的類別。C4.5首先根據決策樹的每個葉

9、子節點生成一個規則集，對于規則集中的每條規則，算法利用“爬山”搜索來嘗試是否有條件可以移除，由于移除一個條件和剪枝一個內部節點本質上是一樣的，因此前面提到的悲觀剪枝算法也被用在這里進行規則簡化。MDL準則在這里也可以用來衡量對規則進行編碼的信息量和對潛在的規則進行排序。簡化后的規則數目要遠遠小于決策樹的葉子節點數。根據簡化后的規則集是無法重構原來的決策樹的。規則集相比決策樹而言更具有可操作性，因此在很多情況下我們需要從決策樹中推理出規則集。C4.5有個缺點就是如果數據集增大了一點，那么學習時間會有一個迅速地增長。出處：J. R. Quinlans book “C4.5: Programs fo

10、r Machine Learning” published by Morgan Kaufmann in 1993（四）：最流行的用于回歸的決策樹算法 CART原理：CART算法采用一種二分遞歸分割的技術，將當前的樣本集分為兩個子樣本集，使得生成的的每個非葉子節點都有兩個分支。因此，CART算法生成的決策樹是結構簡潔的二叉樹。出處：L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stones book “Classification and Regression Trees” published by Wadsworth in 1984（五

11、）：目前最強的基于決策樹的算法 隨機森林 原理：簡單的說，隨機森林就是用隨機的方式建立一個森林，森林里面有很多的決策樹組成，隨機森林里的每一顆決策樹之間是沒有關聯的，在得到森里之后，當有一個新的輸入進入樣本的時候，就讓森里中的每一顆決策樹進行一下判斷，看看這個樣本應該屬于那一類（對于分類算法），然后看看那一類被選擇最多，就預測這個樣本為那一類。而隨機森林的算法主要包括決策樹的生長和投票過程。出處：L. Breimans MLJ01 paper “Random Forests” 6. 在構建決策樹時，如何選擇屬性作為當前節點的測試屬性對最終結果有著重要的影響。現在表三和表四中給出兩組不同學生的相

12、關信息，要求用信息增益度量的方法計算出選擇哪種屬性才是最佳的當前測試屬性。表三表四答： 對于信息增益度量的方法即選擇具有最高信息增益(或最大熵壓縮)的屬性作為當前結點的測試屬性。該屬性使得對結果劃分中的樣本分類所需的信息量最小,并反映劃分的最小隨機性或 “不純性”。 對一個給定的樣本分類所需的期望信息由下式給出 I(S1,S2，···，Sm) =-i=1mSiSlog2SiS其中：S 是 數據樣本的總集合 si 是 類別Ci的訓練樣本 (i=1,2, , m)aj是屬性A的值 (j=1,2, , v)設屬性 A 具有 v 個不同值a1 ,., av。可以用屬性 A

13、 將 S 劃分為 v 個S1 ,.,Sv;其中, Sj包含 S 中這樣一些樣本,它們在 A 上具有值 aj 設 sij是子集 Sj中類 Ci的樣本數，則根據 A劃分子集的熵或期望信息式給出: Ent(A)=i=1ySiAS-j=1mSijASiAlog2SijASiA基于屬性A的信息增益為 ：Gain(A)= I(S1,S2，···，Sm)- Ent(A)信息增益值越大，屬性A用于分類的效果就越好 所以要正確分類的訓練集的信息是I(S1,S2)=I(120,130)=-120250log2120250-130250log2130250=0.9988假設major主

14、要是選擇分割訓練集 當 major=”science” ：S11=84 , S12=42 I(S11,S12)= -84126log284126-42126log242126 =0.9183 當 major=”engineering” ：S21=36, S22=46I(S21,S22)= -3682log23682-4682log24682 =0.9892當 major=“business” : S31=0, S32=42I(S31,S32)=0所以major的熵：E(major)=126250I(S11,S12)+82250I(S21,S22)+42250I(S31,S32)=0.7873主

15、要的信息增益：Gain(major)=I(S1,S2)-E(major)=0.2115我們還可以得到屬性的信息增益:Gain(gender)=0.0003 Gain(birth_country)=0.0407 Gain(gpa)=0.4490 Gain(age_range)=0.5971通過比較：Gain(age_range)> Gain(gpa)> Gain(major)> Gain(birth_country)> Gain(gender)所以選擇age_range作為當前的最佳測試屬性。7. 請使用樸素貝葉斯分類方法對同學X做出其是否能夠買電腦的判斷，其中同學X的年

16、齡小于30，收入為medium，行用等級為fair，訓練數據如表五所示。表五答：貝葉斯分類是一種統計學分類方法，基于貝葉斯法則可以預測類成員關系的可能性，如給定樣本屬于一個特定類的概率。其中貝葉斯法則公式如下：P(H|X)=PHXP(H)P(X) （1）其中： P(H | X ) 是后驗概率,或條件 X 下, H 的后驗概率。 例如,假定數據樣本世界由水果組成,用它們的顏色和形狀描述。假定 X 表示紅色和圓的,H 表示假定 X 是蘋果,則 P(H | X ) 反映當我們看到 X 是紅色并是圓的時,我們對 X 是蘋果的確信程度. P(H)是先驗概率,或 H 的先驗概率。 對于上面的例子,它是任意

17、給定的數據樣本為蘋果的概率,而不管數據樣本看上去如何。 P(X | H) 是條件 H 下,X 的后驗概率。 已知 X 是蘋果,X 是紅色并且是圓的的概率。 P(X)是 X 的先驗概率。 由我們的水果集取出一個數據樣本是紅的和圓的的概率。 由公式（1）可知P(Ci|X)=PCiXP(H)P(X) (2)當Ci之間相互獨立，i（0 ， n）則P(X|Ci)=k=1nP(Xk|Ci) (3) 如果是連續值屬性,則通常假定該屬性服從高斯分布。因而 P(Xk|Ci)=g(Xk, Ci, Ci)=12Cie-(x-Ci)22Ci2 (4)所以結果如下：給出一個實例進行分類： X=(age=<30，i

18、ncome=medium,student=yes,credit_rating=fair)P(Ci): P(C1)=(buys_computer=yes)=9/14=0.643 P(C2)=(buys_computer=no)=5/14=0.357P(X|Ci): since P(age=<30|buys_computer=yes)=0.222 P(age=<30|buys_computer=no)=0.6 P(incomen=medium|buys_computer=yes)=0.444 P(income=medium|buys_computer=no)=0.4 P(student

19、=yes|buys_computer=yes)=0.667 P(student=yes|buys_computer=no)=0.2 P(credit_rating=fair|buys_computer=yes)=0.667 P(credit_rating=fair|buys_computer=no)=0.4 Then P(X|C1)=0.044 P(X|C2)=0.016P(X|Ci)P(Ci)=0.007所以，對于同學X buys_computer=yes8. 請簡要描述K均值聚類方法的原理。答：對于K均值的劃分方法當結果簇是密集的,而簇與簇之間區別明顯時,它的效果較好。 對處理大數據集,該

20、算法是相對可伸縮的和高效率的。 要求用戶必須事先給出 k(待生成簇的數目)不適合發現大小差別很大的簇。 對于“噪音”和孤立點數據是敏感的,少量的該類數據能夠對平均值產生極大的影響。 因此可分為五步來進行：(1) 任意選擇k個對象作為初始的簇中心(2) 根據與每個中心的距離，將每個對象賦給最近的簇(3) 重新計算每個簇的均值并將其作為新蔟中心點; （4）根據與每個新中心的距離,重新將每個對象賦給“最近”的簇;（5）不斷循環（3）-（4）直至每個簇的中心點不再變化。9. 在模型數目已知和未知兩種情況下，給出如何使用高斯混合模型方法(GMM)計算模型高斯參數的步驟。答： 已知高斯密度函數如下：P(x

21、)=1(2)k2|12e-12x-1（x-） （1） 對上式等號兩邊取自然對數結果如下：lnP(x|,)=-12（ln2+ln|+（x-）-1（x-） （2） （1）當模型已知時： 通過 最大化密度函數以求得高斯模型的參數 N（，） 使用最大似然函數法結果如下：xUlnP(x|,) xlnPx,/=0xlnPx,/=0=1NP,=1NP,(-)(-) N=XP(X|,) （2）當模型數目未知時使用期望最大算法： (1) 根據貝葉斯法則計算后驗概率： Cx=arg maxi=1,2,3P(x|ui,i)wi (2)首先假定模型和參數：（1，1，w1=1k）,···，（k，k，wk=1k） (3)每一個對象歸類為其后驗概率值最大的類: Cx=arg maxi=1,···，kP(x|ui,i)wi(4