關於演算法公式推導與python的信息

本文目錄一覽：

• 1、幾種常用演算法的Python實現
• 2、支持向量機—從推導到python手寫
• 3、#Python乾貨#python實現——最優化演算法
• 4、Python 演算法
• 5、python的思維邏輯怎麼樣？
• 6、有哪些用 Python 語言講演算法和數據結構的書

幾種常用演算法的Python實現

既然是常用演算法，網上肯定有大量代碼~ 但是還是建議自己打一遍，然後深入了解~抄書誰都會，但是能理解並記憶深刻，就不是每個人能都堅持做到的。

支持向量機—從推導到python手寫

筆者比較懶能截圖的地方都截圖了。

支持向量機分為三類：

（1）線性可分支持向量機，樣本線性可分，可通過硬間隔最大化訓練一個分類器。

（2）線性支持向量機，樣本基本線性可分，可通過軟間隔最大化訓練一個分類器。

（3）非線性支持向量機，樣本線性不可分，可通過核函數和軟間隔最大化訓練一個分類器。

上面最不好理解的恐怕就是硬間隔和軟間隔了，

說白了硬間隔就是說存在這麼一個平面，可以把樣本完全正確無誤的分開，當然這是一種極理想的情況，現實中不存在，所以就有了軟間隔。

軟間隔說的是，不存在一個平面可以把樣本完全正確無誤的分開，因此呢允許一些樣本被分錯，怎麼做呢就是加入鬆弛變數，因為希望分錯的樣本越小越好，因此鬆弛變數也有約束條件。加入鬆弛變數後，問題就變為線性可分了，因為是每一個樣本都線性可分，因此鬆弛變數是針對樣本的，每一個樣本都對應一個不同的鬆弛變數。

其實感知機說白了就是找到一條直線把樣本點分開，就是上方都是一類，下方是另一類。當然完全分開是好事，往往是不能完全分開的，因此就存在一個損失函數，就是誤分類點到這個平面的距離最短：

這裡啰嗦一句，誤分類點y*(wx+b)0，所以加個負號在前邊。

一般情況下||w||都是可以縮放，那麼我們把它縮放到1，最後的目標函數就變成了

間隔就是距離，我們假設分離超平面為 ，那麼樣本點到這個平面的距離可以記為 。我們都知道通過感知機劃分的點，超平面上方的點 ，下方的點 ，然後通過判斷 的值與y的符號是否一致來判斷分類是否正確。根據這個思路函數間隔定義為：

支持向量的定義來源於幾何間隔，幾何間隔最直接的解釋是離分隔超平面最近點的距離，其他任何點到平面的距離都大於這個值，所以幾何間隔就是支持向量。然後呢同樣道理，w和b是可以縮放的，所以定義支持向量滿足如下條件：

再通俗一點說，支持向量是一些點，這些點到分隔平面的距離最近，為了便於表示，把他們進行一下縮放計算，讓他們滿足了wx+b=+-1.

核函數是支持向量機的核心概念之一，它存在的目的就是將維度轉換之後的計算簡化，達到減少計算量的目的。我們都知道支持向量機求的是間距最大化，通常情況下我們求得的alpha都等於0，因此支持向量決定了間距最大化程度。

核函數的形式是這樣的

其中x(i)和x(j)都是向量，他們兩個相乘就是向量內積，相乘得到一個數。剛才說了目標函數一般只和支持向量有關，因此在做核函數計算之前，實際就是選擇的支持向量進行計算。

這個寫完下面得再補充

我們知道了支持向量的概念，那麼支持向量機的目標函數是要使這兩個支持向量之間的距離儘可能的遠，因為這樣才能更好地把樣本點分開，當然支持向量也要滿足最基本的約束條件，那就是分類正確，還有就是其他點到分隔平面的距離要大於等於支持向量到分隔平面的距離。

