fcm算法_fcm算法原理 - CSDN
精华内容
参与话题
  • 聚类之详解FCM算法原理及应用

    万次阅读 多人点赞 2015-07-27 17:02:47
    模糊C均值(Fuzzy C-means)算法简称FCM算法,是一种基于目标函数的模糊聚类算法,主要用于数据的聚类分析。理论成熟,应用广泛,是一种优秀的聚类算法。本文关于FCM算法的一些原理推导部分介绍等参考下...

    【之前】 该文的pdf清晰版已被整理上传,方便保存学习,下载地址:

    https://download.csdn.net/download/on2way/10394655

    ##(一)原理部分
    模糊C均值(Fuzzy C-means)算法简称FCM算法,是一种基于目标函数的模糊聚类算法,主要用于数据的聚类分析。理论成熟,应用广泛,是一种优秀的聚类算法。本文关于FCM算法的一些原理推导部分介绍等参考下面视频,加上自己的理解以文字的形式呈现出来,视频参考如下,比较长,看不懂的可以再去看看:

    FCM原理介绍

    FCM分析1
    FCM分析2
    FCM分析3

    首先介绍一下模糊这个概念,所谓模糊就是不确定,确定性的东西是什么那就是什么,而不确定性的东西就说很像什么。比如说把20岁作为年轻不年轻的标准,那么一个人21岁按照确定性的划分就属于不年轻,而我们印象中的观念是21岁也很年轻,这个时候可以模糊一下,认为21岁有0.9分像年轻,有0.1分像不年轻,这里0.9与0.1不是概率,而是一种相似的程度,把这种一个样本属于结果的这种相似的程度称为样本的隶属度,一般用u表示,表示一个样本相似于不同结果的一个程度指标。

    基于此,假定数据集为X,如果把这些数据划分成c类的话,那么对应的就有c个类中心为C,每个样本j属于某一类i的隶属度为uiju_{ij},那么定义一个FCM目标函数(1)及其约束条件(2)如下所示:

    J=i=1cj=1nuijmxjci2(1)J=\sum\limits_{i=1}^{c}\sum\limits_{j=1}^{n}u_{ij}^m||x_j-c_i||^2 \tag{1} i=1cuij=1,j=1,2...,n(2)\sum\limits_{i=1}^cu_{ij}=1,j=1,2...,n \tag{2}
    看一下目标函数(式1)而知,由相应样本的隶属度与该样本到各个类中心的距离相乘组成的,m是一个隶属度的因子,个人理解为属于样本的轻缓程度,就像x2x^2x3x^3这种一样。式(2)为约束条件,也就是一个样本属于所有类的隶属度之和要为1。观察式(1)可以发现,其中的变量有uijciu_{ij}、c_i,并且还有约束条件,那么如何求这个目标函数的极值呢?

    这里首先采用拉格朗日乘数法将约束条件拿到目标函数中去,前面加上系数,并把式(2)的所有j展开,那么式(1)变成下列所示:
    J=i=1cj=1nuijmxjci2+λ1(i=1cui11)+...+λj(i=1cuij1)+...+λn(i=ncuin1))(3)J=\sum\limits_{i=1}^{c}\sum\limits_{j=1}^{n}u_{ij}^m||x_j-c_i||^2+\lambda_1(\sum\limits_{i=1}^{c}u_{i1}-1)+...+\lambda_j(\sum\limits_{i=1}^{c}u_{ij}-1)+...+\lambda_n(\sum\limits_{i=n}^{c}u_{in}-1))\tag{3}
    现在要求该式的目标函数极值,那么分别对其中的变量uijciu_{ij}、c_i求导数,首先对uiju_{ij}求导。

    分析式(3),先对第一部分的两级求和的uiju_{ij}求导,对求和形式下如果直接求导不熟悉,可以把求和展开如下:
    \begin{bmatrix} u_{11}m||x_1-c_1||2 &\cdots &u_{1j}m||x_j-c_1||2 &\cdots & u_{1n}m||x_n-c_1||2 \\vdots &\vdots& \vdots& \vdots&\vdots\u_{i1}m||x_1-c_i||2 &\cdots &u_{ij}m||x_j-c_i||2 &\cdots & u_{in}m||x_n-c_i||2 \\vdots& \vdots& \vdots&\vdots&\vdots\u_{c1}m||x_1-c_c||2 &\cdots &u_{cj}m||x_j-c_c||2 &\cdots & u_{cn}m||x_n-c_c||2\end{bmatrix}
    这个矩阵要对uiju_{ij}求导,可以看到只有uiju_{ij}对应的uijmxjci2u_{ij}^m||x_j-c_i||^2保留,其他的所有项中因为不含有uiju_{ij},所以求导都为0。那么uijmxjci2u_{ij}^m||x_j-c_i||^2uiju_{ij}求导后就为mxjci2uijm1m||x_j-c_i||^2u_{ij}^{m-1}

    再来看后面那个对uiju_{ij}求导,同样把求和展开,再去除和uiju_{ij}不相关的(求导为0),那么只剩下这一项:λj(uij1)\lambda_j(u_{ij}-1),它对uiju_{ij}求导就是λj\lambda_j了。

    那么最终J对uiju_{ij}的求导结果并让其等于0就是:
    Juij=mxjci2uijm1+λj=0\frac{\partial J}{\partial u_{ij}}=m||x_j-c_i||^2u_{ij}^{m-1}+\lambda_j=0
    这个式子化简下,将uiju_{ij}解出来就是:
    uijm1=λjmxjci2 u_{ij}^{m-1}=\frac{-\lambda_j}{m||x_j-c_i||^2}
    进一步:
    $ u_{ij}=(\frac{-\lambda_j}{m||x_j-c_i||2}){\frac{1}{m-1}}=(\frac{-\lambda_j}{m}){\frac{1}{m-1}}(\frac{1}{||x_j-c_i||{(\frac{2}{m-1})}})\tag{4}$

    要解出uiju_{ij}则需要把λj\lambda_j去掉才行。这里重新使用公式(2)的约束条件,并把算出来的uiju_{ij}代入式(2)中有:

    1=i=1cuij=i=1c(λjm)1m1(1xjci(2m1))=(λjm)1m1i=1c(1xjci(2m1))1=\sum\limits_{i=1}^cu_{ij}=\sum\limits_{i=1}^c(\frac{-\lambda_j}{m})^{\frac{1}{m-1}}(\frac{1}{||x_j-c_i||^{(\frac{2}{m-1})}})=(\frac{-\lambda_j}{m})^{\frac{1}{m-1}} \sum\limits_{i=1}^c(\frac{1}{||x_j-c_i||^{(\frac{2}{m-1})}})

    这样就有(其中把符号i换成k):
    (λjm)1m1=(1i=1c(1xjci(2m1)))=(1k=1c(1xjck(2m1)))(\frac{-\lambda_j}{m})^{\frac{1}{m-1}} = (\frac{1}{\sum\limits_{i=1}^c(\frac{1}{||x_j-c_i||^{(\frac{2}{m-1})}})})=(\frac{1}{\sum\limits_{k=1}^c(\frac{1}{||x_j-c_k||^{(\frac{2}{m-1})}})})

    把这个重新代入到式(4)中有:
    $ u_{ij}=(\frac{1}{\sum\limits_{k=1}c(\frac{1}{||x_j-c_k||{(\frac{2}{m-1})}})})(\frac{1}{||x_j-c_i||{(\frac{2}{m-1})}})=(\frac{1}{\sum\limits_{k=1}c(\frac{{||x_j-c_i||{(\frac{2}{m-1})}})}{||x_j-c_k||{(\frac{2}{m-1})}})})=\frac{1}{\sum\limits_{k=1}c(\frac{||x_j-c_i||}{||x_j-c_k||}){(\frac{2}{m-1})}}\tag{5}$

    好了,式子(5)就是最终的$ u_{ij}$迭代公式。

    下面在来求J对cic_i的导数。由公式(2)可以看到只有i=1cj=1nuijmxjci2\sum\limits_{i=1}^{c}\sum\limits_{j=1}^{n}u_{ij}^m||x_j-c_i||^2这一部分里面含有cic_i,对其二级求和展开如前面所示的,那么它对cic_i的导数就是:
    Jci=j=1n(uijm2(xjci))=0\frac{\partial J}{\partial c_i}=\sum\limits_{j=1}^n(-u_{ij}^m*2*(x_j-c_i))=0
    即:
    j=1n(uijmci)=j=1n(xjuijm)\sum\limits_{j=1}^n(u_{ij}^mc_i)=\sum\limits_{j=1}^n(x_ju_{ij}^m) KaTeX parse error: \tag works only in display equations

    好了,公式(6)就是类中心的迭代公式。

    我们发现$ u_{ij}c_ifcm是相互关联的,彼此包含对方,有一个问题就是在fcm算法开始的时候既没有 u_{ij}也没有c_i便,那要怎么求解呢?很简单,程序开始的时候我们随便赋值给 u_{ij}或者c_i其中的一个,只要数值满足条件即可。然后就开始迭代,比如一般的都赋值给 u_{ij},那么有了 u_{ij}就可以计算c_i,然后有了c_i又可以计算 u_{ij}JJ,反反复复,在这个过程中还有一个目标函数J一直在变化,逐渐趋向稳定值。那么当J不在变化的时候就认为算法收敛到一个比较好的结了。可以看到 u_{ij}c_i$在目标函数J下似乎构成了一个正反馈一样,这一点很像EM算法,先E在M,有了M在E,在M直至达到最优。

    公式(5),(6)是算法的关键。现在来重新从宏观的角度来整体看看这两个公式,先看(5),在写一遍
    uij=1k=1c(xjcixjck)(2m1) u_{ij}=\frac{1}{\sum\limits_{k=1}^c(\frac{||x_j-c_i||}{||x_j-c_k||})^{(\frac{2}{m-1})}}
    假设看样本集中的样本1到各个类中心的隶属度,那么此时j=1,i从1到c类,此时上述式中分母里面求和中,分子就是这个点相对于某一类的类中心距离,而分母是这个点相对于所有类的类中心的距离求和,那么它们两相除表示什么,是不是表示这个点到某个类中心在这个点到所有类中心的距离和的比重。当求和里面的分子越小,是不是说就越接近于这个类,那么整体这个分数就越大,也就是对应的$ u_{ij}$就越大,表示越属于这个类,形象的图如下:
    这里写图片描述
    再来宏观看看公式(6),考虑当类i确定后,式(6)的分母求和其实是一个常数,那么式(6)可以写成:
    ci=j=1n(xjuijm)j=1nuijm=j=1nuijmj=1nuijmxjc_i=\frac{\sum\limits_{j=1}^n(x_ju_{ij}^m)}{\sum\limits_{j=1}^nu_{ij}^m}=\sum\limits_{j=1}^n\frac{u_{ij}^m}{\sum\limits_{j=1}^nu_{ij}^m}x_j
    这是类中心的更新法则。说这之前,首先让我们想想kmeans的类中心是怎么更新的,一般最简单的就是找到属于某一类的所有样本点,然后这一类的类中心就是这些样本点的平均值。那么FCM类中心怎么样了?看式子可以发现也是一个加权平均,类i确定后,首先将所有点到该类的隶属度u求和,然后对每个点,隶属度除以这个和就是所占的比重,乘以xjx_j就是这个点对于这个类i的贡献值了。画个形象的图如下:
    这里写图片描述
    由上述的宏观分析可知,这两个公式的迭代关系式是这样的也是可以理解的。
    ##(二)简单程序实现
    下面我们在matlab下用最基础的循环实现上述的式(5)与式(6)的FCM过程。首先,我们需要产生可用于FCM的数据,为了可视化方便,我们产生一个二维数据便于在坐标轴上显示,也就是每个样本由两个特征(或者x坐标与y坐标构成),生成100个这样的点,当然我们在人为改变一下,让这些点看起来至少属于不同的类。生成的点画出来如下:
    这里写图片描述
    那么我们说FCM算法的一般步骤为:
    (1)确定分类数,指数m的值,确定迭代次数(这是结束的条件,当然结束的条件可以有多种)。
    (2)初始化一个隶属度U(注意条件—和为1);
    (3)根据U计算聚类中心C;
    (4)这个时候可以计算目标函数J了
    (5)根据C返回去计算U,回到步骤3,一直循环直到结束。

    还需要说一点的是,当程序结束后,怎么去判断哪个点属于哪个类呢?在结束后,肯定有最后一次计算的U吧,对于每一个点,它属于各个类都会有一个u,那么找到其中的最大的u就认为这个点就属于这一类。基于此一个基础的程序如下:

    clc
    clear
    close all
    %% create samples:
    for i=1:100  
        x1(i) = rand()*5;      %人为保证差异性  
        y1(i) = rand()*5;    
        x2(i) = rand()*5 + 3; %人为保证差异性  
        y2(i) = rand()*5 + 3;
    end  
    x = [x1,x2];  
    y = [y1,y2];  
    data = [x;y];
    data = data';%一般数据每一行代表一个样本
    %plot(data(:,1),data(:,2),'*');  %画出来 
    %%---
    cluster_n = 2;%类别数
    iter = 50;%迭代次数
    m = 2;%指数
     
    num_data = size(data,1);%样本个数
    num_d = size(data,2);%样本维度
    %--初始化隶属度u,条件是每一列和为1
    U = rand(cluster_n,num_data);
    col_sum = sum(U);
    U = U./col_sum(ones(cluster_n,1),:);
    %% 循环--规定迭代次数作为结束条件
    for i = 1:iter
        %更新c
        for j = 1:cluster_n
            u_ij_m = U(j,:).^m;
            sum_u_ij = sum(u_ij_m);
            sum_1d = u_ij_m./sum_u_ij; 
            c(j,:) = u_ij_m*data./sum_u_ij;
        end
        %-计算目标函数J
        temp1 = zeros(cluster_n,num_data);
        for j = 1:cluster_n
            for k = 1:num_data
                temp1(j,k) = U(j,k)^m*(norm(data(k,:)-c(j,:)))^2;
            end
        end
        J(i) = sum(sum(temp1));
        %更新U
        for j = 1:cluster_n
            for k = 1:num_data
                sum1 = 0;
                for j1 = 1:cluster_n
                    temp = (norm(data(k,:)-c(j,:))/norm(data(k,:)-c(j1,:))).^(2/(m-1));
                    sum1 = sum1 + temp;
                end
                U(j,k) = 1./sum1;
            end
        end
    end
    figure;
    subplot(1,2,1),plot(J);
    [~,label] = max(U); %找到所属的类
    subplot(1,2,2);
    gscatter(data(:,1),data(:,2),label)
    

    得到结果如下:
    这里写图片描述
    分成3类看看:
    这里写图片描述
    基于此,结果还算正确。但是不得不说的一个问题就是算法的效率问题。为了和公式计算方式吻合,便于理解,这个程序里面有很多的循环操作,当分类数大一点,样本多一点的时候,这么写是很慢的,matlab号称矩阵实验室,所以要尽量少的使用循环,直接矩阵操作,那么上述的操作很多地方是可以把循环改成矩阵计算的,这里来介绍下matlab自带的fcm函数,就是使用矩阵运算来的。

    Matlab下help fcm既可以查阅相关用法们这里只是简单介绍,fcm函数输入需要2个或者3个参数,返回3个参数,如下:
    [center, U, obj_fcn] = fcm(data, cluster_n, options)
    对于输入:data数据集(注意每一行代表一个样本,列是样本个数)
    cluster_n为聚类数。
    options是可选参数,完整的options包括:
    OPTIONS(1): U的指数 (default: 2.0)
    OPTIONS(2): 最大迭代次数 (default: 100)
    OPTIONS(3): 目标函数的最小误差 (default: 1e-5)
    OPTIONS(4): 是否显示结果 (default: 1,显示)
    options都有默认值,自带的fcm结束的条件是OPTIONS(2)与OPTIONS(3)有一个满足就结束。
    对于输出:center聚类中心,U隶属度,obj_fcn目标函数值,这个迭代过程的每一代的J都在这里面存着。

    为了验证我们写的算法是否正确,用它的fcm去试试我们的数据(前提是数据一样),分成3类,画出它们的obj_fcn看看如下:
    这里写图片描述
    可以看到,虽然迭代的中间过程不一样,但是结果却是一样的。

    ##(三)进阶应用
    了解了fcm,再来看看它的几个应用。
    ###3.1)基于fcm的图像分割
    我们知道fcm主要用于聚类,而图像分割本身就是一个聚类的过程。所以可以用fcm去实现图像分割。

    这里以matlab下的灰度图像为例。灰度图像一图像的角度看是二维的,但是我们知道,决定图像的无非是里面的灰度值。而灰度值就是一个值,所以当我们把图像变成1维,也就是拉成一行或者一列的时候,其实灰度图像就是一个一维数据(上面那个例子生成的随机点是二维的)。

    那么我们就可以对这个一维数据进行聚类,待得到了分类结果后,再把这个结果返回到二维图像空间去显示就可以了。
    一个例子如下:

    clc
    clear
    close all
    img = double(imread('lena.jpg'));
    subplot(1,2,1),imshow(img,[]);
    data = img(:);
    %分成4类
    [center,U,obj_fcn] = fcm(data,4);
    [~,label] = max(U); %找到所属的类
    %变化到图像的大小
    img_new = reshape(label,size(img));
    subplot(1,2,2),imshow(img_new,[]);
    

    这里写图片描述
    需要注意的是label出来的是标签类别(1-4),并非真实的灰度,这里不过是把它显示出来就行了。

    ###3.2)实际数据的分类
    这里介绍一个常用于机器学习、模式划分的数据下载网站:
    http://archive.ics.uci.edu/ml/datasets.html

    这里面包含众多的数据库可用分类划分等。这里我们选择其中一个数据库:
    http://archive.ics.uci.edu/ml/datasets/seeds#

    这个数据库看介绍好像是关于种子分类的,里面共包含3类种子,每类种子通过什么x射线技术等等采集他们的特征,反正最后每个种子共有7个特征值来表示它(也就是说在数据里面相当于7维),每类种子又有70个样本,那么整个数据集就是210*7的样本集。从上面那个地方下载完样本集存为txt文件,并放到matlab工作目录下就可以使用了(注意看看下下来的数据有没有串位的,有的话要手动调整回去)。因为matlab只能显示低于3维的数据,这里有7维,我们现在在二维下显示其中的两维以及正确的分类结果看看什么情况:

    clc
    clear
    close all
    data = importdata('data.txt');
    %data中还有第8列,正确的标签列
    subplot(2,2,1);
    gscatter(data(:,1),data(:,6),data(:,8)),title('choose:1,6 列')
    subplot(2,2,2);
    gscatter(data(:,2),data(:,4),data(:,8)),title('choose:2,4 列')
    subplot(2,2,3);
    gscatter(data(:,3),data(:,5),data(:,8)),title('choose:3,5 列')
    subplot(2,2,4);
    gscatter(data(:,4),data(:,7),data(:,8)),title('choose:4,7 列')
    

    这里写图片描述
    组合有限,随便组合几种看看,发现似乎任意两个特征都可以把他们分开,当然还是有一些分不开的,其中最后一个选择特征4,7似乎很好的分开了。

    Ok,看过之后我们来试试fcm算法对其进行分类,并计算一下准确率,我们先把7个特征都用上看看:

    clc
    clear
    close all
    data = importdata('data.txt');
    %data中还有第8列,正确的标签列
    [center,U,obj_fcn] = fcm(data(:,1:7),3);
    [~,label] = max(U); %找到所属的类
    subplot(1,2,1);
    gscatter(data(:,4),data(:,7),data(:,8)),title('choose:4,7列,理论结果')
    % cal accuracy
    a_1 = size(find(label(1:70)==1),2);
    a_2 = size(find(label(1:70)==2),2);
    a_3 = size(find(label(1:70)==3),2);
    a = max([a_1,a_2,a_3]);
    b_1 = size(find(label(71:140)==1),2);
    b_2 = size(find(label(71:140)==2),2);
    b_3 = size(find(label(71:140)==3),2);
    b = max([b_1,b_2,b_3]);
    c_1 = size(find(label(141:210)==1),2);
    c_2 = size(find(label(141:210)==2),2);
    c_3 = size(find(label(141:210)==3),2);
    c = max([c_1,c_2,c_3]);
    accuracy = (a+b+c)/210;
    % plot answer
    subplot(1,2,2);
    gscatter(data(:,4),data(:,7),label),title(['实际结果,accuracy=',num2str(accuracy)])
    

    这里写图片描述
    这里选择以第1与6维的数据来可视化这个结果。可以看到准确率为0.89524。

    这就是用了所有特征来实验的,这与用哪个特征能到达更好的结果、怎么样吧特征进行处理下能达到更好的结果,这都是机器学习与分类领域在研究的事情。上面我们感觉特征4,7不错,那么当我们只用特征4与7去进行fcm会怎样呢?
    这里写图片描述
    好像并不是很好,想想只用特征4与7结果本来就是这样的,不好就对了,fcm是根据数据距离划分来的,所以结果就是这样。

    试了很多组特征,都没有超过0.89524的,那就所有特征都用上吧。其实这个准确率是可以提高的,我们看到这7个特征似乎有点重复有没有,如果我们把这7个特征采用pca降维到3,4个特征了再去fcm实验呢?可以去试试,有待实验…

    展开全文
  • FCM算法

    千次阅读 2020-02-10 13:26:06
    FCM算法 一、FCM简述 FCM算法是基于对目标函数的优化基础上的一种数据聚类方法。聚类结果是每一个数据点对聚类中心的隶属程度,该隶属程度用一个数值来表示。该算法允许同一数据属于多个不同的类。 FCM算法是一种无...

    FCM算法

    一、FCM简述

    FCM算法是基于对目标函数的优化基础上的一种数据聚类方法。聚类结果是每一个数据点对聚类中心的隶属程度,该隶属程度用一个数值来表示。该算法允许同一数据属于多个不同的类。
    FCM算法是一种无监督的模糊聚类方法,在算法实现过程中不需要人为的干预。
    这种算法的不足之处:首先,算法中需要设定一些参数,若参数的初始化选取的不合适,可能影响聚类结果的正确性;其次,当数据样本集合较大并且特征数目较多时,算法的实时性不太好。
    K-means也叫硬C均值聚类(HCM),而FCM是模糊C均值聚类,它是HCM的延伸与拓展,HCM与FCM最大的区别在于隶属函数(划分矩阵)的取值不同,HCM的隶属函数只取两个值:0和1,而FCM的隶属函数可以取[0,1]之间的任何数。K-means和FCM都需要事先给定聚类的类别数,而FCM还需要选取恰当的加权指数α,α的选取对结果有一定的影响,α属于[0,+∞)。

    二、算法描述

    1、目标函数

    在这里插入图片描述
    在这里插入图片描述

    2、算法优化

    对于FCM算法采用拉格朗日乘子法进行优化:
    在这里插入图片描述迭代公式:
    在这里插入图片描述

    3、算法流程

    在这里插入图片描述

    4、Matlab实现

    FCM1.m代码:

    clear all;
    close all;
    ClustringMethod = 'FCM_test';
    DataSet = input('input dataset:','s');
    %% 读入不同的数据集
    %% iris
    % data=importdata([DataSet,'iris_data.txt']);
    % id=importdata([DataSet,'iris_id.txt']);
    % [data_num,data_dim]=size(data);
    % id_label=min(id):max(id);
    % center_num=max(id)-min(id)+1;
    DataFile = ['D:\matlab_text\Data\',DataSet,'iris_data.txt'];
    data = load(DataFile);%data
    IdFile = ['D:\matlab_text\Data\',DataSet,'iris_id.txt'];
    id = load(IdFile);%id
    DataSet_name = 'iris';
    
    % 读取数据信息
    id_label = min(id):max(id);
    [data_num,data_dim] = size(data);
    center_num = max(id)-min(id)+1;
    %% 参数设置
    alpha=2;
    threshold=1e-6;
    loopnum = 100;
    %% 输出文件
    ResultDirection=['Result\',DataSet,'\',ClustringMethod,'\',DataSet_name];
    if ~exist(ResultDirection,'dir')
        mkdir(ResultDirection);
    end
    Resultfile = [ResultDirection,'\alpha',num2str(alpha),'_',DataSet_name,'.txt'];
    fp_result = fopen(Resultfile,'wt');
    %% 将数据归一化到[0,1],采用min_max方法
    data = (data-(ones(data_num,1)*min(data)))./(ones(data_num,1)*(max(data)-min(data)));
    % ***************************************************************************************
    % 避免陷入局部最优,重复计算100% ***************************************************************************************
    for loop = 1:loopnum
        U = zeros(data_num,center_num);
        C = zeros(center_num,data_dim);
        % 初始化聚类中心--根据类中心初始化
        for i = 1:center_num
            temp = find(id==id_label(i));
            C(i,:) = data(temp(ceil(rand(1,1)*length(temp))),:);
        end
        iteration = 0;
        objfunc_old=0;
        %% Start----------FCM
        while(1)
            % 根据初始化的C计算隶属度U
            % 计算数据到聚类中心的距离
            distance_C = zeros(center_num,data_num);
            for i = 1:center_num
                distance_C(i,:) = ((bsxfun(@minus,C(i,:),data)).^2)*ones(1,data_dim)';
            end
            U = 1./(bsxfun(@times,(distance_C').^(1/(alpha-1)),sum((distance_C').^(-1/(alpha-1)),2)));
            U(distance_C'==0)=1;
            % 计算目标函数
            objfunc=sum(sum((U.^alpha).*(distance_C')));
            % 判断迭代终止条件
            if (abs(objfunc-objfunc_old)<threshold)
                break;
            end
            objfunc_old = objfunc;
            iteration = iteration + 1;
            % 更新聚类中心C
            Um = U.^alpha;
            C = bsxfun(@times,(Um')*data,((sum(Um))').^(-1));
        end
        %% End----------FCM
        % 将输出的隶属度U转换成id形式
        [~,id_U] = max(U,[],2);
        id_U = id_U - 1;
        % Compute the ACC
        [ACC,id_U_result] = Function_ACC( center_num,data_num,id_U,id_label,id );
        % Compute the NMI
        NMI = Function_NMI( id_U_result,id );
        % Output the ITE
        ITE = iteration;
        % Calculate the average value of evaluation indexes
        ACC_max = max(ACC,ACC_max);
        ACC_average = ACC_average + ACC/loopnum;
        NMI_average = NMI_average + NMI/loopnum;
        ITE_average = ITE_average + ITE/loopnum;
    end
    %% Output final results to .txt
    fprintf(fp_result,'DataSet = %s\t',DataSet_name);
    fprintf(fp_result,'ACC_max = %f\t',ACC_max);
    fprintf(fp_result,'ACC_average = %f\t',ACC_average);
    fprintf(fp_result,'NMI_average = %f\t',NMI_average);
    fprintf(fp_result,'ITE_average = %f\n',ITE_average);
    %% Output final results to terminal
    fprintf('DataSet=%s\t ACC_max=%d\t ACC_average=%f\t NMI_average=%f\t ITE_average=%f\n',DataSet_name,ACC_max,ACC_average,NMI_average,ITE_average);

    Function_ACC代码:

    function [ accuracy_max,id_U_result ] = Function_ACC( center_num,data_num,id_U,id_label,id )
    accuracy_max = 0;
    % function_ACC 计算评价指标----准确率
    % 全排列
    id_permutation = perms(id_label);
    id_temp = zeros(data_num,factorial(center_num));
    for i = 1:factorial(center_num)
        for k = 1:center_num
            for j = 1:data_num
                if(id_U(j) == id_permutation(i,k))
                    id_temp(j,i)=id_label(k);
                end
            end
        end
    end
    %分别计算每一种排列组合下的准确率
    error = zeros(data_num,factorial(center_num));
    for i = 1:data_num
        error(i,:) = (abs(id_temp(i,:)-id(i))>0)*1;%错误数
    end
    accuracy = max((data_num-sum(error))/data_num);
    %得到准确率最高时的分类结果
    id_U_result = id_temp(:,find((data_num-sum(error))/data_num==accuracy));
    accuracy_max = max(accuracy,accuracy_max);
    end

    Function_NMI代码:

    function [ NMI ] = Function_NMI( id_new,id_real )
    % Function_NMI:hard clustering measure: normalized mutual information
    % [data_num,center_num]=size(U);
    data_num = length(id_real);
    center_num = max(id_real(:))-min(id_real(:))+1;
    id_label=min(id_real(:)):max(id_real(:));
    %% compute the number of each cluster
    Pn_id_new = zeros(1,center_num);
    Pn_id_real = zeros(1,center_num);
    P_id_new = zeros(1,center_num);
    P_id_real = zeros(1,center_num);
    for i = 1:center_num
        Pn_id_new(i) = length(find(id_new(:)==id_label(i)));
        Pn_id_real(i) = length(find(id_real(:)==id_label(i)));
        P_id_new(i) = length(find(id_new(:)==id_label(i)))/data_num;
        P_id_real(i) = length(find(id_real(:)==id_label(i)))/data_num;
    end
    %% compute entropy
    H_new = 0;
    H_real = 0;
    for i = 1:center_num
        H_new = H_new - P_id_new(i)*log2(P_id_new(i));
        H_real = H_real-P_id_real(i)*log2(P_id_real(i));    
    end
    %% compute the number of mutual information
    count_new_real=zeros(center_num,center_num);%同时隶属于Ri与Qj的数据点的个数
    for i = 1:center_num
        for j = 1:center_num
            for n = 1:data_num
                if ((id_new(n) == id_label(i)) && (id_real(n) == id_label(j)))
                    count_new_real(i,j) = count_new_real(i,j) + 1;
                end
            end
        end
    end
    P_new_real=count_new_real/data_num;
    NMI=0;
    for i=1:center_num
        for j=1:center_num
            if(P_new_real(i,j) ~= 0)
                NMI = NMI + P_new_real(i,j)*log2(P_new_real(i,j)/(P_id_new(i)*P_id_real(j)));
            end
        end
    end
    NMI = NMI/sqrt(H_new*H_real);
    end

    结果:
    在这里插入图片描述
    数据:
    iris

    三、参考文献

    1.认识FCM算法
    2.FCM算法的matlab程序
    3.FCM理论详解

    展开全文
  • FCM聚类算法介绍

    千次阅读 2018-03-23 17:06:29
    FCM聚类算法介绍FCM算法是一种基于划分的聚类算法,它的思想就是使得被划分到同一簇的对象之间相似度最大,而不同簇之间的相似度最小。模糊C均值算法是普通C均值算法的改进,普通C均值算法对于数据的划分是硬性的,...

    FCM聚类算法介绍

    FCM算法是一种基于划分的聚类算法,它的思想就是使得被划分到同一簇的对象之间相似度最大,而不同簇之间的相似度最小。模糊C均值算法是普通C均值算法的改进,普通C均值算法对于数据的划分是硬性的,而FCM则是一种柔性的模糊划分。在介绍FCM具体算法之前我们先介绍一些模糊集合的基本知识。

    1 模糊集基本知识

      首先说明隶属度函数的概念。隶属度函数是表示一个对象x隶属于集合A的程度的函数,通常记做μA(x),其自变量范围是所有可能属于集合A的对象(即集合A所在空间中的所有点),取值范围是[0,1],即0<=μA(x)<=1。μA(x)=1表示x完全隶属于集合A,相当于传统集合概念上的x∈A。一个定义在空间X={x}上的隶属度函数就定义了一个模糊集合A,或者叫定义在论域X={x}上的模糊子集。对于有限个对象x1,x2,……xn模糊集合可以表示为:

                  

         (6.1)

      有了模糊集合的概念,一个元素隶属于模糊集合就不是硬性的了,在聚类的问题中,可以把聚类生成的簇看成模糊集合,因此,每个样本点隶属于簇的隶属度就是[01]区间里面的值。

    2 K均值聚类算法(HCM,K-Means)介绍

      K均值聚类(K-Means),即众所周知的C均值聚类,已经应用到各种领域。它的核心思想如下:算法把n个向量xj(1,2…,n)分为c个组Gi(i=1,2,…,c),并求每组的聚类中心,使得非相似性(或距离)指标的价值函数(或目标函数)达到最小。当选择欧几里德距离为组j中向量xk与相应聚类中心ci间的非相似性指标时,价值函数可定义为:

          

             (6.2)

      这里是组i内的价值函数。这样Ji的值依赖于Gi的几何特性和ci的位置。

      一般来说,可用一个通用距离函数d(xk,ci)代替组I中的向量xk,则相应的总价值函数可表示为:

           

              (6.3)

      为简单起见,这里用欧几里德距离作为向量的非相似性指标,且总的价值函数表示为(6.2)式。

      划分过的组一般用一个c×n的二维隶属矩阵U来定义。如果第j个数据点xj属于组i,则U中的元素uij为1;否则,该元素取0。一旦确定聚类中心ci,可导出如下使式(6.2)最小uij:

     

           (6.4)

      重申一点,如果ci是xj的最近的聚类中心,那么xj属于组i。由于一个给定数据只能属于一个组,所以隶属矩阵U具有如下性质:

           

             (6.5)

    且         

                       (6.6)

      另一方面,如果固定uij则使(6.2)式最小的最佳聚类中心就是组I中所有向量的均值:        

                     (6.7)

      这里|Gi|Gi的规模或。

      为便于批模式运行,这里给出数据集xi(12…n)的K均值算法;该算法重复使用下列步骤,确定聚类中心ci和隶属矩阵U

      步骤1:初始化聚类中心ci,i=1,…,c。典型的做法是从所有数据点中任取c个点。

      步骤2:用式(6.4)确定隶属矩阵U

      步骤3:根据式(6.2)计算价值函数。如果它小于某个确定的阀值,或它相对上次价值函数质的改变量小于某个阀值,则算法停止。

      步骤4:根据式(6.5)修正聚类中心。返回步骤2

      该算法本身是迭代的,且不能确保它收敛于最优解。K均值算法的性能依赖于聚类中心的初始位置。所以,为了使它可取,要么用一些前端方法求好的初始聚类中心;要么每次用不同的初始聚类中心,将该算法运行多次。此外,上述算法仅仅是一种具有代表性的方法;我们还可以先初始化一个任意的隶属矩阵,然后再执行迭代过程。

      K均值算法也可以在线方式运行。这时,通过时间平均,导出相应的聚类中心和相应的组。即对于给定的数据点x,该算法求最近的聚类中心ci,并用下面公式进行修正:

             

                   (6.8)

      这种在线公式本质上嵌入了许多非监督学习神经元网络的学习法则。

    3   模糊C均值聚类

      模糊C均值聚类FCM),即众所周知的模糊ISODATA,是用隶属度确定每个数据点属于某个聚类的程度的一种聚类算法。1973年,Bezdek提出了该算法,作为早期硬C均值聚类(HCM)方法的一种改进。

      FCMn个向量xi(i=1,2,…,n)分为c个模糊组,并求每组的聚类中心,使得非相似性指标的价值函数达到最小。FCMHCM的主要区别在于FCM用模糊划分,使得每个给定数据点用值在01间的隶属度来确定其属于各个组的程度。与引入模糊划分相适应,隶属矩阵U允许有取值在01间的元素。不过,加上归一化规定,一个数据集的隶属度的和总等于1:         

                 (6.9)

      那么,FCM的价值函数(或目标函数)就是式(6.2)的一般化形式:   

              (6.10)

      这里uij介于01间;ci为模糊组I的聚类中心,dij=||ci-xj||为第I个聚类中心与第j个数据点间的欧几里德距离;且是一个加权指数。

      构造如下新的目标函数,可求得使(6.10)式达到最小值的必要条件:

       

            (6.11)

      这里lj,j=1n,是(6.9)式的n个约束式的拉格朗日乘子。对所有输入参量求导,使式(6.10)达到最小的必要条件为:

                            (6.12)

    和            

             (6.13)

      由上述两个必要条件,模糊C均值聚类算法是一个简单的迭代过程。在批处理方式运行时,FCM用下列步骤确定聚类中心ci和隶属矩阵U[1]

      步骤1:用值在01间的随机数初始化隶属矩阵U,使其满足式(6.9)中的约束条件

      步骤2:用式(6.12)计算c个聚类中心ci,i=1,…,c

      步骤3:根据式(6.10)计算价值函数。如果它小于某个确定的阀值,或它相对上次价值函数值的改变量小于某个阀值,则算法停止。

      步骤4:用(6.13)计算新的U矩阵。返回步骤2

      上述算法也可以先初始化聚类中心,然后再执行迭代过程。由于不能确保FCM收敛于一个最优解。算法的性能依赖于初始聚类中心。因此,我们要么用另外的快速算法确定初始聚类中心,要么每次用不同的初始聚类中心启动该算法,多次运行FCM

    4 FCM算法的应用

      通过上面的讨论,我们不难看出FCM算法需要两个参数一个是聚类数目C,另一个是参数m。一般来讲C要远远小于聚类样本的总个数,同时要保证C>1。对于m,它是一个控制算法的柔性的参数,如果m过大,则聚类效果会很次,而如果m过小则算法会接近HCM聚类算法。

      算法的输出是C个聚类中心点向量和C*N的一个模糊划分矩阵,这个矩阵表示的是每个样本点属于每个类的隶属度。根据这个划分矩阵按照模糊集合中的最大隶属原则就能够确定每个样本点归为哪个类。聚类中心表示的是每个类的平均特征,可以认为是这个类的代表点。

      从算法的推导过程中我们不难看出,算法对于满足正态分布的数据聚类效果会很好,另外,算法对孤立点是敏感的。

    展开全文
  • 详解FCM算法原理及应用

    万次阅读 2015-11-03 20:55:04
     ...本文关于FCM算法的一些原理推导部分介绍等参考下面视频,加上自己的理解以文字的形式呈现出来,视频参考如下,比较长,看不懂的可以再去看看: FCM原理介绍 FCM分析1 FCM分析2 FCM
    


    (一)原理部分

    模糊C均值(Fuzzy C-means)算法简称FCM算法,是一种基于目标函数的模糊聚类算法,主要用于数据的聚类分析。理论成熟,应用广泛,是一种优秀的聚类算法。本文关于FCM算法的一些原理推导部分介绍等参考下面视频,加上自己的理解以文字的形式呈现出来,视频参考如下,比较长,看不懂的可以再去看看:

    FCM原理介绍

    FCM分析1
    FCM分析2
    FCM分析3

    首先介绍一下模糊这个概念,所谓模糊就是不确定,确定性的东西是什么那就是什么,而不确定性的东西就说很像什么。比如说把20岁作为年轻不年轻的标准,那么一个人21岁按照确定性的划分就属于不年轻,而我们印象中的观念是21岁也很年轻,这个时候可以模糊一下,认为21岁有0.9分像年轻,有0.1分像不年轻,这里0.9与0.1不是概率,而是一种相似的程度,把这种一个样本属于结果的这种相似的程度称为样本的隶属度,一般用u表示,表示一个样本相似于不同结果的一个程度指标。

    基于此,假定数据集为X,如果把这些数据划分成c类的话,那么对应的就有c个类中心为C,每个样本j属于某一类i的隶属度为uij,那么定义一个FCM目标函数(1)及其约束条件(2)如下所示:

    J=i=1cj=1numij||xjci||2(1)
    i=1cuij=1,j=1,2...,n(2)

    看一下目标函数(式1)而知,由相应样本的隶属度与该样本到各个类中心的距离相乘组成的,m是一个隶属度的因子,个人理解为属于样本的轻缓程度,就像x2x3这种一样。式(2)为约束条件,也就是一个样本属于所有类的隶属度之和要为1。观察式(1)可以发现,其中的变量有uijci,并且还有约束条件,那么如何求这个目标函数的极值呢?

    这里首先采用拉格朗日乘数法将约束条件拿到目标函数中去,前面加上系数,并把式(2)的所有j展开,那么式(1)变成下列所示:

    J=i=1cj=1numij||xjci||2+λ1(i=1cui11)+...+λj(i=1cuij1)+...+λn(i=ncuin1))(3)

    现在要求该式的目标函数极值,那么分别对其中的变量uijci求导数,首先对uij求导。

    分析式(3),先对第一部分的两级求和的uij求导,对求和形式下如果直接求导不熟悉,可以把求和展开如下:

    um11||x1c1||2umi1||x1ci||2umc1||x1cc||2um1j||xjc1||2umij||xjci||2umcj||xjcc||2um1n||xnc1||2umin||xnci||2umcn||xncc||2

    这个矩阵要对uij求导,可以看到只有uij对应的umij||xjci||2保留,其他的所有项中因为不含有uij,所以求导都为0。那么umij||xjci||2uij求导后就为m||xjci||2um1ij

    再来看后面那个对uij求导,同样把求和展开,再去除和uij不相关的(求导为0),那么只剩下这一项:λj(uij1),它对uij求导就是λj了。

    那么最终J对uij的求导结果并让其等于0就是:

    Juij=m||xjci||2um1ij+λj=0

    这个式子化简下,将uij解出来就是:
    um1ij=λjm||xjci||2

    进一步:
    uij=(λjm||xjci||2)1m1=(λjm)1m1(1||xjci||(2m1))(4)

    要解出uij则需要把λj去掉才行。这里重新使用公式(2)的约束条件,并把算出来的uij代入式(2)中有:

    1=i=1cuij=i=1c(λjm)1m1(1||xjci||(2m1))=(λjm)1m1i=1c(1||xjci||(2m1))

    这样就有(其中把符号i换成k):
    (λjm)1m1=(1i=1c(1||xjci||(2m1)))=(1k=1c(1||xjck||(2m1)))

    把这个重新代入到式(4)中有:
    uij=(1k=1c(1||xjck||(2m1)))(1||xjci||(2m1))=(1k=1c(||xjci||(2m1))||xjck||(2m1)))=1k=1c(||xjci||||xjck||)(2m1)(5)

    好了,式子(5)就是最终的uij迭代公式。

    下面在来求J对ci的导数。由公式(2)可以看到只有i=1cj=1numij||xjci||2这一部分里面含有ci,对其二级求和展开如前面所示的,那么它对ci的导数就是:
    Jci=j=1n(umij2(xjci))=0
    即:
    j=1n(umijci)=j=1n(xjumij) ci=j=1n(xjumij)j=1numij(6)

    好了,公式(6)就是类中心的迭代公式。

    我们发现uijci是相互关联的,彼此包含对方,有一个问题就是在fcm算法开始的时候既没有uij也没有ci,那要怎么求解呢?很简单,程序开始的时候我们随便赋值给uij或者ci其中的一个,只要数值满足条件即可。然后就开始迭代,比如一般的都赋值给uij,那么有了uij就可以计算ci,然后有了ci又可以计算uij,反反复复,在这个过程中还有一个目标函数J一直在变化,逐渐趋向稳定值。那么当J不在变化的时候就认为算法收敛到一个比较好的结了。可以看到uijci在目标函数J下似乎构成了一个正反馈一样,这一点很像EM算法,先E在M,有了M在E,在M直至达到最优。

    公式(5),(6)是算法的关键。现在来重新从宏观的角度来整体看看这两个公式,先看(5),在写一遍

    uij=1k=1c(||xjci||||xjck||)(2m1)

    假设看样本集中的样本1到各个类中心的隶属度,那么此时j=1,i从1到c类,此时上述式中分母里面求和中,分子就是这个点相对于某一类的类中心距离,而分母是这个点相对于所有类的类中心的距离求和,那么它们两相除表示什么,是不是表示这个点到某个类中心在这个点到所有类中心的距离和的比重。当求和里面的分子越小,是不是说就越接近于这个类,那么整体这个分数就越大,也就是对应的uij就越大,表示越属于这个类,形象的图如下:
    这里写图片描述
    再来宏观看看公式(6),考虑当类i确定后,式(6)的分母求和其实是一个常数,那么式(6)可以写成:
    ci=j=1n(xjumij)j=1numij=j=1numijj=1numijxj

    这是类中心的更新法则。说这之前,首先让我们想想kmeans的类中心是怎么更新的,一般最简单的就是找到属于某一类的所有样本点,然后这一类的类中心就是这些样本点的平均值。那么FCM类中心怎么样了?看式子可以发现也是一个加权平均,类i确定后,首先将所有点到该类的隶属度u求和,然后对每个点,隶属度除以这个和就是所占的比重,乘以xj就是这个点对于这个类i的贡献值了。画个形象的图如下:
    这里写图片描述
    由上述的宏观分析可知,这两个公式的迭代关系式是这样的也是可以理解的。

    (二)简单程序实现

    下面我们在matlab下用最基础的循环实现上述的式(5)与式(6)的FCM过程。首先,我们需要产生可用于FCM的数据,为了可视化方便,我们产生一个二维数据便于在坐标轴上显示,也就是每个样本由两个特征(或者x坐标与y坐标构成),生成100个这样的点,当然我们在人为改变一下,让这些点看起来至少属于不同的类。生成的点画出来如下:
    这里写图片描述
    那么我们说FCM算法的一般步骤为:
    (1)确定分类数,指数m的值,确定迭代次数(这是结束的条件,当然结束的条件可以有多种)。
    (2)初始化一个隶属度U(注意条件—和为1);
    (3)根据U计算聚类中心C;
    (4)这个时候可以计算目标函数J了
    (5)根据C返回去计算U,回到步骤3,一直循环直到结束。

    还需要说一点的是,当程序结束后,怎么去判断哪个点属于哪个类呢?在结束后,肯定有最后一次计算的U吧,对于每一个点,它属于各个类都会有一个u,那么找到其中的最大的u就认为这个点就属于这一类。基于此一个基础的程序如下:

    clc
    clear
    close all
    %% create samples:
    for i=1:100  
        x1(i) = rand()*5;      %人为保证差异性  
        y1(i) = rand()*5;    
        x2(i) = rand()*5 + 3; %人为保证差异性  
        y2(i) = rand()*5 + 3;
    end  
    x = [x1,x2];  
    y = [y1,y2];  
    data = [x;y];
    data = data';%一般数据每一行代表一个样本
    %plot(data(:,1),data(:,2),'*');  %画出来 
    %%---
    cluster_n = 2;%类别数
    iter = 50;%迭代次数
    m = 2;%指数
    
    num_data = size(data,1);%样本个数
    num_d = size(data,2);%样本维度
    %--初始化隶属度u,条件是每一列和为1
    U = rand(cluster_n,num_data);
    col_sum = sum(U);
    U = U./col_sum(ones(cluster_n,1),:);
    %% 循环--规定迭代次数作为结束条件
    for i = 1:iter
        %更新c
        for j = 1:cluster_n
            u_ij_m = U(j,:).^m;
            sum_u_ij = sum(u_ij_m);
            sum_1d = u_ij_m./sum_u_ij; 
            c(j,:) = u_ij_m*data./sum_u_ij;
        end
        %-计算目标函数J
        temp1 = zeros(cluster_n,num_data);
        for j = 1:cluster_n
            for k = 1:num_data
                temp1(j,k) = U(j,k)^m*(norm(data(k,:)-c(j,:)))^2;
            end
        end
        J(i) = sum(sum(temp1));
        %更新U
        for j = 1:cluster_n
            for k = 1:num_data
                sum1 = 0;
                for j1 = 1:cluster_n
                    temp = (norm(data(k,:)-c(j,:))/norm(data(k,:)-c(j1,:))).^(2/(m-1));
                    sum1 = sum1 + temp;
                end
                U(j,k) = 1./sum1;
            end
        end
    end
    figure;
    subplot(1,2,1),plot(J);
    [~,label] = max(U); %找到所属的类
    subplot(1,2,2);
    gscatter(data(:,1),data(:,2),label)

    得到结果如下:
    这里写图片描述
    分成3类看看:
    这里写图片描述
    基于此,结果还算正确。但是不得不说的一个问题就是算法的效率问题。为了和公式计算方式吻合,便于理解,这个程序里面有很多的循环操作,当分类数大一点,样本多一点的时候,这么写是很慢的,matlab号称矩阵实验室,所以要尽量少的使用循环,直接矩阵操作,那么上述的操作很多地方是可以把循环改成矩阵计算的,这里来介绍下matlab自带的fcm函数,就是使用矩阵运算来的。

    Matlab下help fcm既可以查阅相关用法们这里只是简单介绍,fcm函数输入需要2个或者3个参数,返回3个参数,如下:
    [center, U, obj_fcn] = fcm(data, cluster_n, options)
    对于输入
    :data数据集(注意每一行代表一个样本,列是样本个数)
    cluster_n为聚类数。
    options是可选参数,完整的options包括:
    OPTIONS(1): U的指数 (default: 2.0)
    OPTIONS(2): 最大迭代次数 (default: 100)
    OPTIONS(3): 目标函数的最小误差 (default: 1e-5)
    OPTIONS(4): 是否显示结果 (default: 1,显示)
    options都有默认值,自带的fcm结束的条件是OPTIONS(2)与OPTIONS(3)有一个满足就结束。
    对于输出:center聚类中心,U隶属度,obj_fcn目标函数值,这个迭代过程的每一代的J都在这里面存着。

    为了验证我们写的算法是否正确,用它的fcm去试试我们的数据(前提是数据一样),分成3类,画出它们的obj_fcn看看如下:
    这里写图片描述
    可以看到,虽然迭代的中间过程不一样,但是结果却是一样的。

    (三)进阶应用

    了解了fcm,再来看看它的几个应用。

    3.1)基于fcm的图像分割

    我们知道fcm主要用于聚类,而图像分割本身就是一个聚类的过程。所以可以用fcm去实现图像分割。

    这里以matlab下的灰度图像为例。灰度图像一图像的角度看是二维的,但是我们知道,决定图像的无非是里面的灰度值。而灰度值就是一个值,所以当我们把图像变成1维,也就是拉成一行或者一列的时候,其实灰度图像就是一个一维数据(上面那个例子生成的随机点是二维的)。

    那么我们就可以对这个一维数据进行聚类,待得到了分类结果后,再把这个结果返回到二维图像空间去显示就可以了。
    一个例子如下:

    clc
    clear
    close all
    img = double(imread('lena.jpg'));
    subplot(1,2,1),imshow(img,[]);
    data = img(:);
    %分4类
    [center,U,obj_fcn] = fcm(data,4);
    [~,label] = max(U); %找到所属的类
    %变化到图像的大小
    img_new = reshape(label,size(img));
    subplot(1,2,2),imshow(img_new,[]);

    这里写图片描述
    需要注意的是label出来的是标签类别(1-4),并非真实的灰度,这里不过是把它显示出来就行了。

    3.2)实际数据的分类

    这里介绍一个常用于机器学习、模式划分的数据下载网站:
    http://archive.ics.uci.edu/ml/datasets.html

    这里面包含众多的数据库可用分类划分等。这里我们选择其中一个数据库:
    http://archive.ics.uci.edu/ml/datasets/seeds#

    这个数据库看介绍好像是关于种子分类的,里面共包含3类种子,每类种子通过什么x射线技术等等采集他们的特征,反正最后每个种子共有7个特征值来表示它(也就是说在数据里面相当于7维),每类种子又有70个样本,那么整个数据集就是210*7的样本集。从上面那个地方下载完样本集存为txt文件,并放到matlab工作目录下就可以使用了(注意看看下下来的数据有没有串位的,有的话要手动调整回去)。因为matlab只能显示低于3维的数据,这里有7维,我们现在在二维下显示其中的两维以及正确的分类结果看看什么情况:

    clc
    clear
    close all
    data = importdata('data.txt');
    %data中还有第8列,正确的标签列
    subplot(2,2,1);
    gscatter(data(:,1),data(:,6),data(:,8)),title('choose:1,6 列')
    subplot(2,2,2);
    gscatter(data(:,2),data(:,4),data(:,8)),title('choose:2,4 列')
    subplot(2,2,3);
    gscatter(data(:,3),data(:,5),data(:,8)),title('choose:3,5 列')
    subplot(2,2,4);
    gscatter(data(:,4),data(:,7),data(:,8)),title('choose:4,7 列')

    这里写图片描述
    组合有限,随便组合几种看看,发现似乎任意两个特征都可以把他们分开,当然还是有一些分不开的,其中最后一个选择特征4,7似乎很好的分开了。

    Ok,看过之后我们来试试fcm算法对其进行分类,并计算一下准确率,我们先把7个特征都用上看看:

    clc
    clear
    close all
    data = importdata('data.txt');
    %data中还有第8列,正确的标签列
    [center,U,obj_fcn] = fcm(data(:,1:7),3);
    [~,label] = max(U); %找到所属的类
    subplot(1,2,1);
    gscatter(data(:,4),data(:,7),data(:,8)),title('choose:4,7列,理论结果')
    % cal accuracy
    a_1 = size(find(label(1:70)==1),2);
    a_2 = size(find(label(1:70)==2),2);
    a_3 = size(find(label(1:70)==3),2);
    a = max([a_1,a_2,a_3]);
    b_1 = size(find(label(71:140)==1),2);
    b_2 = size(find(label(71:140)==2),2);
    b_3 = size(find(label(71:140)==3),2);
    b = max([b_1,b_2,b_3]);
    c_1 = size(find(label(141:210)==1),2);
    c_2 = size(find(label(141:210)==2),2);
    c_3 = size(find(label(141:210)==3),2);
    c = max([c_1,c_2,c_3]);
    accuracy = (a+b+c)/210;
    % plot answer
    subplot(1,2,2);
    gscatter(data(:,4),data(:,7),label),title(['实际结果,accuracy=',num2str(accuracy)])

    这里写图片描述
    这里选择以第1与6维的数据来可视化这个结果。可以看到准确率为0.89524。

    这就是用了所有特征来实验的,这与用哪个特征能到达更好的结果、怎么样吧特征进行处理下能达到更好的结果,这都是机器学习与分类领域在研究的事情。上面我们感觉特征4,7不错,那么当我们只用特征4与7去进行fcm会怎样呢?
    这里写图片描述
    好像并不是很好,想想只用特征4与7结果本来就是这样的,不好就对了,fcm是根据数据距离划分来的,所以结果就是这样。

    试了很多组特征,都没有超过0.89524的,那就所有特征都用上吧。其实这个准确率是可以提高的,我们看到这7个特征似乎有点重复有没有,如果我们把这7个特征采用pca降维到3,4个特征了再去fcm实验呢?

    展开全文
  • Fuzzy c-means (FCM)聚类算法

    万次阅读 2011-01-02 18:14:00
    算法原理 允许同一数据属于多个不同的类。该算法(developed by Dunn in 1973 and improved by Bezdek in 1981)经常用于模式识别,基于最小化
  • FCM聚类算法(模糊C均值算法

    千次阅读 2017-10-21 20:56:51
    FCM算法是一种基于划分的聚类算法,它的思想就是使得被划分到同一簇的对象之间相似度最大,而不同簇之间的相似度最小。模糊C均值算法是普通C均值算法的改进,普通C均值算法对于数据的划分是硬性的,而FCM则是一种...
  • 经典fcm算法程序+详细解释

    热门讨论 2011-05-12 13:23:50
    传统的fcm算法源程序,带有详细程序解释哦
  • FCM 算法

    2017-04-11 19:29:23
    FCM算法概述
  • FCM算法理论及其Python实现

    千次阅读 2019-03-05 15:00:25
    FCM算法 全名为Fuzzy C-Means,是一种聚类算法。 Fuzzy c-means (FCM) is a method of clustering which allows one piece of data to belong to two or more clusters. This method (developed by Dunn in 1973...
  • FCM算法与K-means 算法

    千次阅读 2019-10-27 13:31:42
    FCM算法 一.原理介绍 模糊C均值(Fuzzy C-means)算法简称FCM算法,是一种基于目标函数的模糊聚类算法,主要用于数据的聚类分析。理论成熟,应用广泛,是一种优秀的聚类算法。 首先介绍一下模糊这个概念,所谓...
  • FCM算法研究(一)

    万次阅读 2016-06-27 11:25:53
    FCM算法来源 聚类方法是一种研究数据结构的推导工具,可用于无监督模式识别技术、数据挖掘技术等。一般将聚类分为层次聚类和划分聚类。层次聚类算法产生一个嵌套聚类的层次,算法最多包含N步,在第t步,执行的操作...
  • FCM算法属于一种聚类算法,文件中写出了FCM算法在matlab中的程序代码
  • FCM算法推导过程

    2020-02-22 22:46:43
    最近毕业,然后可能用到FCM,找了挺多博客论文,更多的是关于用法没有推导过程,于是自己总结写一篇详细版尽量小白也能看懂的fcm推导过程,加深对算法的理解。标题或内容可能会挺暴力,个人习惯问题哈哈哈。如果写的...
  • 机器学习笔记-FCM算法python实现

    万次阅读 2016-06-08 21:56:56
    FCM算法是一种重叠聚类算法,它计算数据集中每个数据点与分类的匹配度,近日写个python程序重温了一下FCM算法。 一、算法代码 给定同维向量数据集合points,数目为n,将其聚为C类,m为权重值,u为初始匹配度矩阵...
  • fcm算法的MATLAB实现

    万次阅读 多人点赞 2017-11-27 17:59:33
    **fcm算法**分析:1.算法中包含的参数: a.模糊因子expo(expo&amp;amp;amp;amp;amp;gt;1) b.最大迭代次数max_t c.迭代终止条件ε2.算法中包含的过程: a.目标函数 b.欧式距离 c.隶属矩阵 d.聚类...
  • matlab实现FCM算法

    千次阅读 2019-05-23 21:15:04
    % author:wangjunzuo % date:2019/5/21 % fuction:fcm algrithmn load data load label maxgen = 100; %?????? m = 2; %2?? threshold = 10e-1000; %????? cluster_n = 3; %???? %%%%%%%%%...
  • 代码实现了基于遗传算法的模糊c均值算法,用于改进FCM当中的局部收敛问题,以达到全局最优。
  • FCM算法实现Python(简洁版)

    千次阅读 2019-04-17 17:46:11
    FCM算法 全名为Fuzzy C-Means,是一种聚类算法。 Fuzzy c-means (FCM) is a method of clustering which allows one piece of data to belong to two or more clusters. This method (developed by Dunn in 1973...
  • 模糊 C 均值(Fuzzy C-means)算法简称 FCM 算法,是一种基于目标函数的模糊聚类算法,主要用于数据的聚类分析。 限于篇幅和数学公式的表达,笔者誊写了一篇文档用于介绍FCM的数学推导,这篇推导主要参考on2way的...
  • FCM算法原理及matlab实现

    万次阅读 2016-12-20 14:58:07
    (一)FCM算法原理Fuzzy c-means (FCM) is a clustering method that allows each data point to belong to multiple clusters with varying degrees of membership.FCM is based on the minimization of the ...
1 2 3 4 5 ... 20
收藏数 1,389
精华内容 555
关键字:

fcm算法