kmeanscsharp.cs

k均值聚类的c#版本

using System;
using System.Collections.Generic;
using System.Text;

namespace Cluster
{
    public class KmeansClassifier
    {
        int N;    //数据个数
        int K;    //集合个数
        int[] CenterIndex; //初始化质心数组的索引
        float[] Center;  //质心集合
        float[] CenterCopy; //质心集合副本
        float[] AllData; //数据集合
        float[][] Cluster; //簇的集合
        int[] Top;   //集合中元素的个数，也会用作栈处理

        //随机生成k个数x(0<=x<=n-1)作为起始的质心集合中元素的ID
        void CreateRandomArray(int n, int k, int[] center)
        {
            int i = 0, j;
            bool flag;

            Random random = new Random();

            while (i < k)      //随机生成k个数
            {
                int randK = random.Next(n);
                flag = false;

                for (j = 0; j < i; j++)   //判重
                {
                    if (center[j] == randK) //重复
                    {
                        flag = true;
                        break;
                    }
                }

                if (flag == false)   //如果不重复，加入
                {
                    center[i] = randK;
                    i++;
                }
                else      //如果重复，本次重新随机生成
                {
                }
            }
        }

        //返回距离最小的质心的序号
        int GetIndex(float value, float[] center)
        {
            int i;
            int index = 0;      //最小的质心序号
            double min = Math.Abs(value - center[0]); //距质心最小距离

            for (i = 0; i < K; i++)
            {
                if (Math.Abs(value - center[i]) < min) //如果比当前距离还小，更新最小的质心序号和距离值
                {
                    index = i;
                    min = Math.Abs(value - center[i]);
                }
            }

            return index;
        }

        //拷贝质心数组到副本
        void CopyCenter()
        {
            int i;

            for (i = 0; i < K; i++)
            {
                CenterCopy[i] = Center[i];
            }
        }

        //初始化质心，随机生成法
        void InitCenter()
        {
            int i = 0;
            CreateRandomArray(N, K, CenterIndex);   //产生随机的K个<N的不同的序列

            for (i = 0; i < K; i++)
            {
                Center[i] = AllData[CenterIndex[i]];//将对应数据赋值给质心数组
            }

            // CopyCenter();          //拷贝到质心副本
        }

        //加入一个数据到一个Cluster[index]集合
        void AddToCluster(int index, float value)
        {
            Cluster[index][Top[index]++] = value; //这里同进栈操作
        }

        //重新计算簇集合
        void UpdateCluster()
        {
            int i = 0;
            int tempIndex;

            //将所有的集合清空，即将TOP置0
            for (i = 0; i < K; i++)
            {
                Top[i] = 0;
            }

            for (i = 0; i < N; i++)
            {
                tempIndex = GetIndex(AllData[i], Center); //得到与当前数据最小的质心索引
                AddToCluster(tempIndex, AllData[i]);      //加入到相应的集合中 
            }
        }

        //重新计算质心集合，对每一簇集合中的元素加总求平均即可
        void UpdateCenter()
        {
            int i, j;
            double sum;

            for (i = 0; i < K; i++)
            {
                sum = 0;
                //计算簇i的元素和
                for (j = 0; j < Top[i]; j++)
                {
                    sum += Cluster[i][j];
                }
                if (Top[i] > 0)//如果该簇元素不为空
                {
                    Center[i] = (float)sum / Top[i];//求其平均值
                }
            }
        }

        //判断2数组元素是否相等
        bool IsEqual(float[] center1, float[] center2)
        {
            int i;

            for (i = 0; i < K; i++)
            {
                if (Math.Abs(center1[i] != center2[i]))
                {
                    return false;
                }
            }

            return true;
        }

        //打印聚合结果
        void Print()
        {
            int i, j;
            printf("-------------------------------------- ");
            for (i = 0; i < K; i++)
            {
                printf("\n第%d个聚类: 质心(%f)", i, Center[i]);
                for (j = 0; j < Top[i]; j++)
                {
                    printf("%f ", Cluster[i][j]);
                }
            }
        }

        /// <summary>
        /// 初始化聚类的各种数据
        /// </summary>
        /// <param name="N">数据个数</param>
        /// <param name="K"><簇个数/param>
        void InitData(float[] data, int k)
        {
            AllData = data;
            N = data.Length;
            K = k;

            if (K > N)
            {
                throw new Exception("N less than K");
            }

            //为质心集合申请空间
            Center = new float[K];
            //为质心集合索引申请空间
            CenterIndex = new int[K];
            //为质心集合副本申请空间
            CenterCopy = new float[K];
            Top = new int[K];

            //Cluster = (float**)malloc(sizeof(float*) * K);
            //为簇集合申请空间
            Cluster = new float[K][];

            //初始化K个簇集合
            for (i = 0; i < K; i++)
            {
                //Cluster[i] = (float*)malloc(sizeof(float) * N);
                Cluster[i] = new float[N];
                Top[i] = 0;
            }

            InitCenter();//初始化质心集合      
            UpdateCluster();//初始化K个簇集合
        }

        /*********************************************************
        算法描述:
         K均值聚类算法:
            给定类的个数K，将N个对象分到K个类中去，
            使得类内对象之间的相似性最大，而类之间的相似性最小。
        **********************************************************/
        //main()
        //{
        //    int Flag=1;//迭代标志，若为false,则迭代结束
        //    int i=0;
        // InitData();//初始化数据      
        // while (Flag)//开始迭代
        // {
        //  UpdateCluster();//更新各个聚类
        //  UpdateCenter();//更新质心数组
        //  if (IsEqual(Center, CenterCopy))//如果本次迭代与前次的质心聚合相等，即已收敛，结束退出
        //  {
        //   Flag = 0;
        //  }
        //  else//否则将质心副本置为本次迭代得到的的质心集合
        //  {
        //   CopyCenter();//将质心副本置为本次迭代得到的的质心集合
        //  }
        // }

        // Print();//输出结果
        // getchar();
        // getchar();

        //}
    }
}