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

Koala++'s blog

计算广告学 RTB

 
 
 

日志

 
 

Weka开发[20]——IB1源代码分析  

2009-05-11 11:24:25|  分类: 机器学习 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

       首先先解释一下算法名字,很多人很奇怪为什么叫IB1,IBKIB Instance-Based的缩写,但按Jiawei Han书上所写,KNN其实是Instance-based learning(也被称为Lazing learning)中一种,他还讲解了基于案例的推理(Case-based reasoning)。算法其实是KNN,但是作者论文的名字是Instance-based Learning Algorithms

       我先介绍一下IB1IB1就是只找一个邻居。我们还是先看buildClassifier

public void buildClassifier(Instances instances) throws Exception {

 

    if (instances.classAttribute().isNumeric()) {

       throw new Exception("IB1: Class is numeric!");

    }

    if (instances.checkForStringAttributes()) {

       throw new UnsupportedAttributeTypeException(

              "IB1: Cannot handle string attributes!");

    }

    // Throw away training instances with missing class

    m_Train = new Instances(instances, 0, instances.numInstances());

    m_Train.deleteWithMissingClass();

 

    m_MinArray = new double[m_Train.numAttributes()];

    m_MaxArray = new double[m_Train.numAttributes()];

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

       m_MinArray[i] = m_MaxArray[i] = Double.NaN;

    }

      

    Enumeration enu = m_Train.enumerateInstances();

    while (enu.hasMoreElements()) {

       updateMinMax((Instance) enu.nextElement());

    }

}

       是的,KNN也有buildClassifier,听起来蛮奇怪的。第二个ifIB1不能对字符串属性进行学习,因为这种属性不好定义距离,比如aab0.5还是1呢?然类别缺失的样本抛弃。m_MinArraym_MaxArray分别保存每一个属性的最小值和最大值。最下面是对样本进行循环,找出最大值,最小值,updataMinMax代码如下:

private void updateMinMax(Instance instance) {

 

    for (int j = 0; j < m_Train.numAttributes(); j++) {

       if ((m_Train.attribute(j).isNumeric()) &&

           (!instance.isMissing(j))) {

           if (Double.isNaN(m_MinArray[j])) {

              m_MinArray[j] = instance.value(j);

              m_MaxArray[j] = instance.value(j);

           } else {

               if (instance.value(j) < m_MinArray[j]) {

                  m_MinArray[j] = instance.value(j);

               } else {

                  if (instance.value(j) > m_MaxArray[j]) {

                      m_MaxArray[j] = instance.value(j);

                  }

               }

           }

       }

    }

}

       Double.isNaN(m_MinArray[j])判断是不是m_MinArraym_MaxArray已经赋值过了,else,如果可以更新minmax更新。

       再看一下classifyInstance函数:

public double classifyInstance(Instance instance) throws Exception {

 

    if (m_Train.numInstances() == 0) {

       throw new Exception("No training instances!");

    }

 

    double distance, minDistance = Double.MAX_VALUE, classValue = 0;

    updateMinMax(instance);

    Enumeration enu = m_Train.enumerateInstances();

    while (enu.hasMoreElements()) {

       Instance trainInstance = (Instance) enu.nextElement();

       if (!trainInstance.classIsMissing()) {

           distance = distance(instance, trainInstance);

           if (distance < minDistance) {

              minDistance = distance;

              classValue = trainInstance.classValue();

           }

       }

    }

 

    return classValue;

}

       因为要进化归范化,所以对这个分类的样本再次调用updateMinMax。然后对训练样本进行循环,用distance计算与每一个样本的距离,如果比前面的距离小,则记录,最后返回与测试样本距离最小的样本的类别值。

private double distance(Instance first, Instance second) {

    double diff, distance = 0;

 

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

       if (i == m_Train.classIndex()) {

           continue;

       }

       if (m_Train.attribute(i).isNominal()) {

              // If attribute is nominal

           if (first.isMissing(i) || second.isMissing(i)

                  || ((int) first.value(i) != (int) second.value(i))) {

              distance += 1;

           }

       } else {

           // If attribute is numeric

           if (first.isMissing(i) || second.isMissing(i)) {

              if (first.isMissing(i) && second.isMissing(i)) {

                  diff = 1;

              } else {

                  if (second.isMissing(i)) {

                     diff = norm(first.value(i), i);

                  } else {

                     diff = norm(second.value(i), i);

                  }

                  if (diff < 0.5) {

                     diff = 1.0 - diff;

                  }

              }

           } else {

              diff = norm(first.value(i), i) - norm(second.value(i), i);

           }

           distance += diff * diff;

       }

    }

 

    return distance;

}

       Jiawei Han书里面说的一样,对离散属性来说,两个样本任一在对应属性上为缺失值,距离为1,不相等相然还是为1。对于连续属性,如果两个都是缺失值,距离为1,其中之一在对应属性上为缺失值,把另一个不为缺失值的属性值规范化,距离为1-diff,意思就是设到可能的最远(当然那个缺失值比m_MinArraym_MaxArray还小还大,这就不对了)。如果两个都有值,就把距离相加,最后平方。

       为了完整性,将norm列出来:

private double norm(double x, int i) {

 

    if (Double.isNaN(m_MinArray[i])

           || Utils.eq(m_MaxArray[i], m_MinArray[i])) {

       return 0;

    } else {

       return (x - m_MinArray[i]) / (m_MaxArray[i] - m_MinArray[i]);

    }

}

  评论这张
 
阅读(1975)| 评论(1)
推荐 转载

历史上的今天

评论

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

页脚

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