互信息演算法

① 全面歸納距離和相似度計算方法

距離(distance，差異程度)、相似度(similarity，相似程度)方法可以看作是以某種的距離函數計算元素間的距離，這些方法作為機器學習的基礎概念，廣泛應用於如：Kmeans聚類、協同過濾推薦演算法、相似度演算法、MSE損失函數等等。本文對常用的距離計算方法進行歸納以及解析，分為以下幾類展開：

對於點x=(x1,x2...xn) 與點y=(y1,y2...yn) , 閔氏距離可以用下式表示：

閔氏距離是對多個距離度量公式的概括性的表述，p=1退化為曼哈頓距離；p=2退化為歐氏距離；切比雪夫距離是閔氏距離取極限的形式。

曼哈頓距離 公式：

歐幾里得距離公式：

如下圖藍線的距離即是曼哈頓距離（想像你在曼哈頓要從一個十字路口開車到另外一個十字路口實際駕駛距離就是這個「曼哈頓距離」，此即曼哈頓距離名稱的來源，也稱為城市街區距離），紅線為歐幾里得距離：

切比雪夫距離起源於國際象棋中國王的走法，國際象棋中國王每次只能往周圍的8格中走一步，那麼如果要從棋盤中A格(x1,y1)走到B格(x2,y2)最少需要走幾步？你會發現最少步數總是max(|x2-x1|,|y2-y1|)步。有一種類似的一種距離度量方法叫切比雪夫距離。

切比雪夫距離就是當p趨向於無窮大時的閔氏距離：

距離函數並不一定是距離度量，當距離函數要作為距離度量，需要滿足：

由此可見，閔氏距離可以作為距離度量，而大部分的相似度並不能作為距離度量。

閔氏距離也是Lp范數（如p==2為常用L2范數正則化）的一般化定義。
下圖給出了一個Lp球（ ||X||p = 1 ）的形狀隨著P的減少的可視化圖：

距離度量隨著空間的維度d的不斷增加，計算量復雜也逐增，另外在高維空間下，在維度越高的情況下，任意樣本之間的距離越趨於相等（樣本間最大與最小歐氏距離之間的相對差距就趨近於0），也就是維度災難的問題，如下式結論：

對於維度災難的問題，常用的有PCA方法進行降維計算。

假設各樣本有年齡，工資兩個變數，計算歐氏距離（p=2）的時候，(年齡1-年齡2)² 的值要遠小於(工資1-工資2)² ，這意味著在不使用特徵縮放的情況下，距離會被工資變數（大的數值）主導, 特別當p越大，單一維度的差值對整體的影響就越大。因此，我們需要使用特徵縮放來將全部的數值統一到一個量級上來解決此問題。基本的解決方法可以對數據進行「標准化」和「歸一化」。

另外可以使用馬氏距離（協方差距離），與歐式距離不同其考慮到各種特性之間的聯系是（量綱）尺度無關 (Scale Invariant) 的，可以排除變數之間的相關性的干擾，缺點是誇大了變化微小的變數的作用。馬氏距離定義為：

馬氏距離原理是使用矩陣對兩兩向量進行投影後，再通過常規的歐幾里得距離度量兩對象間的距離。當協方差矩陣為單位矩陣，馬氏距離就簡化為歐氏距離；如果協方差矩陣為對角陣，其也可稱為正規化的歐氏距離。

根據向量x,y的點積公式：

我們可以利用向量間夾角的cos值作為向量相似度[1]：

餘弦相似度的取值范圍為：-1~1，1 表示兩者完全正相關，-1 表示兩者完全負相關，0 表示兩者之間獨立。餘弦相似度與向量的長度無關，只與向量的方向有關，但餘弦相似度會受到向量平移的影響（上式如果將 x 平移到 x+1, 餘弦值就會改變）。

另外，歸一化後計算歐氏距離，等價於餘弦值：兩個向量x,y, 夾角為A，歐氏距離D=(x-y)^2 = x ^2+y 2-2|x||y|cosA = 2-2cosA

協方差是衡量多維數據集中，變數之間相關性的統計量。如下公式X，Y的協方差即是，X減去其均值 乘以 Y減去其均值，所得每一組數值的期望（平均值）。

如果兩個變數之間的協方差為正值，則這兩個變數之間存在正相關，若為負值，則為負相關。

