題目

連接：https://www.kaggle.com/c/titanic

簡(jiǎn)析

上一篇用了貝葉斯分類器，這次用決策樹和隨機(jī)森林試一試，不過(guò)最終的得分沒(méi)有貝葉斯分類器高，好吧，說(shuō)實(shí)話，感覺再用幾個(gè)不同的機(jī)器學(xué)習(xí)方法應(yīng)該結(jié)果也差不多，現(xiàn)在主要是試水，先搞懂基礎(chǔ)的算法，然后再通過(guò)數(shù)據(jù)的處理與分析去優(yōu)化結(jié)果。

決策樹

我個(gè)人認(rèn)為，決策樹應(yīng)該是比較好理解的機(jī)器學(xué)習(xí)算法了。其中心思想就是ifelse，存在很多個(gè)條件的時(shí)候，如果第一個(gè)條件是A，第二個(gè)條件是B…………就選擇方案C。是一個(gè)很自然的方法，我們平常生活中也可能很常用，比如下圖就是一個(gè)屌絲假日的日常決策樹：

看起來(lái)是很簡(jiǎn)單的，但是要怎么應(yīng)用到機(jī)器學(xué)習(xí)上，讓它成為一個(gè)分類器呢？以本例中的問(wèn)題來(lái)說(shuō)，我知道每一個(gè)人的生還情況，還有他的各種屬性（特征），我們要根據(jù)這些特征，來(lái)生成一顆決策樹，最終到達(dá)葉子節(jié)點(diǎn)的時(shí)候，我們就知道對(duì)于某一系列的屬性，最終是生還還是死亡，大概就是要生成這樣一棵樹（進(jìn)行了簡(jiǎn)化）：

中間還可以加很多其他屬性，比如艙位信息之類的，最終，在篩完所有信息以后，你就可以通過(guò)當(dāng)前訓(xùn)練數(shù)據(jù)給出一個(gè)概率，表示當(dāng)前葉結(jié)點(diǎn)生還的概率。
接下來(lái)的問(wèn)題是如何實(shí)現(xiàn)，選擇條件的順序是否影響結(jié)果，是不是可以隨便選擇條件呢？當(dāng)然這里樹的結(jié)構(gòu)肯定會(huì)影響最終的結(jié)果，如何去構(gòu)造一棵樹呢？
這里需要用到一個(gè)信息熵的概念。熵這個(gè)東西應(yīng)該大家都聽說(shuō)過(guò)，熵表明的是一個(gè)事物的混亂程度，熵越大，混亂程度越高，熵越小，表明混亂程度越低。信息熵的概念也是一樣的，就是用來(lái)表明信息的混亂程度，我們選擇一個(gè)樹根的時(shí)候，最好的情況肯定是通過(guò)這個(gè)屬性把數(shù)據(jù)分成幾類以后，這些數(shù)據(jù)的熵越小越好，因?yàn)樵叫〈碓接行?，分類越清晰。那么我們要做的就是?jì)算每個(gè)條件作為當(dāng)前的根結(jié)點(diǎn)的信息熵，最終選一個(gè)最小的分類方法作為根節(jié)點(diǎn)，并以此類推，直到葉節(jié)點(diǎn)~
信息熵的計(jì)算公式如下：

其中，m是最終的分類結(jié)果，在本例中，就是生還與否兩個(gè)類，pi是這個(gè)決策（分類）發(fā)生的概率。

隨機(jī)森林

隨機(jī)森林就是決策樹的加強(qiáng)版，決策樹這種方法，雖然有信息熵作為劃分方法，但是實(shí)際上，如果劃分到最精細(xì)的一層，那么就會(huì)出現(xiàn)過(guò)擬合的問(wèn)題，泛化能力就比較差，往往訓(xùn)練數(shù)據(jù)上表現(xiàn)的比較好，對(duì)于新的數(shù)據(jù)，準(zhǔn)確度就會(huì)變低。在我寫的決策樹代碼就出現(xiàn)了這個(gè)問(wèn)題，當(dāng)時(shí)沒(méi)多想，直接分到最后一層，結(jié)果準(zhǔn)確率只有0.57。但是如果不分得更精細(xì)，準(zhǔn)確度也不夠高?？赡苄枰M(jìn)行大量的測(cè)試，才能找到一個(gè)平衡點(diǎn)，既不至于過(guò)擬合，也不至于欠擬合導(dǎo)致準(zhǔn)確率太低。
隨機(jī)森林提供了一個(gè)比較通用的解決方法，就是隨機(jī)生成多個(gè)比較淺的決策樹，當(dāng)進(jìn)行擬合的時(shí)候，讓多個(gè)決策樹進(jìn)行投票，最終哪個(gè)分類的票高就決定是哪個(gè)類。

