第二章 分類方法 王海

內容提要 分類的基本概念與步驟 分類的常用方法 基於距離的分類方法 決策樹分類方法 組合分類 貝葉斯分類 Logistic回歸分類 支持向量機分類 分類有關的問題

分類是數據挖掘中重要的任務 分類的目的是學會一個分類器（分類函數或模型），該分類器能 把待分類的數據映射到給定的類別中。 分類可用於預測。從利用歷史數據紀錄中自動推導出對給定數據 的推廣描述，從而能對未來數據進行類預測。 分類具有廣泛的應用，例如醫療診斷、信用卡系統的信用分級、 圖像模式識別等。 分類器的構造依據的方法很廣泛： 統計方法：包括貝葉斯法和非參數法等。 機器學習方法：包括決策樹法和規則歸納法。 神經網路方法。 其他，如粗糙集等。

分類——一個兩步過程 第一步，建立一個模型，描述預定數據類集和概念集 第二步，使用模型，對將來的或未知的對象進行分類 假定每個元組屬於一個預定義的類，由一個類標號屬性確定 基本概念 訓練數據集：由為建立模型而被分析的數據元組形成 訓練樣本：訓練數據集中的單個樣本（元組） 學習模型可以用分類規則、判定樹或數學公式的形式提供 第二步，使用模型，對將來的或未知的對象進行分類 首先評估模型的預測準確率 對每個測試樣本，將已知的類標號和該樣本的學習模型類預測比較 模型在給定測試集上的準確率是正確被模型分類的測試樣本的百分比 測試集要獨立於訓練樣本集，否則會出現“過分適應數據”的情況

第一步——建立模型 分類演算法 訓練數 據集 分類規則 IF rank = ‘professor’ OR years > 6 THEN tenured = ‘yes’

第二步——用模型進行分類 分類規則 測試集 未知數據 (Jeff, Professor, 4) Tenured?

應用案例—垃圾郵件處理 案例闡述：對於企業和個人，如何處理垃圾郵件都是很頭疼的一件事情。在磐石公司開發的磐郵 系統中，每個客戶可以有300G的郵件儲存容量，雖然有足夠的容量容納垃圾郵件，但是沒有過濾 掉的垃圾郵件仍然會造成糟糕的用戶體驗。表述問題：如何對每個郵箱中收到的每封郵件進行處 理，將有用郵件保留而過濾掉垃圾郵件是用戶關心的一大問題。 解決問題：目前的垃圾郵件過濾方 法主要是採用文本挖掘技術（Text Mining）。作為數據挖掘的重要分支， 文本挖掘在數據挖掘傳統方法的基礎 上引入了語義處理等其他學科知識。 在垃圾郵件過濾的分類技術中最常見 的是貝葉斯分類法。貝葉斯分類法主 要是通過對郵件的信封標題、主題和 內容進行掃描和判別。 垃圾郵件

應用案例—信用卡分級 案例闡述：現如今金融行業的競爭異常激烈。在美國，出現在每一家郵箱裏最多的信件恐 怕就是信用卡邀請信。如何吸引合適的用戶來使用信用卡，以及準確分析申請人的信用風險， 是每個商業銀行最關注也是最頭痛的事情。銀行要不惜一切代價吸引低風險高價值的客戶， 但是對於高風險的信用卡申請者要儘量避免。 表述問題：如何把信用卡申請者分類為低、中、高風險。 解決問題：需要建設客戶 風險模型對客戶的風險進行分 類。整個建模過程與直郵營銷 類似。不過因為行業的特殊性， 申請表中包含了大量關於用戶 的個人資訊，再加上通常會做 的客戶信用查詢，可以用來參 考的數據維度更多一些，所以 相對來說建模的精准度也會高 很多。

內容概要 分類的基本概念與步驟 分類的常用方法 基於距離的分類方法 決策樹分類方法 組合分類 貝葉斯分類 Logistic回歸分類 支持向量機分類 分類有關的問題

1.基於距離的分類方法的思路 用距離來表徵相似性，距離越近，相似性越大，距離越遠，相似 性越小。 （a）類定義 （b）待分類樣例 （c）分類結果

K-近鄰分類算法 K-近鄰分類算法（K Nearest Neighbors，簡稱KNN）通過計算每個訓練數據 到待分類元組的距離，取和待分類元組距離最近的K個訓練數據，K個數據 中哪個類別的訓練數據占多數，則待分類元組就屬於哪個類別。 演算法 4-2 K-近鄰分類算法 輸入： 訓練數據T；近鄰數目K；待分類的元組t。 輸出： 輸出類別c。 （1）N=； （2）FOR each d ∈T DO BEGIN （3） IF |N|≤K THEN （4） N=N ∪{d}； （5） ELSE （6） IF  u ∈N such that sim(t，u) < sim(t，d) THEN BEGIN （7） N=N - {u}； （8） N=N ∪{d}； （9） END （10）END （11）c=class to which the most u ∈N.

KNN：舉例 高度”用於計算距離，K=5，對<Pat，女，1.6>分類？ 姓名 性別 身高(米) 類別 姓名 性別 身高(米) 類別 Kristina 女 1.6 矮 Jim 男 2 高 Maggie 女 1.9 中等 Martha 女 1.88 中等 Stephanie 女 1.7 矮 Bob 男 1.85 中等 Kathy 女 1.6 矮 Dave 男 1.7 矮 Worth 男 2.2 高 Steven 男 2.1 高 Debbie 女 1.8 中等 Todd 男 1.95 中等 Kim 女 1.9 中等 Amy 女 1.8 中等 Wynette 女 1.75 中等 高度”用於計算距離，K=5，對<Pat，女，1.6>分類？

KNN：舉例 對T前K=5個記錄，N={<Kristina，女， 1.6>、< Jim，男，2>、< Maggie，女，1.9>、< Martha，女，1.88>和< Stephanie，女，1.7>}。 對第6個記錄d=< Bob，男，1.85>，得到N={<Kristina，女， 1.6>、< Bob，男，1.85>、< Maggie，女，1.9>、< Martha，女，1.88>和< Stephanie，女，1.7>}。 對第7個記錄d=< Kathy，女，1.6>，得到N={<Kristina，女， 1.6>、< Bob，男，1.85>、< Kathy，女，1.6>、< Martha，女，1.88>和< Stephanie，女，1.7>}。 對第8個記錄d=< Dave，男，1.7>，得到N={<Kristina，女， 1.6>、< Dave，男，1.7>、< Kathy，女，1.6>、< Martha，女，1.88>和< Stephanie，女，1.7>}。 對第9和10個記錄，沒變化。 對第11個記錄d=< Debbie，女，1.8>，得到N={<Kristina，女， 1.6>、< Dave，男，1.7>、< Kathy，女，1.6>、< Debbie，女，1.8>和< Stephanie，女，1.7>}。 對第12到14個記錄，沒變化。 對第15個記錄d=< Wynette，女，1.75>，得到N={<Kristina，女， 1.6>、< Dave，男，1.7>、< Kathy，女，1.6>、< Wynette，女，1.75>和< Stephanie，女，1.7>}。 姓名 性別 身高(米) 類別 Kristina 女 1.6 矮 Jim 男 2 高 Maggie 女 1.9 中等 Martha 女 1.88 中等 Stephanie 女 1.7 矮 Bob 男 1.85 中等 Kathy 女 1.6 矮 Dave 男 1.7 矮 Worth 男 2.2 高 Steven 男 2.1 高 Debbie 女 1.8 中等 Todd 男 1.95 中等 Kim 女 1.9 中等 Amy 女 1.8 中等 Wynette 女 1.75 中等

KNN：舉例 姓名 性別 身高(米) 類別 Kristina 女 1.6 矮 Jim 男 2 高 Maggie 女 1.9 中等 Martha 女 1.88 中等 Stephanie 女 1.7 矮 Bob 男 1.85 中等 Kathy 女 1.6 矮 Dave 男 1.7 矮 Worth 男 2.2 高 Steven 男 2.1 高 Debbie 女 1.8 中等 Todd 男 1.95 中等 Kim 女 1.9 中等 Amy 女 1.8 中等 Wynette 女 1.75 中等 最後的輸出元組是<Kristina，女， 1.6>、<Kathy，女，1.6>、<Stephanie，女，1.7>、<Dave，男，1.7>和<Wynette，女，1.75>。 在這五項中，四個屬於矮個、一個屬於中等。最終KNN方法認為Pat為矮個。

KNN演算法存在的問題 K=6？ K=11？ 問題：有一個未知形狀X(圖中綠色的點)，如何判斷X是什麼形狀? 更多範本、視頻教程：http://www.mysoeasy.com

