guagua

版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://uestcguagua.blogbus.com/logs/13538190.html

K-means算法是聚类算法中划分方法下的一种常用算法

算法：k-平均。
输入：簇的数目k和包含n个对象的数据库。
输出：k个簇，使平方误差最小。
方法：
任意选择k个对象作为初始的簇中心；
repeat
根据与每个中心的距离，将每个对象赋给“最近”的簇；
重新计算每个簇的平均值；
until 不再发生变化

任务：编写程序将如下的八个点（用(x,y)代表位置）聚类为三个类。 A1(2,10),A2(2,5),A3(8,4),B1(5,8),B2(7,5),B3(6,4),C1(1,2),C2(4,9)
距离函数是Euclidean（欧几里德）函数。简单地用C#编写了一个程序：

Points.cs:

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

namespace k_means
{
public class Point
{
private double x;
private double y;
public double X
{
get { return x; }
set { x = value; }
}
public double Y
{
get { return y; }
set { y = value; }
}
public Point()
{
x = 0;
y = 0;
}
public Point(double xx, double yy)
{
x = xx;
y = yy;
}
public void SetPoint(double xx, double yy)
{
x = xx;
y = yy;
}
public static double DistanceBetween(Point p1,Point p2)
{
double distance;
return distance=Math.Pow((p1.X - p2.X) * (p1.X - p2.X) + (p1.Y - p2.Y) * (p1.Y - p2.Y),1.0/2);
}
}
}
Program.cs:

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

namespace k_means
{
class Program
{
static void Main(string[] args)
{
int k=3; //簇的数目
int n=8;
List points = new List(); //n条数据

points.Add(new Point(2,10));

points.Add(new Point(5, 8));

points.Add(new Point(1, 2));

points.Add(new Point(2, 5));

points.Add(new Point(8,4));

points.Add(new Point(7,5));

points.Add(new Point(6,4));

points.Add(new Point(4,9));

string[] clusters = new string[k]; //k个簇,每个簇存储数据在points中的位置，数据之间用","分开
Point[] centers = new Point[k]; //k个簇的中心
Point[] preCenters = new Point[k];//前一次计算的簇中心
Regex r=new Regex(",");

for (int i = 0; i < k; i++) //取前k个对象作为初始的簇中心
{
centers[i] = new Point(points[i].X,points[i].Y);
}
bool stop=false;
while (!stop)
{
for (int i = 0; i < clusters.Length; i++)//清空簇中的数据
{
clusters[i] = null;
}
for (int i = 0; i < n; i++)//搜索所有对象
{
double distance = Point.DistanceBetween(points[i], centers[0]);
double temp;
int num = 0;

for (int j = 0; j < k; j++)//搜索k个簇，比较对象与簇中心的距离，将与当前对象距离最小的簇的编号放入num
{
if ((temp = Point.DistanceBetween(points[i], centers[j])) < distance) { num = j; distance = temp; }
}
clusters[num] = clusters[num] + i + ",";
}
for (int i = 0; i < k; i++)
{
preCenters[i] = new Point(centers[i].X,centers[i].Y);//保存先前的簇中心
}

for(int i=0;i
{
centers[i].X = 0;
centers[i].Y = 0;
if(clusters[i]!=null)
{
string[] pointsNum = r.Split(clusters[i]);
for (int j = 0; j < pointsNum.Length-1; j++)
{
centers[i].X = centers[i].X + points[Convert.ToInt32(pointsNum[j])].X;
centers[i].Y = centers[i].Y + points[Convert.ToInt32(pointsNum[j])].Y;
}
centers[i].X = Convert.ToDouble(centers[i].X) / (pointsNum.Length-1);
centers[i].Y = Convert.ToDouble(centers[i].Y) / (pointsNum.Length-1);
}
}
stop = true;
for (int i = 0; i < k;i++ )
{
if (preCenters[i].X != centers[i].X || preCenters[i].Y != centers[i].Y) stop = false;
}
}

for (int i = 0; i < k; i++)//输出每个簇中数据所在的位置
{
string[] nums = r.Split(clusters[i]);
for (int j = 0; j < nums.Length-1; j++)
{
Console.Write("({0},{1}) ", points[Convert.ToInt32(nums[j])].X, points[Convert.ToInt32(nums[j])].Y);
}
Console.Write('\n');
}
Console.Read();
}
}
}
遇到的问题：1.竟然把算法给搞错了，只算了一次，明显不合理（受初值影响），我的实验报告啊！郁闷，啥时候这么没有严谨的治学精神了。。。

2.C#中的数据类型没有注意，比如这样的一段代码

for (int i = 0; i < k; i++)
{
preCenters[i] = new Point(centers[i].X,centers[i].Y);//保存先前的簇中心
}

曾经直接写成

for (int i = 0; i < k; i++)
{
preCenters[i] = centers[i];//保存先前的簇中心
}

要知道，C#对象是引用类型，如果这样写，改变 centers会改变preCenters的值。

3.最无聊的错误：

return distance=Math.Pow((p1.X - p2.X) * (p1.X - p2.X) + (p1.Y - p2.Y) * (p1.Y - p2.Y),1.0/2);

写成

return distance=Math.Pow((p1.X - p2.X) * (p1.X - p2.X) + (p1.Y - p2.Y) * (p1.Y - p2.Y),1/2);

每次distance都为1.0