K-Means算法与FCM算法

一、前期准备
1.收集数据
2.描述数据集

二、原理分析
1.K-Means聚类法
这要从聚类开始说起：
聚类
①是对于静态数据分析的一门技术，在许多领域受到广泛应用，包括机器学习，数据挖掘，模式识别，图像分析以及生物信息。
②是把相似的对象通过静态分类的方法分成不同的组别或者更多的子集，让在同一个子集中的成员都有相似的一些属性。
③是其他分析算法的一个预处理步骤。
④是一种无监督的分类

聚类分析的算法分类：
划分法（分割式）、层次式（阶层式）、基于密度的方法、基于网格的方法、基于模型的方法

而K-means与fuzzy c-means算法都属于划分法

划分法概念：
给定一个有N个元组或者记录的数据集，构造K(K<N)个分组，每一个分组就代表一个聚类
Ⅰ每一个分组至少包含一个数据记录（在某些模糊聚类算法中可放宽）
Ⅱ 每一个数据记录属于且仅属于一个分组

对于给定的K，算法首先给出一个初始的分组方法，以后通过反复迭代的方式改变分组，使得每一次改进之后的分组方案都较前一次好。
好的标准：同一分组中的记录越近越好，不同分组中的记录越远越好。

K-Means聚类法：
----将N个数据依照其数据特征聚类为K类的聚类算法，K为一正整数----目标在于求各个数据与其对应聚类中心点距离平方和的最小值

Ji为第i个聚类的目标函数
K为聚类个数
Xj为第j个输入向量
Ci为第i个聚类中心
Wij为权重（Xj是否属于聚类Ci）

K-Means的归属矩阵

K-Means实现步骤：
1.随机选取k个数据点Ci，i=1,…,k,并将之分别视为各聚类的初始中心
2.决定各数据点所属之聚类，若数据点Xj判定属于第i聚类，则权重值Wij=1，否则为0

并满足(2)式
3.由(1)式计算目标函数J,如果J保持不变,代表结果已经稳定不变,则可结束此次迭代方法,否则进入步骤4

4.以(4)式更新聚类的中心点,回到步骤2
编程步骤:
1.设定聚类数目K,最大执行步骤tmax,一个很小的容忍误差ε>0;
2.决定聚类中心起始位置Cj(0),0<j<=K;
3.for t=1,…,tmax
a.for j=1,…,N
(i)计算各数据点到聚类中心的距离

(ii)计算数据点属于哪一聚类(隶属度矩阵)

b.更新聚类中心

c.计算收敛准则,若E(t)=||J(t) - J(t-1)||<ε成立则停止运算,否则进行下一轮迭代E(t)=||C(t) - C(t-1)||<ε

K-Means聚类分析是一种硬划分,它把每个待辨识的对象严格地划分到某个类中,具有非此即彼的性质

但在遇到蝴蝶型数据集时,K-Means聚类法则无法很好地解决

为了解决这样的情况,Dunn利用Ruspini提出的模糊划分的概念,将硬聚类推广到模糊聚类,1973年Jim Bezdek将Dunn的工作推广到基于模糊度m的一般Fuzzy C-Means形式,其目标函数定义如同K-Means聚类法,但其权重矩阵W不再是二元矩阵,而是应用了模糊理论的概念,使得每一输入向量不再仅归属于某一特定的聚类,而以其归属程度来表现属于各聚类的程度.

目标函数J如下:

Xj为数据点
Ci为聚类中心
N为数据个数
K为聚类中心点个数
m为权重指数
样本点Xj

Fuzzy C-means实现步骤:
1.设定分类个数k,设定初始权重矩阵,随机给定0~1之值,并满足权重总和为1如(6)式

2.如(7)式计算聚类中心点

3.由(5)式计算目标函数值,当目标函数值小于设定的容忍误差可结束迭代过程,否则执行步骤4
E(t)=||J(t) - J(t-1)||<ε
4.重新计算权重矩阵W如(8)式,并回到步骤2进行运算

编程步骤:
1.设定聚类数目K,最大执行步骤tmax,一个很小的容忍误差ε>0;
2.决定聚类中心起始位置Cj(0),0<j<=K;
3.for t=1,…,tmax
a.for j=1,…,N,计算隶属度矩阵

b.for i=1,…,K,更新聚类中心点

c.计算收敛准则,若E(t)=||J(t) - J(t-1)||<ε成立则停止运算,否则进行下一轮迭代E(t)=||C(t) - C(t-1)||<ε

使用K-Means聚类法与Fuzzy C-Means聚类法都需要事先确定聚类的数目两者最大的差异在于FCM聚类法加入了模糊的概念,使得每一输入向量不再仅隶属于某一特定的聚类,而是以隶属程度来表现.