鳶尾花演算法

❶ 楦㈠熬鑺卞喅絳栨爲綆楁硶閫夐樼殑鐩鐨勫拰鎰忎箟

楦㈠熬鑺卞喅絳栨爲綆楁硶閫夐樼殑鐩鐨勫拰鎰忎箟涓猴細
1銆佺洰鐨勶細鏄鍒涘緩涓縐嶆ā鍨嬩粠鏁版嵁鐗瑰緛涓瀛︿範綆鍗曠殑鍐崇瓥瑙勫垯鏉ラ勬祴涓涓鐩鏍囧彉閲忕殑鍊箋
2銆佹剰涔夛細閫氳繃瀵歸涪灝捐姳鏁版嵁闆嗚繘琛屽喅絳栨爲鍒嗙被錛屽苟瀵瑰垎綾葷粨鏋滀笌瀹為檯緇撴灉榪涜屾瘮瀵癸紝榪涜屽垎鏋愬叾鍒嗙被鐨勫噯紜鐜囷紝鏈鍚庡熀浜嶱ython璇璦錛岃捐′笌瀹炵幇浜嗗喅絳栨爲妯″瀷鍦ㄥ歸涪灝捐姳鏁版嵁闆嗗垎綾諱腑鐨勫簲鐢ㄥ疄渚嬨

❷ KNN 演算法-理論篇-如何給電影進行分類

KNN 演算法 的全稱是 K-Nearest Neighbor ，中文為 K 近鄰 演算法，它是基於 距離 的一種演算法，簡單有效。

KNN 演算法 即可用於分類問題，也可用於回歸問題。

假如我們統計了一些 電影數據，包括電影名稱，打鬥次數，接吻次數，電影類型 ，如下：

可以看到，電影分成了兩類，分別是動作片和愛情片。

如果現在有一部新的電影A，它的打鬥和接吻次數分別是80 和7，那如何用KNN 演算法對齊進行分類呢？

我們可以將打鬥次數作為 X 軸 ，接吻次數作為 Y 軸 ，將上述電影數據畫在一個坐標系中，如下：

通過上圖可以直觀的看出，動作電影與愛情電影的分布范圍是不同的。

KNN 演算法 基於距離，它的原理是： 選擇與待分類數據最近的K 個點，這K 個點屬於哪個分類最多，那麼待分類數據就屬於哪個分類 。

所以，要判斷電影A 屬於哪一類電影，就要從已知的電影樣本中，選出距離電影A 最近的K 個點：

比如，我們從樣本中選出三個點（即 K 為 3），那麼距離電影A 最近的三個點是《功夫》，《黑客帝國》和《戰狼》，而這三部電影都是動作電影。因此，可以判斷電影A 也是動作電影。

另外，我們還要處理兩個問題：

關於點之間的距離判斷，可以參考文章 《計算機如何理解事物的相關性》 。

至於K 值的選擇，K 值較大或者較小都會對模型的訓練造成負面影響，K 值較小會造成 過擬合 ，K 值較大 欠擬合 。

因此，K 值的選擇，一般採用 交叉驗證 的方式。

交叉驗證的思路是，把樣本集中的大部分樣本作為訓練集，剩餘部分用於預測，來驗證分類模型的准確度。一般會把 K 值選取在較小范圍內，逐一嘗試K 的值，當模型准確度最高時，就是最合適的K 值。

可以總結出， KNN 演算法 用於分類問題時，一般的步驟是：

如果，我們現在有一部電影B，知道該電影屬於動作電影，並且知道該電影的接吻次數是 7 ，現在想預測該電影的打鬥次數是多少？

這個問題就屬於 回歸問題 。

首先看下，根據已知數據，如何判斷出距離電影B 最近的K 個點。

我們依然設置K 為3，已知數據為：

根據已知數據可以畫出下圖：

圖中我畫出了一條水平線，這條線代表所有接吻次數是7 的電影，接下來就是要找到距離 這條線 最近的三部（K 為 3）動作電影。

可以看到，距離這條水平線最近的三部動作電影是《功夫》，《黑客帝國》和《戰狼》，那麼這三部電影的打鬥次數的平均值，就是我們預測的電影B 的打鬥次數。

