使用Java实现的ID3算法

这里就不描述ID3算法了。

关于如何使用java实现，其实网上也不少，只是感觉没有拿来就直接能用的，而且，就我搜索到的实现，并没有能够将属性值以及最后的结果加入进来。

算是一个小小的加强版吧。

整个项目已经上传上来了。 项目截图如下：

 

值得说的有几个地方：

1. 从arff之中解析出属性

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

 使用的是正则来进行解析的。这样的解析方式 无法解析数字类型的属性， 比如 属性为numeric or Real的时候就不行了~

 

2. 就我学到的ID3， 熵的计算只有两个计算因子，即 p+ 跟 p- 

我看到有的文章说 熵的计算可以是 p1 p2 ... pn 感觉很奇怪。 因为类似的公式计算出来的熵值居然>1 !

我计算熵值的代码如下：

public static double entropy(int positiveCount, int negativeCount) {
	int sum = positiveCount + negativeCount;
	double positiveP = (double)positiveCount / (double)sum ;
	double negativeP = (double)negativeCount / (double)sum;
	return Math.abs(positiveP * log2(positiveP) + negativeP * log2(negativeP) );
}

 

3. 最后解释一下运行的结果：(数据来源是weka自带的weather.arff)

{
  "attribute": "outlook",
  "options": {
    "rainy": {
      "attribute": "windy",
      "options": {
        
      },
      "subLeafs": {
        "FALSE": {
          "count": 3,
          "attributeValue": "yes",
          "option": "FALSE"
        },
        "TRUE": {
          "count": 2,
          "attributeValue": "no",
          "option": "TRUE"
        }
      }
    },
    "sunny": {
      "attribute": "humidity",
      "options": {
        
      },
      "subLeafs": {
        "normal": {
          "count": 2,
          "attributeValue": "yes",
          "option": "normal"
        },
        "high": {
          "count": 3,
          "attributeValue": "no",
          "option": "high"
        }
      }
    }
  },
  "subLeafs": {
    "overcast": {
      "count": 4,
      "attributeValue": "yes",
      "option": "overcast"
    }
  }
}

 attribute是属性的名字，option表示这个属性的分支条件，比如

attribute = outlook, option = rainy  这个分支对应的属性应该是 windy

每个树节点(TreeNode)下都应该跟至少一个叶子节点TreeLeaf 表示这条分支的结束

 

写了好几个小时终于写出来了。。。  就是现在还不能图形化的显示。。。

 

 

[2014-02-15] 增加了一个预测方法：

/**
 * 使用决策树进行预测
 * @param dataSource <br>
 * HashMap: <br>
 * &nbsp;&nbsp; key: attribute name
 * &nbsp;&nbsp; value: attribute value
 * @param decistionTree 
 * @return <br>
 * 预测结果
 */
public String predict(Map<String, String> dataSource,  TreeNode decistionTree) {
	String result = null;
	if(dataSource.containsKey(decistionTree.attribute)) {
		String currentAttributeValue = dataSource.get(decistionTree.attribute);
		if(decistionTree.options.containsKey(currentAttributeValue)) {
			return predict(dataSource, decistionTree.options.get(currentAttributeValue)); 
		} else if(decistionTree.subLeafs.containsKey(currentAttributeValue)){
			result = decistionTree.subLeafs.get(currentAttributeValue).attributeValue;
		}
	}
	
	return result;
}

 

 

PS: 写得不够规范吧，当前目标是能写得出来 写得不好的地方还请各位看官指正