精华内容
下载资源
问答
  • [ID3算法是J. RossQuinlan在1975提出的分类预测算法,当时还没有数据挖掘吧,哈哈哈。该算法的核心是“信息熵”,属于数学问题,我也是从这里起发现数据挖掘最底层最根本的0 引言决策树的目的在于构造一颗树像下面...

    [ID3算法是J. RossQuinlan在1975提出的分类预测算法,当时还没有数据挖掘吧,哈哈哈。该算法的核心是“信息熵”,属于数学问题,我也是从这里起发现数据挖掘最底层最根本的

    0 引言

    决策树的目的在于构造一颗树像下面这样的树。

    80e637892a7b17669e1d5fb56bc720c9.png

    图1

    a4a35fa2ae23dd319f6b43ab1a7eb025.png

    图2

    1. 如何构造呢?

    1.1   参考资料。       本例以图2为例,并参考了以下资料。 (1)

    http://www.cnblogs.com/zhangchaoyang/articles/2196631.html

    写的东西非常经典。 (2)

    http://blog.sina.com.cn/s/blog_67bc5aa60100qays.html

    (3)机器学习(Tom.Mitchell著) 第三章 决策树,里面详细介绍了信息增益的计算,和熵的计算。建议大家参考

    1.2 数据集(训练数据集)

    outlook

    temperature

    humidity

    windy

    play sunny hot high FALSE no sunny hot high TRUE no overcast hot high FALSE yes rainy mild high FALSE yes rainy cool normal FALSE yes rainy cool normal TRUE no overcast cool normal TRUE yes sunny mild high FALSE no sunny cool normal FALSE yes rainy mild normal FALSE yes sunny mild normal TRUE yes overcast mild high TRUE yes overcast hot normal FALSE yes rainy mild high TRUE no

    1.3 构造原则—选信息增益最大的 从图中知,一共有四个属性,outlook     temperature    humidity  windy,首先选哪一个作为树的第一个节点呢。答案是选信息增益越大的作为开始的节点。信息增益的计算公式如下:

    b4313774a5a40348183ad0ec9ff8418b.png Entropy(s)是熵,S样本集,Sv是子集。熵的计算公式如下:

    6bbaeeebdaf2359b7c624879f7e7c7b7.png 举例: 根据以上的数据,我们只知道新的一天打球的概率是9/14,不打的概率是5/14。此时的熵为

    a31aabc4ea83e07ed9f79bfdfca265f0.png

    对每项指标分别统计:在不同的取值下打球和不打球的次数。

    table 2

    outlook

    temperature

    humidity

    windy

    play   yes no   yes no   yes no   yes no yes no sunny 2 3 hot 2 2 high 3 4 FALSE 6 2 9 5 overcast 4 0 mild 4 2 normal 6 1 TRUR 3 3     rainy 3 2 cool 3 1

    下面我们计算当已知变量outlook的值时,信息熵为多少。[所谓决策树就是用树来帮助我们做决策,从树的根节点开始一级一级的访问节点,直到叶子节点,也就完成了决策的过程。决策树算法是描述用已知的样本来构建决策树的过程,这

    outlook=sunny时,2/5的概率打球,3/5的概率不打球。entropy=0.971

    outlook=overcast时,entropy=0

    outlook=rainy时,entropy=0.971

    而根据历史统计数据,outlook取值为sunny、overcast、rainy的概率分别是5/14、4/14、5/14,所以当已知变量outlook的值时,信息熵为:5/14 × 0.971 + 4/14 × 0 + 5/14 × 0.971 = 0.693

    这样的话系统熵就从0.940下降到了0.693,信息增溢gain(outlook)为0.940-0.693=0.247

    同样可以计算出gain(temperature)=0.029,gain(humidity)=0.152,gain(windy)=0.048。

    gain(outlook)最大(即outlook在第一步使系统的信息熵下降得最快),所以决策树的根节点就取outlook。

    1.4 为什么选信息增益最大的? 根据参考资料(2)的结论是:信息增益量越大,这个属性作为一棵树的根节点就能使这棵树更简洁(2)

    66f74c6e38ce932fed7a32573cbe5f1c.png

    1.5 递归:

    接下来要确定N1取temperature、humidity还是windy?在已知outlook=sunny的情况,根据历史数据,我们作出类似table 2的一张表,分别计算gain(temperature)、gain(humidity)和gain(windy),选最大者为N1。

    依此类推,构造决策树。当系统的信息熵降为0时,就没有必要再往下构造决策树了,此时叶子节点都是纯的--这是理想情况。最坏的情况下,决策树的高度为属性(决策变量)的个数,叶子节点不纯(这意味着我们要以一定的概率来作出决策)。

    1.6 递归结束的条件: 如果Examples都为正,那么返回label =+ 的单结点树Root , 熵为0

     如果Examples都为反,那么返回label =- 的单结点树Root , 熵为0

     如果Attributes为空,那么返回单结点树Root,label=Examples中最普遍的

    2. 伪代码

    5c90381b3397b676b541911b0f9bcb97.png

    3. java 实现 此仅贴主要的代码,源码请到我的github下载:

    https://github.com/Bellonor/myHadoopProject/tree/master/com.homework/src/sequence/machinelearning/decisiontree/sequence/machinelearning/decisiontree/myid3

    package sequence.machinelearning.decisiontree.myid3;

    import java.io.BufferedReader;

    import java.io.File;

    import java.io.FileReader;

    import java.io.FileWriter;

    import java.io.IOException;

    import java.util.ArrayList;

    import java.util.HashMap;

    import java.util.Iterator;

    import java.util.LinkedList;

    import java.util.List;

    import java.util.Map;

    import java.util.regex.Matcher;

    import java.util.regex.Pattern;

    import java.util.LinkedList;

    public class MyID3 {

    private static LinkedList attribute = new LinkedList(); // 存储属性的名称

    private static LinkedList> attributevalue = new LinkedList>(); // 存储每个属性的取值

    private static LinkedList data = new LinkedList();; // 原始数据

    public static final String patternString = "@attribute(.*)[{](.*?)[}]";

    public static String[] yesNo;

    public static TreeNode root;

    /**

    *

    * @param lines 传入要分析的数据集

    * @param index 哪个属性?attribute的index

    */

    public Double getGain(LinkedList lines,int index){

    Double gain=-1.0;

    List li=new ArrayList();

    //统计Yes No的次数

    for(int i=0;i

    Double sum=0.0;

    for(int j=0;j

    String[] line=lines.get(j);

    //data为结构化数据,如果数据最后一列==yes,sum+1

    if(line[line.length-1].equals(yesNo[i])){

    sum=sum+1;

    }

    }

    li.add(sum);

    }

    //计算Entropy(S)计算Entropy(S) 见参考书《机器学习 》Tom.Mitchell著 第3.4.1.2节

    Double entropyS=TheMath.getEntropy(lines.size(), li);

    //下面计算gain

    List la=attributevalue.get(index);

    List lasv=new ArrayList();

    for(int n=0;n

    String attvalue=la.get(n);

    //统计Yes No的次数

    List lisub=new ArrayList();//如:sunny 是yes时发生的次数,是no发生的次数

    Double Sv=0.0;//公式3.4中的Sv 见参考书《机器学习(Tom.Mitchell著)》

    for(int i=0;i

    Double sum=0.0;

    for(int j=0;j

    String[] line=lines.get(j);

    //data为结构化数据,如果数据最后一列==yes,sum+1

    if(line[index].equals(attvalue)&&line[line.length-1].equals(yesNo[i])){

    sum=sum+1;

    }

    }

    Sv=Sv+sum;//计算总数

    lisub.add(sum);

    }

    //计算Entropy(S) 见参考书《机器学习(Tom.Mitchell著)》

    Double entropySv=TheMath.getEntropy(Sv.intValue(), lisub);

    //

    Point p=new Point();

    p.setSv(Sv);

    p.setEntropySv(entropySv);

    lasv.add(p);

    }

    gain=TheMath.getGain(entropyS,lines.size(),lasv);

    return gain;

    }

    //寻找最大的信息增益,将最大的属性定为当前节点,并返回该属性所在list的位置和gain值

    public Maxgain getMaxGain(LinkedList lines){

    if(lines==null||lines.size()<=0){

    return null;

    }

    Maxgain maxgain = new Maxgain();

    Double maxvalue=0.0;

    int maxindex=-1;

    for(int i=0;i

    Double tmp=getGain(lines,i);

    if(maxvalue< tmp){

    maxvalue=tmp;

    maxindex=i;

    }

    }

    maxgain.setMaxgain(maxvalue);

    maxgain.setMaxindex(maxindex);

    return maxgain;

    }

    //剪取数组

    public LinkedList filterLines(LinkedList lines, String attvalue, int index){

    LinkedList newlines=new LinkedList();

    for(int i=0;i

    String[] line=lines.get(i);

    if(line[index].equals(attvalue)){

    newlines.add(line);

    }

    }

    return newlines;

    }

    public void createDTree(){

    root=new TreeNode();

    Maxgain maxgain=getMaxGain(data);

    if(maxgain==null){

    System.out.println("没有数据集,请检查!");

    }

    int maxKey=maxgain.getMaxindex();

    String nodename=attribute.get(maxKey);

    root.setName(nodename);

    root.setLiatts(attributevalue.get(maxKey));

    insertNode(data,root,maxKey);

    }

    /**

    *

    * @param lines 传入的数据集,作为新的递归数据集

    * @param node 深入此节点

    * @param index 属性位置

    */

    public void insertNode(LinkedList lines,TreeNode node,int index){

    List liatts=node.getLiatts();

    for(int i=0;i

    String attname=liatts.get(i);

    LinkedList newlines=filterLines(lines,attname,index);

    if(newlines.size()<=0){

    System.out.println("出现异常,循环结束");

    return;

    }

    Maxgain maxgain=getMaxGain(newlines);

    double gain=maxgain.getMaxgain();

    Integer maxKey=maxgain.getMaxindex();

    //不等于0继续递归,等于0说明是叶子节点,结束递归。

    if(gain!=0){

    TreeNode subnode=new TreeNode();

    subnode.setParent(node);

    subnode.setFatherAttribute(attname);

    String nodename=attribute.get(maxKey);

    subnode.setName(nodename);

    subnode.setLiatts(attributevalue.get(maxKey));

    node.addChild(subnode);

    //不等于0,继续递归

    insertNode(newlines,subnode,maxKey);

    }else{

    TreeNode subnode=new TreeNode();

    subnode.setParent(node);

    subnode.setFatherAttribute(attname);

    //叶子节点是yes还是no?取新行中最后一个必是其名称,因为只有完全是yes,或完全是no的情况下才会是叶子节点

    String[] line=newlines.get(0);

    String nodename=line[line.length-1];

    subnode.setName(nodename);

    node.addChild(subnode);

    }

    }

    }

    //输出决策树

    public void printDTree(TreeNode node)

    {

    if(node.getChildren()==null){

    System.out.println("--"+node.getName());

    return;

    }

    System.out.println(node.getName());

    List childs = node.getChildren();

    for (int i = 0; i < childs.size(); i++)

    {

    System.out.println(childs.get(i).getFatherAttribute());

    printDTree(childs.get(i));

    }

    }

    public static void main(String[] args) {

    // TODO Auto-generated method stub

    MyID3 myid3 = new MyID3();

    myid3.readARFF(new File("datafile/decisiontree/test/in/weather.nominal.arff"));

    myid3.createDTree();

    myid3.printDTree(root);

    }

    //读取arff文件,给attribute、attributevalue、data赋值

    public void readARFF(File file) {

    try {

    FileReader fr = new FileReader(file);

    BufferedReader br = new BufferedReader(fr);

    String line;

    Pattern pattern = Pattern.compile(patternString);

    while ((line = br.readLine()) != null) {

    if (line.startsWith("@decision")) {

    line = br.readLine();

    if(line=="")

    continue;

    yesNo = line.split(",");

    }

    Matcher matcher = pattern.matcher(line);

    if (matcher.find()) {

    attribute.add(matcher.group(1).trim());

    String[] values = matcher.group(2).split(",");

    ArrayList al = new ArrayList(values.length);

    for (String value : values) {

    al.add(value.trim());

    }

    attributevalue.add(al);

    } else if (line.startsWith("@data")) {

    while ((line = br.readLine()) != null) {

    if(line=="")

    continue;

    String[] row = line.split(",");

    data.add(row);

    }

    } else {

    continue;

    }

    }

    br.close();

    } catch (IOException e1) {

    e1.printStackTrace();

    }

    }

    }

    [上一篇博客写了ID3算法的简单实现 这一篇讲讲ID3的原理 写这个算法是由于某同事的同学的毕业设计,关系够复杂的了==|||,写完这个算法,突然对数据挖掘有了兴趣,决定把C4

    展开全文
  • 数据挖掘C4.5算法实现

    2021-06-05 13:45:50
    实现c4.5算法。要求: 1.给定一个训练数据集,得到决策树并用图形显示该决策树。 2. 用学习得到的决策树对测试集进行判决或分类,得到测试集上的分类错误率。 2实验过程: 数据集 本实验采用西瓜数据集2.0 ...

    1实验目的:

    实现c4.5算法。要求:

    1.给定一个训练数据集,得到决策树并用图形显示该决策树。

    2. 用学习得到的决策树对测试集进行判决或分类,得到测试集上的分类错误率。

    2实验过程:

    1. 数据集

         本实验采用西瓜数据集2.0

    dataSet=[['青绿','蜷缩','浊响','清晰','凹陷','硬滑','是'],
                 ['乌黑','蜷缩','沉闷','清晰','凹陷','硬滑','是'],
                 ['乌黑','蜷缩','浊响','清晰','凹陷','硬滑','是'],
                 ['青绿','蜷缩','沉闷','清晰','凹陷','硬滑','是'],
                 ['浅白','蜷缩','浊响','清晰','凹陷','硬滑','是'],
                 ['青绿','稍蜷','浊响','清晰','稍凹','软粘','是'],
                 ['乌黑','稍蜷','浊响','稍糊','稍凹','软粘','是'],
                 ['乌黑','稍蜷','浊响','清晰','稍凹','硬滑','是'],
                 ['乌黑','稍蜷','沉闷','稍糊','稍凹','硬滑','否'],
                 ['青绿','硬挺','清脆','清晰','平坦','软粘','否'],
                 ['浅白','硬挺','清脆','模糊','平坦','硬滑','否'],
                 ['浅白','蜷缩','浊响','模糊','平坦','软粘','否'],
                 ['青绿','稍蜷','浊响','稍糊','凹陷','硬滑','否'],
                 ['浅白','稍蜷','沉闷','稍糊','凹陷','硬滑','否'],
                 ['乌黑','稍蜷','浊响','清晰','稍凹','软粘','否'],
                 ['浅白','蜷缩','浊响','模糊','平坦','硬滑','否'],
                 ['青绿','蜷缩','沉闷','稍糊','稍凹','硬滑','否']]
    
    labels=['色泽','根蒂','敲声','纹理','脐部','触感']

      2.C4.5算法实现

       

    2.1定义函数:计算信息熵

    # 函数说明:计算给定数据集的经验熵(香农熵)
    def calcShannonEnt(dataSet):
        numEntires = len(dataSet)                       #返回数据集的行数
        labelCounts = {}                               #保存每个标签(Label)出现次数的字典
        for featVec in dataSet:                        #对每组特征向量进行统计
            currentLabel = featVec[-1]                 #提取标签(Label)信息
            if currentLabel not in labelCounts.keys(): #如果标签(Label)没有放入统计次数的字典,添加进去
                labelCounts[currentLabel] = 0
            labelCounts[currentLabel] += 1             #Label计数
        shannonEnt = 0.0                               #经验熵(香农熵)
        for key in labelCounts:                        #计算香农熵
            prob = float(labelCounts[key]) / numEntires#选择该标签(Label)的概率
            shannonEnt -= prob * log(prob, 2)          #利用公式计算
        return shannonEnt                              #返回经验熵(香农熵)
    

    2.2 定义函数:将数据集中某一特征所在的列去掉

    def splitDataSet(dataSet, axis, value):
        retDataSet = []                                #创建返回的数据集列表
        for featVec in dataSet:                        #遍历数据集
            if featVec[axis] == value:
                reducedFeatVec = featVec[:axis]        #去掉axis特征
                reducedFeatVec.extend(featVec[axis+1:])#将符合条件的添加到返回的数据集
                retDataSet.append(reducedFeatVec)
        return retDataSet                              #返回划分后的数据集

    2.3定义函数:计算信息增益率,并返回当前数据集的信息增益率最大的属性

    def chooseBestFeatureToSplit(dataSet,label):
        numFeatures = len(label)                  #特征数量
        baseEntropy = calcShannonEnt(dataSet)                 #计算数据集的香农熵
        bestInfoGainRatio = 0.0                                    #信息增益率
        bestFeature = -1                                      #最优特征的索引值
        
        for i in range(numFeatures):                          #遍历所有特征
            #获取dataSet的第i个所有特征
            featList = [example[i] for example in dataSet]
            uniqueVals = set(featList)                         #创建set集合{},元素不可重复
            newEntropy = 0.0                                   #经验条件熵
            IV = 1e-5
            for value in uniqueVals:                           #计算信息增益
                subDataSet = splitDataSet(dataSet, i, value)   #subDataSet划分后的子集
                prob = len(subDataSet) / float(len(dataSet))   #计算子集的概率
                newEntropy += prob * calcShannonEnt(subDataSet)#根据公式计算经验条件熵
                IV -= prob * log(prob,2)                       #计算IV
            infoGain = baseEntropy - newEntropy                #信息增益
            Gain_ratio = infoGain/IV                           #增益率
            # print("第%d个特征的增益为%.3f" % (i, infoGain))   #打印每个特征的信息增益
            if (Gain_ratio > bestInfoGainRatio):                      #计算信息增益
                bestInfoGainRatio = Gain_ratio                        #更新信息增益,找到最大的信息增益
                bestFeature = i                                #记录信息增益最大的特征的索引值
        return bestFeature                                     #返回信息增益最大的特征的索引值

    2.4定义函数:统计分类数组中类别最多的标签

    def majorityCnt(classList):
        classCount = {}
        for vote in classList:#统计classList中每个元素出现的次数
            if vote not in classCount.keys():
                classCount[vote] = 0
            classCount[vote] += 1
        sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1), reverse = True)#根据字典的值降序排序
        return sortedClassCount[0][0]#返回classList中出现次数最多的元素

    2.5定义函数:判断所有样本在所有属性上取值是否相同

    def isSame(dataSet):
        temp = dataSet[0]
        for data in dataSet:
            i =0
            while i < len(dataSet[0]):
                if temp[i] != data[i]:
                    return 0
                i = i+1
        return 1

    2.6定义函数:创建决策树

    def createTree(dataSet,label,featLabels,G,parentId,edge_name,dataSet_orgin,label_orgin):
        label2 = label[:]
        nowId = G.number_of_nodes()+1                          #记录递归栈中本层的节点编号
        classList = [example[-1] for example in dataSet]       #取分类标签(是否放贷:yes or no)
        if classList.count(classList[0]) == len(classList):    #如果类别完全相同则停止继续划分case1
            print("nowId1==",nowId,"parentId1==",parentId)
            G.add_node(nowId,label=classList[0],fontname="Microsoft YaHei", style="filled",color="#B4E7B7")
            print("edge_name1==",edge_name)
            G.add_edge(parentId,nowId,color="#B4DBFF", penwidth=1.5, fontsize=12,fontname="Microsoft YaHei", label=edge_name)
            return classList[0]
        
        if (len(label) == 0 or isSame(dataSet)):                               #case2:当前属性集为空或者所有样本在所有属性上取值相同,返回出现次数最多的类标签
            maxLabel = majorityCnt(classList)
            G.add_node(nowId,label=maxLabel,fontname="Microsoft YaHei", style="filled",color="#dddddd")
            G.add_edge(parentId,nowId,color="#B4DBFF", penwidth=1.5, fontsize=12,fontname="Microsoft YaHei", label=edge_name)
            return maxLabel
        bestFeat = chooseBestFeatureToSplit(dataSet,label)           #选择最优特征
        print('bestFeat==',bestFeat,'labels==',labels)
        bestFeatLabel = label[bestFeat]                       #最优特征的标签
        #先把这个最优特征的点加到图中
        print("nowId2==",nowId,"parentId2==",parentId)
        G.add_node(nowId,label=bestFeatLabel,fontname="Microsoft YaHei", style="filled",color="#1296db")
        if parentId != -1:
                print('edgename2==',edge_name)
                print("nowId3==",nowId,"parentId3==",parentId)
                G.add_edge(parentId,nowId,color="#B4DBFF", penwidth=1.5, fontsize=12,fontname="Microsoft YaHei", label=edge_name)
        print("bestFeatLabel",bestFeatLabel)
        
        featLabels.append(bestFeatLabel)
        myTree = {bestFeatLabel:{}}                            #根据最优特征的标签生成树
        del(label2[bestFeat])                                  #删除已经使用特征标签
        orginIndex = label_orgin.index(bestFeatLabel)                      #输出最优特征在原始数据集的位置
        featValues = [example[orginIndex] for example in dataSet_orgin]#得到训练集中所有最优特征的属性值
        uniqueVals = set(featValues)                           #去掉重复的属性值
        print("uniqueVals",uniqueVals)
        
        fatherDataSet = []
        for value in uniqueVals:                               #遍历特征,创建决策树。
            newDataSet = splitDataSet(dataSet, bestFeat, value)
            if newDataSet:
                for item in newDataSet:
                    fatherDataSet.append(item)
           
        for value in uniqueVals:                               #遍历特征,创建决策树。
            print("value==",value)
            newDataSet = splitDataSet(dataSet, bestFeat, value)
            if newDataSet:
                #print('newDataSet==',newDataSet)
                myTree[bestFeatLabel][value] = createTree(newDataSet,label2, featLabels,G,nowId,value,dataSet_orgin,label_orgin)
            else:
                #print('fatherDataSet==',fatherDataSet)
                classList = [example[-1] for example in fatherDataSet]
                mlabel = majorityCnt(classList)
                print("mlabel==",mlabel)
                nextId = G.number_of_nodes()+1 
                G.add_node(nextId,label=mlabel,fontname="Microsoft YaHei", style="filled",color="#B4E7B7")
                G.add_edge(nowId,nextId,color="#B4DBFF", penwidth=1.5, fontsize=12,fontname="Microsoft YaHei", label=value)
        return myTree
    

    2.7定义函数:测试模型

    def judge(node,data,labels):
        key=list(node.keys())[0]
        node = node[key]
        idx = labels.index(key)
        pred = None
        for key in node:
            if data[idx] == key:
                if isinstance(node[key],dict):
                    pred = judge(node[key],data,labels)
                else:
                    pred = node[key]
                
        return pred

    2.8划分数据集训练模型

    G = pgh.AGraph()
    #划分数据集
    np.random.shuffle(readyArr)
    offset = int(len(readyArr)*0.9)
    trainData = readyArr[:offset]
    testData = readyArr[offset:]
    featLabels = []
    Trees = createTree(trainData,labels,featLabels,G,-1,'0',trainData,labels)
    print(Trees)
    G.layout()
    G.draw(r'C:\Users\admin\OneDrive\anaconda\c45test.dot')

    2.9测试模型,并计算错误率

    errSum =0
    for data in testData:
        test_result = judge(Trees,data,labels)
        if test_result != data[-1]:
            errSum = errSum +1
    totalNum = len(testData)
    print("出错率为",float(errSum/totalNum))

    3实验总结:

    1. 在决策树生成过程中, 由于为了方便计算决策树分支的最优属性,所以会删除已经作为过最优属性的属性,当某个属性被用到后直接删除后,在后面再使用到该属性时会出现错误。因此,需要改正算法,思路是在递归时,只有在进入分类属性X下一层递归时才会删除当前分类属性X,当前分类属性X平行的节点则不会删除分类属性X.
    2. 分类到某分支时,会出现某属性A的某个取值v没有样本数据的情况,需要将该属性A当前样本的最多的分类作为v的分类。
    3. 另外,也采用sklearn进行训练,对比C4.5算法结果,发现不一样。通过阅读源码,得知sklearn 里面的决策树采用的是基尼指数,而C4.5决策树采用的是信息增益率来选择最优分类属性。

     

     

     

     

     

    展开全文
  • ​​​​​​...request_id=&bz_id=102&utm_term=id3%E5%86%B3%E7%AD%96%E6%A0%91%E7%AE%97%E6%B3%95C++%E5%AE%9E%E7%8E%B0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~

    转自:数据挖掘-决策树ID3分类算法的C++实现_Coding for Dreams-CSDN博客

    原链接:数据挖掘-决策树ID3分类算法的C++实现_Coding for Dreams-CSDN博客

    如有侵权,请联系,立即删除! 

    #include <iostream>
    #include <string>
    #include <vector>
    #include <map>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    #define MAXLEN 6//输入每行的数据个数
     
    //多叉树的实现 
    //1 广义表
    //2 父指针表示法,适于经常找父结点的应用
    //3 子女链表示法,适于经常找子结点的应用
    //4 左长子,右兄弟表示法,实现比较麻烦
    //5 每个结点的所有孩子用vector保存
    //教训:数据结构的设计很重要,本算法采用5比较合适,同时
    //注意维护剩余样例和剩余属性信息,建树时横向遍历考循环属性的值,
    //纵向遍历靠递归调用
     
    vector <vector <string> > state;//实例集
    vector <string> item(MAXLEN);//对应一行实例集
    vector <string> attribute_row;//保存首行即属性行数据
    string end("end");//输入结束
    string yes("yes");
    string no("no");
    string blank("");
    map<string,vector < string > > map_attribute_values;//存储属性对应的所有的值
    int tree_size = 0;
    struct Node{//决策树节点
    	string attribute;//属性值
    	string arrived_value;//到达的属性值
    	vector<Node *> childs;//所有的孩子
    	Node(){
    		attribute = blank;
    		arrived_value = blank;
    	}
    };
    Node * root;
     
    //根据数据实例计算属性与值组成的map
    void ComputeMapFrom2DVector(){
    	unsigned int i,j,k;
    	bool exited = false;
    	vector<string> values;
    	for(i = 1; i < MAXLEN-1; i++){//按照列遍历
    		for (j = 1; j < state.size(); j++){
    			for (k = 0; k < values.size(); k++){
    				if(!values[k].compare(state[j][i])) exited = true;
    			}
    			if(!exited){
    				values.push_back(state[j][i]);//注意Vector的插入都是从前面插入的,注意更新it,始终指向vector头
    			}
    			exited = false;
    		}
    		map_attribute_values[state[0][i]] = values;
    		values.erase(values.begin(), values.end());
    	}	
    }
     
    //根据具体属性和值来计算熵
    double ComputeEntropy(vector <vector <string> > remain_state, string attribute, string value,bool ifparent){
    	vector<int> count (2,0);
    	unsigned int i,j;
    	bool done_flag = false;//哨兵值
    	for(j = 1; j < MAXLEN; j++){
    		if(done_flag) break;
    		if(!attribute_row[j].compare(attribute)){
    			for(i = 1; i < remain_state.size(); i++){
    				if((!ifparent&&!remain_state[i][j].compare(value)) || ifparent){//ifparent记录是否算父节点
    					if(!remain_state[i][MAXLEN - 1].compare(yes)){
    						count[0]++;
    					}
    					else count[1]++;
    				}
    			}
    			done_flag = true;
    		}
    	}
    	if(count[0] == 0 || count[1] == 0 ) return 0;//全部是正实例或者负实例
    	//具体计算熵 根据[+count[0],-count[1]],log2为底通过换底公式换成自然数底数
    	double sum = count[0] + count[1];
    	double entropy = -count[0]/sum*log(count[0]/sum)/log(2.0) - count[1]/sum*log(count[1]/sum)/log(2.0);
    	return entropy;
    }
    	
    //计算按照属性attribute划分当前剩余实例的信息增益
    double ComputeGain(vector <vector <string> > remain_state, string attribute){
    	unsigned int j,k,m;
    	//首先求不做划分时的熵
    	double parent_entropy = ComputeEntropy(remain_state, attribute, blank, true);
    	double children_entropy = 0;
    	//然后求做划分后各个值的熵
    	vector<string> values = map_attribute_values[attribute];
    	vector<double> ratio;
    	vector<int> count_values;
    	int tempint;
    	for(m = 0; m < values.size(); m++){
    		tempint = 0;
    		for(k = 1; k < MAXLEN - 1; k++){
    			if(!attribute_row[k].compare(attribute)){
    				for(j = 1; j < remain_state.size(); j++){
    					if(!remain_state[j][k].compare(values[m])){
    						tempint++;
    					}
    				}
    			}
    		}
    		count_values.push_back(tempint);
    	}
    	
    	for(j = 0; j < values.size(); j++){
    		ratio.push_back((double)count_values[j] / (double)(remain_state.size()-1));
    	}
    	double temp_entropy;
    	for(j = 0; j < values.size(); j++){
    		temp_entropy = ComputeEntropy(remain_state, attribute, values[j], false);
    		children_entropy += ratio[j] * temp_entropy;
    	}
    	return (parent_entropy - children_entropy);	
    }
     
    int FindAttriNumByName(string attri){
    	for(int i = 0; i < MAXLEN; i++){
    		if(!state[0][i].compare(attri)) return i;
    	}
    	cerr<<"can't find the numth of attribute"<<endl; 
    	return 0;
    }
     
    //找出样例中占多数的正/负性
    string MostCommonLabel(vector <vector <string> > remain_state){
    	int p = 0, n = 0;
    	for(unsigned i = 0; i < remain_state.size(); i++){
    		if(!remain_state[i][MAXLEN-1].compare(yes)) p++;
    		else n++;
    	}
    	if(p >= n) return yes;
    	else return no;
    }
     
    //判断样例是否正负性都为label
    bool AllTheSameLabel(vector <vector <string> > remain_state, string label){
    	int count = 0;
    	for(unsigned int i = 0; i < remain_state.size(); i++){
    		if(!remain_state[i][MAXLEN-1].compare(label)) count++;
    	}
    	if(count == remain_state.size()-1) return true;
    	else return false;
    }
     
    //计算信息增益,DFS构建决策树
    //current_node为当前的节点
    //remain_state为剩余待分类的样例
    //remian_attribute为剩余还没有考虑的属性
    //返回根结点指针
    Node * BulidDecisionTreeDFS(Node * p, vector <vector <string> > remain_state, vector <string> remain_attribute){
    	//if(remain_state.size() > 0){
    		//printv(remain_state);
    	//}
    	if (p == NULL)
    		p = new Node();
    	//先看搜索到树叶的情况
    	if (AllTheSameLabel(remain_state, yes)){
    		p->attribute = yes;
    		return p;
    	}
    	if (AllTheSameLabel(remain_state, no)){
    		p->attribute = no;
    		return p;
    	}
    	if(remain_attribute.size() == 0){//所有的属性均已经考虑完了,还没有分尽
    		string label = MostCommonLabel(remain_state);
    		p->attribute = label;
    		return p;
    	}
     
    	double max_gain = 0, temp_gain;
    	vector <string>::iterator max_it = remain_attribute.begin();
    	vector <string>::iterator it1;
    	for(it1 = remain_attribute.begin(); it1 < remain_attribute.end(); it1++){
    		temp_gain = ComputeGain(remain_state, (*it1));
    		if(temp_gain > max_gain) {
    			max_gain = temp_gain;
    			max_it = it1;
    		}
    	}
    	//下面根据max_it指向的属性来划分当前样例,更新样例集和属性集
    	vector <string> new_attribute;
    	vector <vector <string> > new_state;
    	for(vector <string>::iterator it2 = remain_attribute.begin(); it2 < remain_attribute.end(); it2++){
    		if((*it2).compare(*max_it)) new_attribute.push_back(*it2);
    	}
    	//确定了最佳划分属性,注意保存
    	p->attribute = *max_it;
    	vector <string> values = map_attribute_values[*max_it];
    	int attribue_num = FindAttriNumByName(*max_it);
    	new_state.push_back(attribute_row);
    	for(vector <string>::iterator it3 = values.begin(); it3 < values.end(); it3++){
    		for(unsigned int i = 1; i < remain_state.size(); i++){
    			if(!remain_state[i][attribue_num].compare(*it3)){
    				new_state.push_back(remain_state[i]);
    			}
    		}
    		Node * new_node = new Node();
    		new_node->arrived_value = *it3;
    		if(new_state.size() == 0){//表示当前没有这个分支的样例,当前的new_node为叶子节点
    			new_node->attribute = MostCommonLabel(remain_state);
    		}
    		else 
    			BulidDecisionTreeDFS(new_node, new_state, new_attribute);
    		//递归函数返回时即回溯时需要1 将新结点加入父节点孩子容器 2清除new_state容器
    		p->childs.push_back(new_node);
    		new_state.erase(new_state.begin()+1,new_state.end());//注意先清空new_state中的前一个取值的样例,准备遍历下一个取值样例
    	}
    	return p;
    }
     
    void Input(){
    	string s;
    	while(cin>>s,s.compare(end) != 0){//-1为输入结束
    		item[0] = s;
    		for(int i = 1;i < MAXLEN; i++){
    			cin>>item[i];
    		}
    		state.push_back(item);//注意首行信息也输入进去,即属性
    	}
    	for(int j = 0; j < MAXLEN; j++){
    		attribute_row.push_back(state[0][j]);
    	}
    }
     
    void PrintTree(Node *p, int depth){
    	for (int i = 0; i < depth; i++) cout << '\t';//按照树的深度先输出tab
    	if(!p->arrived_value.empty()){
    		cout<<p->arrived_value<<endl;
    		for (int i = 0; i < depth+1; i++) cout << '\t';//按照树的深度先输出tab
    	}
    	cout<<p->attribute<<endl;
    	for (vector<Node*>::iterator it = p->childs.begin(); it != p->childs.end(); it++){
    		PrintTree(*it, depth + 1);
    	}
    }
     
    void FreeTree(Node *p){
    	if (p == NULL)
    		return;
    	for (vector<Node*>::iterator it = p->childs.begin(); it != p->childs.end(); it++){
    		FreeTree(*it);
    	}
    	delete p;
    	tree_size++;
    }
     
    int main(){
    	Input();
    	vector <string> remain_attribute;
    	
    	string outlook("Outlook");
    	string Temperature("Temperature");
    	string Humidity("Humidity");
    	string Wind("Wind");
    	remain_attribute.push_back(outlook);
    	remain_attribute.push_back(Temperature);
    	remain_attribute.push_back(Humidity);
    	remain_attribute.push_back(Wind);
    	vector <vector <string> > remain_state;
    	for(unsigned int i = 0; i < state.size(); i++){
    		remain_state.push_back(state[i]); 
    	}
    	ComputeMapFrom2DVector();
    	root = BulidDecisionTreeDFS(root,remain_state,remain_attribute);
    	cout<<"the decision tree is :"<<endl;
    	PrintTree(root,0);
    	FreeTree(root);
    	cout<<endl;
    	cout<<"tree_size:"<<tree_size<<endl;
    	return 0;
    }

     运行结果:

     输入部分为:

    Day Outlook Temperature Humidity Wind PlayTennis
    1 Sunny Hot High Weak no
    2 Sunny Hot High Strong no
    3 Overcast Hot High Weak yes
    4 Rainy Mild High Weak yes
    5 Rainy Cool Normal Weak yes
    6 Rainy Cool Normal Strong no
    7 Overcast Cool Normal Strong yes
    8 Sunny Mild High Weak no
    9 Sunny Cool Normal Weak yes
    10 Rainy Mild Normal Weak yes
    11 Sunny Mild Normal Strong yes
    12 Overcast Mild High Strong yes
    13 Overcast Hot Normal Weak yes
    14 Rainy Mild High Strong no

    END

    展开全文
  • 1.已知:流感训练数据集,预定义两个类别;求类别的描述特征。(要求用ID3算法,写出选择诀策树根节点属性计算过程。假设:诀策属性患流感用D,条件属性头痛用A1表示,肌肉痛A2表示;体温A3表示) ...

    1.已知:流感训练数据集,预定义两个类别;求类别的描述特征。(要求用ID3算法,写出选择诀策树根节点属性计算过程。假设:诀策属性患流感用D,条件属性头痛用A1表示,肌肉痛A2表示;体温A3表示)
    在这里插入图片描述
    答案

    关于第二根节点如何判断在这里插入图片描述

    展开全文
  • 数据挖掘之分类算法

    2021-05-23 10:49:41
    1.2 分类模型的实用性非常适合预测或描述二元或标称类型的数据集不适合序数性数据集的分类不考虑隐含在目标类中的序数关系和继承关系1.3 评价分类方法预测的准确率:正确地预测新的或先前未见过的数据的类标号的能力...
  • 1、K-近邻算法(Knn)其原理为在一个样本空间中,有一些已知分类的样本,当出现一个未知分类的样本,则根据距离这个...2、算法实现步骤(1)计算所有点距离未知点的欧式距离(2)对所有点进行排序(3)找到距离未知点最近的k...
  • 清华大学-数据挖掘理论与算法(国家级精品课)by 袁博老师 《数据挖掘概念与技术》
  • 决策树 ID3算法手动实现 1. ID3算法 决策树中每一个非叶结点对应着一个非类别属性,树枝代表这个属性的值。一个叶结点代表从树根到叶结点之间的路径对应的记录所属的类别属性值。 每一个非叶结点都将与属性中具有...
  • 项目描述 Compute the PageRank scores on the Wikipedia dataset Dataset: WikiData.txt The format of the lines in the file is as ...In this project, you need to report the Top 100 NodeID with their PageRa
  • id3/.classpathid3/.projectid3/.settings/org.eclipse.jdt.core.prefsid3/bin/com/lamp/crf/DecModel.classid3/bin/com/lamp/crf/DecTreeDisplay$1.classid3/bin/...
  • 文章目录前言一、C4.5 算法二、SVM 算法三、KNN算法四、AdaBoost算法五、CART算法六、Apriori算法七、K-Means算法八、朴素贝叶斯(Naive Bayes)算法九、EM算法十、PageRank算法二、使用步骤1.引入库2.读入数据总结 ...
  • 数据挖掘相关算法

    2021-08-23 16:12:29
    数据获取1.1 数据挖掘的对象1.2数据挖掘的步骤1.3支持数据挖掘的关键技术1.4数据仓库1.5数据仓库的模型1.6典型的OLAP操作2 数据准备2.1 维归约/特征提取2.1.1决策树归约2.1.2粗糙集归约2.2 数据变换2.2.1归一化与...
  • 本文主要分析皆来自其他资料,借用较为权威的总结来对我已经学习的这些经典算法做一个极为精简的概述(根据自身经验有一定修改),另外同时附上机器学习实战中作者对各种算法的评价。另外机器学习实战这本书是本人看...
  • 数据挖掘主要分为分类算法,聚类算法和关联规则三大类,这三类基本上涵盖了目前商业市场对算法的所有需求。而这三类里又包含许多经典算法。市面上很多关于数据挖掘算法的介绍深奥难懂,今天就给大家用简单的大白话来...
  • ↑↑↑关注后"星标"Datawhale 每日干货 & 每月组队学习,不错过 Datawhale干货 作者:黄雨龙,中国科学技术大学 对于回归问题,Datawhale已经梳理过完整的实践方案(可点击),本文对多分类的数据挖掘问题做了...
  • 一、ID3算法信息熵。信息熵是用来描述信息的纯度,或者确定性的。已经确定的东西,当然就没有什么信息可以发现了。越是确定的信息,这个值越小,如果信息是均匀分布,这个值就会很大。相反,要是都确定这个值就会很...
  • = 8: print("The third param must be a list as 8 member") exit(-1) gain = I(s[6], s[7]) - E(s[0], s[1], s[2], s[3], s[4], s[5]) print("Gain = {}\n".format(gain)) return gain 主函数 main.py import numpy...
  • knn算法(k-Nearest Neighbor algorithm).是一种经典的分类算法.注意,不是聚类算法.所以这种分类算法必然包括了训练过程.然而和一般性的分类算法不同,knn算法是一种懒惰算法.它并非像其他的分类算法先通过训练建立...
  • C语言简单实现ID3算法

    2021-11-23 17:10:11
    C语言简单实现ID3算法 #include <stdio.h> #include <math.h> typedef struct N_node { int item[100]; } N_node; N_node n[100][100]; N_node f[100][100]; double s[100]; //s数组用于存放信息熵 ...
  • 数据挖掘十大经典算法(1) C4.5_决策树算法机器学习中,决策树是一个预测模型;他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象,而每个分叉路径则代表的某个可能的属性值,而每个叶结点则...
  • 数据挖掘领域十大经典算法之—K-Means算法(超详细附代码) 数据挖掘领域十大经典算法之—SVM算法(超详细附代码) 数据挖掘领域十大经典算法之—Apriori算法 数据挖掘领域十大经典算法之—EM算法 数据挖掘...
  • 1.数据准备: 检查样本属性特征是否一致、完整,不同样本之间是否相互独立 2.特征选择: 选择与类别相关的特征,可大致分为:强相关(能区分类别的属性)、弱相关(能区分部分类别的水属性)、不相关(不能区分...
  • 数据挖掘算法原理与实践:决策树第二关:决策树算法原理第三关:动手实现ID3决策树 第二关:决策树算法原理 #encoding=utf8 import numpy as np # 计算熵 def calcInfoEntropy(label): ''' input: label(narray)...
  • 数据挖掘期末复习------算法

    千次阅读 2021-01-07 16:45:00
    ID3算法: 详细见博客: https://blog.csdn.net/weixin_43216017/article/details/87474045 ID3算法使用的数据特征函数(标准)为信息增益。熵表示的是不确定度,熵越大,不确定度就越大。 熵计算公式 假设在数据S...
  • ID3算法思想分析

    2021-07-11 19:42:45
    ID3算法 ... ID3基本思想: ... ID3算法需要解决的问题是如何选择特征作为划分数据集的标准。在ID3算法中,选择信息增益最大的属性作为当前的特征对数据集分类。信息增益的概念将在下面介绍,通过不断的选...
  • 1 /****************************************************************************2 * *3 * KMEANS ...
  • 决策树是最经常使用的数据挖掘算法,其核心是一个贪心算法,它采用自顶向下的递归方法构建决策树。 目前常用的决策树算法ID3算法、改进的C4.5,C5.0算法和CART算法 ID3算法的核心是在决策树各级节点上选择属性时,...
  • 挑西瓜决策树3.1利用信息增益选择最优划分属性3.2python代码实现二.sk-learn库对西瓜数据集,分别进行ID3、C4.5和CART的算法代码实现1.ID3算法2.C4.5算法3.CART算法三.总结四.参考链接: 一.决策树 在机器学习中,...
  • K-中心点聚类算法 (1)任意选择k个对象作为初始的簇中心点 (2)指派每个剩余对象给离他最近的中心点所表示的簇 (3)选择一个未被选择的中心点直到所有的中心点都被选择过 (4)选择一个未被选择过的非中心点对象...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 33,495
精华内容 13,398
关键字:

数据挖掘id3算法实现