所以，電影B 的打鬥次數是：

本篇文章主要介紹了 KNN 演算法 的基本原理，它簡單易懂，即可處理分類問題，又可處理回歸問題。

KNN 演算法 是基於 距離 的一種機器學習演算法，需要計算測試點與樣本點之間的距離。因此，當數據量大的時候，計算量就會非常龐大，需要大量的存儲空間和計算時間。

另外，如果樣本數據分類不均衡，比如有些分類的樣本非常少，那麼該類別的分類准確率就會很低。因此，在實際應用中，要特別注意這一點。

（本節完。）

推薦閱讀：

決策樹演算法-理論篇-如何計算信息純度

決策樹演算法-實戰篇-鳶尾花及波士頓房價預測

樸素貝葉斯分類-理論篇-如何通過概率解決分類問題

樸素貝葉斯分類-實戰篇-如何進行文本分類

計算機如何理解事物的相關性-文檔的相似度判斷

❸ 決策樹（Decision Tree）

決策樹是一種非參數有監督的機器學習方法，可以用於解決回歸問題和分類問題。通過學習已有的數據，計算得出一系列推斷規則來預測目標變數的值，並用類似流程圖的形式進行展示。決策樹模型可以進行可視化，具有很強的可解釋性，演算法容易理解，以決策樹為基礎的各種集成演算法在很多領域都有廣泛的應用。

熵的概念最早起源於物理學，用於度量一個熱力學系統的無序程度。在資訊理論裡面，信息熵代表著一個事件或一個變數等所含有的信息量。 在信息世界，熵越高，則能傳輸越多的信息，熵越低，則意味著傳輸的信息越少。

發生概率低的事件比發生概率高的事件具有更大的不確定性，需要更多的信息去描述他們，信息熵更高。

我們可以用計算事件發生的概率來計算事件的信息，又稱「香農信息」（ Shannon Information ）。一個離散事件x的信息可以表示為：
h(x) = -log(p(x))
p() 代表事件x發生的概率， log() 為以二為底的對數函數，即一個事件的信息量就是這個事件發生的概率的負對數。選擇以二為底的對數函數代表計算信息的單位是二進制。因為概率p(x)小於1，所以負號就保證了信息熵永遠不為負數。當事件的概率為1時，也就是當某事件百分之百發生時，信息為0。

熵（ entropy ），又稱「香農熵」（ Shannon entropy ），表示一個隨機變數的分布所需要的平均比特數。一個隨機變數的信息熵可以表示為：
H(x) = -sum(each k in K p(k)log(p(k)))
K表示變數x所可能具有的所有狀態（所有事件），將發生特定事件的概率和該事件的信息相乘，最後加和，即可得到該變數的信息熵。可以理解為，信息熵就是平均而言發生一個事件我們得到的信息量大小。所以數學上，信息熵其實是事件信息量的期望。

當組成該隨機變數的一個事件的概率為1時信息熵最小，為0， 即該事件必然發生。當組成該隨機變數的所有事件發生的概率相等時，信息熵最大，即完全不能判斷那一個事件更容易發生，不確定性最大。

當一個事件主導時，比如偏態分布（ Skewed Probability Distribution ），不確定性減小，信息熵較低（low entropy）；當所有事件發生概率相同時，比如均衡分布（ Balanced Probability Distribution ），不確定性極大，信息熵較高（high entropy）。

由以上的香農信息公式可知，信息熵主要有三條性質：
- 單調性 。發生概率越高的事件，其所攜帶的信息熵越低。比如一個真理的不確定性是極低的，那麼它所攜帶的信息熵就極低。
- 非負性 。信息熵不能為負。單純從邏輯層面理解，如果得知了某個信息後，卻增加了不確定性，這也是不合邏輯的。
- 可加性 。即多隨機事件同時發生存在的總不確定性的量度是可以表示為各事件不確定性的量度的和。