這種凸優化問題都可以通過拉格朗日運算元進行優化，就是把約束條件通過拉格朗日係數放到目標函數上。這部分基礎知識，就是拉格朗日演算法可以將等式約束和不等式約束都加到目標函數上，完成求解問題的轉換，但是要滿足一些約束條件，也就是我們後邊要說的kkt條件。

這裡有個細節就是轉換時候的加減號問題，這個和目標函數還有約束的正負號有關。一般這麼理解，就是求最小化問題時候，如果約束是大於0的，那麼拉個朗日運算元可以減到這一部分，這樣一來目標函數只能越來越小，最優解就是約束為0的時候，這個時候和沒有約束的等價，再求最小就是原問題了。

這裡是最小化問題，直接減掉這部分約束，然後後半部分永遠大於等於0所以這個式子的值是要小於原來目標函數值的。我們知道當x滿足原問題的約束條件的時候，最大化L就等於那個原目標函數。所以我們可以把這個問題轉化為：

把它帶回去原來的目標函數中，整理一下。

這個時候只要求最優的α，就可以求出w和b了。我們上邊做了那麼一堆轉換，這個過程要滿足一個叫做kkt條件的東西，其實這個東西就是把一堆約束條件整理到一起。

（1）原有問題的可行性，即h(x )=0,g(x )0

放到這裡就是：

SMO演算法的核心思想是求出最優化的α，然後根據之前推導得到的w,b,α之間的關係計算得到w和b，最後的計算公式是：

現在的問題就是怎麼求α了。

SMO演算法總共分兩部分，一部分是求解兩個α的二次規劃演算法，另一部分是選擇兩個α的啟發式演算法。

先說這個選擇α的啟發式演算法部分：大神可以證明優先優化違反kkt條件的α可以最快獲得最優解，至於咋證明的，就先不看了。

在講支持向量機的求解演算法時候，直接給出了核函數K，那麼怎麼去理解核函數呢。核函數的作用是解決樣本點在高維空間的內積運算問題，怎麼理解呢，通常的分類問題都是有很多個特徵的，然後為了達到現線性可分，又會從低維映射到高維，樣本量再一多計算量非常大，因此先通過函數進行一個轉換，減少乘法的計算量。

要理解核函數，先理解內積運算，內積運算實際是兩個向量，對應位置相乘加和，比如我有x1 = [v1,v2], x2=[w1,w2]，那麼x1和x2的內積計算方法就是：v1w1+v2w2。

如果上面那種情況線性不可分，需要到高維進行映射，讓數據變得線性可分，然後數據變為五維的，即v1 2+v2 2+v1+v2+v1v2，然後再進行一次內積計算，數據變為 。

稍作變換，可以變為 ，形式展開和上邊那個長式子差不多，然後其實可以映射內積相乘的情況，所以可以進行核函數的變化。

問題在於，當你需要顯式的寫出來映射形式的時候，在維度很高的時候，需要計算的量太大，比如x1有三個維度，再進行映射就有19維度了，計算很複雜。如果用核函數，還是在原來低維度進行運算，既有相似的效果（映射到高維），又低運算量，這就是核函數的作用了。

核函數的種類：

這部分的核心在於SMO演算法的編寫。有待補充。

#Python乾貨#python實現——最優化演算法

函數詳見rres，此代碼使該演算法運行了兩次

收穫：

這是我第一個實現的代碼。學習完該演算法以後，邏輯框架基本上就有了，剩下需要明確的就是對應的python的語言。於是我就開始了查找「如何定義函數」（詳見mofan的優酷），「循環體」和「if條件語句」的格式（）「數學符號」（詳見mofan的優酷），以及print的使用

1.def是python中指定義，一般用來定義函數，如果需要深度學習搭建網路可用來定義網路。值得注意的一點是

我不清楚為什麼，但是如果沒有加的話，那個函數公式就是一個花瓶，就像一個結果輸不出去。