在R中對iris數據集進行K近鄰分類並評估分類模型。 R實戰-KNN 在R中對iris數據集進行K近鄰分類並評估分類模型。 install.packages("class") install.packages("ggvis") library(class) library(ggvis) normalize <- function(x){ num <- x - min(x) denom <- max(x) - min(x) return(num/denom) } iris_norm <-as.data.frame(lapply(iris[,1:4], normalize)) set.seed(1234) ind <- sample(2,nrow(iris), replace=TRUE, prob=c(0.67, 0.33)) iris_train <-iris[ind==1, 1:4] iris_test <-iris[ind==2, 1:4] train_label <-iris[ind==1, 5] test_label <-iris[ind==2, 5] iris_pred <-knn(train=iris_train, test=iris_test, cl=train_label, k=3) Sepal.Length Sepal.Width Petal.Length Petal.Width Species 1 5.1 3.5 1.4 0.2 setosa 2 4.9 3.0 1.4 0.2 setosa 3 4.7 3.2 1.3 0.2 setosa 4 4.6 3.1 1.5 0.2 setosa 5 5.0 3.6 1.4 0.2 setosa 6 5.4 3.9 1.7 0.4 setosa

內容概要 分類的基本概念與步驟 分類的常用方法 基於距離的分類方法 決策樹分類方法 組合分類 貝葉斯分類 Logistic回歸分類 支持向量機分類 分類有關的問題

2.決策樹 什麼是決策樹？ age? youth senior 決策樹：Buys_computer student? yes 類似於流程圖的樹結構 每個內部節點表示在一個屬性上的測試 每個分枝代表一個測試輸出 每個樹葉節點存放一個類編號 age? youth Middle aged senior 決策樹：Buys_computer student? yes credit rating? no yes fair excellent no yes no yes

2.決策樹 使用決策樹分類 決策樹的生成由兩個階段組成 給定一個類標號未知的元組X，在決策樹上測試元組的屬性值，跟蹤一條由 根到葉節點的路徑，葉節點存放該元組的類預測。 決策樹容易轉換為分類規則 決策樹的生成由兩個階段組成 決策樹構建 使用屬性選擇度量來選擇將元組最好的劃分為不同的類的屬性 遞歸的通過選定的屬性，來劃分樣本 （必須是離散值） 樹剪枝 決策樹建立時，許多分枝反映的是訓練數據中的噪聲和離群點，樹剪枝 試圖識別並剪去這種分枝，以提高對未知數據分類的準確性

2.決策樹--演算法步驟 輸入 數據劃分D是訓練元組和對應類標號的集合 attribute_list,候選屬性的集合 Attribute_selection_method，指定選擇屬性的啟發性過程 演算法步驟 樹以代表訓練樣本的單個節點（N）開始 如果樣本都在同一個類，則該節點成為樹葉，並用該類標記 否則，演算法調用Attribute_selection_method，選擇能夠最好的將樣本分類的屬性；確定“分 裂準則”，指出“分裂點”或“分裂子集”。 對測試屬性每個已知的值，創建一個分支，並以此劃分元組； 演算法使用同樣的過程，遞歸的形成每個劃分上的元組決策樹。一旦一個屬性出現在一個節 點上，就不在該節點的任何子節點上出現； 遞歸劃分步驟停止的條件 劃分D（在N節點提供）的所有元組屬於同一類 沒有剩餘屬性可以用來進一步劃分元組——使用多數表決沒有剩餘的樣本 給定分支沒有元組，則以D中多數類創建一個樹葉

屬性選擇度量 屬性選擇度量是一種選擇分裂準則，將給定類標號的訓練元組最好的進行劃分的方法 常用的屬性選擇度量 理想情況，每個劃分都是“純”的，即落在給定劃分內的元組都屬於相同的類 屬性選擇度量又稱為分裂準則 常用的屬性選擇度量 信息增益--ID3 增益率--C4.5 Gini指標--CART

屬性選擇度量：舉例 學生膳食結構和缺鈣調查表 學生 雞肉 豬肉 牛肉 羊肉 魚肉 雞蛋 青菜 番茄 牛奶 健康情況 1 不缺鈣 2 3 缺鈣 不缺鈣 2 3 缺鈣 4 5 6 7 8 9 10

屬性選擇度量：舉例 採用不同的測試屬性及其先後順序將會生成不同的決策樹 雞肉 豬肉 豬肉 牛肉 牛肉 牛肉 不缺鈣（2） 缺鈣（3，6） 是 否 豬肉 豬肉 否 是 是 否 牛肉 牛肉 牛肉 不缺鈣（2） 否 是 否 是 否 是 缺鈣（3，6） 不缺鈣（4） 不缺鈣（10） 缺鈣（5） 不缺鈣（1） 魚肉 否 是 缺鈣（5） 不缺鈣（7，9）

在上例中，顯然生成的兩種決策樹的複雜性和分類意義相差很大，由此可見選擇測試屬性是決策樹學習演算法中需要研究的重要課題。 屬性選擇度量：舉例 牛奶 不缺鈣 （1，2，4， 7，9，10） 缺鈣 （3，5，6，8） 在上例中，顯然生成的兩種決策樹的複雜性和分類意義相差很大，由此可見選擇測試屬性是決策樹學習演算法中需要研究的重要課題。

概念介紹：信息增益 (1) S是一個訓練樣本的集合，該樣本中每個集合的類編號已知。每個樣 本為一個元組，有個屬性用來判定某個訓練樣本的類編號。 假設S中有m個類，總共s個訓練樣本，每個類Ci有si個樣本(i＝ 1,2,3...m)，那麼任意一個樣本屬於類Ci的概率是si / s，那麼用來分類 一個給定樣本的期望信息是：

概念介紹：資訊增益 (2) 一個有v個值的屬性A{a1,a2,...,av}可以將S分成v個子集{S1,S2,...,Sv}，其中Sj包含S中屬性A 上的值為aj的樣本。假設Sj包含類Ci的sij個樣本。根據A的這種劃分的期望信息稱為A的 熵 A上該劃分的獲得的信息增益定義為： 具有高信息增益的屬性，是給定集合中具有高區分度的屬性。所以可以通過計算S中樣 本的每個屬性的信息增益，來得到一個屬性的相關性的排序。

概念介紹：信息增益率 一個有v個值的屬性A{a1,a2,...,av}可以將S分成v個子集{S1,S2,...,Sv}，其中 Sj包含S中屬性A上的值為aj的樣本。根據A的這種劃分的信息增益為： A上該劃分的獲得的信息增益率定義為： 與ID3算法相比，C4.5算法選擇信息增益率最大的屬性進行分支，整體 上看，分支更明確，獲得有用信息更多。

概念介紹：Gini指標 一個有v個值的屬性A{a1,a2,...,av}可以將S分成v個子集{S1,S2,...,Sv}，其中 Sj包含S中屬性A上的值為aj的樣本。假設fij是Sj包含類Ci的樣本概率， 則Gini指數可以通過如下公式計算： 最好的劃分就是使得Gini最小的劃分。

決策樹 假定數據集D擁有4個特徵：age、income、student和credit_rating,計算基於熵的度量——信息增益，作為樣本劃分的根據： Gain(age)=0.246 Gain(income)=0.029 Gain(student)=0.151 Gain(credit_rating)=0.048 然後，對測試屬性每個已知的值，創建一個分支，並以此劃分樣本，得到第一次劃分。

決策樹 age? <=30 overcast >40 決策樹 算法(D1) yes(D2) 決策樹 算法(D3) 30-40 >40 決策樹 算法(D1) yes(D2) 決策樹 算法(D3) PS. 數據均屬於同一類別，無需再迭代

決策樹 age? <=30 overcast >40 student? yes credit rating? no yes 30-40 >40 student? yes credit rating? no yes excellent fair no yes no yes

防止分類中的過分適應 產生的決策樹會出現過分適應數據的問題 防止過分適應的兩種方法 由於數據中的雜訊和孤立點，許多分枝反應的是訓練數據中的異常 對新樣本的判定很不精確 防止過分適應的兩種方法 先剪枝：通過提前停止樹的構造——如果在一個節點劃分樣本將導致低於預定義臨界值 的分裂（e.g. 使用信息增益度量） 選擇一個合適的臨界值往往很困難 後剪枝：由“完全生長”的樹剪去分枝——對於樹中的每個非樹葉節點，計算該節點上 的子樹被剪枝可能出現的期望錯誤率 使用一個獨立的測試集來評估每顆樹的準確率，就能得到具有最小期望錯誤率的決策樹

防止分類中的過分適應--後剪枝 知所有的數據總共有60條，則節點T4的節點誤差代價為： 子樹誤差代價為： 找到α值最小的非葉子節點，令其左右孩子為NULL。當多個非葉子節點的值同時達到最小時，取包含的葉子節點個數最大的子樹進行剪枝。

由決策樹提取分類規則 可以提取決策樹表示的知識，並以IF-THEN形式的分類規則表示 對從根到樹葉的每條路徑創建一個規則 示例： IF age = “youth” AND student = “no” THEN buys_computer = “no” IF age = “youth” AND student = “yes” THEN buys_computer = “yes” IF age = “middle_aged” THEN buys_computer = “yes” IF age = “senior” AND credit_rating = “excellent” THEN buys_computer = “yes” IF age = “senior” AND credit_rating = “fair” THEN buys_computer = “no”

