終于做到了決策樹柬姚，這是一個(gè)很有意思的分類模型
什么是決策樹
盡管我一直將決策樹理解為一個(gè)分類模型，但實(shí)際上捣域，他也是可以解決回歸問題的焕梅，如何理解決策樹呢贞言？
我們應(yīng)該從以下幾個(gè)方面理解：
1该窗、他是一棵樹
2、他是一堆If - then規(guī)則的集合
3义钉、定義在特征空間與類空間上的條件概率分布捶闸，決策樹實(shí)際上是將特征空間劃分成了互不相交的單元删壮，每個(gè)從根到葉的路徑對(duì)應(yīng)著一個(gè)單元央碟。決策樹所表示的條件概率分布由各個(gè)單元給定條件下類的條件概率分布組成均函。實(shí)際中苞也，哪個(gè)類別有較高的條件概率墩朦，就把該單元中的實(shí)例強(qiáng)行劃分為該類別氓涣。
決策樹有什么優(yōu)點(diǎn)
- 模型具有可解釋性陋气，容易向業(yè)務(wù)部門人員描述巩趁。
- 分類速度快
如何用決策樹分類
1议慰、特征選擇
2别凹、決策樹的生成
3、決策樹的剪枝
4堕战、分類
如何進(jìn)行特征選擇
先說為什么要進(jìn)行特征選擇?
我認(rèn)為，我們要搭建決策樹薪介，就要找到一系列的If-then條件汁政，而If-then條件又是依賴于特征空間的烂完，所以我們就要找到真正“管事”的特征抠蚣。
所以我們?cè)撊绾握业揭粋€(gè)管事的特征呢履澳？
很容易知道距贷，如果我們?cè)O(shè)計(jì)的分類規(guī)則帶來的結(jié)果與隨機(jī)分類的結(jié)果相差不大忠蝗，那么就說明這個(gè)我們選取的特征不管事阁最。
所以在這里，我們引入兩個(gè)概念：
- 信息增益
- 信息增益率
我們要理解這兩個(gè)概念的話姜盈，首先要明白什么是熵：
熵馏颂，表示隨機(jī)變量的不確定性
Entropy
現(xiàn)在救拉，來解釋什么是信息增益：
按照上面講的亿絮，理所當(dāng)然葱绒，我們?cè)O(shè)置分類規(guī)則后地淀，這個(gè)點(diǎn)屬于的類別的不確定性應(yīng)該或多或少的有所減少岖是，也就是說豺撑，設(shè)置分類規(guī)則后的熵（條件熵）應(yīng)該比未設(shè)置分類規(guī)則前的熵要小一些聪轿，而小的部分就是信息增益陆错。
但是呢音瓷，信息增益有一些缺點(diǎn)绳慎，就是某個(gè)類別的樣本數(shù)如果很大的話杏愤，那么他的信息增益一定會(huì)很大。
所以乏奥，為了解決這種不準(zhǔn)確的問題亥曹，昆蘭（大佬）在ID3算法的基礎(chǔ)改進(jìn)媳瞪，提出了C4.5蛇受，利用信息增益率來解決問題兢仰，也就是用信息增益除以對(duì)應(yīng)的條件熵。
如何生成決策樹
1轻专、ID3算法
通過比較信息增益请垛，獲得最優(yōu)的分類規(guī)則宗收，然后遞歸混稽，生成整個(gè)決策樹荚坞。
需要注意的地方：
- 當(dāng)訓(xùn)練集（子集）只有一種類別時(shí)菲盾，生成葉子節(jié)點(diǎn)（類別）
包括只有一個(gè)懒鉴，和都是一種的情況临谱。
2、c4.5算法
trick
將一些我在做的時(shí)候城豁，遇到的唱星，思考的一些有意思的地方：
1跟磨、經(jīng)驗(yàn)熵與經(jīng)驗(yàn)條件熵的估計(jì)方法，在書上我們可以看到哎榴，他簡(jiǎn)單的使用了頻率估計(jì)概率的方法估計(jì)得到了概率迎变，但是我們知道，這樣其實(shí)是不夠準(zhǔn)確的（裝逼的）氏豌，所以理所當(dāng)然的我們要用極大似然估計(jì)啊泵喘。
怎么用呢纪铺？
首先碟渺，我們先來回顧一下苫拍，在樸素貝葉斯的搭建過程中绒极，我們用到的極大似然估計(jì)是怎么回事？
我們通過貝葉斯公式展開了待求的條件概率榔袋，然后有兩個(gè)概率我們需要去估計(jì)一下：
待求概率
我們只說一下后面那個(gè)：
首先就是他的實(shí)際意義：當(dāng)類別是Yi時(shí)凰兑，特征向量/第i維特征值是Xi的概率是多少吏够，顯然锅知，對(duì)于這個(gè)條件概率喉镰，我們并不知道該怎么求解惭笑，但是利用極大似然估計(jì)的想法沉噩，我們假設(shè)這個(gè)條件概率符合參數(shù)為thete的某種分布川蒙，當(dāng)然畜眨，如果我們想知道這個(gè)條件概率的話，我們只需要算出參數(shù)theta贰健，然后我們就得到了概率密度函數(shù)伶椿，剩下的就不用多說了氓侧，但是怎么算theta呢？我們就要用到訓(xùn)練數(shù)據(jù)了偎痛，也就是說：X1, X3, X6都是Y1類別的（舉例）看彼，那么出現(xiàn)X1,X3,X6同時(shí)為Y1類別的可能性（似然函數(shù)）就非常的大了靖榕，所以后面的大家就都知道了茁计，求偏導(dǎo)谓松，等于零鬼譬，得到theta优质。
那么军洼，對(duì)于決策樹的這個(gè)問題呢匕争？我們?cè)趺蠢脴O大似然估計(jì)解決甘桑，其實(shí)是一樣的跑杭，只不過現(xiàn)在我們要求的不是剛才的第二個(gè)了艘蹋，而是第一個(gè)了女阀，同樣浸策，我們假設(shè)這個(gè)概率符合某種分布庸汗，我們需要求解這個(gè)參數(shù)蚯舱，同樣的我們將所有的為該類的數(shù)據(jù)全部帶入到似然函數(shù)中枉昏，使他最大化，這樣我們就算出來了這個(gè)概率兄裂。
下面是我是實(shí)現(xiàn)的代碼：
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Date : 2019-02-02 14:19:55
# @Author : Vophan Lee (vophanlee@gmail.com)
# @Link : http://www.reibang.com/u/3e6114e983ad
from sklearn.datasets import make_classification
import numpy as np
import math
class decision_tree(object):
"""
one step to access my dream
"""
def __init__(self):
super(decision_tree, self).__init__()
self.features = 5
self.samples = 100
self.data = make_classification(n_samples=self.samples, n_features=self.features, n_classes=2)
self.data_0 = []
self.data_1 = []
for i in enumerate(self.data[1]):
if i[1] == 0:
self.data_0.append(self.data[0][i[0]])
else:
self.data_1.append(self.data[0][i[0]])
self.means_1 = np.mean(self.data_1, axis=0, keepdims=True).reshape(self.features)
self.std_1 = np.std(self.data_1, axis=0, keepdims=True, ddof=1).reshape(self.features)
self.means_0 = np.mean(self.data_0, axis=0, keepdims=True).reshape(self.features)
self.std_0 = np.std(self.data_0, axis=0, keepdims=True, ddof=1).reshape(self.features)
self.std = [self.std_0, self.std_1]
self.means = [self.means_0, self.means_1]
self.empirical_entropy = self.cal_emp_entropy()
def cal_emp_entropy(self):
all_p = []
data_list = [self.data_0, self.data_1]
for i in range(2):
p = 1
for dim in range(self.features):
for data in data_list[i]:
# print(self.std[data_list.index(all_data)][dim])
p *= (1 / (pow(2 * math.pi, 0.5) * self.std[i][dim])) * pow(math.e, -(pow((data[dim] - self.means[i][dim]), 2) / 2 * pow(self.std[i][dim], 2)))
all_p.append(p)
entropy = 0
for p in all_p:
entropy += -p * math.log2(p)
return entropy
2、我還想說些什么呢匾南？
就是蛆楞，書本上我們可以發(fā)現(xiàn)臊岸，給的特征都是離散的尊流，如果我們給幾組連續(xù)的特征呢逻住？比如西瓜書上的例子瞎访，西瓜的含糖率以及密度扒秸，我們應(yīng)該怎么處理呢伴奥？
在這里，有一種方法叫做二分法求最佳劃分點(diǎn)
首先翼闽，我們先對(duì)所有數(shù)據(jù)按照某一個(gè)維度排序拾徙，然后在將每?jī)蓚€(gè)點(diǎn)的中點(diǎn)作為劃分點(diǎn)，然后分別計(jì)算他們的信息增益感局，最終確定一個(gè)最佳的劃分點(diǎn)
下面是我的全部代碼：
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Date : 2019-02-03 15:17:08
# @Author : Vophan Lee (vophanlee@gmail.com)
# @Link : http://www.reibang.com/u/3e6114e983ad
from sklearn.datasets import make_classification
import numpy as np
import math
class Decision_Tree(object):
"""
this is a class to build the decision tree
"""
feature_list = []
gain_list = []
dim_list = []
index = 0
def __init__(self):
super(Decision_Tree, self).__init__()
self.features = 5
self.samples = 100
self.data = make_classification(
n_samples=self.samples, n_features=self.features, n_classes=2)
self.empirical_entropy = self.cal_emp_entropy(self.data)
def cal_emp_entropy(self, data):
"""
calculate the empirical entropy
"""
data_0 = []
data_1 = []
for i in enumerate(data[1]):
if i[1] == 0:
data_0.append(data[0][i[0]])
else:
data_1.append(data[0][i[0]])
entropy = 0
for data_ in [data_0, data_1]:
entropy += - \
(len(data_) / len(data[0])) * \
math.log2(len(data_) / len(data[0]))
return entropy
def div_point(self, dim_data):
"""
decide the divided point of each feature,here we sopposed that dim_data is a continuous dataset
dim_data: tuple
"""
def dichotomy(dim_data):
div_points = np.zeros((1, self.samples)).reshape(self.samples)
for i in enumerate(dim_data):
if i[0] == len(dim_data) - 1:
break
div_points[i[0]] = (dim_data[i[0] + 1] + i[1]) / 2
return div_points
dim_data = list(dim_data)
dim_data = np.array(dim_data)
dim_data = dim_data[:, dim_data[0].argsort()]
dim_data = tuple(dim_data)
div_points = dichotomy(dim_data[1])
information_gain_list = []
for i in div_points:
div_index = list(div_points).index(i) + 1
front = dim_data[1][:div_index]
behind = dim_data[1][div_index:]
front_flag = dim_data[0][:div_index]
behind_flag = dim_data[0][div_index:]
front_data = (front, front_flag)
behind_data = (behind, behind_flag)
if len(front_data[0]) == 1 or ((front_data[1] == front_data[1][::-1]).all() and len(front_data[0]) != len(dim_data[0]) / 2):
behind_entropy = self.cal_emp_entropy(behind_data)
information_gain = self.empirical_entropy - \
(behind_entropy * (len(behind) / len(dim_data[0])))
information_gain_list.append(information_gain)
elif len(behind_data[0]) == 1 or ((behind_data[1] == behind_data[1][::-1]).all() and len(front_data[0]) != len(dim_data[0]) / 2):
front_entropy = self.cal_emp_entropy(front_data)
information_gain = self.empirical_entropy - \
(front_entropy * (len(front) / len(dim_data[0])))
information_gain_list.append(information_gain)
elif (front_data[1] == front_data[1][::-1]).all() and len(front_data[0]) == len(dim_data[0]) / 2:
return -1, div_points[int(len(dim_data[0]) / 2 - 1)]
else:
front_entropy = self.cal_emp_entropy(front_data)
behind_entropy = self.cal_emp_entropy(behind_data)
information_gain = self.empirical_entropy - (front_entropy * (len(front) / len(
dim_data[0])) + behind_entropy * (len(behind) / len(dim_data[0])))
information_gain_list.append(information_gain)
max_information_gain = max(information_gain_list)
return max_information_gain, div_points[information_gain_list.index(max_information_gain)]
def compare_features(self):
"""
here we choose a maximium information gain among all features
"""
gain_list_tmp = []
point_list = []
for i in range(self.features):
information_gain, div_point = self.div_point((self.data[1], self.data[0].transpose()[i]))
gain_list_tmp.append(information_gain)
point_list.append(div_point)
com_matrix = np.array([
gain_list_tmp,
point_list,
range(self.features)
])
com_matrix = com_matrix[:, com_matrix[0].argsort()]
Decision_Tree.feature_list = list(com_matrix[1])
Decision_Tree.gain_list = list(com_matrix[0])
Decision_Tree.dim_list = list(com_matrix[2])
def planet_tree(self, data):
"""
here is the process of planeting the tree
data: without flag
"""
feature = Decision_Tree.feature_list[Decision_Tree.index]
dim = Decision_Tree.dim_list[Decision_Tree.index]
Decision_Tree.index += 1
if Decision_Tree.gain_list[Decision_Tree.feature_list.index(feature)] == -1 or Decision_Tree.index >= len(Decision_Tree.feature_list) - 1:
return tree_node([x for x in data.transpose()[int(dim)] if x < feature],
[x for x in data.transpose()[int(dim)] if x > feature],
feature)
else:
return tree_node(self.planet_tree([x for x in data[0] if x < feature]),self.planet_tree([x for x in data[0] if x > feature]), feature)
class tree_node(object):
"""
this is the node of the decision tree
"""
def __init__(self, left, right, data):
self.left=left
self.right=right
self.data=data
這就是今天晚上的全部?jī)?nèi)容尼啡，剪枝以及回歸的內(nèi)容請(qǐng)關(guān)注我后續(xù)的文章哦