皮爾遜相關系數數值范圍也是[-1，1]。皮爾遜相關系數可看作是在餘弦相似度或協方差基礎上做了優化（變數的協方差除以標准差）。它消除每個分量標准不同（分數膨脹）的影響，具有平移不變性和尺度不變性。

卡方檢驗X2，主要是比較兩個分類變數的關聯性、獨立性分析。如下公式，A代表實際頻數；E代表期望頻數：

Levenshtein 距離是 編輯距離 (Editor Distance) 的一種，指兩個字串之間，由一個轉成另一個所需的最少編輯操作次數。允許的編輯操作包括將一個字元替換成另一個字元，插入一個字元，刪除一個字元。
像hallo與hello兩個字元串編輯距離就是1，我們通過替換」a「 為 」e「，就可以完成轉換。

漢明距離為兩個等長字元串對應位置的不同字元的個數，也就是將一個字元串變換成另外一個字元串所需要替換的字元個數。例如：1011101 與 1001001 之間的漢明距離是 2，「toned」 與 「roses」 之間的漢明距離是 3

另外的，對於字元串距離來說，不同字元所佔的份量是不一樣的。比如」我樂了「 與【「我怒了」，」我樂了啊」 】的Levenshtein 距離都是1，但其實兩者差異還是很大的，因為像「啊」這種語氣詞的重要性明顯不如「樂」，考慮字元（特徵）權重的相似度方法有：TF-IDF、BM25、WMD演算法。

Jaccard 取值范圍為0~1，0 表示兩個集合沒有重合，1 表示兩個集合完全重合。

但Dice不滿足距離函數的三角不等式，不是一個合適的距離度量。

基礎地介紹下信息熵，用來衡量一個隨機變數的不確定性程度。對於一個隨機變數 X，其概率分布為：

互信息用於衡量兩個變數之間的關聯程度，衡量了知道這兩個變數其中一個，對另一個不確定度減少的程度。公式為：

如下圖，條件熵表示已知隨機變數X的情況下，隨機變數Y的信息熵，因此互信息實際上也代表了已知隨機變數X的情況下，隨機變數Y的(信息熵)不確定性的減少程度。

JS 散度解決了 KL 散度不對稱的問題，定義為：

群體穩定性指標（Population Stability Index，PSI）， 可以看做是解決KL散度非對稱性的一個對稱性度量指標，用於度量分布之間的差異（常用於風控領域的評估模型預測的穩定性）。

psi與JS散度的形式是非常類似的，如下公式：

PSI的含義等同P與Q，Q與P之間的KL散度之和。

DTW 距離用於衡量兩個序列之間的相似性，適用於不同長度、不同節奏的時間序列。DTW採用了動態規劃DP（dynamic programming）的方法來進行時間規整的計算，通過自動warping扭曲 時間序列（即在時間軸上進行局部的縮放），使得兩個序列的形態盡可能的一致，得到最大可能的相似度。(具體可參考[5])

圖結構間的相似度計算，有圖同構、最大共同子圖、圖編輯距離、Graph Kernel 、圖嵌入計算距離等方法（具體可參考[4][6]）。

度量學習的對象通常是樣本特徵向量的距離，度量學習的關鍵在於如何有效的度量樣本間的距離，目的是通過訓練和學習，減小或限制同類樣本之間的距離，同時增大不同類別樣本之間的距離，簡單歸類如下[2]：

最後，附上常用的距離和相似度度量方法[3]：

② 決策樹（Decision Tree）

通俗來說，決策樹分類的思想類似於找對象。現想像一個女孩的母親要給這個女孩介紹男朋友，於是有了下面的對話：

      女兒：多大年紀了？

      母親：26。

      女兒：長的帥不帥？

      母親：挺帥的。

      女兒：收入高不？

      母親：不算很高，中等情況。

      女兒：是公務員不？

      母親：是，在稅務局上班呢。

      女兒：那好，我去見見。

      這個女孩的決策過程就是典型的分類樹決策。相當於通過年齡、長相、收入和是否公務員對將男人分為兩個類別：見和不見。假設這個女孩對男人的要求是：30歲以下、長相中等以上並且是高收入者或中等以上收入的公務員，圖1表示了女孩的決策邏輯。