若兩事件A和B同時發生，兩個事件相互獨立。 p(X=A,Y=B) = p(X = A)*p(Y=B) , 那麼信息熵為 H(A,B) = H(A) + H(B) 。但若兩事件不相互獨立，那麼 H(A,B) = H(A) + H(B) - I(A,B) 。其中 I(A,B) 是互信息（ mutual information，MI ），即一個隨機變數包含另一個隨機變數信息量的度量。即已知X的情況下，Y的分布是否會改變。

可以理解為，兩個隨機變數的互信息度量了兩個變數間相互依賴的程度。X 和 Y的互信息可以表示為：
I(X;Y) = H(X) - H(X|Y)
H(X)是X的信息熵，H(X|Y)是已知Y的情況下，X的信息熵。結果的單位是比特。
簡單來說，互信息的性質為：
- I(X;Y)>=0 互信息永遠不可能為負
- H(X) - H(X|Y) = I(X;Y) = I (Y;X) = H(Y) - H(Y|X) 互信息是對稱的
-當X，Y獨立的時候， I(X;Y) = 0 互信息值越大，兩變數相關性越強。
-當X，Y知道一個就能推斷另一個的時候， I(X;Y) = H(Y) = H(X)

在數據科學中，互信息常用於特徵篩選。在通信系統中互信息也應用廣泛。在一個點到點的通信系統中，發送信號為X，通過信道後，接收端接收到的信號為Y，那麼信息通過信道傳遞的信息量就是互信息 I(X,Y) 。根據這個概念，香農推導出信道容量（即臨界通信傳輸速率的值）。

信息增益（ Information Gain ）是用來按照一定規則劃分數據集後，衡量信息熵減少量的指數。

那數據集的信息熵又是怎麼計算的呢？比如一個常見的0,1二分類問題，我們可以計算它的熵為：
Entropy = -(p(0) * log(P(0)) + p(1) * log(P(1)))
當該數據集為50/50的數據集時，它的信息熵是最大的（1bit）。而10/90的數據集將會大大減少結果的不確定性，減小數據集的信息熵（約為0.469bit）。

這樣來說，信息熵可以用來表示數據集的純度（ purity ）。信息熵為0就表示該數據集只含有一個類別，純度最高。而較高的信息熵則代表較為平衡的數據集和較低的純度。

信息增益是提供了一種可以使用信息熵計算數據集經過一定的規則（比如決策樹中的一系列規則）進行數據集分割後信息熵的變化的方法。
IG(S,a) = H(S) - H(S|a)
其中，H(s) 是原數據集S的信息熵（在做任何改變之前），H(S|a)是經過變數a的一定分割規則。所以信息增益描述的是數據集S變換後所節省的比特數。

信息增益可以用做決策樹的分枝判斷方法。比如最常用CART樹（ Classification and Regression Tree ）中的分枝方法，只要在python中設置參數 criterion 為 「entropy」 即可。

信息增益也可以用作建模前的特徵篩選。在這種場景下，信息增益和互信息表達的含義相同，會被用來計算兩變數之間的獨立性。比如scikit-learn 中的函數 mutual_info_classiif()

信息增益在面對類別較少的離散數據時效果較好，但是面對取值較多的特徵時效果會有 偏向性 。因為當特徵的取值較多時，根據此特徵劃分得到的子集純度有更大的可能性會更高(對比與取值較少的特徵)，因此劃分之後的熵更低，由於劃分前的熵是一定的，因此信息增益更大，因此信息增益比較偏向取值較多的特徵。舉一個極端的例子來說，如果一個特徵為身份證號，當把每一個身份證號不同的樣本都分到不同的子節點時，熵會變為0，意味著信息增益最大，從而該特徵會被演算法選擇。但這種分法顯然沒有任何實際意義。

這種時候，信息增益率就起到了很重要的作用。
gR(D,A)=g(D,A)/HA(D)
HA(D) 又叫做特徵A的內部信息，HA(D)其實像是一個衡量以特徵AA的不同取值將數據集D分類後的不確定性的度量。如果特徵A的取值越多，那麼不確定性通常會更大，那麼HA(D)的值也會越大，而1/HA(D)的值也會越小。這相當於是在信息增益的基礎上乘上了一個懲罰系數。即 gR(D,A)=g(D,A)∗懲罰系數 。