2.最坑的就是邏輯。一開始邏輯沒理清楚，或者說在代碼上有疏漏，導致我將left和right放在了循環體里，結果可想而知。不過也是因為這個錯誤，我知道pycharm中的debug怎麼用，挺簡單的，百度一下就出來了。

3.不知道什麼原因，看的莫煩視頻中的print多個變數一起輸出是沒有辦法在我的pycharm中使用的，出來的結果很奇怪。可能是因為我是win10不是ios吧。print如果多個變數一起輸出必須是print(“名字：%s,名字2：%s”%(a,b))結果輸出就是名字：a ,名字2：b

關於python中數據變數。第一遍運行結果出現很明顯不對，於是我採用了debug。結果發現，mid1處一直為1而不是1.5，於是就開始了解數據變數。起初我猜測python默認所有變數為整型，但是根據二分法的結果我意識到此猜測不對，所以要改整個file的變數格式沒有必要。所以我就在mid1式子前面加了一個float，結果就顯示為1.5了。但是如果我將整個式子用（）括起來，前面加float，結果還是1。我不太理解為什麼。不過我知道了python的數據格式是根據輸入量決定的，也就是說你的輸入量如果是整型，那麼與其直接相關的計算輸出結果一定是整型，而且還是不採用進位的整型。在我沒有採用+float/+.0這兩種方法之前，mid1~3全部是整型。

或者不再mid1前面加float,直接將輸入量後面點個點就行

真的很想吐槽一下print,好麻煩啊啊啊啊每次都得弄個%s,而且有時候還不能放一起！！！！

不要問我掌握了什麼，要問我現在寫完這個代碼後有多麼的愛python的精度表示 :-)我決定以後只要再編寫數學公式的代碼都將輸入量的小數學點後面補很多0

fibonacci函數定義，每次debug後我的手都是抖的O( _ )O~

不知道自己什麼時候有的強迫症，只要是代碼下面有「~」我就必須要消掉。笑哭。這個很簡單，前四個除了費波納茨，都很簡單。

這個公式看起來很麻煩，便寫的時候更要謹慎。我上回把那個2擱在了分號下面，結果很大，所以還是換算成0.5更好（PS：勿忘那長河般的0）。

雖然代碼很長，但是主要是因為print太多。本打算在開頭print，最後結果會漏掉最後一部分。懶得想其他辦法了，直接就這樣吧

一開始while裡面寫成了,導致run不出來。繼而，debug也沒法用。在網上一查才知道 「沒聯網」+「沒選斷點」。最後想嘗試將else裡面的內容輸出來，結果發現run以後被刷屏了。於是改成i7以後還是不行，於是想著加一個break跳出循環，結果成效了。

然後剛剛由debug了一下，才知道原來是i+1在if裡面，因為沒有辦法+1，所以i=6一直存在，就不斷循環。因為加break也好，i+1也好，都可以。

這是我第一組自己實現的python代碼，就是數學公式用python語言組裝起來。剛開始的時候知道大概需要在語言中體現什麼，但不太清楚。於是我就在網上找了幾個二分法的，他們都各有不同，但框架都差不多，不過如果要用到我們的那個公式里還需要改變很多。然後我就開始分析我們的題，我發現大體需要兩部分，一部分函數定義，一部分循環體。但我不知道如何定義函數，如何寫數學公式，如何弄變數，也就是說一些小點不太會，所以我選擇直接百度。因為我知道自己閱讀的能力不錯，相比於從視頻中提取要素，我更擅長通過閱讀獲得要點。有目的性地找知識點，掌握地更牢固。

於是我就開始了第一個——二分法的編寫。我發現，自己出現了很多錯誤而且有很多地方都很基礎。但我依然沒選擇視頻，而是將這些問題直接在百度上找，因為視頻講完或許你也沒找到點。當然，這是一步一步走的，不是直接就將程序擺上去，一點一點改。

