#include<iostream>此肢此
#include<math.h>
#include<stdlib.h>
#include<stdio.h>
using namespace std
int N //数据个数
int K //集合个数
int *CenterIndex//质心索引集合,即属于第几个参考点
double *Center //质心集合
double *CenterCopy
double *DataSet
double **Cluster
int *Top
/*算法描饥氏述:
C-Fuzzy均值聚类算法采用的是给定类的个数K,将N个元素(对象)分配到K个类中去使得类内对象之间的相似性最大,而类之间的相似性最小 */
//函数声明部分
void InitData()
void InitCenter()
void CreateRandomArray(int n,int k,int *centerIndex)
void CopyCenter()
void UpdateCluster()
void UpdateCenter()
int GetIndex(double value,double *centerIndex)
void AddtoCluster(int index,double value)
void print()
bool IsEqual(double *center,double *centercopy)
int main()
{
int Flag=1
InitData()
while(Flag)//无限次循环
{
UpdateCluster()
UpdateCenter()
if(IsEqual(Center,CenterCopy))
{
Flag=0
}
else
{
CopyCenter()
}
}
print()
getchar()
system("pause")
}
void InitData()
{
int i=0
int a
cout<<"请输入数据元素的个数: "
cin>>N
cout<<"请输入分类数: "
cin>>K
if(K>N)
{
return
}
CenterIndex =new int [sizeof(int)]
Center =new double [sizeof(double)*K]
CenterCopy =new double [sizeof(double)*K]
DataSet =new double [sizeof(double)*N]
Cluster =new double* [sizeof(double*)*K]
Top =new int [sizeof(int)*K]
//初始化K个类的集合
for(i=0i<Ki++)
{
Cluster[i]=new double [sizeof(double)*N]
Top[i]=0
}
cout<<"请输入数据"<<endl
for(i=0i<Ni++)
{
cin>>a
DataSet[i]=a
}
//初始化质心集合
InitCenter()
UpdateCluster()
}
void InitCenter()//初始化中心点（参照点）
{
int i=0
//产生随即的K个<N的不同的序列
CreateRandomArray(N,K,CenterIndex)
for(i=0i<Ki++)
{
Center[i]=DataSet[CenterIndex[i]]
}
CopyCenter()
}
void CreateRandomArray(int n,int k,int *centerIndex)//产生可以随输出控制的 k与n （可舍弃）
{
int i=0,j=0
for(i=0i<Ki++)
{
int a=rand()%n
for(j=0j<ij++)
{
if(centerIndex[j]==a)
break
}
if(j>=i)
{
centerIndex[i]=a
}
else
{
i--
}
}
}
void CopyCenter()//将旧的中心点保留以作森迅比较
{
int i=0
for(i=0i<Ki++)
{
CenterCopy[i]=Center[i]
}
}
void UpdateCluster()//
{
int i=0
int tindex
for(i<Ki++)
{
Top[i]=0
}
for(i=0i<Ni++)
{
tindex=GetIndex(DataSet[i],Center)
AddtoCluster(tindex,DataSet[i])
}
}
int GetIndex(double value,double *center)//判断属于哪个参照点
{
int i=0
int index=i
double min=fabs(value-center[i])
for(i=0i<Ki++)
{
if(fabs(value-center[i])<min)
{
index=i
min=fabs(value-center[i])
}
}
return index
}
void AddtoCluster(int index,double value)//统计每组个数（用于均值法求新的参照点）
{
Cluster[index][Top[index]]=value
Top[index]++
}
void UpdateCenter()//更新参照点
{
int i=0,j=0
double sum
for(i=0i<Ki++)
{
sum=0.0
for(j=0j<Top[i]j++)
{
sum+=Cluster[i][j]
}
if(Top[i]>0)
{
Center[i]=sum/Top[i]
}
}
}
bool IsEqual(double *center,double*centercopy)//
{
int i
for(i=0i<Ki++)
{
if(fabs(center[i]!=centercopy[i]))
return 0
}
return 1
}
void print()//
{
int i,j
cout<<"===================================="<<endl
for(i=0i<Ki++)
{
cout<<"第"<<i<<"组：质心为："<<Center[i]<<endl
cout<<"数据元素为:\n"
for(j=0j<Top[i]j++)
{
cout<<Cluster[i][j]<<'\t'
}
cout<<endl
}
}
function [center, U, obj_fcn] = FCMClust(data, cluster_n, options)% FCMClust.m 采用模糊C均值对数据集data聚为cluster_n类
%
% 用法：
% 1. [center,U,obj_fcn] = FCMClust(Data,N_cluster,options)
% 2. [center,U,obj_fcn] = FCMClust(Data,N_cluster)
%
% 输入：
% data---- nxm矩阵,表示n个样本,每个样本具有m的维特征值
让颤斗% N_cluster ---- 标量,表示聚合中心数目,即类别数
% options ---- 4x1矩阵，其中
% options(1): 隶属度矩阵U的指数，>1 (缺省值: 2.0)
% options(2): 最大迭代次数 (缺省值: 100)
坦磨% options(3): 隶属度最小变化量,迭代终止条件 (缺省值: 1e-5)
% options(4): 每次迭代是否输出信息标志(缺省值: 1)
% 输出：
% center ---- 聚类中心
% U ---- 隶属度矩阵
% obj_fcn ---- 目标函数值
% Example:
% data = rand(100,2)
% [center,U,obj_fcn] = FCMClust(data,2)
% plot(data(:,1), data(:,2),'o')
% hold on
% maxU = max(U)
% index1 = find(U(1,:) == maxU)
% index2 = find(U(2,:) == maxU)
% line(data(index1,1),data(index1,2),'marker','*','color','g')
% line(data(index2,1),data(index2,2),'marker','*','color','r')
% plot([center([1 2],1)],[center([1 2],2)],'*','color','k')
% hold off
if nargin ~= 2 &nargin ~= 3,%判断输入参数个数只能是2个或3个
error('Too many or too few input arguments!')
end
data_n = size(data, 1)% 求出data的第一维(rows)数,即样本个数
in_n = size(data, 2) % 求出data的第二维(columns)数，即特征值长度
% 默认 *** 作参数
default_options = [2% 隶属度矩阵U的指数
100 % 最大迭代次数
1e-5 % 隶属度最小变化量,迭代终止条件
1]% 每次迭代是否输出信息标志
if nargin == 2,
options = default_options
else %分析有options做参数时候的情况
% 如果输洞神入参数个数是二那么就调用默认的option
if length(options) <4, %如果用户给的opition数少于4个那么其他用默认值
tmp = default_options
tmp(1:length(options)) = options
options = tmp
end
% 返回options中是数的值为0(如NaN),不是数时为1
nan_index = find(isnan(options)==1)
%将denfault_options中对应位置的参数赋值给options中不是数的位置.
options(nan_index) = default_options(nan_index)
if options(1) <= 1, %如果模糊矩阵的指数小于等于1
error('The exponent should be greater than 1!')
end
end
%将options 中的分量分别赋值给四个变量
expo = options(1) % 隶属度矩阵U的指数
max_iter = options(2) % 最大迭代次数
min_impro = options(3) % 隶属度最小变化量,迭代终止条件
display = options(4) % 每次迭代是否输出信息标志
obj_fcn = zeros(max_iter, 1)% 初始化输出参数obj_fcn
U = initfcm(cluster_n, data_n)% 初始化模糊分配矩阵,使U满足列上相加为1,
% Main loop 主要循环
for i = 1:max_iter,
%在第k步循环中改变聚类中心ceneter,和分配函数U的隶属度值
[U, center, obj_fcn(i)] = stepfcm(data, U, cluster_n, expo)
if display,
fprintf('FCM:Iteration count = %d, obj. fcn = %f\n', i, obj_fcn(i))
end
% 终止条件判别
if i >1,
if abs(obj_fcn(i) - obj_fcn(i-1)) <min_impro,
break
end,
end
end
iter_n = i% 实际迭代次数
obj_fcn(iter_n+1:max_iter) = []
% 子函数
function U = initfcm(cluster_n, data_n)
% 初始化fcm的隶属度函数矩阵
% 输入:
% cluster_n ---- 聚类中心个数
% data_n ---- 样本点数
% 输出：
% U ---- 初始化的隶属度矩阵
U = rand(cluster_n, data_n)
col_sum = sum(U)
U = U./col_sum(ones(cluster_n, 1), :)
% 子函数
function [U_new, center, obj_fcn] = stepfcm(data, U, cluster_n, expo)
% 模糊C均值聚类时迭代的一步
% 输入：
% data---- nxm矩阵,表示n个样本,每个样本具有m的维特征值
% U ---- 隶属度矩阵
% cluster_n ---- 标量,表示聚合中心数目,即类别数
% expo---- 隶属度矩阵U的指数
% 输出：
% U_new ---- 迭代计算出的新的隶属度矩阵
% center ---- 迭代计算出的新的聚类中心
% obj_fcn ---- 目标函数值
mf = U.^expo % 隶属度矩阵进行指数运算结果
center = mf*data./((ones(size(data, 2), 1)*sum(mf'))')% 新聚类中心(5.4)式
dist = distfcm(center, data) % 计算距离矩阵
obj_fcn = sum(sum((dist.^2).*mf)) % 计算目标函数值 (5.1)式
tmp = dist.^(-2/(expo-1))
U_new = tmp./(ones(cluster_n, 1)*sum(tmp)) % 计算新的隶属度矩阵 (5.3)式
% 子函数
function out = distfcm(center, data)
% 计算样本点距离聚类中心的距离
% 输入：
% center ---- 聚类中心
% data ---- 样本点
% 输出：
% out---- 距离
out = zeros(size(center, 1), size(data, 1))
for k = 1:size(center, 1), % 对每一个聚类中心
% 每一次循环求得所有样本点到一个聚类中心的距离
out(k, :) = sqrt(sum(((data-ones(size(data,1),1)*center(k,:)).^2)',1))
end
所谓聚类算法是指将一堆没有标签的数据自动划分成几类的方法，属于无监督学习方法，这个方法要保证同一类的数据有相似的特征，如下图所示：
根据样本之间的距离或者说是相似性（亲疏性），把越相似、差异越小的样本聚成一类（簇），最后形成多个簇，使同一个簇内部的样本相似度高，不同簇之间差异性高。
相关概念：
K值 ：要得到的簇的个数
质心 ：每个簇的均值向量，即向量各维取平均即可
距离量度 ：常用欧几里得距离和余弦相似度（先标准化）
算法流程：
1、首先确定一个k值，即我们希望将数据集经悔野过聚类得到k个集合。
2、从数据集中随机选择k个数据点作为质心。
3、对数据集中每一个点，计算其与每一个质心的距离（如欧式距离），离哪个质心近，就划分到那个质心所属的集合。
4、把所有数据归好集合后，一共有k个集合。然后重新计算每个集合的质心。
5、如果新计算出来的质心和原来的质心之间的距离小于某一个设置的阈值（表示重新计算的质心的位置变化不大，趋于稳定，或者说收敛），我们可以认为聚类已经达到期望的结果，算法终止。
6、如果新质心和原质心距离变化很大，需要迭代3~5步骤。
K-Means采用的启发式方式很简单，用下面一组图就可以形象的描述:
上图a表达了初始的数据集，假设k=2。在图b中，我们随机选择了两个k类所对应的类别质心，即图中的红色质心和蓝色质心，然后分别求样本中所有点到这两个质心的距离，并标记每个样本的类别为和该样本距离最小的质心的类别，如图c所示，经过计算样本和红色质心和蓝色质心的距离，我们得到了所有样本点的第一轮迭代后的类别。此时我们对我们当前标记为红色和蓝色的点分别求其新的质心，如图d所示，新的红色质心和蓝色质心的位置已经发生了变动。图e和图f重复了我们在图c和图d的过程，即将所有点的类别标记为距离最近的质心的类别并求新的质心。最终我们得到的两个类别如图f。
坐标系中有六个点：
1、我们分两组，令K等于2，我们随机选择两个点：P1和P2
2、通过勾股定理计算剩余点分别到这两个点的距离：
3、第一次分组后结果：
组A：P1
组B：P2、P3、P4、P5、P6
4、分别计算A组和B组的质心：
A组质心还是P1=（0，0）
B组新的质心坐标为：P哥=（（1+3+8+9+10）/5，（2+1+8+10+7）/5）=（6.2，5.6）
5、再次计算每个点到质心的距离：
6、第二次分组结果：
组A：P1、P2、P3
组B：P4、P5、P6
7、再次计算质心：
P哥1=（1.33，1）
P哥2=（9，8.33）
8、再次计算每个点到质心的距离顷前亩：
9、第三次分组结果：
组A：P1、P2、P3
组B：P4、P5、P6
可以发现，第三次分组结果和第二次分组结果一致，说明已经收敛，聚类结束。
优点：
1、原理比较简单，实现也是很容易，收敛速度快。
2、当结果簇是密集的，而簇与簇之间区别明显时, 它的效果较好。
3、主要需要调参的参数仅仅是簇数k。
缺点：
1、K值需要预先给定，很多情况下K值的估计是非常困雀森难的。
2、K-Means算法对初始选取的质心点是敏感的，不同的随机种子点得到的聚类结果完全不同 ，对结果影响很大。
3、对噪音和异常点比较的敏感。用来检测异常值。
4、采用迭代方法， 可能只能得到局部的最优解，而无法得到全局的最优解 。
1、K值怎么定？
答：分几类主要取决于个人的经验与感觉，通常的做法是多尝试几个K值，看分成几类的结果更好解释，更符合分析目的等。或者可以把各种K值算出的 E 做比较，取最小的 E 的K值。
2、初始的K个质心怎么选？
答：最常用的方法是随机选，初始质心的选取对最终聚类结果有影响，因此算法一定要多执行几次，哪个结果更reasonable，就用哪个结果。 当然也有一些优化的方法，第一种是选择彼此距离最远的点，具体来说就是先选第一个点，然后选离第一个点最远的当第二个点，然后选第三个点，第三个点到第一、第二两点的距离之和最小，以此类推。第二种是先根据其他聚类算法（如层次聚类）得到聚类结果，从结果中每个分类选一个点。
3、关于离群值？
答：离群值就是远离整体的，非常异常、非常特殊的数据点，在聚类之前应该将这些“极大”“极小”之类的离群数据都去掉，否则会对于聚类的结果有影响。但是，离群值往往自身就很有分析的价值，可以把离群值单独作为一类来分析。
4、单位要一致！
答：比如X的单位是米，Y也是米，那么距离算出来的单位还是米，是有意义的。但是如果X是米，Y是吨，用距离公式计算就会出现“米的平方”加上“吨的平方”再开平方，最后算出的东西没有数学意义，这就有问题了。
5、标准化
答：如果数据中X整体都比较小，比如都是1到10之间的数，Y很大，比如都是1000以上的数，那么，在计算距离的时候Y起到的作用就比X大很多，X对于距离的影响几乎可以忽略，这也有问题。因此，如果K-Means聚类中选择欧几里德距离计算距离，数据集又出现了上面所述的情况，就一定要进行数据的标准化（normalization），即将数据按比例缩放，使之落入一个小的特定区间。
参考文章： 聚类、K-Means、例子、细节
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）