数据挖掘报告

数据挖掘课程报告班级 XXXXXX 学生姓名 XXXXXX 学号2010100XXXXX指导教师 XXXXXXX日期2013年10月15日k-means算法与猫群算法的聚类效果比较分析摘要：本文在聚类个数k值预先设定的前提下，分别应用了k-means算法、猫群算法对储层含油性问题进行聚类分析，比较了这两种算法的聚类效果。实验结果显示：本文所采用的传统的k-means算法常容易陷入局部最优。而猫群算法在样本数目较小时（如以表oilsk81为例时），是一种快速、高效的识别算法。当样本数目翻倍时，受实际算法代码设计的影响，识别的正确率将会下降，这也充分说明了猫群算法的运算效果受代码和样本大小的影响，有较大的不确定性。关键词：k-means；猫群算法；聚类分析；1引言K-means算法⑴是由J.B.MacQueen于1967年提出的，该算法是一个经典的基于划分的聚类算法，因其算法效率较高，易于其它方法相结合，目前已成为数据挖掘、机器学习、模式识别和数量统计等领域应用最广的聚类算法之一。近几年来提出了很多的群体智能算法,这些算法都是通过模仿生物界中某些动物的行为演化出来的智能算法⑵。猫群算法作为群体智能算法之一，具有良好的局部搜索和全局搜索能力⑶，算法控制参数较少，通过两种模式的结合搜索，大大的提高了搜索优良解的可能性和搜索效率，较其他算法较容易实现，收敛速度快，具有较高的运算速度，易于其他算法结合。但也有出现“早熟”现象的弊端［4］。群体中个体的优化只是根据一些表层的信息，即只是通过适应度值来判断个体的好坏，缺乏深层次的理论分析和综合因素的考虑。由于猫群算法出现较晚，该算法目前主要应用于函数优化问题习，故在聚类分析研究方面，很有必要对猫群算法进行深入研究。传统的k-means算法与新兴的聚类方法猫群算法相比较会有哪些异同点呢，接下来将具体阐述。2算法模型2.1K-means算法模型设对n个m维样本集进行聚类，n个样本集表示为X二｛X,X，…，X｝，其中TOC\o"1-5"\h\z1 2 nX=（x,x，…，x），聚类成k个分类表示为C二｛C,C，…C｝，其质心表示为i i1i2 im 12 k1z=工X,j=1,2,....k\o"CurrentDocument"jn' nC 一jxeCj ，j为j中包含的数据点的个数，则聚类的目标是使k个类满足以下条件：

