【菜狗每日記錄】啟發式算法、傅里葉變換、AC-DTC、Xmeans

🐱1、啟發式算法

① 定義

② 特點

③ 案例

🐱2、快速傅里葉變換FFT

① DFT離散傅里葉變換

② FFT快速傅里葉變換

🐱3、AC-DTC聚類

🐱4、Xmeans

🐱1、啟發式算法

????????啟發式算法是和最優化算法相對的。

????????一般而言，最優化算法所需要解決的問題，都能分成三個部分：

目標：什么是目標呢？簡單點說就是要優化的東西，比如運籌學的背包問題中，要優化的就是所選物品的價值，使其最大。
決策：顧名思義就是根據目標所作出的決策，比如在這里就是決定選取哪些物品裝進我們的背包。
約束：那么何又為約束呢？就是說再進行決策時必須遵循的條件，比如上面的背包問題，我們所選取的物品總的重量不能超過背包的容量。要是沒有容量的約束，小學生才做選擇呢，我全都要！

????????在求最優解過程中，啟發式策略可依個體或全局經驗調整搜索路徑，當求最優解困難時，它是高效得可行解的方法。這種算法主要用于解決NP-hard問題，NP即非確定性多項式。

① 定義

? ? ? ? 基于直觀、經驗構造的算法，在一定成本下給出可以解決優化問題的一個可行解。主要以仿自然算法為主。

????????遺傳算法，模擬退火，各種群算法，蟻群，魚群，粒子群，人工神經網絡等模仿自然界或生命體行為模式的算法，一般又稱人工智能算法或全局優化算法。

② 特點

幫助尋求答案，告訴怎么去找，知道路怎么走，不知道路往哪里走。
結果具有偶然性，過程具有啟發性，像是問路的過程中了解更多目的地相關的內容。（這里感覺很像人生，一直在路上，不斷尋找自己想要追求的。）

③ 案例

通俗理解啟發式算法 - 知乎

????????最終目標：爬上最高的山峰。

爬山法：一個人往更高的地方走，會變更高，但是那座山不一定是珠穆朗瑪峰。
模擬退火：一個人喝醉了，隨機跳了很長時間，可能變高可能變低，但是慢慢朝更高的地方走。
禁忌搜索：很多人，互相轉告哪個地方的山已經去了，留下一個人做記號，制定了下一步往哪里找的策略。
遺傳算法：人活在地球，不知道自己要干什么，過幾年就會殺死低海拔的土地上的人，人們也會自己去找最高的山峰。

🐱2、快速傅里葉變換FFT

① DFT離散傅里葉變換

????????對于任意多項式系數表示轉點值表示，可以隨便取任意n個x值代入計算,但這樣時間復雜度是O ( n 2 )所以偉大數學家傅里葉取了一些特殊的點代入，從而進行優化。
????????他規定了點值表示中的n個x為n個模長為1的復數。這n個復數不是隨機的，而是單位根。
????????把上述的n個復數（單位根）ω n0 , ω n1 . . . . . , ωn?1代入多項式，能得到一種特殊的點值表示，這種點值表示就叫DFT（離散傅里葉變換）。

????????想象你有一個多項式，比如，通常我們用它的系數（這里是1、2、1）來表示它。但另一種方法是，你可以找一些點，比如，然后算出這些點對應的的值，分別是1、4、9。這樣，你就可以用這三個點（0,1）、（1,4）、（2,9）來表示這個多項式。這種方法就叫點值表示。

????????復數可以看成是平面上的點，有實部和虛部。模長就是這個點到原點的距離。如果一個復數的模長為1，那就意味著它在平面上離原點的距離正好是1。這些點都落在一個以原點為中心、半徑為1的圓上，這個圓叫單位圓。

????????現在，我們要在單位圓上均勻地找n個點。比如，n=4，我們就在單位圓上找4個等分的點。這些點在數學里叫單位根。它們有一個很特別的性質：當你把它們代入多項式的時候，計算會變得很方便。

????????所以，這句話的意思是：在點值表示法中，我們選擇的n個x值，不是隨便挑的，而是單位圓上的n個均勻分布的點。這些點都是模長為1的復數，它們在計算多項式的時候特別有用。

② FFT快速傅里葉變換

