【正文】 樹也利用二分劃分數(shù)據(jù)?？梢钥闯鰣D 14利用切分點s將特征空間進行劃分，y是在劃分單元上的輸出值。如圖 13所示就是一個分類樹。分類問題輸出特征向量對應的分類結果，回歸問題輸出特征向量對應的預測值。而且二分策略可以直接處理連續(xù)型屬性值。它們利用信息增益和信息增益比劃分數(shù)據(jù)集。為了便于理解，仍然使用表格 8所示數(shù)據(jù)集進行說明。類別039。類別039。劃分后，如果是圓的:1，則分類:1；如果是圓的:0, 則分類:0。 第二種為如果是紅的:1, 則得到如下數(shù)據(jù)子集 {圓的:1,分類：1。為了便于理解，用表1所示數(shù)據(jù)集進行詳細說明。除了可以使用信息增益和信息增益比來選擇最優(yōu)劃分特征之外，基尼指數(shù)也可以用來實現(xiàn)這個目的。特征 A 對數(shù)據(jù)集 D 的信息增益 g(D,A)為 D 的信息熵與按特征 A 進行劃分后 D 的信息熵之差，即其中， . 信息增益比 – 用于 決策樹信息增益比為了避免傾向于選擇屬性值多的特征作為最優(yōu)特征這個問題，在信息增益的基礎上引入了類似懲罰因子的概念。. 決策樹原理. 選擇最優(yōu)特征決策樹通過不斷選擇最優(yōu)特征劃分數(shù)據(jù)集，對劃分后的子數(shù)據(jù)集不斷迭代得選擇最優(yōu)特征劃分，直到所有的數(shù)據(jù)集屬于同一個類別，或者沒有特征可以選擇為止。這種缺陷體現(xiàn)在信息增益對選擇屬性取值多的特征更有利。用所有類別所有可能值包含的信息期望值表示信息熵，計算方法如下：ID3 決策樹利用了信息增益來選擇最優(yōu)特征，用這種方法選擇的特征是使得信息熵增益最大的特征。衡量數(shù)據(jù)的混亂程度就必須提到信息和信息熵的概念。圖 12 決策樹示例圖1所示決策樹用來將數(shù)據(jù)分為兩類，是蘋果和非蘋果。決策樹利用了樹型結構進行決策，是經(jīng)典的 ifthen 結構。6. 決策樹基本原理決策樹算法又分很多種，常用的有ID3， 和 CART 決策樹。campus39。已知：如果 log(P(X|C0) *P(C0) ) log(P(X|C1) *P(C1) )，則 P(C0|X) P(C1|X)，可得 X 屬于 C0 類；如果 log(P(X|C0) *P(C0) ) log(P(X|C1) *P(C1) )，則 P(C0|X) P(C1|X)，可得 X 屬于 C1 類。others39。campus39。sky39。others39。campus39。book39。, 39。表格 5 示例測試數(shù)據(jù)集類別訓練文本？39。039。139。, 39。, 39。, 39。最終比較 P(C0|X)、P(C1|X)大小得到 X 屬于 C0 類還是 C1 類。鑒于此，往往在實際運算中，會借助 log 函數(shù)，比較 log(P(X|C0) *P(C0)) 和 log(P(X|C1) *P(C1))的大小來判斷 X 所屬類別。為了避免 P(Xi|C)為 0 造成 P(X|C)為 0 而影響分類結果，在此引入拉普拉斯平滑，本文分別給分子和分母加上 1 和 2，即 P(Xi|C) = (|Dc,xi| + 1) / (|Dc,x| + 2)。其中 P(C)稱為先驗概率，P(X|C)是條件概率，P(C|X)稱為后驗概率，將后驗概率最大的類作為 X 的類別輸出。這種情況需要考慮半樸素貝葉斯，即放松屬性之間條件獨立這一假設，一定程度上考慮屬性之間的依賴關系。詞向量的每一項是該詞出現(xiàn)的頻數(shù)。5. NaiveBayes基本原理樸素貝葉斯模型主要用來分類，但是與 SVM 模型不同的的是，樸素貝葉斯模型不需要針對目標變量建立模型，而是借助貝葉斯公式計算樣本屬于各個類別的概率，然后取概率值大的類別作為分類類別。圖 11 b元素的前綴路徑構成的條件FP樹將其他元素 a,b,d 同樣按照上述對 c 的操作，得到表格 3所示頻繁項集。2. 對元素 b，獲得前綴路徑{a}，則將前綴路徑創(chuàng)建成條件 FP 樹，如圖 11所示。首先，獲得以 c 元素的前綴路徑{a:2,b:2}，注意此處 a 和 b 的頻數(shù)為 2 是因為 c 的頻數(shù)為 2，所以與 c 共同出現(xiàn)的 a 和 b 的頻數(shù)就都為 2。具體過程為：首先獲得頻繁項的前綴路徑，然后將前綴路徑作為新的數(shù)據(jù)集，以此構建前綴路徑的條件 FP 樹。創(chuàng)建 FP 樹時，當待添加的記錄與 FP 樹中的路徑相同，則只需更新元素對應的頻數(shù)；如果待添加的記錄與 FP 樹存在不一致，則在不一致的地方分叉，創(chuàng)建新的結點。下面用上文提到的數(shù)據(jù)集展開說明，假設最小支持度為 2。. 頻繁項集挖掘原理頻繁項集挖掘分為構建 FP 樹，和從 FP 樹中挖掘頻繁項集兩步。} {39。如規(guī)則{39。}的置信度為 / = 。, 39。, 39。, 39。假設{39。雞蛋39。面包39。牛奶39。雞蛋39。面包39。面包39。. 支持度 Support支持度指某頻繁項集在整個數(shù)據(jù)集中的比例。牛奶39。雞蛋39。. 關聯(lián)規(guī)則簡介關聯(lián)規(guī)則是在頻繁項集的基礎上得到的。FPgrowth，即 Frequent Pattern Growth，它通過構建 FP 樹(即 Frequent Pattern Tree)這樣的數(shù)據(jù)結構，巧妙得將數(shù)據(jù)存儲在 FP 樹中，只需要在構建 FP 樹時掃描數(shù)據(jù)庫兩次，后續(xù)處理就不需要再訪問數(shù)據(jù)庫了。3. 用于發(fā)現(xiàn)事物的熱點信息。這種場景其實我們經(jīng)常會遇到。那么發(fā)現(xiàn)這些頻繁項集有什么意義呢？1. 用于制定營銷策略。有研究發(fā)現(xiàn)，在超市的訂單記錄中，啤酒和尿布總是頻繁共同出現(xiàn)在同一條訂單記錄里。第一篇中的 SVM 就屬于分類。有朋友就會問，求出 alpha 之后呢？如何判斷新樣本數(shù)據(jù)屬于 1 還是1 呢？別忘了，在最優(yōu)化求解一節(jié)，我們得到了如下：若 f(x)大于 0，則新樣本數(shù)據(jù)屬于 1；否則，新樣本數(shù)據(jù)屬于1。下面是詳細的 SMO 過程。由于目標變量中自變量 alpha 有 N 個，為了便與求解，每次選出一對自變量 alpha，然后求目標函數(shù)關于其中一個 alpha 的偏導，這樣就可以得到這一對 alpha 的新值。為什么說不用一一映射到高維空間很有用呢？原因就在于首先我們無法針對每種情況提供精確的映射函數(shù)，再者對于需要映射到無窮維的情況顯然無法一一映射完成。倘若能將超平面換成超曲面，則可以將正負樣本正確分類，如圖 5所示。那么，對每個不等式約束引入拉格朗日乘子，得到拉格朗日函數(shù)如下：分析可知：則原最優(yōu)化問題轉換成： 由于原最優(yōu)化問題直接求解很困難，利用拉格朗日對偶性，可通過求解原最優(yōu)化問題的對偶問題得到原問題的最優(yōu)解。圖 4 Outlier特異點為了解決這種問題，對每個樣本點引進一個松弛變量，使得約束條件變?yōu)椋哼@樣給 outlier 的約束條件加上一個變量，使其可以滿足大于等于 1 的條件。既然要最大化間隔，那么回顧下點x到超平面(w,b)的距離公式：其中超平面的公式為：由此可推出點 x 到超平面(w,b)的幾何間隔為： 其中 xi代表第i條數(shù)據(jù)，yi代表第i條數(shù)據(jù)對應的目標變量的取值，取值有+1 和1 兩種。. 軟間隔最大化SVM的核心思路是最大化支持向量到分隔超平面的間隔。2. 不支持類別型數(shù)據(jù)，需在預處理階段將類別型數(shù)據(jù)轉換成離散型數(shù)據(jù)。SVM的優(yōu)點是：1. 可以解決線性不可分的情況。支持向量到分類超平面的間隔最大化的思路很完美，按這種思路得到的模型理論上是準確度最高的一種模型。如圖 1所示，支持向量到超平面1的間隔大于支持向量到超平面2的間隔，因此超平面1優(yōu)于超平面2。分類算法主要包括K近鄰、決策樹、樸素貝葉斯、邏輯回歸、支持向量機、AdaBoost等；回歸主要包括線性回歸、嶺回歸、lasso、樹回歸等；聚類主要包括 KMeans 以及它的各種變形算法；關聯(lián)分析主要包括 Apriori、FPgrowth 等算法。回歸是根據(jù)特征值、目標變量擬合出特征值與目標變量之間的函數(shù)關系，可用來估計特征值對應的目標變量的可能取值。分類就是給定大量帶標簽的數(shù)據(jù)，計算出未知標簽樣本的標簽取值。其中提到的規(guī)律有很多種，比如分類、聚類、回歸、關聯(lián)分析等。如電信行業(yè)可以根據(jù)用戶的月長途電話分鐘數(shù)、上網(wǎng)時長、短信使用數(shù)、地理位置、月消費數(shù)，將所有用戶聚集成有典型特征的簇，聚集出的某簇特征可能是月長途電話分鐘數(shù)長、上網(wǎng)時間長、地理位置變化不大、月消費數(shù)目低，分析可得這類人極有可能是在校大學生，那么電信公司就可以針對這類特定人群制定有針對性的營銷策略。如超市訂單中有大量訂單同時包含啤酒與尿布，這其中的頻繁項就是啤酒和尿布，那么超市就可以針對這個規(guī)律對啤酒和尿布進行組合促銷活動。出發(fā)點很容易理解，距離分類超平面近的那些點到該超平面的間隔最大化代表了該超平面對兩類數(shù)據(jù)的區(qū)分度強，不容易出現(xiàn)錯分的情況。然后將測試數(shù)據(jù)分別帶入3個SVM模型中，得到的3個結果中的最大值則為最終的分類結果。任何模型都是優(yōu)點與缺點并存的。SVM 的缺點是：1. 經(jīng)典的 SVM 算法僅支持二分類，對于多分類問題需要改動模型。雖然這些名詞看起來很晦澀，但是深入探索后就會發(fā)現(xiàn)其中的思想并沒有那么復雜。因此，我們下面首先需要推導出SVM模型的目標函數(shù)和約束條件?？紤]到現(xiàn)實生活中的真實數(shù)據(jù)，存在一些特異點即 outliers，這些數(shù)據(jù)點并不滿足上面推導出的約束條件，如圖 4所示，圖中點 A 就是 outlier 特異點。. 拉格朗日對偶對于凸二次優(yōu)化問題，通過引入拉格朗日乘子，將目標函數(shù)和約束條件整合到拉格朗日函數(shù)中，這樣能方便求解最值問題。對三個變量分別求偏導得： 將以上三式帶入拉格朗日函數(shù)中得：那么極大極小化拉格朗日函數(shù)轉換成：為求解方便，將極大轉換成極小得： . 核函數(shù)對于線性不可分問題，如圖 2所示，這類問題是無法用超平面劃分正負樣本數(shù)據(jù)的。這點非常有用，利用核函數(shù)，無需先將變量一一映射到高維空間再計算內(nèi)積，而是簡單得在低維空間中利用核函數(shù)完成這一操作。運用核函數(shù)后，最優(yōu)化問題的目標函數(shù)和約束條件變?yōu)椋? . 序列最小優(yōu)化 (Sequential minimal optimization)到目前為止，優(yōu)化問題已經(jīng)轉化成了一個包含 N 個 alpha 自變量的目標變量和兩個約束條件。為何不能每次只選一個自變量進行優(yōu)化？那是因為只選一個自變量 alpha 的話，會違反第一個約束條件，即所有 alpha 和 y 值乘積的和等于 0。按上述方法不斷選擇一對 alpha 并更新，直到達到最大迭代次數(shù)或所有 alpha 都不再變化，則停止迭代。在文章一開始，筆者提到機器學習主要分為四大類，分別是分類，聚類，回歸和關聯(lián)分析。生活中的數(shù)據(jù)本身包含著各種規(guī)律，機器學習模型可以從數(shù)據(jù)中挖掘出這些規(guī)律，啤酒與尿布就是一個典型的例子。頻繁項集是在數(shù)據(jù)庫中大量頻繁出現(xiàn)的數(shù)據(jù)集合。2. 用于發(fā)現(xiàn)共現(xiàn)詞。同理，頻繁項集和關聯(lián)規(guī)則也頻繁得共同出現(xiàn)在搜索記錄中。其中 Apriori 算法需要多次掃描數(shù)據(jù)庫，這就使得該算法本身不適合大數(shù)據(jù)量。挖掘出頻繁項集后，可以從頻繁項集中進一步挖掘關聯(lián)規(guī)則。舉個例子，有關聯(lián)規(guī)則如：{39。} {39。這其中需要先闡明兩個概念：支持度和置信度。, 39。, 39。有關聯(lián)規(guī)則如{39。} {39。, 39。}的支持度/{39。}的支持度。面包39。雞蛋39。雞蛋39。牛奶39。在信息安全領域，需要根據(jù)已有流量數(shù)據(jù)制定規(guī)則，來判斷是否觸發(fā)安全報警。