數(shù)據(jù)挖掘與生物醫(yī)學(xué)應(yīng)用作業(yè) 楊帆

1、數(shù)據(jù)挖掘與生物醫(yī)學(xué)應(yīng)用作業(yè) 姓名：楊帆 學(xué)號： B110903141. 請用分箱方法對向量3, 6, 7, 15, 11, 40, 33, 20, 30進(jìn)行清除噪聲處理。要求是分別使用等深度和等寬度分割，然后再分別使用均值、中值和邊界平滑。答：等深度分割： 分類一：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. 請用表一所示數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，給出構(gòu)建分類預(yù)測模型的步驟。用表二所示數(shù)據(jù)作為測試數(shù)據(jù)，給出預(yù)測每個人是否為終身教授(Tenured)的步驟。表一表二答：分為兩步：一，構(gòu)建基于訓(xùn)練數(shù)據(jù)的模型； 在測試樣本數(shù)據(jù)時，我們以樣本的Years和Rank兩個屬相值為評判標(biāo)準(zhǔn)，來獲得訓(xùn)練模型。在上述的實驗中，我們對表一進(jìn)行訓(xùn)練，得出模型的訓(xùn)練標(biāo)準(zhǔn)為Rank屬性為Professor或者Years屬性值大于6時，我們判斷該目標(biāo)的Tenured為Yes，否則，為No 二，使用構(gòu)建模型預(yù)測目標(biāo)的類型或特征值。 將表二中的數(shù)據(jù)帶入訓(xùn)練模型，通過判斷其Rank和Years屬性是否符合判斷

4、標(biāo)準(zhǔn)，斷定其Tenured屬性。 則結(jié)果：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. 請用年齡、是否為學(xué)生以及信用等級為屬性構(gòu)建一棵決策樹，用于判斷能否批準(zhǔn)客戶的信用卡申請。答：決策樹(Decision Tree）是在已知各種情況發(fā)生概率的基礎(chǔ)上，通過構(gòu)

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

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

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

8、將不確定的內(nèi)容轉(zhuǎn)為確定的內(nèi)容，因此信息伴著不確定性。出處：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決策樹能夠根據(jù)決策樹生成一系列規(guī)則集,我們可以把一顆決策樹看成一系列規(guī)則的組合。一個規(guī)則對應(yīng)著從根節(jié)點到葉子節(jié)點的路徑，該規(guī)則的條件是路徑上的條件，結(jié)果是葉子節(jié)點的類別。C4.5首先根據(jù)決策樹的每個葉

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

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

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

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

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

14、要是選擇分割訓(xùn)練集 當(dāng) major=”science” ：S11=84 , S12=42 I(S11,S12)= -84126log284126-42126log242126 =0.9183 當(dāng) major=”engineering” ：S21=36, S22=46I(S21,S22)= -3682log23682-4682log24682 =0.9892當(dāng) 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作為當(dāng)前的最佳測試屬性。7. 請使用樸素貝葉斯分類方法對同學(xué)X做出其是否能夠買電腦的判斷，其中同學(xué)X的年

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

17、給定的數(shù)據(jù)樣本為蘋果的概率,而不管數(shù)據(jù)樣本看上去如何。 P(X | H) 是條件 H 下,X 的后驗概率。 已知 X 是蘋果,X 是紅色并且是圓的的概率。 P(X)是 X 的先驗概率。 由我們的水果集取出一個數(shù)據(jù)樣本是紅的和圓的的概率。 由公式（1）可知P(Ci|X)=PCiXP(H)P(X) (2)當(dāng)Ci之間相互獨立，i（0 ， n）則P(X|Ci)=k=1nP(Xk|Ci) (3) 如果是連續(xù)值屬性,則通常假定該屬性服從高斯分布。因而 P(Xk|Ci)=g(Xk, Ci, Ci)=12Cie-(x-Ci)22Ci2 (4)所以結(jié)果如下：給出一個實例進(jìn)行分類： 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所以，對于同學(xué)X buys_computer=yes8. 請簡要描述K均值聚類方法的原理。答：對于K均值的劃分方法當(dāng)結(jié)果簇是密集的,而簇與簇之間區(qū)別明顯時,它的效果較好。 對處理大數(shù)據(jù)集,該

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

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