決策樹：舉例 決策樹的建立 分類屬性：買電腦？ 該屬性共分為兩類（m=2）：買/不買 s1=641，s2=383 s=s1+s2=1024 ——對測試樣例的信息期望 計數 年齡 收入 學生 信譽 歸類：買電腦？ 64 青 高 否 良 不買 優 128 中 買 60 老 低 是 132 32 63 1 分類屬性：買電腦？ 該屬性共分為兩類（m=2）：買/不買 s1=641，s2=383 s=s1+s2=1024

決策樹：舉例 決策樹的建立 ——對測試樣例的信息期望 平均信息期望E，是節點各直系分支的信息期望值的加權總和 1.假定選擇年齡作為樹根節點，則： 青年組：I(128,256)=0.9183 中年組：I(256,0)=0 老年組：I(257,127)=0.9157 青年組比例：(128+256)/1024=0.375 中年組比例：256/1024=0.25 老年組比例：(257+127)/1024=0.375 平均信息期望(加權總和): E(年齡)=0.375*0.9183+0.25*0+0.375*0.9157=0.6877 Gain(年齡)=I(641,383)-E(年齡)=0.9537-0.6877=0.2660 計數 年齡 收入 學生 信譽 歸類：買電腦？ 64 青 高 否 良 不買 優 128 中 低 是 買 計數 年齡 收入 學生 信譽 歸類：買電腦？ 128 中 高 否 良 買 64 低 是 優 32 計數 年齡 收入 學生 信譽 歸類：買電腦？ 60 老 中 否 良 買 64 低 是 優 不買 132 63 1

決策樹：舉例 決策樹的建立 2.假定選擇收入作為樹根節點，則： 高收入組：I(160,128)=0.9911 ——對測試樣例的信息期望 2.假定選擇收入作為樹根節點，則： 高收入組：I(160,128)=0.9911 中收入組：I(289,191)=0.9697 低收入組：I(192,64)=0.8133 高收入組比例：288/1024=0.2813 中收入組比例：480/1024=0.4687 低收入組比例：256/1024=0.25 平均信息期望(加權總和): E(年齡)=0.2813*0.9911+0.4687*0.9697+0.25*0.8133 =0.9361 Gain(年齡)=I(641,383)-E(收入)=0.9537-0.9361=0.0176 計數 年齡 收入 學生 信譽 歸類：買電腦？ 128 中 高 否 良 買 32 是 64 青 不買 優 計數 年齡 收入 學生 信譽 歸類：買電腦？ 32 中 否 優 買 128 青 良 不買 64 是 60 老 132 63 1 計數 年齡 收入 學生 信譽 歸類：買電腦？ 64 中 低 是 優 買 青 良 老 不買

決策樹：舉例 決策樹的建立 3.假定選擇學生作為樹根節點，則： 學生組：I(420,64)=0.5635 ——對測試樣例的信息期望 計數 年齡 收入 學生 信譽 歸類：買電腦？ 64 青 中 是 優 買 132 老 良 32 高 低 不買 3.假定選擇學生作為樹根節點，則： 學生組：I(420,64)=0.5635 非學生組：I(221,319)=0.9761 學生組比例：484/1024=0.4727 非學生組比例：540/1024=0.5273 平均信息期望(加權總和): E(年齡)=0.4727*0.5635+0.5273*0.9761=0.7811 Gain(年齡)=I(641,383)-E(學生)=0.9537-0.7811=0.1726 計數 年齡 收入 學生 信譽 歸類：買電腦？ 32 中 否 優 買 128 青 良 不買 60 老 63 1 高 64

決策樹：举例 決策樹的建立 3.假定選擇信譽作為樹根節點，則： 良好組：I(480,192)=0.8631 ——對測試樣例的信息期望 3.假定選擇信譽作為樹根節點，則： 良好組：I(480,192)=0.8631 優秀組：I(161,191)=0.9948 良好組比例：672/1024=0.6563 優秀組比例：352/1024=0.3437 平均信息期望(加權總和): E(年齡)=0.6563*0.8631+0.3437*0.9948=0.9048 Gain(年齡)=I(641,383)-E(信譽)=0.9537-0.9048=0.0453 計數 年齡 收入 學生 信譽 歸類：買電腦？ 128 青 中 否 良 不買 60 老 買 高 64 132 是 32 低 計數 年齡 收入 學生 信譽 歸類：買電腦？ 32 中 否 優 買 63 老 不買 1 64 青 高 是 低

決策樹：舉例 決策樹的建立 決定樹根節點 E(年齡)=0.6877，Gain(年齡)=0.2660 ——對測試樣例的信息期望 資訊增益 最大 決定樹根節點 E(年齡)=0.6877，Gain(年齡)=0.2660 E(收入)=0.9361，Gain(收入)=0.0176 E(學生)=0.7811，Gain(學生)=0.1726 E(信譽)=0.9048，Gain(信譽)=0.0453

決策樹：舉例 決策樹的建立 —決策樹建立步驟（例） 年齡 青 老 中 計數 收入 學生 信譽 歸類：買電腦？ 60 中 否 良 買 64 低 是 優 不買 132 63 1 計數 收入 學生 信譽 歸類：買電腦？ 64 高 否 良 不買 優 128 中 低 是 買 中 計數 收入 學生 信譽 歸類：買電腦？ 128 高 否 良 買 64 低 是 優 32 中

決策樹：舉例 決策樹的建立 —決策樹建立步驟（例） 年齡 青 老 中 買 計數 收入 學生 信譽 歸類：買電腦？ 60 中 否 良 買 64 低 是 優 不買 132 63 1 計數 收入 學生 信譽 歸類：買電腦？ 64 高 否 良 不買 優 128 中 低 是 買 中 買

決策樹：舉例 決策樹的建立 —決策樹建立步驟（例） 青年組數據表分析：1.假定選擇收入作節點 I(128,256)=0.9183 計數 收入 學生 信譽 歸類：買電腦？ 64 高 否 優 不買 良 I(0,128)=0 比例：128/384=0.3333 計數 收入 學生 信譽 歸類：買電腦？ 64 高 否 良 不買 優 128 中 低 是 買 計數 收入 學生 信譽 歸類：買電腦？ 64 中 是 優 買 128 否 良 不買 I(64,128)=0.9183 比例：192/384=0.5 I(64,0)=0 比例：64/384=0.1667 計數 收入 學生 信譽 歸類：買電腦？ 64 低 是 良 買 平均信息期望(加權總和): E(收入)=0.3333*0+0.5*0.9183=0.4592 Gain(收入)=I(128,256)-E(收入)=0.9183-0.4592=0.4591

決策樹：舉例 決策樹的建立 —決策樹建立步驟（例） 青年組數據表分析：2.假定選擇學生作節點 I(128,256)=0.9183 比例：128/384=0.3333 計數 收入 學生 信譽 歸類：買電腦？ 64 高 否 良 不買 優 128 中 低 是 買 計數 收入 學生 信譽 歸類：買電腦？ 64 中 是 優 買 低 良 I(0,256)=0 比例：256/384=0.6667 計數 收入 學生 信譽 歸類：買電腦？ 128 中 否 良 不買 64 高 優 平均信息期望(加權總和): E(學生)=0.3333*0+0.6667*0=0 Gain(學生)=I(128,256)-E(學生)=0.9183-0=0.9183 結論：不需要考慮屬性信譽，決定選擇屬性學生

決策樹：舉例 年齡 老 青 中 學生 決策樹的建立 —決策樹建立步驟（例） 樹葉 買 計數 收入 學生 信譽 歸類：買電腦？ 60 中 否 良 買 64 低 是 優 不買 132 63 1 學生 買 計數 收入 信譽 歸類：買電腦？ 128 中 良 不買 64 高 優 計數 收入 信譽 歸類：買電腦？ 64 中 優 買 低 良 樹葉

決策樹：舉例 …… 年齡 老 青 中 學生 買 買 是 否 不買 買 計數 收入 學生 信譽 歸類：買電腦？ 60 中 否 良 買 64 低 優 不買 132 63 1 學生 買 買 是 否 不買 買 ……

