- 浏览: 77744 次
- 性别:
- 来自: 拜月神教
最新评论
-
huangfenghit:
你绝对的大牛~
答复: 阿里巴巴面试感言 -
liuxuejin:
好!慢慢下载来看看
区间树 -
xiaobian:
看不懂,怎么知道是讲的好呢 ?
数据挖掘 决策树ID3算法原理 -
longay00:
不错,很牛,不过没有原理与实验很难相信它的正确性。从代码上看, ...
决策树C4.5算法 -
yangguo:
用我的study方法就可以了。
答复: java最优算法讨论
数据挖掘中决策树C4.5预测算法实现(半成品,还要写规则后煎支及对非离散数据信息增益计算),下一篇博客讲原理
package org.struct.decisiontree; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.TreeSet; /** * @author Leon.Chen */ public class DecisionTreeBaseC4p5 { /** * root node */ private DecisionTreeNode root; /** * visableArray */ private boolean[] visable; private static final int NOT_FOUND = -1; private static final int DATA_START_LINE = 1; private Object[] trainingArray; private String[] columnHeaderArray; /** * forecast node index */ private int nodeIndex; /** * @param args */ @SuppressWarnings("boxing") public static void main(String[] args) { Object[] array = new Object[] { new String[] { "age", "income", "student", "credit_rating", "buys_computer" }, new String[] { "youth", "high", "no", "fair", "no" }, new String[] { "youth", "high", "no", "excellent", "no" }, new String[] { "middle_aged", "high", "no", "fair", "yes" }, new String[] { "senior", "medium", "no", "fair", "yes" }, new String[] { "senior", "low", "yes", "fair", "yes" }, new String[] { "senior", "low", "yes", "excellent", "no" }, new String[] { "middle_aged", "low", "yes", "excellent", "yes" }, new String[] { "youth", "medium", "no", "fair", "no" }, new String[] { "youth", "low", "yes", "fair", "yes" }, new String[] { "senior", "medium", "yes", "fair", "yes" }, new String[] { "youth", "medium", "yes", "excellent", "yes" }, new String[] { "middle_aged", "medium", "no", "excellent", "yes" }, new String[] { "middle_aged", "high", "yes", "fair", "yes" }, new String[] { "senior", "medium", "no", "excellent", "no" }, }; DecisionTreeBaseC4p5 tree = new DecisionTreeBaseC4p5(); tree.create(array, 4); System.out.println("===============END PRINT TREE==============="); System.out.println("===============DECISION RESULT==============="); //tree.forecast(printData, tree.root); } /** * @param printData * @param node */ public void forecast(String[] printData, DecisionTreeNode node) { int index = getColumnHeaderIndexByName(node.nodeName); if (index == NOT_FOUND) { System.out.println(node.nodeName); } DecisionTreeNode[] childs = node.childNodesArray; for (int i = 0; i < childs.length; i++) { if (childs[i] != null) { if (childs[i].parentArrtibute.equals(printData[index])) { forecast(printData, childs[i]); } } } } /** * @param array * @param index */ public void create(Object[] array, int index) { this.trainingArray = Arrays.copyOfRange(array, DATA_START_LINE, array.length); init(array, index); createDecisionTree(this.trainingArray); printDecisionTree(root); } /** * @param array * @return Object[] */ @SuppressWarnings("boxing") public Object[] getMaxGain(Object[] array) { Object[] result = new Object[2]; double gain = 0; int index = -1; for (int i = 0; i < visable.length; i++) { if (!visable[i]) { //TODO ID3 change to C4.5 double value = gainRatio(array, i, this.nodeIndex); System.out.println(value); if (gain < value) { gain = value; index = i; } } } result[0] = gain; result[1] = index; // TODO throws can't forecast this model exception if (index != -1) { visable[index] = true; } return result; } /** * @param array */ public void createDecisionTree(Object[] array) { Object[] maxgain = getMaxGain(array); if (root == null) { root = new DecisionTreeNode(); root.parentNode = null; root.parentArrtibute = null; root.arrtibutesArray = getArrtibutesArray(((Integer) maxgain[1]) .intValue()); root.nodeName = getColumnHeaderNameByIndex(((Integer) maxgain[1]) .intValue()); root.childNodesArray = new DecisionTreeNode[root.arrtibutesArray.length]; insertDecisionTree(array, root); } } /** * @param array * @param parentNode */ public void insertDecisionTree(Object[] array, DecisionTreeNode parentNode) { String[] arrtibutes = parentNode.arrtibutesArray; for (int i = 0; i < arrtibutes.length; i++) { Object[] pickArray = pickUpAndCreateSubArray(array, arrtibutes[i], getColumnHeaderIndexByName(parentNode.nodeName)); Object[] info = getMaxGain(pickArray); double gain = ((Double) info[0]).doubleValue(); if (gain != 0) { int index = ((Integer) info[1]).intValue(); DecisionTreeNode currentNode = new DecisionTreeNode(); currentNode.parentNode = parentNode; currentNode.parentArrtibute = arrtibutes[i]; currentNode.arrtibutesArray = getArrtibutesArray(index); currentNode.nodeName = getColumnHeaderNameByIndex(index); currentNode.childNodesArray = new DecisionTreeNode[currentNode.arrtibutesArray.length]; parentNode.childNodesArray[i] = currentNode; insertDecisionTree(pickArray, currentNode); } else { DecisionTreeNode leafNode = new DecisionTreeNode(); leafNode.parentNode = parentNode; leafNode.parentArrtibute = arrtibutes[i]; leafNode.arrtibutesArray = new String[0]; leafNode.nodeName = getLeafNodeName(pickArray,this.nodeIndex); leafNode.childNodesArray = new DecisionTreeNode[0]; parentNode.childNodesArray[i] = leafNode; } } } /** * @param node */ public void printDecisionTree(DecisionTreeNode node) { System.out.println(node.nodeName); DecisionTreeNode[] childs = node.childNodesArray; for (int i = 0; i < childs.length; i++) { if (childs[i] != null) { System.out.println(childs[i].parentArrtibute); printDecisionTree(childs[i]); } } } /** * init data * * @param dataArray * @param index */ public void init(Object[] dataArray, int index) { this.nodeIndex = index; // init data this.columnHeaderArray = (String[]) dataArray[0]; visable = new boolean[((String[]) dataArray[0]).length]; for (int i = 0; i < visable.length; i++) { if (i == index) { visable[i] = true; } else { visable[i] = false; } } } /** * @param array * @param arrtibute * @param index * @return Object[] */ public Object[] pickUpAndCreateSubArray(Object[] array, String arrtibute, int index) { List<String[]> list = new ArrayList<String[]>(); for (int i = 0; i < array.length; i++) { String[] strs = (String[]) array[i]; if (strs[index].equals(arrtibute)) { list.add(strs); } } return list.toArray(); } /** * gain(A) * * @param array * @param index * @return double */ public double gain(Object[] array, int index, int nodeIndex) { int[] counts = separateToSameValueArrays(array, nodeIndex); String[] arrtibutes = getArrtibutesArray(index); double infoD = infoD(array, counts); double infoaD = infoaD(array, index, nodeIndex, arrtibutes); return infoD - infoaD; } /** * @param array * @param nodeIndex * @return */ public int[] separateToSameValueArrays(Object[] array, int nodeIndex) { String[] arrti = getArrtibutesArray(nodeIndex); int[] counts = new int[arrti.length]; for (int i = 0; i < counts.length; i++) { counts[i] = 0; } for (int i = 0; i < array.length; i++) { String[] strs = (String[]) array[i]; for (int j = 0; j < arrti.length; j++) { if (strs[nodeIndex].equals(arrti[j])) { counts[j]++; } } } return counts; } /** * gainRatio = gain(A)/splitInfo(A) * * @param array * @param index * @param nodeIndex * @return */ public double gainRatio(Object[] array,int index,int nodeIndex){ double gain = gain(array,index,nodeIndex); int[] counts = separateToSameValueArrays(array, index); double splitInfo = splitInfoaD(array,counts); if(splitInfo != 0){ return gain/splitInfo; } return 0; } /** * infoD = -E(pi*log2 pi) * * @param array * @param counts * @return */ public double infoD(Object[] array, int[] counts) { double infoD = 0; for (int i = 0; i < counts.length; i++) { infoD += DecisionTreeUtil.info(counts[i], array.length); } return infoD; } /** * splitInfoaD = -E|Dj|/|D|*log2(|Dj|/|D|) * * @param array * @param counts * @return */ public double splitInfoaD(Object[] array, int[] counts) { return infoD(array, counts); } /** * infoaD = E(|Dj| / |D|) * info(Dj) * * @param array * @param index * @param arrtibutes * @return */ public double infoaD(Object[] array, int index, int nodeIndex, String[] arrtibutes) { double sv_total = 0; for (int i = 0; i < arrtibutes.length; i++) { sv_total += infoDj(array, index, nodeIndex, arrtibutes[i], array.length); } return sv_total; } /** * ((|Dj| / |D|) * Info(Dj)) * * @param array * @param index * @param arrtibute * @param allTotal * @return double */ public double infoDj(Object[] array, int index, int nodeIndex, String arrtibute, int allTotal) { String[] arrtibutes = getArrtibutesArray(nodeIndex); int[] counts = new int[arrtibutes.length]; for (int i = 0; i < counts.length; i++) { counts[i] = 0; } for (int i = 0; i < array.length; i++) { String[] strs = (String[]) array[i]; if (strs[index].equals(arrtibute)) { for (int k = 0; k < arrtibutes.length; k++) { if (strs[nodeIndex].equals(arrtibutes[k])) { counts[k]++; } } } } int total = 0; double infoDj = 0; for (int i = 0; i < counts.length; i++) { total += counts[i]; } for (int i = 0; i < counts.length; i++) { infoDj += DecisionTreeUtil.info(counts[i], total); } return DecisionTreeUtil.getPi(total, allTotal) * infoDj; } /** * @param index * @return String[] */ @SuppressWarnings("unchecked") public String[] getArrtibutesArray(int index) { TreeSet<String> set = new TreeSet<String>(new SequenceComparator()); for (int i = 0; i < trainingArray.length; i++) { String[] strs = (String[]) trainingArray[i]; set.add(strs[index]); } String[] result = new String[set.size()]; return set.toArray(result); } /** * @param index * @return String */ public String getColumnHeaderNameByIndex(int index) { for (int i = 0; i < columnHeaderArray.length; i++) { if (i == index) { return columnHeaderArray[i]; } } return null; } /** * @param array * @return String */ public String getLeafNodeName(Object[] array,int nodeIndex) { if (array != null && array.length > 0) { String[] strs = (String[]) array[0]; return strs[nodeIndex]; } return null; } /** * @param name * @return int */ public int getColumnHeaderIndexByName(String name) { for (int i = 0; i < columnHeaderArray.length; i++) { if (name.equals(columnHeaderArray[i])) { return i; } } return NOT_FOUND; } }
package org.struct.decisiontree; /** * @author Leon.Chen */ public class DecisionTreeNode { DecisionTreeNode parentNode; String parentArrtibute; String nodeName; String[] arrtibutesArray; DecisionTreeNode[] childNodesArray; }
package org.struct.decisiontree; /** * @author Leon.Chen */ public class DecisionTreeUtil { /** * entropy:Info(T)=(i=1...k)pi*log(2)pi * * @param x * @param total * @return double */ public static double info(int x, int total) { if (x == 0) { return 0; } double x_pi = getPi(x, total); return -(x_pi * logYBase2(x_pi)); } /** * log2y * * @param y * @return double */ public static double logYBase2(double y) { return Math.log(y) / Math.log(2); } /** * pi=|C(i,d)|/|D| * * @param x * @param total * @return double */ public static double getPi(int x, int total) { return x / (double) total; } }
package org.struct.decisiontree; import java.util.Comparator; /** * @author Leon.Chen * */ @SuppressWarnings("unchecked") public class SequenceComparator implements Comparator { public int compare(Object o1, Object o2) throws ClassCastException { String str1 = (String) o1; String str2 = (String) o2; return str1.compareTo(str2); } }
评论
2 楼
longay00
2010-11-09
不错,很牛,不过没有原理与实验很难相信它的正确性。从代码上看,博主的编程能力不错。谢谢分享
1 楼
sdscx0530
2010-04-21
老大,我在等着你的原理。
发表评论
-
庞果英雄会 覆盖数字
2013-11-14 15:13 820庞果覆盖数字原题如下 给定整数区间[a,b]和整数区间[x, ... -
2-3 tree
2013-10-09 17:10 714package com.leon.cc; imp ... -
编译原理生成LL1预测分析表
2013-08-11 20:47 5800package com.leon; impo ... -
应用倍增法后缀数组以及RMQ求解N个字符串最长公共子串问题
2011-11-30 16:35 1464/** * @see IOI2009国家集训队论文《后 ... -
谷哥的KOF连招问题
2010-10-09 14:38 1472传说问题是这样的 玩过KOF(拳皇)的人都知道,玩的时候会连招 ... -
KOF
2010-10-09 00:13 0package org.struct.trietree; ... -
ACM/ICPC HDU 1195
2010-09-06 10:37 1860本年度还有8篇博客需要完成 开篇前附加一个看完《盗梦空间》的我 ... -
答复: 阿里巴巴面试感言
2009-10-09 22:27 2147好吧,我承认我闲的蛋疼 问题:3000万条的记录取最大的前50 ... -
正向最大匹配改进算法
2009-05-26 22:11 5809AD.: 2年J2EE经验,熟悉常用数据结构算法,熟悉常 ... -
区间树
2008-07-18 15:47 2143package acmcode; /** * ... -
红黑树初版
2008-07-16 17:20 1532package acmcode; /** * R ... -
四则运算的中缀转后缀,逆波兰表达式求值
2008-04-23 23:10 9005首先描述问题 给定一 ... -
最大0,1子矩阵
2008-04-20 21:16 5990首先描述一下问题 /** * * 时间限制(普 ... -
数据挖掘 决策树ID3算法原理
2008-04-11 22:24 11349上一篇博客写了ID3算法的简单实现 这一篇讲讲ID3的原理 写 ... -
决策树ID3算法
2008-04-01 22:18 7547算了,还是自己修正一个BUG.... package gr ... -
ext2.0 的XMLWriter
2008-02-20 21:04 1247做ext相关的一个example项目,把我们的客户端移植成ex ... -
树与哈夫曼树
2008-02-20 20:50 1546package tree; public ... -
LCS与图算法
2008-02-20 20:46 1193求两个字符串最长公共子串的问题。大体解法是用一个矩阵来记录两个 ... -
《程序员》算法擂台:骑士聚会
2008-02-20 20:40 1172在8×8的棋盘上分布着n个骑士,他们想约在某一个格中聚会。骑士 ...
相关推荐
1、资源内容:基于Matlab实现决策树C4.5算法(源码+数据+教程).rar 2、适用人群:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业或毕业设计,作为“参考资料”使用。 3、解压说明:本资源需要电脑...
数据挖掘中的决策树C4.5算法的实现,用matlab实现
可以完美的实现用于统计学习的算法C4.5分类,完整的matlab程序
数据挖掘十大算法:决策树c4.5算法,可以快速了解c4.5算法原理
决策树c4.5算法简单实现,ID3改进,用C++编程实现
C4.5决策树算法,使用VC++实现的,比较好用
本程序为VS2010编写,其中源程序中包含测试数据。
提出一种基于Kendall和谐系数的C4.5决策树优化算法,用于解决条件属性之间相关性的问题,提高算法属性选择的准确性。在引入系数的基础上运用等价无穷小原理对计算公式进行简化,提高了算法的效率。对改进后的C4.5...
针对决策树C4.5集成算法中基分类器多样性差的问题,提出了修正矩阵correction matrix-C4.5(CMC4.5)集成学习算法,并将其应用于图像自动标注。该算法首先对特征子集进行多样性处理,然后通过构造修正矩阵依次得到基...
c语言的决策树C4.5。数据挖掘中决策树是一种经常要用到的技术,可以用于分析数据,同样也可以用来作预测。决策树的分类模型,以其特有的优点广为人们采用。首先,决策树方法结构简单,便于人们理解;其次,决策树...
C4.5是一种用于分类决策树的算法。
针对决策树C4.5算法在处理数值型因素时比较复杂和分类精度不高等问题,在数据预处理过程中采用云变换进行连续因素离散化,给出了连续属性离散化的具体算法.利用因素空间理论给出一种构造决策树算法的新的启发式函数—...
这款程序仿真特别适合初学者联系,欢迎大家下载
决策树分类算法C4.5的matlab代码实现,可返回训练集和测试集的结果,有详细注释
C4.5 决策树算法源码。C4.5决策树是决策树领域的经典算法。以其为内容的书籍引用率已经达到一万次以上
经典的数据挖掘算法决策树C4.5
C++、决策树、测试数据集、http://www.cnblogs.com/xiaoyi115/p/3696107.html这是博文地址
该文主要讨论如何应用C4.5 算法构造客户CRM等级分类决策树及其在 中的应用。