k平均法（k-meansクラスタリング）実装

Courseraの機械学習コースでk平均法を学んだので、理解を深めるために実装してみた。
わざわざ日記にするほど難しくはないが、メモということで。ソースコードはここ。

メインは次のGetKMeans_withCost()で、tryNumの数だけk平均法を試して、コスト(最寄りのセントロイドまでの距離の合計)が最小になった結果を返している。返り値は各セントロイドの位置と最終的なコストのタプル。多次元対応。

入力はクラスタ数kとMatrix型の変数x。xは行が１サンプル、列が特徴を表す。

アルゴリズムは単純で、　　

• xからk個ランダムに選び出し、この位置をセントロイドの初期値にする
• それぞれのxに、最も近いセントロイドを割り当てる
• セントロイドの位置を、割り当てられているxの平均値にアップデート

を繰り返しているだけ。セントロイドの位置が変わらなくなるまでループする。

static Tuple<int[], double> GetKMeans_withCost(int tryNum, int K, Matrix x)
{
    var r = new Random();

    int[] ret = null;
    var centroids = new Matrix[K];

    var minCost = double.MaxValue;
    while (tryNum > 0)
    {
        Initialize(r, x, centroids);

        var J = 0.0;
        int[] c = null;
        while (true)
        {
            var cTuple = AssignC(centroids, x);
            c = cTuple.Item1;

            var prevJ = J;
            J = cTuple.Item2;
            if (DoubleUtil.Equals(prevJ, J)) break;

            UpdateCentroids(centroids, x, c);
        }

        if (J < minCost || ret == null)
        {
            ret = c;
            minCost = J;
        }

        tryNum--;
    }

    return new Tuple<int[], double>(ret, minCost);
}

こちらはkの値をいろいろ試してみるコード。kの候補値(Ks[])ごとの結果を返す。
うまい具合にエルボー（これ以上増やしてもあまりコストが下がらないようなkの値）があれば、それを使うのが良いらしい。

public static double[] FindK(int tryNum, int[] Ks, Matrix x)
{
    var ret = new double[Ks.Length];

    for (int i = 0; i < Ks.Length; i++)
    {
        var result = GetKMeans_withCost(tryNum, Ks[i], x);
        ret[i] = result.Item2;
    }

    return ret;
}