Posts match “ algorithm ” tag:

一、 Describe the problem

系統目標

為使用者告訴我們想去哪裡,系統告訴他一套完整行程怎麼玩。

  • 輸入: 使用者輸入地點關鍵字(想去的地方),和去的日期(何時去,選填)
  • 輸出: 引擎計算出搜尋結果的地點子集合,且該子集合為有順序性,同時滿足下列條件:
    1. 包含想去的區域內最熱門、必去的景點集合
    2. 子集合內的景點都是使用者最有興趣的
    3. 所有要去的地點花費總時間滿足時間限制
    4. 所有要去的地點在要去的期間內都有開放或營業
    5. 三餐有建議的餐飲,晚上有住宿
    6. 交通總時間要最小

Symbolization

  • For each place p in {PLACE}, has search rank R,place category pc, place weight pw , popularity & rating pr, open day 'od', open time ot, routing time rt, and spend time st.
  • For the user u, has place keywords keywords, travel dates dates (total days=D) and user favorite uf.
  • We have to find the subset trip of {PLACE}, which search rank, popularity, user favorite is maximum, the summation of routing time + spend time is less than and equal to D.

二、 Choose some decision variables

Xi 表示地點p 有選擇或沒有選擇到排程當中。

三、 Express the problem constraints in term of there variables

  1. 所有要去的地點花費總時間滿足時間限制
  2. 所有要去的地點在要去的期間內都有開放或營業
  3. 三餐有建議的餐飲,晚上有住宿

四、 Express the objective function ( the quality of the solution )

  1. 包含想去的區域內最熱門、必去的景點集合
  2. 子集合內的景點都是使用者最有興趣的
  3. 整個交通時間要最小

This is a paper study note for my startup travel service called StyleTrip.
The paper is Trip-Mine: An Efficient Trip Planning Approach with Travel Time Constraints

Introduction

  • How to efficiently search for the most interesting trip which satisfies a travel time constraint from a large number of attractions.
  • The efficient of trip planning is sensitive to the scalability of travel regions.
  • The optimal trip finding problem is different from Traveling Sales Problem(TSP).
  • The reason is that TSP finds the shortest path from the extra N given locations. However, the optimal trip problem is to finds a sub-permutation of given N locations.
  • The dynamic programming searches all possible trips based on the concept of DFS.

Optimization mechanisms

  • Attraction sorting ( User favorite, the must-go / popular / high-rating places )
  • Low bound checking ( meeting time, cost constaints )
  • Score Checking ( meeting low bound checking and the score is maximum)

Definitions

  • Score: It can refer to user favorite , popularity or rating value.
  • Valid trip: A trip is valid if the total trip time is less than or equal to the required travel time.
  • Optima trip: A valid trip is optimal if the Score(tripA) is maximum among the valid trip.

Proposed theorem

  • We can find out that calculation of the trip takes an exponential time, so that it can conclude that this is a NP complete problem.
  • Triangle inequality Travel time (x,y)+(y,x) >= (x,z)
  • If travel time (a0,trip1) <= (a0,trip2), then trip1 is the sub-trip of trip2.
  • Given a invalid (total trip time exploded) trip1, then any super-trip of trip1 is invalid, too. (pruning strategy 1)

Pruning strategy

  1. Given a invalid (total trip time exploded) trip1, then any super-trip of trip1 is invalid, too. Based on the pruning strategy 1, we can prune the trips which contain any invalid trip to reduce the calculations.
  2. Given an place set A, A is not a valid trip set if the trip time is greater than the travel time constraint.

