javascript - k-means聚类算法收敛但不是使用javascript的稳定收敛

Question

我收敛了，但是，刷新算法时结果永远不会相同。即使数据观察是相同的数据集，也会发生这种情况。谁能告诉我我的方法哪里错了？对于我的一生，我无法弄清楚该过程哪里出了问题。

function kmeans2(k, data, canvas, converge) {
    this.canvas = jsHS.GetDimensions(canvas);
    this.k = k;
    this.centroids = []; // Array of centroids
    this.centroids2compare = [];
    this.data = data;
    this.converge = converge;
    this.init();
}
kmeans2.prototype.distance = function () {
    var dif = 0,
        iArray = jsHS.isArray(arguments);
    if (iArray) {
        if (arguments.length > 2) {
            for (var i = 0; i < arguments.length; i+2) {
                var p0 = arguments[i],
                    p1 = arguments[i + 1];
                dif += Math.pow(p0[0] - p1[0], 2);
                dif += Math.pow(p0[1] - p1[1], 2);
            }
        }
        else {
            var pd0 = arguments[0],
                pd1 = arguments[1];
            dif += Math.pow(pd0[0] - pd1[0], 2);
            dif += Math.pow(pd0[1] - pd1[1], 2);
        }
    }
    return Math.sqrt(dif);
};
kmeans2.prototype.Means = function (Array) {
    var bin = 0;
    [].forEach.call(Array, function(a){
        bin += a;
    });
    return bin / Array.length;
};
kmeans2.prototype.init = function () {
    for (var l = 0; l < this.k; l++) {
        var dataItem = this.data[Math.floor(Math.random() * this.data.length)];
        this.centroids.push(dataItem);
    }
    for (var i = 0; i < this.centroids.length; i++) {
        if (i > 0) {
            var distance = this.distance(this.centroids[i], this.centroids[i - 1]);
            console.log(distance);
        }
    }
    this.clusterCentroids(); // return centroid center after calculating means.
};
kmeans2.prototype.clusterCentroids = function () {
    var points0 = [];
    this.centroids2compare = this.centroids;

    // Find distances between centroid and observations.
    for (var d = 0; d < this.data.length; d++) {
        var cinbin = [];
        for (var c0 = 0; c0 < this.k; c0++) {
            var dis = this.distance(this.centroids[c0], this.data[d]);
            cinbin.push({ 'cid': c0, 'distance': dis });
        }
        var minResult = cinbin.reduce((cid, obj) => {
            return obj.distance < cid.distance ? obj : cid;
        });
        points0.push({ 'id': d, 'datapoint': this.data[d], 'centroid': minResult.cid });
    }

    // Assign observations their appropriate centroid.
    var centroidBin = [];
    for (var c = 0; c < this.k; c++) {
        var cb = [];
        for (var p = 0; p < points0.length; p++) {
            if (c === points0[p].centroid) {
                cb.push(points0[p]);
            }
        }
        centroidBin.push(cb);
    }
    
    // Calculate the mean distance between centroids and its assigned observations.
    this.centroids = [];
    for (var bin = 0; bin < centroidBin.length; bin++) {
        var xAxis = [],
            yAxis = [],
            cb0 = centroidBin[bin];
        [].forEach.call(cb0, function (dp) {
            xAxis.push(dp.datapoint[0]);
            yAxis.push(dp.datapoint[1]);
        });

        var xMean = this.Means(xAxis);
        var yMean = this.Means(yAxis);
        this.centroids.push([xMean, yMean]);
    }

    // Test for convergence. If stored centroids equal new centroids then convergence is achieved.
    if (JSON.stringify(this.centroids2compare) !== JSON.stringify(this.centroids)) {
        this.centroids2compare = [];
        points0 = [];
        this.clusterCentroids();
    }
    else {
        this.converge(centroidBin, this.centroids);
    }
};
window['jsHS']['kmeans2'] = kmeans2;

实现

var k50 = new jsi.kmeans2(5, Array50, canvas, function (con, centroids) {
        var count50 = 0;

        var cmark = {
            x: 0,
            y: 0,
            rad:0,
            clr: null,
            setArc: function () {
                ctx.beginPath();
                ctx.arc(this.x, this.y, this.rad, 0, Math.PI * 2, true);
                ctx.fillStyle = this.clr;
                ctx.fill();
            }
        };
        [].forEach.call(centroids, (c) => {
            cmark.x = c[0];
            cmark.y = c[1];
            cmark.clr = '#0B6623';
            cmark.rad = 25;
            cmark.setArc();
        });
    });

此示例在 Canvas 区域上绘制的质心足够精细，但当浏览器刷新时，质心会发生变化。

Answer 1

我没有仔细查看您的代码，但我知道 k-means 算法在多次运行时往往会给出不同的结果。这是因为它高度依赖于第一个质心(随机选择)的位置。该算法可以找到局部最小值并“卡住”在那里，然后终止。无法保证您会在第一次运行时找到全局最小值。