注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Koala++'s blog

计算广告学 RTB

 
 
 

日志

 
 

Weka开发[36]——InfoGainAttributeEval源代码分析  

2010-01-17 16:33:30|  分类: 机器学习 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

    最近要用到特征选择,但需要的特征选择又有点不同,还是看看源码,本文后面介绍了weka中熵的计算,它的计算与公式中不太一样,以前给weka中文站人的介绍过一次,这次我专门周末把公式敲出来,方便大家看。

         buildEvaluator开始看:

int classIndex = data.classIndex();

int numInstances = data.numInstances();

 

if (!m_Binarize) {

    Discretize disTransform = new Discretize();

    disTransform.setUseBetterEncoding(true);

    disTransform.setInputFormat(data);

    data = Filter.useFilter(data, disTransform);

} else {

    NumericToBinary binTransform = new NumericToBinary();

    binTransform.setInputFormat(data);

    data = Filter.useFilter(data, binTransform);

}

         看是要离散成二个值,还是多个值。

int numClasses = data.attribute(classIndex).numValues();

 

// Reserve space and initialize counters

double[][][] counts = new double[data.numAttributes()][][];

for (int k = 0; k < data.numAttributes(); k++) {

    if (k != classIndex) {

       int numValues = data.attribute(k).numValues();

       counts[k] = new double[numValues + 1][numClasses + 1];

    }

}

 

// Initialize counters

double[] temp = new double[numClasses + 1];

for (int k = 0; k < numInstances; k++) {

    Instance inst = data.instance(k);

    if (inst.classIsMissing()) {

       temp[numClasses] += inst.weight();

    } else {

       temp[(int) inst.classValue()] += inst.weight();

    }

}

for (int k = 0; k < counts.length; k++) {

    if (k != classIndex) {

        for (int i = 0; i < temp.length; i++) {

           counts[k][0][i] = temp[i];

       }

    }

}

         Counts第一维是属性个数,第二列是属性值个数+1,第三列是类别个数+1。将第属性值的第0个元素,设为样本权重,且属性值第0个元素的类别第0个元素为,所有类别缺失样本权重之和。

// Get counts

for (int k = 0; k < numInstances; k++) {

    Instance inst = data.instance(k);

    for (int i = 0; i < inst.numValues(); i++) {

       if (inst.index(i) != classIndex) {

           if (inst.isMissingSparse(i) || inst.classIsMissing()) {

              if (!inst.isMissingSparse(i)) {

                  counts[inst.index(i)][(int) inst.valueSparse(i)]

[numClasses] += inst.weight();

                  counts[inst.index(i)][0][numClasses] -= inst

                         .weight();

              } else if (!inst.classIsMissing()) {

                  counts[inst.index(i)][data.attribute(inst.index(i))

                         .numValues()][(int) inst.classValue()] += inst

                         .weight();

                  counts[inst.index(i)][0][(int) inst.classValue()]

-= inst.weight();

              } else {

                  counts[inst.index(i)][data.attribute(inst.index(i))

                         .numValues()][numClasses] += inst.weight();

                  counts[inst.index(i)][0][numClasses] -= inst

                         .weight();

              }

           } else {

              counts[inst.index(i)][(int) inst.valueSparse(i)]

[(int) inst.classValue()] += inst.weight();

              counts[inst.index(i)][0][(int) inst.classValue()]

-= inst.weight();

           }

       }

    }

}

         核心的就是最下面的else的第一句,将这个属性的这个属性值的类别值的元素加上它的权重。if(m_missing_merge)就是把那些缺失值平均分到相应的元素中去,懒的细看了,下一个:

// Compute info gains

m_InfoGains = new double[data.numAttributes()];

for (int i = 0; i < data.numAttributes(); i++) {

    if (i != classIndex) {

       m_InfoGains[i] = (ContingencyTables

              .entropyOverColumns(counts[i]) - ContingencyTables

              .entropyConditionedOnRows(counts[i]));

    }

}

         重要的有两个函数entropyOverColumnsentropyConditionedOnRows

public static double entropyOverColumns(double[][] matrix) {

 

    double returnValue = 0, sumForColumn, total = 0;

 

    for (int j = 0; j < matrix[0].length; j++) {

       sumForColumn = 0;

       for (int i = 0; i < matrix.length; i++) {

           sumForColumn += matrix[i][j];

       }

       returnValue = returnValue - lnFunc(sumForColumn);

       total += sumForColumn;

    }

    if (Utils.eq(total, 0)) {

       return 0;

    }

    return (returnValue + lnFunc(total)) / (total * log2);

}

         这里要注意一下,其实从名字也反应出来了Over Columns是求这个属性的熵,也就是InfoGain前面的那一项。

public static double entropyConditionedOnRows(double[][] matrix) {

 

    double returnValue = 0, sumForRow, total = 0;

 

    for (int i = 0; i < matrix.length; i++) {

       sumForRow = 0;

       for (int j = 0; j < matrix[0].length; j++) {

           returnValue = returnValue + lnFunc(matrix[i][j]);

           sumForRow += matrix[i][j];

       }

       returnValue = returnValue - lnFunc(sumForRow);

       total += sumForRow;

    }

    if (Utils.eq(total, 0)) {

       return 0;

    }

    return -returnValue / (total * log2);

}

         这一步也就是InfoGain公式的后面一项。

         这里先以ID3为例讲一下如何计算信息熵,weka中所用的计算有点点不同:

private double computeEntropy(Instances data) throws Exception {

 

    double[] classCounts = new double[data.numClasses()];

    Enumeration instEnum = data.enumerateInstances();

    while (instEnum.hasMoreElements()) {

       Instance inst = (Instance) instEnum.nextElement();

       classCounts[(int) inst.classValue()]++;

    }

    double entropy = 0;

    for (int j = 0; j < data.numClasses(); j++) {

       if (classCounts[j] > 0) {

           entropy -= classCounts[j] * Utils.log2(classCounts[j]);

       }

    }

    entropy /= (double) data.numInstances();

    return entropy + Utils.log2(data.numInstances());

}

         classCounts数组不必说,自然是每个类别的样本数。这里设数样本数为N,类别数为M,类别i的样本数为Ci (Ci=classCounts[i])。中间的for循环用公式表示出来就是:

Weka开发[34]——InfoGainAttributeEval源代码分析 - quweiprotoss - Koala++s blogWeka开发[34]——InfoGainAttributeEval源代码分析 - quweiprotoss - Koala++s blogWeka开发[34]——InfoGainAttributeEval源代码分析 - quweiprotoss - Koala++s blog

 

 

  评论这张
 
阅读(1988)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017