在CART演算法中，基尼不純度表示一個隨機選中的樣本被分錯類別的可能性，即這個樣本被選中的概率乘以它被分錯的概率。當一個節點中所有樣本均為一種時（沒有被分錯的樣本），基尼不純度達到最低值0。

舉例來說，如果有綠色和藍色兩類數據點，各佔一半（藍色50%，綠色50%）。那麼我們隨機分類，有以下四種情況：
-分為藍色，但實際上是綠色（❌），概率25%
-分為藍色，實際上也是藍色（✔️），概率25%
-分為綠色，實際上也是綠色（✔️），概率25%
-分為綠色，但實際上是藍色（❌），概率25%
那麼將任意一個數據點分錯的概率為25%+25% = 50%。基尼不純度為0.5。

在特徵選擇中，我們可以選擇加入後使數據不純度減少最多的特徵。

噪音數據簡單來說就是會對模型造成誤導的數據。分為類別雜訊（ class noise 或 label noise ）和 變數雜訊（ attribute noise ）。類別雜訊指的的是被錯誤標記的錯誤數據，比如兩個相同的樣本具有不同的標簽等情況。變數雜訊指的是有問題的變數，比如缺失值、異常值和無關值等。

決策樹其實是一種圖結構，由節點和邊構成。
-根節點：只有出邊沒有入邊。包含樣本全集，表示一個對樣本最初的判斷。
-內部節點：一個入邊多個出邊。表示一個特徵或是屬性。每個內部節點都是一個判斷條件，包含數據集中從根節點到該節點所有滿足條件的數據的集合。
-葉節點：一個入邊無出邊。表示一個類，對應於決策結果。

決策樹的生成主要分為三個步驟：
1. 節點的分裂 ：當一個節點不夠純（單一分類佔比不夠大或者說信息熵較大）時，則選擇將這一節點進行分裂。
2. 決策邊界的確定 ：選擇正確的決策邊界（ Decision Boundary ），使分出的節點盡量純，信息增益（熵減少的值）盡可能大。
3. 重復及停止生長 ：重復1，2步驟，直到純度為0或樹達到最大深度。為避免過擬合，決策樹演算法一般需要制定樹分裂的最大深度。到達這一深度後，即使熵不等於0，樹也不會繼續進行分裂。

下面以超級知名的鳶尾花數據集舉例來說明。
這個數據集含有四個特徵：花瓣的長度（ petal length ）、花瓣的寬度( petal width )、花萼的長度( sepal length )和花萼的寬度( sepal width )。預測目標是鳶尾花的種類 iris setosa, iris versicolor 和 iris virginica 。

建立決策樹模型的目標是根據特徵盡可能正確地將樣本劃分到三個不同的「陣營」中。

根結點的選擇基於全部數據集，使用了貪婪演算法：遍歷所有的特徵，選擇可以使信息熵降到最低、基尼不純度最低的特徵。

如上圖，根節點的決策邊界為' petal width = 0.8cm '。那麼這個決策邊界是怎麼決定的呢？
-遍歷所有可能的決策邊界（需要注意的是，所有可能的決策邊界代表的是該子集中該特徵所有的值，不是以固定增幅遍歷一個區間內的所有值！那樣很沒有必要的～）
-計算新建的兩個子集的基尼不純度。
-選擇可以使新的子集達到最小基尼不純度的分割閾值。這個「最小」可以指兩個子集的基尼不純度的和或平均值。

ID3是最早提出的決策樹演算法。ID3演算法的核心是在決策樹各個節點上根據 信息增益 來選擇進行劃分的特徵，然後遞歸地構建決策樹。
- 缺點 ：
（1）沒有剪枝
（2）只能用於處理離散特徵
（3）採用信息增益作為選擇最優劃分特徵的標准，然而信息增益會偏向那些取值較多的特徵(例如，如果存在唯一標識屬性身份證號，則ID3會選擇它作為分裂屬性，這樣雖然使得劃分充分純凈，但這種劃分對分類幾乎毫無用處。)

