(Day 26) 最小生成樹 (Minimum Spanning Tree)
在前幾天,我們學習了最短路徑問題 (Shortest Path),例如 Dijkstra、Bellman-Ford、Floyd-Warshall、A*,今天要介紹的則是圖論中的另一個核心問題 —— 最小生成樹 (Minimum Spanning Tree, MST)
在前幾天,我們學習了最短路徑問題 (Shortest Path),例如 Dijkstra、Bellman-Ford、Floyd-Warshall、A*,今天要介紹的則是圖論中的另一個核心問題 —— 最小生成樹 (Minimum Spanning Tree, MST)
在前幾天,我們介紹了 Dijkstra、Bellman-Ford、Floyd-Warshall,這些都是經典的最短路徑演算法。今天要談的是 A* 搜尋演算法 (A-star Search) —— 一個結合最短路徑與啟發式 (Heuristic) 的演算法,在人工智慧 (AI)、遊戲與導航中應用極為廣泛
在前兩天我們分別介紹了 Dijkstra 與 Bellman-Ford ,它們都解決的是 單源最短路徑 (Single Source Shortest Path, SSSP) 問題。今天要介紹的是 Floyd-Warshall 演算法 —— 一個能計算 所有點對 (All-Pairs Shortest Path, APSP) 的演算法
在前一天我們介紹了 Dijkstra 演算法,它能有效解決 單源最短路徑 (Single Source Shortest Path, SSSP) 問題,但有一個限制: 不能處理負權重邊 (Negative Weights)。然而,現實世界的很多問題 (例如金融套利、債務網路、價格波動) 都可能出現負權重,這時候我們就需要 Bellman-Ford 演算法。
Dijkstra 最短路徑演算法是一種用於計算從單一源點到圖中所有其他節點的最短路徑的經典演算法。這個演算法適用於加權圖,其中邊的權重必須是非負的,核心思想是每次選擇「距離起點最近」的尚未處理節點,並用它來更新鄰居的最短距離,這種策略屬於貪心演算法 (Greedy Algorithm)
自從我們 Day 10 簡單地說一下圖結構後,就再也沒提到這個詞,我們今天開始就要介紹這個應用非常廣泛的圖 (Graph) 的演算法總覽,後續會接著介紹常見的圖演算法,因為圖是非線性資料結構中最重要的一員,在學術研究與實務應用上都有極高地位,從網路連線、地圖導航、社交網路到金融交易,幾乎都離不開圖的建模與演算法
貪婪演算法 (Greedy Algorithm) 是一種在每一步選擇中都採取在當前狀態下最好或最優 (即最有利) 的選擇,從而希望導致結果是全局最好或最優的演算法。這種方法每次做出選擇時,只考慮當前最優解,而不考慮未來的後果
動態規劃 (Dynamic Programming; DP) 是一種將複雜問題分解為較小子問題,並儲存子問題解以避免重複計算的演算法設計方法。它常用於具有「重疊子問題」和「最優子結構」性質的問題
前面介紹了幾個簡單又常見的排序與搜尋的演算法,接下來我們來談談演算法設計策略,仿間有很多演算法的書並不會特地把 Divide and Conquer 或 Dynamic Programming 編成一個章節,這也導致新手學完了一些演算法後,不知道自己學的是 Divide and Conquer 或 Dynamic Programming,這也包括我,所以我們在來花幾天的時間來談談這些演算法設計策略。
內插搜尋法 (Interpolation Search) 是一種基於數值分布估算落點的搜尋演算法,是對 二元搜尋 (Binary Search) 的改良。它特別適合用在已排序且元素分布相對均勻的資料集上,能有效地減少搜尋次數。
在排序演算法之後,我們終於要介紹一個非常經典且實用的搜尋演算法 —— 二元搜尋 (Binary Search)。如果說排序演算法是「把資料整理好」,那麼搜尋演算法就是「如何在整理好的資料中快速找到想要的元素」。二元搜尋憑藉著「折半」的概念,將搜尋的時間複雜度大幅降低。
在前面三天,我們分別介紹了氣泡排序 (Bubble Sort)、選擇排序 (Selection Sort)、插入排序 (Insertion Sort)。這三個演算法都是經典的「基礎排序」,時間複雜度同樣是 $O(n^2)$,但它們在設計思路、操作方式、適用場景上各有不同。今天我們就來做一次系統化的分析比較。
插入排序 (Insertion Sort) 也是一種簡單直觀的排序演算法。它的工作原理是通過構建有序序列,對於未排序資料,在已排序序列中從後向前掃描,找到相應位置並插入。
選擇排序 (Selection Sort) 是一種簡單直觀的排序演算法。核心概念: 每一輪從尚未排序的元素中挑出最小(或最大)者,放到目前應在的位置,一直重複直到完成。可以把它想成「選拔賽」: 第一輪選出最優放第一名,第二輪從剩下的人選次優放第二名,依此類推。
終於進入演算法的部分,預計會介紹 3~4 個很常見的排序演算法,所以光排序這個主題就會用掉 3~4 天的篇幅,今天除了介紹 Bubble Sort 外,會先簡單介紹一下排序,讓各位讀者更好地認識排序演算法。
到目前為止,我們已經介紹了各種資料結構 (Array、Linked List、Stack、Queue、Tree、Graph),也練習了基本操作。但光有資料結構還不夠,要能設計演算法,就必須懂得如何評估一個演算法的效率。
這是資料結構的最後一篇,明天開始進入本系列的重點驗算法,前面幾天,我們介紹了各種樹結構 Binary Tree、Balanced Tree,以及其他衍生樹。而樹是一種特殊的圖結構,今天我們正式進入 Graph 的世界。
在前面兩天,粗淺的介紹了 Binary Tree 與 Balanced Tree,今天更粗淺的介紹一下其他樹,因為本系列只是要做一個拋磚引玉的動作,如果讀者對於資料結構有興趣,建議可以買書來研讀。
Balanced Tree 是一種特殊的二元樹結構,旨在保持樹的高度盡可能低,以提高操作效率。常見的平衡樹包括 AVL 樹、紅黑樹和 B 樹等。以下是關於平衡樹的詳細介紹。
前面幾天所介紹的資料結構就是線性的資料結構,今天開始所介紹的樹資料節構是屬於非線性資料結構,也非常的重要。
Queue (佇列) 與 Stack 一樣,是一種線性資料結構,但它遵循的是先進先出 (First-In-First-Out; FIFO) 的規則。你可以把 Queue 想像成排隊買票: 最早排隊的人會最先買到票並離開,而新加入的人只能站在隊伍最後。
Stack (堆疊) 是一種受限的線性資料結構,遵循先進後出 (Last-In-First-Out; LIFO) 的資料結構。你可想像有一疊盤子,最後放上去的盤子會最先被拿走,所以 Stack 只允許在「頂端」進行操作,簡單來說就是你不能看或是取非最上層的元素。
Linked List (鏈表) 是一種常見的資料結構,用來儲存一系列的元素。與陣列 (Array) 不同,Linked List 的元素稱為節點 (Node) 在記憶體中不必是連續的。每個節點除了儲存資料外,還會儲存一個指向下一個節點的參考 (指標)。
前陣子在一個群組裡,我看到一個案例。一位年僅 19 歲的年輕人,沒有繼續升學,而是直接進入一家小型乙方軟體公司工作。他對此洋洋自得,甚至把「不讀書」當成一種優越感,強調「讀書無用」,彷彿他提早進入職場就是成功的證明。
我不知道大家看到這天會不會驚訝一下,不是應該接續鏈表 (Linked List) 這是什麼? Matrix 就是 Array 只是我單獨抽出來說明,如果你沒有在學習或處理資料科學相關的,應該不會使用到 Matrix,但是我認為這是一個蠻常被忽略的部分,也就花一點篇幅來介紹它。
Array 是一種 Static Data Structure 或稱為 Dense List,它是一種將有序串列的資料結構使用 Contiguous Allocation 來儲存,意味著儲存的元素必須是相同類型,且靜態資料結構的記憶體配置是在編譯時,就必須配置給相關的變數,因此在創建時必須先宣告空間大小。
我遇過很多學習程式語言的人,都一直學框架或是 API 怎麼用,都不是很注重底層的知識,我認為一棟樓要蓋多高取決於地基打得多深,因為框架與 API 會變,但時間複雜度、記憶體模型、資料結構設計是不會變的。
終於來到這個系列的最後一天。老實說,如果要我替這 30 天打個分數,我大概只會給自己一個 勉強及格。原因很簡單: 這個系列從一開始就有宏大的規劃與期待,但在實際執行的過程中,遭遇了不少現實挑戰,也暴露了自己在知識深度、寫作規劃與時間管理上的不足。
在前一天,我們介紹了 Seq2Seq 架構 (Encoder-Decoder),它將輸入序列壓縮成一個固定維度的上下文向量 (Context Vector),再交由解碼器 (Decoder) 逐步生成輸出。這種方法為機器翻譯、摘要生成等任務帶來了突破,但它也有一個致命的缺陷——瓶頸效應 (Bottleneck Problem)。
在前幾天的文章中,我們依序介紹了 RNN、LSTM、GRU,並討論它們如何建模序列資料。這些模型能夠捕捉序列中的上下文關係,並緩解傳統 RNN 的梯度消失問題。然而,若我們想要處理更複雜的任務——例如機器翻譯 (Machine Translation),僅僅依靠單向 RNN 或 LSTM 並不夠。
在前兩篇文章,我們分別介紹了 RNN (Recurrent Neural Network) 與 LSTM (Long Short-Term Memory)。RNN 為序列建模提供了基礎架構,但受限於梯度消失與爆炸問題,難以捕捉長距離依賴;LSTM 則透過引入 記憶單元 (Cell State) 與 門控機制 (Gating Mechanism),成功緩解了這一問題。
在前一篇,我們介紹了循環神經網路 (RNN),並指出了它在處理序列資料時的強大之處:透過「隱藏狀態」將前後資訊連結起來。然而,我們同時也看到了 RNN 的最大瓶頸——梯度消失與梯度爆炸,使得它在長距離依賴 (long-term dependency) 的學習上表現不佳。
在前面幾天,我們介紹了全連接神經網路 (FCNN) 與卷積神經網路 (CNN)。這些架構在處理結構化數據或影像資料上非常成功,但若應用到「序列資料」時就顯得不足。
在前一天,我們整理了深度學習中常見的優化方法,從最基本的隨機梯度下降 (SGD),到 Momentum、RMSProp、Adagrad 等。今天我們要深入介紹其中最具代表性、也是實務中最常見的優化方法之一——Adam (Adaptive Moment Estimation)。
在前一篇,我們談到了深度學習中的正規化與正則化,重點在於如何避免過擬合並保持訓練穩定。然而,光是解決過擬合還不夠:在龐大的神經網路裡,我們還得面對另一個關鍵問題——如何有效率地找到參數的最佳解。
在前幾天的文章裡,我們已經從線性迴歸、邏輯迴歸一路走到 CNN (卷積神經網路),逐步體驗了機器學習與深度學習的不同。到了深度學習階段,模型的複雜度往往大幅增加,參數數量動輒上百萬甚至上億,這也帶來了一個非常嚴重的問題: 過擬合 (Overfitting)。
在初步暸解全連接神經網絡 (Fully Connected Neural Network) 後,接下來必須介紹的經典架構就是卷積神經網絡 (Convolutional Neural Network; CNN)。卷積神經網絡可以說是深度學習的代表性架構之一,特別是在電腦視覺 (Computer Vision) 領域幾乎無處不在。
承接昨天的神經元 (Neuron),神經元的輸出是線性輸出,若僅停留在這個階段,輸出仍然是線性函數,即便我們把很多神經元堆疊在一起,整體模型仍然等效於一個線性轉換,無法捕捉到真實世界中複雜的非線性關係為了解決這個問題,我們需要引入激活函數 (Activation Function) 可以讓模型學習到更複雜的模式 (非線性),所以激活函數必須是非線性的,這樣才能跟神經元做搭配。
前一篇我們先介紹了全連接神經網絡 (Fully Connected Neural Network),相信大家還是不太清楚這是什麼,接下來會用幾天的篇幅一一介紹相關的專有名詞,若要理解神經網路,必須先從最小的組成單位 —— 神經元 (Neuron) 開始。
在進入深度學習的第一步,必須要先認識最基礎的深度學習架構,這個架構稱為: 全連接神經網路 (Fully Connected Neural Network; FCNN)、多層感知機 (Multi-Layer Perceptron; MLP) 這兩個都是指同一個東西,這個架構也是所有深度學習架構的基石,CNN、RNN、Transformer 都可以看作是在 FCNN 上加入特殊結構與限制後的延伸
我們機器學習的部分還有 XGBoost、PCA、OneClass SVM 都還沒有談,只是篇幅限制,原本規劃深度學習大概就要花 15 篇左右的內容來談談,如果後續有篇幅我再補充。
今天本來要說極限梯度提升數 (XGBoost),但是我發現後面的篇幅可能快不夠了,今天開始的內容會調整成,無監督式學習 → 深度學習 → 如果有時間再回來補充 One-Class SVM 跟 XGBoost。
隨機森林是以「多棵弱學習器 (決策樹)」為基底的集成學習 (Ensemble) 方法,透過資料抽樣 (Bagging) 與特徵隨機子抽樣 (Random Subspace) 降低單棵樹的方差與不穩定性。直覺上,它像是一群專家各自投票: 每位專家 (樹) 看見的資料與特徵都不完全相同,最後以多數決 (分類) 或平均 (回歸) 給出更穩健的預測。
Decision Tree 是一種基於條件分支的監督式學習模型,可用於分類與回歸任務。它透過一連串的「是/否」判斷,將資料不斷切分成更純淨的子集,最終形成一個由節點 (Nodes) 與邊 (Edges) 組成的樹狀結構。直覺上,你可以將它想成一連串的決策問句:「乘客的性別是女性嗎?」 → 是 → 「年齡是否小於 12 歲?」 → 是 → 存活機率高。其最大特色是 可解釋性高,每個決策規則都能清楚對應到特徵與閾值,便於與非技術背景的利害關係人溝通。
分類任務有混淆矩陣作為指標的核心基礎,迴歸任務則建立在誤差分佈 (Error Distribution) 之上。所有迴歸指標,都是在真實值與預測值的差異上進行數學運算。迴歸的評估相對分類簡單,沒有多種 TP、FP 的組合,但每個指標關注的面向、對異常值的敏感度、在商業決策上的意義卻各有不同。
多元分類任務驗證指標就只是從二元分類任務驗證指標延伸而來,核心概念一樣是二元分類任務驗證指標,而兩者只是在計算內容上有些許差異,所以指標仍然是 Accuracy、Recall、F1-score 等,所以請讀者先將二元分類任務驗證指標熟練後再來看。
今天要介紹的是常見的分類任務驗證指標,會以二元分類問題為例,因為多元分類也是用相同的指標,只是計算方式會有所不同而已,預計會用 2-3 天的篇幅介紹完,分類與迴歸任務的驗證指標;先給各位讀者一個正確的觀念,選指標時必須回到業務背景與資料特性,不要迷信某個數值越高越好,真正有價值的模型評估,是能在技術表現與業務需求之間找到平衡。
終於來到 SVM,這也是本系列介紹 Machine Learning 中分類演算法的最後一個,當然在機器學習中還有很多的監督式分類演算法,我個人認為相對沒我介紹的這幾個經典,就留給讀者自行學習。從明天開始到進入樹模型之前,我會補充一下,模型 Validation Index 的內容 (用來衡量模型結果好不好),因為前面飆的有點快,後來有發現這部分也很重要,預計會花 2 ~ 3 天的篇幅來介紹。
前幾天的討論中,我們已經探討了迴歸分析、邏輯迴歸,以及最近兩天介紹的 K-Nearest Neighbors (KNN)。今天要討論的是另一種基礎且直覺性極強的分類演算法: 樸素貝氏分類器 (Naive Bayes Classifier)。儘管樸素貝氏分類器的基本原理非常簡單,甚至經常被視為基礎模型,但在實務應用中,它仍然是許多場合的首選,尤其是在文本分類領域,例如垃圾郵件分類與情感分析。
K-近鄰 (K-Nearest Neighbors; KNN) 是一種很直學的機器學習演算法。它沒有模型參數、沒有訓練過程,卻可以在某些任務上有不錯的效果。它的核心理念只有一句話: 「你是誰,由你周圍最像你的人決定」。
前面 5 天我們聚焦於「回歸系列」模型: 線性迴歸 (Linear Regression)、多項式迴歸 (Polynomial Regression)、正則化迴歸 (Lasso / Ridge / ElasticNet Regression) 以及邏輯迴歸 (Logistic Regression)。雖然它們名稱上都掛著「Regression」,實則涵蓋了連續值預測與分類任務兩大主題。
在上一篇中,我們深入介紹了邏輯迴歸的模型邏輯、損失函數與分類行為。這篇則要進一步延伸這個經典模型,回答一個關鍵問題: 邏輯迴歸能否結合多項式特徵與正規化機制,來對抗非線性與過擬合問題?
邏輯迴歸 (Logistic Regression) 是一種常見的分類模型,主要用於預測二元分類或多元分類,有別於先前的線性迴歸是用來預測無邊界的連數據值,而邏輯迴歸間單來說就是預測有邊界的不連續數值,如 [0, 1], [1, 2, 3]。
延續昨日的多項式迴歸中,我們觀察到一個現象: 雖然二次特徵提升了模型的表現,但同時也引入過擬合 (Overfitting) 風險。這是因為當特徵數量暴增,模型就會變得過於「貪婪」,試圖將每個資料點都擬合得極好,結果反而喪失了在新資料上的泛化 (Generalization) 能力。
昨天介紹了線性迴歸 (Linear Regression),它適合用來處理特徵與目標之間為線性關係的情境。然而,真實世界的資料往往並非純粹線性,而是呈現複雜的非線性關係,例如曲線、拋物線、甚至更複雜的波動趨勢。
線性迴歸 (Linear Regression) 是統計學中的一種預測方法,主要分為簡單線性迴歸 (Simple Linear Regression) 與多元線性迴歸 (Multiple Linear Regression),又稱複迴歸,以及其他變形的迴歸等,但在線性迴歸中,通常會有 1~N 個自變數 (Independent Variable) X,也可以稱作特徵 (Feature);和 1 個因變數 (Dependent Variable) Y,也可以稱作目標 (Target)。而最終目的就是找出一條最佳迴歸線,來擬合這些數據點,便可以用來預測未來的數據點。
在學習機器學習 (Machine Learning) 的過程中,可能會陷入兩種極端,一種是只會調用套件 (套模),模型背後的機制一知半解,遇到問題只能「換模型試試看」,或者是過度陷入數學細節,花大量時間推導公式,卻無法轉化為實際應用與模型選擇能力。
近年來,我觀察到無論在台灣還是中國,「學歷無用論」的聲音愈發強烈。許多人開始質疑讀書是否還有意義,認為不靠學歷反而更能致富,網紅、直播、投資客、白手起家的商人充斥版面,讀書人反倒被視為落後者、被剝削者、社會規訓的犧牲品,但我有不同的看法。
這是一個資料科學專案,目標是透過 Kaggle 經典的 Titanic 生存預測題目,建立一套結構清晰、模組化的預測系統。我不只是想交出一份準確的預測結果,更希望藉由這個專案練習
最近,我正在參加一門職訓課程。本來對這堂課滿懷期待,尤其是對某位老師的專業背景很感興趣。不過,隨著課程進行,我漸漸感到一股說不出的落差感:每當我主動提出深入問題,收到的回信卻幾乎都像是 ChatGPT 生成的答案——格式漂亮、邏輯完整、語氣中立,但就是少了「人味」與「針對性」。
在資料科學領域中,對企業進行舞弊檢測 (Fraud Detection) 被視為是一種分類問題: 輸入企業相關的數據,輸出舞弊或非舞弊。然而,真正投入研究後會發現,這個問題很難解決,非常具挑戰性。
五年前,我踏入壽險產業,成為一名 Business Analyst (BA)。當時的工作內容相當清晰: 需求文件撰寫、報表製作、簡單的數據分析與溝通協調,是我每天的日常。那時候,這些任務仍需靠人力一項一項完成,效率與品質全憑個人經驗與熟練度。但如今,這些「核心能力」正快速被人工智慧工具重塑,甚至取代。
這是一個資料視覺化專案——「Dynamic Visualization: 200 Countries, 200 Years, 4 Minutes」。它將涵蓋 1816 至 2016 年,200 個國家的歷史變遷以互動動畫呈現,整體動畫長度約四分鐘,旨在結合「時間」與「地理」維度,提供用戶沉浸式的歷史視覺體驗。