数据挖掘（Data Mining）扫盲笔记
知識框架來源：人工智能之數據挖掘
其他補充來源：拿下Offer-數據分析師求職面試指南、數據分析實戰45講
Data Mining
- 概述篇
- 基礎認知
- 挖掘對象
- 常見任務：
- 模型分類
- 問題與挑戰
- 十大經典算法
- C4.5
- 1. 決策樹
- 2.信息增益（ID3 算法）
- 3.信息增益率（C4.5 算法）
- 項目鏈接
- CART（Classification and Regression Trees）
- 1.定義
- 2.基尼系數
- 核心解讀
- 項目鏈接
- KNN（K-Nearest Neighbor）
- 1.定義
- 2.核心解讀
- 項目鏈接
- K-Means.
- 1. 定義
- 2.核心解讀
- 項目鏈接
- Naive Bayes 樸素貝葉斯法
- 1.相關定義
- 工作原理
- SVM（Support Vector Machine）
- 1.基本認知
- 2.項目
- EM（Expectation Maximization
- 1.基本認知
- 2.案例：EM 算法的基本思想
- Page Rank.
- 1.介紹
- Apriori
- 1.基本認知
- AdaBoost.
- 1.基本認知
- 算法示例
- 模型效果評估
- 預測模型評估：
- 二分類模型評估：
概述篇
基礎認知
-
廣義：
一類深層次的數據分析方法 -
目的：
自動抽取隱含的、以前未知的、具有潛在應用價值的模式或規則等有用知識 -
涉及學科
使用人工智能、機器學習、統計學和數據庫等交叉學科領域方法 -
對象
大規模、不完全、有噪聲、模糊隨機的數據集。 -
核心過程：
（1） 數據清理：消除噪聲和刪除不一致數據。
（2） 數據集成：將多種數據源組合在數據倉庫。
（3） 數據選擇：定義問題，從數據庫中提取與分析任務相關的數據。
（4） 數據變換：分析整理數據。通過匯總或聚集操作把數據變換、統一成適合挖掘的形式。
（5） 數據挖掘：使用智能方法提取數據模式。
（6） 模式評估：根據某種度量，識別代表知識的模式。
（7） 知識表示：使用可視化與知識表示技術，向用戶提供挖掘的知識。 -
挖掘的核心
建模：另利用用模型學習已知數據集中的變量特征，并通過一系列方法提高模型的學習能力，最終對一些結果位置的數據及輸出相映的結果。 -
數據集
- 訓練集
訓練模型 ，用于模型訓練擬合的樣本，占總體樣本的百分之七十到百分之八十 - 驗證集
模型調試 ，結果已知不參與模型訓練擬合，用于驗證訓練后模型的擬合效果。對模型中的超參數進行選擇。在實際工作中 - 測試集
驗證結果，利用模型輸出結果的數據集模型上線后，輸出測試集的結果與最終結果進行對比。測試及后續可以轉換為訓練集或驗證及實現模型的循環迭代。
- 訓練集
-
模型評估
- 過擬合Overfitting
樣本量相對于模型復雜度較小,樣本噪聲導致復雜模型的泛化能力較差 。訓練集只是全部數據的抽樣，而且存在噪聲，該噪音不具有通用性并不能體現全部數據的特點,當模型過于復雜時，會太依賴于訓練集，也會大量學習訓練其中的噪音，并當成所有數據的特點。結果過于精準，容錯率就會比較低，導致分化能力變差。
泛化能力是指：分類器是通過訓練集抽象出來的分類能力。模型的“泛化能力”差,模型的訓練結果過分精準,以至于存在“死板”的情況，在實際應用的過程中，會導致分類錯誤。 - 欠擬合
表明模型過于簡單，沒有很好的擬合訓練集變量之間的特征。需要進一步提高復雜度。
- 過擬合Overfitting
-
參數
- 參數
通過模型對訓練集的擬合獲得，比如線性回歸模型中斜率和截距。 - 超參數
無法通過模型獲得在模型訓練前仍為給定的超參數，只能通過驗證及進行驗證并最終決定：決策樹的深度、隨機森林模型中樹的數量的。
- 參數
-
參數調整
- 工作量大 ：
模型調整參數,是一個非常耗時的工作,需要綜合考慮模型效果，實現復雜度以及工作量。 - 復雜度
模型屬性數相對于訓練集數，復雜的模型未必能帶來好的結果，也可能使得模型出現過擬合現象。導致誤差增加 - 平衡
需要平衡過擬合和欠擬合，降低整體的誤差。
- 工作量大 ：
-
誤差
- 偏差bias
模型的精準度。偏差高代表著：模型存在欠擬合的現象反應模型在訓練集上。期望輸出于真實輸出之間的差距。 - 方差variance
模型的穩定性。 方差高代表著模型過擬合。反映了模型在不同情況下得到的結果與真實結果之間的誤差。
- 偏差bias
-
算法的強弱
學習器的強弱。強學習器和弱學儀器是一個相對的概念，沒有很明確的劃分。體現在學習區對復雜場景的處理能力上。相對于決策樹模型，隨機森林是強學習器。但和其他更加復雜的模型相比，他就是弱學習器。 -
模型集成
- 將多個弱學習器（基模型）構造成一個強學習器。
能夠實現更好的效果的原因：模型的誤差包括偏差和方差，集成能夠降低方差。假設決策樹模型有相同的偏差和方差：將通過通過多個決策樹模型得到的結果進行平均或投票，可以保證隨機森林的偏差于單個決策樹模型的偏差基本相同，但是由于各個決策樹模型之間的相互獨立，對結果進行平均或加強之后，能夠大幅度減小隨機森林模型的方差，最終將誤差減小。 - 類型
- 同質集成模型：類似于隨機森林將，多個決策樹模型 、相同種類模型集成
- 異質集成模型：將不同種類的模型進行集成
- 集成方法
- Bagging 隨機對樣本進行隨機采樣，得到n個樣板間。對每一個樣本獨立訓練決策樹模型。通過集合策略輸出最終結果
- Boosting 新決策樹模型基于舊策樹模型的結果，方法
- AdaBoot ：加大此前決策樹模型中分類錯誤數據的權重，使得下一個生成決策樹模型能夠盡量將這些模型分類訓練正確。
- GBDT：通過計算損失函數梯度下降方向，定位模型的不足而建立新的決策樹模型。應用更廣泛。以Cart樹作為基模型
- 將多個弱學習器（基模型）構造成一個強學習器。
-
模型融合
在模型集成中將各個基模型的結果進行組合，得到最終的結果的過程稱為模型融合。- 方法
平均法 ：在預測問題中，將各個基模型的結果進行平均作為最終結果。
投票法 ：在分類問題中，選擇基模型中預測比較多的類別作為最終結果。
- 方法
-
與大數據的關系
- 大數據包含數據挖掘的各個階段，即數據收集、預處理、特征選擇、模式挖掘、知識表示等
- 大數據的基礎架構又為數據挖掘提供數據處理的硬件設施；
- 最后大數據的迅速發展也使得數據挖掘對象變得更為復雜不僅包括人類社會與物理世界的復雜聯系，還愈加明顯地呈現出高度動態化。要從大量無序數據中獲取真正價值，數據挖掘算法必須滿足對真實數據和實時數據的處理能力，這使得很多傳統算法不再適用
- 大數據的 5V 特性
目前比較公認的定義是麥肯錫全球研究機構（McKinsey Global Institute）也給出的，綜合了“現有技術無法處理”和“數據特征定義”，即規模龐大Volume）、種類繁多（Variety）、數據時效高（Velocity）和價值密度低（Value）。
-
發展歷程
-
知識圖譜
-
研究進展
近期的主要發展歸為兩大類：復雜數據挖掘與分布式數據挖掘。- 復雜數據包括序列數據、圖數據等。
- 分布式數據挖掘遵循“全局分布、局部集中”的挖掘原則，數據挖掘領域非常有前途的方向。
-
十大問題與挑戰
1 數據挖掘的統一理論框架的構建（Developing a Unifying Theory of DataMining）
2 高維數據和高速數據流的挖掘（Scaling Up for High DimensionalData/High Speed Streams）
3 序列和時序數據的挖掘（Mining Sequence Data and Time Series Data）
4 復雜數據中復雜知識的挖掘（Mining Complex Knowledge from ComplexData）
5 網絡環境中的數據挖掘（Data Mining in a Network Setting）
6 分布式數據和多代理數據的挖掘（Distributed Data Mining and MiningMulti-agent Data）
7生物和環境數據的挖掘（Data Mining for Biological and EnvironmentalProblems）
8 數據挖掘過程中的相關問題處理（Data-Mining-Process Related Problems）
9 數據挖掘中數據安全、數據所涉及到的隱私和數據完整性的維護（Security,Privacy and Data Integrity）
10 非靜態、非平衡及成本敏感數據的挖掘（Dealing with Non-static,Unbalanced and Cost-sensitive Data）
挖掘對象
大規模、不完全、有噪聲、模糊隨機的數據集。可以是任何類型的數據源，包括數據庫數據、數據倉庫、事物數據，以及文本、多媒體數據、空間數據、時序數據、web 數據、數據流、圖或網絡數據等。
- 數據庫數據
- 一種結構化數據，比如關系數據庫、圖數據庫中的數據。
- 數據倉庫（Data Warehouse）
從多個數據源收集的信息存儲庫，存放在一致的模式下，并且通常駐留在單個站點上，是決策支持系統和聯機分析應用數據源的結構化數據環境。數據倉庫通常使用數據立方體（Data Cube）的多維數據結構建模。通過鉆取、上卷、切片、切塊、旋轉等聯機分析處理（Online Analytical Processing, OLAP）操作，允許用戶在不同匯總級別觀察數據。
- 事物數據
通常表示人類一次活動記錄，比如一次購物、一個航班訂票等。一個事物數據包含一個唯一的事物標識號，以及一個組成事物的項列表（購買的商品）。從圖 2 可以看出，事物數據包含嵌套關系，難以放在關系數據庫中，通常存放在表 1 所示的表格式的文件中
常見任務：
是對目標類數據的一般特征或指定特征的總結。對應于用戶指定類的數據通常通過數據庫查詢收集。例如，要研究上一年銷售額增長 10％的軟件產品的特征，可以通過執行 SQL 查詢來收集與此類產品相關的數據。
數據庫可能包含不符合數據一般行為或模型的數據對象，這些數據對象即為異常值。大多數數據挖掘方法將異常值視為噪聲或異常但是在諸如欺詐檢測等應用中，罕見事件可能比常見的更有價值。異常值數據的分析通常被稱為異常值挖掘。
搜索變量之間的關系。例如，一個超市可能會收集顧客購買習慣的資料。運用關聯規則學習，超市可以確定哪些產品經常一起買，并利用這些信息促進銷售，這種學習也被稱為市場購物籃分析。
發現數據的類別與結構。聚類算法基于最大化類內相似性和最小化類間相似性的原則，將對象進行聚類或分組。也就是說，形成對象集群，使得集群內的對象彼此之間具有較高的相似性，但與其他集群中的對象非常不相似。每個集群都可以被視為一類對象，從中可以派生出規則。
分類是查找描述和區分數據類別或概念的模型（或函數）的過程，目的是為了能夠使用模型來預測未知對象的類別。例如，一個電子郵件程序可能試圖將一個電子郵件分類為“合法的”或“垃圾郵件”。
試圖找到能夠以最小誤差對該數據建模的函數。回歸分析是最常用于數字預測的統計方法，還可以根據現有數據預測趨勢。
描述并建模對象行為隨時間變化的規則或趨勢。這種分析具有時間序列數據分析、序列或周期性模式匹配以及基于相似性的數據分析的特征
模型分類
-
監督學習和非監督學習
- 區別：訓練數據中是否有標簽，這是二者最根本的區別。監督學習的數據既有特征又有標簽，而非監督學習的數據中只有特征而沒有標簽。
- 監督學習supervised learning
讓機器自己找到特征和標簽之間的聯系，在以后面對只有特征而沒有標簽的數據時可以自己判別出標簽，監督學習可以分為兩大類：回歸(Regression）、分類（Classification) ，二者之間的區別在于回歸分析針對的是連續數據，而分類針對的是離散數據。
問題模型 預測問題。 線性回歸模型 、時間序列模型 、神經網絡 分類問題 邏輯回歸模型 、svm模型 、決策樹模型、 隨機森林模型 Boosting模型。 - 非監督學習unsupervised learning
挖掘數據之間的內在聯系，將樣本分成若干類。訓練數據只有特征沒有分類標簽，這可能是因為我們不具備先驗的知識，或者打標簽的成本很高。所以我們需要機器對數據進行聚類分析，然后就可以通過聚類的方式從數據中提取一個特殊的結構。
問題模型 聚類問題 K-means聚類模型、 DBSCAN聚類模型、 E_m聚類模型。 降維問題 PCA主要成分分析 - 半監督學習
半監督學習的訓練數據中有一部分是有標簽的，另一部分是沒有標簽的，而沒標簽的數據量遠遠大于有標簽的數據量。隱藏在半監督學習下的基本規律在于數據的分布必然不是完全隨機的，通過一些有標簽數據的局部特征，以及更多沒標簽數據的整體分布，就可以得到可以接受甚至是非常好的分類結果
-
參數和非參數模型
| 參數模型 | 限定了目標函數的形式 | 線性回歸模型、邏輯回歸模型、樸素貝葉斯模型 | 1.提前對目標函數作出假設。現實問題很難應用某一目標函數，特別是復雜問題很難得到擬合效果好的模型。2.復雜度偏低，容易出現欠擬合現象 | 1.可解釋性強沖 2.學習和訓練速度較快 3.數據量小 |
| 非參數模型 | 沒有對目標形式進行限定，通過訓練自由的從訓練數據集中學習任意的函數。 | 1.svm模型 2.決策樹模型3.隨機森林模 型 | 1.計算量大-數據量大2.可解釋性弱-么 | 1.適用于大數據量邏輯復雜的問題。效果好于參數模型，由于不存在錯誤前提假設，在數據量趨于無窮大的時候，可以無限逼近于真實模型。2.存在超參數選擇 |
| 半參數模型 | 固定了隱藏的數目和每一層神經元的個數，屬于參數模型。隱層數目和每一層神經元個數在模型中通常是不固定的。 | 神經網絡模型 |
- 生成和判別
| 生成模型 | 能夠學習數據生成機制，得到聯合分布p （x，y），特征x和y共同出現的概率，然后求條件概率分布， | 數據量需求大，能夠很好的估計概率密度。數據充足的情況下，生成模型的收斂速度較快。能夠處理隱變量。相對于判別模型生產模型準確率以及適用范圍弱 | 樸素貝葉斯模型、混合高斯模型、隱馬爾可夫模型。 |
| 判別模型。 | 學習得到條件概率分布p（y | x），在特征x的調情況下標簽y出現的概率 | 計算量小。準確率和適用范圍大切。較為常用 |
問題與挑戰
- 數據挖掘過程中的相關問題處理
大數據的規模大、來源種類多樣、價值密度低、增長速度快、準確性低等特征，給數據挖掘過程中每個階段造成不同的問題挑戰
（1） 數據采集和入庫：不同類型的數據存儲在一個地方、相同數據在不同的數據源中命名形式不一樣、不同數據源中的數據性質不同等會給數據采集和存儲帶來很大挑戰。（2） 數據清洗：定義和確定錯誤類型，搜索和識別錯誤，更正錯誤，記錄錯誤以及修改數據輸入程序以減少結構化、非結構化和半結構化數據會帶來數據清理方面的挑戰。當數據沒有存在噪音、不完整、不一致等問題時，數據挖掘和分析過程會提供正確的信息。（3） 數據分析與挖掘：數據分析與挖掘是大數據的核心挑戰。如果在采集、存儲、清理、集成、轉換等流程中出現任何問題，會導致容易挖掘到無用的數據。如果想在大數據中獲取有價值的信息，有必要研究適用于所有類型數據的挖掘技術。（4） 數據集成與融合：在大數據挖掘中，不同類型的數據模式集成和融合是最大的挑戰。例如，集成的數據模式通常是在不同數據源中獲取，而不同數據源中的同一對象通常具有不同的名稱表示形式。如何正確將指向同一對象的不同數據融合到一起，是數據集成和融合技術的巨大挑戰。- 數據完整性（Data Integrity）
數據挖掘所使用的數據常常是為其他 用途收集的，原始數據中出現的問題會對下一階段的分析過程產生重大的影響， 因此在數據清洗階段需要檢驗數據完整性。數據對象遺漏一個或多個屬性值的 情況在數據挖掘任務中屢見不鮮，例如有的人拒絕透露年齡和體重，這時信息 收集不全的現象變得十分常見。
指數據的準確性和可靠性，用于描述存 儲的所有數據值均處于客觀真實的狀態。完整性檢驗5 個基本原則：可溯源、清晰、同步、原始或真實復制、準確策略，包括刪除數據對象或屬性、估計遺漏值、在分析時忽略遺漏值、使用默認值、使用屬性平均值、使用同類樣本平均值、預測最可能的值 等。-
傳統數據挖掘技術與網絡動態數據挖掘
傳統數據挖掘技術主要針對靜態數據集、數據倉庫問題定義、數據采集、數據預處理、數據清理/集成、數據選擇/變換/歸約、 數據挖掘、模式評估、解釋和應用
網絡動態數據挖掘需要面對不斷變化的網絡環境及各種動態變化的實時數據之外， 還需要對整個數據挖掘過程、數據集與關聯規則集的更新過程等進行實時分析 和處理。
-
非平衡樣本數據挖掘
在不平衡數據中，人們將擁有較多實例的那一類稱為多數類（有時也稱為 負樣本），將擁有相對較少實例的那一類稱為少數類（有時也稱為正樣本）。現有分類算法（如決策樹和神經網絡等）大多假定每個樣本的誤分類具有同樣的代價而致力于提高分類器的泛化精度，分類的結果偏向于大類別樣本，即大類別樣本的分類精度高于小類別樣本。但對很多現實的應用，如醫療診斷、信用卡欺詐檢測、網絡入侵、故障識別等，不同類別的樣本數相差較大，不同樣本的誤分類代價通常不相等，僅憑全局精度評價分類器的性能優劣是不夠的。此時需要引入代價敏感數據挖掘技術（Cost Sensitive Data Mining, CSDM）
十大經典算法
- C4.5
- KNN（K-Nearest Neighbor）
- K-Means
- CART（Classification and Regression Trees
- SVM（Support Vector Machine Apriori ）
- EM（Expectation Maximization
- Page Rank.
- AdaBoost.
- Naive Bayes
- Apriori
C4.5
C4.5 算法是由 Ross Quinlan 在 ID3 算法的基礎上，開發的用于產生決策樹的算法，通常用于統計分類。C4.5 算法與 ID3 算法一樣使用了信息熵的概念，并和 ID3 一樣通過學習數據來建立決策樹。把哪個屬性作為根節點，是 C4.5 算法研究的重點，它采用信息增益率來選擇屬性。信息增益率使用“分裂信息”值將信息增益規范化，選擇具有最大增益率的屬性作為分裂屬性。信息增益率的計算公式如下所示
1. 決策樹
-
作用
給定一個數據集，其中的每一個元組都能用一組屬性值來描述，每一個元組屬于一個互斥的類別中的某一類。C4.5 、ID3 的目標是通過學習，找到一個從屬性值到類別的映射關系，并且這個映射能用于對新的類別未知的實體進行分類 -
工作原理
類似于流程圖的樹形結構，每一個節點代表對一個特征的測試。樹的分支代表著該特征的一個測試結果。每一個節點代表一個類別。決策樹的核心就是尋找純凈的劃分
-
類別
- 分類樹 ，處理離散數據，也就是數據種類有限的數據，它輸出的是樣本的類別 cart
- 回歸樹 ，對連續型的數值進行預測，也就是數據在某個區間內都有取值的可能，輸出的是一個數值。
-
構造
選擇什么屬性作為節點，三種節點 - 根節點 ：樹的最頂端 - 天氣
- 內部節點 ：樹中間的那些節點 - 溫度”、“濕度”、“刮風
- 葉節點 ：決策結果，停止并得到目標狀態 -樹最底部的節點，葉節點不存在子節點
-
節點選擇指標
- 純度 ：讓目標變量的分歧最小 - 不純度指標 集合 1：6 次都去打籃球；集合 2：4 次去打籃球，2 次不去打籃球；集合 3：3 次去打籃球，3 次不去打籃球。按照純度指標來說，集合 1> 集合 2> 集合 3。因為集合 1 的分歧最小，集合 3 的分歧最大。
- 信息熵 entropy : 信息的不確定度 - 度量信息量 ,信息熵越大，純度越低。當集合中的所有樣本均勻混合時，信息熵最大，純度最低。
- 計算模型 :ID3 算法 C4.5 算法 cart算法
-
優缺點
-
優點 :
1.不需要對樣本進行預先假設，更快地處理復雜樣本。可以處理多維度輸出的分類問題。
2.非參數模型 計算速度快。使用決策樹預測的代價是O(log2m)。m為樣本數。
3.簡單直觀，生成的決策樹很直觀。能夠通過繪制分支清晰的剖析模型的選擇流程，快速發現影響結果的因素，能及時指導業務進行調整修改。
4.可以同時處理分類問題和預測問題 .
5.能夠處理離散型和連續型變量同時存在的場景。 很多算法只是專注于離散值或者連續值。
6.對缺失值不敏感。 基本不需要預處理，不需要提前歸一化和處理缺失值。對于異常點的容錯能力好，健壯性高。
7.可解釋性強 。相比于神經網絡之類的黑盒分類模型，決策樹在邏輯上可以很好解釋。可以交叉驗證的剪枝來選擇模型，從而提高泛化能力。 -
缺點 :
1.弱學習器。有些比較復雜的關系，決策樹很難學習，比如異或。這個就沒有辦法了，一般這種關系可以換神經網絡分類方法來解決。
2.即使通過調優方法進行優化。也容易產生過擬合現象，造成結果誤差大。 可以通過設置節點最少樣本數量和限制決策樹深度來改進。
3.在處理特征關聯性較強的數據時表現不好。
4.受樣本影響大。決策樹會因為樣本發生一點的改動，導致樹結構的劇烈改變。這個可以通過集成學習之類的方法解決。 如果某些特征的樣本比例過大，生成決策樹容易偏向于這些特征。這個可以通過調節樣本權重來改善。
5.尋找最優的決策樹是一個NP難題，我們一般是通過啟發式方法，容易陷入局部最優。可以通過集成學習的方法來改善。
-
-
調優方法
- 剪枝 ,控制數的深度及節點個數等參數，避免過擬合。
給決策樹瘦身，防止“過擬合”，目標是，不需要太多的判斷
- 剪枝 ,控制數的深度及節點個數等參數，避免過擬合。
- 預剪枝Pre-Pruning
在決策樹構造時就進行剪枝。 方法是在構造的過程中對節點進行評估， 如果對某個節點進行劃分， 在驗證集中不能帶來準確性的提升，那么對這個節點進行劃分就沒有意義，這時就會把當前節點作為葉節點，不對其進行劃分 - 后剪枝Post-Pruning
在生成決策樹之后再進行剪枝， 通常會從決策樹的葉節點開始，逐層向上對每個節點進行評估。 如果剪掉這個節點子樹，與保留該節點子樹在分類準確性上差別不大，或者剪掉該節點子樹，能在驗證集中帶來準確性的提升，那么就可以把該節點子樹進行剪枝。方法是：用這個節點子樹的葉子節點來替代該節點，類標記為這個節點子樹中最頻繁的那個類。 CCP 方法：cost-complexity prune，中文叫做代價復雜度 - 要用交叉驗證法，選擇合適的參數。
- 通過模型及集成的方法，基于決策樹形成更加復雜的模型。
2.信息增益（ID3 算法）
ID3 算法計算的是信息增益，信息增益指的就是劃分可以帶來純度的提高，信息熵的下降
-
公式
定義：父親節點的信息熵減去所有子節點的信息熵
D 是父親節點，
Di 是子節點，計算每個子節點的歸一化信息熵，即按照每個子節點在父節點中出現的概率
Gain(D,a) 中的 a 作為 D 節點的屬性選擇 -
缺陷：
ID3 算法傾向于選擇取值比較多的屬性，有些屬性可能對分類任務沒有太大作用，但是他們仍然可能會被選為最優屬性 比如我們會發現 這樣，如果我們把“編號”作為一個屬性（一般情況下不會這么做，這里只是舉個例子），那么“編號”將會被選為最優屬性 -
案例
1.將天氣屬性作為根節點，信息增益計算
根節點的信息熵： 練集中一共有 7 條數據，3 個打籃球，4 個不打籃球，所以根節點的信息熵是
2.三個葉子節點的信息熵，
D1(天氣 = 晴天)={1-,2-,6+}D2(天氣 = 陰天)={3+,7-}D3(天氣 = 小雨)={4+,5-}，+ 代表去打籃球，- 代表不去打籃球
歸一化信息熵 = 3/70.918+2/71.0+2/7*1.0=0.965。
3.天氣作為屬性節點的信息增益為
Gain(D , 天氣)=0.985-0.965=0.020。
4.同理我們可以計算出其他屬性作為根節點的信息增益， 它們分別為 ：
Gain(D , 溫度)=0.128
Gain(D , 濕度)=0.020
Gain(D , 刮風)=0.020
5.溫度作為屬性的信息增益最大。因為 ID3 就是要將信息增益最大的節點作為父節點，這樣可以得到純度高的決策樹，
6.要將上圖中第一個葉節點，也就是 D1={1-,2-,3+,4+}進一步進行分裂，往下劃分，計算其不同屬性（天氣、濕度、刮風）作為節點的信息增益，可以得到：Gain(D , 濕度)=1Gain(D , 天氣)=1Gain(D , 刮風)=0.3115，
7.我們能看到濕度，或者天氣為 D1 的節點都可以得到最大的信息增益，這里我們選取濕度作為節點的屬性劃分。同理，我們可以按照上面的計算步驟得到完整的決策樹，結果如下：
3.信息增益率（C4.5 算法）
- 公式
信息增益率 = 信息增益 / 屬性熵，
屬性熵 SpliIInfoA(D)
-
C4.5 算法對 ID3 算法的改進之處在于：
（1）克服多屬性偏向
C4.5 算法用信息增益率來選擇屬性，克服了 ID3 算法用信息增益選擇屬性時偏向選擇取值多的屬性的不足；當屬性有很多值的時候，相當于被劃分成了許多份，雖然信息增益變大了，但是對于 C4.5 來說，屬性熵也會變大，所以整體的信息增益率并不大
（2） 在樹構造過程中進行悲觀剪枝；
采用悲觀剪枝ID3 構造決策樹的時候，容易產生過擬合的情況。在 C4.5 中，會在決策樹構造之后采用悲觀剪枝（PEP），這樣可以提升決策樹的泛化能力。悲觀剪枝是后剪枝技術中的一種，通過遞歸估算每個內部節點的分類錯誤率，比較剪枝前后這個節點的分類錯誤率來決定是否對其進行剪枝。這種剪枝方法不再需要一個單獨的測試數據集。
（3） 能夠完成對連續屬性的離散化處理；
可以處理連續值 。C4.5 可以處理連續屬性的情況，對連續的屬性進行離散化的處理。比如打籃球存在的“濕度”屬性，不按照“高、中”劃分，而是按照濕度值進行計算，那么濕度取什么值都有可能。該怎么選擇這個閾值呢，C4.5 選擇具有最高信息增益的劃分所對應的閾值。
（4） 能夠對不完整數據進行處理。
基于比例，當數據集不完整的情況，C4.5 也可以進行處理。假如我們得到的是如下的數據，你會發現這個數據中存在兩點問題。
第一個問題是，數據集中存在數值缺失的情況，如何進行屬性選擇？第二個問題是，假設已經做了屬性劃分，但是樣本在這個屬性上有缺失值，該如何對樣本進行劃分？我們不考慮缺失的數值，可以得到溫度 D={2-,3+,4+,5-,6+,7-}。溫度 = 高：D1={2-,3+,4+} ；溫度 = 中：D2={6+,7-}；溫度 = 低：D3={5-} 。針對將屬性選擇為溫度的信息增為：Gain(D′, 溫度)=Ent(D′)-0.792=1.0-0.792=0.208屬性熵 =1.459, 信息增益率 Gain_ratio(D′, 溫度)=0.208/1.459=0.1426。D′的樣本個數為 6，而 D 的樣本個數為 7，所以所占權重比例為 6/7，所以 Gain(D′，溫度) 所占權重比例為 6/7，所以：Gain_ratio(D, 溫度)=6/7*0.1426=0.122。這樣即使在溫度屬性的數值有缺失的情況下，我們依然可以計算信息 -
案例
這里使用打籃球的案例來研究 C4.5 算法的執行流程。給定一些訓練樣本，具有
如下 4 個屬性：Outlook（天氣）、Temperature（溫度）、Humidity（濕度）、Windy（是否刮風），來判斷今天是否適合出去打籃球。圖 12 展示了 C4.5 算法根據訓練樣本生成的決策樹。根節點是 Outlook 屬性，劃分出了三個組合（Sunny、Overcast、Rainy）。
其中，Overcast 劃分中的集合是“純”的，故此子樹就停止生長，表示 Outlook 的屬性值為 Overcast 時，適合出去打籃球。
而 Sunny 和 Rainy 的屬性值劃分樣例集合中包含 Humidity 和 Windy 的不同屬性值，因此它們不“純”，需要繼續使用子樹來表示子集，直到子集為“純”的（即子集中的所有實例都屬于同一個類別），樹才停止生長。根據 Yes，得出只有符合以上屬性值要求（比如 Outlook 為 Sunny，Humidity<=75；或者 Outlook為 Rainy，Windy 為 False），才能適合出去打籃球。
項目鏈接
- List item
CART（Classification and Regression Trees）
1.定義
-
簡介
CART 算法，英文全稱叫做 Classification And Regression Tree，中文叫做分類回歸樹。由 ID3，C4.5 演化而來，是許多基于樹的 bagging、boosting 模型的基礎。CART 是在給定輸入隨機變量 x 條件下輸出隨機變量 y 的條件概率分布。 -
特征
- 只支持二叉樹 ，ID3 和 C4.5 算法可以生成二叉樹或多叉
- 既可以作分類樹，又可以作回歸樹。夠處理連續值。python，sklearn默認決策樹模型
- 用Gini系數也稱Gini不純度代替信息熵。選擇特征：使Gini不純度變小的特征作為節點。
-
ID3、C4.5 和 CART 的一個比較總結
| ID3 | 分類 | 多叉樹 | 信息增益 | 不支持 | 不支持 | 不支持 |
| C4.5 | 分類 | 多叉樹 | 信息增益比 | 支持 | 支持 | 支持 |
| CART | 分類、回歸 | 二叉樹 | 基尼系數、均方差 | 支持 | 支持 | 支持 |
- CART 算法優缺點：
- CART 算法的缺點在于：
（1） 在做特征選擇的時候都是選擇最優的一個特征來做分類決策，但是大多數，分類決策不應該是由某一個特征決定的，而是應該由一組特征決定的。
（2） 如果樣本發生一點點的改動，就會導致樹結構的劇烈改變。 - CART 算法的優點
可以對復雜和非線性的數據建模，缺點是結果不易理解。
- CART 算法的缺點在于：
2.基尼系數
-
簡介
- 基尼系數本身反應了樣本的不確定度。
當基尼系數越小的時候，說明樣本之間的差異性小，不確定程度低。 - 用來衡量一個國家收入差距的常用指標。
當基尼系數大于 0.4 的時候，說明財富差異懸殊。基尼系數在 0.2-0.4 之間說明分配合理，財富差距不大。
- 基尼系數本身反應了樣本的不確定度。
-
公式
假設 t 為節點，那么該節點的 GINI 系數的計算公式為：
p(Ck|t) :節點 t 屬于類別 Ck 的概率，節點 t 的基尼系數為 1 減去各類別 Ck 概率平方和。 -
計算基尼系數
兩個集合的基尼系數分別為多少：集合 D1：6 個都去打籃球；集合 D2：3 個去打籃球，3 個不去打籃球。
針對集合D1：所有人都去打籃球，所以 p(Ck|t)=1，因此 GINI(t)=1-1=0。
集合 D2：有一半人去打籃球，而另一半不去打籃球，所以，p(C1|t)=0.5，p(C2|t)=0.5，GINI(t)=1-（0.5* 0.5+0.5* 0.5）=0.5。
通過兩個基尼系數你可以看出，集合 1 的基尼系數最小，也證明樣本最穩定，而集合 2 的樣本不穩定性更大。 -
基于基尼系數 建立CART 算法
基尼系數對特征屬性進行二元分裂，假設屬性 A 將節點 D 劃分成了 D1 和 D2，如下圖所示：
節點 D 的基尼系數等于子節點 D1 和 D2 的歸一化基尼系數之和，用公式表示為：
節點 D 被屬性 A 劃分后的基尼系數越大，樣本集合的不確定性越大，也就是不純度越高。
核心解讀
- CART 算法由以下兩步組成：
（1） 樹的生成：基于訓練數據集生成決策樹，生成的決策樹要盡量大；
（2） 樹的剪枝：用驗證數據集對已生成的樹進行剪枝并選擇最優子樹這時損失函數最小作為剪枝的標準。
-
CART 分類樹的工作流程
分類的過程本身是一個不確定度降低的過程。決策樹的生成就是基于訓練數據集，通過遞歸地構建二叉決策樹的過程，選擇基尼系數最小的屬性作為屬性的劃分。樹內部結點特征取值為“是”和“否”，左分支取值為“是”，右分支取值為“否”。這樣的判定樹等價于遞歸地二分每一個特征，將輸入空間劃分為有限個單元，并在這些單元上預測概率分布，也就是在輸入給定的條件下輸出條件概率分布。 -
CART分類樹算法
- 算法輸入訓練集D，基尼系數的閾值，樣本個數閾值。
- 算法從根節點開始，用訓練集遞歸建立CART分類樹。
(1)對于當前節點的數據集為D，如果樣本個數小于閾值或沒有特征，則返回決策子樹，當前節點停止遞歸。
(2)計算樣本集D的基尼系數，如果基尼系數小于閾值，則返回決策樹子樹，當前節點停止遞歸。
(3)計算當前節點現有的各個特征的各個特征值對數據集D的基尼系數。
(4)在計算出來的各個特征的各個特征值對數據集D的基尼系數中，選擇基尼系數最小的特征A和對應的特征值a。根據這個最優特征和最優特征值，把數據集劃分成兩部分D1和D2，同時建立當前節點的左右節點，做節點的數據集D為D1，右節點的數據集D為D2。
(5)對左右的子節點遞歸的調用1-4步，生成決策樹。
-
決策樹的剪枝
- 定義：
用驗證數據集對生成的樹進行剪枝并選擇最優子樹，損失函數最小作為剪枝的標準重復上面的過程，得到了剪枝后的子樹集合后，我們需要用驗證集對所有子樹的誤差計算一遍。可以通過計算每個子樹的基尼指數或者平方誤差，取誤差最小的那個樹，得到我們想要的結果。 - 剪枝方法
主要采用的是 CCP 方法，它是一種后剪枝的方法，英文全稱叫做 cost-complexity prune，中文叫做代價復雜度。這種剪枝方式用到一個指標叫做節點的表面誤差率增益值，以此作為剪枝前后誤差的定義。尋找的就是最小值對應的節點，把它剪掉 - 表面誤差率增益值
等于節點 t 的子樹被剪枝后的誤差變化除以剪掉的葉子數量。用公式表示則是：
其中 Tt 代表以 t 為根節點的子樹，C(Tt) 表示節點 t 的子樹沒被裁剪時子樹 Tt 的誤差，C(t) 表示節點 t 的子樹被剪枝后節點 t 的誤差，|Tt|代子樹 Tt 的葉子數，剪枝后，T 的葉子數減少了|Tt|-1。
- 定義：
-
CART 回歸的流程包括
構建回歸樹用平方誤差最小化準則，對分類樹用基尼指數最小化準則，進行特征選擇，生成二叉樹：
（1） 遍歷每個特征，對于特征，遍歷每個取值 s，用切分點 s 將數據集分為兩份，計算切分后的誤差；
（2） 求出誤差最小的特征及其對應的切分點，此特征即被選中作為分裂結點，切分點形成左右分支；
（3） 遞歸地重復以上步驟。 -
回歸樹中節點劃分的標準
CART 回歸樹中，用樣本的離散程度來評價“不純度”。分別對應著兩種目標函數最優化的標準，即用最小絕對偏差（LAD），或者使用最小二乘偏差（LSD）。這通常使用最小二乘偏差的情況更常見一些。- 最小絕對偏差（LAD）
差值的絕對值為樣本值減去樣本均值的絕對值：
- 最小二乘偏差（LSD）
方差為每個樣本值減去樣本均值的平方和除以樣本個數：
- 最小絕對偏差（LAD）
項目鏈接
- List item
KNN（K-Nearest Neighbor）
1.定義
-
理解
“近朱者赤，近墨者黑”。最鄰近規則分類算法在確定分類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。 -
KNN 的核心思想是
如果一個樣本在特征空間中的 K 個最相鄰的樣本中的大多數屬于某一個類別，則該樣本也屬于這個類別，并具有這個類別上樣本的特性。KNN 算法中，所選擇的鄰居都是已經正確分
類的對象。通過找出一個樣本的 K 個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。KNN 方法在做類別決策時，只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。而不是靠判別類域的方法來確定所屬類別的，因此對于類域的交叉或重迭較多的待分樣本集來說，KNN方法較其他方法更為適合。
-
過程
（1） 計算測試數據與各個訓練數據之間的距離；
（2） 按照距離的遞增關系進行排序；
（3） 選取距離最小的 K 個點；
（4） 確定前 K 個點所在類別的出現頻率；
（5） 返回前 K 個點中出現頻率最高的類別作為測試數據的預測分類。 -
KD 樹
KNN 的計算過程是大量計算樣本點之間的距離。為了減少計算距離次數，提升 KNN 的搜索效率，人們提出了 KD 樹（K-Dimensional 的縮寫）。
KD 樹是對數據點在 K 維空間中劃分的一種數據結構。在 KD 樹的構造中，每個節點都是 k 維數值點的二叉樹。既然是二叉樹，就可以采用二叉樹的增刪改查操作，這樣就大大提升了搜索效率。
不需要對 KD 樹的數學原理了解太多，只需要知道它是一個二叉樹的數據結構，方便存儲 K 維空間的數據就可以了。而且在 sklearn 中，我們直接可以調用 KD 樹，很方便。 -
優缺點
優點：簡單、容易理解，通過 K 值的增大可具備噪音數據的魯棒性。
缺點：需要大量的空間去儲存已知的實例，算法復雜度高。 -
案例1.分類：
假設，我們想對電影的類型進行分類，統計了電影中打斗次數、接吻次數，當然還有其他的指標也可以被統計到，如下表所示。《戰狼》《紅海行動》《碟中諜 6》是動作片，《前任 3》《春嬌救志明》《泰坦尼克號》是愛情片，但是有沒有一種方法讓機器也可以掌握這個分類的規則，當有一部新電影的時候，也可以對它的類型自動分類呢？
我們可以把打斗次數看成 X 軸，接吻次數看成 Y 軸，然后在二維的坐標軸上，對這幾部電影進行標記，如下圖所示。對于未知的電影 A，坐標為 (x,y)，我們需要看下離電影 A 最近的都有哪些電影，這些電影中的大多數屬于哪個分類，那么電影 A 就屬于哪個分類。實際操作中，我們還需要確定一個 K 值，也就是我們要觀察離電影 A 最近的電影有多少個。 -
案例2.回歸
對于一個新電影 X，我們要預測它的某個屬性值，比如打斗次數，具體特征屬性和數值如下所示。
此時，我們會先計算待測點（新電影 X）到已知點的距離，選擇距離最近的 K 個點。假設 K=3，此時最近的 3 個點（電影）分別是《戰狼》，《紅海行動》和《碟中諜 6》，那么它的打斗次數就是這 3 個點的該屬性值的平均值，即(100+95+105)/3=100 次。
2.核心解讀
-
K 等于不同值時的算法分類結果？
- K 值比較小
就相當于未分類物體與它的鄰居非常接近才行。這樣產生的一個問題就是，如果鄰居點是個噪聲點，那么未分類物體的分類也會產生誤差，這樣 KNN 分類就會產生過擬合。 - K 值比較大
相當于距離過遠的點也會對未知物體的分類產生影響，雖然這種情況的好處是魯棒性強，但是不足也很明顯，會產生欠擬合情況，也就是沒有把未分類物體真正分類出來。
- K 值比較小
-
K值選擇
K 值應該是個實踐出來的結果，并不是我們事先而定的。在工程上，我們一般采用交叉驗證的方式選取 K 值，交叉驗證的思路：
把樣本集中的大部分樣本作為訓練集，剩余的小部分樣本用于預測，來驗證分類模型的準確性。所以在 KNN 算法中，我們一般會把 K 值選取在較小的范圍內，同時在驗證集上準確率最高的那一個最終確定作為 K 值。 -
關于距離的度量
兩個樣本點之間的距離代表了這兩個樣本之間的相似度。距離越大，差異性越大；距離越小，相似度越大。關于距離的計算方式有下面五種方式： - 歐氏距離；
- 曼哈頓距離；
- 閔可夫斯基距離；
- 切比雪夫距離；
- 余弦距離。
項目鏈接
- List item
K-Means.
1. 定義
-
簡介
K-Means 是一種非監督學習，解決的是聚類問題。K 代表的是 K 類，Means 代表的是中心，可以理解算法的本質是確定 K 類的中心點，當你找到了這些中心點，也就完成了聚類。 -
算法的思想
對于給定的樣本集，按照樣本之間的距離大小，將樣本集劃分為 K 個簇，讓簇內的點盡量緊密地連在一起，而讓簇間的距離盡量的大。 -
- 數據表達式表示
最小值采用的是啟發式的迭代方法，假設簇劃分為（C1,C2,…Ck），則目標是最小化平方誤差 E：
其中μi是簇 Ci的均值向量，有時也稱為質心，表達式為：
- 數據表達式表示
-
圖可以形象描述上式
圖（a）表達了初始的數據集，假設 k=2。
在圖（b）中，我們隨機選擇了兩個 k 類所對應的類別質心，即圖中的紅色質心和藍色質心，然后分別求樣本中所有點到這兩個質心的距離，并標記每個樣本的類別為和該樣本距離最小的質心的類別。
如圖 c 所示，經過計算樣本和紅色質心和藍色質心的距離，我們得到了所有樣本點的第一輪迭代后的類別。
如圖（d）所示此時我們對當前標記為紅色和藍色的點分別求其新的質心，新的紅色質心和藍色質心的位置已經發生了變動。
圖（e）和圖（f）重復了圖（c）和圖（d）的過程，即將所有點的類別標記為距離最近的質心的類別并求新的質心。最終我們得到的兩個類別如圖（f）。
-
優缺點
優點有：比較簡單，實現也很容易，收斂速度快；算法的可解釋度比較強。
缺點有：K 值的選取不好把握；采用迭代方法，得到的結果只是局部最優；對噪音和異常點比較敏感。
2.核心解讀
假設我有 20 支亞洲足球隊，想要將它們按照成績劃分成 3 個等級，可以怎樣劃分？
-
如何確定 K 類的中心點？
-
選取 K 個點作為初始的類中心點，這些點一般都是從數據集中隨機抽取的；
一開始我們是可以靠我們的經驗隨機指派，一流的亞洲球隊伊朗。二流的亞洲球隊中國。三流的亞洲球隊越南。三個等級的典型代表，也就是我們每個類的中心點。 -
將每個點分配到最近的類中心點，這樣就形成了 K 個類，然后重新計算每個類的中心點；
計算每個隊伍分別到中國、日本、韓國的距離，然后根據距離遠近來劃 -
糾正中心點：重復第二步，直到類不發生變化，或者你也可以設置最大迭代次數，這樣即使類中心點發生變化，但是只要達到最大迭代次數就會結束。中心點在整個迭代過程中，并不是唯一的，只是你需要一個初始值，一般算法會隨機設置初始的中心點。
再重新計算這三個類的中心點，如何計算呢？最簡單的方式就是取平均值，然后根據新的中心點按照距離遠近重新分配球隊的分類，再根據球隊的分類更新中心點的位置。 -
如何將其他點劃分到 K 類中？
實際上是關于距離的定義，我們知道距離有多種定義的方式，在 K-Means 和 KNN 中，我們都可以采用歐氏距離、曼哈頓距離、切比雪夫距離、余弦距離等。對于點的劃分，就看它離哪個類的中心點的距離最近，就屬于哪一類。 -
如何區分 K-Means 與 KNN？
- 兩個算法解決數據挖掘的兩類問題。K-Means 是聚類算法，KNN 是分類算法。
- 這兩個算法分別是兩種不同的學習方式。K-Means 是非監督學習，也就是不需要事先給出分類標簽，而 KNN 是有監督學習，需要我們給出訓練數據的分類標識。
- K 值的含義不同。K-Means 中的 K 值代表 K 類。KNN 中的 K 值代表 K 個最接近的鄰居。
項目鏈接
- List item
Naive Bayes 樸素貝葉斯法
1.相關定義
-
簡介
基于貝葉斯定理與特征條件獨立假設的分類方法，和決策樹模型是使用最為廣泛的兩種分類模型。相比決策樹模型，樸
素貝葉斯模型所需估計的參數很少，對缺失數據不太敏感，算法也比較簡單。具有穩定的分類效率。但是在實際應用中，屬性之間相互獨立的假設往往是不成立的，給樸素貝葉斯模型的分類準確度帶來一定影響。
- 貝葉斯分類
在統計資料的基礎上，依據條件概率公式，計算當前特征的樣本屬于某個分類的概率，選擇最大的概率分類 - 預測建模算法
強制假設每個輸入變量是獨立的，統計的是屬性的條件概率 - 樸素
貝葉斯之所以樸素是因為它假設屬性是相互獨立的，因此對實際情況有所約束，雖然不太現實，但對于絕大多數問題有很好的解決。如果屬性之間存在關聯，分類準確率會降低。 - 條件概率
訓練樸素貝葉斯模型，我們需要先給出訓練數據，以及這些數據對應的分類。那么類別概率和條件概率。他們都可以從給出的訓練數據中計算出來。一旦計算出來，概率模型就可以使用貝葉斯原理對新數據進行預測。
- 貝葉斯分類
-
數學原理
貝葉斯統計 -
組成
由兩種類型的概率組成：1. 每個類別的概率P(Cj)；2. 每個屬性的條件概率P(Ai|Cj)。
- 類別概率
將數據集轉換為頻率表，然后創建概率表，比如 P(sunny) =0.36 - 條件概率
用樸素貝葉斯計算后驗概率，后驗概率大的為預測分類。如果天氣是 sunny 就出去玩，這樣說是 否 正 確 ？ 可 以 根 據 后 驗 概 率 來 確 定 以 上 說 法 是 否 正 確 ，即P(Yes|Sunny)=P(Sunny|Yes)*P(Yes)/P(Sunny)=0.60>0.5，所以天氣好就可以出去玩
- 類別概率
-
適用環境
樸素貝葉斯分類常用于文本分類，尤其是對于英文等語言來說，分類效果很好。它常用于垃圾文本過濾、情感預測、推薦系統等 -
優缺點
- 優點包括：
- 算法的邏輯性十分簡單，當數據呈現不同的特點時，樸素貝葉斯的分類性能不會有太大的差異，算法的魯棒性比較好。
- 當數據集屬性之間的關系相對比較獨立時，樸素貝葉斯分類算法會有較好的效果。
- 缺點包括：
- 屬性獨立性的條件同時也是樸素貝葉斯分類器的不足之處。數據集屬性的獨立性在很多情況下是很難滿足的，因為數據集的屬性之間往往都存在著相互關聯，如果在分類過程中出現這種問題，會導致分類的效果大大降低
- 優點包括：
工作原理
根據以往的經驗判斷性別就是分類過程
-
離散數據
數據：身高“高”、體重“中”，鞋碼“中”，請問這個人是男還是女？- 轉化為數學問
用 A1, A2, A3 分別為身高 = 高、體重 = 中、鞋碼 = 中。一共有兩個類別，假設用 C 代表類別，那么 C1,C2 分別是：男、女，在未知的情況下我們用 Cj 表示。 - 條件概率問題
想求在 A1、A2、A3 屬性下，Cj 的概率，用條件概率表示就是 P(Cj|A1A2A3)。 - 貝葉斯公式應用
P(A1A2A3) 都是固定的，我們想要尋找使得 P(Cj|A1A2A3) 的最大值，就等價于求 P(A1A2A3|Cj)P(Cj) 最大值。 - 繼續簡化
假定 Ai 之間是相互獨立的，P(A1A2A3|Cj)=P(A1|Cj)P(A2|Cj)P(A3|Cj)，需要從數據集 Ai 和 Cj 中計算出 P(Ai|Cj) 的概率：P(A1|C1)=1/2, P(A2|C1)=1/2, P(A3|C1)=1/4，P(A1|C2)=0, P(A2|C2)=1/2, P(A3|C2)=1/2 - 得出結論
帶入到上面的公式得出 P(A1A2A3|Cj)，最后找到使得 P(A1A2A3|Cj) 最大的類別 Cj。所以 P(A1A2A3|C1)=1/16, P(A1A2A3|C2)=0
- 轉化為數學問
-
連續數據
數據，身高 180、體重 120，鞋碼 41，請問該人是男是女呢？連續變量，不能采用離散變量的方法計算概率。樣本太少，所以也無法分成區間計算
-數據分布
假設男性和女性的身高、體重、鞋碼都是正態分布，男性的身高是均值 179.5、標準差為 3.697 的正態分布
- 分別計算概率
通過樣本計算出均值和方差，也就是得到正態分布的密度函數，計算得：
男性的身高為 180 的概率為 0.1069。
男性體重為 120 的概率為 0.000382324
男性鞋碼為 41 號的概率為 0.120304111。
- 應用貝葉斯計算總概率
有了密度函數，就可以把值代入，算出某一點的密度函數的值，男性的可能： P(A1A2A3|C1)=P(A1|C1)P(A2|C1)P(A3|C1)=0.10690.0003823240.120304111=4.9169e-6 女的可能性：
P(A1A2A3|C2)=P(A1|C2)P(A2|C2)P(A3|C2)=0.000001474890.0153541440.120306074=2.7244e
- 結論
很明顯這組數據分類為男的概率大于分類為女的概率
SVM（Support Vector Machine）
1.基本認知
-
介紹
支持向量機（Support Vector Machine）是一種監督式學習的方法，它廣泛的應用于統計分類以及回歸分析中。SVM將向量映射到一個更高維的空間里，在這個空間里建立有一個最大間隔超平面。在分開數據的超平面的兩邊建有兩個互相平行的超平面，分隔超平面使兩個平行超平面的距離最大化。 -
基本思想是
在分類問題中，很多時候有多個解，如下圖左邊所示，找到集合邊緣上的若干數據（稱為支持向量），用這些點在理想的線性可分的情況下其決策平面會有多個。而 SVM 的基本模型是在特征空間上找到找到一個超平面（稱為決策面）使得訓練集上正負樣本間隔最大，=這個超平面就是我們的 SVM 分類器。
SVM 算法計算出來的分界會保留對類別最大的間距，即有足夠的余量，如圖 14 右邊所示。能將不同的樣本劃分開，同時使得樣本集中的點到這個分類超平面的最小距離（即分類間隔）最大化，“最大間隔“決策面就是 SVM 要找的最優解，使得支持向量到該平面的距離最大
- 支持向量
離分類超平面最近的樣本點，實際上如果確定了支持向量也就確定了這個超平面。所以支持向量決定了分類間隔到底是多少，而在最大間隔以外的樣本點，其實對分類都沒有意義。 - 超平面
如果在一維空間里就表示一個點，在二維空間里表示一條直線，在三維空間中代表一個平面，當然空間維數還可以更多，這樣我們給這個線性函數起個名稱叫做“超平面”- 案例
桌子上我放了紅色和藍色兩種球，請你用一根棍子將這兩種顏色的球分開。 你可以很快想到解決方案，在紅色和藍色球之間畫條直線就好了，如下圖所示：
練習 2：這次難度升級，桌子上依然放著紅色、藍色兩種球，但是它們的擺放不規律，如下圖所示。
如何用一根棍子把這兩種顏色分開呢？你可能想了想，認為一根棍子是分不開的。除非把棍子彎曲，像下面這樣：所以這里直線變成了曲線。如果在同一個平面上來看，紅藍兩種顏色的球是很難分開的。那么有沒有一種方式，可以讓它們自然地分開呢？這里你可能會靈機一動，猛拍一下桌子，這些小球瞬間騰空而起，如下圖所示。
在騰起的那一剎那，出現了一個水平切面，恰好把紅、藍兩種顏色的球分開。在這里，二維平面變成了三維空間。原來的曲線變成了一個平面。這個平面，我們就叫做超平面。
- 案例
- 分類間隔
點到超平面的距離公式這里我們可以用線性函數來表示
在這個公式里，w、x 是 n 維空間里的向量，其中 x 是函數變量；w 是法向量。法向量這里指的是垂直于平面的直線所表示的向量，它決定了超平面的方向。實際中求超平面公式中的 w* 和 b* 進行求解，需要涉及軟間隔、核函數 - 決策面
其實我們可以有多種直線的劃分，比如下圖所示的直線 A、直線 B 和直線 C，分類環境不是在二維平面中的，而是在多維空間中，這樣直線 C 就變成了決策面 C - 最優決策面
在保證決策面不變，且分類不產生錯誤的情況下，我們可以移動決策面 C，直到產生兩個極限的位置：如圖中的決策面 A 和決策面 B。極限的位置是指，如果越過了這個位置，就會產生分類錯誤。這樣的話，兩個極限位置 A 和 B 之間的分界線 C 就是最優決策面。
- 分類間隔margin
極限位置到最優決策面 C 之間的距離，就是“分類間隔”。某類樣本集到超平面的距離是這個樣本集合內的樣本到超平面的最短距離。 - 分類間隔的大小
我們用 di 代表點 xi 到超平面 wxi+b=0 的歐氏距離。因此我們要求 di 的最小值，用它來代表這個樣本到超平面的最短距離。di 可以用公式計算得出，其中||w||為超平面的范數，di 的公式可以用解析幾何知識進行推導，這里不做解釋
- 最大間隔max margin
如果我們轉動這個最優決策面，你會發現可能存在多個最優決策面，它們都能把數據集正確分開，這些最優決策面的分類間隔可能是不同的，而那個擁有“最大間隔”（max margin）的決策面就是 SVM 要找的最優解。支持向量就是離分類超平面最近的樣本點,決定了分類間隔到底是多少, - 最大間隔的優化模型
目標就是找出所有分類間隔中最大的那個值對應的超平面。在數學上，這是一個凸優化問題（凸優化就是關于求凸集中的凸函數最小化的問題，這里不具體展開）。通過凸優化問題，最后可以求出最優的 w 和 b，也就是我們想要找的最優超平面。中間求解的過程會用到拉格朗日乘子，和 KKT（Karush-Kuhn-Tucker）條件。數學公式比較多，這里不進行展開。
- 支持向量
-
分類器類別
- 完全線性可分情
硬間隔指的就是完全分類準確，不能存在分類錯誤的情況線性可分是個理想。完全線性可分情況下的線性分類器，也就是線性可分的情況，是最原始的 SVM，它最核心的思想就是找到最大的分類間隔； - 大部分線性可分 軟間隔
就是允許一定量的樣本分類錯誤，實際數據會存在噪音 - 線性不可分 非線性支持向量機
在解決線性不可分問題時，它可以通過引入核函數，巧妙地解決了在高維空間中的內積運算，從而很好地解決了非線性分類問題。如下圖所示，通過核函數的引入，將線性不可分的數據映射到一個高維的特征空間內，使得數據在特征空間內是可分的。
核函數：線性核、多項式核、高斯核、拉普拉斯核、sigmoid 核，或者是這些核函數的組合
- 完全線性可分情
-
SVM尋找最大間隔的意義
支持向量機之所以堅持尋找最大邊緣超平面，是因為它具有最好的泛化能力。它不僅使訓練數據具有最佳的分類性，而且為測試數據的正確分類留下了很大的空間。 -
優缺點
- 優點在于：
- 有嚴格的數學理論支持，可解釋性強，不依靠統計方法，從而簡化了通常的分類和回歸問題；
- 能找出對任務至關重要的關鍵樣本；
- 采用核技巧之后，可以處理非線性分類/回歸任務。
- 缺點包括：
- 訓練時間長；
- 當支持向量的數量較大時，預測計算復雜度較高。因此支持向量機目前只適合小批量樣本的任務，無法適應百萬甚至上億樣本的任務。
- 優點在于：
2.項目
EM（Expectation Maximization
1.基本認知
- 簡介
EM 的英文是 Expectation Maximization，所以 EM 算法也叫最大期望算法。EM 算法直接的應用就是求參數估計，最初是為了解決數據缺失情況下的參數估計問題。EM 算法是最常見的隱變量估計方法，在機器學習中有極為廣泛的用途，例如常被用來學習高斯混合模型的參數、隱式馬爾科夫算法、LDA主題模型的變分推斷等。 - EM 算法的工作原理
EM 算法是一種求解最大似然估計的方法，通過迭代優化策略，來找出樣本的模型參數。三個主要的步驟：初始化參數、觀察預期、重新估計。1.根據己經給出的觀測數據，估計出模型參數的值；2.E 步：通過舊的參數來計算隱藏變量（缺失數據的值）；3.M 步：通過得到的隱藏變量的結果來重新估計參數。反復迭代，直到收斂（參數不再發生變化），得到我們想要的結果，迭代結束。
假設你炒了一份菜，想要把它平均分到兩個碟子里，該怎么分？1.先給每個碟子初始化一些菜量，碟子 A 和碟子 B 中菜的份量就是想要求得的模型參數。2.觀察份量的差距，兩步完成期望步驟（Expectation）。3.如果結果存在偏差就需要重新估計參數，調整 A 和 B 的參數，這個就是最大化步驟（Maximization）。 - 最大似然”
Maximum Likelihood,最大可能性，相同年齡下男性的平均身高比女性的高一些，有一男一女，財產男同學高的可能性會很大。 - 最大似然估計
是一種通過已知結果，估計參數的方法。指的就是一件事情已經發生了，然后反推更有可能是什么因素造成的。還是用一男一女比較身高為例，假設有一個人比另一個人高，反推他可能是男性。 - EM 聚類的工作原理
把潛在類別當做隱藏變量，樣本看做觀察值，就可以把聚類問題轉化為參數估計問題。 - EM 算法是一個框架
EM 算法相當于一個框架，你可以采用不同的模型來進行聚類，常用的 EM 聚類有 GMM 高斯混合模型和 HMM 隱馬爾科夫模型。GMM（高斯混合模型）聚類比如下面這兩個圖，可以采用 GMM 來進行聚類
GMM 是通過概率密度來進行聚類，聚成的類符合高斯分布（正態分布）。而 HMM 用到了馬爾可夫過程，在這個過程中，我們通過狀態轉移矩陣來計算狀態轉移的概率。HMM 在自然語言處理和語音識別領域中有廣泛的應用。 - 優缺點
- 優點：
- 相比于 K-Means 算法，EM 聚類更加靈活。K-Means 是通過距離來區分樣本之間的差別的，且每個樣本在計算的時候只能屬于一個分類，稱之為是硬聚類算法。而 EM 聚類在求解的過程中，實際上每個樣本都有一定的概率和每個聚類相關，叫做軟聚類算法。軟的輸出概率，硬的要給出答
- 缺點
- 傳統 EM 算法對初始值敏感，聚類結果隨不同的初始值而波動較大。總的來說，EM 算法收斂的優劣很大程度上取決于其初始參數。
- 優點：
2.案例：EM 算法的基本思想
假設我們有 A 和 B 兩枚硬幣，實際情況是我不知道每次投擲的硬幣是 A 還是 B，那么如何求得硬幣 A 和硬幣 B 出現正面的概率呢？我們做了 5 組實驗，每組實驗投擲 10 次，然后統計出現正面的次數，實驗結果如下：
求得硬幣 A 和 B 出現正面次數的概率：
我們假設硬幣 A 和 B 的正面概率（隨機指定）是θA=0.5 和θB=0.9。
假設實驗 1 投擲的是硬幣 A，那么正面次數為 5 的概率為：
假設實驗 1 是投擲的硬幣 B ，那么正面次數為 5 的概率為：
實驗 1 更有可能投擲的是硬幣 A。對實驗 2~5 重復上面的計算過程，可以推理出來硬幣順序應該是{A，A，B，B，A}。
Page Rank.
1.介紹
-
簡介
PageRank 這個概念引自論文影響力因子，一篇論文的被引述的頻度——即被別人引述的次數越多，一般判斷這篇論文的權威性就越高。PageRank 算法是 Google 排名運算法則（排名公式）的一個非常重要的組成部分，目的就是要找到優質的網頁，不僅為用戶提供想要的內容，而且還會從眾多網頁中篩選出權重高的呈現給用戶。做法：每個到頁面的鏈接都是對該頁面的一次投票，被鏈接的越多，就意味著被其他網站投票越多。
-
簡化模型
出鏈指的是鏈接出去的鏈接。入鏈指的是鏈接進來的鏈接。比如圖中 A 有 2 個入鏈，3 個出鏈。
一個網頁的影響力 = 所有入鏈集合的頁面的加權影響力之和，
u 為待評估的頁面，Bu? 為頁面 u 的入鏈集合。針對入鏈集合中的任意頁面 v，它能給 u 帶來的影響力是其自身的影響力 PR(v) 除以 v 頁面的出鏈數量，即頁面 v 把影響力 PR(v) 平均分配給了它的出鏈，這樣統計所有能給 u 帶來鏈接的頁面 v，得到的總和就是網頁 u 的影響力，即為 PR(u)。出鏈會給被鏈接的頁面賦予影響力，當我們統計了一個網頁鏈出去的數量，也就是統計了這個網頁的跳轉概率。
一共有 4 個網頁 A、B、C、D。它們之間的鏈接信息如圖所示：
A 有三個出鏈分別鏈接到了 B、C、D 上，跳轉概率均為 1/3。B 有兩個出鏈，跳轉概率為 1/2。A、B、C、D 這四個網頁的轉移矩陣 M：
假設 A、B、C、D 四個頁面的初始影響力都是相同：
第一次轉移之后，各頁面的影響力 w1? 變為:
再用轉移矩陣乘以 w1? 得到 w2? 結果，直到第 n 次迭代后 wn? 影響力不再發生變化，可以收斂到 (0.3333，0.2222，0.2222，0.2222），也就是對應著 A、B、C、D 四個頁面最終平衡狀態下的影響力 -
兩個問題：
- 等級泄露（Rank Leak）：如果一個網頁沒有出鏈，就像是一個黑洞一樣，吸收了其他網頁的影響力而不釋放，最終會導致其他網頁的 PR 值為 0。
- 等級沉沒（Rank Sink）：如果一個網頁只有出鏈，沒有入鏈（如下圖所示），計算的過程迭代下來，會導致這個網頁的 PR 值為 0（也就是不存在公式中的 V）。針對等級泄露和等級沉沒的情況，我們需要靈活處理。
-
隨機瀏覽模型
為了解決簡化模型中存在的等級泄露和等級沉沒的問題,提出了 PageRank 的隨機瀏覽模型。
他假設了這樣一個場景：用戶并不都是按照跳轉鏈接的方式來上網，還有一種可能是不論當前處于哪個頁面，都有概率訪問到其他任意的頁面，比如說用戶就是要直接輸入網址訪問其他頁面，雖然這個概率比較小.所以他定義了阻尼因子 d，這個因子代表了用戶按照跳轉鏈接來上網的概率，通常可以取一個固定值 0.85，而 1-d=0.15 則代表了用戶不是通過跳轉鏈接的方式來訪問網頁的，比如直接輸入網址。
其中 N 為網頁總數，這樣我們又可以重新迭代網頁的權重計算了，因為加入了阻尼因子 d，一定程度上解決了等級泄露和等級沉沒的問題。
Google 不斷地重復計算每個頁面的 PageRank，如果給 每個頁面一個隨機 PageRank 值(非 0)，那么經過不斷地重復計算，這些頁面 的 PR 值會趨向于穩定，也就是收斂的狀態 -
應用
只要是有網絡的地方，就存在出鏈和入鏈，就會有 PR 權重的計算，也就可以運用我們今天講的 PageRank 算法。- 社交網絡領域
- 微博粉絲數并不一定等于他的實際影響力。如果按照 PageRank 算法，還需要看這些粉絲的質量如何。如果有很多明星或者大 V 關注，那么這個人的影響力一定很高。如果粉絲是通過購買僵尸粉得來的，那么即使粉絲數再多，影響力也不高
- 工作場景中，比如說脈脈這個社交軟件，它計算的就是個人在職場的影響力。如果你的工作關系是李開復、江南春這樣的名人，那么你的職場影響力一定會很高。反之，如果你是個學生，在職場上被鏈入的關系比較少的話，職場影響力就會比較低。
- 社交網絡領域
Apriori
1.基本認知
-
簡介
Apriori 算法是一種挖掘關聯規則的頻繁項集算法，其核心思想是通過候選集生成和情節的向下封閉檢測兩個階段來挖掘頻繁項集。已被 廣泛的應用到商業、網絡安全等各個領域。在實際工作中，我們常用 FP-Growth 來做頻繁項集的挖掘。當然 Apriori 的改進算法除了 FP-Growth 算法以外，還有 CBA 算法、GSP 算法。- 關聯規則
最早是由 Agrawal 等人在 1993 年提出的。在 1994 年 Agrawal 等人又提出了基于關聯規則的 Apriori 算法，至今 Apriori 仍是關聯規則挖掘的重要算法。
- 關聯規則
-
重要概念
-
項集 itemset
它可以是單個的商品，也可以是商品的組合。 -
支持度
支持度是個百分比，度量 一個集合在原始數據中出現的頻率。指的是：某個商品組合出現的次數與總次數之間的比例。支持度越高，代表這個組合出現的頻率越大
在這個例子中，我們能看到“牛奶”出現了 4 次，那么這 5 筆訂單中“牛奶”的支持度就是 4/5=0.8。同樣“牛奶 + 面包”支持度就是 3/5=0.6。 -
最小支持度Min Support
支持度是針對項集來說的，因此可以定義一個最小支持度，只保 留最小支持度的項集 。 -
頻繁項集
頻繁項集就是支持度大于等于最小支持度 閾值的項集，所以小于最小值支持度的項目就是非頻繁項集，而大于等于最小支持度的項集就是頻繁項集 -
置信度
置信度是個條件概念，就是說在 A 發生的情況下，B 發生的概率是多少。它指的就是當你購買了商品 A，會有多大的概率購買商品 B，在上面這個例子中：
置信度（牛奶→啤酒）=2/4=0.5，代表如果你購買了牛奶，有多大的概率會購買啤酒？
置信度（啤酒→牛奶）=2/3=0.67，代表如果你購買了啤酒，有多大的概率會購買牛奶？ -
提升度
我們在做商品推薦的時候，重點考慮的是提升度，因為提升度代表的是“商品 A 的出現，對商品 B 的出現概率提升的”程度。
還是看上面的例子，如果我們單純看置信度 (可樂→尿布)=1，也就是說可樂出現的時候，用戶都會購買尿布，那么當用戶購買可樂的時候，我們就需要推薦尿布么？
實際上，就算用戶不購買可樂，也會直接購買尿布的，所以用戶是否購買可樂，對尿布的提升作用并不大。
我們可以用下面的公式來計算商品 A 對商品 B 的提升度：
提升度 (A→B)= 置信度 (A→B)/ 支持度 (B)
這個公式是用來衡量 A 出現的情況下，是否會對 B 出現的概率有所提升。
所以提升度有三種可能：
提升度 (A→B)>1：代表有提升；
提升度 (A→B)=1：代表有沒有提升，也沒有下降；
提升度 (A→B)<1：代表有下降
-
-
Apriori 算法的工作原理
關聯分析，從數據集中發現項與項（item 與 item）之間的關系——有兩個目標: 頻繁項集frequent itemset、關聯規則。頻繁項集指經常一塊出現的物品集合;關聯規則暗示兩 種物品之間可能存在很強的關系。-
規則：通過排除法來選擇頻繁項集和關聯規則，
(1) 如果某個項集是頻繁的，那么它的所有子集也是頻繁的;
(2) 如果某個項集是非頻繁的，那么它的所有超集也是非頻繁的;
(3) 基于此，Apriori算法從單元素項集開始，通過組合滿足最小支持 度的項集來形成更大的集合。 -
遞歸流程：
- K=1，計算 K 項集的支持度；
- 篩選掉小于最小支持度的項集；
- 如果項集為空，則對應 K-1 項集的結果為最終結果。
- 否則 K=K+1，重復 1-3 步。
-
-
步驟
首先我們把上面案例中的商品用 ID 來代表，牛奶、面包、尿布、可樂、啤酒、雞蛋的商品 ID 分別設置為 1-6，上面的數據表可以變為：
假設我隨機指定最小支持度是 50%，也就是 0.5。
1.先計算單個商品的支持度，也就是得到 K=1 項的支持度
因為最小支持度是 0.5，所以你能看到商品 4、6 是不符合最小支持度的，不屬于頻繁項集，于是經過篩選商品的頻繁項集就變成：
2.將商品兩兩組合（根據規則2），得到 k=2 項的支持度
篩掉小于最小值支持度的商品組合，可以得到：
3.K=3 項的商品組合，可以得到
再篩掉小于最小值支持度的商品組合，可以得到
改進算法：FP-Growth 算法
- Apriori 優點，算法簡單明了，沒有復雜的理論推導，也易于實現
- Apriori 缺點，會浪費很多計算空間和計算時間：
- FP-Growth 算法，它的特點是：
- 創建了一棵 FP 樹來存儲頻繁項集。在創建前對不滿足最小支持度的項進行刪除，減少了存儲空間。
- 整個生成過程只遍歷數據集 2 次，大大減少了計算量。
FP-Growth 的原理
1. 創建項頭表（item header table）
項頭表包括了項目、支持度，以及該項在 FP 樹中的鏈表。初始的時候鏈表為空。
創建項頭表的作用是為 FP 構建及頻繁項集挖掘提供索引。這一步的流程是先掃描一遍數據集，對于滿足最小支持度的單個項（K=1 項集）按照支持度從高到低進行排序，這個過程中刪除了不滿足最小支持度的項。
2. 構造 FP 樹
FP 樹的根節點記為 NULL 節點。整個流程是需要再次掃描數據集，對于每一條數據，按照支持度從高到低的順序進行創建節點（也就是第一步中項頭表中的排序結果），節點如果存在就將計數 count+1，如果不存在就進行創建。同時在創建的過程中，需要更新項頭表的鏈表
具體的操作會用到一個概念，叫“條件模式基”，它指的是以要挖掘的節點為葉子節點，自底向上求出 FP 子樹，然后將 FP 子樹的祖先節點設置為葉子節點之和。
“啤酒”的節點為例，從 FP 樹中可以得到一棵 FP 子樹，將祖先節點的支持度記為葉子節點之和，得到：
相比于原來的 FP 樹，尿布和牛奶的頻繁項集數減少了。這是因為我們求得的是以“啤酒”為節點的 FP 子樹，也就是說，在頻繁項集中一定要含有“啤酒”這個項。你可以再看下原始的數據，其中訂單 1{牛奶、面包、尿布}和訂單 5{牛奶、面包、尿布、可樂}并不存在“啤酒”這個項，所以針對訂單 1，尿布→牛奶→面包這個項集就會從 FP 樹中去掉，針對訂單 5 也包括了尿布→牛奶→面包這個項集也會從 FP 樹中去掉，所以你能看到以“啤酒”為節點的 FP 子樹，尿布、牛奶、面包項集上的計數比原來少了 2。條件模式基不包括“啤酒”節點，而且祖先節點如果小于最小支持度就會被剪枝，所以“啤酒”的條件模式基為空。
同理，我們可以求得“面包”的條件模式基為：
AdaBoost.
1.基本認知
-
簡介
AdaBoost 算法，Adaptive Boosting，中文含義是自適應提升算法，分類算法中的集成算法。其核心思想是其實是針對同一個訓練集訓練不同的分 類器(弱分類器)，然后把這些弱分類器根據不同的權重組合，構成一個更強的最終分類器 (強分類器)。
實際上 AdaBoost 算法是一個框架，你可以指定任意的分類器，通常我們可以采用 CART 分類器作為弱分類器 -
組合公式
假設弱分類器為 Gi?(x)，它在強分類器中的權重 αi?，那么就可以得出強分類器 f(x)：
-
如何得到弱分類器，也就是在每次迭代訓練的過程中，如何得到最優弱分類器？
通過改變樣本的數據分布來實現的。
(1) 先通過對N個訓練樣本的學習得到第一個弱分類器;
(2) 將分錯的樣本增加權重和其他的新數據一起構成一個新的N個的訓練樣本， 再基于上一次得到的分類準確率，來確定這次訓練樣本中每個樣本的權重，將修改過權值的新數據集送給下層分類器進行訓練，得到第二個弱分類器，整個訓練過程如此迭代地進行下去;
(3) 將第1、2步都分錯了的樣本加上其他的新樣本構成另一個新的N 個的訓練樣本，通過對這個樣本的學習得到第三個弱分類器;
(4) 最終分類器最后融合成強分類器。即某個數據被分為哪一類要由各分類器 權值決定。
Dk+1? 代表第 k+1 輪訓練中，樣本的權重集合，其中 Wk+1,1? 代表第 k+1 輪中第一個樣本的權重，以此類推 Wk+1,N? 代表第 k+1 輪中第 N 個樣本的權重，因此用公式表示為：
第 k+1 輪中的樣本權重，是根據該樣本在第 k 輪的權重以及第 k 個分類器的準確率而定，具體的公式為：
該算法其實是簡單的弱分類算法的提升過程，這個過程通過不斷地訓練，可以提高對數據的分類能力。這樣做的好處就是，通過每一輪訓練樣本的動態權重，可以讓訓練的焦點集中到難分類的樣本上，最終得到的弱分類器的組合更容易得到更高的分類準確率。 -
每個弱分類器在強分類器中的權重是如何計算的？
基于這個弱分類器對樣本的分類錯誤率來決定它的權重。實際上在一個由 K 個弱分類器中組成的強分類器中，如果弱分類器的分類效果好，那么權重應該比較大，如果弱分類器的分類效果一般，權重應該降低。所以我們需要用公式表示就是：
其中 ei? 代表第 i 個分類器的分類錯誤率。 -
主要解決
兩類問題、 多類單標簽問題、多類多標簽問題、大類單標簽問題和回歸問題。 -
優缺點
- 優點
- Aadboost 算法系列具有較高的檢測速率，且不易出現過擬合現象。
- 缺點
- 該 算法在實現過程中為取得更高的檢測精度則需要較大的訓練樣本集，執行效果 依賴于弱分類器的選擇，搜索時間隨之增加，故訓練過程使得所用時間非常大， 也因此限制了該算法的廣泛應用。
- 優點
算法示例
假設我有 10 個訓練樣本如下所示，希望通過 AdaBoost 構建一個強分類器
有 3 個基礎分類器：
分類器 f1 的錯誤率為 0.3，也就是 x 取值 6、7、8 時分類錯誤；
分類器 f2 的錯誤率為 0.4，即 x 取值 0、1、2、9 時分類錯誤
分類器 f3 的錯誤率為 0.3，即 x 取值為 3、4、5 時分類錯誤。
f1、f3 分類器的錯誤率最低，因此我們選擇 f1 或 f3 作為最優分類器，假設我們選 f1 分類器作為最優分類器，即第一輪訓練得到：
分類器權重公式得到：
根據分類器權重公式得到：
在這 3 個分類器中，f2 分類器的錯誤率最低，因此我們選擇 f2 作為第三輪訓練的最優分類器，即：
我們根據分類器權重公式得到：
模型效果評估
預測模型評估：
MSE
Mean squared error，均方誤差。
參數估計值與參數真值之差平方的期望值，
用于評估數據的變化程度，MSE值越小，模型精確度越高。
RMSE
均方誤差的算術平方根
MAE
mMean absolute error.平均絕對誤差，絕對誤差的平均值。平均絕對誤差在一些問題上能夠更好地反映預測誤差的實際情況。
二分類模型評估：
| 實際為正例 | TP：True Positive。 | FN：False Negative |
| 實際為負例 | FP：False Positive | TN：True Negative |
-
正例反例
是一個相對概念。正想里通常我是我們所關注的結果。 -
精確率precision，TP/(TP+FP)
預測為正例的正確率。實際問題中更關注準確率，樣本的正負例分布并不均勻。 -
召回率recall，TP/(TP+FN)
實際為正例的正確率 -
正確率，（TP+TN）/(TP+FP+FP+TN)
判斷的總正確率 -
pr曲線
以precision（精準率）和recall（召回率）這兩個為變量而做出的曲線，其中recall為橫坐標，precision為縱坐標。
一條PR曲線要對應一個閾值。通過選擇合適的閾值，比如50%，對樣本進行劃分，概率大于50%的就認為是正例，小于50%的就是負例,從而計算相應的精準率和召回率。
如果一個學習器的P-R曲線被另一個學習器的P-R曲線完全包住，則可斷言后者的性能優于前者，例如上面的A和B優于學習器C。但是A和B的性能無法直接判斷，我們可以根據曲線下方的面積大小來進行比較，但更常用的是平衡點或者是F1值。平衡點（BEP）是P=R時的取值，如果這個值較大，則說明學習器的性能較好。而F1 = 2 * P * R ／( P + R )，同樣，F1值越大，我們可以認為該學習器的性能較好。 -
ROC曲線
用來刻畫二分類問題的圖形。
橫軸是假正例率（FPR），縱軸是真正例率（TPR）。
(1)真正類率(True Postive Rate)TPR: TP/(TP+FN),代表分類器預測的正類中實際正實例占所有正實例的比例。
(2)負正類率(False Postive Rate)FPR: FP/(FP+TN)，代表分類器預測的正類中實際負實例占所有負實例的比例。
我們可以發現：TPR=Recall。 -
AUC：
ROC曲線一定會經過（0，0）和（1，1）兩個點。在此基礎上，要盡量使曲線下方所圍成的面積最大化。這部分面積稱為AUC。在解釋性較強的問題中會經常用到。 -
多分類問題的評估方法
- 將多分類問題轉化了二分類問題
將最關心的分類作為正例，其余作為負例 - 混淆矩陣
- 將多分類問題轉化了二分類問題
總結
以上是生活随笔為你收集整理的数据挖掘（Data Mining）扫盲笔记的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： spring学习（39）:注入map类型
- 下一篇： 对逻辑数据库的操作