d(x,z) >Minijijjixi£式中，d(x,z)表示计算数据间距离的函数，他jij可以是不同的度量方式，本文选择欧氏距离度量函数来度量，k为聚类数目，Z.为j类样本的聚类中心。j2.1猫群算法模型基本流程：猫群算法的基本流程分为以下5步。具体流程如图1所示。初始化猫群。根据分组率将猫群随机分成搜寻模式和跟踪模式两组。根据猫的模式标志位所确定的模式进行位置更新，如果猫在搜寻模式下，则执行搜寻模式的行为；否则，执行跟踪模式的行为。通过适应度函数来计算每一只猫的适应度，记录保留适应度最优的猫。判断是否满足终止条件，若满足则输出最优解，结束程序；否则继续执行步骤。输出最优解，算法.结束丿图输出最优解，算法.结束丿3储层含油性识别问题的聚类分析本文从储层含油性问题入手，以Oilsk81等3口井测井解释成果为例，对储层参数分布特征通过K-means算法、猫群算法进行了聚类分析，最后与测井原有结果对比，研究比较K-means算法、猫群算法基于不同数据集以及不同迭代次数的分类准确率。3.1样本和指标的选取实验数据来自于江汉油田某区块，该区块有oilsk81等3口井，本文选用的实验数据来分别自于oilsk81、oilsk83、oilsk85井。其中oilsk81井属性和对应的测井解释结论如表1所/示0表1oilsk81井测井解释成果表层号声波(ys/m)中子(%)深测向电阻率(Q.m)孔隙度(%)含油饱和度(%)渗透率(mym2)结论11957.513.06.000干层222510.07.311.000水层323014.05.512.000水层42209.025.09.0561.3油层52258.030.09.0582.3油层62107.026.06.000干层72208.026.010.0602.4油层82259.030.010.0622.5油层91954.036.05.500干层102209.030.09.0611.7油层112177.550.08.0551.1油层122106.0130.07.0480.7差油层131954.0100.05.000干层141954.070.05.000干层152006.090.06.000干层162004.0130.06.000干层172004.090.05.000干层182159.025.09.0541.6油层191954.070.04.000干层202006.055.06.000干层212004.0100.05.000干层2224013.512.012.0402.4油层232128.036.08.0601.5油层241976.050.06.000干层252026.055.07.0520.8差油层261954.550.06.000干层272035.045.07.0460.6差油层281956.050.06.000干层292107.520.08.0571.2油层302016.016.07.0400.4差油层312139.512.09.0612油层从表1中的数据可以看出，用于储层含油性识别的属性集合为：声波时差，中子，深测向电阻率，孔隙度，含油饱和度和渗透率。测并解释结论为：油层，差油层，水层和干层。3.2K-means算法的聚类分析本文应用的是matlab软件自带的K-means函数，即传统的K-means算法。K值是已知的，值为4。在命令窗口中输入命令，[cid,C,sumD]=Kmeans(x,4)”。输出参数分别为cid,C,sumD,cid为N*1的向量，存储的是每个点的聚类标号；C为K*P的矩阵，存储的是K个聚类质心位置；sumD1*K的和向量，存储的是类间所有点与该类质心点距离之和。x为样本数据的矩阵。以Oilsk81为样本数据集，结果为｛333113114112242221442114141411图3K-means聚类分析结果以Oilsk83为样本数据集，聚类分析结果如图:图4最优聚类结果图3K-means图3K-means聚类分析结果以Oilsk83为样本数据集，聚类分析结果如图:图4最优聚类结果图3K-means聚类分析结果图4最优聚类结果以Oilsk85为样本数据集，聚类分析结果如图:图3K-means聚类分析结果图4最优聚类结果由于K-means算法采用随机法选取k个初始聚类中心点，随机选择的初始中心点可能导致算法聚类效果不稳定，且使算法常陷入局部最优而聚类结果非全局最优。从上述K-means聚类分析结果与最优聚类结果的对比图中，可看出K-means算法对初始聚类中心选择具有依赖性。3.2猫群算法的聚类分析设猫群数量CatNum=200,记忆池大小SMP=5,启发式因子Ot=l,样本特征值变化概率CDC=1，样本变化值范围SRD=0.2，每个猫个体所属行为模式标志flag=0为搜寻模式，flag=1时为跟踪模式，同时在种群中选择2%个猫执行跟踪模式，其他为搜寻模式。聚类时以欧氏距离衡量相似性，为消除数值在不同量纲下的差异，对数据进行了归一化处理。数据集的6个属性全部用于储层含油性的识别。聚类的结果如表1、表二所示：表2基于不同数据集的聚类正确率井号迭代次数为50迭代次数为100迭代次数为200迭代次数为500Oilsk81100%100%100%100%Oilsk8394%94%94%94%Oilsk8566.15%69.23%70.77%76.92%表3基于不同数据集的样本聚类错误情况井号迭代次数为50迭代次数为100迭代次数为200迭代次数为500Oilsk81无无无无Oilsk824,5,64,5,64,5,64,5,613,14,16,18,19,20,21,13,14,15,16,17,18,19,5,13,14,18,19,20,21,22,13,14,15,16,17,1&19,222,23,24,25,26,27,31,20,21,22,24,25,26,31,24,25,26,31,40,43,46,470,21,22,24,25,26,31,34,Oilsk8534,40,43,49,50,55,5&34,40,43,49,50,55,5&,49,50,51,54,57,40,43,49,50,55,5&在猫群算法针对oilsk81井测井解释成果表中的特征值进行反复地运行分类后，可以发现oilsk81表的特征值在迭代10次后，在第10代出现了与原有结果完全一致的结论，而后分别在迭代50次、100次、200次、500次中得出了完全一样的结果。所以猫群算法针对oilsk81表的数据集在以上4种迭代次数的环境下，其准确率达到了100%。在猫群算法针对oilsk83井测井解释成果表中的特征值进行反复地运行分类后，发现oilsk83表的特征值在迭代20次后，与原有结论相比，出现了三个不同的结论，即第4,5,6项中的差油层和干层均被分为水层。而后进行了50次、100次、200次、500次的迭代，结果与原结论相比，仍有三个差异项。由于oilsk83表与oilsk81表相比，数据项增多，故在相同迭代条件下，未能达到完全准确。固定的分类错误项受算法本身的代码设计影响，所以猫群算法针对oilsk83表的数据集在以上4种迭代次数的环境下，其准确率达到94%。3.3两种算法的聚类效果比较K-means算法是聚类分析中一种常用的基于划分的方法，同时存在不足，聚类结果受初始类中心影响较大而过早收敛于次优解。从聚类效果的分析对比图中可以看出，K-means倾向于局部最优而非全局最优，这是它的缺点。而猫群算法在以oilsk81井测井结果为数据集时，聚类效果能够达到最优；在数据集较大的情况下，准确率会下降，如以oilsk85井测井结果为数据集时正确率仅能达到67.69%。故大胆推测，在数据量相对较小时，选用猫群算法的聚类效果更好。参考文献:⑴ 张立;基于新闻评论数据的K-means聚类算法的