代碼與結(jié)果

首先是決策樹的代碼，說(shuō)實(shí)話，這代碼寫的比較丑，寫起來(lái)不是很順手，邊學(xué)邊寫，邏輯搞的有點(diǎn)亂。最終準(zhǔn)確率只有0.57416，這個(gè)我認(rèn)為是劃分過(guò)于精細(xì)導(dǎo)致模型過(guò)擬合了，在適當(dāng)?shù)姆种нM(jìn)行剪枝效果可能會(huì)更好，當(dāng)然，也有可能哪里寫出了點(diǎn)小bug（笑）。

import csv
import os
import random
import math

class Node:
    def __init__(self):
        self.attr_name = ""
        self.value_type = ""
        self.classifier = None
        self.childrens = []
        self.entropy = 0

    def getNext(self, value):
        result = 0
        if self.value_type == 'disperse_data':
            pos = 0
            if self.classifier.has_key(value):
                pos = self.classifier[value]
            else:
                pos = random.randint(0, len(self.childrens) - 1) 
            result = self.childrens[pos]
        elif self.value_type == 'continuity_data':
            if value <= self.classifier:
                result = self.childrens[0]
            else:
                result = self.childrens[1] 
        return result
        

def readData(fileName):
    result = {}
    with open(fileName,'rb') as f:
        rows = csv.reader(f)
        for row in rows:
            if result.has_key('attr_list'):
                for i in range(len(result['attr_list'])):
                    key = result['attr_list'][i]
                    if not result.has_key(key):
                        result[key] = []
                    result[key].append(row[i])
            else:
                result['attr_list'] = row
    return result

def writeData(fileName, data):
    csvFile = open(fileName, 'w')
    writer = csv.writer(csvFile)
    n = len(data)
    for i in range(n):
        writer.writerow(data[i])
    csvFile.close()

def convertData(dataList):
    hashTable = {}
    count = 0
    for i in range(len(dataList)):
        if not hashTable.has_key(dataList[i]):
            hashTable[dataList[i]] = count
            count += 1
        dataList[i] = str(hashTable[dataList[i]])

def convertValueData(dataList):
    sumValue = 0.0
    count = 0
    for i in range(len(dataList)):
        if dataList[i] == "":
            continue
        sumValue += float(dataList[i])
        count += 1
        dataList[i] = float(dataList[i])
    avg = sumValue / count
    for i in range(len(dataList)):
        if dataList[i] == "":
            dataList[i] = avg

def dataPredeal(data):
    useDataList = ['Sex','Pclass', 'SibSp','Parch','Embarked']
    result = {}
    convertValueData(data["Age"])
    result['Age'] = data['Age']
    for i in range(len(useDataList)):
        attrName = useDataList[i]
        convertData(data[attrName])
        result[attrName] = data[attrName]
    return result