Approach

  1. Find the candidate place set: starting from 1-place-set, 2-place-set (#2 permutation) ... , n-place-set (#n combination), we find all valid trip permutation and remove all the invalid trip and its super-trip permuation (pruning strategy 1).
  2. Filter the valie trip set with pruning strategy 2.
  3. The trip scores of a trip set and its all permutations are the same, so we don't need to check the permutations which satisifies the travel time constraint.

This is my note for Discrete Optimization in Coursera (https://class.coursera.org/optimization-002)


Greedy Algorithm Intuition

What is Greedy? Build a solution by picking itmes one at a time in greedy fasion.

Idea 1: more items are best.

Start with small ones and take as many as you can.

Idea 2: valuable items are best.

Start with the most valuable items.

Idea 3: value density!

Calculate dollars per kilogram.


Greedy Algorithm

  • For one problem, there are many possible greddy algorithms. Some will do better than others. (Take a look at above ideas)
  • Idea: Take the most valuable items first. And the next valuable item that can fit into a knapsack.
  • Advantages:
    1. Quick to design and implement the algorithm.
    2. It can be very fast to model the problem.
  • Problems:
    1. No quality guarantees (in general). You don't know much you can improve the algorithm, you don't know how good they are.
    2. Quality can vary widely on the input.

Summary of Greedy Algorithm:

Try to understand what the problem is. Get a base line, that's what you have to improve and then afterwards you going to use some of the techniques that we will present:

  • Constraint Programming
  • Local Searching
  • Mixed Integer Programming To improve the greedy algorithm and find out how much you can improve.

Modeling

How to formalize an optimization task as a mathematical model. This is the key to solve the optimal problem.

How to model an optimization problem

  1. Describe the problem
  2. Choose some decision variables
  3. Express the problem constraints in term of there variables
  4. Express the objective function ( the quality of the solution )
  5. There may be many ways to model an optimization problem.

Modeling the knapsack problem

  1. Describe the problem:
    • For each i in Item, has weight Wi and value Vi.
    • We have a knapsack which capacity is K.
    • We have to find the subset of Item which value is maximum and summation of weight is less than or equal to K.
  2. Choose some decision variables:
    • Xi is item i is selected or not
  3. Express the problem constraints in term of there variables:
  4. Express the objective function ( the quality of the solution ) is maximum and be subject to
  5. There may be many ways to model an optimization problem.

Dynamic Programming

Basic Principle:

  • divide and conquer
  • bottom up computation

Define the problem:

  • Item selection I = { 1, 2, 3 ...... n }
  • O( k, j ) is the optimal solution of capacity K of Item[ 1 ... j ] s.t.

maximize

and subject to

Recurrence relation

  • Before we want to solve O( k, j ), we solve sub-problemO( k, j - 1 ) first.
    O( k, j ) = max( O( k, j - 1 ), O( k - Wj, j - 1 ) + Vj ) if Wj <= K    // 第一個是不拿j, 第二個是拿j
    O( k, j ) = O( k, j - 1 ) if Wj > K  // 超重不拿j
    O( k, 0 ) = 0   // 什麼都不拿,價值就為零。
    

以下多機率公式,會看得眼花撩亂,請確保自己清醒後再來看。
如果公式位置錯亂或是沒有顯示,就多重新整理幾次。

前情提要

貝式分類器,擁有幾項特點:

  1. 基於機率型分類(probabilistic classification
  2. 使用貝氏定理來做計算。
  3. 假設特徵之間事件獨立(independence)。
  4. 最常用於文件自動分類的應用上。

所建立出來簡單且有效的分類演算法,以下我們一樣使用新聞分類來作為演算法範例,主要目標為將新聞依照內容描述來自動分類為汽車(C)運動(S)科技(T)


演算法思路

貝氏定理

一切都從條件機率開始說起,我們說B事件發生的條件下發生A事件的機率公式如下:

現在把「B事件發生的條件下發生A事件的機率」和「A事件發生的條件下發生B事件的機率」公式寫在一起,然後做個公式位移:

把 (1) 和 (2) 公式調整一下

最後把P(B ∩ A)帶入置換我們一開始說的P(A|B)公式,就可以導出貝氏定理:

這個公式也可解讀成下列意思:

  • prior probability: 先驗機率,P(A)是在觀察特徵或證據「前」,不考慮任何事件B的因素,能表達事件A的機率分佈。
  • posterior probability: 後驗機率,P(A|B)是在觀察特徵或證據「後」,所得到的條件機率。

貝氏分類

回歸到貝氏分類,我們該如何應用貝氏定理還幫我們執行分類的工作呢??
我們剛剛提的「後驗機率」可以解釋成

給定一些觀察特徵值,我們能計算事物是屬於某個分類的機率。

上述的觀察特徵值我們可以把表示成一個向量,對於新聞分類這問題,我們可以把特徵關鍵字字詞頻率表示成向量:

如果你對於「特徵關鍵字字詞頻率」陌生,可以參考我寫的KNN分類演算法裡面的「前置作業」篇幅。

我們現在的問題是要把新聞自動分類,那麼「後驗機率」就可以說成

給定一些特徵關鍵字字詞頻率向量,我們能計算這篇新聞是屬於某個分類的機率。

寫成貝氏定理的公式就是

換成實際的例子就是

中文解釋就是

在出現「賓士, 寶馬, 籃球, 路跑, 手機, App」這些特徵關鍵字的情況下,該篇新聞是屬於「汽車」的機率是多少?

會等於

在「汽車」新聞當中出現「賓士, 寶馬, 籃球, 路跑, 手機, App」字詞的機率 x 
「汽車」新聞的機率 / 「賓士, 寶馬, 籃球, 路跑, 手機, App」字詞的機率。

上面字過長,滑鼠往右拉。

訓練階段

貝氏分類器的訓練階段是計算

這個算式的數值就要從訓練集合而來,我們要準備各個分類(汽車、運動、科技)的數篇新聞集合,然後做切字並且比對計算特徵關鍵字字詞頻率向量。

新聞 分類 賓士 寶馬 籃球 路跑 手機 App
C63發表會 P 15 25 0 5 8 3
BMW i8 P 35 40 1 3 3 2
林書豪 S 5 0 35 50 0 0
湖人隊 S 1 5 32 15 0 0
Android 5.0 T 10 5 7 0 2 30
iPhone6 T 5 5 5 15 8 32

這邊我已經沒有寫P(特徵關鍵字字詞頻率向量),因為比較不同分類之間的後驗機率時,分母P(特徵關鍵字字詞頻率向量)總是常數,因此可以忽略

獨立事件

實際上,即便有了各分類的新聞集合,我們也很難計算P(特徵關鍵字字詞頻率向量|分類),也就是很難計算

所以要引進貝氏分類最重要的「獨立事件」假設,所謂獨立事件就是一個事件A的結果不會影響另一個事件B發生的機率,舉個例子,給予兩個公正的硬幣,投擲硬幣兩次,那麼第一次投擲的結果不影響第二次投擲的機率。 兩個獨立事件發生的機率就會變成兩個事件機率的乘積。

回到我們的P(特徵關鍵字字詞頻率向量|分類),我們 假設每個分類下的各個特徵關鍵字出現的機率彼此獨立,所以公式可以寫成:

字詞分佈模式

這邊我們有兩個字詞分佈模式,分別為:

  • Bernouli: 只判斷字詞是否有出現,就出現就是1,沒有出現就是0。
    • P(分類) = 該分類新聞篇數 / 所有訓練集合新聞篇數
    • P(特徵關鍵字|分類) = (該分類下包含特徵關鍵字的新聞篇數 + 1) / (該分類下包含特徵關鍵字的新聞篇數 + 2)
  • Multinomial: 直接採用字詞出現頻率。
    • P(分類) = 該分類下字詞頻率總和 / 所有訓練集合字詞頻率總和
    • P(特徵關鍵字|分類) = (該分類下、該關鍵字字詞頻率總和 + 1) / (該分類下所有關鍵字字詞頻率總和 + 訓練集合關鍵字個數)

以下我們都採用Multimonimal來計算。

這邊有一個議題可以探討:不同的字詞分佈模式是否會影響我們最後分類的準度呢??


計算步驟

我們開始先訓練分類器,這邊只用「汽車」分類當作例子,其他分類計算方式類似,各個特徵關鍵字的分類機率如下

訓練階段完成,這些數值等等會使用到。
現在有一篇新的新聞,其特徵關鍵字字詞頻率

地點 分類 賓士 寶馬 籃球 路跑 手機 App
騎士隊 ? 10 2 50 56 8 5

我們要計算該篇新聞屬於「汽車」的機率

這些乘積出來的結果就是這篇新的新聞屬於「汽車」的機率。

向下溢位

如果把這個公式的數值給電腦算,應該有99.99999...%的機率算不出來,為何??因為機率小於1,越小的數字會越乘越小,這樣乘下去電腦就產生「向下溢位」的問題,這邊我們要修改一下機率的計算公式,我們把公式兩邊都取 log,指數就變成相乘,原本相乘就變成相加,算出來的就是機率的log值。

注意,這邊我們重點在於比較各分類的機率 大小關係,而非數值本身,所以所有分類機率數值都取log一樣可以比較所屬分類。


結論

  • 貝氏分類對於少量的訓練集合一樣會有不錯的分類準度,它的威力恰好在於小樣本下,專家意見或歷史經驗,也就是所謂的先驗分配,能夠補足小樣本的不足,使得推論能夠進行。
  • 適合用在資料會不斷成長的應用。

其他參考資訊

http://sebastianraschka.com/Articles/2014_naive_bayes_1.html
http://cn.soulmachine.me/blog/20100528/
http://blog.yhathq.com/posts/naive-bayes-in-python.html
http://scikit-learn.org/stable/modules/naive_bayes.html
http://machinelearningmastery.com/better-naive-bayes/