public static class KMeansAlgorithm {

        private static int findNearestCluster(Point point, ArrayList<PointCollection> allClusters, int dimension) {

            double minimumDistance = 0.0;
            int nearestClusterIndex = -1;

            for (int clusterIndex = 0; clusterIndex < allClusters.size(); clusterIndex++) {

                double distance = Point.findDistance(point, (allClusters.get(clusterIndex)).getCenter(), dimension);

                if (clusterIndex == 0) {
                    minimumDistance = distance;
                    nearestClusterIndex = 0;
                } else {
                    if (minimumDistance > distance) {
                        minimumDistance = distance;
                        nearestClusterIndex = clusterIndex;
                    }
                }
            }

            return nearestClusterIndex;
        }

        public static ArrayList<Cluster> doClustering(PointCollection points, int clusterCount, int dimension)
                throws Exception {

            if (clusterCount > points.size()) {
                throw new Exception("clusterCount > points.size()");
            }

            ArrayList<PointCollection> allClusters = new ArrayList<PointCollection>();
            ArrayList<ArrayList<Point>> allGroups = ListUtility.splitList(points, clusterCount);

            for (ArrayList<Point> group : allGroups) {

                PointCollection cluster = new PointCollection(dimension);
                cluster.addRange(group);
                allClusters.add(cluster);
            }

            int movements = 1;

            while (movements > 0) {

                movements = 0;

                for (PointCollection cluster : allClusters) {

                    for (int pointIndex = 0; pointIndex < cluster.size(); pointIndex++) {

                        Point point = cluster.get(pointIndex);
                        int nearestCluster = findNearestCluster(point, allClusters, dimension);

                        if (nearestCluster != allClusters.indexOf(cluster) && cluster.size() > 1) {

                            Point removedPoint = cluster.removePoint(point);
                            (allClusters.get(nearestCluster)).addPoint(removedPoint);
                            movements += 1;
                        }
                    }
                }
            }

            ArrayList<Cluster> clusters = new ArrayList<Cluster>();

            for (PointCollection clusterPoints : allClusters) {
                clusters.add(new Cluster(clusterPoints));
            }

            return clusters;
        }
    }