本文的筆記來源于<<Web 數據挖掘>> Bing Liu著

監督學習：分類（Classification）或歸納學習（Inductive Learning）

1. 基本概念

屬性值（Attribute-Values）： A = ｛A1， A2， ...， An｝來描述

類標（Class Label）：C = ｛c1，c2，...， cn｝

一個用于學習的數據集就是一張關系表，表里的每條記錄描述了一條“以往經驗”

一條數據記錄即一個case

給出一個DataSet，機器學習的目標 即產生一個聯系屬性值集合A和類標集合C的分類/預測函數（Classification/Predication Function），該函數可用于預測新的屬性集合（數據實例）的類標。

該函數也被稱為分類模型（Classification Model）、預測模型（Predictive Model）或簡稱淡分類器（Classifier）.

監督學習（Supervised Learning）：所有數據已經給出了類標?

無監督學習（Unsupervised Learning）：所有的類屬性都是未知的

訓練數據集（Training Data）：算法用于進行學習的數據集叫做訓練數據集

測試數據集（Test Data）：當學習算法（Learning Algorithm）用訓練數據學習得到一個模型后，使用測試數據集來評測該模型的精準度。

分類精準度 = 正確分類的測試用例個數/測試用的總數

訓練過程（Training Step） -> 訓練階段（Training Phase）

測試過程（Testing Step）-> 測試階段（Testing Phase）

2. 決策樹推理

得到的分類模型表示是一棵樹的形式，稱之為決策樹（Decision Tree）

決策節點（Decision Nodes中間節點）

葉子節點（Leaf Nodes）

純的子集（Pure Subset）：數據實例類標全部一致

（1）學習算法

分治（Divide-and-Conquer）策略：遞歸的對訓練數據進行分隔，從而構造決策樹。

最開始的時候，所有的數據樣例都在根部，隨著決策樹的增長，樣例被不斷的遞歸的分隔。

遞歸的終止條件（Stopping Criteria）：當所有的當前節點中的數據都屬于同一類時，迭代終止。

在學習算法中，每一個后續的遞歸都選擇最佳分類屬性（Best Attribute）作為分隔當前數據實例集的屬性。

最佳分類屬性的選擇是通過一個混雜度函數（Impurity Function）來實現的：這個函數反映了用該屬性進行

數據分隔后的數據集的混雜度。

（2）混雜度函數

信息增益（Information Gain）：

信息增益率（Information Gain Ratio）：

（3）處理連續屬性

為將決策樹構建算法應用于連續屬性，在一個樹節點中可以將屬性Ai的值劃分成幾人上區間，每個區間可被視為一個離散值。

C4.5中采用了二元分割（Binary Split），可使用一個合適的分割閾值（Threshold）

（4）其他問題

剪枝和過度擬合（Tree Pruning and Overfitting）

過度擬合：一個決策樹算法遞歸地劃分數據，直到不純凈度為0或沒有其他屬性。這個過程可能得到深度很大的樹，其中很多葉子節點只覆蓋很少數目的訓練實例。若用這樣的一棵樹去預測訓練集，其精度將非常高；但當它用來對測試數據進行分類時，其精度可能會非常低。這樣的學習結果是意義不大的，也即決策樹不能很好地泛化到所有數據上。這種現象即為過度擬合（Overfitting）。

為減少過度擬合，可對樹進行剪枝，即刪除一些子樹或分支，用多個類的葉節點代替這些分支。一個是提早結束（Stopping Early）樹構建過程（稱為預剪枝，Pre-pruning）；另是在樹構建完畢之后再剪枝（稱為后剪枝，Post-pruning）。一般認為后剪枝比較有效，預剪枝會有危險，因不知道在算法停止前，當樹進一步擴展后會發生什么。

驗證集合（Validation Set）：使用另一個在訓練和測試過程中都未被使用的獨立數據集來進行，這個獨立數據集通常稱為驗證集合。在生成了一個決策樹后，首先使用它來對驗證集合上的數據進行分類。

規則剪枝（Rule Pruning）：一棵決策樹可以被轉換成一組規則的結合，

泛化（Generalization）：因剪枝命名得規則變得 更加一般（具有較少條件限制），即泛化。

特殊（Specific）：具有較多條件限制的規則被稱為比具有較少條件限制的規則要特殊。

經剪枝后所得到的規則集合可能不再是互不相交且完全覆蓋（Mutually Exclusive and Exhaustive）。

在處理那些不滿足任何一個規則條件的測試數據時，可將它分類為一個默認類別（Default Class），通常是數據點最多的類。

處理缺失屬性值（Handling Missing Attribute Values）：eg：屬性缺失時，離散屬性可采用使用屬性中出現最為頻繁的屬性值；連續值屬性，可使用屬性的平均值來填充缺失值。

處理偏斜類別分布（Handling Skewed Class Distribution）：eg：對數據進行排序，采用排名靠前的情況。

3.評估分類器

分類精度（Accuracy）：即用在測試集中被正確分類的數據數量除以測試集中的數據數量得到。

錯誤率（Error Rate）：即1-accuracy

（1）評估方法

Holdout集合：測試集也被稱為holdout集。一般情況下采用50-50或三分之二用于訓練，三分之一用于測試。

將D劃分成訓練集和測試集：

從D 中隨機采樣一組數據作為學習所用，其余部分用于測試；若數據采集是不斷累積的，可使用采集時間較早的數據來進行訓練/學習，用時間靠后的數據進行訓練。

