智能決策
智能決策支持系統(tǒng)是人工智能(AI,Artificial Intelligence)和DSS相結(jié)合,應(yīng)用專(zhuān)家系統(tǒng)(ES,Expert System)技術(shù),使DSS能夠更充分地應(yīng)用人類(lèi)的知識(shí),如關(guān)于決策問(wèn)題的描述性知識(shí),決策過(guò)程中的過(guò)程性知識(shí),求解問(wèn)題的推理性知識(shí),通過(guò)邏輯推理來(lái)幫助解決復(fù)雜的決策問(wèn)題的輔助決策系統(tǒng)。
決策樹(shù)
在現(xiàn)實(shí)生活中,我們會(huì)遇到各種選擇,不論是選擇男女朋友,還是挑選水果,都是基于以往的經(jīng)驗(yàn)來(lái)做判斷。如果把判斷背后的邏輯整理成一個(gè)結(jié)構(gòu)圖,你會(huì)發(fā)現(xiàn)它實(shí)際上是一個(gè)樹(shù)狀圖,這就是決策樹(shù)。
工作原理
決策樹(shù)基本上就是把我們以前的經(jīng)驗(yàn)總結(jié)出來(lái)。如果我們要出門(mén)打籃球,一般會(huì)根據(jù)“天氣”、“溫度”、“濕度”、“刮風(fēng)”這幾個(gè)條件來(lái)判斷,最后得到結(jié)果:去打籃球?還是不去?
上面這個(gè)圖就是一棵典型的決策樹(shù)。我們?cè)谧鰶Q策樹(shù)的時(shí)候,會(huì)經(jīng)歷兩個(gè)階段:構(gòu)造和剪枝。
構(gòu)造
構(gòu)造就是生成一棵完整的決策樹(shù)。簡(jiǎn)單來(lái)說(shuō),構(gòu)造的過(guò)程就是選擇什么屬性作為節(jié)點(diǎn)的過(guò)程,那么在構(gòu)造過(guò)程中,會(huì)存在三種節(jié)點(diǎn):
1.根節(jié)點(diǎn):就是樹(shù)的最頂端,最開(kāi)始的那個(gè)節(jié)點(diǎn)。在上圖中,“天氣”就是一個(gè)根節(jié)點(diǎn);
2.內(nèi)部節(jié)點(diǎn):就是樹(shù)中間的那些節(jié)點(diǎn),比如說(shuō)“溫度”、“濕度”、“刮風(fēng)”;
3.葉節(jié)點(diǎn):就是樹(shù)最底部的節(jié)點(diǎn),也就是決策結(jié)果。
節(jié)點(diǎn)之間存在父子關(guān)系。比如根節(jié)點(diǎn)會(huì)有子節(jié)點(diǎn),子節(jié)點(diǎn)會(huì)有子子節(jié)點(diǎn),但是到了葉節(jié)點(diǎn)就停止了,葉節(jié)點(diǎn)不存在子節(jié)點(diǎn)。那么在構(gòu)造過(guò)程中,你要解決三個(gè)重要的問(wèn)題:
1.選擇哪個(gè)屬性作為根節(jié)點(diǎn);
2.選擇哪些屬性作為子節(jié)點(diǎn);
3.什么時(shí)候停止并得到目標(biāo)狀態(tài),即葉節(jié)點(diǎn)。
剪枝
剪枝就是給決策樹(shù)瘦身,這一步想實(shí)現(xiàn)的目標(biāo)就是,不需要太多的判斷,同樣可以得到不錯(cuò)的結(jié)果。之所以這么做,是為了防止“過(guò)擬合”(Overfitting)現(xiàn)象的發(fā)生。
過(guò)擬合:指的是模型的訓(xùn)練結(jié)果“太好了”,以至于在實(shí)際應(yīng)用的過(guò)程中,會(huì)存在“死板”的情況,導(dǎo)致分類(lèi)錯(cuò)誤。
欠擬合:指的是模型的訓(xùn)練結(jié)果不理想。
造成過(guò)擬合的原因:
一是因?yàn)橛?xùn)練集中樣本量較小。如果決策樹(shù)選擇的屬性過(guò)多,構(gòu)造出來(lái)的決策樹(shù)一定能夠“完美”地把訓(xùn)練集中的樣本分類(lèi),但是這樣就會(huì)把訓(xùn)練集中一些數(shù)據(jù)的特點(diǎn)當(dāng)成所有數(shù)據(jù)的特點(diǎn),但這個(gè)特點(diǎn)不一定是全部數(shù)據(jù)的特點(diǎn),這就使得這個(gè)決策樹(shù)在真實(shí)的數(shù)據(jù)分類(lèi)中出現(xiàn)錯(cuò)誤,也就是模型的“泛化能力”差。
泛化能力:指的分類(lèi)器是通過(guò)訓(xùn)練集抽象出來(lái)的分類(lèi)能力,你也可以理解是舉一反三的能力。如果我們太依賴(lài)于訓(xùn)練集的數(shù)據(jù),那么得到的決策樹(shù)容錯(cuò)率就會(huì)比較低,泛化能力差。因?yàn)橛?xùn)練集只是全部數(shù)據(jù)的抽樣,并不能體現(xiàn)全部數(shù)據(jù)的特點(diǎn)。
剪枝的方法:
預(yù)剪枝:在決策樹(shù)構(gòu)造時(shí)就進(jìn)行剪枝。方法是,在構(gòu)造的過(guò)程中對(duì)節(jié)點(diǎn)進(jìn)行評(píng)估,如果對(duì)某個(gè)節(jié)點(diǎn)進(jìn)行劃分,在驗(yàn)證集中不能帶來(lái)準(zhǔn)確性的提升,那么對(duì)這個(gè)節(jié)點(diǎn)進(jìn)行劃分就沒(méi)有意義,這時(shí)就會(huì)把當(dāng)前節(jié)點(diǎn)作為葉節(jié)點(diǎn),不對(duì)其進(jìn)行劃分。
后剪枝:在生成決策樹(shù)之后再進(jìn)行剪枝。通常會(huì)從決策樹(shù)的葉節(jié)點(diǎn)開(kāi)始,逐層向上對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行評(píng)估。如果剪掉這個(gè)節(jié)點(diǎn)子樹(shù),與保留該節(jié)點(diǎn)子樹(shù)在分類(lèi)準(zhǔn)確性上差別不大,或者剪掉該節(jié)點(diǎn)子樹(shù),能在驗(yàn)證集中帶來(lái)準(zhǔn)確性的提升,那么就可以把該節(jié)點(diǎn)子樹(shù)進(jìn)行剪枝。方法是:用這個(gè)節(jié)點(diǎn)子樹(shù)的葉子節(jié)點(diǎn)來(lái)替代該節(jié)點(diǎn),類(lèi)標(biāo)記為這個(gè)節(jié)點(diǎn)子樹(shù)中最頻繁的那個(gè)類(lèi)。
如何判斷要不要去打籃球?
我們?cè)撊绾螛?gòu)造一個(gè)判斷是否去打籃球的決策樹(shù)呢?再回顧一下決策樹(shù)的構(gòu)造原理,在決策過(guò)程中有三個(gè)重要的問(wèn)題:將哪個(gè)屬性作為根節(jié)點(diǎn)?選擇哪些屬性作為后繼節(jié)點(diǎn)?什么時(shí)候停止并得到目標(biāo)值?
顯然將哪個(gè)屬性(天氣、溫度、濕度、刮風(fēng))作為根節(jié)點(diǎn)是個(gè)關(guān)鍵問(wèn)題,在這里我們先介紹兩個(gè)指標(biāo):純度和信息熵。
純度
決策樹(shù)的構(gòu)建是基于樣本概率和純度來(lái)進(jìn)行的,判斷數(shù)據(jù)集是否“純”可以通過(guò)三個(gè)公式進(jìn)行判斷:Gini系數(shù)、熵(Entropy)、錯(cuò)誤率。
三個(gè)公式的值越大,表示數(shù)據(jù)越不純。值越小,表示數(shù)據(jù)越純。
例:償還貸款的能力。P(1) = 7/10 = 0.7;可以?xún)斶€的概率;P(2) = 3/10 = 0.3;無(wú)法償還的概率;
Error = 1 - max {p(i)} (i =1 ~ n) = 1 - 0.7 = 0.3
如果只有兩種分類(lèi)情況,隨著兩種情況發(fā)生的概率的改變,最后根據(jù)三種公式的計(jì)算所得:
可以發(fā)現(xiàn),三種公式的效果差不多,一般情況使用熵公式。
信息增益
信息增益指的就是劃分可以帶來(lái)純度的提高,信息熵的下降。它的計(jì)算公式,是父親節(jié)點(diǎn)的信息熵減去所有子節(jié)點(diǎn)的信息熵。在計(jì)算的過(guò)程中,我們會(huì)計(jì)算每個(gè)子節(jié)點(diǎn)的歸一化信息熵,即按照每個(gè)子節(jié)點(diǎn)在父節(jié)點(diǎn)中出現(xiàn)的概率,來(lái)計(jì)算這些子節(jié)點(diǎn)的信息熵。所以信息增益的公式可以表示為:
公式中 D 是父親節(jié)點(diǎn),Di 是子節(jié)點(diǎn),Gain(D,a)中的 a 作為 D 節(jié)點(diǎn)的屬性選擇。
如何計(jì)算信息增益呢?
import numpy as npimport pandas as pdfrom collections import Counterimport mathfrom math import log# 熵# print(-(1 / 3) * log(1 / 3, 2) - (2 / 3) * log(2 / 3, 2))def calc_ent(datasets): data_length = len(datasets) label_count = {} for i in range(data_length): label = datasets[i][-1] if label not in label_count: label_count[label] = 0 label_count[label] += 1 ent = -sum([(p / data_length) * log(p / data_length, 2) for p in label_count.values()]) # print(ent) return ent# 經(jīng)驗(yàn)條件熵def cond_ent(datasets, axis=0): data_length = len(datasets) feature_sets = {} for i in range(data_length): feature = datasets[i][axis] if feature not in feature_sets: feature_sets[feature] = [] feature_sets[feature].append(datasets[i]) cond_ent = sum([(len(p) / data_length) * calc_ent(p) for p in feature_sets.values()]) print(cond_ent) return cond_ent# 信息增益def info_gain(ent, cond_ent): return ent - cond_entdef info_gain_train(datasets): count = len(datasets[0]) - 1 print(count) ent = calc_ent(datasets) print(ent) best_feature = [] for c in range(count): c_info_gain = info_gain(ent, cond_ent(datasets, axis=c)) best_feature.append((c, c_info_gain)) print('特征({}) - info_gain - {:.3f}'.format(labels[c], c_info_gain)) # 比較大小 best_ = max(best_feature, key=lambda x: x[-1]) return '特征({})的信息增益最大,選擇為根節(jié)點(diǎn)特征'.format(labels[best_[0]])# labels = ["天氣", "溫度", "濕度", "刮風(fēng)", '類(lèi)別']# datasets = pd.DataFrame([# ["晴", "高", "中", "否", '否'],# ["晴", "高", "中", "是", '否'],# ["陰天", "高", "高", "否", '是'],# ["雨", "高", "高", "否", '是'],# ["雨", "低", "高", "否", '否'],# ["晴", "中", "中", "是", '是'],# ["陰天", "中", "高", "是", '否'],# ])labels = ["天氣", "濕度", "刮風(fēng)", '類(lèi)別']datasets = pd.DataFrame([ ["晴", "中", "否", '否'], ["晴", "中", "是", '否'], ["陰天", "高", "否", '是'], ["雨", "高", "否", '是']])print(datasets)print(info_gain_train(np.array(datasets)))