精华内容
参与话题
问答
  • fcm聚类算法,文献,hd不要下载,可以看看,好好看看fcm聚类算法fcm聚类算法fcm聚类算法fcm聚类算法fcm聚类算法fcm聚类算法
  • 聚类之详解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理论详解

    展开全文
  • 代码实现了基于遗传算法的模糊c均值算法,用于改进FCM当中的局部收敛问题,以达到全局最优。
  • FCM 算法

    2017-04-11 19:29:23
    FCM算法概述

    一 FCM算法概述

     FCM算法的全称是模糊C均值聚类算法,和K-means算法同属于聚类算法,但却有着本质的区别,就其命名而言,模糊二字无疑是该算法的重点,下面就先简单介绍一下:
    
    1. 隶属度和模糊集

        隶属度函数用来描述元素x属于一个集合B的程度,假定为UB(x),其中x为B中的任意元素,UB(x)的取值范围为[0,1]。在隶属度函数的基础上,称空间上X={x}上的隶属度函数为一个模糊集合。

    2. 模糊聚类分析

        传统的聚类分析是把每个元素严格的划分到一个类中,属于硬划分。模糊聚类分析将聚类生成的每个簇均看做模糊集合,通过隶属度来确定聚类关系,是一种柔性划分,得到元素属于各个簇的不确定性程度,使得聚类结果更加准确灵活,因此,模糊聚类分析逐渐成为聚类分析的主流。

    3.FCM

    FCM算法是将N个L维向量分为C个模糊组,通过迭代不断更新隶属度以及聚类中心,最小化目标函数对数据进行聚类。
    

    其中,目标函数为:
    这里写图片描述
    约束条件为:
    这里写图片描述

    根据隶属度的非负性,有
    这里写图片描述

    这里,m指的是模糊加权系数,它的值大于1;d(xi,vc)表示的是第i个数据点与第c个聚类中心的欧式距离;uic是隶属度矩阵中的元素,且[0,1];vc是对应于每个聚类的聚类中心。

    为了求含有约束条件的目标函数的极值,引入拉格朗日因子构造新的目标函数:
    这里写图片描述
    对于目标函数求极值的最优化条件如下:
    这里写图片描述

    从而得到隶属度和聚类中心的计算公式为:
    这里写图片描述

    根据上述公式不断迭代求出满足条件的隶属度以及聚类中心。具体的FCM算法步骤如下:

    首先,给定一个由N个L维向量组成的数据集X以及所要分得的类别个数C,自定义隶属度矩阵

    (1)设定类别的个数C和模糊系数m;

    (2)‚初始化隶属度矩阵且满足公式(2)中的归一化条件;

    (3)根据公式(5)计算聚类中心;

    (4)根据公式(4)更新隶属度矩阵;

    (5)根据矩阵范数比较迭代的隶属度矩阵,如果这里写图片描述,迭代停止,否则返回(3)。

    二 MATLAB实现

    根据上述公式及步骤,采用MATLAB实现,具体如下:

    (1)选取UCI数据库中的wine数据实现,代码:

    clear all
    clc;
    %% 导入数据
    load wine.txt;
    cluster_n=6;
    
    data = wine;
    data(:,1) = [];
    data(:,size(data,2)) = [];
    data_n = size(data, 1); %数据的个数 
    in_n = size(data, 2);% 数据维数
    
    %% 定义变量
    default_options = [10;    % 隶属度函数的幂次方
            300;    % 最大迭代次数
            1e-5;    %步长
            1];    % 判定条件
    
    options = default_options;
    expo = options(1);        % Exponent for U 隶属度函数的幂次方
    max_iter = options(2);        % Max. iteration 最大迭代次数
    min_impro = options(3);        % Min. improvement  最小进化步长
    display = options(4);        % Display info or not 显示信息与否
    obj_fcn = zeros(max_iter, 1);    % Array for objective function
    
    tic
    %% 初始化隶属度矩阵并归一
    U = rand(cluster_n, data_n); %rand()产生随机矩阵 
    col_sum = sum(U);
    U = U./col_sum(ones(cluster_n, 1), :);%归一化
    
    %% 开始迭代
    for i = 1:max_iter,%迭代次数控制
        tic
        mf = U.^expo;      % MF matrix after exponential modification
        center = mf*data./((ones(size(data, 2), 1)*sum((mf')))'); % 建立新的聚类中心
    
           out = zeros(size(center, 1), size(data, 1));  %每个点到每个中心的距离,行数为中心数
    
            if size(center, 2) > 1,%样本的维数大于一执行以下程序
                for k = 1:size(center, 1),%给K赋值
                    abc = ((data-ones(size(data,1),1) * center(k,:)).^2)';
                      out(k, :) = sqrt(sum(abc));%得到欧氏距离
                end
           else    % 1-D data
                for k = 1:size(center, 1),
                      out(k, :) = abs(center(k)-data)';
                end
            end
    
        obj_fcn(i) = sum(sum((out.^2).*mf));  % 目标函数
        tmp = out.^(-2/(expo-1));      % 根据新的隶属度矩阵求解公式求出
        U= tmp./(ones(cluster_n, 1)*sum(tmp));  % 新的隶属度矩阵
    
        if display, 
            fprintf('Iteration count = %d, obj. fcn = %f\n', i, obj_fcn(i));
            %输出迭代次数和函数的结果
        end
        % check termination condition
        if i > 1,  %进化步长控制
            if abs(obj_fcn(i) - obj_fcn(i-1)) < min_impro, break; end,
        end
        toc
    end
    toc
    
    plot(U(1,:),'-ro');
    grid on
    hold on
    plot(U(2,:),'-g*');
    plot(U(3,:),'-b+');
    
    ylabel('Membership degrees')
    legend('FCM1','FCM2','FCM3','location','northeast');
    
    toc

    结果如下:
    这里写图片描述
    (2)选取一张MRI图像,进行图像分割,代码如下:

    clear all 
    clc;
    
    a=imread('MRI.jpg');
    I=imnoise(a,'salt & pepper',0.05);
    figure(1);           
     imshow(I);title('加噪图像');
    
    [height,width,c]=size(a);
    if c~=1
        a=rgb2gray(a);
    end
    
    a=double(a);
    [row,column]=size(a); 
    data = a(:);
    data_n = size(data,1);
    
    cluster_num = 4;
    default_options = [2.0;    % 隶属度函数的幂次方
            300;    % 最大迭代次数
            1e-5;    %步长
            1];    % 判定条件
    
    options = default_options;
    
    
    expo = options(1);        % Exponent for U 隶属度函数的幂次方
    max_iter = options(2);        % Max. iteration 最大迭代次数
    min_impro = options(3);        % Min. improvement  最小进化步长
    display = options(4);        % Display info or not 显示信息与否
    
    obj_fcn = zeros(max_iter, 1);    % Array for objective function
    membership = zeros(height,width,cluster_num);
    center = zeros(cluster_num,1);
    
    tic
    % 初始化隶属度并归一
    for i=1:height 
        for j=1:width
            member_sum=0;
            for k=1:cluster_num
                membership(i,j,k)=rand();
                member_sum = member_sum + membership(i,j,k);
            end        
            for p =1:cluster_num
                membership(i,j,p) = membership(i,j,p) / member_sum;
            end
        end
    end
    
    tic
    for i = 1:max_iter,%迭代次数控制
        mf = membership.^expo;     
        %%%%%%%%建立聚类中心
        for m = 1:cluster_num
            to = 0;
            tp =0;
            for j = 1:height
                for t = 1:width
                    to = to + membership(j,t,m) * a(j,t);
                    tp = tp + membership(j,t,m);
                end
            end
            center(m,1) = to / tp; 
        end
    
        %%%%%%%得到欧式距离以及目标函数
        out = zeros(height,width,cluster_num);
        for m =1:height
            for j =1:width
                for t = 1:cluster_num
                    out(m,j,t) = abs(a(m,j) - center(t,1));
                    obj_fcn(i) = obj_fcn(i) + (membership(m,j,t).^expo) * (out(m,j,t).^2);
                end
            end
        end
    
        for m = 1:height
            for j = 1:width
                for r = 1:cluster_num
                    top =0;
                    for t = 1:cluster_num
                        top = top + (out(m,j,r) / out(m,j,t)).^(expo - 1);
                    end
                    membership(m,j,r) = 1 / top;
                end
            end
        end
    
        %%%%%%归一化隶属度
        for m=1:height 
            for j = 1:width
                member_sum = 0;
                for k = 1:cluster_num
                    member_sum = member_sum + membership(m,j,k);
                end
                for p = 1:cluster_num
                    membership(m,j,p) = membership(m,j,p) / member_sum;
                end
            end
        end
    
         if display, 
            fprintf('Iteration count = %d, obj. fcn = %f\n', i, obj_fcn(i));
            %输出迭代次数和函数的结果
        end
        % check termination condition
        if i > 1,  %进化步长控制
            if abs(obj_fcn(i) - obj_fcn(i-1)) < min_impro, break; end,
        end
    end
    toc
    
    %%%%%%证得如自定义图像中的MCR不能计算,故在此继续尝试直接用newing和A相比较
    
    A = ones(height,width,1);
    for i = 1:height
        for j = 1:width
            if (fix(a(i,j) / 85) == 1)
                A(i,j,1) = 2;
            end
            if (fix(a(i,j) / 85) == 2)
                A(i,j,1) = 3;
            end
            if (fix(a(i,j,1) / 85) == 3)
                A(i,j,1) = 4;
            end
        end
    end    
    A = reshape(A,1,data_n);
    
      newing = zeros(row,column);
    for i=1:row
        for j=1:column         
            maxmembership=membership(i,j,1);
            index=1;
            for k=2:cluster_num            
                if(membership(i,j,k)>maxmembership)
                    maxmembership=membership(i,j,k);
                    index=k;
                end
            end
            newing(i,j) = round(255 * (1-(index-1)/(cluster_num-1)));
        end 
    end
    
    B = reshape(newing,1,data_n);
    b = fix((max(B) - B(1,1)) / cluster_num);
    for i = 2:data_n
        if B(1,i) == B(1,1)
            B(1,i) = 1;
        elseif (fix(B(1,i) / b) == 2)
            B(1,i) = 2;
        elseif (fix(B(1,i) / b)  == 3)
            B(1,i) = 3;
        else
            B(1,i) = 4;
        end
    end
    B(1,1) = 1;
    
    sum = 0;
    for i = 1:data_n
        if ( A(1,i) ~= B(1,i))
            sum = sum + 1;
        end
    end
    MCR = sum / data_n;
    fprintf('MCR = %d\n',MCR);
    
    S = 0;
    for i = 1:data_n
        S = S + (A(1,i) - B(1,i)).^2;
    end
    
    RMS = sqrt(S / (data_n * (data_n -1)));
    fprintf('RMS = %d\n',RMS);
    
    figure(2);
    imshow((uint8(newing)));
    title('FCM分割后的图像');   

    结果如下:
    这里写图片描述
    这里写图片描述

    转载自: http://www.cnblogs.com/ybjourney/p/4735335.html

    展开全文
  • fcm算法调用

    2017-09-04 21:49:57
    FCM算法是将N个L维向量分为C个模糊组,通过迭代不断更新隶属度以及聚类中心,最小化目标函数对数据进行聚类。
  • 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; %???? %%%%%%%%%...

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

    % author:wangjunzuo
    % date:2019/5/21
    % fuction:fcm algrithmn
    
    load data 
    load label
    maxgen = 100;  %??????
    m = 2;         %2??
    threshold = 10e-1000;   %?????
    cluster_n = 3;       %????
    
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %???
    
    [data_row,data_col] =size(data);
    U=rand(cluster_n,data_row); %????01?????
    col_sum=sum(U);    %???????
    U=U./repmat(col_sum,cluster_n,1);  %????????????1
    J(1)=0;
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    
    
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    for i = 1:maxgen
        mf = U.^m;
        center = mf*data./(repmat(sum(mf,2),1,data_col)); %??????
        dist= zeros(size(center, 1), size(data, 1));
        for k=1:size(center,1)
            dist(k,:) = sqrt(sum(((data-repmat(center(k,:),data_row,1)).^2),2)');
        end
         J(i)= sum(sum((dist.^2).*mf));  %??????
         tmp = dist.^(-2/(m-1)); 
         U=tmp./repmat(sum(tmp),cluster_n,1);  %???????
         if i > 1               %????????????????
    		if abs(J(i) - J(i-1)) < threshold 
                break; 
            end,
         end
    end
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %?????
    [max_vluae,index]=max(U);
    index=index';
    count = 0;
    for i=1:data_row
        if index(i)==label(i)
            count = count + 1;
        end
    end
    accurcy = count / data_row;
    
    
    
    
    
    展开全文
  • FCM算法中参数的优选方法及实例应用-FCM算法用于灰度图像分割的初始化方法的研究.pdf replyreload = ',' 51632;====在这个帖子中的内容,我六月份曾在 cinc 2009 上发表,在过几个月这篇文章就会被 EI Compendex, ...
  • fcm算法的matlab

    2015-03-05 14:45:56
    FCM算法实现:基于空间邻域信息的模糊C均值聚类算法的实现,该算法具有抑制噪声的能力
  • Matlab实现FCM算法

    2013-05-26 09:07:58
    Matlab代码实现的FCM算法,有例子,有图
  • FCM算法matlab代码

    2012-04-06 15:48:42
    FCM算法的matlab代码,可以正常运行,且效果挺好
  • FCM算法 matlab实现

    2010-02-04 19:29:45
    fcm算法,matlab 希望对大家有用,给大家共享。
  • 聚类FCM算法

    千次阅读 2017-09-20 15:30:51
    聚类FCM算法个人博客,想要搭建个人博客的可以进来看看: http://www.ioqian.top/ 在科研生活中,学习算法的时间不是很多,毕竟不是主要搞算法的,但是作为读研狗毕竟还是要毕业写论文的,算法还是要慢慢积累。 ...
  • FCM聚类算法

    2012-12-11 21:10:12
    FCM算法是一种基于划分的聚类算法,它的思想是使得被划分到同一簇的对象之间相似度最大,而不同簇之间的相似度最小。最后基于MATLAB实现了对图像信息的聚类。
  • FCM算法改进点

    2014-03-07 20:19:03
    这里是对知识点的一般 概述和 提点,希望做图像处理方向的新手有一定的帮助,详细资料 可以自行查找相关资料
  • 属性加权FCM算法

    2016-05-28 20:06:23
    属性加权FCM算法
  • FCM算法详解

    2018-05-07 15:56:00
    https://www.cnblogs.com/sddai/p/6259553.html 转载于:https://www.cnblogs.com/xueshujiexiaoqiang/p/9003190.html
  • FCM算法研究

    2018-07-26 21:16:00
    https://blog.csdn.net/u014772862/article/details/51767402 https://www.cnblogs.com/xiaohuahua108/p/6187178.html http://lib.csdn.net/article/machinelearning/35272 转载于:...
  • FCM聚类算法介绍

    2013-01-13 10:20:05
    FCM算法是一种基于划分的聚类算法,它的思想就是使得被划分到同一簇的对象之间相似度最大,而不同簇之间的相似度最小。模糊C均值算法是普通C均值算法的改进,普通C均值算法对于数据的划分是硬性的,而FCM则是一种...
  • K-Means算法与FCM算法

    2019-10-27 09:59:00
    一、前期准备 1.收集数据 2.描述数据集 二、原理分析 1.K-Means聚类法 这要从聚类开始说起: 聚类 ①是对于静态数据分析的一门技术,在许多...③是其他分析算法的一个预处理步骤。 ④是一种无监督的分类 聚类分析...
  • FCM算法(matlab)

    2018-10-17 15:31:37
    用matlab语言写成的FCM算法,注释明确,代码经典,适合初学者

空空如也

1 2 3 4 5 ... 20
收藏数 1,721
精华内容 688
关键字:

fcm