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

Koala++'s blog

计算广告学 RTB

 
 
 

日志

 
 

Weka开发[9]—KMeans源码介绍  

2009-02-09 10:38:07|  分类: 机器学习 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

以前介绍的都是分类的内容,这一次介绍聚类,以最简单的SimpleKMeans源码为例。

       分类中训练一个分类器是用buildClassifier(),在聚类中学习一个Clusterer是用buildCluster()。分类中分类一个样本是用classifyInstance,而在聚类中是用clusterInstance。那我怎么知道这些的呢?(或者说:你怎么知道我是不是在骗你呢?)以ID3为例,你可以看出它继承自Classifier类,进入Classifier类,它有三个比较重要的函数,buildClassifer, classifyInstance, distributionForInstance(这个应该讲过了)。那么如果你在看SimpleKMeans那么可以看它继承自RandomizableCluster,而RandomizableCluster又继承自AbstactCluter,进入AbstactCluster,它也有三个比较重要的函数,buildCluster, clusterInstance, distributionForInstance。关联规则的自己找。但所有的这些最初我是如何知道的呢?同学告诉我的,我也问过他最初如何知道的呢?他神秘地告诉我:源代码。

for (int j = initInstances.numInstances() - 1; j >= 0; j--) {

    instIndex = RandomO.nextInt(j + 1);

    hk = new DecisionTableHashKey(initInstances.instance(instIndex),

           initInstances.numAttributes(), true);

    if (!initC.containsKey(hk)) {

       m_ClusterCentroids.add(initInstances.instance(instIndex));

       initC.put(hk, null);

    }

    initInstances.swap(j, instIndex);

 

    if (m_ClusterCentroids.numInstances() == m_NumClusters) {

       break;

    }

}

以上是随机产生centroid的代码,也没什么特别之处,用RandomO产生一个index,如果这个index所指向的样本不是一个中心点了(用Hash表记录),把这个样本加入m_ClusterCentroids中,m_ClusterCentroids中保存的是所有中心点。最后一个if判断如果产生了用户最初设置的cluster的个数,break

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

       Instance toCluster = instances.instance(i);

       int newC = clusterProcessedInstance(toCluster, true);

       if (newC != clusterAssignments[i]) {

           converged = false;

       }

       clusterAssignments[i] = newC;

    }

    对每一个样本,用clusterProcessedInstance函数判断它属于哪个cluster,它属于哪个cluster当然就是根据它离哪个centroid近来决定了,再判断新的cluster和以前的cluster是否一样,如果不一样,那么就还没有convergeclusterAssignments[i]是第i个样本属于某个cluster

// update centroids

m_ClusterCentroids = new Instances(instances, m_NumClusters);

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

    tempI[i] = new Instances(instances, 0);

}

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

    tempI[clusterAssignments[i]].add(instances.instance(i));

}

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

    if (tempI[i].numInstances() == 0) {

    // empty cluster

    emptyClusterCount++;

    } else {

       moveCentroid(i, tempI[i], true);

    }

}

以上代码是更新centroidTempI[i]中保存的是所以当前属于第icluster的所有样本。最后一个for循环,如果tempI[i]中没有样本,那么记录有一个空cluster,如果tempI[i]中有样本,moveCentroid函数移动中心点。moveCentroid这个函数稍稍介绍一下,先看代码前的三句注释,我这里就不翻译了:

// in case of Euclidian distance the centroid is the mean point

// in case of Manhattan distance the centroid is the median point

// in both cases, if the attribute is nominal, the centroid is the mode

if (m_DistanceFunction instanceof EuclideanDistance

                  || members.attribute(j).isNominal()) {

    vals[j] = members.meanOrMode(j);

} else if (m_DistanceFunction instanceof ManhattanDistance) {

    // singleton special case

    if (members.numInstances() == 1) {

       vals[j] = members.instance(0).value(j);

    } else {

       sortedMembers.kthSmallestValue(j, middle + 1);

       vals[j] = sortedMembers.instance(middle).value(j);

       if (dataIsEven) {

           sortedMembers.kthSmallestValue(j, middle + 2);

    vals[j] = (vals[j] + sortedMembers.instance(middle +

1).value(j)) / 2;

       }

    }

}

    这里有一点我不太明白的是:为什么代码不用ifelse把奇数,偶数分开,而是在偶数样本时计算两次,这种代码实在让我有点无法接受。有点需要解释的是为什么偶数的是时候用的是middle+2,这是因为这个coder在求middle的时候用的是(members.numInstances() - 1) / 2;这样如果是偶数实际求出来的middle就小1,另一点是因为数数是从0数起(讲这个有点污辱人了),所以是+2。这也是我吐血的一点,不就多写两行代码吗?何必把代码写的这么古怪。

对于每个属性,对于不同的距离公式,对于离散/连续属性,选择不同确定中心的方式。

    判断聚类是否结束,第一种是如果每一个样本(也就是第二段代码)都在上一次产生的cluster中,也就是converged,另一种是用户设计的一个m_MaxIterations,如果达到最大迭代次数,也结束。

再看一下clusterInstance函数,请注意,它最后调用的clusterProcessedInstance, 刚才提了一下这个函数,这里把核心代码列出来:

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

    double dist = m_DistanceFunction.distance(instance,

       m_ClusterCentroids.instance(i));

    if (dist < minDist) {

       minDist = dist;

       bestCluster = i;

    }

}

讲这种代码,实在没什么意思,就是比较m_NumClusters个中心点,看instance与哪一个中心点近,作为bestCluster返回。

  评论这张
 
阅读(2916)| 评论(7)
推荐 转载

历史上的今天

评论

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

页脚

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