多類別分類器實作-OVO演算法

上次使用了logistic完成了產生簡易版二元分類器實作
這次想挑戰多類別的Python實作,多類別分類的議題可以參考如下網址:

https://en.wikipedia.org/wiki/Multiclass_classification

上面網址介紹了兩個算是蠻容易理解實作的多類別分類器,這兩個演算法都是基於二元分類器模擬出多元分類的效果

One-vs.-rest(OVR or OVA)

OVA演算法假設有N筆資料,且有K個類別,針對每個類別產生一個二元分類器
假設今天有蘋果,香蕉,橘子三種水果的分類
那就會有三種分類器產生

  1. 是不是蘋果
  2. 是不是香蕉
  3. 是不是橘子

然後對於預測的時候就是把資料丟進三個分類器,看哪個分類器預測的分數最高決定他的類別

演算法兩個部分

  1. 針對K的類別產生K個二元分類器
  2. 進行預測時所有個二元分類器都預測一次,對於說”是“的分類器,選出分數最高的當作預測類別

這個演算法的問題在於當類別數量很多,K很大的時候,會有資料嚴重不平衡的情況
這樣的情形就是會讓每個二元分類器很容易說出“不是“這個答案,分類問題也可能變得曖昧
可能全部的分類器都說”不是“,造成無人認領

One-vs.-one(OVO)

而今天要實作的OVO演算法,設有N筆資料,且有K個類別
則將所有類別兩兩比較,也就是想辦法產生個排列組合的二元分類器
三個類別就會有三個分類器,四個類別會有六個,依此類推
該二元分類器回答不再是”是不是“,而是輸出自己可以分類的“兩個類別其中一個”
最後用再讓所有的分類器進行”投票“,最高票當選,這種方法可以降低上面OVA演算法的不平衡問體

在以上面蘋果,香蕉,橘子分類問題舉例,會產生下面三種二元分類器

  1. 是蘋果還是香蕉
  2. 是蘋果還是橘子
  3. 是香蕉還是橘子

今天一個新的水果X過來了,1號說是香蕉,2號說是橘子,3號說是橘子
最後OVO演算法的預測X會是橘子,至於平手的場合,那就隨機挑一個當答案

演算法步驟如下

  1. 針對K個類別兩兩一對產生個二元分類器
  2. 讓所有的分類器進行投票產生預測結果

上面兩個演算法都是用二元分類器當作基底,因此只要是還不錯的二元分類演算法
就能用上面兩種方法當作”樣板“去組合成多元分類器

OVO演算法實作如下:
原始碼:https://github.com/del680202/MachineLearning-memo/blob/master/src/lr/ovo-alogrithm.py

先行準備三個類別的資料,作多類別分類

class1 = [(1, 0.7, 7.6), (1, 1.2, 9.5), (1, 2.3, 9.1), (1, 1.5, 8.4)]
class2 = [(1, 7.6, 0.7), (1, 9, 1.9), (1, 8.1, 3), (1, 7.1, 2.2)]
class3 = [(1, 6, 9.1), (1, 8, 7.8), (1, 8.1, 9), (1, 8.2, 9.2)]
dataset = [(class1, 'bo'), (class2, 'rx'), (class3, 'g*')]

plt.plot([v[1] for v in class1 ], [v[2] for v in class1 ],'bo')
plt.plot([v[1] for v in class2 ], [v[2] for v in class2 ],'rx')
plt.plot([v[1] for v in class3 ], [v[2] for v in class3 ],'g*')
plt.xlim(0, 12)
plt.ylim(0, 12)
plt.show()

畫出來後如下

OVO演算法實作

#接受類別資料跟二元分類器當作參數

def ovo(dataset, binary_classifier):
    #把所有類別的資料兩兩一對,產生CK取2個組合

    training_class_set = itertools.combinations(dataset, 2)
    classifier_set = []
    for pair_class in training_class_set:
        c1, c2 = pair_class
        training_data = [ (v, 1) for v in c1[0]]
        training_data += [ (v, 0) for v in c2[0]]
        #對每組資料分類並記錄每個類別代表的lable

        classifier = (binary_classifier(training_data), (c1[1], c2[1]))
        classifier_set += [classifier]

    #回傳一個基於上面產生的一堆二元類別分類器的投票函式

    def vote(data):
         result = []
         for classifier, labels in classifier_set:
             if classifier.T.dot(data) > 0:
                 result += [labels[0]]
             else:
                 result += [labels[1]]
         count_map = {}
         for r in result:
             count_map[r] = count_map.get(r, 0) + 1
         #選出最高票的進行回傳

         return sorted(count_map.items(), key=lambda x: x[1], reverse=True)[0][0]
    return vote
    
#這邊選定前一章實作的logistic當作二元分類器

multiple_classifier = ovo(dataset, logistic)

上面實作出來之後就可以針對K種類別作多元分類器

來做個驗證

今天準備了三筆還不知道類別的資料

test_data = [(1, 10, 10), (1, 1.5, 10), (1, 10, 1.5)]
for data in test_data:
    plt.plot(data[1], data[2], 'k.')
plt.xlim(0, 12)
plt.ylim(0, 12)
plt.show()

分佈畫出來如下圖

資料的X特意經過設計可以好好分出來
最後用剛剛產生的多元分類器進行分類看看上面三筆資料的分類結果

for data in test_data:
    label = multiple_classifier(data) #預測資料代表的類別為何

    plt.plot(data[1], data[2], label)
plt.xlim(0, 12)
plt.ylim(0, 12)
plt.show()

畫出來結果如下

資料雖然是特別設計過的,但是得到的結果還算滿意
相比二元分類依賴的一堆數學公理,多元分類演算法,反而是一般工程師比較能輕鬆理解的

comments powered by Disqus