如果你作為一個女生，你會優先考慮哪個條件：長相？收入？還是年齡。在考慮年齡條件時使用25歲為劃分點，還是35歲為劃分點。有這么多條件，用哪個條件特徵先做if，哪個條件特徵後做if比較優呢？還有怎麼確定用特徵中的哪個數值作為劃分的標准。這就是決策樹機器學習演算法的關鍵了。

首先，我們需要熟悉資訊理論中熵的概念。熵度量了事物的不確定性，越不確定的事物，它的熵就越大。具體的，隨機變數X的熵的表達式如下：

如拋一枚硬幣為事件 ， ， ，

擲一枚骰子為事件 ， ，

，顯然擲骰子的不確定性比投硬幣的不確定性要高。 

熟悉了單一變數的熵，很容易推廣到多個個變數的聯合熵，這里給出兩個變數X和Y的聯合熵表達式：

有了聯合熵，又可以得到條件熵的表達式H(X|Y)，條件熵類似於條件概率,它度量了我們在知道Y以後X剩下的不確定性。表達式：

我們剛才提到 度量了 的不確定性，條件熵 度量了我們在知道 以後 剩下的不確定性，那麼 呢？它度量了 在知道 以後不確定性減少程度，這個度量我們在資訊理論中稱為互信息，記為 。

信息熵 ，聯合熵 ，條件熵 ，互信息 之間的關系由圖2所示：

在決策樹的ID3演算法中，互信息 被稱為信息增益。ID3演算法就是用信息增益來判斷當前節點應該用什麼特徵來構建決策樹。信息增益大，則越適合用來分類。

下面我們用SNS社區中不真實賬號檢測的例子說明如何使用ID3演算法構造決策樹。為了簡單起見，我們假設訓練集合包含10個元素：

設L、F、H和D表示日誌密度、好友密度、是否使用真實頭像和賬號是否真實，下面計算各屬性的信息增益：

 因此日誌密度的信息增益是0.276。用同樣方法得到H和F的信息增益分別為0.033和0.553。因為F具有最大的信息增益，所以第一次分裂選擇F為分裂屬性，分裂後的結果圖3表示：

在上圖的基礎上，再遞歸使用這個方法計運算元節點的分裂屬性，最終就可以得到整個決策樹。

但是ID3演算法中還存在著一些不足之處：

1.ID3沒有考慮連續特徵，比如長度，密度都是連續值，無法在ID3運用。這大大限制了ID3的用途。

2.ID3採用信息增益大的特徵優先建立決策樹的節點。很快就被人發現，在相同條件下，取值比較多的特徵比取值少的特徵信息增益大。比如一個變數有2個值，各為 ，另一個變數為3個值，各為 ，其實他們都是完全不確定的變數，但是取3個值的比取2個值的信息增益大。（信息增益反映的給定一個條件以後不確定性減少的程度,必然是分得越細的數據集確定性更高,也就是條件熵越小,信息增益越大）如河校正這個問題呢？為了解決這些問題我們有了C4.5演算法。

對於第一個問題，不能處理連續特徵， C4.5的思路是將連續的特徵離散化。比如m個樣本的連續特徵A有m個，從小到大排列為 。則C4.5取相鄰兩樣本值的平均數，一共取得m-1個劃分點，其中第i個劃分點 表示為： 。對於這m-1個點，分別計算以該點作為二元分類點時的信息增益。選擇信息增益最大的點作為該連續特徵的二元離散分類點。比如取到的增益最大的點為 ，取大於 為類別1，小於 為類別2。這樣我們就做到了連續特徵的離散化。

對於第二個問題，信息增益作為標准容易偏向於取值較多的特徵。C4.5中提出了信息增益比：

即特徵 的對數據集 的信息增益與特徵 信息熵的比，信息增益比越大的特徵和劃分點，分類效果越好。某特徵中值得種類越多，特徵對應的特徵熵越大，它作為分母，可以校正信息增益導致的問題。

回到上面的例子：

 

同樣可得：  ， 。

因為F具有最大的信息增益比，所以第一次分裂選擇F為分裂屬性，分裂後的結果圖3表示。

再遞歸使用這個方法計運算元節點的分裂屬性，最終就可以得到整個決策樹。

