每日归档： 2014年2月14日

Canopy集群算法(org.apache.mahout.clustering.canopy.CanopyDriver)

原创文章，转载请注明： 转载自慢慢的回味

本文链接地址: Canopy集群算法(org.apache.mahout.clustering.canopy.CanopyDriver)

理论分析

集群中心点计算

1 选择T1和T2，T1>T2。其中T1为弱归属距离，T2为强归属距离。
2 对每个点进行到中心点的距离计算。其中，第一点计算时没有中心点，则以第一点为中心创建一个集群。
2.1 当距离小于T1时，标记当前点为弱归属点，对应的集群加入此点
2.2 当小于T2时，标记当前点为强归属点。
2.3 如果当前点不是强归属点，则以当前点为中心创建一个新的集群。
3 对所有的集群中心点，计算新的集群。

集群数据

对所有的点，计算其和每个中心的距离，距离最小者为当前点的集群。

例子

 

代码分析

  /* CanopyMapper.java*/
  @Override
  protected void map(WritableComparable<?> key, VectorWritable point,
      Context context) throws IOException, InterruptedException {
    canopyClusterer.addPointToCanopies(point.get(), canopies);
  }
 
  @Override
  protected void cleanup(Context context) throws IOException,
      InterruptedException {
    for (Canopy canopy : canopies) {
      canopy.computeParameters();
      if (canopy.getNumObservations() > clusterFilter) {
        context.write(new Text("centroid"), new VectorWritable(canopy
            .getCenter()));
      }
    }
    super.cleanup(context);
  }
 
  /* CanopyClusterer.java*/
  public void addPointToCanopies(Vector point, Collection<Canopy> canopies) {
    boolean pointStronglyBound = false;
    for (Canopy canopy : canopies) {
      double dist = measure.distance(canopy.getCenter().getLengthSquared(), canopy.getCenter(), point);
      if (dist < t1) {
        if (log.isDebugEnabled()) {
          log.debug("Added point: {} to canopy: {}", AbstractCluster.formatVector(point, null), canopy.getIdentifier());
        }
        canopy.observe(point);
      }
      pointStronglyBound = pointStronglyBound || dist < t2;
    }
    if (!pointStronglyBound) {
      if (log.isDebugEnabled()) {
        log.debug("Created new Canopy:{} at center:{}", nextCanopyId, AbstractCluster.formatVector(point, null));
      }
      canopies.add(new Canopy(point, nextCanopyId++, measure));
    }
  }
 
  /* CanopyReducer.java */
  @Override
  protected void reduce(Text arg0, Iterable<VectorWritable> values,
      Context context) throws IOException, InterruptedException {
    for (VectorWritable value : values) {
      Vector point = value.get();
      canopyClusterer.addPointToCanopies(point, canopies);
    }
    for (Canopy canopy : canopies) {
      canopy.computeParameters();
      if (canopy.getNumObservations() > clusterFilter) {
        ClusterWritable clusterWritable = new ClusterWritable();
        clusterWritable.setValue(canopy);
        context.write(new Text(canopy.getIdentifier()), clusterWritable);
      }
    }
  }

本作品采用知识共享署名 4.0 国际许可协议进行许可。

Fuzzykmeans集群算法(cluster-reuters)

原创文章，转载请注明： 转载自慢慢的回味

本文链接地址: Fuzzykmeans集群算法(cluster-reuters)

理论分析

集群中心点计算

1 随机从待分类的向量中选出20个作为20个集群的中心。
2 对所有的点，计算其和每个中心的距离，得到点归属于每个集群的概率。
3 重新对每个集群计算新的中心，并计算新的中心和老的中心的距离，判断其是否收敛。
4 如果所有集群都收敛或者达到用户指定的条件，则集群完成。否则，从2开始下一轮计算。

集群数据

对所有的点，计算其和每个中心的距离，得到点归属于每个集群的概率。

代码分析

请先阅读kmeans集群算法(cluster-reuters)
这里只说明FuzzyKMeansClusteringPolicy和KMeansClusteringPolicy的不同地方

  /* FuzzyKMeansClusteringPolicy.java中的方法*/
  /* 相对于KMeansClusteringPolicy，KMeansClusteringPolicy只返回最大概率者，而本方法是全部返回。*/
  @Override
  public Vector select(Vector probabilities) {
    return probabilities;
  }
 
  /* 此方法计算当前点属于所以集群中心的概率*/
  @Override
  public Vector classify(Vector data, ClusterClassifier prior) {
    Collection<SoftCluster> clusters = Lists.newArrayList();
    List<Double> distances = Lists.newArrayList();
    for (Cluster model : prior.getModels()) {
      SoftCluster sc = (SoftCluster) model;
      clusters.add(sc);
      distances.add(sc.getMeasure().distance(data, sc.getCenter()));
    }
    FuzzyKMeansClusterer fuzzyKMeansClusterer = new FuzzyKMeansClusterer();
    fuzzyKMeansClusterer.setM(m);
    return fuzzyKMeansClusterer.computePi(clusters, distances);
  }

本作品采用知识共享署名 4.0 国际许可协议进行许可。