1 简介
数据挖掘是当今信息产业界最前沿的研究方向之一,聚类分析是其中的一项重要研究课题。聚类分析是将数据根据一定的相似度度量划分成若干有用的或有意义的类(簇),其在实际应用中许多领域有着广泛的应用。目前,低维数据的聚类算法已较成熟,受“维度灾”(the curse of dimensionality)的影响,许多传统的聚类算法运用到高维数据上往往失效,然而在实际应用中,高维度的数据普遍存在,例如,基因表达数据、金融数据、多媒体数据以及文本数据等。因此对高维数据聚类算法的研究具有非常重要的理论意义和应用价值。 针对高维数据聚类问题,最直接有效的方法是降低维度,通过降维技术将原来高维数据空间归约到较低维空间,从而可以利用传统的聚类方法完成聚类处理。在高维数据中,并不是所有的维度对聚类而言都是有效的,因此需要对特征空间进行有效的搜索从而找出有效的聚类特征子空间。对于高维数据而言,维度越高,其特征子空间的数目也就越大,从而导致了传统的搜索算法像贪婪算法较易陷入局部最优解。作为智能算法的一种,遗传算法(Genetic Algorithms, GA)的全局收敛性得到人们的普遍关注。遗传算法是通过模拟生物在自然界环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。本文利用遗传算法的全局搜索能力对高维数据的特征空间进行搜索,以找出有效的聚类特征子空间。
2 部分代码
clctic%%参数初始化maxgen=100; %进化代数,即迭代次数,初始预定值选为100sizepop=200; %种群规模,初始预定值选为100pcross=0.9; %交叉概率选择,0和1之间,一般取0.9pmutation=0.01; %变异概率选择,0和1之间,一般取0.01individuals=struct('fitness',zeros(1,sizepop),'chrom',[]);%种群,种群由sizepop条染色体(chrom)及每条染色体的适应度(fitness)组成avgfitness=[];%记录每一代种群的平均适应度,首先赋给一个空数组bestfitness=[];%记录每一代种群的最佳适应度,首先赋给一个空数组bestchrom=[];%记录适应度最好的染色体,首先赋给一个空数组%初始化种群for i=1:sizepop%随机产生一个种群individuals.chrom(i,:)=4000*rand(1,12);%把12个0~4000的随机数赋给种群中的一条染色体,代表K=4个聚类中心x=individuals.chrom(i,:);%计算每条染色体的适应度individuals.fitness(i)=fitness(x);end%%找最好的染色体[bestfitness bestindex]=max(individuals.fitness);%找出适应度最大的染色体,并记录其适应度的值(bestfitness)和染色体所在的位置(bestindex)bestchrom=individuals.chrom(bestindex,:);%把最好的染色体赋给变量bestchromavgfitness=sum(individuals.fitness)/sizepop;%计算群体中染色体的平均适应度trace=[avgfitness bestfitness];%记录每一代进化中最好的适应度和平均适应度clc%%画出聚类点data1=load('aa.txt');%待分类的数据kernal=[bestchrom(1:3);bestchrom(4:6);bestchrom(7:9);bestchrom(10:12)];%解码出最佳聚类中心[n,m]=size(data1);%求出待聚类数据的行数和列数index=cell(4,1);%用来保存聚类类别dist=0;%用来计算准则函数for i=1:ndis(1)=norm(kernal(1,:)-data1(i,:));dis(2)=norm(kernal(2,:)-data1(i,:));dis(3)=norm(kernal(3,:)-data1(i,:));dis(4)=norm(kernal(4,:)-data1(i,:));%计算出待聚类数据中的一点到各个聚类中心的距离[value,index1]=min(dis);%找出最短距离和其聚类中心的种类cid(i)=index1;%用来记录数据被划分到的类别index{index1,1}=[index{index1,1} i];dist=dist+value;%计算准则函数endcid;dist;%%作图figure(2)plot3(bestchrom(1),bestchrom(2),bestchrom(3),'ro');title('result100*100') hold on%画出第一类的聚类中心index1=index{1,1};for i=1:length(index1)plot3(data1(index1(i),1),data1(index1(i),2),data1(index1(i),3),'r*')hold onendhold on%画出被划分到第一类中的各点index1=index{2,1};plot3(bestchrom(4),bestchrom(5),bestchrom(6),'bo');hold on%画出第二类的聚类中心for i=1:length(index1)plot3(data1(index1(i),1),data1(index1(i),2),data1(index1(i),3),'b*');grid on;hold onend%画出被划分到第二类中的各点index1=index{3,1};plot3(bestchrom(7),bestchrom(8),bestchrom(9),'go');hold on%画出第三类的聚类中心for i=1:length(index1)plot3(data1(index1(i),1),data1(index1(i),2),data1(index1(i),3),'g*');hold onend%画出被划分到第三类中的各点index1=index{4,1};plot3(bestchrom(10),bestchrom(11),bestchrom(12),'ko');hold on%画出第四类的聚类中心for i=1:length(index1)plot3(data1(index1(i),1),data1(index1(i),2),data1(index1(i),3),'k*');hold onend%画出被划分到第四类中的各点toc
3 仿真结果
编辑
编辑
4 参考文献
[1]熊琅环. 基于遗传算法的高维数据聚类研究[D]. 汕头大学.
博主简介:擅长智能优化算法、神经网络预测、信号处理、元胞自动机、图像处理、路径规划、无人机等多种领域的Matlab仿真,相关matlab代码问题可私信交流。
部分理论引用网络文献,若有侵权联系博主删除。