(Day 26) 最小生成樹 (Minimum Spanning Tree)
在前幾天,我們學習了最短路徑問題 (Shortest Path),例如 Dijkstra、Bellman-Ford、Floyd-Warshall、A*,今天要介紹的則是圖論中的另一個核心問題 —— 最小生成樹 (Minimum Spanning Tree, MST)
多元分類任務驗證指標就只是從二元分類任務驗證指標延伸而來,核心概念一樣是二元分類任務驗證指標,而兩者只是在計算內容上有些許差異,所以指標仍然是 Accuracy、Recall、F1-score 等,所以請讀者先將二元分類任務驗證指標熟練後再來看。
假設我們有 3 個類別 [A, B, C],模型的預測結果如下:
實際 \ 預測 | A | B | C |
---|---|---|---|
A | 50 | 2 | 3 |
B | 4 | 45 | 1 |
C | 5 | 2 | 43 |
對單一類別 (One-vs-All),例如要計算「類別 A」的指標:
這樣每個類別都能得到對應的 TP、FP、FN、TN
對於 A 類別:
$$ \text{Precision}_{A} = \frac{TP_A}{TP_A + FP_A} = \frac{50}{50 + 9} \approx 0.847 $$
$$ \text{Recall}_A = \frac{TP_A}{TP_A + FN_A} = \frac{50}{50 + 5} \approx 0.909 $$
$$ \text{F1}_A = 2 \times \frac{Precision_A \times Recall_A}{Precision_A + Recall_A} \approx 0.877 $$
B, C 類別同理計算
因為多元分類有多個 Precision、Recall、F1,我們需要做彙總。常見的方法:
Macro Average
直接對每個類別的指標取平均
每個類別權重相等,適合類別數據量差異不大時
$$ \text{Macro-Precision} = \frac{\sum_{i=1}^k \text{Precision}_i}{k} $$
Weighted Average
依照每個類別的樣本數加權平均
適合類別不平衡情況
$$ \text{Weighted-Precision} = \frac{\sum_{i=1}^k (\text{Precision}_i \times \text{support}i)}{\sum{i=1}^k \text{support}_i} $$
其中 $\text{support}_i$ = 該類別的樣本數
Micro Average
$$ \text{Accuracy} = \frac{\sum_{i=1}^k TP_i}{\text{全部樣本數}} $$
其實就是混淆矩陣對角線數字的總和 / 全部樣本數。 在例子中:
$$ \text{Accuracy} = \frac{50 + 45 + 43}{50 + 2 + 3 + 4 + 45 + 1 + 5 + 2 + 43} = \frac{138}{155} \approx 0.890 $$