????????雖然DFT能把多項式轉換成點值但它仍然是暴力代入n nn個數，復雜度仍然是O(n2)，所以它只是快速傅里葉變換的樸素版。

原始信號：一首復雜的交響樂

????????想象你聽到一首交響樂，里面有：

????????🎻 小提琴（高音）、🎺 小號（中音）、大鼓（低音等等各種樂器同時演奏

????????你的耳朵聽到的是??混合在一起??的復雜聲音。

FFT就像"音樂分析師"

FFT的作用就是：戴上專業耳機??：把混合的音樂分解開，??分析頻譜??：告訴你這首曲子里有：

? ? ? ? 30%的小提琴聲（高頻）

????????25%的小號聲（中頻）

????????45%的鼓聲（低頻）

概念	通俗解釋	在您研究中的應用
??FFT??	音樂分解器	把駕駛動作分解成不同頻率成分
??重采樣??	重新編曲	把長短不一的駕駛片段變成統一長度
??保持特征??	保留原曲風格	加速還是加速，減速還是減速

??????????一句話總結??：FFT就像給每個駕駛片段做"DNA分析"，找出它的本質特征，然后根據這個特征重新生成標準長度的片段，方便后續比較和分析。

🐱3、AC-DTC聚類

????????聚類分為兩個不同的類別:分層聚類（從很多類到幾個類）和分區聚類（從一個類切分到很多類）。

? ? ? ? 其中分層聚類使用：相似性遞歸聚類——構建樹形圖探索不同粒度級別的聚類。

????????AC-DTC的層次特性有效地捕獲了行動階段數據中的時間依賴性和變化，促進了相似行動階段的準確聚類，同時反映了細微的差異

????????DTC（Dynamic Tree Cutting，動態樹切） 是整個算法的關鍵部分。它的核心作用是：在層次聚類（得到一棵樹狀圖 dendrogram）之后，自動決定如何切割樹來得到合理的簇數，而不是人工設定某一個“水平線”來切。

????????它是層次聚類（Hierarchical clustering）的一種后處理策略：層次聚類（AC）會生成一棵樹狀圖（dendrogram），從“每個點單獨一類”到“所有點合并成一類”的整個過程都能看到。但層次聚類本身不會告訴你“在哪一層切開”才是最佳聚類結果。

????????動態樹切分（DTC）就是自動分析這棵樹的結構，根據數據的上下文，靈活決定在哪里剪枝，把數據劃分成更合適的簇。

????????AC：自底向上合并，先一個點一類，然后逐步合并。

????????DTC：對生成的樹圖進行動態切分，得到最終聚類。

合起來，AC-DTC 能：

自動調整簇的數量（不像普通層次聚類需要手動定層次）。
更好地處理“動作階段數據”這種長度不一、內部有細節差異的序列。

四種 linkage 方法（ward, average, complete, weighted）指的是在聚類分析中，用于計算樣本點之間距離或相似度的四種不同的連接方式。下面分別解釋一下這四種方法：

ward：Ward方法是一種基于方差分析的方法。它通過最小化類內方差來確定簇，目的是使得每個簇內的樣本點盡可能緊密地聚集在一起。在每次合并簇時，會選擇使得總方差增加最小的簇對進行合并。這種方法適用于球形簇，并且對簇的大小較為敏感，簇大小差異較大時可能會影響聚類效果。
average：平均連接法（也稱為UPGMA，Unweighted Pair Group Method with Arithmetic mean）。它計算兩個簇中所有樣本點對之間的平均距離，作為這兩個簇之間的距離。這種方法相對較為穩健，不會因為簇中個別異常點而對簇間距離產生過大影響，適用于不同形狀和大小的簇。
complete：最大連接法（也稱為Furthest Neighbor）。它以兩個簇中所有樣本點對之間的最大距離作為這兩個簇之間的距離。這種方法對異常值較為敏感，因為簇間距離由最遠的點對決定，可能會導致一些較小的簇被過早地合并，適用于簇形狀較為規則的情況。
weighted：加權平均連接法（也稱為WPGMA，Weighted Pair Group Method with Arithmetic mean）。它在計算簇間距離時，會考慮簇的大小，對簇中樣本點的數量進行加權。這種方法在一定程度上平衡了簇的大小對簇間距離的影響，適用于簇大小差異較大的情況，能夠更合理地反映簇之間的相似性。