2023高教社杯數(shù)學(xué)建模思路 - 案例：隨機(jī)森林
0 賽題思路
（賽題出來(lái)以后第一時(shí)間在群內(nèi)分享）
2023高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽
資料思路分享Q群：575833716
隨機(jī)森林屬于 集成學(xué)習(xí) 中的 Bagging（Bootstrap AGgregation 的簡(jiǎn)稱(chēng)） 方法。如果用圖來(lái)表示他們之間的關(guān)系如下：
決策樹(shù) – Decision Tree
在解釋隨機(jī)森林前，需要先提一下決策樹(shù)。決策樹(shù)是一種很簡(jiǎn)單的算法，他的解釋性強(qiáng)，也符合人類(lèi)的直觀思維。這是一種基于if-then-else規(guī)則的有監(jiān)督學(xué)習(xí)算法，上面的圖片可以直觀的表達(dá)決策樹(shù)的邏輯。
隨機(jī)森林 – Random Forest | RF
隨機(jī)森林是由很多決策樹(shù)構(gòu)成的，不同決策樹(shù)之間沒(méi)有關(guān)聯(lián)。
當(dāng)我們進(jìn)行分類(lèi)任務(wù)時(shí)，新的輸入樣本進(jìn)入，就讓森林中的每一棵決策樹(shù)分別進(jìn)行判斷和分類(lèi)，每個(gè)決策樹(shù)會(huì)得到一個(gè)自己的分類(lèi)結(jié)果，決策樹(shù)的分類(lèi)結(jié)果中哪一個(gè)分類(lèi)最多，那么隨機(jī)森林就會(huì)把這個(gè)結(jié)果當(dāng)做最終的結(jié)果。
2 ?隨機(jī)深林構(gòu)造流程
一個(gè)樣本容量為N的樣本，有放回的抽取N次，每次抽取1個(gè)，最終形成了N個(gè)樣本。這選擇好了的N個(gè)樣本用來(lái)訓(xùn)練一個(gè)決策樹(shù)，作為決策樹(shù)根節(jié)點(diǎn)處的樣本。
當(dāng)每個(gè)樣本有M個(gè)屬性時(shí)，在決策樹(shù)的每個(gè)節(jié)點(diǎn)需要分裂時(shí)，隨機(jī)從這M個(gè)屬性中選取出m個(gè)屬性，滿足條件m << M。然后從這m個(gè)屬性中采用某種策略（比如說(shuō)信息增益）來(lái)選擇1個(gè)屬性作為該節(jié)點(diǎn)的分裂屬性。
決策樹(shù)形成過(guò)程中每個(gè)節(jié)點(diǎn)都要按照步驟2來(lái)分裂（很容易理解，如果下一次該節(jié)點(diǎn)選出來(lái)的那一個(gè)屬性是剛剛其父節(jié)點(diǎn)分裂時(shí)用過(guò)的屬性，則該節(jié)點(diǎn)已經(jīng)達(dá)到了葉子節(jié)點(diǎn)，無(wú)須繼續(xù)分裂了）。一直到不能夠再分裂為止。注意整個(gè)決策樹(shù)形成過(guò)程中沒(méi)有進(jìn)行剪枝。
按照步驟1~3建立大量的決策樹(shù)，這樣就構(gòu)成了隨機(jī)森林了。
3 隨機(jī)森林的優(yōu)缺點(diǎn)
3.1 優(yōu)點(diǎn)
它可以出來(lái)很高維度（特征很多）的數(shù)據(jù)，并且不用降維，無(wú)需做特征選擇
它可以判斷特征的重要程度
可以判斷出不同特征之間的相互影響
不容易過(guò)擬合
訓(xùn)練速度比較快，容易做成并行方法
實(shí)現(xiàn)起來(lái)比較簡(jiǎn)單
對(duì)于不平衡的數(shù)據(jù)集來(lái)說(shuō)，它可以平衡誤差。
如果有很大一部分的特征遺失，仍可以維持準(zhǔn)確度。
3.2 缺點(diǎn)
隨機(jī)森林已經(jīng)被證明在某些噪音較大的分類(lèi)或回歸問(wèn)題上會(huì)過(guò)擬合。
對(duì)于有不同取值的屬性的數(shù)據(jù)，取值劃分較多的屬性會(huì)對(duì)隨機(jī)森林產(chǎn)生更大的影響，所以隨機(jī)森林在這種數(shù)據(jù)上產(chǎn)出的屬性權(quán)值是不可信的
4 隨機(jī)深林算法實(shí)現(xiàn)
數(shù)據(jù)集：https://archive.ics.uci.edu/ml/machine-learning-databases/undocumented/connectionist-bench/sonar/
import csv
from random import seed
from random import randrange
from math import sqrt
def loadCSV(filename):#加載數(shù)據(jù)，一行行的存入列表
? ?dataSet = []
? ?with open(filename, 'r') as file:
? ? ? ?csvReader = csv.reader(file)
? ? ? ?for line in csvReader:
? ? ? ? ? ?dataSet.append(line)
? ?return dataSet
# 除了標(biāo)簽列，其他列都轉(zhuǎn)換為float類(lèi)型
def column_to_float(dataSet):
? ?featLen = len(dataSet[0]) - 1
? ?for data in dataSet:
? ? ? ?for column in range(featLen):
? ? ? ? ? ?data[column] = float(data[column].strip())
# 將數(shù)據(jù)集隨機(jī)分成N塊，方便交叉驗(yàn)證，其中一塊是測(cè)試集，其他四塊是訓(xùn)練集
def spiltDataSet(dataSet, n_folds):
? ?fold_size = int(len(dataSet) / n_folds)
? ?dataSet_copy = list(dataSet)
? ?dataSet_spilt = []
? ?for i in range(n_folds):
? ? ? ?fold = []
? ? ? ?while len(fold) < fold_size: ?# 這里不能用if，if只是在第一次判斷時(shí)起作用，while執(zhí)行循環(huán)，直到條件不成立
? ? ? ? ? ?index = randrange(len(dataSet_copy))
? ? ? ? ? ?fold.append(dataSet_copy.pop(index)) ?# pop() 函數(shù)用于移除列表中的一個(gè)元素（默認(rèn)最后一個(gè)元素），并且返回該元素的值。
? ? ? ?dataSet_spilt.append(fold)
? ?return dataSet_spilt
# 構(gòu)造數(shù)據(jù)子集
def get_subsample(dataSet, ratio):
? ?subdataSet = []
? ?lenSubdata = round(len(dataSet) * ratio)#返回浮點(diǎn)數(shù)
? ?while len(subdataSet) < lenSubdata:
? ? ? ?index = randrange(len(dataSet) - 1)
? ? ? ?subdataSet.append(dataSet[index])
? ?# print len(subdataSet)
? ?return subdataSet
# 分割數(shù)據(jù)集
def data_spilt(dataSet, index, value):
? ?left = []
? ?right = []
? ?for row in dataSet:
? ? ? ?if row[index] < value:
? ? ? ? ? ?left.append(row)
? ? ? ?else:
? ? ? ? ? ?right.append(row)
? ?return left, right
# 計(jì)算分割代價(jià)
def spilt_loss(left, right, class_values):
? ?loss = 0.0
? ?for class_value in class_values:
? ? ? ?left_size = len(left)
? ? ? ?if left_size != 0: ?# 防止除數(shù)為零
? ? ? ? ? ?prop = [row[-1] for row in left].count(class_value) / float(left_size)
? ? ? ? ? ?loss += (prop * (1.0 - prop))
? ? ? ?right_size = len(right)
? ? ? ?if right_size != 0:
? ? ? ? ? ?prop = [row[-1] for row in right].count(class_value) / float(right_size)
? ? ? ? ? ?loss += (prop * (1.0 - prop))
? ?return loss
# 選取任意的n個(gè)特征，在這n個(gè)特征中，選取分割時(shí)的最優(yōu)特征
def get_best_spilt(dataSet, n_features):
? ?features = []
? ?class_values = list(set(row[-1] for row in dataSet))
? ?b_index, b_value, b_loss, b_left, b_right = 999, 999, 999, None, None
? ?while len(features) < n_features:
? ? ? ?index = randrange(len(dataSet[0]) - 1)
? ? ? ?if index not in features:
? ? ? ? ? ?features.append(index)
? ?# print 'features:',features
? ?for index in features:#找到列的最適合做節(jié)點(diǎn)的索引，（損失最?。?br> ? ? ? ?for row in dataSet:
? ? ? ? ? ?left, right = data_spilt(dataSet, index, row[index])#以它為節(jié)點(diǎn)的，左右分支
? ? ? ? ? ?loss = spilt_loss(left, right, class_values)
? ? ? ? ? ?if loss < b_loss:#尋找最小分割代價(jià)
? ? ? ? ? ? ? ?b_index, b_value, b_loss, b_left, b_right = index, row[index], loss, left, right
? ?# print b_loss
? ?# print type(b_index)
? ?return {'index': b_index, 'value': b_value, 'left': b_left, 'right': b_right}
# 決定輸出標(biāo)簽
def decide_label(data):
? ?output = [row[-1] for row in data]
? ?return max(set(output), key=output.count)
# 子分割，不斷地構(gòu)建葉節(jié)點(diǎn)的過(guò)程對(duì)對(duì)對(duì)
def sub_spilt(root, n_features, max_depth, min_size, depth):
? ?left = root['left']
? ?# print left
? ?right = root['right']
? ?del (root['left'])
? ?del (root['right'])
? ?# print depth
? ?if not left or not right:
? ? ? ?root['left'] = root['right'] = decide_label(left + right)
? ? ? ?# print 'testing'
? ? ? ?return
? ?if depth > max_depth:
? ? ? ?root['left'] = decide_label(left)
? ? ? ?root['right'] = decide_label(right)
? ? ? ?return
? ?if len(left) < min_size:
? ? ? ?root['left'] = decide_label(left)
? ?else:
? ? ? ?root['left'] = get_best_spilt(left, n_features)
? ? ? ?# print 'testing_left'
? ? ? ?sub_spilt(root['left'], n_features, max_depth, min_size, depth + 1)
? ?if len(right) < min_size:
? ? ? ?root['right'] = decide_label(right)
? ?else:
? ? ? ?root['right'] = get_best_spilt(right, n_features)
? ? ? ?# print 'testing_right'
? ? ? ?sub_spilt(root['right'], n_features, max_depth, min_size, depth + 1)
? ? ? ?# 構(gòu)造決策樹(shù)
def build_tree(dataSet, n_features, max_depth, min_size):
? ?root = get_best_spilt(dataSet, n_features)
? ?sub_spilt(root, n_features, max_depth, min_size, 1)
? ?return root
# 預(yù)測(cè)測(cè)試集結(jié)果
def predict(tree, row):
? ?predictions = []
? ?if row[tree['index']] < tree['value']:
? ? ? ?if isinstance(tree['left'], dict):
? ? ? ? ? ?return predict(tree['left'], row)
? ? ? ?else:
? ? ? ? ? ?return tree['left']
? ?else:
? ? ? ?if isinstance(tree['right'], dict):
? ? ? ? ? ?return predict(tree['right'], row)
? ? ? ?else:
? ? ? ? ? ?return tree['right']
? ? ? ? ? ?# predictions=set(predictions)
def bagging_predict(trees, row):
? ?predictions = [predict(tree, row) for tree in trees]
? ?return max(set(predictions), key=predictions.count)
# 創(chuàng)建隨機(jī)森林
def random_forest(train, test, ratio, n_feature, max_depth, min_size, n_trees):
? ?trees = []
? ?for i in range(n_trees):
? ? ? ?train = get_subsample(train, ratio)#從切割的數(shù)據(jù)集中選取子集
? ? ? ?tree = build_tree(train, n_features, max_depth, min_size)
? ? ? ?# print 'tree %d: '%i,tree
? ? ? ?trees.append(tree)
? ?# predict_values = [predict(trees,row) for row in test]
? ?predict_values = [bagging_predict(trees, row) for row in test]
? ?return predict_values
# 計(jì)算準(zhǔn)確率
def accuracy(predict_values, actual):
? ?correct = 0
? ?for i in range(len(actual)):
? ? ? ?if actual[i] == predict_values[i]:
? ? ? ? ? ?correct += 1
? ?return correct / float(len(actual))
if __name__ == '__main__':
? ?seed(1)
? ?dataSet = loadCSV('sonar-all-data.csv')
? ?column_to_float(dataSet)#dataSet
? ?n_folds = 5
? ?max_depth = 15
? ?min_size = 1
? ?ratio = 1.0
? ?# n_features=sqrt(len(dataSet)-1)
? ?n_features = 15
? ?n_trees = 10
? ?folds = spiltDataSet(dataSet, n_folds)#先是切割數(shù)據(jù)集
? ?scores = []
? ?for fold in folds:
? ? ? ?train_set = folds[
? ? ? ? ? ? ? ? ? ?:] ?# 此處不能簡(jiǎn)單地用train_set=folds，這樣用屬于引用,那么當(dāng)train_set的值改變的時(shí)候，folds的值也會(huì)改變，所以要用復(fù)制的形式。（L[:]）能夠復(fù)制序列，D.copy() 能夠復(fù)制字典，list能夠生成拷貝 list(L)
? ? ? ?train_set.remove(fold)#選好訓(xùn)練集
? ? ? ?# print len(folds)
? ? ? ?train_set = sum(train_set, []) ?# 將多個(gè)fold列表組合成一個(gè)train_set列表
? ? ? ?# print len(train_set)
? ? ? ?test_set = []
? ? ? ?for row in fold:
? ? ? ? ? ?row_copy = list(row)
? ? ? ? ? ?row_copy[-1] = None
? ? ? ? ? ?test_set.append(row_copy)
? ? ? ? ? ?# for row in test_set:
? ? ? ? ? ?# print row[-1]
? ? ? ?actual = [row[-1] for row in fold]
? ? ? ?predict_values = random_forest(train_set, test_set, ratio, n_features, max_depth, min_size, n_trees)
? ? ? ?accur = accuracy(predict_values, actual)
? ? ? ?scores.append(accur)
? ?print ('Trees is %d' % n_trees)
? ?print ('scores:%s' % scores)
? ?print ('mean score:%s' % (sum(scores) / float(len(scores))))
建模資料
資料分享: 最強(qiáng)建模資料
2023高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽
資料思路分享Q群：575833716
