C#とWPFでk-measn法のビジュアル化してみた

クラスタリングで定番のk-means, k-平均法をc#とWPFをつかって視覚化してみました。

今回は、以下2つのサイトに刺激を受けて作成しています。

play.google.com

tech.nitoyon.com

このアルゴリズムですがはだいたい以下のような手順で進みます。

1. データを座標へ配置
2. クラスタをN個配置
3. データをいちばん近いクラスタに割り当て
4. クラスタをデータの重心に移動

4で変化がなくなるまで3→4を繰り返します。

実際の動作

早速ですが、作成したアプリの動作です。

初期条件としてクラスタ数5、データ200を与えています。

[Step]押下1回目、適当に分類された点とクラスタを線で結ぶ。

[Step]押下2回目、点を一番近いクラスタに再分類

[Step]押下3回目、クラスタを中心に移動

[Step]押下4回目、点を最寄りのクラスタに再分類

のようになり、以降[Step]ボタンを押すと2～4を繰り返します。

開発環境

このアプリの作成環境ですが

• Windows10
• VisualStudo2013
• .NET Framework 4.6.2

で、ソフトの見た目をモダンアプリ風にするためにMahAppsを使用しました。

ソフト構成

気の利いた描画ライブラリはよく知らないため基盤も自分で実装します。

以下画像の通りキャンバス上に、WPFのコントロールをクラスタはRectangle、データはEllipse、それらをつなぐ線をLineで描画しています。

色は、6色をXAML上にあらかじめ記述してコード上からオブジェクトを配置するときにSytpeをFindResourceしています。

成果物について

作ったソフトの見た目はこんな感じです。

成果物をGitHubに上げています。

github.com

■記号がクラスタでキャプチャーでは3つになっています。 〇がデータで初期状態だと適当に色分けされています。

各数値やウインドウサイズを変更したときは[Reset]で初期化

[Step]ボタン押下で以下動作を(A)→(B)を繰り返します。

• クラスタと関係する点を線で結ぶ
• (A)クラスタに近い点を再分類する
• (B)中心を移動する

コードの説明

各クラスタ、点を表す構造体は以下のようにPointModelクラスで行います。見た通りですが、所属グループと座標を持ちます。IDはアニメーション時に必要かと思い実装しましたが現時点では未使用です。

public class PointModel
{
    // クラスタ/点のユニークなID
    public int ID { get; set; }

    // クラスタ/点がどのグループに所属するか
    public int Group { get; set; }

    // 現在の座標
    public double X { get; set; }
    public double Y { get; set; }
}

計算はKmeasnModelクラスで行います。 クラスタと点をリストで管理しています。

public class KmeasnModel
{
    // ...(前略)...

    // クラスタを管理するリスト
    public IList<PointModel> ClusterList { get; private set; }
    // 点を管理するリスト
    public IList<PointModel> MeasurementPointList { get; private set; }

KmeasnModelに初期状態を作るときは、クラスタは中心のほうに寄せて出現するように調整しています。

    public void InitCluster(int max)
    {
        // Calc fixed values in advance
        double xCenter = this.Width / 2;
        double yCenter = this.Height / 2;
        double xRadius = this.Width / 10;
        double yRadius = this.Height / 10;

        this.ClusterList.Clear();
        for (int i = 0; i < max; i++)
        {
            this.ClusterList.Add(new PointModel()
            {
                ID = i,
                Group = i,
                X = this.r.Next((int)(xCenter - xRadius), 
                                (int)(xCenter + xRadius)),

                Y = this.r.Next((int)(yCenter - yRadius), 
                                (int)(yCenter + yRadius)),
            });
        }
    }

同クラス内に点の所属を一番近いクラスタに点の所属を変更するメソッドがあり以下の実装をしています。

    // 一番近いクラスタに点の所属を変更する
    public void ChangeMeasurementPointBelongs()
    {
        foreach (var meas in this.MeasurementPointList)
        {
            PointModel nereCluster = null;
            double nearNolm = double.MaxValue;

            foreach (var cluster in this.ClusterList)
            {
                double x = meas.X - cluster.X;
                double y = meas.Y - cluster.Y;
                double norm = Math.Sqrt(x * x + y * y);

                if (nearNolm > norm)
                {
                    nearNolm = norm;
                    nereCluster = cluster;
                }
            }
            meas.Group = nereCluster.Group;
        }
    }

点の所属が変わった後に呼び出すクラスタの移動です。クラスタに関係する点から重心を取り、クラスタを移動させています。

    // クラスタの移動
    public void MoveCluster()
    {
        foreach (var c in this.ClusterList)
        {
            Point p = this.GetCentroid(c.Group);
            if (double.IsNaN(p.X) || double.IsNaN(p.Y))
            {
                return; // not move
            }
            c.X = p.X;
            c.Y = p.Y;
        }
    }

    // 指定したGroupの重心の取得
    public Point GetCentroid(int group)
    {
        double x = 0;
        double y = 0;
        int cnt = 0;

        var items = this.GetSamples(group);

        foreach (var item in items)
        {
            cnt++;
            x += item.X;
            y += item.Y;
        }
        return new Point(x / cnt, y / cnt);
    }

わかったこと

最後に制作を通じて分かった事ですが

• Canvasが重い！

  • オブジェクトが2000点程度でもう計算が0.5秒、描画が3秒程かかっています
    • オブジェクトが増えると指数関数的に動作が重くなる！
    • 全部削除 → 新規に追加しているせいかもしれません

• doubleのNANは==では比較できない

  • double.IsNaN(value)を使わないとNaNかどうかわからない
    • 計算後の値がNaNになる場合の除外ができずクラスタが左上に消えた

でした。