C#:[2D 演示]聚类算法:Kmean & FCM
聚类分析是一种根据样本之间的距离或者说是相似性(亲疏性),把越相似、差异越小的样本聚成一类(簇),最后形成多个簇,使同一个簇内部的样本相似度高,不同簇之间差异性高。
算法演示主界面
视频演示
Kmeans是聚类算法中较为经典的算法之一,由于其效率高,所以一般大规模的数据进行聚类的时候都会被广泛应用。
算法的目的是,先指定聚类的数目c,然后将输入的数据划分为c类,值簇内的数据之间具有较高的相似程度,而簇之间的相似程度较低。
K-means算法基本原理
k均值聚类算法(k-means clustering algorithm)是一种迭代求解的聚类分析算法。其实现过程如下:
第一步:从文件中读取数据,点用元组表示;确定聚类个数k。
第二步:初始化k个聚类中心。在所获得的的样本区间范围内随机产生k个值作为初始质心。
第三步:对每个数据点进行分类,选择相似度最高的质心所在的簇作为该样本的类别,形成k个簇。
第四步:计算每个簇中所有点的平均值,更新聚类中心。
第五步:迭代3~4步,直至聚类中心不再更改或达到最大迭代次数,算法结束。
基本步骤
(1)选择初始聚类中心Zi(0)
(2)计算初始隶属度矩阵U(0)
(3)求各类的新的聚类中心Zi(L)
(4)计算新的隶属度矩阵U(L+1)
(5) 回到第(3)步,重复至收敛
(6)类别调整:①合并②分解③删除
FCM算法流程图
源码:
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Windows.Forms;
namespace KMeans
{
publicpartialclassKmeans : Form
{
publicKmeans()
{
InitializeComponent();
}
//用作数据的点列表
List<< span="">Point2D> points = newList<< span="">Point2D>();
//保存集群(簇)数据的集群(簇)类列表
List<< span="">Cluster> clusters = newList<< span="">Cluster>();
Random random = newRandom();//初始化随机数生成器
privateint IterationCount = 1000;//迭代次数
privatedouble ErrorThreshold = 0.5;//迭代条件
privateint ItemCount = 200;//点数
privateint ClusterCount = 4;//簇数
privatedouble FuzzyFactor = 1.8;//模糊因子
// 收集 UI 上的数据并将其放在边框之间的函数
// 簇数必须在 [2 10] -> 簇数之间
// IterationCount 介于 [10 10000] -> 最多迭代多少次
// ItemCount -> 随机调用时生成多少
// ErrorThreshold -> 当中心位移低于这个值时停止迭代
// FuzzyFactor -> FCM 公式中使用的模糊常数值
void collectData()
{
if (int.TryParse(t_cluster.Text, out ClusterCount) == false) ClusterCount = 4;//簇数
if (int.TryParse(t_iteration.Text, out IterationCount) == false) IterationCount = 1000;//迭代次数
if (int.TryParse(t_item.Text, out ItemCount) == false) ItemCount = 200;//点数
if (double.TryParse(t_err.Text, out ErrorThreshold) == false) ErrorThreshold = 0.5;//迭代终止条件阈值
if (double.TryParse(t_fuzzy.Text, out FuzzyFactor) == false) FuzzyFactor = 1.8;//模糊常数
ClusterCount = Math.Max(2, Math.Min(10, ClusterCount));//簇数 大于2 小于10
IterationCount = Math.Max(10, Math.Min(10000, IterationCount));//迭代次数 介于[10,10000]
ItemCount = Math.Max(20, Math.Min(1000, ItemCount));//坐标点数 [20,1000]
ErrorThreshold = Math.Max(0.1, Math.Min(2, ErrorThreshold));//迭代终止条件 [0.1,2]
FuzzyFactor = Math.Max(1.01, Math.Min(Double.MaxValue, FuzzyFactor));//大于1.01
}
void resetData() => points.Clear();//清空坐标点
//在需要时重新绘制图片框
privatevoid ReDraw() => pictureBox.Invalidate();
//随机数据
void randomData()
{
if (int.TryParse(t_item.Text, out ItemCount) == false) ItemCount = 200;
ItemCount = Math.Max(20, Math.Min(1000, ItemCount));//重新获取坐标点数
resetData();//清空数据列表
for (int i = 0; i < ItemCount; i++)
{ //将在窗口宽度和高度内生成随机数。
points.Add(newPoint2D(pictureBox.Width, pictureBox.Height));
}
ReDraw();
}
//添加数据
void addData(int x, int y)
{
//将在单击区域内与中心的“半径”距离之间产生“计数”点
float radius = Math.Max(pictureBox.Width,pictureBox.Height) / 15f;//半径
int count = ItemCount / 60;//单击图片框在点击半径范围内产生坐标点数量
for (int i = 0; i < count; i++)
{
double r = random.NextDouble() * radius;//点到点击位置距离
double ang = random.NextDouble() * Math.PI;//角度
float _x = (float) (r * Math.Cos(ang)) + x;
float _y = (float) (r * Math.Sin(ang)) + y;
if (0 > _x || _x > pictureBox.Width) continue;
if (0 > _y || _y > pictureBox.Height) continue; //如果结果点不在窗口中,则不将其添加到列表中
points.Add(newPoint2D(_x, _y));
}
ReDraw();
}
// 调用重组
// 重新构建簇并调用其中一种聚类算法
privatevoid resetall()
{
collectData();//获取UI参数设置
clusters.Clear(); //清空簇
//如果之前没有手动输入点,则生成随机点
if (points.Count == 0) randomData();
//我们最多允许 10 个簇,我们选择了 10 种颜色。
// 如果要增加簇数,增加颜色。
var colours = new[]
{
Color.Red, Color.Blue, Color.Green, Color.Yellow, Color.Violet, Color.Chocolate, Color.DarkOrchid,
Color.YellowGreen, Color.Teal, Color.Purple
};//颜色数组
for(int i=0;i<clustercount;i++)< span=""></clustercount;i++)<>
{ //在窗口内再次使用随机选择的中心点重新构造簇
clusters.Add(newCluster(random,pictureBox.Width, pictureBox.Height, colours[i%colours.Length]));//colours[i%colours.Length]第i个簇的颜色
}
ReDraw();//重新绘制图片框
AnimTimer.Enabled = animatecheck.Checked;//仿真定时器是否可用
}
//图片框绘制
privatevoid pictureBox_Paint(object sender, PaintEventArgs e)
{
Graphics g = e.Graphics;
//清晰的背景
g.FillRectangle(Brushes.White, 0, 0, pictureBox.Width, pictureBox.Height);
//画出所有的点
foreach (var p in points) p.draw(g);
//finalscene 如果为真,则显示所有簇中心。
// 绘制它以便我们可以看到变化。
bool finalscene = AnimTimer.Enabled == false;//定时器禁用时,finalscene=true
finalscene = finalscene || animatecheck.Checked == false;//或者定时器未启用
finalscene = finalscene && show_olds.Checked;//并且 勾选显示旧的簇原点
//绘制所有簇
foreach (var c in clusters) c.draw(g, finalscene);
}
double iterasyonFCM()
{
//计算所有聚类中心的所有点的隶属度
foreach (var point in points) { point.CalculateMSV(clusters, FuzzyFactor); }
//根据点的隶属度计算所有集合的新中心
double err = clusters.Select((t, i) => t.calculateOrigin(i, points, FuzzyFactor)).Sum();
//如果位移减小,则迭代结束。
if (err < ErrorThreshold) AnimTimer.Enabled = false;
return err;
}
double iterasyonKMEAN()
{
//清除所有簇的成员
clusters.ForEach(c => c.members.Clear());
//计算所有点到所有聚类中心的距离
//将离簇中心最近的点添加到该簇中
foreach (var p in points)//遍历所有点
{
float m = float.MaxValue;
Cluster c = clusters[0];
foreach(var cl in clusters)//遍历所有簇
{
float dist = cl.origins.dist(p);//点p到簇cl距离平方
if (dist > m) continue;
m = dist;//寻找点p到所有簇中心 最小的距离平方
c = cl;//找到点p离哪个簇中心最近
}
c.add(p);//将p添加到最近的簇
}
//使其成员的所有簇的坐标的算术中点成为该簇的新中心
double err = clusters.Sum(c => c.CheckOrigin());//计算新的簇中心并返回 每个簇新中心与旧的簇中心距离平方的和
//如果所有簇中心位移平方和低于误差范围,则完成迭代。
AnimTimer.Enabled = err > ErrorThreshold;
return err;
}
privatebool kmeans = true;//默认使用kmean聚类算法
privateint iterCount = 0;//迭代次数
privatevoid AnimTimer_Tick(object sender, EventArgs e)//定时器触发
{
double err = kmeans ? iterasyonKMEAN() : iterasyonFCM();//迭代 kmean为true,执行iterasyonKMEAN函数
if (++iterCount > IterationCount)//超过迭代次数
AnimTimer.Enabled = false;//停止定时器
Text = $@"Iterasyon : {iterCount} Error : {err:E2}";//窗体文本显示:迭代次数 & 所有簇中心位移平方和(两位小数)
ReDraw();//重新绘制图片框
}
privatevoid Animate_CheckedChanged(object sender, EventArgs e)
{
AnimTimer.Enabled = animatecheck.Checked;//定时器启用状态
}
//单击 K-Means按钮
privatevoid start_Click(object sender, EventArgs e)
{
kmeans = true;
resetall();//生成随机点,构造簇。执行完毕,定时器tick事件才会有有效执行
}
//单击 FCM按钮
privatevoid button1_Click(object sender, EventArgs e)
{
kmeans = false;
resetall();
}
//单击图片框
privatevoid pictureBox_MouseDown(object sender, MouseEventArgs e)
{
if (AnimTimer.Enabled) return;//定时器启用期间不可用
addData(e.X, e.Y);//添加数据
}
//Random按钮 生成随机数据点,并绘制点
privatevoid random_data_Click(object sender, EventArgs e)
{
randomData();
}
//清空数据
privatevoid clear_data_Click(object sender, EventArgs e)
{
resetData();
clusters.Clear();
pictureBox.Invalidate();//图片框清空
}
}
}
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace KMeans
{
publicclassPoint2D//单个点
{
publicfloat x, y;//坐标
public Color color;//颜色
Pen pen = new Pen(Color.Red);//绘制直线或曲线的对象
publicdouble[] MSV;//
publicdouble[] distList;//到簇中心距离列表
publicPoint2D(float x, float y)
{
this.x = x;
this.y = y;
this.color = Color.Black;
}
publicPoint2D(float a)
{
x = y = a;
color = Color.Black;
}
static Random r = new Random();
publicPoint2D(int w,int h)//在宽w和高h内随机生成坐标点
{//坐标原点在图片框左上角
x = (float)r.NextDouble() * w;
y = (float)r.NextDouble() * h;
color = Color.Black;//黑色
}
publicvoid CalculateMSV(List
{
// kmean 算法不需要 MSV 和 distList。
// 所以当这个函数被调用时,如果需要,将创建数组
if (MSV == null || MSV.Length != cls.Count)
{
MSV = newdouble [cls.Count];//簇数个MSV
distList = newdouble[cls.Count];//簇数个距离列表
}
/*
m -> 模糊因子
dist(p,o) -> 计算权重的簇中心到点p的距离
dist(p,o(i)) -> i。聚类中心到点 p 的距离
C -> 集群
重量 =
{ 1 /<TOTAL ( 1 到簇数 ) [ dist(p,o) / dist(p,o(i)) ] ^ [ 2 - (m-1) ]> }
MSV = 重量 ^ 米
它是用公式计算的.
*/
double fizzm = 2.0 / (m - 1.0); //由于顶部总是固定的,所以我没有计算很多次。
for (int i = 0; i < cls.Count; i++)
distList[i] = Math.Sqrt(dist(cls[i].origins)); //一旦我们找到了距离
double best = 0;
for (int i = 0; i < cls.Count; i++)
{
double mm = 0;
for (int j = 0; j < cls.Count; j++)
{
double ratio = i!=j ? distList[i] / distList[j] : 1.0;
double val = Math.Pow(ratio, fizzm); // 距离比 ^ fizzm
mm += val; //累加所有
}
MSV[i] = Math.Pow(1.0 / mm, m); //找到 MSV 值.
if (MSV[i] > best)
{
best = MSV[i];
bestCluster = cls[i]; //将此点绘制为好像它属于具有最高权重的任何集群
} // 别忘了在 FCM 中,一个点在
// 我在这里做的只是为了着色。否则,每个点都属于每个度<< span="">权重>的簇.
}
}
public Cluster bestCluster;//最佳簇
//计算距离平方
publicfloat dist(Point2D p)
{
float xx = p.x - x;
float yy = p.y - y;
return xx * xx + yy * yy;
}
internalvoid draw(Graphics g, float s = 2f)//2s:点宽度
{
pen.Color = color;
g.FillEllipse(pen.Brush, x - s, y - s, 2*s, 2*s);//绘制边框点
}
}
}
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace KMeans
{
publicclassCluster//单个簇
{
public List
public List
public Point2D origins;//最终簇中心
//构造函数:随机数生成器,宽度,高度,颜色。
publicCluster(Random r, int width, int height, Color color)
{
origins = new Point2D((float) (width * r.NextDouble()), (float) (height * r.NextDouble())) {color = color};//随机生成簇中心
pen = new Pen(color);//初始化pen颜色
}
private Pen pen;//笔
//簇的绘制函数
publicvoid draw(Graphics g,bool final = false)
{
if (final)
{ //如果我们要显示以前的中心,让我们先绘制它们,以便它留在后面
for (int i = 0; i < oldOrigins.Count; i++)
{
oldOrigins[i].draw(g,8f + 0.05f * i);//第i簇 绘制簇中心, 越新簇中心越大
}
}
// 绘制最后一个中心
origins.draw(g, 10);
// 从中心到该集合的元素画一条线。
foreach (var p in members) { g.DrawLine(pen, origins.x, origins.y, p.x, p.y); }
}
//添加点p到簇
publicvoid add(Point2D p)
{
members.Add(p);//将p点添加到簇
p.color = origins.color;//点p的颜色与簇中心颜色一致
}
//kMeans 的中心计算
publicdouble CheckOrigin()
{
double x = 0, y = 0;
foreach (var p in members)//遍历簇的点集合
{ //取中间的算术
x += p.x;
y += p.y;
}
x /= members.Count;//算数平均值
y /= members.Count;
//创建一个新点:计算的中心点坐标
Point2D no = new Point2D((float) x, (float) y) {color = origins.color};
//将旧中心(待绘制)添加到列表中
oldOrigins.Add(origins);
//使用两个中心之间的距离进行误差计算
var err = no.dist(origins);//上一中心到新的中心距离
origins = no;//更新 中心坐标
return err;//返回两次中心坐标点间距离平方
}
//FCM 中心
publicdouble calculateOrigin(int index,List
{
double x = 0, y = 0;
double mem = 0;
members.Clear();
/*
newCenterX = (w1 * p1.x + w2 * p2.x + ... + wn * pn.x) / (w1 + w2 + ... + wn)//加权平均
newCenterY = (w1 * p1.y + w2 * p2.y + ... + wn * pn.y) / (w1 + w2 + ... + wn)
*/
foreach (Point2D point in points)
{
double tmp = point.MSV[index]; //用这个集合的点权重
mem += tmp;//权重累加
x += tmp * point.x; // 乘以点的坐标
y += tmp * point.y;
if(point.bestCluster == this) add(point);
}
x /= mem;
y /= mem; //除以总重量
//之后与kmeans相同
oldOrigins.Add(origins);
var n = new Point2D((float) x, (float) y) {color = origins.color};
var result = n.dist(origins);
origins = n;
return result;
}
}
}
参考:
FCM聚类与K-means聚类的分析比较_Grape_o的博客-CSDN博客_fcm与kmeans的区别
聚类分析:k-means和层次聚类 - 简书 (jianshu.com)
Python--Kmeans和FCM聚类效果对比(对图像与数据处理)_GlassySky的博客-CSDN博客