一、背景
煤矿地磅产生了一系列数据：
我想从这些数据中，取出最能反映当前车辆重量的数据（有很多数据是车辆上磅过程中产生的数据）。我于是想到了聚类算法KMeans，该算法思想比较简单。
二、算法步骤
1、从样本中随机取出k个值，作为初始中心
2、以k个中心划分这些数据，分为k个组
3、重新计算出每个组的中心，作为新中心
4、如果初始中心和新中心不相等，则把新中心作为初始中心，重复2，3。反之，结束
注意：
1、我没有用严格的算法定义，怕不好理解
2、KMeans善于处理球形数据，因此随机取k个质心，每个质心吸引离它最近的数据
3、由于质心的取值是不科学的，所以需要不断地计算调整，直到质心名副其实
三、算法分析及特点
1、从算法步骤当中可以看出有两个问题，需要解决：
首先，如何计算每个组（簇）的质心？
其次，如何把值划分到不同的组？
2、解决上面两个问题，因场景和要求不同而有不同的小算法，由于我的数据是一维的，而不是点，所以可以简单处理：
a、以每个组的平均值作为质心
b、根据值离质心的距离（相减），选择距离最近的组加入
3、此算法有两个缺点：
1）某个组（簇）划分不充分，还可以再划分为更小的组。（容易陷入局部最优）
2）需要用户指定k，聚类结果对初始质心的选择较为敏感（初始选择不同，聚类结果可能不同）
4、优点：简单易理解和上手
四、实现
public class KMeans
{
/*
* 聚类函数主体。
* 针对一维 decimal 数组。指定聚类数目 k。
* 将数据聚成 k 类。
*/
public static decimal[][] cluster(decimal[] p, int k)
{
// 存放聚类旧的聚类中心
decimal[] c = new decimal[k];
// 存放新计算的聚类中心
decimal[] nc = new decimal[k];
// 存放放回结果
decimal[][] g;
// 初始化聚类中心
// 经典方法是随机选取 k 个
// 本例中采用前 k 个作为聚类中心
// 聚类中心的选取不影响最终结果
for (int i = ; i < k; i++)
c[i] = p[i];
// 循环聚类，更新聚类中心
// 到聚类中心不变为止
while (true)
{
// 根据聚类中心将元素分类
g = group(p, c);
// 计算分类后的聚类中心
for (int i = ; i < g.Length; i++)
{
nc[i] = center(g[i]);
}
// 如果聚类中心不同
if (!equal(nc, c))
{
c = nc;
nc = new decimal[k];
}
else
break;
}
return g;
}
/*
* 聚类中心函数
* 简单的一维聚类返回其算数平均值
* 可扩展
*/
public static decimal center(decimal[] p)
{
if (p.Length == ) return ;
return sum(p) / p.Length;
}
/*
* 给定 decimal 型数组 p 和聚类中心 c。
* 根据 c 将 p 中元素聚类。返回二维数组。
* 存放各组元素。
*/
public static decimal[][] group(decimal[] p, decimal[] c)
{
// 中间变量，用来分组标记
int[] gi = new int[p.Length];
// 考察每一个元素 pi 同聚类中心 cj 的距离
// pi 与 cj 的距离最小则归为 j 类
for (int i = ; i < p.Length; i++)
{
// 存放距离
decimal[] d = new decimal[c.Length];
// 计算到每个聚类中心的距离
for (int j = ; j < c.Length; j++)
{
d[j] = distance(p[i], c[j]);
}
// 找出最小距离
int ci = min(d);
// 标记属于哪一组
gi[i] = ci;
}
// 存放分组结果
decimal[][] g = new decimal[c.Length][];
// 遍历每个聚类中心，分组
for (int i = ; i < c.Length; i++)
{
// 中间变量，记录聚类后每一组的大小
int s = ;
// 计算每一组的长度
for (int j = ; j < gi.Length; j++)
if (gi[j] == i)
s++;
// 存储每一组的成员
g[i] = new decimal[s];
s = ;
// 根据分组标记将各元素归位
for (int j = ; j < gi.Length; j++)
if (gi[j] == i)
{
g[i][s] = p[j];
s++;
}
}
// 返回分组结果
return g;
} /*
* 计算两个点之间的距离， 这里采用最简单得一维欧氏距离， 可扩展。
*/
public static decimal distance(decimal x, decimal y)
{
return Math.Abs(x - y);
} /*
* 返回给定 decimal 数组各元素之和。
*/
public static decimal sum(decimal[] p)
{
decimal sum = 0.0M;
for (int i = ; i < p.Length; i++)
sum += p[i];
return sum;
} /*
* 给定 decimal 类型数组，返回最小值得下标。
*/
public static int min(decimal[] p)
{
int i = ;
decimal m = p[];
for (int j = ; j < p.Length; j++)
{
if (p[j] < m)
{
i = j;
m = p[j];
}
}
return i;
} /*
* 判断两个 decimal 数组是否相等。 长度一样且对应位置值相同返回真。
*/
public static bool equal(decimal[] a, decimal[] b)
{
if (a.Length != b.Length)
return false;
else
{
for (int i = ; i < a.Length; i++)
{
if (a[i] != b[i])
return false;
}
}
return true;
}
}
客户端调用：
static void Main(string[] args)
{
var path = string.Empty;
int k = ;
try
{
path = Path.Combine(AppDomain.CurrentDomain.BaseDirectory, "blanceTest.txt");//数据文件路径
k = ;
}
catch (Exception)
{
Console.Write("参数错误");
return;
} decimal[] p = { , , , , , , , , , , , , , , , , , , , , , , , , }; List<decimal> pList = new List<decimal>(); var lines = File.ReadAllLines(path); foreach (var line in lines)
{
var data = System.Text.RegularExpressions.Regex.Replace(line, @" +", " ");
var datas = data.Split(' '); pList.AddRange(datas.Where(d => d != "").Select(d => Convert.ToDecimal(d)));
} p = pList.ToArray(); k = ;
decimal[][] g;
g = KMeans.cluster(p, k);
for (int i = ; i < g.Length; i++)
{
for (int j = ; j < g[i].Length; j++)
{
Console.WriteLine(g[i][j]);
}
Console.WriteLine("----------------------");
}
Console.ReadKey(); }
注意：
1、如果数据文件为空或不存在，则用初始化的p数组，作为测试数据
2、文件中的数据，见开篇截图
参考文章：