C4.5 與ID3相似，但對ID3進行了改進：
-引入「悲觀剪枝」策略進行後剪枝
-信息增益率作為劃分標准
-將連續特徵離散化，假設 n 個樣本的連續特徵 A 有 m 個取值，C4.5 將其排序並取相鄰兩樣本值的平均數共 m-1 個劃分點，分別計算以該劃分點作為二元分類點時的信息增益，並選擇信息增益最大的點作為該連續特徵的二元離散分類點；
-可以處理缺失值

對於缺失值的處理可以分為兩個子問題：
（1）在特徵值缺失的情況下進行劃分特徵的選擇？（即如何計算特徵的信息增益率）
C4.5 中對於具有缺失值特徵，用沒有缺失的樣本子集所佔比重來折算；
（2）選定該劃分特徵，對於缺失該特徵值的樣本如何處理？（即到底把這個樣本劃分到哪個結點里）
C4.5 的做法是將樣本同時劃分到所有子節點，不過要調整樣本的權重值，其實也就是以不同概率劃分到不同節點中。

（1）剪枝策略可以再優化；
（2）C4.5 用的是多叉樹，用二叉樹效率更高；
（3）C4.5 只能用於分類；
（4）C4.5 使用的熵模型擁有大量耗時的對數運算，連續值還有排序運算；
（5）C4.5 在構造樹的過程中，對數值屬性值需要按照其大小進行排序，從中選擇一個分割點，所以只適合於能夠駐留於內存的數據集，當訓練集大得無法在內存容納時，程序無法運行。

可以用於分類，也可以用於回歸問題。CART 演算法使用了基尼系數取代了信息熵模型，計算復雜度更低。

CART 包含的基本過程有 分裂，剪枝和樹選擇 。
分裂 ：分裂過程是一個二叉遞歸劃分過程，其輸入和預測特徵既可以是連續型的也可以是離散型的，CART 沒有停止准則，會一直生長下去；
剪枝 ：採用「代價復雜度」剪枝，從最大樹開始，每次選擇訓練數據熵對整體性能貢獻最小的那個分裂節點作為下一個剪枝對象，直到只剩下根節點。CART 會產生一系列嵌套的剪枝樹，需要從中選出一顆最優的決策樹；
樹選擇 ：用單獨的測試集評估每棵剪枝樹的預測性能（也可以用交叉驗證）。

（1）C4.5 為多叉樹，運算速度慢，CART 為二叉樹，運算速度快；
（2）C4.5 只能分類，CART 既可以分類也可以回歸；
（3）CART 使用 Gini 系數作為變數的不純度量，減少了大量的對數運算；
（4）CART 採用代理測試來估計缺失值，而 C4.5 以不同概率劃分到不同節點中；
（5）CART 採用「基於代價復雜度剪枝」方法進行剪枝，而 C4.5 採用悲觀剪枝方法。

（1）決策樹易於理解和解釋，可以可視化分析，容易提取出規則
（2）可以同時處理分類型和數值型數據
（3）可以處理缺失值
（4）運行速度比較快（使用Gini的快於使用信息熵，因為信息熵演算法有log）

（1）容易發生過擬合（集成演算法如隨機森林可以很大程度上減少過擬合）
（2）容易忽略數據集中屬性的相互關聯；
（3）對於那些各類別樣本數量不一致的數據，在決策樹中，進行屬性劃分時，不同的判定準則會帶來不同的屬性選擇傾向。

寫在後面：這個專輯主要是本小白在機器學習演算法學習過程中的一些總結筆記和心得，如有不對之處還請各位大神多多指正！（關於決策樹的剪枝還有很多沒有搞懂，之後弄明白了會再單獨出一篇總結噠）

參考資料鏈接：
1. https://machinelearningmastery.com/what-is-information-entropy/
2. https://zhuanlan.hu.com/p/29679277
3. https://machinelearningmastery.com/information-gain-and-mutual-information/
4. https://victorzhou.com/blog/gini-impurity/
5. https://sci2s.ugr.es/noisydata
6. https://towardsdatascience.com/understanding-decision-trees-once-and-for-all-2d891b1be579
7. https://blog.csdn.net/weixin_36586536/article/details/80468426
8. https://zhuanlan.hu.com/p/85731206