滑動窗口 (Sliding Window)

 滑動窗口 (Sliding Window) 的核心概念：

想像一下，你有一長串的珠子（代表數據，例如數字、文字、時間序列的量測值等等）。你現在有一個固定長度的框框（代表窗口）。你可以將這個框框放在珠子的開頭，然後逐步地將這個框框向右移動一個或多個位置，每次移動後，你都會觀察或處理框框內的珠子。這個移動的框框就是「滑動窗口」。

在演算法設計中的應用：

滑動窗口是一種非常有用的演算法技巧，尤其在處理陣列、字串或串列等循序資料時，可以有效地降低時間複雜度。

• 固定大小的滑動窗口： 窗口的大小在滑動的過程中是固定的。這種方法常用於解決以下問題：

  • 尋找固定大小子陣列的最大/最小值/總和： 例如，給定一個數字陣列和一個數字 k，找出所有長度為 k 的子陣列中，總和最大的那個。使用滑動窗口，我們只需要遍歷一次陣列，維護一個大小為 k 的窗口，並在窗口滑動的過程中更新總和，而不需要使用巢狀迴圈。
  • 尋找字串中符合特定條件的子字串： 例如，找出一個字串中最長的不重複字元子字串。我們可以維護一個滑動窗口，並根據窗口內字元的重複情況來調整窗口的左右邊界。

• 可變大小的滑動窗口： 窗口的大小在滑動的過程中可以根據條件擴大或縮小。這種方法常用於解決以下問題：

  • 尋找總和等於特定值的最小子陣列： 我們可以維護一個滑動窗口，如果窗口內的元素總和小於目標值，則擴大窗口的右邊界；如果總和大於等於目標值，則縮小窗口的左邊界，並記錄滿足條件的最小窗口大小。
  • 尋找滿足特定字元條件的最小/最大子字串： 例如，找出一個字串中包含所有指定字元的最短子字串。我們可以擴大窗口直到包含所有目標字元，然後嘗試縮小窗口的左邊界，直到不再滿足條件。

在機器學習中的應用：

滑動窗口在機器學習領域也有多種應用：

• 時間序列預測： 對於時間序列資料（例如股票價格、溫度變化），我們可以使用滑動窗口來創建訓練樣本。一個固定長度的過去時間序列數據窗口作為模型的輸入，而窗口之後的一個或多個時間點的數據作為模型的輸出（預測目標）。窗口會隨著時間的推移而滑動，產生多個訓練樣本。窗口的大小（考慮多少歷史數據）和滑動的步長（每次滑動多少時間單位）是重要的超參數。
• 圖像中的目標檢測（早期方法）： 在深度學習方法普及之前，目標檢測常常使用滑動窗口技術。一個固定大小的窗口在整張圖片上滑動，並在每個位置使用分類器判斷窗口內是否包含感興趣的目標。為了檢測不同大小的目標，通常會使用多個不同尺寸的滑動窗口。現在這種方法由於效率問題已被更先進的方法取代。
• 神經網路中的注意力機制： 在一些先進的神經網路架構（例如 Transformer）中，會使用「滑動窗口注意力」。與讓序列中的每個元素都關注所有其他元素不同，滑動窗口注意力只允許每個元素關注其周圍固定大小窗口內的元素。這可以降低處理長序列時的計算成本。
• 資料預處理和特徵工程： 對於時間序列資料，可以使用滑動窗口計算各種統計特徵，例如移動平均、標準差等。這些基於窗口計算的特徵可以作為機器學習模型的輸入。
• 滑動窗口驗證： 對於時間相關的資料，可以使用滑動窗口進行模型驗證。資料被分成連續的窗口，一個窗口用於訓練，後續的窗口用於測試，確保模型總是在時間上未見過的數據上進行評估。

總結來說，滑動窗口是一種有效處理循序或空間資料的技術，它通過在資料上移動一個固定或可變大小的窗口，並在每個窗口位置執行特定的操作，來實現對局部資料的分析和處理。 這種技術在演算法設計中可以優化時間複雜度，而在機器學習中則用於處理時間序列、圖像等資料，進行特徵提取、模型訓練和評估。