隨著前兩個的成功，我發現自己對於這些代碼有了自信，似乎看透了他們的偽裝，抓住了本質。除此之外，我還意識到自己自從8月份以後，學習能力似乎提高了不少，而且有了更為有效的學習方法。各方面都有了一定的覺醒。除了第一個找了幾個牛頭不對馬嘴的代碼，其他都是根據自己的邏輯寫，邏輯通下來以後，對應語言中某一部分不知道如何翻譯就去百度，其實這幾個套路都一樣或者說數學公式轉化的套路都一樣。

我還意識到，彙編其實是最難的語言，目前為止所學到的，因為很多都需要自己去定義，去死摳，需要記住大量的指令且不能靈活變通。但是其他的卻只需要將一些對應的記下來就好。python真的挺簡單的。而且，我發現自己今天似乎打開了新世界的大門，我愛上了這種充滿了靈性的東西，充滿了嚴謹的美麗，還有那未知的變化，我發現我似乎愛上了代碼。可能不僅僅局限於python，這些語言都充滿了挑戰性。我覺得當你疑惑的時候，就需要相信直覺，至少我發現它很准

Python 演算法

什麼是演算法

「演算法（Algorithm）是指解題方案的準確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制。」

「在談到演算法時，我們不得不去了解一下什麼是時間複雜度和空間複雜度這兩個概念」

計算機科學中，演算法的時間複雜度是一個函數，它定量描述了該演算法的運行時間,時間複雜度常用大O符號（大O符號（Big O notation）是用於描述函數漸進行為的數學符號。

空間複雜度：它是用來評估演算法內存佔用大小的一個式子。

Python 演算法的幾大重要特徵

Python演算法除了具有以上特徵，還和時間和空間有關係，不同的演算法可能用不同的時間、空間或效率來完成同樣的任務，因此， 一個Python演算法的優劣可以用空間複雜度與時間複雜度來衡量。

通過實例加深對演算法的理解

如題所示：

要求x,y,z的1000以內取值滿足x x+y y=z*z，同時x+y+z=1000,求解出所以x,y,z的組合情況？

求解過程如下

這裡使用了一個waste_time方法作為裝飾器來計算裝飾過的方法的執行時間，這裡有兩種演算法來求解這個問題

代碼如下：

總結：

通過這個示例，對於同一個問題給出兩種不同的演算法，兩種演算法在執行過程中我增加了對程序執行時間的統計，通過時間上的對比發現兩個演算法的執行時間相差非常的大，如響應結果所示。

由此我們可以得出一個結論，就是實現不同的演算法程序執行的時間可以反應出演算法的效率，即演算法有優劣之分，好的演算法可以節約時間，提高效率，反之則不然。

python的思維邏輯怎麼樣？

Python作為一門強大的面向對象，程序設計，類似於現在主流的其他設計語言。它可以勝任程序開發的各個方面，無論是從入門級還是到專業級的科學計算。#我要學Python#

兒童編程

Python特點

Python有一個很顯著的特點就是，現在流行的人工智慧技術大部分都是使用它來編寫的，這大大地促進了Python的發展。機器學習和人工智慧本身的一個進化特點決定了它不太適合靜態編譯性的語言，而適合使用解釋性的語言，同時它是非常的簡單易學，容易上手，語法清晰明了，導致了很多數學家，科學家選擇使用Python來寫一些數學計算相關的一些庫，最終直接導致了他在科學計算領域無可比擬的優勢。

Python可以做什麼

寫腳本：最簡單的你可以用它寫一些小腳本Web網站：再複雜一點的，你可以用它寫一個網站科學計算：Python應用最廣泛的其實還是和數學科學計算相關的，比如說你去做一些網路爬蟲，從網上抓一些數據，然後進行數據分析，就可以用它很方便地做到定量分析：還可以自己根據一些數學的公式推導出來的數學模型建模，來達到自己的一個目標，比如說做特定的定量分析，這就是現在，華爾街或者說金融圈最熱門的一個方向機器學習：目前最最熱門的方向，Python現在被廣泛的應用在機器學習和人工智慧領域

