[D]用Python 建立 Decision Tree

谁能给点意见怎样用python 建立一个ID3 algorithm 基础的decisiontree ?? 



herba .
ty

----------------------------
Double行动：
原帖分数：40
加分：40

7 个解决方案

#1

弄懂算法,再实现它.这个和python有特别的关系么?

#2

的确，算法归算法，搞懂了，用其他语言也能实现
用python写算法的话会发现很多地方用起来很方便，列表，循环，迭代，交换等等，可读性也相当好

#3

谢谢各位～～～～～～XD

#4

额，有点问题在写attribute 的时候。我搞不明白怎么用dictionary 方式去分

#5

引用 4 楼  的回复:

额，有点问题在写attribute 的时候。我搞不明白怎么用dictionary 方式去分

贴上你的代码，否则别人不好回答（不知道你的程序框架，数据结构...)

#6

谢谢，提醒。 我的想法是先把程序分成3个部分 第一 写decision tree的

def create_decision_tree(data, attributes, target_attr, fitness_func):
    data    = data[:]
    vals    = [record[target_attr] for record in data]
    default = majority_value(data, target_attr)

 
    if not data or (len(attributes) - 1) <= 0:
        return default

    elif vals.count(vals[0]) == len(vals):
        return vals[0]
    else:
  
        best = choose_attribute(data, attributes, target_attr,
                                fitness_func)

    
        tree = {best:{}}

       
        for val in get_values(data, best):
 
            subtree = create_decision_tree(
                get_examples(data, best, val),
                [attr for attr in attributes if attr != best],
                target_attr,
                fitness_func)

            tree[best][val] = subtree

    return tree

z这个部分解释了所有的attribute

2. 下面一步就是算法了。

def entropy(data, target_attr):

    val_freq     = {}
    data_entropy = 0.0

    for record in data:
        if (val_freq.has_key(record[target_attr])):
            val_freq[record[target_attr]] += 1.0
        else:
            val_freq[record[target_attr]]  = 1.0

    for freq in val_freq.values():
        data_entropy += (-freq/len(data)) * math.log(freq/len(data), 2) 
        
    return data_entropy

3. 怎样得到最好的attribute 

def gain(data, attr, target_attr):
    val_freq       = {}
    subset_entropy = 0.0

    for record in data:
        if (val_freq.has_key(record[attr])):
            val_freq[record[attr]] += 1.0
        else:
            val_freq[record[attr]]  = 1.0

    for val in val_freq.keys():
        val_prob        = val_freq[val] / sum(val_freq.values())
        data_subset     = [record for record in data if record[attr] == val]
        subset_entropy += val_prob * entropy(data_subset, target_attr)

    return (entropy(data, target_attr) - subset_entropy)

下面就是
attribute 
我想是用dictionary的方式 还是mapping 的方式去做比较好呢？》

#7

哦 对了。。还漏了 File I/O