在R中對iris數據集進行決策樹分類並評估分類模型。 R實戰-決策樹-C4.5 在R中對iris數據集進行決策樹分類並評估分類模型。 #調用程式包 library(RWeka) library(grid) library(partykit) #第一步：獲取數據集， data(iris) View(iris) summary(iris) #第二步：使用C4.5決策樹算法對iris數據集做分類 iris_j48 <- J48(Species ~ ., data = iris) iris_j48 #第三步：決策樹模型摘要分析 summary(iris_j48) #第五步：模型的可視化 plot(iris_j48)包的調用 Sepal.Length Sepal.Width Petal.Length Petal.Width Species 1 5.1 3.5 1.4 0.2 setosa 2 4.9 3.0 1.4 0.2 setosa 3 4.7 3.2 1.3 0.2 setosa 4 4.6 3.1 1.5 0.2 setosa 5 5.0 3.6 1.4 0.2 setosa 6 5.4 3.9 1.7 0.4 setosa library(rpart); ## rpart.control對樹進行一些設置 ## xval是10折交叉驗證 ## minsplit是最小分支節點數，這裏指大於等於20，那麼該節點會繼續分劃下去，否則停止 ## minbucket：葉子節點最小樣本數 ## maxdepth：樹的深度 ## cp全稱為complexity parameter，指某個點的複雜度，對每一步拆分,模型的擬合優度必須提高的程度 ct <- rpart.control(xval=10, minsplit=20, cp=0.1) ## kyphosis是rpart這個包自帶的數據集 ## na.action：缺失數據的處理辦法，默認為刪除因變數缺失的觀測而保留引數缺失的觀測。 ## method：樹的末端數據類型選擇相應的變數分割方法: ## 連續性method=“anova”,離散型method=“class”,計數型method=“poisson”,生存分析型method=“exp” ## parms用來設置三個參數:先驗概率、損失矩陣、分類純度的度量方法（gini和information） ## cost我覺得是損失矩陣，在剪枝的時候，葉子節點的加權誤差與父節點的誤差進行比較，考慮損失矩陣的時候，從將“減少-誤差”調整為“減少-損失” fit <- rpart(Kyphosis~Age + Number + Start, data=kyphosis, method="class",control=ct, parms = list(prior = c(0.65,0.35), split = "information")); ## 第一種 par(mfrow=c(1,3)); plot(fit); text(fit,use.n=T,all=T,cex=0.9)； ## 第二種，這種會更漂亮一些 library(rpart.plot); rpart.plot(fit, branch=1, branch.type=2, type=1, extra=102, shadow.col="gray", box.col="green", border.col="blue", split.col="red", split.cex=1.2, main="Kyphosis決策樹"); ## rpart包提供了複雜度損失修剪的修剪方法，printcp會告訴分裂到每一層，cp是多少，平均相對誤差是多少 ## 交叉驗證的估計誤差（“xerror”列），以及標準誤差(“xstd”列)，平均相對誤差=xerror±xstd printcp(fit); ## 通過上面的分析來確定cp的值 ## 我們可以用下麵的辦法選擇具有最小xerror的cp的辦法： ## prune(fit, cp= fit$cptable[which.min(fit$cptable[,"xerror"]),"CP"]) fit2 <- prune(fit, cp=0.01); rpart.plot(fit2, branch=1, branch.type=2, type=1, extra=102,

在R中對iris數據集進行決策樹分類並評估分類模型。 R實戰-決策樹-CART 在R中對iris數據集進行決策樹分類並評估分類模型。 set.seed(1234) index <-sample(1:nrow(iris),100) iris.train <-iris[index,] iris.test <-iris[-index,] #第二步：加載包含CART算法的R包 library(rpart) #第三步：構建CART模型 model.CART <-rpart(Species~.,data=iris.train) #第四步：模型應用到測試集 results.CART <-predict(model.CART,newdata=iris.test, type="class") #第五步：生成混淆矩陣 table(results.CART, iris.test$Species) Sepal.Length Sepal.Width Petal.Length Petal.Width Species 1 5.1 3.5 1.4 0.2 setosa 2 4.9 3.0 1.4 0.2 setosa 3 4.7 3.2 1.3 0.2 setosa 4 4.6 3.1 1.5 0.2 setosa 5 5.0 3.6 1.4 0.2 setosa 6 5.4 3.9 1.7 0.4 setosa library(rpart); ## rpart.control對樹進行一些設置 ## xval是10折交叉驗證 ## minsplit是最小分支節點數，這裏指大於等於20，那麼該節點會繼續分劃下去，否則停止 ## minbucket：葉子節點最小樣本數 ## maxdepth：樹的深度 ## cp全稱為complexity parameter，指某個點的複雜度，對每一步拆分,模型的擬合優度必須提高的程度 ct <- rpart.control(xval=10, minsplit=20, cp=0.1) ## kyphosis是rpart這個包自帶的數據集 ## na.action：缺失數據的處理辦法，默認為刪除因變數缺失的觀測而保留引數缺失的觀測。 ## method：樹的末端數據類型選擇相應的變數分割方法: ## 連續性method=“anova”,離散型method=“class”,計數型method=“poisson”,生存分析型method=“exp” ## parms用來設置三個參數:先驗概率、損失矩陣、分類純度的度量方法（gini和information） ## cost我覺得是損失矩陣，在剪枝的時候，葉子節點的加權誤差與父節點的誤差進行比較，考慮損失矩陣的時候，從將“減少-誤差”調整為“減少-損失” fit <- rpart(Kyphosis~Age + Number + Start, data=kyphosis, method="class",control=ct, parms = list(prior = c(0.65,0.35), split = "information")); ## 第一種 par(mfrow=c(1,3)); plot(fit); text(fit,use.n=T,all=T,cex=0.9)； ## 第二種，這種會更漂亮一些 library(rpart.plot); rpart.plot(fit, branch=1, branch.type=2, type=1, extra=102, shadow.col="gray", box.col="green", border.col="blue", split.col="red", split.cex=1.2, main="Kyphosis決策樹"); ## rpart包提供了複雜度損失修剪的修剪方法，printcp會告訴分裂到每一層，cp是多少，平均相對誤差是多少 ## 交叉驗證的估計誤差（“xerror”列），以及標準誤差(“xstd”列)，平均相對誤差=xerror±xstd printcp(fit); ## 通過上面的分析來確定cp的值 ## 我們可以用下麵的辦法選擇具有最小xerror的cp的辦法： ## prune(fit, cp= fit$cptable[which.min(fit$cptable[,"xerror"]),"CP"]) fit2 <- prune(fit, cp=0.01); rpart.plot(fit2, branch=1, branch.type=2, type=1, extra=102,

在R中對kyphosis數據集進行決策樹分類並評估分類模型。 install.packages("rpart") install.packages("rpart.plot") library(rpart) library(rpart.plot) ct <- rpart.control(xval=10, minsplit=20, cp=0.1) fit <- rpart(Kyphosis~Age + Number + Start, data=kyphosis, method="class",control=ct, parms = list(prior = c(0.65,0.35), split = "information")) plot(fit); text(fit,use.n=T,all=T,cex=0.9) rpart.plot(fit, branch=1, branch.type=2, type=1, extra=102, shadow.col="gray", box.col="green", border.col="blue", split.col="red", split.cex=1.2, main="Kyphosis決策樹") fit2 <- prune(fit, cp=0.01) rpart.plot(fit2, ……) Kyphosis Age Number Start 1 absent 71 3 5 2 absent 158 3 14 3 present 128 4 5 4 absent 2 5 1 5 absent 1 4 15 6 absent 1 2 16 kyphosis數據集的各列含義： 數據集是從兒童接受外科脊柱矯正手術中來的，數據集有4列、81行（81個病例）。 1、kyphosis：採取手術後依然出現脊柱後凸（駝背）的因數 2、Age：單位是“月” 3、Number：代表進行手術的脊柱椎骨的數目 4、Start：在脊柱上從上往下數、參與手術的第一節椎骨所在的序號 library(rpart); ## rpart.control對樹進行一些設置 ## xval是10折交叉驗證 ## minsplit是最小分支節點數，這裏指大於等於20，那麼該節點會繼續分劃下去，否則停止 ## minbucket：葉子節點最小樣本數 ## maxdepth：樹的深度 ## cp全稱為complexity parameter，指某個點的複雜度，對每一步拆分,模型的擬合優度必須提高的程度 ct <- rpart.control(xval=10, minsplit=20, cp=0.1) ## kyphosis是rpart這個包自帶的數據集 ## na.action：缺失數據的處理辦法，默認為刪除因變數缺失的觀測而保留引數缺失的觀測。 ## method：樹的末端數據類型選擇相應的變數分割方法: ## 連續性method=“anova”,離散型method=“class”,計數型method=“poisson”,生存分析型method=“exp” ## parms用來設置三個參數:先驗概率、損失矩陣、分類純度的度量方法（gini和information） ## cost我覺得是損失矩陣，在剪枝的時候，葉子節點的加權誤差與父節點的誤差進行比較，考慮損失矩陣的時候，從將“減少-誤差”調整為“減少-損失” fit <- rpart(Kyphosis~Age + Number + Start, data=kyphosis, method="class",control=ct, parms = list(prior = c(0.65,0.35), split = "information")); ## 第一種 par(mfrow=c(1,3)); plot(fit); text(fit,use.n=T,all=T,cex=0.9)； ## 第二種，這種會更漂亮一些 library(rpart.plot); rpart.plot(fit, branch=1, branch.type=2, type=1, extra=102, shadow.col="gray", box.col="green", border.col="blue", split.col="red", split.cex=1.2, main="Kyphosis決策樹"); ## rpart包提供了複雜度損失修剪的修剪方法，printcp會告訴分裂到每一層，cp是多少，平均相對誤差是多少 ## 交叉驗證的估計誤差（“xerror”列），以及標準誤差(“xstd”列)，平均相對誤差=xerror±xstd printcp(fit); ## 通過上面的分析來確定cp的值 ## 我們可以用下麵的辦法選擇具有最小xerror的cp的辦法： ## prune(fit, cp= fit$cptable[which.min(fit$cptable[,"xerror"]),"CP"]) fit2 <- prune(fit, cp=0.01); rpart.plot(fit2, branch=1, branch.type=2, type=1, extra=102,