人工智慧

為什麼學習Python

Python越來越熱了，以後會加入全國計算機等級考試，還有傳說是連高考也會加入Python相關的一些內容。目前想做一系列課程，主要是給小學階段的學生們學習Python的，所以會介紹的儘可能簡單。

有哪些用 Python 語言講演算法和數據結構的書

1.Python數據結構篇

數據結構篇主要是閱讀[Problem Solving with Python](Welcome to Problem Solving with Algorithms and Data Structures) [該網址鏈接可能會比較慢]時寫下的閱讀記錄，當然，也結合了部分[演算法導論](Introduction to Algorithms)中的內容，此外還有不少wikipedia上的內容，所以內容比較多，可能有點雜亂。這部分主要是介紹了如何使用Python實現常用的一些數據結構，例如堆棧、隊列、二叉樹等等，也有Python內置的數據結構性能的分析，同時還包括了搜索和排序(在演算法設計篇中會有更加詳細的介紹)的簡單總結。每篇文章都有實現代碼，內容比較多，簡單演算法一般是大致介紹下思想及演算法流程，複雜的演算法會給出各種圖示和代碼實現詳細介紹。

**這一部分是下面演算法設計篇的前篇，如果數據結構還不錯的可以直接看演算法設計篇，遇到問題可以回來看數據結構篇中的某個具體內容充電一下，我個人認為直接讀演算法設計篇比較好，因為大家時間也都比較寶貴，如果你會來讀這些文章說明你肯定有一定基礎了，後面的演算法設計篇中更多的是思想，這裡更多的是代碼而已，嘿嘿。**

(1)[搜索](Python Data Structures)

簡述順序查找和二分查找，詳述Hash查找(hash函數的設計以及如何避免衝突)

(2)[排序](Python Data Structures)

簡述各種排序演算法的思想以及它的圖示和實現

(3)[數據結構](Python Data Structures)

簡述Python內置數據結構的性能分析和實現常用的數據結構：棧、隊列和二叉堆

(4)[樹總結](Python Data Structures)

簡述二叉樹，詳述二叉搜索樹和AVL樹的思想和實現

2.Python演算法設計篇

演算法設計篇主要是閱讀[Python Algorithms: Mastering Basic Algorithms in the Python Language](Python Algorithms: Mastering Basic Algorithms in the Python Language)[**點擊鏈接可進入Springer免費下載原書電子版**]之後寫下的讀書總結，原書大部分內容結合了經典書籍[演算法導論](Introduction to Algorithms)，內容更加細緻深入，主要是介紹了各種常用的演算法設計思想，以及如何使用Python高效巧妙地實現這些演算法，這裡有別於前面的數據結構篇，部分演算法例如排序就不會詳細介紹它的實現細節，而是側重於它內在的演算法思想。這部分使用了一些與數據結構有關的第三方模塊，因為這篇的重點是演算法的思想以及實現，所以並沒有去重新實現每個數據結構，但是在介紹演算法的同時會分析Python內置數據結構以及第三方數據結構模塊的優缺點，也就意味著該篇比前面都要難不少，但是我想我的介紹應該還算簡單明了，因為我用的都是比較樸實的語言，並沒有像演算法導論一樣列出一堆性質和定理，主要是對著某個問題一步步思考然後演算法就出來了，嘿嘿，除此之外，裡面還有很多關於python開發的內容，精彩真的不容錯過！

