具有多个参数的 K-means 算法

Question

我在地图上有一组点。我正在尝试创建集群。除了距离，我还在考虑每个集群的最大成本（作为另一个参数）。

请找到下面的代码片段。

private void assignCluster(List<Cluster> finalClusters, List<Node> clusterNodes, int maxCostLimit) {
    double max = Double.MAX_VALUE;
    double min = max;
    int clusterIndex = 0;
    double distance = 0.0;

    for (Node node : clusterNodes) {
        min = max;
        for (int i = 0; i < finalClusters.size(); i++) {
            Cluster cluster = finalClusters.get(i);
            distance = Point.getDistanceBetweenPoints(node.getPoint(), cluster.getPoint());
            if (distance < min && (cluster.getTotalCost() + node.getCost()) <= maxCostLimit) {
                min = distance;
                clusterIndex = i;
            }
        }
        if (min != max) {
            Cluster cluster = finalClusters.get(clusterIndex);
            cluster.setTotalCost(cluster.getTotalCost() + node.getCost());
            cluster.addClusterNode(node);
        }
    }
}

如果我尝试创建集群，它将进入无限循环。或者，地图上的两个点被分配给两个不同的集群。在每次迭代中，这两个簇的质心都在变化。请建议我，我怎样才能做到这一点？

编辑

Cluster.java

public class Cluster{
    private List<Node> clusterNodes = new ArrayList<Node>();
    private Integer totalCost = 0;
    private Point2D point;

         //getters and setters
}

Point.java

public class Point{
    private double x = 0;
    private double y = 0;

        // getters and setters

       //method to find the distance between 2 points
}

我指的是这个 link 的基本 Kmeans 算法：http://www.dataonfocus.com/k-means-clustering-java-code/

Answer 1

通常，K-means 算法可以证明从不重复上一次迭代中的节点到集群的分配。

也许这在你的情况下是可能的，因为你引入的额外成本限制在使用 K-means 时传统上不存在，但也许它仍然存在't，我不确定。

我想知道您如何使用您提供代码的 assignCluster() 方法。您是否有另一个循环，它不断调用 assignCluster() 和 finalClusters = 最新的集群分配列表，以及 clusterNodes = 所有节点的列表，并不断循环直到结束一项等于前一项的分配？

如果是这样，您确定 cluster.addClusterNode() 正确地从其先前的集群中删除了该节点（如果您按上述方式实施它，我认为应该如此？）。另一件要看的事情可能是 (cluster.getTotalDemand() + node.getCost()) 计算。我怀疑，如果您碰巧正在查看该节点已经存在的集群，您可能不想在该计算中包含 node.getCost()，因为如果它也是 ，它将被计算为两倍 包含在 cluster.getTotalDemand().

中

我不得不对您究竟希望代码做什么，或者您如何实现代码未显示的其他方法做出一些假设...所以如果有任何错误，您必须指出在我的假设中。

Answer 2

查看您随问题提供的代码并通过 link，我看不出有任何无限循环的原因（假设您正确调整了代码）除了可能，总计集群数量乘以每个集群的最大成本小于所有节点的总成本。您可以通过在进入循环之前遍历所有节点来检查这一点。

另一个问题可能是，您忘记在 clearClusters() 方法中重置每个群集的 totalCost，但我认为这不会导致无限循环。

为什么你的质心是class类型的Point2D而不是你自己的Pointclass？

具有多个参数的 K-means 算法

K-means Algorithm with multiple parameters

java

algorithm

k-means