內容概要 分類的基本概念與步驟 分類的常用方法 基於距離的分類方法 決策樹分類方法 組合分類 貝葉斯分類 Logistic回歸分類 支持向量機分類 分類有關的問題

多個“弱”分類器集合，組成一個“強”分類器 3.組合分類 多個“弱”分類器集合，組成一個“強”分類器 樣本集 樣本集 分類器 VS 弱分類器1 弱分類器2 弱分類器T 錯誤率： 60% 強分類器 錯誤率： 5%

隨機森林 隨機森林顧名思義，是用隨機的方式建立一個森林，森林裏面有很多的決策 樹組成，隨機森林的每一棵決策樹之間是沒有關聯的。 在得到森林之後，當有一個新的輸 入樣本進入的時候，就讓森林中的每一 棵決策樹分別進行一下判斷，看看這個樣本應該屬於哪一類（對於分類算 法），然後看看哪一類被選擇最多，就預測這個樣本為那一類。 自動樣本集1 樹分類器1 …… …… 全部訓練樣本 自動樣本集i 樹分類器i 隨機森林 投票結果 …… …… 自動樣本集k 樹分類器k

隨機森林 隨機森林算法描述 1：首先，通過Bootstrap方法在原始樣本集S中抽取k個訓練樣本集，一般情況下每個訓練集的樣本容量與S一致； 2：其次，對k個訓練集進行CART學習，以此生成k個決策樹模型。在決策樹生成過程中，假設共有M個特徵向量，從M個特徵向量中隨機抽取m個，各個內部節點均是利用這m個特徵變量上最優的分裂方式來分裂，且m值在隨機森林模型的形成過程中為恒定常數； 3：最後，將k個決策樹的結果進行組合，形成最終結果。針對分類問題，組合方法是簡單多數投票法；針對回歸問題，組合方法則是簡單平均法。

在R中對iris數據集進行隨機森林分類並評估分類模型。 Sepal.Length Sepal.Width Petal.Length Petal.Width Species 1 5.1 3.5 1.4 0.2 setosa 2 4.9 3.0 1.4 0.2 setosa 3 4.7 3.2 1.3 0.2 setosa 4 4.6 3.1 1.5 0.2 setosa 5 5.0 3.6 1.4 0.2 setosa 6 5.4 3.9 1.7 0.4 setosa library(randomForest) data(iris) set.seed(111) ind <- sample(2, nrow(iris), replace = TRUE, prob=c(0.8, 0.2)) iris.rf <- randomForest(Species ~ ., data=iris[ind == 1,]) iris.pred <- predict(iris.rf, iris[ind == 2,]) table(observed = iris[ind==2, "Species"], predicted = iris.pred) library(rpart); ## rpart.control對樹進行一些設置 ## xval是10折交叉驗證 ## minsplit是最小分支節點數，這裏指大於等於20，那麼該節點會繼續分劃下去，否則停止 ## minbucket：葉子節點最小樣本數 ## maxdepth：樹的深度 ## cp全稱為complexity parameter，指某個點的複雜度，對每一步拆分,模型的擬合優度必須提高的程度 ct <- rpart.control(xval=10, minsplit=20, cp=0.1) ## kyphosis是rpart這個包自帶的數據集 ## na.action：缺失數據的處理辦法，默認為刪除因變數缺失的觀測而保留引數缺失的觀測。 ## method：樹的末端數據類型選擇相應的變數分割方法: ## 連續性method=“anova”,離散型method=“class”,計數型method=“poisson”,生存分析型method=“exp” ## parms用來設置三個參數:先驗概率、損失矩陣、分類純度的度量方法（gini和information） ## cost我覺得是損失矩陣，在剪枝的時候，葉子節點的加權誤差與父節點的誤差進行比較，考慮損失矩陣的時候，從將“減少-誤差”調整為“減少-損失” fit <- rpart(Kyphosis~Age + Number + Start, data=kyphosis, method="class",control=ct, parms = list(prior = c(0.65,0.35), split = "information")); ## 第一種 par(mfrow=c(1,3)); plot(fit); text(fit,use.n=T,all=T,cex=0.9)； ## 第二種，這種會更漂亮一些 library(rpart.plot); rpart.plot(fit, branch=1, branch.type=2, type=1, extra=102, shadow.col="gray", box.col="green", border.col="blue", split.col="red", split.cex=1.2, main="Kyphosis決策樹"); ## rpart包提供了複雜度損失修剪的修剪方法，printcp會告訴分裂到每一層，cp是多少，平均相對誤差是多少 ## 交叉驗證的估計誤差（“xerror”列），以及標準誤差(“xstd”列)，平均相對誤差=xerror±xstd printcp(fit); ## 通過上面的分析來確定cp的值 ## 我們可以用下麵的辦法選擇具有最小xerror的cp的辦法： ## prune(fit, cp= fit$cptable[which.min(fit$cptable[,"xerror"]),"CP"]) fit2 <- prune(fit, cp=0.01); rpart.plot(fit2, branch=1, branch.type=2, type=1, extra=102,

Adaboost算法 核心思想 Adaboost（Adaptive Boosting, R.Scharpire, Y.Freund, ICML, 1996）是一種迭代算法，其核心思想是針對同一個訓練集訓練不同的分類器（弱分類器），然後把這些弱分類器集合起來，構成一個更強的最終分類器（強分類器）。

Adaboost算法 1. 如何調整訓練集，使得在訓練集上訓練的弱分類器得以進行？ 2. 如何將訓練得到的各個弱分類器聯合起來形成強分類器？ 對於Boosting算法，存在兩個問題： 1. 如何調整訓練集，使得在訓練集上訓練的弱分類器得以進行？ 2. 如何將訓練得到的各個弱分類器聯合起來形成強分類器？

AdaBoost算法 AdaBoost 算法分析 針對以上兩個問題，AdaBoost算法進行了調整： 1. 使用加權後選取的訓練數據代替隨機選取的訓練樣本，這樣將訓練的焦點集中在比較難分的訓練數據樣本上； 　　 2. 將弱分類器聯合起來，使用加權的投票機制代替平均投票機制。讓分類效果好的弱分類器具有較大的權重，而分類效果差的分類器具有較小的權重。

AdaBoost算法 AdaBoost算法的具體步驟如下： 1. 給定訓練樣本集S，其中X和Y分別對應於正例樣本和負例樣本；T為訓練的最大循環次數； 2. 初始化樣本權重為1/n ，即為訓練樣本的初始概率分佈； 　　 3. 第一次迭代：(1)訓練樣本的概率分佈相當，訓練弱分類器;(2)計算弱分類器的錯誤率;(3)選取合適閾值，使得誤差最小；(4)更新樣本權重； 　　 經T次迴圈後，得到T個弱分類器，按更新的權重疊加，最終得到的強分類器。

AdaBoost ：舉例 下麵我們舉一個簡單的例子來看看Adaboost 的實現過程： D1 圖中，“+”和“-”分別表示兩種類別，在這個過程中， 我們使用水準或者垂直的直線作為分類器，來進行分類。

AdaBoost ：舉例 D2 ε1=0.3 α1=0.42 h1 第一步根據分類的正確率，得到一個新的樣本分佈D2，一個子分離器h1。其中畫圈的樣本表示被分錯的。在右邊圖中，比較大的“+”表示對該樣本做了加權。具體過程為算法最開始給了一個均勻的分佈D1，所以每個點的值為0.1。當劃分後，有三個點被劃分錯了，根據演算法的誤差運算式ε1=Pr[h1(xi) ≠ yi]得到誤差為分錯了的三個點的概率值之和，則ε1=0.1+0.1+0.1=0.3，而α1=0.42，然後增加分錯點的權值。

得到一個新的樣本分佈D3，一個子分類器h2。 AdaBoost ：舉例 D3 ε2=0.21 α2=0.65 h2 得到一個新的樣本分佈D3，一個子分類器h2。

AdaBoost ：舉例 h3 ε3=0.14 α3=0.92 基於新的樣本分佈D3，得到一個子分類器h3。