def calEntropy(dataList, labelList, isContinuity):
    if not isContinuity:
        count = 0.0
        attrCount = {}
        for i in range(len(dataList)):
            key = dataList[i]
            label = labelList[i]
            count += 1
            if not attrCount.has_key(key):
                attrCount[key] = {'0':0.0,'1':0.0}
            if not attrCount[key].has_key(label):
                attrCount[key][label] = 0.0
            attrCount[key][label] += 1.0
        entropy = 0
        for key in attrCount:
            p0 = attrCount[key]['0']/(attrCount[key]['0'] + attrCount[key]['1'])
            p1 = attrCount[key]['1']/(attrCount[key]['0'] + attrCount[key]['1'])
            v0 = 0 if p0 == 0 else p0*math.log(p0,2)
            v1 = 0 if p1 == 0 else p1*math.log(p1,2)
            temp = (attrCount[key]['0'] + attrCount[key]['1']) / count * (v0 + v1)
            entropy -= temp
        return entropy, None
    else:
        ageList = set([dataList[i] for i in range(len(dataList))])
        ageList = list(ageList)
        ageList.sort()
        minEntropy = 1
        targetAge = 0
        for i in range(len(ageList) - 1):
            avgAge = (ageList[i] + ageList[i + 1]) / 2
            count = 0.0
            left_sum = {'0':0.0,'1':0.0}
            right_sum = {'0':0.0,'1':0.0}
            for j in range(len(dataList)):
                if dataList[j] <= avgAge:
                    left_sum[labelList[j]] += 1.0
                else:
                    right_sum[labelList[j]] += 1.0
                count += 1.0
            pl = (left_sum['0'] + left_sum['1']) / count
            pl0 = left_sum['0']/(left_sum['0'] + left_sum['1'])
            pl1 = 1.0 - pl0
            pr = (right_sum['0'] + right_sum['1']) / count
            pr0 = right_sum['0']/(right_sum['0'] + right_sum['1'])
            pr1 = 1.0 - pr0
            vl0 = 0 if pl0 == 0 else pl0*math.log(pl0,2)
            vl1 = 0 if pl1 == 0 else pl1*math.log(pl1,2)
            vr0 = 0 if pr0 == 0 else pr0*math.log(pr0,2)
            vr1 = 0 if pr1 == 0 else pr1*math.log(pr1,2)
            entropy = - pl*(vl0 + vl1) - pr*(vr0 + vr1)
            if entropy < minEntropy:
                minEntropy = entropy
                targetAge = avgAge
        return minEntropy, targetAge

def checkFinal(data,labelList, root):
    diff_count = 0
    hash_key = {}
    attrName = ""
    for key in data:
        if not hash_key.has_key(key):
            hash_key[key] = True
            diff_count += 1
            attrName = key
        if diff_count > 1:
            break
    if diff_count > 1:
        return False
    root.attr_name = attrName
    root.value_type = 'continuity_data' if attrName == 'Age' else 'disperse_data'
    ageBoundary = None
    if attrName == 'Age':
        entropy,ageBoundary = calEntropy(data[attrName], labelList, True)
    statistics = {}
    for i in range(len(data[attrName])):
        key = data[attrName][i]
        if ageBoundary != None:
            key = 0 if key <= ageBoundary else 1
        if not statistics.has_key(key):
            statistics[key] = [0.0,0.0]
        pos = int(labelList[i])
        statistics[key][pos] += 1.0
    
    root.classifier = ageBoundary if attrName == 'Age' else {}
    root.childrens = [] if attrName != 'Age' else [0,0]
    count = 0
    for key in statistics:
        if ageBoundary == None:
            if not root.classifier.has_key(key):
                root.classifier[key] = count
                root.childrens.append(0)
                count += 1
            root.childrens[root.classifier[key]] = 0 if statistics[key][0] > statistics[key][1] else 1
        else:
            root.childrens[key] = 0 if statistics[key][0] > statistics[key][1] else 1
    return True

def deepPrint(deep, info):
    s = ''
    for i in range(deep):
        s += ' '
    s += 'deep:' + str(deep) + '   attr:' + info
    print s

def buildTree(data, labelList, deep=0):
    root = Node()
    if checkFinal(data, labelList, root) == True:
        #deepPrint(deep, root.attr_name)
        return root
    minEntropy = 1
    targetAttrName = ''
    continuityValueBoundary = None
    for key in data:
        entropy, targetAge = calEntropy(data[key], labelList, key == 'Age')
        if entropy < minEntropy:
            minEntropy = entropy
            targetAttrName = key
            continuityValueBoundary = targetAge
    root.attr_name = targetAttrName
    #deepPrint(deep, root.attr_name)
    if continuityValueBoundary != None:
        root.value_type = 'continuity_data'
        root.classifier = continuityValueBoundary
        root.childrens = [0,0]
    else:
        root.value_type = 'disperse_data'
        root.classifier = {}
        root.childrens = []
    subDatas = {}
    for i in range(len(data[targetAttrName])):
        key = data[targetAttrName][i]
        if continuityValueBoundary != None:
            if key <= root.classifier:
                key = 0
            else:
                key = 1
        if not subDatas.has_key(key):
            subDatas[key] = {'data':{},'labelList':[]}
        for k in data:
            if k != targetAttrName:
                if not subDatas[key]['data'].has_key(k):
                    subDatas[key]['data'][k] = []
                subDatas[key]['data'][k].append(data[k][i])
        subDatas[key]['labelList'].append(labelList[i])

    count = 0
    for key in subDatas:
        child = buildTree(subDatas[key]['data'], subDatas[key]['labelList'], deep+1)
        if root.value_type == 'continuity_data':
            root.childrens[key] = child
        else:
            root.classifier[key] = count
            root.childrens.append(child)
            count += 1
    return root
    
