• TOP
• 確率・統計

[C#]K-Meansによるクラスタリング(区分け)

2021-01-24T09:58:00+09:00 2021-03-24T03:59:23Z C# 確率・統計

 

K-means(K平均法)による分類のC#での実装です。
K-meansの詳しい説明はWikiなどをご参照ください。

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace KMeans
{
    class CKMeans
    {
        //配列データ
        public class DataSet {
            public List data = new List();
        }

        public class Cluster {
            public List dataIndexes = new List();
        }

        //ユークリッド距離を求める
        private static double Distance(List v1, Listv2) {
            double fDistance = 0.0;

            for (int i = 0; i < v1.Count; ++i) {
                fDistance = (i * fDistance + Math.Sqrt((v1[i] - v2[i]) * (v1[i] - v2[i]))) / (i + 1);
            }

            return fDistance;
        }

        private static bool IsMatchCluster(Cluster[] c1, Cluster[] c2) {
            if (c1.Length != c2.Length) return false;

            for (int i = 0; i < c1.Length; ++i) {
                if (c1[i].dataIndexes.Count != c2[i].dataIndexes.Count) return false;
                int count = c1[i].dataIndexes.Count;
                for (var j = 0; j < count; ++j) {
                    if (c1[i].dataIndexes[j] != c2[i].dataIndexes[j]) return false;
                }
            }

            return true;
        }

        //K平均法でグループ化する
        public static Cluster[] K_means(List dataSet, int group_k)
        {

            //データの範囲を保持する配列
            var range_min = dataSet[0].data.ToArray();
            var range_max = dataSet[0].data.ToArray();

            //データの個数
            int dataLength = range_max.Length;

            //各点の最小・最大値を求める
            foreach (var data in dataSet)
            {
                for (int i = 0; i < dataLength; ++i)
                {
                    range_max[i] = Math.Max(range_max[i], data.data[i]);
                    range_min[i] = Math.Min(range_min[i], data.data[i]);
                }
            }

            //中心をランダムにgroup_k個設置する
            var listCenter = new List();
            var random = new Random();

            for (int k = 0; k < group_k; ++k)
            {
                var data = new double[dataLength];
                for (int i = 0; i < dataLength; ++i)
                {
                    data[i] = random.NextDouble() * (range_max[i] - range_min[i]) + range_min[i];
                }
                var center = new DataSet();
                center.data = new List(data);
                listCenter.Add(center);
            }

            //最後の確認データ
            Cluster[] lastmatches = null;

            //
            for (int i = 0; i < 100; ++i)
            {
                var bestmatches = new Cluster[group_k];
                for (int j = 0; j < group_k; ++j) {
                    bestmatches[j] = new Cluster();
                }

                //それぞれの行に対し最も近い重心を探し出す
                for (int j = 0; j < dataSet.Count; ++j)
                {
                    var row = dataSet[j];
                    int bestmatch = 0;
                    double bestMachDistance = Distance(listCenter[0].data, row.data); ;
                    for (int k = 1; k < group_k; ++k)
                    {
                        double fDistance = Distance(listCenter[k].data, row.data);
                        //Debug.WriteLine(String.Format("DataSet={0}, k={1}, distance={2}, bestMachDistance={3}", j, k, fDistance, bestMachDistance));
                        if (fDistance < bestMachDistance)
                        {
                            bestMachDistance = fDistance;
                            bestmatch = k;
                        }
                    }
                    bestmatches[bestmatch].dataIndexes.Add(j);
                }

                //結果が前回と同じなら完了
                if (lastmatches != null && IsMatchCluster(lastmatches, bestmatches)) {
                    return lastmatches;
                }
                lastmatches = bestmatches;

                //重心をそのメンバーの平均に移動する
                for (int k = 0; k < group_k; ++k)
                {

                    if (bestmatches[k].dataIndexes.Count > 0)
                    {

                        double[] averages = new double[dataLength];
                        Array.Clear(averages, 0, dataLength);

                        for (int j = 0; j < bestmatches[k].dataIndexes.Count; ++j)
                        {
                            DataSet data = dataSet[bestmatches[k].dataIndexes[j]];

                            for (int l = 0; l < data.data.Count; ++l)
                            {
                                averages[l] = (j * averages[l] + data.data[l]) / (j + 1);
                            }
                        }
                        listCenter[k].data = new List(averages);
                    }
                }
            }

            return lastmatches;
        }
    }
}

以下のように使用します。

//データセットを作る
List listDataSet = new List();

listDataSet.Clear();
Random random = new Random();
for (int i = 0; i < 1000; ++i) {
    var dataSet = new CKMeans.DataSet();
    dataSet.data.Add(random.Next((int)1000));
    dataSet.data.Add(random.Next((int)1000));
    listDataSet.Add(dataSet);
}

//K-meansにより分類する
var cluster = CKMeans.K_means(listDataSet, 10);