AdaBoost ：舉例 ) = h3 Hfina =sign( 0.42 +0.65 +0.92 x3 x1 x2 H(x1) =sign(0.42+0.65−0.92) = +1 H(x2) = sign(−0.42+0.65−0.92) = −1 H(x3) = sign(−0.42−0.65 + 0.92) = −1 = x1 x2 每個區域是屬於哪個屬性，由這個區域所在分類器的權值綜合決定。比如左下角的區域，屬於藍色分類區的權重為h1 中的0.42和h2 中的0.65，其和為1.07；屬於淡紅色分類區域的權重為h3 中的0.92；屬於淡紅色分類區的權重小於屬於藍色分類區的權值，因此左下角屬於藍色分類區。因此可以得到整合的結果如上圖所示，從結果圖中看，即使是簡單的分類器，組合起來也能獲得很好的分類效果。

AdaBoost權值調整的原因 注意到算法最後的表到式為 這裏面的αt表示的權值，是由 得到的。

在R中對iris數據集進行Adaboost分類並評估分類模型。 R實戰-Adaboost 在R中對iris數據集進行Adaboost分類並評估分類模型。 library(lattice) library(rpart) library(mlbench) library(ggplot2) library(caret) library(adabag) #利用boosting（）（原來的adaboost.M1（）函數）建立adaboost分類 a=boosting(Species~.,data=iris) #建立adaboost分類模型 (z0=table(iris[,5],predict(a,iris)$class)) #查看模型的預測結果 (E0=(sum(z0)-sum(diag(z0)))/sum(z0)) #計算誤差率 barplot(a$importance) #畫出變數重要性圖 b<-errorevol(a,iris) #計算全體的誤差演變 plot(b$error,type="l",main="AdaBoost error vs number of trees") #對誤差演變進行畫圖 Sepal.Length Sepal.Width Petal.Length Petal.Width Species 1 5.1 3.5 1.4 0.2 setosa 2 4.9 3.0 1.4 0.2 setosa 3 4.7 3.2 1.3 0.2 setosa 4 4.6 3.1 1.5 0.2 setosa 5 5.0 3.6 1.4 0.2 setosa 6 5.4 3.9 1.7 0.4 setosa library(rpart); ## rpart.control對樹進行一些設置 ## xval是10折交叉驗證 ## minsplit是最小分支節點數，這裏指大於等於20，那麼該節點會繼續分劃下去，否則停止 ## minbucket：葉子節點最小樣本數 ## maxdepth：樹的深度 ## cp全稱為complexity parameter，指某個點的複雜度，對每一步拆分,模型的擬合優度必須提高的程度 ct <- rpart.control(xval=10, minsplit=20, cp=0.1) ## kyphosis是rpart這個包自帶的數據集 ## na.action：缺失數據的處理辦法，默認為刪除因變數缺失的觀測而保留引數缺失的觀測。 ## method：樹的末端數據類型選擇相應的變數分割方法: ## 連續性method=“anova”,離散型method=“class”,計數型method=“poisson”,生存分析型method=“exp” ## parms用來設置三個參數:先驗概率、損失矩陣、分類純度的度量方法（gini和information） ## cost我覺得是損失矩陣，在剪枝的時候，葉子節點的加權誤差與父節點的誤差進行比較，考慮損失矩陣的時候，從將“減少-誤差”調整為“減少-損失” fit <- rpart(Kyphosis~Age + Number + Start, data=kyphosis, method="class",control=ct, parms = list(prior = c(0.65,0.35), split = "information")); ## 第一種 par(mfrow=c(1,3)); plot(fit); text(fit,use.n=T,all=T,cex=0.9)； ## 第二種，這種會更漂亮一些 library(rpart.plot); rpart.plot(fit, branch=1, branch.type=2, type=1, extra=102, shadow.col="gray", box.col="green", border.col="blue", split.col="red", split.cex=1.2, main="Kyphosis決策樹"); ## rpart包提供了複雜度損失修剪的修剪方法，printcp會告訴分裂到每一層，cp是多少，平均相對誤差是多少 ## 交叉驗證的估計誤差（“xerror”列），以及標準誤差(“xstd”列)，平均相對誤差=xerror±xstd printcp(fit); ## 通過上面的分析來確定cp的值 ## 我們可以用下麵的辦法選擇具有最小xerror的cp的辦法： ## prune(fit, cp= fit$cptable[which.min(fit$cptable[,"xerror"]),"CP"]) fit2 <- prune(fit, cp=0.01); rpart.plot(fit2, branch=1, branch.type=2, type=1, extra=102,

內容概要 分類的基本概念與步驟 分類的常用方法 基於距離的分類方法 決策樹分類方法 組合分類 貝葉斯分類 Logistic回歸分類 支持向量機分類 分類有關的問題

4.貝葉斯分類 定義4-2 設X是類標號未知的數據樣本。設H為某種假定，如數據樣本X屬於某 特定的類C。對於分類問題，我們希望確定P(H|X)，即給定觀測數據樣本X，假 定H成立的概率。貝葉斯定理給出了如下計算P(H|X)的簡單有效的方法: P(H)是先驗概率，或稱H的先驗概率。P(X |H)代表假設H成立的情況下，觀察 到X的概率。P(H| X )是後驗概率，或稱條件X下H的後驗概率。 例如，假定數據樣本域由水果組成，用它們的顏色和形狀來描述。假定X表示 紅色和圓的，H表示假定X是蘋果，則P(H|X)反映當我們看到X是紅色並是圓的 時，我們對X是蘋果的確信程度。 貝葉斯分類器對兩種數據具有較好的分類效果：一種是完全獨立的數據，另一 種是函數依賴的數據。

樸素貝葉斯分類 樸素貝葉斯分類的工作過程如下： (1)  每個數據樣本用一個n維特徵向量X= {x1，x2，……，xn}表示，分別描述對n 個屬性A1，A2，……，An樣本的n個度量。 (2) 假定有m個類C1，C2，…，Cm，給定一個未知的數據樣本X（即沒有類標 號），分類器將預測X屬於具有最高後驗概率（條件X下）的類。也就是說，樸 素貝葉斯分類將未知的樣本分配給類Ci（1≤i≤m）當且僅當P(Ci|X)> P(Cj|X)，對 任意的j=1，2，…，m，j≠i。這樣，最大化P(Ci|X)。其P(Ci|X)最大的類Ci稱為最 大後驗假定。根據貝葉斯定理

樸素貝葉斯分類 (3) 由於P(X)對於所有類為常數，只需要P(X|Ci)*P(Ci)最大即可。如果Ci類的先驗 概率未知，則通常假定這些類是等概率的，即P(C1)=P(C2)=…=P(Cm)，因此問 題就轉換為對P(X|Ci)的最大化（P(X|Ci)常被稱為給定Ci時數據X的似然度，而使 P(X|Ci)最大的假設Ci稱為最大似然假設）。否則，需要最大化P(X|Ci)*P(Ci)。注 意，類的先驗概率可以用P(Ci)=si/s計算，其中si是類Ci中的訓練樣本數，而s是 訓練樣本總數。 (4) 給定具有許多屬性的數據集，計算P(X|Ci)的開銷可能非常大。為降低計算 P(X|Ci)的開銷，可以做類條件獨立的樸素假定。給定樣本的類標號，假定屬性 值相互條件獨立，即在屬性間，不存在依賴關係。這樣

樸素貝葉斯分類 其中概率P(x1|Ci)，P(x2|Ci)，……，P(xn|Ci)可以由訓練樣本估值。 如果Ak是離散屬性，則P(xk|Ci)=sik|si，其中sik是在屬性Ak上具有值xk的類Ci的訓練樣本數， 而si是Ci中的訓練樣本數。 如果Ak是連續值屬性，則通常假定該屬性服從高斯分佈。因而，   是高斯分佈函數， 分別為平均值和標準差。 (5) 對未知樣本X分類，也就是對每個類Ci，計算P(X|Ci)*P(Ci)。樣本X被指派到 類Ci，當且僅當P(Ci|X)> P(Cj|X)，1≤j≤m，j≠i，換言之，X被指派到其 P(X|Ci)*P(Ci)最大的類。

樸素貝葉斯分類：舉例 我們希望分類的未知樣本為: 樣本數據 Age income studen credit_rating buy_computer <=30 High No Fair No <=30 High No Excellent No 31…40 High No Fair Yes >40 Medium No Fair Yes >40 Low Yes Fair Yes >40 Low Yes Excellent No 31…40 Low Yes Excellent Yes <=30 Medium No Fair No <=30 Low Yes Fair Yes >40 Medium Yes Fair Yes <=30 Medium Yes Excellent Yes 31…40 Medium No Excellent Yes 31…40 High Yes Fair Yes >40 Medium No Excellent No 數據樣本用屬性age，income，student和credit_rating描述。類標號屬性buys_computer具有兩個不同值（即{yes，no}）。設C1對應於類buys_computer=”yes”，而C2對應於類buys_computer=”no”。 我們希望分類的未知樣本為: X=（age=”<=30”，income=”medium”，student=”yes”，credit_rating=”fair”）。

因此，對於樣本X，樸素貝葉斯分類預測buys_computer=”yes”。 樸素貝葉斯分類：舉例 (1) 我們需要最大化P(X|Ci)*P(Ci)，i=1，2。每個類的先驗概率P(Ci)可以根據訓練樣本計算： P(buys_computer=”yes”)=9/14=0.643， P(buys_computer=”no”)=5/14=0.357。 (2) 為計算P(X|Ci)，i=1，2，我們計算下麵的條件概率： P(age<=30|buys_computer=”yes” )=2/9=0.222， P(age<=30”|buys_computer=”no” )=3/5=0.600， P(income=”medium”|buys_computer=”yes” )=4/9=0.444， P(income=”medium”|buys_computer=”no” )=2/5=0.400， P(student=”yes”|buys_computer=”yes” )=6/9=0.677， P(student=”yes”|buys_computer=”no” )=1/5=0.200， P(credit_rating=”fair”|buys_computer=”yes” )=6/9=0.667， P(credit_rating=”fair”|buys_computer=”no” )=2/5=0.400。 (3) 假設條件獨立性，使用以上概率，我們得到： P(X|buys_computer=”yes” )=0.222*0.444*0.667*0.667=0.044， P(X|buys_computer=”no” )=0.600*0.400*0.200*0.400=0.019， P(X|buys_computer=”yes” )*P(buys_computer=”yes” )= 0.044*0.643=0.028 P(X|buys_computer=”no” )*P(buys_computer=”no” )=0.019*0.357=0.007。 因此，對於樣本X，樸素貝葉斯分類預測buys_computer=”yes”。

在R中對iris數據集進貝葉斯分類並評估分類模型。 #程式如下： library(MASS) library(klaR) data(iris) index<-sample(2,size=nrow(iris),replace=TRUE,prob=c(0.75,0.25)) train<-iris[index==1,] test<-iris[index==2,] #使用樸素貝葉斯算法 res2<-NaiveBayes(Species~.,data=train) pre<-predict(res2,newdata=test[,1:4]) #混淆矩陣 table(test$Species,pre$class) Sepal.Length Sepal.Width Petal.Length Petal.Width Species 1 5.1 3.5 1.4 0.2 setosa 2 4.9 3.0 1.4 0.2 setosa 3 4.7 3.2 1.3 0.2 setosa 4 4.6 3.1 1.5 0.2 setosa 5 5.0 3.6 1.4 0.2 setosa 6 5.4 3.9 1.7 0.4 setosa

內容概要 分類的基本概念與步驟 分類的常用方法 基於距離的分類方法 決策樹分類方法 組合分類 貝葉斯分類 Logistic回歸分類 支持向量機分類 分類有關的問題

5.Logistic回歸 設因變量y是一個二分類變量，其取值為 y=1和 y=0。影響y取值的 m個 自變量分別為x1、x2、…、xm。在m個自變量（即暴露因素）作用下陽 性結果發生的條件概率為 ，則Logistic回歸模型可表示為： 其中， 為常數項， 為偏回歸係數。

Logistic回歸 設Z=β0+β1x1+β2x2+……+βmxm，則Z與P之間關係的Logistic曲線如下圖所示： 可以看出：當Z趨於+∞，P值漸進於1；當Z趨於-∞，P值漸進於0。P值的變化在0~1之間，並且隨Z值的變化於點(0,0.5)為中心對稱S形變化。

Logistic回歸模型的參數估計 Logistic回歸模型的參數估計採用最大似然估計。其基本思想是先建立似然函數與對數似然函數，求使對數似然函數最大時的參數值，其估計值即為最大似然估計值。 建立樣本似然函數： 其中Pi表示第i例觀測對象處於暴露條件下時陽性結果發生的概率。陽性結果時，yi=1；陰性結果時，yi=0。

Logistic回歸 根據最大似然原理，似然函數L應取最大值。 對似然函數取對數形式： 式中為對數似然函數，對其取一階導數求解參數。對於參數βj，令lnL的一階導數為0，即 用Newton-Raphson迭代方法求解方程組，得出參數 的估計值bj和bj的漸進標準誤差 。

Logistic 回歸：舉例 發病(y=1) 不發病(y=0) 暴露(x=1) a b 不暴露(x=0) c d 以四格表為例來說明最大似然求解的意義及過程。 四格表的一般表達形式 —————————————————————————————————— 發病(y=1) 不發病(y=0) 暴露(x=1) a b 不暴露(x=0) c d ————————————————————— 合計 a+c b+d —————————————————————————————————--- 暴露者發病概率 p1 = a /(a+b); 不暴露者發病概率 p0= c/(c+d)。

Logistic回歸：舉例 發病(y=1) 不發病(y=0) 暴露(x=1) p1 1-p1 不暴露(x=0) p0 1-p0 用發病概率來表示四格表，可以得到四格表的另外一種表示形式： 四格表的另外一種表達形式(1) ———————————————————————————— 發病(y=1) 不發病(y=0) 暴露(x=1) p1 1-p1 不暴露(x=0) p0 1-p0 ————————————————————————————— 暴露者發病概率: p1 = exp(α + βx)/[1+ exp(α + βx)] 暴露者不發病概率: q0= 1/ [1+ exp(α + βx)]; 不暴露者發病概率: p0 = exp(α)/[1+ exp(α)] 不暴露者不發病概率: q0 = 1/[1+ exp(α)] 。

Logistic回歸：舉例 暴露(x=1) e(α + β)/[1+ e (α + β)] 1/ [1+ e (α + β)] 用發病概率來表示四格表，可以得到四格表的另外一種表示形式： 四格表的另外一種表達形式(2) —————————————————————————————— 發病(y=1) 不發病(y=0) 暴露(x=1) e(α + β)/[1+ e (α + β)] 1/ [1+ e (α + β)] 不暴露(x=0) e α/[1+ e α] 1/ [1+ e α] 因為四格表的四個實際數為a,b,c及d， 故可構造似然函數為： L = {e(α + β)/[1+ e (α + β)] }a {1/ [1+ e (α + β)] }b{e α/[1+ e α] }c {1/ [1+ e α] }d 取對數，有 Ln (L) = a (α+β) –aln[1+e(α +β)]– b ln[1+e (α + β)]+ cα–cln[1+eα] – dln[1+eα ] 對以上似然函數分別求對α和 β 的一階偏導數，再令兩個偏導數為零，就可以解得α和β的估計值。

在R中對iris數據集進行Logistic回歸分類並評估分類模型。 R實戰-Logistic回歸 在R中對iris數據集進行Logistic回歸分類並評估分類模型。 data_sample <- iris[51:150,]; m <- dim(data_sample)[1] #獲取數據集記錄條數 val <- sample(m, size =round(m/3), replace = FALSE, prob= rep(1/m, m)) #抽樣，選取三分之二的數據作為訓練集。 iris.learn <- data_sample[-val,] #選取訓練集 iris.valid <- data_sample[val,] #選取驗證集 logit.fit <- glm(Species~Petal.Width+Petal.Length, family = binomial(link = 'logit'), data = iris.learn); dfrm <- data.frame(Petal.Width=iris.valid$Petal.Width, Petal.Length=iris.valid$Petal.Length); real_sort <- iris.valid$Species; #測試數據集實際類別 prdict_res <- predict(logit.fit, type="response", newdata=dfrm); #預測數據產生概率 data.frame(predict=prdict_res, real=real_sort); #查看數據產生概率和實際分類的關係 data.frame(predict=ifelse(prdict_res>0.5, "virginica", "versicolor"), real=real_sort); #根據數據產生概率生成預測分類 table(data.frame(predict=ifelse(prdict_res>0.5, "virginica", "versicolor"), real=real_sort)); #計算分類準確度 Sepal.Length Sepal.Width Petal.Length Petal.Width Species 1 5.1 3.5 1.4 0.2 setosa 2 4.9 3.0 1.4 0.2 setosa 3 4.7 3.2 1.3 0.2 setosa 4 4.6 3.1 1.5 0.2 setosa 5 5.0 3.6 1.4 0.2 setosa 6 5.4 3.9 1.7 0.4 setosa

在R中對kyphosis數據集進行Logistic回歸分類並評估分類模型。 R實戰-Logistic回歸 在R中對kyphosis數據集進行Logistic回歸分類並評估分類模型。 install.packages("DAAG") library(DAAG) ##用匯總的數據進行建模，以打麻醉劑的用量不同進行匯總，並計算病人不動的比例 anestot=aggregate(anesthetic[,c('move','nomove')],by=list(conc=anesthetic$conc),FUN=sum) anestot$conc=as.numeric(as.character(anestot$conc)) anestot$total=apply(anestot[,c('move','nomove')],1,sum) anestot$prop=anestot$nomove/anestot$total ##用病人未移動的概率與麻醉劑量做logistic分析 anes2=glm(prop~conc,family=binomial(link='logit'),weights=total,data=anestot) summary(anes2) plot(prop~conc,pch=16,col='red',data=anestot,xlim=c(0.5,3),main='Logistic回歸曲線圖',ylab='病 人靜止概率',xlab='麻醉劑量') lines(anestot$conc,fitted(anes2),lty=2,col='blue') move conc logconc nomove 1 0 1.0 0.0000000 1 2 1 1.2 0.1823216 0 3 0 1.4 0.3364722 1 4 1 1.4 0.3364722 0 5 1 1.2 0.1823216 0 6 0 2.5 0.9162907 1 本例來自於John Maindonald所著的《Data Analysis and Graphics Using R》一書，數據集anesthetic來自於一組醫學數據，調查了30例患者在做手術之前的15分鐘，給予預定水準的麻醉劑，觀察患者在這15分鐘的表現，是否有如肌肉抽搐和身體扭曲等的表現，如果有上述表現統稱為有移動，其中變數conc表示麻醉劑的用量，move則表示手術病人是否有所移動；用nomove作為因變數，研究conc的增加是否會使nomove的概率增加。 ##（0）安裝並加載包“DAAG” install.packages('DAAG') library(DAAG) ##（1）載入數據集 data(anesthetic);head(anesthetic) ##（2）作出條件密度圖，觀察變數之間的關係曲線 cdplot(factor(nomove)~conc,data=anesthetic,main='條件密度圖',ylab='病人移動',xlab='麻醉劑量') ##（3）用匯總的數據進行建模，以打麻醉劑的用量不同進行匯總，並計算病人不動的比例 anestot=aggregate(anesthetic[,c('move','nomove')],by=list(conc=anesthetic$conc),FUN=sum) anestot$conc=as.numeric(as.character(anestot$conc)) anestot$total=apply(anestot[,c('move','nomove')],1,sum) anestot$prop=anestot$nomove/anestot$total ##（4）用病人未移動的概率與麻醉劑量做logistic分析 anes2=glm(prop~conc,family=binomial(link='logit'),weights=total,data=anestot) summary(anes2) plot(prop~conc,pch=16,col='red',data=anestot,xlim=c(0.5,3),main='Logistic回歸曲線圖',ylab='病人靜止概率',xlab='麻醉劑量',lines(y~x,lty=2,col='blue')) lines(anestot$conc,fitted(anes2),lty=2,col='blue')

內容概要 分類的基本概念與步驟 分類的常用方法 基於距離的分類方法 決策樹分類方法 組合分類 貝葉斯分類 Logistic回歸分類 支持向量機分類 分類有關的問題

線性分類器 x f y f(x,w,b) = sign(w. x - b) +1 -1 如何對左圖的數據進行分類？

線性分類器 f y x f(x,w,b) = sign(w. x - b) +1 -1 如果g1(x)>0，則判定x屬於C1， g1(x)=w1. x –b1

線性分類器 f y x f(x,w,b) = sign(w. x - b) +1 -1 如果g2(x)>0，則判定x屬於C1， g2(x)=w2. x –b2

線性分類器 f y x f(x,w,b) = sign(w. x - b) +1 -1 g3(x)=w3. x –b3 如果g3(x)>0，則判定x屬於C1， 如果g3(x)<0，則判定x屬於C2， 如果g3(x)=0，則可以將x任意 g3(x)=w3. x –b3

線性分類器 x f y f(x,w,b) = sign(w. x - b) +1 -1 滿足分類條件的直線有多條！ 哪一條是最優的？

線性分類器 f y 衡量指標： x f(x,w,b) = sign(w. x - b) +1 -1 線性分類器的間隔（Margin）：到超平面最近的樣本與此超平面之間的距離。

最大間隔 f y x f(x,w,b) = sign(w. x - b) +1 -1 具有最大間隔的線性分類器叫做最大間隔線性分類器。 其就是一種最簡單的支持向量機(SVM) (稱為線性支持向量機，即LSVM) 線性支持向量機

支持向量機（SVM） f y x f(x,w,b) = sign(w. x - b) +1 -1 具有最大間隔的線性分類器叫做最大間隔線性分類器。 其就是一種最簡單的支持向量機(SVM) (稱為線性支持向量機，即LSVM) 支持向量(Support Vectors) :是那些距離超平面最近的點。 線性支持向量機

支持向量機（SVM） SVM是從線性可分情況下的最優分類面發展而來的 圖中, 方形點和圓形點代表兩類樣本, H為分類線,H1,H2分別為過各類中離分類線最近的樣本且平行於分類線的直線, 它們之間的距離叫做分類間隔(Margin)。   所謂最優分類線就是要求分類線不但能將兩類正確分開(訓練錯誤率為0),而且使分類間隔最大. 推廣到高維空間，最優分類線就變為最優分類面。

支持向量機：廣義最優分類面

支持向量機：廣義最優分類面 最優分類面問題可以表示成約束優化問題 凸優化問題：So Easy！ 定義Lagrange函數 Minimize Subject to 定義Lagrange函數 凸優化問題：So Easy！

核函數：升維—低維不可分問題未必高維也不可分 支持向量機：核函數 SVM處理線性可分的情況，而對於非線性的情況？ 核函數：升維—低維不可分問題未必高維也不可分

支持向量機：核函數 可以使用核函數，將輸入空間映射到特徵空間，從而，使得原本線性不可分 的樣本可以在特徵空間可分。 在實際應用中，往往依賴先驗領域知識才能選擇有效的核函數 多項式核函數 高斯核函數 字串核函數 如：兩個字串的最長公共子序列LCS(X,Y)

？ 支持向量機：舉例 給定3個數據點：正例點x1=(3,3)T，x2 =(4,3)T，負例點x3=(1,1) T， 求線性可分支持向量機。

支持向量機：舉例 Lagrange對偶問題

將約束帶入目標函數，化簡計算 將α3= α1+α2帶入目標函數，得到關於α1、α2的函數： 對α1,α2求偏導並令其為0，易知s(α1,α2)在點(1.5,-1)處取極值。而該點不滿足 條件α2≥0，所以，最小值在邊界上達到。 當α1=0時，最小值s(0,2/13)=-2/13； 當α2=0時，最小值s(1/4,0)=-1/4； 於是，s(α1,α2)在α1=1/4，α2=0時達到最小，此時，α3= α1+α2=1/4。

分離超平面 α1=α3=1/4對應的點x1，x3是支持向量。 帶入公式： 得到w1=w2=0.5，b=-2 因此，分離超平面為 分離決策函數為

在R中對iris數據集進行SVM分類並評估分類模型。 library(e1071) set.seed(1234) ind<-sample(2,nrow(iris),replace=TRUE,prob=c(0.7,0.3)) #70%為訓練集 30%為測試集 train<-iris[ind==1,] test<-iris[ind==2,] ##演算法的調用 svm<-svm(train[,1:4],train[,5],type="C-classification", cost=10,kernel="radial",probability=TRUE,scale=FALSE) pred<-predict(svm,test[,1:4],type="probabilities") #檢驗集的預測 table(pred,test[,5]) #混淆矩陣 Sepal.Length Sepal.Width Petal.Length Petal.Width Species 1 5.1 3.5 1.4 0.2 setosa 2 4.9 3.0 1.4 0.2 setosa 3 4.7 3.2 1.3 0.2 setosa 4 4.6 3.1 1.5 0.2 setosa 5 5.0 3.6 1.4 0.2 setosa 6 5.4 3.9 1.7 0.4 setosa

內容概要 分類的基本概念與步驟 分類的常用方法 基於距離的分類方法 決策樹分類方法 組合分類 貝葉斯分類 Logistic回歸分類 支持向量機分類 分類有關的問題

分類數據預處理 分類的效果一般和數據的特點有關，有的數據噪聲大，有的有空缺值，有的分佈 稀疏，有的字段或屬性間相關性強，有的屬性是離散的而有的是連續值或混合式 的。目前普遍認為不存在某種方法能適合於各種特點的數據。因此，在分類以前 需要做一些數據的預處理。 數據清理 主要是消除或減少數據噪聲和處理空缺值。 特徵選擇 從已知一組特徵集中按照某一準則選擇出有很好的區分特性的特徵子集 或按照某一準則對特徵的分類性能進行排序，用於分類器的優化設計。 數據變換 就是通過平滑、聚集、數據概化、規範化、特徵構造等手段將數據轉化為適合於挖掘的形 式。

分類器性能的表示 分類器性能的表示方法類似資訊檢索系統的評價方法，可以採用OC 曲線和ROC曲線、混淆矩陣等。 定義4-3 給定一個類Cj和一個資料庫元組ti，ti可能被分類器判定為屬於Cj或不屬於 Cj，其實ti本身可能屬於Cj或不屬於Cj，這樣就會產生如下一些情況： 真正: 判定ti在Cj中，實際上的確在其中。 假正: 判定ti在Cj中，實際上不在其中。 真負: 判定ti不在Cj中，實際上不在其中。 假負: 判定ti不在Cj中，實際上的確在其中。 在上述定義的基礎上，人們經常使用OC曲線和ROC曲線表示“假正”和“真正” 的關係。OC曲線通常用於通信領域來測試誤報率。OC曲線的水準軸一般表示 “假正”的百分比，另外一個軸表示“真正”的百分比。

分類器性能的表示（續） 混淆矩陣是另外一種表示分類準確率的方法。假定有m個類，混淆 矩陣是一個 m*m 的矩陣，Ci,j表明了D中被分到類Cj但實際類別是Ci 的元組的數量。顯然地，最好解決方案是對角線以外的值為全零。 混淆矩陣示例 實 際 分 類 矮 中等 高 4 5 3 1 2

分類器性能的評估 保持法和交叉驗證是兩種基於給定數據隨機選樣劃分的、常用的評估分 類方法準確率的技術。 （1）保持法 把給定的數據隨機地劃分成兩個獨立的集合：訓練集和測試集。通常，三分之二 的數據分配到訓練集，其餘三分之一分配到測試集。使用訓練集得到分類器，其 準確率用測試集評估。 （2）交叉驗證 先把數據隨機分成不相交的n份，每份大小基本相等，訓練和測試都進行n次。比 如，如果把數據分成10份，先把第一份拿出來放在一邊用作模型測試，把其他9份 合在一起來建立模型，然後把這個用90%的數據建立起來的模型用上面放在一邊的 第一份數據做測試。這個過程對每一份數據都重複進行一次，得到10個不同的錯 誤率。最後把所有數據放在一起建立一個模型，模型的錯誤率為上面10個錯誤率 的平均。

謝謝！