def train(train_data):
    x = dataPredeal(train_data)
    tree = buildTree(x, train_data['Survived'])
    return tree

def fit(tree, test_data, pos):
    result = tree
    while(result != 0 and result != 1):
        result = result.getNext(test_data[result.attr_name][pos])
    return [test_data['PassengerId'][pos],result]

def run():
    dataRoot = '../../kaggledata/titanic/'
    train_data = readData(dataRoot + 'train.csv')
    test_data = readData(dataRoot + 'test.csv')
    tree = train(train_data)
    result_list = []
    result_list.append(['PassengerId', 'Survived'])
    for i in range(len(test_data['PassengerId'])):
        result_list.append(fit(tree, test_data, i))
    writeData(dataRoot + 'result.csv', result_list)

run()

下面的代碼用了sklearn庫(kù)里的隨機(jī)森林的方法，還是很方便的，效果也還行，準(zhǔn)確率有0.74641，果然三個(gè)臭皮匠干死諸葛亮~

import csv
import os
import random
import math
from sklearn.ensemble import RandomForestClassifier

def readData(fileName):
    result = {}
    with open(fileName,'rb') as f:
        rows = csv.reader(f)
        for row in rows:
            if result.has_key('attr_list'):
                for i in range(len(result['attr_list'])):
                    key = result['attr_list'][i]
                    if not result.has_key(key):
                        result[key] = []
                    result[key].append(row[i])
            else:
                result['attr_list'] = row
    return result

def writeData(fileName, data):
    csvFile = open(fileName, 'w')
    writer = csv.writer(csvFile)
    n = len(data)
    for i in range(n):
        writer.writerow(data[i])
    csvFile.close()

def convertData(dataList):
    hashTable = {}
    count = 0
    for i in range(len(dataList)):
        if not hashTable.has_key(dataList[i]):
            hashTable[dataList[i]] = count
            count += 1
        dataList[i] = str(hashTable[dataList[i]])

def convertValueData(dataList):
    sumValue = 0.0
    count = 0
    for i in range(len(dataList)):
        if dataList[i] == "":
            continue
        sumValue += float(dataList[i])
        count += 1
        dataList[i] = float(dataList[i])
    avg = sumValue / count
    for i in range(len(dataList)):
        if dataList[i] == "":
            dataList[i] = avg

def dataPredeal(data):
    useDataList = ['Sex','Pclass', 'SibSp','Parch','Embarked']
    convertValueData(data["Age"])
    for i in range(len(useDataList)):
        attrName = useDataList[i]
        convertData(data[attrName])
    
def train(train_data):
    dataPredeal(train_data)
    useList = ['Pclass', 'Sex', 'Age', 'SibSp', 'Parch']
    x = []
    y = []
    for i in range(len(train_data['Survived'])):
        item = []
        for j in range(len(useList)):
            item.append(train_data[useList[j]][i])
        x.append(item)
        y.append(train_data['Survived'][i])
    clf = RandomForestClassifier().fit(x,y)
    return clf

def predict(clf, test_data, pos):
    x = [[]]
    useList = ['Pclass', 'Sex', 'Age', 'SibSp', 'Parch']
    for i in range(len(useList)):
        x[0].append(test_data[useList[i]][pos])
    result = clf.predict(x)
    return [test_data['PassengerId'][pos],int(result[0])]

def run():
    dataRoot = '../../kaggledata/titanic/'
    train_data = readData(dataRoot + 'train.csv')
    test_data = readData(dataRoot + 'test.csv')
    clf = train(train_data) 
    dataPredeal(test_data)
    result_list = []
    result_list.append(['PassengerId', 'Survived'])
    for i in range(len(test_data['PassengerId'])):
        result_list.append(predict(clf, test_data, i))
        print 'cal:' + str(i)
    writeData(dataRoot + 'result.csv', result_list)

run()