《to buy or not to buy》筆記

論文地址：https://www.isi.edu/integration/papers/etzioni03-kdd.pdf

作者是Oren Etzioni， farecast創始人(被微軟收購），http://decide.com創始人（被ebay收購），華盛頓大學計算機系教授

摘要

這篇論文的目的是預測機票價格，我們用multi-strategy data mining algorithm（HAMLET）的方法為模擬的341個乘客節省了 $198,074，在完整的信息環境中，最多可節省$320,572，也就是達到了最優的61.8%。

對於整個數據集，4488名乘客平均節省了4.4%的機票費用。

1 動機介紹

公司通常會是用複雜的隨時間變化的定價策略來為產品定價，飛機行業是動態定價的典型。

調整定價的原因有季節性，剩餘座位數量，其它航線的競爭等很多。

隨著網上購物的興起及產品的爆炸性增長，購買者變得越來越精明，他們會從產品價格的變化中發現一些變化規律，比如在國慶通常會搞個大促銷，我要等著那個時候買。這篇論文的目的就是用數據挖掘的方式，幫助買家更便宜的買到機票。

這篇論文主要想解決以下幾個問題：

a.機票價格隨時間變化的規律？

機票價格變化的頻率？幅度？傾向於隨時間上漲還是下調？

b.什麼數據挖掘方法可以找到其中的規律？

我們會用到rule learning， time series methods， reinforcement learning

c.在實際應用中，用data mining真的可以為買家省錢嘛？

航空公司在改變定價時，依據的很多變數是我們不可見的，比如未售出的座位數，這樣來看，似乎很難預測啊。

但是實際上，我們發現，在某些情況下，預測的效果驚人的好。

2 數據收集

我們做了個爬蟲，定期的抓取機票價格數據，解析，存儲到資料庫中。

為了簡化問題，我們只不經停，往返的兩個航線：

1. Los Angeles (LAX) to Boston (BOS)

2.Seattle

出發時間是2003.1的所有天，7日後返回

我們收集每個出發日期前21天的價格數據，每3個小時收集一次，也就是每天收集8次。

我們一共收集了12000條數據，共包含41天，6個航空公司的數據。

對於每個航班，我們記錄經濟艙的最低價，當經濟艙賣完時，我們標註為sold out狀態。

2.1 數據中的價格模式

我們發現一個航班的價格，在1天中，最高變化過7次。

我們把價格變化劃分成兩類：

a. dependence price changes（比如同一航空公司的相似航班的價格變化，這類變化一般一天1-2次）

b. independence price changes（獨立變化，當變化時同一航空公司的相似航班價格沒有變化，這種變化一般來源於剩餘座位數量的變化）

對於很對航班，價格是分成層的，而且很容易觀察出來，價格一般會分成2-4層，即便是同一公司的同一航班，但不同出發日期，價格分層的個數也會不同。

航空公司會用軟體追蹤競爭對手的出價歷史，並作出是否調整價格的決策，這個過程是和ATPCO交互的。

我們可以從圖三看出非常有規律的價格記錄，這很符合提前7或14天買機票的說法。

但是我們也可以發現一些驚人的價格變化，比如在節假日附近出發的航班，價格變化會更加劇烈。

圖二和圖三是同一航班，但出發日期不一樣，圖二是節假日附近出發。

根據價格策略，我們可以把航空公司劃分為兩類：大玩家比如聯合航空，美國航空，小玩家（廉價航空）比如西南航空，空中運輸航空。

相同類航空公司的調價策略比較類似，第一種的價格較貴，調價相對頻繁，第二種價格便宜，且價格比較穩定。

當然這兩類公司也有相同的調價策略，比如在離出發還有兩周的時候上調價格，在出發前達到最高價。

3.相關工作

最近有很多時序數據的數據挖掘研究，但和我們的問題還不太一樣。

和價格預測最相近的是時間序列分析，和計算金融學中的"optimal stopping problem"

但是這些方法並沒有真正用來做過商品的價格預測。

所以我們把這些方法組合起來，並加上rule learning方法，來提高整體的性能。

計算金融學是預測何時購買股票，期權等金融產品的。金融產品的價格不會受未知信息影響，它只取決於供給，需求和買賣行為。股票價格通常的變化是連續的，而不是像機票價格的變化有非常明顯的起落。

但是，期權交易還是我們的問題比較類似的，都是在一個截止時間內選擇最好的時間出手。強化學習已經被運用在了期權交易中，所以我們考慮強化學習方法。

時間序列分析是統計學中的一大塊，機票價格的變化，天然的就是一種時間序列。

4.數據挖掘方法

本部分介紹我們使用的模型：Ripper，time series， 和Q－learning。

為什麼用這三種呢，實際上代表了真實規律的不同方面，原文叫做：

multiple data mining methods with very different

characteristics (Ripper, Q-learning, and time series)

4.1 Rule learning

設計的feature如下：

航班號

離起飛的小時數

當前價格

航空公司

航線

label為wait或buy

可以看到，目前還沒有獲取到季節性，剩餘座位數這些feature。

對於我們的場景，classification accuracy並不是一個好的metric，因為錯分的代價非常大，可能會讓用戶多花很多冤枉錢。

一種對不同的分類錯誤產生不同的懲罰粒度的cost叫做是Meta－Cost。

對於產生wait，我們應該是更保守一些的。

Meta－Cost提高了Ripper 14%的性能，但是降低HAMLET 29%的性能，所以最後並沒有用Meta－Cost。

4.2 Q-learning

待看

4.3 time series

first order moving average model

三種模型實質上是反映了真實規則的不同方面，三種模型在建模時用的feature也不一樣，

rule learning可以看作一些比較死的規則，而time series利用了時序信息

但time series只是預測下一步的價格，如果下一個價格大於當前價格，那就buy，否則wait。

可以預料到，time series的效果並不會很好（只預測下一步嘛），但是對HAMLET來說，它提供了當前價格和平均價格的比較，這個是很重要的信息。

4.4 stacked generalization

集成學習一般是bagging和boosting，但是還有一種叫stacking（也叫stacked generalization）。

之所以不用bagging，而用stacking的原因是：因為這三個模型的差異非常大，所以每個模型的使用場景不同，而作者認為可以找到何種場景使用何種model的規則。

我們把stacking後的模型叫做HAMLET，源自哈姆雷特的名句to be or not to be(to buy or not to buy)

4.5 人工規則

上面的stacking模型可能沒有考慮用戶的等待成本，所以需要手寫一些規則來防止用戶等太久。

比如離出發只剩7天了，那麼直接買就好了，如果票賣完需要升艙那損失就大了。

5. 實驗結果

6. 未來工作

a.研究需要中轉的航班，這種更複雜，因為其中每一段都可能變化

b.收集更多的特徵，比如很重要的剩餘座位數，是有方法可以拿到這些信息的

c.其它領域的定價也和機票領域類似，相關的技術可以復用，比如酒店價格，超市的商品價格

d.雖然缺少很重要的特徵，但是最終的模型表現的驚人的不錯

收穫：

1. 首次證明了機票價格是可以預測的，並且是在沒有剩餘座位數的情況下。

2. 機票價格是階梯變化的。

3. 不同的模型反映了真實規律的不同方面，現在有了更好的工具，比如RNN，gbdt，stacking後的效果估計會更好。