[ML, Python] Adaboost part 2

進入到實作部份, 先稍微整理一下, 用Adaboost要準備三個材料

1. Structured Input Data (意思就是檔案要整理過比較方便)

2. Weak Learner (一個簡單的演算法)

3. Adaboost (演算法主體)

4. 鹽巴一小匙(XD)

其實Adaboost屬於一種meta-algorithm, 白話一點說, 就是他是附加在某一演算法上的演算法

其實那個weak learner, 才是去學習的演算法, Adaboost不過就是強化了他罷了

所以來討論一下傳說中的weak learner
(其實每個演算法都可以當weak learner, 但, 還是不要太強)

實作會參考Machine Learning in Action的範例來使用, 不過會稍微修改
(對了這是一本好書, 想學ML實作的人應該都去買來看看)

Decision Stump

首先最常見的是Decision Stump

Decision Stump Paper: http://lyonesse.stanford.edu/~langley/papers/stump.ml92.pdf
(92'年的ICML paper)

Decision Stump wiki: http://en.wikipedia.org/wiki/Decision_stump

通常的解釋就是他是只有一層的 Decision Tree (哎呀這好像我還沒講過XD)

簡單講就是, 他判斷準則很單純, 只看一個 feature (1-rule), 就針對一個 feature 去判定

假設今天有一組 training set, 某個 feature 分別是2, 4, 7, 8, 然後要在這之中找一個點分出這些data

例如如果2 跟 4是 class 1, 7 跟 8是 class -1

那我只要找再4~7中間的點, 例如5, 說小於5是1, 大於5是-1, 就ok啦

當然說的很簡單, 實作就會稍微麻煩了一點點

為了之後要用Adaboost的角度下, 我們也假設一下這些training set有weight

當然目前角度下樣本皆生而平等, 所以如果有m筆, 那每筆資料的weight初值就是 1/m 啦

所以流程很簡單, 拿到training set, 有多少筆資料 (m), 有多少features (n)

從第1個feature慢慢跑到第n筆, 每個feature都要經過DS判斷

針對DS對於每個feature的判斷, 做的事情也很簡單, 前面我是知道1 or -1, 所以我知道切在哪邊判斷

再來, 其實要切哪邊很難判定是最好, 所以乾脆每個點都切切看, 然後看結果來說話

也就是說, 如果今天最大是8, 最小2, 我就切個十份(11筆)好了
(你要切百份也不是不可以, 花時間罷了)

2, 2.6, 3.2, 3.8, 4.4, 5, 5.6, 6.2, 6.8, 7.2, 8

我從這十份開始去比較看切在哪個點, 整個training set正確率比較高, 我就選哪個點

實作上這邊其實可能可以加考慮兩個點, 1.4跟8.6, 因為有可能真正的邊界是大於最大或者小於最小

保險一點就多加兩個點進來判斷, 注意, 算錯誤的時候要把weight也跟著算上去, 這點其實不是DS所必需的, 只是為了配合後續的Adaboost

下面我範例拿的是Machine Learning in Action中的Adaboost那章

此本書作者使用了python numpy (BSD License)來幫忙coding,

numpy請google查一下相關資料 (http://www.numpy.org/)

def buildStump(dataArr,classLabels,D):
    dataMatrix = mat(dataArr); labelMat = mat(classLabels).T
    # numpy的mat可以把python的list轉成數學上的matrix格式
    # dataMatrix為training set, labelMat為training set的class label

    m,n = shape(dataMatrix)
    # shape是算出matrix維度, m在這邊實際上就是筆數, n就是feature數量

    numSteps = 10.0; bestStump = {}; bestClasEst = mat(zeros((m,1)))
    # numSteps就是上面所提的, 切成10等份共11份來找
    # numpy.zeros(m, n) 會組成一個零矩陣 m x n

    minError = inf 
    # 最後會選錯誤率最低的Stump, 這邊先設定成最大, numpy有inf變數意思為無窮大的值

    # 所以就開始一個一個feature開始跑
    for i in range(n):
        rangeMin = dataMatrix[:,i].min(); rangeMax = dataMatrix[:,i].max();
        # 找出此feature的最大值ˊ, 最小值

        stepSize = (rangeMax - rangeMin) / numSteps
        # 根據前面設定的步數設定出等一下要切的數量

        for j in range(-1, int(numSteps) + 1):
            # 那判斷有兩個方向, 一個是比大, 一個比小, 這邊他有把邊界最小直納入考量, 最大反而沒有
            for inequal in ['lt', 'gt']:
                threshVal = (rangeMin + float(j) * stepSize)
                # 這邊只是計算一下現在是判斷到哪一個切割點

                predictedVals = stumpClassify(dataMatrix,i,threshVal,inequal)
                # 這就是把training set, 哪一個feature, 切割點, 比大還是比小傳入stumpClassify

                errArr = mat(ones((m, 1)))
                # 設定錯誤的vector, 先假設都1, 都錯的初始

                errArr[predictedVals == labelMat] = 0 
                # 有猜對的話, 就改成為0

                weightedError = D.T * errArr
                # 算錯誤率, 要乘上weight
                print "split: dim %d, thresh %.2f, thresh ineqal: %s, the weighted error is %.3f" % (i, threshVal, inequal, weightedError)
                if weightedError < minError:
                    # 找哪個是最好的Decision Stump切割
                    minError = weightedError
                    bestClasEst = predictedVals.copy()
                    bestStump['dim'] = i 
                    bestStump['thresh'] = threshVal
                    bestStump['ineq'] = inequal
    return bestStump,minError,bestClasEst

下面是stumpClassify的function

基本上剩餘的功夫就是真的去判斷training set哪些值大於/小於切割點

# 這個function判斷完切割點之後, 就會猜測這是1 or -1, 也就是class label, 然後會把猜測的回傳
def stumpClassify(dataMatrix,dimen,threshVal,threshIneq):
    retArray = ones((shape(dataMatrix)[0],1))
    # 先設定猜測每筆都是1, 只是設定初值而已, 別太在意

    if threshIneq == 'lt':
        retArray[dataMatrix[:,dimen] <= threshVal] = -1.0
        # 這個就只是判斷值有沒有小於等於切割點, 有的話就是-1
    else:
        retArray[dataMatrix[:,dimen] > threshVal] = -1.0
    return retArray

給個書上設定的參數, 會回傳training set & label

def loadSimpData():
    datMat = matrix([[ 1. , 2.1],
        [ 2. , 1.1],
        [ 1.3, 1. ],
        [ 1. , 1. ],
        [ 2. , 1. ]]) 

    classLabels = [1.0, 1.0, -1.0, -1.0, 1.0]
    return datMat,classLabels

簡單呼叫一下就可以看到結果了

t, l = loadSimpData()
m = shape(t)[0]
D = mat(ones((m,1))/m)
print buildStump(t, l, D)

跑之前先判斷一下, 有兩個feature

第一個最大2, 最小1, 從0.9判斷到2, 要比大跟小, 所以會輸出20筆資料

第二個最大2.1, 最小1, 從0.89判斷到2.1, 要比大跟小, 也會輸出20筆資料

split: dim 0, thresh 0.90, thresh ineqal: lt, the weighted error is 0.400
split: dim 0, thresh 0.90, thresh ineqal: gt, the weighted error is 0.600
split: dim 0, thresh 1.00, thresh ineqal: lt, the weighted error is 0.400
split: dim 0, thresh 1.00, thresh ineqal: gt, the weighted error is 0.600
split: dim 0, thresh 1.10, thresh ineqal: lt, the weighted error is 0.400
split: dim 0, thresh 1.10, thresh ineqal: gt, the weighted error is 0.600
split: dim 0, thresh 1.20, thresh ineqal: lt, the weighted error is 0.400
split: dim 0, thresh 1.20, thresh ineqal: gt, the weighted error is 0.600
split: dim 0, thresh 1.30, thresh ineqal: lt, the weighted error is 0.200
split: dim 0, thresh 1.30, thresh ineqal: gt, the weighted error is 0.800
split: dim 0, thresh 1.40, thresh ineqal: lt, the weighted error is 0.200
split: dim 0, thresh 1.40, thresh ineqal: gt, the weighted error is 0.800
split: dim 0, thresh 1.50, thresh ineqal: lt, the weighted error is 0.200
split: dim 0, thresh 1.50, thresh ineqal: gt, the weighted error is 0.800
split: dim 0, thresh 1.60, thresh ineqal: lt, the weighted error is 0.200
split: dim 0, thresh 1.60, thresh ineqal: gt, the weighted error is 0.800
split: dim 0, thresh 1.70, thresh ineqal: lt, the weighted error is 0.200
split: dim 0, thresh 1.70, thresh ineqal: gt, the weighted error is 0.800
split: dim 0, thresh 1.80, thresh ineqal: lt, the weighted error is 0.200
split: dim 0, thresh 1.80, thresh ineqal: gt, the weighted error is 0.800
split: dim 0, thresh 1.90, thresh ineqal: lt, the weighted error is 0.200
split: dim 0, thresh 1.90, thresh ineqal: gt, the weighted error is 0.800
split: dim 0, thresh 2.00, thresh ineqal: lt, the weighted error is 0.600
split: dim 0, thresh 2.00, thresh ineqal: gt, the weighted error is 0.400
split: dim 1, thresh 0.89, thresh ineqal: lt, the weighted error is 0.400
split: dim 1, thresh 0.89, thresh ineqal: gt, the weighted error is 0.600
split: dim 1, thresh 1.00, thresh ineqal: lt, the weighted error is 0.200
split: dim 1, thresh 1.00, thresh ineqal: gt, the weighted error is 0.800
split: dim 1, thresh 1.11, thresh ineqal: lt, the weighted error is 0.400
split: dim 1, thresh 1.11, thresh ineqal: gt, the weighted error is 0.600
split: dim 1, thresh 1.22, thresh ineqal: lt, the weighted error is 0.400
split: dim 1, thresh 1.22, thresh ineqal: gt, the weighted error is 0.600
split: dim 1, thresh 1.33, thresh ineqal: lt, the weighted error is 0.400
split: dim 1, thresh 1.33, thresh ineqal: gt, the weighted error is 0.600
split: dim 1, thresh 1.44, thresh ineqal: lt, the weighted error is 0.400
split: dim 1, thresh 1.44, thresh ineqal: gt, the weighted error is 0.600
split: dim 1, thresh 1.55, thresh ineqal: lt, the weighted error is 0.400
split: dim 1, thresh 1.55, thresh ineqal: gt, the weighted error is 0.600
split: dim 1, thresh 1.66, thresh ineqal: lt, the weighted error is 0.400
split: dim 1, thresh 1.66, thresh ineqal: gt, the weighted error is 0.600
split: dim 1, thresh 1.77, thresh ineqal: lt, the weighted error is 0.400
split: dim 1, thresh 1.77, thresh ineqal: gt, the weighted error is 0.600
split: dim 1, thresh 1.88, thresh ineqal: lt, the weighted error is 0.400
split: dim 1, thresh 1.88, thresh ineqal: gt, the weighted error is 0.600
split: dim 1, thresh 1.99, thresh ineqal: lt, the weighted error is 0.400
split: dim 1, thresh 1.99, thresh ineqal: gt, the weighted error is 0.600
split: dim 1, thresh 2.10, thresh ineqal: lt, the weighted error is 0.600
split: dim 1, thresh 2.10, thresh ineqal: gt, the weighted error is 0.400
({'dim': 0, 'ineq': 'lt', 'thresh': 1.3}, matrix([[ 0.2]]), array([[-1.],
       [ 1.],
       [-1.],
       [-1.],
       [ 1.]]))

輸出資料一大堆, 可以看到最後一行有結果, 那從輸出來看

第一個feature最好頂多0.2, 在切割點 1.3, 1.4, 1.5, 1.6, 1.8 的lt效果最好 (這樣取最小的1.3即可)

第二個feature最好頂多0.2, 在切割點 1 的lt效果最好, 但是因為沒有比第一個好, 所以所以不採取

所以這個Decision Stump就跟你說, 在這個data之下, 你選第一個feature判斷就好

只要大於1.3就說1, 小於就說 -1, 就只會錯第一筆喔!!

不過, 也看得出他很笨, 只會看一個feature, 其餘都不太在乎, 這樣能力相當的弱

所以, 接下來才準備要開始進入Adaboost來強化他!!!

Adaboost

回到adaboost, 回想一下Adaboost流程

1. 收到data, 設定好要跑幾次weak learner

2. 叫weak learner去學習一下

3. 根據結果調整weight (依據公式修改, 九成的程式碼都在這邊)

4. 回到第2步繼續做, 第3的推導上一篇文章都有提過了

5. 回傳結果, 打完收工, 簡單到爆

來看一下Code, 預設了跑40回合weak leaner, 傳入的時候修改成其他回合會比較容易看到效果

def adaBoostTrainDS(dataArr,classLabels,numIt=40):
    weakClassArr = []
    # 用來存放等會每回合會產生的weak learner

    m = shape(dataArr)[0]
    D = mat(ones((m,1))/m)
    aggClassEst = mat(zeros((m,1)))
    for i in range(numIt):
        bestStump,error,classEst = buildStump(dataArr,classLabels,D)
        # 呼叫weak learner, classEst就是ht(xi

        print "D:",D.T
        alpha = float(0.5 * log((1.0 - error) / max(error,1e-16)))
        # alpha 的公式

        bestStump['alpha'] = alpha
        weakClassArr.append(bestStump)
        # 將學好的存起來

        print "classEst: ",classEst.T
        expon = multiply(-1 * alpha * mat(classLabels).T, classEst)
        # 不要被這串嚇到了, 就只是 -α * y * h(x)

        D = multiply(D, exp(expon))
        # 然後跟原本的distribution相乘, 也就是D * -α * y * h(x)

        D = D / D.sum()
        # 除掉Zt, 就完成了更新

        aggClassEst += alpha*classEst
        # 把已經學過得weak learner合體

        print "aggClassEst: ",aggClassEst.T

        aggErrors = multiply(sign(aggClassEst) != mat(classLabels).T,ones((m,1)))
        # 合體後的learner的結果

        errorRate = aggErrors.sum()/m
        print "total error: ",errorRate,"\n"

        if errorRate == 0.0: break
        # 如果training error 0就可以停了, 然後傳出classifier

    return weakClassArr

不難吧, 只是把公式套入程式碼而已, 一點都不難(打這些到網誌上好麻煩到是真的XDD)


一樣簡單呼叫一下就可以看到結果了

t, l = loadSimpData()
m = shape(t)[0]
D = mat(ones((m,1))/m)

classifierArray = adaBoostTrainDS(t, l, 9)
print classifierArray

結果

D: [[ 0.2  0.2  0.2  0.2  0.2]]
classEst:  [[-1.  1. -1. -1.  1.]]
aggClassEst:  [[-0.69314718  0.69314718 -0.69314718 -0.69314718  0.69314718]]
total error:  0.2 

D: [[ 0.5    0.125  0.125  0.125  0.125]]
classEst:  [[ 1.  1. -1. -1. -1.]]
aggClassEst:  [[ 0.27980789  1.66610226 -1.66610226 -1.66610226 -0.27980789]]
total error:  0.2 

D: [[ 0.28571429  0.07142857  0.07142857  0.07142857  0.5       ]]
classEst:  [[ 1.  1.  1.  1.  1.]]
aggClassEst:  [[ 1.17568763  2.56198199 -0.77022252 -0.77022252  0.61607184]]
total error:  0.0

[{'dim': 0, 'ineq': 'lt', 'thresh': 1.3, 'alpha': 0.6931471805599453}, {'dim': 1, 'ineq': 'lt', 'thresh': 1.0, 'alpha': 0.9729550745276566}, {'dim': 0, 'ineq': 'lt', 'thresh': 0.90000000000000002, 'alpha': 0.8958797346140276}]

稍微解釋一下, 這才跑了三個weak leaner就結束了

第一個weak learner跟講decision stump是一樣的

第二個根據第一個做了點修正, 第三個修正更多, 直接就解決掉了整個training set

仔細看各點的distribution是不是上一回猜對就下降, 下一回猜錯就上升~!

雖然decision stump能力不強, 只會看一個維度, 但是配合著adaboost就可以達到相當不錯的結果

最後一行的意思

第一個 DS 在第一個feature 1.3 那邊切了一刀

第二個 DS 在第二個feature 1.0 切了一刀

第三個 DS 在第一個feature 0.9 又切了一刀

組合這三個結果剛好可以分出這個 training set 的 1 or -1

白話一點講, 要使用也就依照上面流程, 今天進來一筆資料,

1. 把資料跟 feature 0, threshold: 1.3 跟 lt 給DS判斷

2. 把資料跟 feature 1, threshold: 1.0 跟 lt 給DS判斷

3. 把資料跟 feature 0, threshold: 0.9 跟 lt 給DS判斷

三個剩上相對的alpha然後取sigh就知道是1 or -1啦

以下就是這白話的程式碼

def adaClassify(datToClass,classifierArr):
    # dataMatrix就是要被classifiy的data

    dataMatrix = mat(datToClass)
    # 其實這意思就是, 你可以傳不只一筆資料進來

    m = shape(dataMatrix)[0]
    aggClassEst = mat(zeros((m,1)))

    for i in range(len(classifierArr)):
        classEst = stumpClassify(dataMatrix,classifierArr[i]['dim'], classifierArr[i]['thresh'], classifierArr[i]['ineq'])
        # 就是把傳入資料, feature, threshold, 跟lt or gt傳入

        aggClassEst += classifierArr[i]['alpha'] * classEst
        # 配合著相對的alpha把結果都加起來

        print aggClassEst

    return sign(aggClassEst)
    # 傳回猜測答案

來看一下使用

t, l = loadSimpData()
m = shape(t)[0]
D = mat(ones((m,1))/m)

classifierArray = adaBoostTrainDS(t, l, 9)

guess = adaClassify([0, 0],classifierArray

print "Class:", guess

結果

[[-0.69314718]] <- 負
[[-1.66610226]] <- 更負
[[-2.56198199]] <- 更負
Class: [[-1.]]

所以會出現結果是 -1 class, 印出的過程是會發現, 這筆資料一直往負的發展, 有很高機率是-1

那你可以做的事情就是,  classifierArray存起來, 以後要用的時候在讀出, 存起來這東西就變成常見的model檔案

一個簡單的ML演算法就完成了

下次應該會來介紹Logistic or Bayes or Decision Tree....