Posts match “ classification ” tag:

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

前情提要

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

  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/

這篇內容多謝了我的好友Bob Lu協助我理解kNN演算法才能完成。

前情提要

今天要來講一個非常容易理解的分類演算法,叫做kNN (K Nearest Neighbor),此演算法在2007年IEEE統計排名前十名資料採礦演算法之一,以目前來說是廣泛使用、非常有效而且是易於掌握的演算法。

以下我們使用新聞分類來作為演算法範例,主要目標為將新聞依照內容描述來自動分類為汽車(C)運動(S)科技(T)


演算法思路

kNN分類演算法簡單來說就是要找和新數據最近的K個鄰居,這些鄰居是什麼分類,那麼新數據就是什麼樣的分類。


現在給定一個特徵樣本 (我們稱為訓練集合),我們輸入一個新樣本要把一個該樣本分藍色、紅色,我們可以從訓練集合找跟這新樣本距離最近的K個特徵樣本,看這些K個點是什麼顏色,來決定該點的最終顏色。


原本藍色、紅色的點為特徵樣本 (訓練集合),問號點為新樣本,我們設定K=5,即要找跟新樣本距離最近的K=5個特徵點,藍色一個、紅色四個,所以我們可以決定新樣本會是紅色


實作步驟

前置作業

首先,我們要找特徵跟準備特徵樣本!!讓我們先理解這兩個名詞是什麼:

  1. Q: 什麼叫特徵 (Feature)?? A: 特徵就是那些能讓我們判斷分類的屬性,例如我們要分類男生、女生,一般是用是否有喉結、生殖器的不同來判斷,那麼有喉結、有生殖器就是我們所稱的特徵。
  2. Q: 什麼叫特徵樣本 (訓練集合Train Set)?? A: 由特徵值和正確分類組成的集合,例如: (有喉結 = 男), (有小鳥 = 男),這個集合用來告訴機器哪些特徵數據它的分類是什麼,讓機器可以去做學習。

對於新聞分類這問題,我們就可以找一些關鍵字作為各分類的特徵,我們稱做特徵關鍵字 (Feature Keywords),這邊我們找的特徵關鍵字如下:

分類 關鍵字
汽車C 賓士 寶馬
運動S 籃球 路跑
科技T 手機 App

接著,我們先找分類正確的新聞,而每則新聞都有內文,我們把內文去做切字,比對特徵關鍵字、找出該字詞出現的頻率,最後形成一個特徵關鍵字字詞頻率向量 (以下用TF向量簡稱),每個TF向量再給它加上正確的分類,形成我們的特徵樣本如下:

新聞 分類 賓士 寶馬 籃球 路跑 手機 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

訓練集合準備完成。

這些向量就是上圖的藍色、紅色的點。

新的先文輸入後一樣找出TF向量,但是我們不曉得正確的分類為何,等等跑完kNN分類後才會知道結果(廢話)。

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

這個向量就是上圖的問號點。

計算階段

分類演算法就是要先找和新樣本 騎士隊 距離最近K個特徵樣本,這邊距離就是TF向量的距離,我們用 Cosine Similarity 作為距離計算公式,公式如下圖,即是向量的內積除以向量的長度。

對於我們來說就是要計算 騎士隊C63發表會iPhone6 所有TF向量距離。

這邊我們計算完所有向量距離並排序後分別為:

計算完所有向量距離後,我們要找出K=3,3個距離最短的向量距離,然後分別看他們的分類為何,來決定最後新地點的分類。