看完上述材料，我們知道在ID3演算法中我們使用了信息增益來選擇特徵，信息增益大的優先選擇。在C4.5演算法中，採用了信息增益比來選擇特徵，以減少信息增益容易選擇特徵值種類多的特徵的問題。但是無論是ID3還是C4.5,都是基於資訊理論的熵模型的，這裡面會涉及大量的對數運算。能不能簡化模型同時也不至於完全丟失熵模型的優點呢？有！CART分類樹演算法使用基尼系數來代替信息增益比，基尼系數代表了模型的不純度，基尼系數越小，則不純度越低，特徵越好。這和信息增益(比)是相反的。

在分類問題中，假設有 個類別，第 個類別的概率為 ,則基尼系數為：

對於給定的樣本 ，假設有 個類別，第 個類別的數量為 ，則樣本的基尼系數為:

特別的，對於樣本D,如果根據特徵A的某個值a,把D分成D1和D2兩部分，則在特徵A的條件下，D的基尼系數為：

回到上面的例子：

同理得： ， 。

因為L具有最小的基尼系數，所以第一次分裂選擇L為分裂屬性。

再遞歸使用這個方法計運算元節點的分裂屬性，最終就可以得到整個決策樹。

小夥伴們如果覺得文章還行的請點個贊呦！！同時覺得文章哪裡有問題的可以評論一下  謝謝你！

③ 決策樹（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

④ 求信息熵的計算方法!!

H(x)=lb，應該是求平均互信息熵。

熵的計算

⑤ 聚類演算法（上）06

這篇文章的整體排版主要是根據個人的博客來噠，如果感興趣的話可以去我的自己搭建的個人博客看這篇 文章 。

聚類演算法很多，所以和講回歸演算法一樣，分成了上下，上中主要講了傳統的K-Means演算法以及其相應的優化演算法入K-Means++，K-Means||和Canopy等。下中主要講了另外兩種的思路的聚類演算法，即層次聚類和密度聚類。

聚類算就是懟大量未知標注的數據集，按照數據 內部存在的數據特徵 將數據集 劃分為多個不同的類別 ，使類別內的數據比較相似，類別之間的數據相似度比較小，屬於 無監督學習 。

從定義就可以看出，聚類演算法的關鍵在於計算樣本之間的 相似度 ，也稱為 樣本間的距離 。

說到聚類演算法，那肯定核心就是計算距離的公式了，目前常用的有以下幾種。
閔可夫斯基距離（Minkowski） ：公式2.1

KL距離（相對熵） ：
思考下條件熵的定義，簡單的來說就是在放生一件事情的時候，發生另一件事的概率。公式如下公式2.7.
註：這里書的概率不是實指概率，而是熵表達的含義。這個公式其實就是條件熵的公式。

傑卡德相似系數(Jaccard) ：
這個很好理解，它的核心就是使用兩個集合的交集和並集的比率來代表兩者的相似度，也就是說重合的越多越相似。公式如下，公式2.8.

Pearson相關系數 ：
這個就是考研數學中的相關系數，表達就是兩者之間的想關系，所以直接拿來用就好了，公式如下公式2.9。

給定一個有M個對象的數據集，構建一個具有k個簇的模型，其中k<=M。滿足 以下條件:

基本思想:
對於給定的類別數目k，首先給定初始劃分，通過迭代改變樣本和簇的隸屬關系，使的每次處理後得到的劃分方式比上一次的好，即 總的數據集之間的距離和變小了

K-means的核心演算法如下：

再循環中的第二步，我們移動了中心點的位置，把中心點移到了隸屬於該中心點類別的所有樣本的中間，並使用樣本的均值作為位置。這樣子看似是拍腦袋想的移動策略，其實是可以推導出來的。正如聚類演算法思想所指出的，我們要讓所有的點到自己的分類的中心點的歐幾里得距離最小，所以我們設置目標放稱為公式4.1，公式中的1/2是為了之後求導運算方便。我們為了讓目標函數盡可能的小，所以使用了之前一直在使用的思考方式，對其使用梯度下降演算法，求導後得到公式4.2，之後令其等於0，就得到了公式4.3。

最後這個看似不錯的演算法，其實有著不小的缺點，那就是 初值敏感 。我們來仔細想一想，如果兩個不小心隨機生成的初值落到了一個類別中，兩者的距離還特別近，這中情況下就很難正確分類了。除此之外，由於移動策略中使用的是均值，也就是說如果集合中含有非常大的誤差點的話，這樣子會是中心點的設置偏離正確點很遠，所以很多時候我們改用 中值來更新中心點 ，這就是我們說的K-Mediods聚類，即K中值聚類。

