机器学习之决策树ID3(python完成)

黑石动态
2019-10-19 12:14:03 0

机器学习中的决策树：ID3算法（Python实现）

在机器学习领域，决策树是一种常用的预测模型，它通过一系列属性和属性值之间的映射关系来预测目标值。决策树的每个节点代表一个对象，每个分支代表一个属性，而每个叶子节点则对应从根节点到该叶子节点路径所表示的目标值。决策树通常用于单个输入，但可以通过建立多个独立的决策树来处理多个输入。数据挖掘中广泛使用决策树进行数据分析和预测。

简单了解

例如，考虑以下决策树的示例：

属性：['是否可以在水下生活', '是否有鳍']
根据这两个属性，我们可以判断某个对象是否属于鱼类。

首先需要决定使用哪个属性作为初始分类的标准。这里，我们使用ID3算法。稍后会介绍其改进版本C4.5和CART。

决策树与ID3算法

决策树具有树状结构，每个外部节点表示一个属性的测试，每个分支代表一个测试的结果，每个叶子节点则表示最终的分类结果。分类树（决策树）是一种监督学习方法，主要用于分类任务。决策树通过递归地对数据进行分割，直到所有数据都属于同一类别为止。

决策树的特点包括： - 易于理解和解释，尤其适合标称型数据。 - 对于连续性数据的处理效果较差。

ID3算法

ID3算法的核心在于选择最佳的属性来划分数据集。具体来说，它通过计算每个属性的信息增益来确定最优划分属性。信息增益高的属性更容易区分不同的类别。ID3算法通过不断重复这一过程，直到生成一个可以完美分类训练数据的决策树。

信息增益的计算

信息增益的计算基于信息熵的概念。信息熵用于衡量数据集的混乱程度，信息增益则是通过计算每个属性的信息熵来选择最优划分属性。具体实现时，通过计算每个属性的信息熵和信息增益，选择信息增益最大的属性作为划分依据。

Python代码实现

以下是使用Python实现决策树的示例代码：

```python def create_dataset(): dataset = [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']] labels = ['是否可以在水下生活', '是否有鳍'] return dataset, labels

def calcshannonentropy(dataset): numentries = len(dataset) labelcounts = {} for featvec in dataset: currentlabel = featvec[-1] if currentlabel not in labelcounts.keys(): labelcounts[currentlabel] = 0 labelcounts[current_label] += 1

shannon_entropy = 0.0
for key in label_counts:
    prob = float(label_counts[key]) / num_entries
    shannon_entropy -= prob * math.log2(prob)

return shannon_entropy

def splitdataset(dataset, axis, value): retdataset = [] for featvec in dataset: if featvec[axis] == value: reducedfeatvec = featvec[:axis] reducedfeatvec.extend(featvec[axis + 1:]) retdataset.append(reducedfeatvec) return retdataset

def choosebestfeaturetosplit(dataset): numfeatures = len(dataset[0]) - 1 baseentropy = calcshannonentropy(dataset) bestinfogain = 0.0 best_feature = -1

for i in range(num_features):
    feat_list = [number[i] for number in dataset]
    unique_vals = set(feat_list)
    new_entropy = 0.0

    for value in unique_vals:
        sub_dataset = split_dataset(dataset, i, value)
        prob = len(sub_dataset) / float(len(dataset))
        new_entropy += prob * calc_shannon_entropy(sub_dataset)

    info_gain = base_entropy - new_entropy
    if info_gain > best_info_gain:
        best_info_gain = info_gain
        best_feature = i

return best_feature

def majoritycnt(classlist): classcount = {} for vote in classlist: if vote not in classcount.keys(): classcount[vote] = 0 class_count[vote] += 1

sorted_class_count = sorted(class_count.items(), key=lambda x: x[1], reverse=True)
return sorted_class_count[0][0]

def createtree(dataset, labels): classlist = [example[-1] for example in dataset]

if class_list.count(class_list[0]) == len(class_list):
    return class_list[0]

if len(dataset[0]) == 1:
    return majority_cnt(class_list)

best_feat = choose_best_feature_to_split(dataset)
best_feat_label = labels[best_feat]
my_tree = {best_feat_label: {}}
del(labels[best_feat])

feat_values = [example[best_feat] for example in dataset]
unique_vals = set(feat_values)

for value in unique_vals:
    sub_labels = labels[:]
    my_tree[best_feat_label][value] = create_tree(split_dataset(dataset, best_feat, value), sub_labels)

return my_tree

def classify(inputtree, featlabels, testvec): firststr = list(inputtree.keys())[0] seconddict = inputtree[firststr] featindex = featlabels.index(firststr) classlabel = None

for key in second_dict.keys():
    if test_vec[feat_index] == key:
        if type(second_dict[key]).__name__ == 'dict':
            class_label = classify(second_dict[key], feat_labels, test_vec)
        else:
            class_label = second_dict[key]

return class_label

def storetree(inputtree, filename): import pickle with open(filename, 'wb') as fw: pickle.dump(input_tree, fw)

def grab_tree(filename): import pickle with open(filename, 'rb') as fr: return pickle.load(fr) ```