这次介绍一下Id3源码,这次用Weka的源码介绍一下。首先Id3是继承于Classifier的:
public class Id3 extends Classifier
Id3[]成员变量是递归保存树的变量,数据中每一个元素都是当前结点的子结点。
/** The node's successors. */
private Id3[] m_Successors;
Attribute是属性类,m_Attribute是分裂属性
/** Attribute used for splitting. */
private Attribute m_Attribute;
如果当前结果是叶子结点,m_ClassValue是类别
/** Class value if node is leaf. */
private double m_ClassValue;
Distribution表示的是这个结点属于某个类别的概率,如m_Distribution[0] == 0.1表示当前结点属于类别0的概率为0.1
/** Class distribution if node is leaf. */
private double[] m_Distribution;
数据集的类别,以前也讲过了
/** Class attribute of dataset. */
private Attribute m_ClassAttribute;
以前也讲过,继承自Classifier类的类都要实现buildClassifier函数。
public void buildClassifier(Instances data) throws Exception {
// can classifier handle the data?
getCapabilities().testWithFail(data);
// remove instances with missing class
data = new Instances(data);
data.deleteWithMissingClass();
makeTree(data);
}
getCapabilities().testWithFail(data)是判断是否ID3能处理选择的数据集,比如什么连续属性,类别索引没有设置等等。
而data.deleteWithMissingClass则是删除有缺失样本的函数,具体代码如下:
for (int i = 0; i < numInstances(); i++) {
if (!instance(i).isMissing(attIndex)) {
newInstances.addElement(instance(i));
}
}
m_Instances = newInstances;
简单一点,不用为上面的东西分心,关注makeTree(data)就行了:
// Compute attribute with maximum information gain.
double[] infoGains = new double[data.numAttributes()];
Enumeration attEnum = data.enumerateAttributes();
while (attEnum.hasMoreElements()) {
Attribute att = (Attribute) attEnum.nextElement();
infoGains[att.index()] = computeInfoGain(data, att);
}
m_Attribute = data.attribute(Utils.maxIndex(infoGains));
infoGains保存每个属性的信息增益(IG),枚举每个属性,用computeInfoGain函数计算信息增益值。Util.maxIndex返回信息增益最大的下标,这个属性作为分裂属性保存在m_Attribute成员变量中。
// Make leaf if information gain is zero.
if (Utils.eq(infoGains[m_Attribute.index()], 0)) {
m_Attribute = null;
m_Distribution = new double[data.numClasses()];
Enumeration instEnum = data.enumerateInstances();
while (instEnum.hasMoreElements()) {
Instance inst = (Instance) instEnum.nextElement();
m_Distribution[(int) inst.classValue()]++;
}
Utils.normalize(m_Distribution);
m_ClassValue = Utils.maxIndex(m_Distribution);
m_ClassAttribute = data.classAttribute();
}
当信息增益等于0时为叶子结点(这为什么再讲,就没完了)。
m_Attribute = null,已经不用再分裂了,所以为null。刚才也说过m_Distribution保存的是当前结点属于类别的概率,所以数组大小于data.numClasses()。枚举当前结点中的每一个样本,inst.classValue()就是inst样本的类别值,请注意不要以为类别都是”good”,”bad”之类的值,而是第一个类别就是0,第二个类别就是1的double型。
m_Distribution[(int) inst.classValue()]++;也就是将每个样本的相应的下标加1,比如当前叶子结点有10个样本,9个属于第一个类别,1个属于第五个类别,则m_Distribution[0]=9,m_Distribution[4]=1。
Utils.normalize(m_Distribution);简单地理解为归一化吧,刚在例子也就是m_Distribution[0]=0.9,m_Distribution[4]=0.1。
m_ClassValue = Utils.maxIndex(m_Distribution);属于哪个类别的概率最高,那当然就是哪个类别
m_ClassAtrribute也就是类别属性。
// Otherwise create successors.
else {
Instances[] splitData = splitData(data, m_Attribute);
m_Successors = new Id3[m_Attribute.numValues()];
for (int j = 0; j < m_Attribute.numValues(); j++) {
m_Successors[j] = new Id3();
m_Successors[j].makeTree(splitData[j]);
}
}
如果信息增益不是0那么分裂当前结点,在splitData(data, m_Attribute)函数中,data被分裂成m_Attribute离散值个子结点,比如m_Attribute有三种取值”green”,”red”,”blue”,则splitData将data分成3部分到splitData中。
在例子中当前结点有3个子结点,则m_Attribute.numValues()==3,递归地makeTree。(再讲清楚点,也就是每一个子树都是一个决策树,所以new Id3())
这里有一个问题,如果在例中,当前结点的green子结点没有样本,那么:
// Check if no instances have reached this node.
if (data.numInstances() == 0) {
m_Attribute = null;
m_ClassValue = Instance.missingValue();
m_Distribution = new double[data.numClasses()];
return;
}
这就没什么好解释的了。
对于分类一个样本:
if (m_Attribute == null) {
return m_ClassValue;
} else {
return m_Successors[(int) instance.value(m_Attribute)]
.classifyInstance(instance);
}
当然也是递归了,如果已经到达叶子结点了,那直接返回类别值。不是叶子结点,那么根据样本属性值到相应的子结点,再调用classifyInstance(instance)。
还有distributionForInstance也差不多,不作解释了:
if (m_Attribute == null) {
return m_Distribution;
} else {
return m_Successors[(int) instance.value(m_Attribute)]
.distributionForInstance(instance);
}
computeInfoGain和computeEntropy两个函数也不解释了,不过还是应该看一下,有时候还能用的着(最重要的其实是,这都不懂,也过份了点吧)。
分裂结点的函数:
private Instances[] splitData(Instances data, Attribute att) {
Instances[] splitData = new Instances[att.numValues()];
for (int j = 0; j < att.numValues(); j++) {
splitData[j] = new Instances(data, data.numInstances());
}
Enumeration instEnum = data.enumerateInstances();
while (instEnum.hasMoreElements()) {
Instance inst = (Instance) instEnum.nextElement();
splitData[(int) inst.value(att)].add(inst);
}
for (int i = 0; i < splitData.length; i++) {
splitData[i].compactify();
}
return splitData;
}
将data分裂成att.numValues()个子结点,inst.value(att)就是根据inst样本att属性值将inst样本分成相应的子结点中。(确切点,也不是子结点,一个Instances数组元素)
相关推荐
Weka开发[8]-ID3源码介绍 18 Weka开发[9]—KMeans源码介绍 21 Weka开发[10]—NBTree源码介绍 25 Weka开发[11]—J48源代码介绍 31 Weka开发[13]-Ensemble 39 Weka开发[14]-AdaBoost源代码介绍 42 ...
- **学习数据挖掘算法**:Weka源码提供了大量常用的数据挖掘算法的实现,如ID3、C4.5、Naive Bayes、K-means等,这些算法的实现可以帮助开发者理解算法的细节。 - **自定义预处理和后处理**:如果标准的预处理或后...
**Weka 3.6.10 源码详解:数据挖掘的Java工具** Weka,全称为Waikato Environment for Knowledge Analysis,是一个开源的数据挖掘软件,由新西兰怀卡托大学的信息科学学院开发。Weka 3.6.10 版本是其历史上的一个...
**Weka概述** Weka(Waikato Environment for Knowledge Analysis)是一个开源的...通过深入研究Weka源码,不仅可以学习到各种机器学习算法的实现,还能提升Java编程和数据处理能力,为后续的AI项目开发打下坚实基础。
这个压缩包“weka-3-6-13源代码;为了支持中文,做了少量修改”包含了Weka 3.6.13版本的源代码,并且特别指出是为了支持中文环境进行了某些定制化的修改。这意味着它可能包含了对原始Weka源码的调整,以更好地处理...
ID3是决策树算法的一种,它基于信息熵和信息增益来选择最佳划分属性。KMeans是聚类算法,通过迭代更新质心来将数据分到最接近的簇。 NBTree是基于朴素贝叶斯的分类器,它使用树结构来存储概率信息,提高分类速度。J...
3. **分类与回归**:Weka支持多种分类和回归算法,如朴素贝叶斯、决策树(如C4.5和ID3)、随机森林、支持向量机等。源代码揭示了这些算法的实现逻辑,有助于理解它们的工作原理。 4. **聚类**:Weka提供了K-means、...
在分类任务中,Weka内置了多种算法,如决策树(如C4.5和ID3)、贝叶斯分类器(如Naive Bayes)、支持向量机(SVM)、神经网络等,这些算法各有优势,适用于不同的数据集和问题场景。聚类算法则包括K-means、层次聚类...
- **分类**:Weka支持众多经典的分类算法,如决策树(C4.5, ID3)、贝叶斯网络、神经网络、支持向量机、K近邻等,用户可以根据实际需求选择合适的算法进行训练。 - **回归**:对于连续值预测问题,Weka提供了线性...
- ID3:由Ross Quinlan开发,基于信息熵和信息增益进行特征选择。 - C4.5:是ID3的升级版,处理了连续数值型特征和信息增益不纯度的问题。 - CART(Classification and Regression Trees):用于分类和回归,采用...
C4.5则是ID3决策树算法的优化版本,能够处理连续属性并处理过拟合问题;而朴素贝叶斯则假设各特征之间相互独立,通过计算每个类别的先验概率和特征条件概率来进行分类。 在源码中,我们还看到其他辅助函数,如...
ID3、C4.5和CART是决策树的代表算法。这些算法通过对数据集进行递归分割,构建出一个能够最小化预测误差的树状结构。Java中的Weka库提供了多种决策树算法的实现。 3. **粗糙集(Rough Set)**:粗糙集理论是处理不...