決策樹的生成 - 決策樹的構(gòu)建設(shè)計(jì)并用Graphviz實(shí)現(xiàn)決策樹的可視化

查看生成的決策樹:
In [2]: clf.tree
Out[2]:
{'tearRate': {'normal': {'astigmatic': {'no': {'age': {'pre': 'soft',
'presbyopic': {'prescript': {'hyper': 'soft', 'myope': 'no lenses'}},
'young': 'soft'}},
'yes': {'prescript': {'hyper': {'age': {'pre': 'no lenses',
'presbyopic': 'no lenses',
'young': 'hard'}},
'myope': 'hard'}}}},
'reduced': 'no lenses'}}

可視化決策樹

直接通過嵌套字典表示決策樹對(duì)人來說不好理解，我們需要借助可視化工具可視化樹結(jié)構(gòu)，這里我將使用Graphviz來可視化樹結(jié)構(gòu)。為此實(shí)現(xiàn)了講字典表示的樹生成Graphviz Dot文件內(nèi)容的函數(shù)，大致思想就是遞歸獲取整棵樹的所有節(jié)點(diǎn)和連接節(jié)點(diǎn)的邊然后將這些節(jié)點(diǎn)和邊生成Dot格式的字符串寫入文件中并繪圖。

遞歸獲取樹的節(jié)點(diǎn)和邊，其中使用了uuid給每個(gè)節(jié)點(diǎn)添加了id屬性以便將相同屬性的節(jié)點(diǎn)區(qū)分開.
def get_nodes_edges(self, tree=None, root_node=None):
''' 返回樹中所有節(jié)點(diǎn)和邊
'''
Node = namedtuple('Node', ['id', 'label'])
Edge = namedtuple('Edge', ['start', 'end', 'label'])

if tree is None:
tree = self.tree

if type(tree) is not dict:
return [], []

nodes, edges = [], []

if root_node is None:
label = list(tree.keys())[0]
root_node = Node._make([uuid.uuid4(), label])
nodes.append(root_node)

for edge_label, sub_tree in tree[root_node.label].items():
node_label = list(sub_tree.keys())[0] if type(sub_tree) is dict else sub_tree
sub_node = Node._make([uuid.uuid4(), node_label])
nodes.append(sub_node)

edge = Edge._make([root_node, sub_node, edge_label])
edges.append(edge)

sub_nodes, sub_edges = self.get_nodes_edges(sub_tree, root_node=sub_node)
nodes.extend(sub_nodes)
edges.extend(sub_edges)

return nodes, edges

生成dot文件內(nèi)容
def dotify(self, tree=None):
''' 獲取樹的Graphviz Dot文件的內(nèi)容
'''
if tree is None:
tree = self.tree

content = 'digraph decision_tree {\n'
nodes, edges = self.get_nodes_edges(tree)

for node in nodes:
content += ' "{}" [label="{}"];\n'.format(node.id, node.label)

for edge in edges:
start, label, end = edge.start, edge.label, edge.end
content += ' "{}" -> "{}" [label="{}"];\n'.format(start.id, end.id, label)
content += '}'

return content

