文档介绍:该【【原创】数据挖掘案例——ReliefF和K-means算法的医学应用 】是由【hh思密达】上传分享,文档一共【6】页,该文档可以免费在线阅读,需要了解更多关于【【原创】数据挖掘案例——ReliefF和K-means算法的医学应用 】的内容,可以使用淘豆网的站内搜索功能,选择自己适合的文档,以下文字是截取该文章内的部分文字,如需要获得完整电子版,请下载此文档到您的设备,方便您编辑和打印。【原创】数据挖掘案例——ReliefF和K-means算法的医学应? 数据挖掘?法的提出,让?们有能?最终认识数据的真正价值,即蕴藏在数据中的信息和知识。数据挖掘(DataMiriing),指的是从?型数据库或数据仓库中提取?们感兴趣的知识,这些知识是隐含的、事先未知的潜在有?信息,数据挖掘是?前国际上,数据库和信息决策领域的最前沿研究?向之?。因此分享?下很久以前做的?个?研究成果。也算是?个简单的数据挖掘处理的例?。?般由以下?个步骤:(l)分析问题:源数据数据库必须经过评估确认其是否符合数据挖掘标准。以决定预期结果,也就选择了这项?作的最优算法。(2)提取、清洗和校验数据:提取的数据放在?个结构上与数据模型兼容的数据库中。以统?的格式清洗那些不?致、不兼容的数据。?旦提取和清理数据后,浏览所创建的模型,以确保所有的数据都已经存在并且完整。(3)创建和调试模型:将算法应?于模型后产??个结构。浏览所产?的结构中数据,确认它对于源数据中“事实”的准确代表性,这是很重要的?点。虽然可能?法对每?个细节做到这?点,但是通过查看?成的模型,就可能发现重要的特征。(4)查询数据挖掘模型的数据:?旦建?模型,该数据就可?于决策?持了。(5)维护数据挖掘模型:数据模型建?好后,初始数据的特征,如有效性,可能发?改变。?些信息的改变会对精度产?很?的影响,因为它的变化影响作为基础的原始模型的性质。因?,维护数据挖掘模型是?常重要的环节。 聚类分析是数据挖掘采?的核?技术,成为该研究领域中?个?常活跃的研究课题。聚类分析基于”物以类聚”的朴素思想,根据事物的特征,对其进?聚类或分类。作为数据挖掘的?个重要研究?向,聚类分析越来越得到?们的关注。聚类的输?是?组没有类别标注的数据,事先可以知道这些数据聚成?簇?也可以不知道聚成?簇。通过分析这些数据,根据?定的聚类准则,合理划分记录集合,从?使相似的记录被划分到同?个簇中,不相似的数据划分到不同的簇中。?系列算法,它包括最早提出的Relief以及后来拓展的ReliefF和RReliefF,其中RReliefF算法是针对?标属性为连续值的回归问题提出的,下?仅介绍?下针对分类问题的Relief和ReliefF算法。,最初局限于两类数据的分类问题。Relief算法是?种特征权重算法(Featureweightingalgorithms),根据各个特征和类别的相关性赋予特征不同的权重,权重?于某个阈值的特征将被移除。Relief算法中特征和类别的相关性是基于特征对近距离样本的区分能?。算法从训练集D中随机选择?个样本R,然后从和R同类的样本中寻找最近邻样本H,称为NearHit,从和R不同类的样本中寻找最近邻样本M,称为NearMiss,然后根据以下规则更新每个特征的权重:如果R和NearHit在某个特征上的距离?于R和NearMiss上的距离,则说明该特征对区分同类和不同类的最近邻是有益的,则增加该特征的权重;反之,如果R和NearHit在某个特征的距离?于R和NearMiss上的距离,说明该特征对区分同类和不同类的最近邻起负?作?,则降低该特征的权重。以上过程重复m次,最后得到各特征的平均权重。特征的权重越?,表?该特征的分类能?越强,反之,表?该特征分类能?越弱。Relief算法的运?时间随着样本的抽样次数m和原始特征个数N的增加线性增加,因?运?效率?常?。具体算法如下所?:?较简单,但运?效率?,并且结果也?较令?满意,因此得到?泛应?,但是其局限性在于只能处理两类别数据,因此1994年Kononeill对其进?了扩展,得到了ReliefF作算法,可以处理多类别问题。该算法?于处理?标属性为连续值的回归问题。ReliefF算法在处理多类问题时,每次从训练样本集中随机取出?个样本R,然后从和R同类的样本集中找出R的k个近邻样本(nearHits),从每个R的不同类的样本集中均找出k个近邻样本(nearMisses),然后更新每个特征的权重,如下式所?:Relief系列算法运?效率?,对数据类型没有限制,属于?种特征权重算法,算法会赋予所有和类别相关性?的特征较?的权重,所以算法的局限性在于不能有效的去除冗余特征。-means聚类算法由于聚类算法是给予数据?然上的相似划法,要求得到的聚类是每个聚类内部数据尽可能的相似?聚类之间要尽可能的?差异。所以定义?种尺度来衡量相似度就显得?常重要了。?般来说,有两种定义相似度的?法。第?种?法是定义数据之间的距离,描述的是数据的差异。第?种?法是直接定义数据之间的相似度。下?是?种常见的定义距离的?法:,这是?种传统的距离概念,适合于2、3维空间。,是Euclidean距离的扩展,可以理解为N维空间的距离。聚类算法有很多种,在需要时可以根据所涉及的数据类型、聚类的?的以及具的应?要求来选择合适的聚类算法。下?介绍K-means聚类算法:K-means算法是?种常?的基于划分的聚类算法。K-means算法是以k为参数,把n个对象分成k个簇,使簇内具有较?的相似度,?簇间的相似度较低。K-means的处理过程为:?先随机选择k个对象作为初始的k个簇的质?;然后将余对象根据其与各个簇的质?的距离分配到最近的簇;最后重新计算各个簇的质?。不断重复此过程,直到?标函数最?为?。簇的质?由公式下列式?求得:在具体实现时,为了防?步骤2中的条件不成??出现?限循环,往往定义?个最?迭代次数。K-means尝试找出使平?误差函数值最?的k个划分。当数据分布较均匀,且簇与簇之间区别明显时,它的效果较好。?对?规模数据集,该算法是相对可扩展的,并且具有较?的效率。其中,n为数据集中对象的数?,k为期望得到的簇的数?,t为迭代的次数。通常情况下,算法会终?于局部最优解。但?,例如涉及有?数值属性的数据。其次,这种算法要求事先给出要?成的簇的数?k,显然这对?户提出了过?的要求,并且由于算法的初始聚类中?是随机选择的,?不同的初始中?对聚类结果有很?的影响。另外,K-means算法不适?于发现?凸?形状的簇,或者??差别很?的簇,?且它对于噪?和孤?点数据是敏感的。3.??实验数据来?著名的UCI机器学习数据库,该数据库有?量的??智能数据挖掘数据,?址为:。该数据库是不断更新的,也接受数据的捐赠。数据库种类涉及?活、?程、科学各个领域,记录数也是从少到多,最多达??万条。截?2010年底,数据库共有199个数据集,每个数据集合中有不同类型、时间的相关数据。可以根据实际情况进?选?。本?选?的数据来类型为:BreastCancerWisconsin(Original)Data,中Set?名称为:威斯康星州乳腺癌数据集。这些数据来源美国威斯康星?学医院的临床病例报告,每条数据具有11个属性。下载下来的数据?件格式为“.data通”过使?,Excel和Matlab?具将其转换为Matlab默认的数据集保存,?便程序进?调?。下表是该数据集的11个属性名称及说明:对上述数据进?转换后,以及数据说明可知,可以?于特征提取的有9个指标,样品编号和分类只是?于确定分类。本?的数据处理思路是先采?ReliefF特征提取算法计算各个属性的权重,剔除相关性最?的属性,然后采?K-means聚类算法对剩下的属性进?聚类分析。?在转换数据后,?先进?了预处理,由于本?的数据范围都是1-10,因此不需要归?化,但是数据样本中存在?些不完整,会影响实际的程序运?,经过程序处理,将这?部分数据删除。这些不完整的数据都是由于实际中?些原因没有登记或者遗失的,以“?的”形式代表。本?采?Matlab软件进?编程计算。根据第三章提到的ReliefF算法过程,先编写ReliefF函数程序,?来计算特征属性,再编写主程序,在主程序中调?该函数进?计算,并对结果进?分析,绘图,得到有?的结论。程序统?在最后贴出。?采?,权重?于某个阈值的特征将被移除,针对本?的实际情况,将对权重最?的2-3种剔除。由于算法在运?过程中,会选择随机样本R,随机数的不同将导致结果权重有?定的出?,因此本?采取平均的?法,将主程序运?20次,然后将结果汇总求出每种权重的平均值。如下所?,列为属性编号,?为每?次的计算结果:下?是特征提取算法计算的特征权重趋势图,计算20次的结果趋势相同:上述结果是否运?主程序所得的计算结果,看起来不直观,下?将其按照顺序绘图,可以直观显?各个属性权重的??分布,如下图所?: 按照从?到?顺序排列,可知,各个属性的权重关系如下:属性9<属性5<属性7<属性4<属性2<属性3<属性8<属性1<,则属性9、属性4和属性5剔除。从上?的特征权重可以看出,属性6裸核??是最主要的影响因素,说明乳腺癌患者的症状最先表现了裸核??上,将直接导致裸核??的变化,其次是属性1和属性8等,后?个属性权重??接近,但是从多次计算规律来看,还是能够说明其中不同的重要程度,下?是着重对?个重要的属性进?分析。下?是20次测试中,裸核??(属性6)的权重变化:从上图中可以看到该属性权重?-,是权重最?的?个属性。下?看看属性1的权重分布:-25左右变动,也是权重极?的?个,说明该特征属性在乳腺癌患者检测指标中是相当重要的?个判断依据。进?步分析显?,在单独对属性6,和属性1进?聚类分析,%。本?将在下节中的Kmeans算法中详细介绍。?节中通过ReliefF算法对数据集的分析,可以得到属性权重的重要程度,这些可以对临床诊断有?些参考价值,可以?来对实际案例进?分析,可以尽量的避免错误诊断,并提?诊断的速度和正确率。下?将通过K-menas聚类分析算法对数据进?分析。本?节将分为?个步骤来进?对?,确定聚类分析算法的结果以及与ReliefF算法结合的结果等。-means算法单独分析数据集下?将采?Kmeans算法单独对数据集进?分析。Matlab中已经包括了?些常规数据挖掘的算法,例如本?所?到的K-means算法。该函数名为kmeans,可以对数据集进?聚类分析。?先本?对乳腺癌数据集的所有属性列(除去?份信息和分类列)直接进?分类,由于数据集结果只有2种类型,所以?先进?分2类的测试,结果如下:总体将683条数据分成了2类,%,其中第?%,第?%。下?是分类后对按照不同属性的绘制的属性值分布图:限于篇幅,只选择了上述3个特征属性进?图像绘制,从结果来看,可以很直观的观察到K-means算法分类后的情况,第?类与第?类的分类界限?较清晰。但是不容易观察到正确和错误的情况。下表是分类结果中各个属性的聚类中?:从K-means算法的效果来看,能够很准确的将数据集进?分类。???是由于该数据集,可能是该案例特征?较明显,另???是由于K-menas算法对这种2类的作?较?。-means结合ReliefF分析数据集单从分类正确率和结果??来看,K-mens算法已经完全可以对乳腺癌数据集做出?常准确的判断。但是考虑ReliefF算法对属性权重的影响,本?节将结合ReliefF算法和K-means算法来对该数据集进?分析,???得到处理该问题?些简单的结论,另外???可以得到?些对医学处理数据的?法研究?法。?先,本?节??些结论,根据不同属性的权重来对k-menas分类数据进?预处理,以得到更精确的结论和对该数据更深度的特征规律。,得知属性9<属性5<属性7<属性4<属性2<属性3<属性8<属性1<属性6,根据ReliefF算法原理本?可以认为,对于这种属性6和属性1重要的特征属性,应该对分类起到更加到的作?。所以下?将单独对各个属性的数据进?分类测试,详细结果如下表:总的分类正确率中,属性9最低,属性6最?,这与ReliefF算法测试的结果?致相似,但是由于ReliefFar算法中间部分权重接近,所以也区分不明显。说明特征属性权重的判断对分类是有影响的。上述单独分类中,只将需要分类的列数据取出来,输?到K-means算法中即可。由于输?数据的变化,K-means分类时结果肯定是有差距的,所以单独从?个属性判断其类型是不可靠的。下?选择了单个分类时最?和最低的情况,绘制其分类属性值分布图,如下图所?:下?将对特征权重按照从?到?的顺序,选择相应的数据,进?聚类分析,结论如下:,分类成功率为:%;,属性1,分类成功率为:%;,1,8,3,分类成功率为:%;,1,8,3,2,4,分类成功率为:%;,1,8,3,2,4,5,7,分类成功率为:%;从上?的测试可以看出,选择特征权重最?的6个属性,其正确率就达到选择所有属性的情况,因此我们可以认为特征权重最?的?个属性在乳腺癌诊断过程的作?实际可能?较?,实际有可能造成反作?,也就是这?个属性值与乳腺癌没有必然的联系。这?点可以给诊断参考,或者引起注意,进?进?步的研究,确认。-means分成3类的情况虽然从上述2?节的实验中可以得到该数据集的?部分结果和结论。但是为了将相同类型的数据更加准确的分出,下?将尝试分为3类的情况。???,可以分析在乳腺癌良性和恶性情况下的显著特征属性;另???也可以根据此结果找到更加合理的解决?法。还是采?Matlab中的kmeans函数,将分类数改为3,由于分为3类后数据类型增多,判断较复杂,所以?动对数据进?分析,将所有特征属性加?进去。运?结果如下,测试数据中总共683条,其中良性共444条,恶性共239条:?类的记录中,%;?类的记录中,恶性占100%;,恶性占92%;根据上述结果可以认为第?类为良性的分类,第?类为恶性分类,第三类为混合类。对于混合类,说明??的数据较其他数据更加接近于偏离病例的典型数据,所以进?步分析在第?类中和第?类中的分类正确率:?类为良性,共448条数据,%;?类为恶性,共99条数据,分类正确率为100%;,共136条数据因此单独从分类后的正确率来看,效果有提?,说明对典型的病例数据分类更准确,但是对于第三类数据,??法区分,因此这种情况下,其意义不在于分类的整体正确率,?在于在?些特殊情况下,可以根据?些重要的特征属性值就可以为患者确诊,从?提?效率和准确率,减少误诊断的?率。上?是将所有属性进?K-means变换,下?将结合ReliefF算法,先去掉?部分特征权重较?的特征属性后,再进?K-means处理。,下?提取权重最?的6个属性进?测试,分别是:属性6,属性1,属性8,属性3,属性2,属性4。?类为良性,共281条数据,%;?类为恶性,共211条数据,%;,共191条数据因此,对?可以看到,虽然良性的正确率增加了,但是检测出的数据减少了。第三类混合的数量也增多了,说明提出了特种属性较?的属性,可以更加容易区分极端的病例数据,对极端数据的检测更加准确。 %主函数2 clear;clc;3 load('')4 D=data(:,2:size(data,2));%5 m=80;%抽样次数6 k=8;7 N=20;%运?次数8 fori1=:N9 W(i,:)=ReliefF(D,m,k);10 end11 fori=1:N%将每次计算的权重进?绘图,绘图N次,看整体效果12 plot(1:size(W,2),W(i,:));13 holdon;14 end15 fori=1:size(W,2)%计算N次中,每个属性的平均值16 result(1,i)=sum(W(:,i))/size(W,1);17 end18 xlabel('属性编号');19 ylabel('特征权重');20 title('ReliefF算法计算乳腺癌数据的特征权重');21 axis([])22 %-------绘制每?种的属性变化趋势23 xlabel('计算次数');24 ylabel('特征权重');25 name=char('块厚度','细胞??均匀性','细胞形态均匀性','边缘粘附?','单上?细胞尺?','裸核','Bland染?质','正常核仁','核分裂');26 name=cellstr(name);27 28 fori=1:size(W,2)29 figure30 plot(1:size(W,1),W(:,i));31 xlabel('计算次数');32 ylabel('特征权重');33 title([char(name(i))'(属性'num2Str(i)')的特征权重变化']);34 %Relief函数实现2 %D为输?的训练集合,输?集合去掉?份信息项?;k为最近邻样本个数3 functionW=ReliefF(D,m,k)4 Rows=size(D,1);%样本个数5 Cols=size(D,2);%特征熟练,不包括分类列6 type2=sum((D(:,Cols)==2))/Rows;7 type4=sum((D(:,Cols)==4))/Rows;8 %先将数据集分为2类,可以加快计算速度9 D1=zeros(0,Cols);%第?类10 D2=zeros(0,Cols);%第?类11 fori=1:Rows12 ifD(i,Cols)==213 D1(size(D1,1)+1,:)=D(i,:);14 elseifD(i,Cols)==415 D2(size(D2,1)+1,:)=D(i,:);16 end17 end18 W=zeros(1,Cols-1);%初始化特征权重,置019 fori=1:m%进?m次循环选择操作20 %从D中随机选择?个样本R21 [R,Dh,Dm]=GetRandSamples(D,D1,D2,k);22 %更新特征权重值23 forj=1:length(W)每个特征累计?次,循环%24 1W(,j)=W(1,j)-sum(Dh(:,j))/(k*m)+sum(Dm(:,j))/(k*m)按照公式更新权重;%25 end26 endReliefF辅助函数,寻找最近的样本数K1%获取随机R以及找出邻近样本2%D:训练集;D1:类别1数据集;D2:类别2数据集;3%Dh:与R同类相邻的样本距离;Dm:与R不同类的相邻样本距离4function[R,Dh,Dm]=GetRandSamples(D,D1,D2,k)5%先产??个随机数,确定选定的样本R6r=ceil(1+(size(D,1)-1)*rand);7R=D(r,:);将第%r?选中,赋值给R8d1=zeros(1,0);%先置0,d1是与R的距离,是不是同类在下?判断9d2=zeros(1,0);%先置0,d2是与R的距离10%D1,D2是先传?的参数,在ReliefF函数中已经分类好了11fori1=:size(D1,1)%计算R与D1的距离12d1(1,i)=Distance(R,D1(i,:));13end14forj=1:size(D2,1)%计算R与D2的距离15d2(1,j)=Distance(R,D2(j,:));16end17[v1,L1]=sort(d1);%d1排序,18[v2,L2]=sort(d2);%d2排序19ifR(1,size(R,2))==2%如果R样本=2,是良性20H=D1(L1(1,2:k+1),:);%L1中是与R最近的距离的编号,赋值给H。21M=D2(L2(1,1:k),:);%v2(1,1:k);22else23H=D1(L1(1,1:k),:);24M=D2(L2(1,2:k+1),:);25end26%循环计算每2个样本特征之间的特征距离:(特征1-特征2)/(max-min)27fori=1:size(H,1)28forj1=:size(H,2)29Dh(i,j)=abs(H(i,j)-R(1,j))/9;%本?数据范围都是1-10,所以max-min=9为固定30Dm(i,j)=abs(M(i,j)-R(1,j))/9;-means算法主程序1 clc;clear;2 load('')%加载测试数据3 N0=1;%从多少列开始的数据进?预测分类4 N1=size(data,1);%所有数据的?数5 data=data(N0:N1,:);%只选取需要测试的数据6 data1=data(:,[2,3,4,5,6,7,8,9]);%2[,4,7,9]2:size(data,2)-17 opts=statset('Display','final');%控制选项8 [idx,ctrs,result,D]=kmeans(data1,2,...%data1为要分类的数据,2为分类的类别数,本?只有2类9 'Distance','city',...选择的距离的计算?式%10 'Options',opts);控制选项%,参考matlab帮助11 t=[data(:,size(data,2)),idx(:,1)];%把测试数据最后?列,也就是分类属性和分类结果取出来:列+列12 d2=data(idx==1,11);%提取原始数据中属于第1类的数据的最后?列13 a=sum(d2==2);14 b=a/length(d2);15 totalSum=0;%总的正确率16 rate1=0;%第? rate2=0;%第? if(b>)%说明第1类属于良性,则a的值就是良性中判断正确的个数19 totalSum=totalSum+a;20 rate1=a/length(d2);21 %然后加上恶性中判断正确的?例22 totalSum=totalSum+sum(data(idx==2,11)==4);23 rate2=sum(data(idx==2,11)==4)/length(data(idx==2,11));24 else%说明第1类属于恶性25 totalSum=totalSum+sum(data(idx==1,11)==4);26 totalSum=totalSum+sum(data(idx==2,11)==2);27 rate1=sum(data(idx==2,11)==2)/length(data(idx==2,11));28 rate2=sum(data(idx==1,11)==4)/length(data(idx==1,11));29 end30 x1=1;%第x1个属性31 x2=1;%第x2个属性32 plot(1:sum(idx==1),data1(idx==1,x1),'r.','MarkerSize',12);33 holdon;34 plot(sum(idx==1)+1:sum(idx==1)+sum(idx==2),data1(idx==2,x1),'b.','MarkerSize',12);35 xlabel('记录数');36 ylabel('属性值');37 title('属性9的值分布');38 legend('第?类','第?类');39 axis([0640010])40 rate=totalSum/size(t,1)总的判断准确率%