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

Koala++'s blog

计算广告学 RTB

 
 
 

日志

 
 

Weka开发[41]——FarthestFirst源代码分析  

2010-05-14 16:25:00|  分类: 机器学习 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

       FarthestFirst算法可以参考performance guarantees for hierarchical clustering

       buildClusterer开始,先看一下initMinMax函数:

protected void initMinMax(Instances data) {

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

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

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

       m_Min[i] = m_Max[i] = Double.NaN;

    }

 

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

       updateMinMax(data.instance(i));

    }

}

       可以看出,这里的MinMax是指每个属性值的最小值,最大值。

private void updateMinMax(Instance instance) {

 

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

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

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

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

       } else {

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

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

           } else {

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

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

              }

           }

       }

    }

}

       这里是指出每个属性(j)的最小值(m_Min[j]),最大值(m_Max[j])

       回到buildClusterer函数中,在initMinMax的代码是:

m_ClusterCentroids = new Instances(m_instances, m_NumClusters);

 

int n = m_instances.numInstances();

Random r = new Random(m_Seed);

boolean[] selected = new boolean[n];

double[] minDistance = new double[n];

 

for (int i = 0; i < n; i++)

    minDistance[i] = Double.MAX_VALUE;

 

int firstI = r.nextInt(n);

m_ClusterCentroids.add(m_instances.instance(firstI));

selected[firstI] = true;

       m_ClusterCentroids是各个类别的中心点集合,它有m_NumClusters个类别,即用户指定的类别数,firstI是一个随机的样本下标,而这个样本就是第一个类别的中心点,selected数组用于标明一个样本是否被选中。

       再下面的updateMinDistance代码如下:

updateMinDistance(minDistance, selected, m_instances,

       m_instances.instance(firstI));

 

protected void updateMinDistance(double[] minDistance, boolean[] selected, Instances data, Instance center) {

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

       if (!selected[i]) {

           double d = distance(center, data.instance(i));

           if (d < minDistance[i])

              minDistance[i] = d;

       }

}

       这里是更新样本中与第firstI个样本的最小距离,即如果这次距离小于先前的,就更新。

if (m_NumClusters > n)

    m_NumClusters = n;

 

for (int i = 1; i < m_NumClusters; i++) {

    int nextI = farthestAway(minDistance, selected);

    m_ClusterCentroids.add(m_instances.instance(nextI));

    selected[nextI] = true;

    updateMinDistance(minDistance, selected, m_instances, m_instances

           .instance(nextI));

}

 

m_instances = new Instances(m_instances, 0);

       如果m_NumClusters比样本数还多,那最多就只能聚样本数个类了。

       接下来是找下一个类的中心点,这里是找与其它类别中心点都远的一个样本。

protected int farthestAway(double[] minDistance, boolean[] selected) {

    double maxDistance = -1.0;

    int maxI = -1;

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

       if (!selected[i])

           if (maxDistance < minDistance[i]) {

              maxDistance = minDistance[i];

              maxI = i;

           }

    return maxI;

}

       farthestAwayminDistance中的最大值下标返回,它就是离所有中心点最远的样本,因为在updateMinDistance中,当产生一个新的中心点时,所有新的中心点较近的样本值都会变,并且这个值只会变小,不会变大。

public int clusterInstance(Instance instance) throws Exception {

    m_ReplaceMissingFilter.input(instance);

    m_ReplaceMissingFilter.batchFinished();

    Instance inst = m_ReplaceMissingFilter.output();

 

    return clusterProcessedInstance(inst);

}

protected int clusterProcessedInstance(Instance instance) {

    double minDist = Double.MAX_VALUE;

    int bestCluster = 0;

    for (int i = 0; i < m_NumClusters; i++) {

       double dist = distance(instance,

m_ClusterCentroids.instance(i));

       if (dist < minDist) {

           minDist = dist;

           bestCluster = i;

       }

    }

    return bestCluster;

}

       判断这个样本与最个中心点近,就认为它属于哪个簇。

       计算距离的代码如下:

protected double distance(Instance first, Instance second) {

 

    double distance = 0;

    int firstI, secondI;

 

    for (int p1 = 0, p2 = 0; p1 < first.numValues()

           || p2 < second.numValues();) {

       if (p1 >= first.numValues()) {

           firstI = m_instances.numAttributes();

       } else {

           firstI = first.index(p1);

       }

       if (p2 >= second.numValues()) {

           secondI = m_instances.numAttributes();

       } else {

           secondI = second.index(p2);

       }

       if (firstI == m_instances.classIndex()) {

           p1++;

           continue;

       }

       if (secondI == m_instances.classIndex()) {

           p2++;

           continue;

       }

       double diff;

       if (firstI == secondI) {

           diff = difference(firstI, first.valueSparse(p1), second

                  .valueSparse(p2));

           p1++;

           p2++;

       } else if (firstI > secondI) {

           diff = difference(secondI, 0, second.valueSparse(p2));

           p2++;

       } else {

           diff = difference(firstI, first.valueSparse(p1), 0);

           p1++;

       }

       distance += diff * diff;

    }

 

    return Math.sqrt(distance / m_instances.numAttributes());

}

       前两个if/else是得到当前属性的值,numValues代码注释里写的是与numAttributes返回的一样,这里这样写不知道出来什么原因?再下面两个if是不考虑类别值,因为这个按理说应该是不知道的。将下面是用difference函数来判断两个属性值的差。这里计算距离用的是欧几里德距离公式。

protected double difference(int index, double val1, double val2) {

    switch (m_instances.attribute(index).type()) {

    case Attribute.NOMINAL:

       // If attribute is nominal

       if (Instance.isMissingValue(val1)

|| Instance.isMissingValue(val2)

              || ((int) val1 != (int) val2)) {

           return 1;

       } else {

           return 0;

       }

    case Attribute.NUMERIC:

       // If attribute is numeric

       if (Instance.isMissingValue(val1)

|| Instance.isMissingValue(val2)) {

           if (Instance.isMissingValue(val1)

                  && Instance.isMissingValue(val2)) {

              return 1;

           } else {

              double diff;

              if (Instance.isMissingValue(val2)) {

                  diff = norm(val1, index);

              } else {

                  diff = norm(val2, index);

              }

              if (diff < 0.5) {

                  diff = 1.0 - diff;

              }

              return diff;

           }

       } else {

           return norm(val1, index) - norm(val2, index);

       }

    default:

       return 0;

    }

}

protected double norm(double x, int i) {

 

    if (Double.isNaN(m_Min[i]) || Utils.eq(m_Max[i], m_Min[i])) {

       return 0;

    } else {

       return (x - m_Min[i]) / (m_Max[i] - m_Min[i]);

    }

}

       如果是离散属性,属性值相等为1,否则为0。如果是连续属性,就麻烦点,都是缺失值为1,如果其中一个是缺失值,则判断归一化后的值,如果小于0.5,返回1-diff,否则返回diff。如果两个都不是缺失值,则返回两个归一化后的值的差值。

 

 

  评论这张
 
阅读(1889)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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