隱形眼鏡數(shù)據(jù)生成Dot文件內(nèi)容如下:
digraph decision_tree {
"959b4c0c-1821-446d-94a1-c619c2decfcd" [label="call"];
"18665160-b058-437f-9b2e-05df2eb55661" [label="to"];
"2eb9860d-d241-45ca-85e6-cbd80fe2ebf7" [label="your"];
"bcbcc17c-9e2a-4bd4-a039-6e51fde5f8fd" [label="areyouunique"];
"ca091fc7-8a4e-4970-9ec3-485a4628ad29" [label="02073162414"];
"aac20872-1aac-499d-b2b5-caf0ef56eff3" [label="ham"];
"18aa8685-a6e8-4d76-bad5-ccea922bb14d" [label="spam"];
"3f7f30b1-4dbb-4459-9f25-358ad3c6d50b" [label="spam"];
"44d1f972-cd97-4636-b6e6-a389bf560656" [label="spam"];
"7f3c8562-69b5-47a9-8ee4-898bd4b6b506" [label="i"];
"a6f22325-8841-4a81-bc04-4e7485117aa1" [label="spam"];
"c181fe42-fd3c-48db-968a-502f8dd462a4" [label="ldn"];
"51b9477a-0326-4774-8622-24d1d869a283" [label="ham"];
"16f6aecd-c675-4291-867c-6c64d27eb3fc" [label="spam"];
"adb05303-813a-4fe0-bf98-c319eb70be48" [label="spam"];
"959b4c0c-1821-446d-94a1-c619c2decfcd" -> "18665160-b058-437f-9b2e-05df2eb55661" [label="0"];
"18665160-b058-437f-9b2e-05df2eb55661" -> "2eb9860d-d241-45ca-85e6-cbd80fe2ebf7" [label="0"];
"2eb9860d-d241-45ca-85e6-cbd80fe2ebf7" -> "bcbcc17c-9e2a-4bd4-a039-6e51fde5f8fd" [label="0"];
"bcbcc17c-9e2a-4bd4-a039-6e51fde5f8fd" -> "ca091fc7-8a4e-4970-9ec3-485a4628ad29" [label="0"];
"ca091fc7-8a4e-4970-9ec3-485a4628ad29" -> "aac20872-1aac-499d-b2b5-caf0ef56eff3" [label="0"];
"ca091fc7-8a4e-4970-9ec3-485a4628ad29" -> "18aa8685-a6e8-4d76-bad5-ccea922bb14d" [label="1"];
"bcbcc17c-9e2a-4bd4-a039-6e51fde5f8fd" -> "3f7f30b1-4dbb-4459-9f25-358ad3c6d50b" [label="1"];
"2eb9860d-d241-45ca-85e6-cbd80fe2ebf7" -> "44d1f972-cd97-4636-b6e6-a389bf560656" [label="1"];
"18665160-b058-437f-9b2e-05df2eb55661" -> "7f3c8562-69b5-47a9-8ee4-898bd4b6b506" [label="1"];
"7f3c8562-69b5-47a9-8ee4-898bd4b6b506" -> "a6f22325-8841-4a81-bc04-4e7485117aa1" [label="0"];
"7f3c8562-69b5-47a9-8ee4-898bd4b6b506" -> "c181fe42-fd3c-48db-968a-502f8dd462a4" [label="1"];
"c181fe42-fd3c-48db-968a-502f8dd462a4" -> "51b9477a-0326-4774-8622-24d1d869a283" [label="0"];
"c181fe42-fd3c-48db-968a-502f8dd462a4" -> "16f6aecd-c675-4291-867c-6c64d27eb3fc" [label="1"];
"959b4c0c-1821-446d-94a1-c619c2decfcd" -> "adb05303-813a-4fe0-bf98-c319eb70be48" [label="1"];
}

這樣我們便可以使用Graphviz將決策樹繪制出來
with open('lenses.dot', 'w') as f:
dot = clf.tree.dotify()
f.write(dot)

dot -Tgif lenses.dot -o lenses.gif

效果如下:

使用生成的決策樹進(jìn)行分類

對(duì)未知數(shù)據(jù)進(jìn)行預(yù)測(cè)，主要是根據(jù)樹中的節(jié)點(diǎn)遞歸的找到葉子節(jié)點(diǎn)即可。z這里可以通過為遞歸進(jìn)行優(yōu)化，代碼實(shí)現(xiàn)如下:
def classify(self, data_vect, feat_names=None, tree=None):
''' 根據(jù)構(gòu)建的決策樹對(duì)數(shù)據(jù)進(jìn)行分類
'''
if tree is None:
tree = self.tree

if feat_names is None:
feat_names = self.feat_names

# Recursive base case.
if type(tree) is not dict:
return tree

feature = list(tree.keys())[0]
value = data_vect[feat_names.index(feature)]
sub_tree = tree[feature][value]

return self.classify(feat_names, data_vect, sub_tree)

決策樹的存儲(chǔ)

通過字典表示決策樹，這樣我們可以通過內(nèi)置的pickle或者json模塊將其存儲(chǔ)到硬盤上，同時(shí)也可以從硬盤中讀取樹結(jié)構(gòu)，這樣在數(shù)據(jù)集很大的時(shí)候可以節(jié)省構(gòu)建決策樹的時(shí)間.
def dump_tree(self, filename, tree=None):
''' 存儲(chǔ)決策樹
'''
if tree is None:
tree = self.tree

with open(filename, 'w') as f:
pickle.dump(tree, f)

def load_tree(self, filename):
''' 加載樹結(jié)構(gòu)
'''
with open(filename, 'r') as f:
tree = pickle.load(f)
self.tree = tree
return tree

總結(jié)

本文一步步實(shí)現(xiàn)了決策樹的實(shí)現(xiàn), 其中使用了ID3算法確定最佳劃分屬性，并通過Graphviz可視化了構(gòu)建的決策樹。

參考:

《Machine Learning in Action》

數(shù)據(jù)挖掘系列（6）決策樹分類算法