多次隨機采樣：當可用數據集比較小時，測試數據集可能會太小而不具有代表性，解決這一問題的方法是進行n次隨機采樣過程，每次都產生一個不同的訓練集合和一個不同的測試集合，同時產生n個測試精度。在數據上最終的估計精度值這n個測試精度的平均值。

交叉驗證（cross-Validation）：當數據集合較小時，n重交叉驗證（n-fold Cross-Validation）是經常被采用的方法。該方法中，可用數據集被分成n個不相交的等大數據子集。然后每個子集被當作測試集，其余的n-1個子集合起來當作是訓練集用來學習得到分類器。

缺一交叉驗證（Leave-One-Out Cross-Validation）：在每次交叉驗證中只有一個測試數據，其余的數據被用于訓練。即若初始數據共有m個數據點，則這種方法就是一個m重交叉驗證。該方法可用于數據很小的情況下，而對于大數據集來說這這種驗證驗證過程中建立m個分類器往往是很低效的。

（2）查準率、查全率、F-score 和平衡點（Breakeven Point）

正例類別（Postive Class）：那些用戶感興趣的類別

負例類別（Negative Class）：除正例類別外的

?	分類為正例	分類為負例
實際為正例	TP	FN
實際為負例	FP	TN

查準率（p）：正確分類的正例數量 / 被分類的正例數量 ? p = TP / (TP+ FP)

查全率（r）：被正確分類的正例 / 測試數據集中實際正例數量 ?r = TP / (TP+FN)

F-score：查準率和查全率的調和平均值。 F = 2*p*r / (1/p + 1/r)

平衡點：查準率和查全率的平衡點，即兩者相等的地方。r = p

4. 規則推理

（1）序列化覆蓋

有序化的規則（Ordered Rules）

有序化的類（Ordered Classes）

（2）規則學習：Learn-One-Rule函數

5. 基于關聯規則的分類

（1）使用類關聯規則進行分類

類關聯規則（CAR）：

CBA（Classification Based on Association）

（2）類關聯規則挖掘

規則剪枝：

多個不同的最低支持度：

?稀有類：一個單獨的最小支持度是不夠的，因DataSet的分布可能是非常不均勻的，可能一個類占據了數據的大多數，而另一個類在數據集中只有很小的比例，可賦予不同的最低支持minsup，使用一個全局的最低支持度t_minsup，可得到各個類的最低支持度。

6. 樸素貝葉斯 分類

條件獨立：

數值屬性： 離散的，連續數據需經離散化處理

估計產生的零概率：

丟失的數據：丟失的數據可被忽略，無論是在訓練時估計概率還是分類時計鼻概率。

7. 樸素貝葉斯文本分類

（1）概率框架

生成模型主要基于兩個假設：

數據（文檔）由一個混合模型生成；混合模型的每一個成分和類別一一對應。

（2）樸素貝葉斯模型

樸素貝葉斯學習效率很高，因只需對訓練數據進行一次掃描即可估計出所有需要的概率，可作為增量算法使用。

8. 支持向量機

支持向量機是一個線性的學習系統，可用于兩類的分類問題 輸入向量： 每個數據樣例 超平面：決策邊界（Decision Boundary）或決策面（Decision Surface） 法向量：
線性支持向量機：數據可分的情況： 給定一組線性可分的訓練樣本，D = ｛（x1， y1），（x2，y2），......，（xn， yn）｝， 學習問題即解決最小化問題（constrained minimization problem）： 最小化：<w*w>/2 滿足：yi（<w*xi> + b）>= 1
解決問題可得到w和b的解，就得到了具有最大邊距2/|w|的超平面<w*x> + b = 0

（1）線性支持向量機：數據不可分的情況

實際上訓練數據是有噪聲的，即某些原因存在誤差

采用拉格良朗日乘子

（2）非線性支持向量機：核方法

之前討論的支持向量機需要正負便被 線性分隔，即決策邊界必須是一個超平面。為解決非純屬分割的數據，需將原始的輸入數據變換成另一個空間（通常是一個更高維的空間），這樣在的空間中可以用線性決策邊界分割正例和負例，這個新的空間被稱為特征空間，原始的數據空間被稱為輸入空間。

9. k-近鄰學習

決策樹、規則集合（sets of rules）、后驗概率及超平面 均屬迫切學習（Eager Learning）方法

k近鄰（kNN）是一種惰性學習（Lazing Learning）方法

10. 分類器的集成

（1）Bagging

給定一個有n個樣例的訓練集合D和一個基本的學習算法，bagging（Bootstrap Aggregating）是這樣實現的：

訓練：

生成k個bootstrap樣本集合S1，S2，...， Sk，每個樣本集合都由有放回地從D中隨機抽取得到（drawing at random with replacement）。這樣一個樣本集合被稱為原始訓練樣本D的一個自展復制（Bootstrap Replicate）。每個樣本集合Si平均含有63.2%的原始樣本D，其中一些樣本可能復制出現。

對每一個樣本集合Si都構造一個分類器，將得到的k個分類器，所有分類器由同樣的基本學習算法得到。

測試：

對每個測試樣例進行分類，由k個分類投票（權重相同）決定、占多數的類別將會被賦予那個測試樣例。

（2）Boosting

Boosting指的是一組集成方法，通過操作訓練樣本和生成許多分類器來提高分類準確率。

AdaBoost算法：給每個訓練樣本賦予不同的權重。

總結

以上是生活随笔為你收集整理的数据挖掘之监督学习篇的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。