總結下K-means演算法
優點：

由於K-Means對初始中心點非常敏感，我們這里就嘗試著通過二分法弱化初始中心點。這種演算法的具體步驟如下：

我們在這個演算法中提到了SSE，這個可以是簇內所有樣本點，到其中心點的距離的總和，代表著簇內的點是不是高度相關。計算公式如下公式4.4。

可以看出在這種演算法下，很好的避開了，兩個中心點都在一起的情況。

K-Means++做的改善，是直接對初始點的生成位置的選擇進行優化的，他的初始點生成策略如下：

Canopy屬於一種「粗略地」聚類演算法，簡單的來說就是，不那麼追求自動獲得最優解，而是引入了一種人為規定的先驗值進行聚類，具體步驟如下：

註：Canopy演算法得到的最終結果的值，聚簇之間是可能存在重疊的，但是不會存在 某個對象不屬於任何聚簇的情況
顯然，這種演算法雖然快，但是很難生成滿足我們應用的模型，所以通常我們將它作為解決K-Means初值敏感的方案，他們合在一起就是Canopy+K-Means演算法。
順序就是先使用Canopy演算法獲得K個聚類中心，然後用這K個聚類中心作為K-Means演算法。這樣子就很好的解決了K-Means初值敏感的問題。

Mini Batch K-Means演算法是K-Means演算法的一種優化變種，採用小規模的數據子集，來減少計算時間。其中採用小規模的數據子集指的是每次訓練使用的數據集是在訓練演算法的時候隨機抽取的數據子集。Mini Batch K-Means演算法可以減少K-Means演算法的收斂時間，而且產生的結果效果只是略差於標准K-Means演算法。
它的演算法步驟如下：

聚類演算法的衡量標准有很多，包括均一性、完整性、V-measure、調整蘭德系數（ARI ，Adjusted Rnd Index）、調整互信息(AMI，Adjusted Mutual Information)以及輪廓系數等等。

均一性：一個簇中只包含一個類別的樣本，則滿足均一性。其實也可以認為就是正確率，即每個聚簇中正確分類的樣本數占該聚簇總樣本數的比例和。其公式如下公式5.1。

完整性：同類別樣本被歸類到相同簇中，則滿足完整性。每個聚簇中正確分類的樣本數占該類型的總樣本數比例的和，通俗的來說就是，我們已分類類別中，分類正確的個數。
其公式如下，公式5.2：

在實際的情況中，均一性和完整性是往往不能兼得的，就好像抓特務時的矛盾一樣，到底是保證每個抓的人都是特務，還是寧可錯抓也不放過一個特務，之間的取捨很難把握。所以再一次貫徹，魚和熊掌不可兼得，我們就加權，於是得到的就是V-measure，其公式如下公式5.3：

蘭德系數（RI，Rand index） ，我用中文看了不少講蘭德系數的博客，其中的文字說明幾乎都是相同的，對個人的理解幫助不是特別大，於是用英文查的。最終理解了這個系數的參數的意思，想看英文說明的，個人覺得還挺好懂的參考 這里 。以下是我個人的講解。

首先，將原數據集中的元素進行兩兩配對形成一個新的數據集，我們稱之為S數據集。這時候，我們將原數據集，根據兩種不同的策略分別劃分成r份和s份，並對這兩個數據集命名為X和Y。在這里我們可以看出，X和Y的元素是相同的，只是他們的劃分方式不同。
接下來我們來思考，S數據集中，每個元素中的兩個樣本，在X和Y中只有兩種可能，就是兩個樣本都在一個子集中，或者不在一個子集中，那麼對於S中的一個元素，只有四種可能性。

接下來引入， 調整蘭德系數(ARI，Adjusted Rnd Index) ，ARI取值范圍 ，值越大，表示聚類結果和真實情況越吻合。從廣義的角度來將，ARI是衡量兩個數據分布的吻合程度的，公式5.5如下：

調整互信息，整體的流程很像ARI，AMI則是對MI進行調整。而MI是使用信息熵來描述的。那麼互信息表示了什麼呢，首先先看下 維基網路的定義 ：

之前我們說到的衡量指標都是有標簽的，這里的輪廓系數則是不包含標簽的評價指標。