程式

  1. 首先第一步我們先準備好特徵樣本(訓練集合)。

    def create_trainset():
    """
    產生訓練集合。
    :return:
    """
    trainset_tf = dict()
    trainset_tf[u'C63發表會'] = (15, 25, 0, 5, 8, 3)
    trainset_tf[u'BMW i8'] = (35, 40, 1, 3, 3, 2)
    trainset_tf[u'林書豪'] = (5, 0, 35, 50, 0, 0)
    trainset_tf[u'湖人隊'] = (1, 5, 32, 15, 0, 0)
    trainset_tf[u'Android 5.0'] = (10, 5, 7, 0, 2, 30)
    trainset_tf[u'iPhone6'] = (5, 5, 5, 15, 8, 32)
    
    trainset_class = dict()
    trainset_class[u'C63發表會'] = 'P'
    trainset_class[u'BMW i8'] = 'P'
    trainset_class[u'林書豪'] = 'S'
    trainset_class[u'湖人隊'] = 'S'
    trainset_class[u'Android 5.0'] = 'T'
    trainset_class[u'iPhone6'] = 'T'
    
    return trainset_tf, trainset_class
    
  2. 計算Cosine similarity公式

    def cosine_similarity(v1, v2):
    """
    計算兩個向量的正弦相似度。距離越近,相似度數值會越高。
    :param v1:
    :param v2:
    :return:
    """
    sum_xx, sum_xy, sum_yy = 0.0, 0.0, 0.0
    for i in range(0, len(v1)):
        sum_xx += math.pow(v1[i], 2)
        sum_xy += v1[i] * v2[i]
        sum_yy += math.pow(v2[i], 2)
    
    return sum_xy / math.sqrt(sum_xx * sum_yy)
    
  3. 執行分類演算法

    def knn_classify(input_tf, trainset_tf, trainset_class, k):
    """
    執行kNN分類演算法
    :param input_tf: 輸入向量
    :param trainset_tf: 訓練集合向量
    :param trainset_class: 訓練集合分類
    :param k: 取k個最近鄰居
    :return:
    """
    tf_distance = dict()
    # 計算每個訓練集合特徵關鍵字字詞頻率向量和輸入向量的距離
    
    print '(1) 計算向量距離'
    for place in trainset_tf.keys():
        tf_distance[place] = cosine_similarity(trainset_tf.get(place), input_tf)
        print '\tTF(%s) = %f' % (place, tf_distance.get(place))
    
    # 把距離排序,取出k個最近距離的分類
    
    class_count = dict()
    print '(2) 取K個最近鄰居的分類, k = %d' % k
    for i, place in enumerate(sorted(tf_distance, key=tf_distance.get, reverse=True)):
        current_class = trainset_class.get(place)
        print '\tTF(%s) = %f, class = %s' % (place, tf_distance.get(place), current_class)
        class_count[current_class] = class_count.get(current_class, 0) + 1
        if (i + 1) >= k:
            break
    
    print '(3) K個最近鄰居分類出現頻率最高的分類當作最後分類'
    input_class = ''
    for i, c in enumerate(sorted(class_count, key=class_count.get, reverse=True)):
        if i == 0:
            input_class = c
        print '\t%s, %d' % (c, class_count.get(c))
    print '(4) 分類結果 = %s' % input_class
    

主程式

if __name__ == '__main__':
    input_tf = (10, 2, 50, 56, 8, 5)
    trainset_tf, trainset_class = create_trainset()
    knn_classify(input_tf, trainset_tf, trainset_class, k=3)

完整程式可以從Github下載。

程式執行結果如下

(1) 計算向量距離
    TF(湖人隊) = 0.902367
    TF(BMW i8) = 0.167385
    TF(Android 5.0) = 0.249728
    TF(iPhone6) = 0.483053
    TF(C63發表會) = 0.237799
    TF(林書豪) = 0.983887
(2) 取K個最近鄰居的分類, k = 3
    TF(林書豪) = 0.983887, class = S
    TF(湖人隊) = 0.902367, class = S
    TF(iPhone6) = 0.483053, class = T
(3) K個最近鄰居分類出現頻率最高的分類當作最後分類
    S, 2
    T, 1
(4) 分類結果 = S

經過計算分類後我們可以知道「騎士隊」的分類是屬於S,也就是運動。(這邊我們不討論真實狀況,因為計算都非真實數據)


結論

  • kNN分類演算法是一個基於實例(instance-based)的演算法,所以特徵樣本的好壞和樣本當中個分類的數量深深影響分類結果的準度,如果特徵樣本當中的A分類數量遠大於B分類,那麼我們可以預期K個最近距離的鄰居也會有很高的機率是A分類,這樣就會分類失去準度。
  • 整體來說,優點在於簡單、不需要輸入資料的假設、對於異常值不敏感,而缺點在於計算量大、非常耗時,而且因為要載入所有特徵集合加入距離計算,所以記憶體空間用量也非常大。
  • 可探討的議題有「參數K值如何取」、「如何提升計算效能」...等等,這些都有一些相關的書籍或論文都有探討,有興趣研究的可以自行搜尋。