這裡每篇文章都有實現代碼，但是代碼我一般都不會分析，更多地是分析演算法思想，所以內容都比較多，即便如此也沒有包括原書對應章節的所有內容，因為內容實在太豐富了，所以我只是選擇經典的演算法實例來介紹演算法核心思想，除此之外，還有不少內容是原書沒有的，部分是來自演算法導論，部分是來自我自己的感悟，嘻嘻。該篇對於大神們來說是小菜，請一笑而過，對於菜鳥們來說可能有點難啃，所以最適合的是和我水平差不多的，對各個演算法都有所了解但是理解還不算深刻的半桶水的程序猿，嘿嘿。

本篇的順序按照原書[Python Algorithms: Mastering Basic Algorithms in the Python Language](Python Algorithms: Mastering Basic Algorithms in the Python Language)的章節來安排的(章節標題部分相同部分不同喲)，為了節省時間以及保持原著的原滋原味，部分內容(一般是比較難以翻譯和理解的內容)直接摘自原著英文內容。

**1.你也許覺得很多內容你都知道嘛，沒有看的必要，其實如果是我的話我也會這麼想，但是如果只是歸納一個演算法有哪些步驟，那這個總結也就沒有意義了，我覺得這個總結的亮點在於想辦法說清楚一個演算法是怎麼想出來的，有哪些需要注意的，如何進行優化的等等，採用問答式的方式讓讀者和我一起來想出某個問題的解，每篇文章之後都還有一兩道小題練手喲**

**2.你也許還會說演算法導論不是既權威又全面么，基本上每個演算法都還有詳細的證明呢，讀演算法導論豈不更好些，當然，你如果想讀演算法導論的話我不攔著你，讀完了感覺自己整個人都不好了別怪小弟沒有提醒你喲，嘻嘻嘻，左一個性質右一個定理實在不適合演算法科普的啦，沒有多少人能夠堅持讀完的。但是碼農與蛇的故事內容不多喲，呵呵呵**

**3.如果你細讀本系列的話我保證你會有不少收穫的，需要看演算法導論哪個部分的地方我會給出提示的，嘿嘿。溫馨提示，前面三節內容都是介紹基礎知識，所以精彩內容從第4節開始喲，么么噠 O(∩_∩)O~**

(1)[Python Algorithms – C1 Introduction](Python Algorithms)

本節主要是對原書中的內容做些簡單介紹，說明演算法的重要性以及各章節的內容概要。

(2)[Python Algorithms – C2 The basics](Python Algorithms)

**本節主要介紹了三個內容：演算法漸近運行時間的表示方法、六條演算法性能評估的經驗以及Python中樹和圖的實現方式。**

(3)[Python Algorithms – C3 Counting 101](Python Algorithms)

原書主要介紹了一些基礎數學，例如排列組合以及遞歸循環等，但是本節只重點介紹計算演算法的運行時間的三種方法

(4)[Python Algorithms – C4 Induction and Recursion and Reduction](Python Algorithms)

**本節主要介紹演算法設計的三個核心知識：Induction(推導)、Recursion(遞歸)和Reduction(規約)，這是原書的重點和難點部分**

(5)[Python Algorithms – C5 Traversal](Python Algorithms)

**本節主要介紹圖的遍歷演算法BFS和DFS，以及對拓撲排序的另一種解法和尋找圖的(強)連通分量的演算法**

(6)[Python Algorithms – C6 Divide and Combine and Conquer](Python Algorithms)

**本節主要介紹分治法策略，提到了樹形問題的平衡性以及基於分治策略的排序演算法**

(7)[Python Algorithms – C7 Greedy](Python Algorithms)

**本節主要通過幾個例子來介紹貪心策略，主要包括背包問題、哈夫曼編碼和最小生成樹等等**

(8)[Python Algorithms – C8 Dynamic Programming](Python Algorithms)

**本節主要結合一些經典的動規問題介紹動態規劃的備忘錄法和迭代法這兩種實現方式，並對這兩種方式進行對比**

(9)[Python Algorithms – C9 Graphs](Python Algorithms)

**本節主要介紹圖演算法中的各種最短路徑演算法，從不同的角度揭示它們的內核以及它們的異同**