数据挖掘聚合算法K-Means

目录

• 基本信息
• 工作原理
• 算法优缺点
• 算法实现

基本信息

K-means算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。该算法认为簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。

工作原理

从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然 后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到聚类中心K个对象不在更换为止。k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。

算法优缺点

K-Means聚类算法的优点主要集中在：

1. 算法快速、简单
2. 对大数据集有较高的效率并且是可伸缩性的
3. 时间复杂度接近于线性，而且适合挖掘大规模数据集，K-Means聚类算法的时间复杂度是O(nkt)，其中n代表数据集中对象的数量，t代表着算法迭代的次数，k代表着簇的数目。

K-Means算法的缺点

1. 很多时候，事先并不知道给定的数据集应该分成多少个类才最合适。在算法中K是事先给定的，对聚类结果有较大的影响，一旦初始值选择不好，可能得到有效的聚类结果，对于该问题的解决，许多算法采用遗传算法，对于数据是密集的，簇与簇之间区别较明显，得到的聚类结果较为有效。
2. 该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的。所以需要对算法的时间复杂度进行分析、改进，提高算法应用范围

算法实现

例如：如下随机生成1-100内10个double类型的数，可以看出数据簇与簇之间区别较为明显，得到的聚类较为有效，结果也比较明显。

如下：随机生成100个数

 

 代码：

namespace DataStructure
{
    using System;
    using System.Collections.Generic;
    /// <summary>
    /// author yanhf
    /// K-Means
    /// </summary>
    public class K_Means
    {
        /// <summary>
        /// Update index cluster identification based on cluster point key
        /// </summary>
        /// <param name="data">Data</param>
        /// <param name="index">index</param>
        /// <param name="key">key values</param>
        public static void _K_Means(double[] data, ref int[] index, int[] key)
        {
            bool change = true;
            int _index = 0;
            double Length = 0;
            while (change)
            {
                change = false;
                for (int i = 0; i < data.Length; i++)//根据当前的聚簇点更新index聚簇标识数组
                {
                    for (int j = 0; j < key.Length; j++)
                    {
                        double currentLength = Math.Abs(data[key[j]] - data[i]);
                        if (j == 0 || Length > currentLength)
                        {
                            Length = Math.Abs(data[key[j]] - data[i]);
                            _index = j + 1;
                        }
                    }
                    index[i] = _index;
                    Length = 0;
                }
                change = _ChangeKey(data, index, ref key);
            }
        }
        /// <summary>
        /// Judging the current Key needs not to be changed
        /// </summary>
        /// <param name="data">Data</param>
        /// <param name="index">index</param>
        /// <param name="key">key values</param>
        /// <returns></returns>
        public static bool _ChangeKey(double[] data, int[] index, ref int[] key)
        {
            bool IsChange = false;
            int i = 0;
            List<double> _listData = new List<double>();
            while (i++ < key.Length)
            {
                _listData.Clear();
                for (int j = 0; j < index.Length; j++)
                {
                    if (index[j] == i)
                    {
                        _listData.Add(data[j]);
                    }
                }
                _listData.Sort();
                if (_listData.Count > 1)
                {
                    if (key[i - 1] != _index(data, _listData[_listData.Count / 2]))
                    {
                        IsChange = true;
                        key[i - 1] = _index(data, _listData[_listData.Count / 2]);
                    }
                }
            }
            return IsChange;
        }
        /// <summary>
        /// Get the index in the key's data
        /// </summary>
        /// <param name="data">Data</param>
        /// <param name="num">key values</param>
        /// <returns></returns>
        public static int _index(double[] data, double num)
        {
            List<double> _listData = new List<double>(data);
            return _listData.IndexOf(num) >= 0 ? _listData.IndexOf(num) : -1;
        }
    }
}

using DataStructure;
using System;

namespace ClusterNumeric
{
    class ClusterNumProgram
    {
        public static int dataNumber = 0;
        public static int keyNumber = 0;
        static void Main(string[] args)
        {
            start:
            string[] inputArray = null;
            {
                Console.WriteLine("
Enter the total number of data you want to divide and The number of divisions
For example: 100,3");
                string input = Console.ReadLine();
                inputArray = input.Split(new char[] { ',' });
            } while (!int.TryParse(inputArray[0], out dataNumber) || !int.TryParse(inputArray[1], out keyNumber) || keyNumber >= dataNumber) ;

            Random random = new Random();
            double[] _data = new double[dataNumber];
            Console.WriteLine("
Show the total number of  random generated  data");
            Console.WriteLine("-------------------------------------------------------------------------");
            int M = 1;
            for (int i = 0; i < _data.Length; i++)
            {
                _data[i] = Math.Round(random.NextDouble() * (100 < dataNumber ? dataNumber : 100), 2);
                Console.Write(_data[i].ToString("F2").PadLeft(7));
                if (M++ % 10 == 0)
                {
                    Console.WriteLine();
                }
            }
            int[] _index = new int[dataNumber];
            int[] keyData = new int[keyNumber];
            for (int i = 0; i < keyNumber; i++)
            {
                keyData[i] = random.Next(0, dataNumber);
            }
            K_Means._K_Means(_data, ref _index, keyData);
            Console.WriteLine("
*************************************************************************");
            Console.WriteLine("
Show the Result");
            Console.WriteLine("-------------------------------------------------------------------------");
            for (int i = 0; i < keyData.Length; i++)
            {
                M = 1;
                Console.WriteLine("Value values of the " + (i + 1) + " group:key " + _data[keyData[i]].ToString().PadRight(7));
                Console.WriteLine();
                for (int j = 0; j < _index.Length; j++)
                {
                    if (_index[j] == i + 1)
                    {
                        Console.Write(_data[j].ToString("F2").PadLeft(7));
                        if (M++ % 10 == 0)
                        {
                            Console.WriteLine();
                        }
                    }
                }
                Console.WriteLine();
                Console.WriteLine("-------------------------------------------------------------------------");
            }
            Console.WriteLine("*************************************************************************");
            goto start;
        }
    }
}