# 量化分析師的Python日記【第9天 Q Quant兵器譜之二叉樹】 > 來源：https://uqer.io/community/share/5523a4a1f9f06c8f3390453b 通過之前幾天的學習，Q Quant們應該已經熟悉了Python的基本語法，也了解了Python中常用數值庫的算法。到這里為止，小Q們也許早就對之前簡單的例子不滿意，希望能在Python里面玩票大的！Ok，我們這里引入一個不怎么像玩具的模型——二叉樹算法。我們仍然以期權為例子，教會大家： 1. 如何利用Python的控制語句與基本內置計算方法，構造一個二叉樹模型； 1. 如何使用類封裝的方式，抽象二叉樹算法，并進行擴展； 1. 利用繼承的方法為已有二叉樹算法增加美式期權算法。 ```py import numpy as np import math import seaborn as sns from matplotlib import pylab font.set_size(15) ``` ## 1. 小Q的第一棵“樹”——二叉樹算法Python描述 我們這邊只會簡單的描述二叉樹的算法，不會深究其原理，感興趣的讀者可以很方便的從公開的文獻中獲取細節。 我們這里仍然考慮基礎的 Black - Scholes 模型：  這里各個字母的含義如之前介紹，多出來的 r 代表股息率。 之所以該算法被稱為 二叉樹，因為這個算法的基礎結構是一個逐層遞增的樹杈式結構： 一個基本的二叉樹機構由以下三個參數決定： 1. `up` 標的資產價格向上跳升的比例， `up`必然大于1 （對應上圖中的 `u`) 1. `down` 標的資產價格向下跳升的比例， `dow`n必然小于1 (對應上圖中的 `d`) 1. `upProbability` 標的資產價格向上跳升的概率 這里我們用一個具體的例子，使用Python實現二叉樹算法。以下為具體參數： + `ttm` 到期時間，單位年 + `tSteps` 時間方向步數 + `r` 無風險利率 + `d` 標的股息率 + `sigma` 波動率 + `strike` 期權行權價 + `spot` 標的現價 這里我們只考慮看漲期權。 ```py # 設置基本參數 ttm = 3.0 tSteps = 25 r = 0.03 d = 0.02 sigma = 0.2 strike = 100.0 spot = 100.0 ``` 我們這里用作例子的樹結構被稱為 Jarrow - Rudd 樹，其中：  ```py dt = ttm / tSteps up = math.exp((r - d - 0.5*sigma*sigma)*dt + sigma*math.sqrt(dt)) down = math.exp((r - d - 0.5*sigma*sigma)*dt - sigma*math.sqrt(dt)) discount = math.exp(-r*dt) ``` ```py pylab.figure(figsize = (12,8)) pylab.plot(lattice[tSteps]) pylab.title(u'二叉樹到期時刻標的價格分布', fontproperties = font, fontsize = 20) <matplotlib.text.Text at 0x16bb2290> ```  ```py # 在節點上計算payoff def call_payoff(spot): global strike return max(spot - strike, 0.0) pylab.figure(figsize = (12,8)) pylab.plot(map(call_payoff, lattice[tSteps])) pylab.title(u'二叉樹到期時刻標的Pay off分布', fontproperties = font, fontsize = 18) <matplotlib.text.Text at 0x16bc4210> ```  在我們從樹最茂盛的枝葉向根部回溯的時候，第`i`層節點與第`i+1`層節點的關系滿足：  ```py # 反方向回溯整棵樹 for i in range(tSteps,0,-1): for j in range(i,0,-1): if i == tSteps: lattice[i-1][j-1] = 0.5 * discount * (call_payoff(lattice[i][j]) + call_payoff(lattice[i][j-1])) else: lattice[i-1][j-1] = 0.5 * discount * (lattice[i][j] + lattice[i][j-1]) ``` ```py print u'二叉樹價格： %.4f' % lattice[0][0] print u'解析法價格： %.4f' % BSMPrice(1, strike, spot, r, d, sigma, ttm, rawOutput= True)[0] 二叉樹價格： 14.2663 解析法價格： 14.1978 ``` ## 2. 從“樹”到“森林”—— 面向對象方式實現二叉樹算法 之前的部分展示了一個樹算法的基本結構。但是現在的實現由很多缺點： + 沒有明確接口，作為用戶優雅簡潔的使用既有算法； + 沒有完整封裝，十分不利于算法的擴展； 下面我們將給出一個基于Python類的二叉樹算法實現，實際上我們通過上面的實驗性探索，發現整個程序可以拆成三個互相獨立的功能模塊： + 二叉樹框架 樹的框架結構，包括節點數以及基本參數的保存； + 二叉樹類型描述 具體數算法的參數，例如上例中的 Jarrow Rudd樹； + 償付函數 到期的償付形式，即為Payoff Function。 ### 2.1 二叉樹框架（`BinomialTree`） 這個類負責二叉樹框架的構造，也是基本的二叉樹算法的調用入口。它有三個成員： + 構造函數（`__init__`） 負責接受用戶定義的具體參數，例如：`spot`等；真正二叉樹的構造方法，由私有方法`_build_lattice`以及傳入參數`treeTraits`共同完成； + 樹構造細節（`_build_lattice`） 接手具體的樹構造過程，這里需要依賴根據`treeTraits`獲取的參數例如：`up`, `down`。 + 樹回溯（`roll_back`） 從樹的最茂盛枝葉節點向根節點回溯的過程。最終根節點的值即為期權的價值。這里它要求的參數是一個`pay_off`函數。 ```py # 二叉樹框架（可以通過傳入不同的treeTraits類型，設計不同的二叉樹結構） class BinomialTree: def __init__(self, spot, riskFree, dividend, tSteps, maturity, sigma, treeTraits): self.dt = maturity / tSteps self.spot = spot self.r = riskFree self.d = dividend self.tSteps = tSteps self.discount = math.exp(-self.r*self.dt) self.v = sigma self.up = treeTraits.up(self) self.down = treeTraits.down(self) self.upProbability = treeTraits.upProbability(self) self.downProbability = 1.0 - self.upProbability self._build_lattice() def _build_lattice(self): ''' 完成構造二叉樹的工作 ''' self.lattice = np.zeros((self.tSteps+1, self.tSteps+1)) self.lattice[0][0] = self.spot for i in range(self.tSteps): for j in range(i+1): self.lattice[i+1][j+1] = self.up * self.lattice[i][j] self.lattice[i+1][0] = self.down * self.lattice[i][0] def roll_back(self, payOff): ''' 節點計算，并反向倒推 ''' for i in range(self.tSteps,0,-1): for j in range(i,0,-1): if i == self.tSteps: self.lattice[i-1][j-1] = self.discount * (self.upProbability * payOff(self.lattice[i][j]) + self.downProbability * payOff(self.lattice[i][j-1])) else: self.lattice[i-1][j-1] = self.discount * (self.upProbability * self.lattice[i][j] + self.downProbability * self.lattice[i][j-1]) ``` ### 2.2 二叉樹類型描述（`Tree Traits`） 正像我們之前描述的那樣，任意的樹只要描述三個方面的特征就可以。所以我們設計的`Tree Traits`類只要通過它的靜態成員返回這些特征就可以： + `up` 返回向上跳升的比例； + `down` 返回向下調降的比例； + `upProbability` 返回向上跳升的概率 下面的類定義了 Jarrow - Rudd 樹的描述： ```py class JarrowRuddTraits: @staticmethod def up(tree): return math.exp((tree.r - tree.d - 0.5*tree.v*tree.v)*tree.dt + tree.v*math.sqrt(tree.dt)) @staticmethod def down(tree): return math.exp((tree.r - tree.d - 0.5*tree.v*tree.v)*tree.dt - tree.v*math.sqrt(tree.dt)) @staticmethod def upProbability(tree): return 0.5 ``` 我們這里再給出另一個 Cox - Ross - Rubinstein 樹的描述： ```py class CRRTraits: @staticmethod def up(tree): return math.exp(tree.v * math.sqrt(tree.dt)) @staticmethod def down(tree): return math.exp(-tree.v * math.sqrt(tree.dt)) @staticmethod def upProbability(tree): return 0.5 + 0.5 * (tree.r - tree.d - 0.5 * tree.v*tree.v) * tree.dt / tree.v / math.sqrt(tree.dt) ``` ### 2.3 償付函數（`pay_off`） 這部分很簡單，就是一元函數，輸入為標的價格，輸出的償付收益，對于看漲期權來說就是：  ```py def pay_off(spot): global strike return max(spot - strike, 0.0) ``` ### 2.4 組裝 讓我們三部分組裝起來，現在整個調用過程變得什么清晰明了，同時最后的結果和第一部分是完全一致的。 ```py testTree = BinomialTree(spot, r, d, tSteps, ttm, sigma, JarrowRuddTraits) testTree.roll_back(pay_off) print u'二叉樹價格： %.4f' % testTree.lattice[0][0] 二叉樹價格： 14.2663 ``` 這里我們想更進一步，用我們現在的算法框架來測試二叉樹的收斂性。這里我們用來作比較的算法即為之前描述的 Jarrow - Rudd 以及 Cox - Ross - Rubinstein 樹： ```py stepSizes = range(25, 500,25) jrRes = [] crrRes = [] for tSteps in stepSizes: # Jarrow - Rudd 結果 testTree = BinomialTree(spot, r, d, tSteps, ttm, sigma, JarrowRuddTraits) testTree.roll_back(pay_off) jrRes.append(testTree.lattice[0][0]) # Cox - Ross - Rubinstein 結果 testTree = BinomialTree(spot, r, d, tSteps, ttm, sigma, CRRTraits) testTree.roll_back(pay_off) crrRes.append(testTree.lattice[0][0]) ``` 我們可以繪制隨著步數的增加，兩種二叉樹算法逐漸向真實值收斂的過程。 ```py anyRes = [BSMPrice(1, strike, spot, r, d, sigma, ttm, rawOutput= True)[0]] * len(stepSizes) pylab.figure(figsize = (16,8)) pylab.plot(stepSizes, jrRes, '-.', marker = 'o', markersize = 10) pylab.plot(stepSizes, crrRes, '-.', marker = 'd', markersize = 10) pylab.plot(stepSizes, anyRes, '--') pylab.legend(['Jarrow - Rudd', 'Cox - Ross - Rubinstein', u'解析解'], prop = font) pylab.xlabel(u'二叉樹步數', fontproperties = font) pylab.title(u'二叉樹算法收斂性測試', fontproperties = font, fontsize = 20) <matplotlib.text.Text at 0x15e46490> ```  我們也可以繪制兩種算法的誤差隨著步長下降的過程。 ```py jrErr = np.array(jrRes) - np.array(anyRes) crrErr = np.array(crrRes) - np.array(anyRes) jrErr = np.log10(np.abs(jrErr)) crrErr = np.log10(np.abs(crrErr)) ``` ```py pylab.figure(figsize = (16,8)) pylab.plot(stepSizes, jrErr, '-.', marker = 'o', markersize = 10) pylab.plot(stepSizes, crrErr, '-.', marker = 'd', markersize = 10) pylab.xlabel(u'二叉樹步數', fontproperties = font) pylab.ylabel(u'誤差（log）', fontproperties = font) pylab.title(u'二叉樹算法誤差分布測試', fontproperties = font, fontsize = 20) <matplotlib.text.Text at 0x172b06d0> ```  ## 3. 新想法 —— 美式期權？ 有小Q要問了，既然我們已經有解析算法了，為什么還要多此一舉的去種“樹”呢？是的，如果只是普通歐式期權的話，二叉樹就是多此一舉的做法。但是由于二叉樹天然的反向回溯的特性，使得它特別適合處理有提前行權結構的期權產品。這里我們將以美式期權為例。 美式期權的行權結構在二叉樹結構下處理起來特別簡單，要做的只是在每個節點上做這樣的比較：  這里的 `ExerciseValue` 就是立即行權的價值， `EuropeanValue`為對應節點的歐式價值。 為了實現上面的比較，我們需要擴展原先的算法，這個我們可以通過Python的類繼承在原先的類之上添加新功能： ```py class ExtendBinomialTree(BinomialTree): def roll_back_american(self, payOff): ''' 節點計算，并反向倒推 ''' for i in range(self.tSteps,0,-1): for j in range(i,0,-1): if i == self.tSteps: europeanValue = self.discount * (self.upProbability * payOff(self.lattice[i][j]) + self.downProbability * payOff(self.lattice[i][j-1])) else: europeanValue = self.discount * (self.upProbability * self.lattice[i][j] + self.downProbability * self.lattice[i][j-1]) # 處理美式行權 exerciseValue = payOff(self.lattice[i-1][j-1]) self.lattice[i-1][j-1] = max(europeanValue, exerciseValue) ``` 我們將使用同樣的參數測試美式期權算法的實現： ```py stepSizes = range(25, 500,25) jrRes = [] crrRes = [] for tSteps in stepSizes: # Jarrow - Rudd 結果 testTree = ExtendBinomialTree(spot, r, d, tSteps, ttm, sigma, JarrowRuddTraits) testTree.roll_back_american(pay_off) jrRes.append(testTree.lattice[0][0]) # Cox - Ross - Rubinstein 結果 testTree = ExtendBinomialTree(spot, r, d, tSteps, ttm, sigma, CRRTraits) testTree.roll_back_american(pay_off) crrRes.append(testTree.lattice[0][0]) ``` 我們畫出美式期權價格的收斂圖，價格始終高于歐式期權的價格，符合預期。 ```py anyRes = [BSMPrice(1, strike, spot, r, d, sigma, ttm, rawOutput= True)[0]] * len(stepSizes) pylab.figure(figsize = (16,8)) pylab.plot(stepSizes, jrRes, '-.', marker = 'o', markersize = 10) pylab.plot(stepSizes, crrRes, '-.', marker = 'd', markersize = 10) pylab.plot(stepSizes, anyRes, '--') pylab.legend([u'Jarrow - Rudd（美式）', u'Cox - Ross - Rubinstein（美式）', u'解析解（歐式）'], prop = font) pylab.xlabel(u'二叉樹步數', fontproperties = font) pylab.title(u'二叉樹算法美式期權', fontproperties = font, fontsize = 20) <matplotlib.text.Text at 0x17aae2d0> ```