Posts match “ 分類演算法 ” tag:

這篇內容多謝了我的好友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值如何取」、「如何提升計算效能」...等等,這些都有一些相關的書籍或論文都有探討,有興趣研究的可以自行搜尋。