数据挖掘课程报告班级 XXXXXX学生姓名 XXXXXX学号 2010100XXXXX指导教师 XXXXXXX日期 2013年10月15日k-means 算法与猫群算法的聚类效果比较分析摘要：本文在聚类个数k 值预先设定的前提下，分别应用了k-means 算法、猫群算法对储层含油性问题进行聚类分析，比较了这两种算法的聚类效果。

实验结果显示：本文所采用的传统的k-means 算法常容易陷入局部最优。

而猫群算法在样本数目较小时（如以表oilsk81为例时），是一种快速、高效的识别算法。

当样本数目翻倍时，受实际算法代码设计的影响，识别的正确率将会下降，这也充分说明了猫群算法的运算效果受代码和样本大小的影响，有较大的不确定性。

关键词：k-means ；猫群算法；聚类分析；1 引言K-means 算法[1]是由J.B. Mac Queen 于1967 年提出的，该算法是一个经典的基于划分的聚类算法，因其算法效率较高，易于其它方法相结合，目前已成为数据挖掘、机器学习、模式识别和数量统计等领域应用最广的聚类算法之一。

近几年来提出了很多的群体智能算法，这些算法都是通过模仿生物界中某些动物的行为演化出来的智能算法[2]。

猫群算法作为群体智能算法之一，具有良好的局部搜索和全局搜索能力[3]，算法控制参数较少，通过两种模式的结合搜索，大大的提高了搜索优良解的可能性和搜索效率，较其他算法较容易实现，收敛速度快，具有较高的运算速度，易于其他算法结合。

但也有出现“早熟”现象的弊端[4]。

群体中个体的优化只是根据一些表层的信息，即只是通过适应度值来判断个体的好坏，缺乏深层次的理论分析和综合因素的考虑。

由于猫群算法出现较晚，该算法目前主要应用于函数优化问题[5]，故在聚类分析研究方面，很有必要对猫群算法进行深入研究。

传统的k-means 算法与新兴的聚类方法猫群算法相比较会有哪些异同点呢，接下来将具体阐述。

2 算法模型2.1 K-means 算法模型设对n 个m 维样本集进行聚类，n 个样本集表示为12{,,,}n X X X X = ，其中12(,,,)i i i im X x x x = ，聚类成k 个分类表示为12{,,}k C C C C = ，其质心表示为1,1,2,....jj ix C jz X j kn ∈==∑，jn 为jC 中包含的数据点的个数，则聚类的目标是使k 个类满足以下条件：1(,)i jkiji j j x C dx z Min=∈−−→∑∑式中，(,)ij i j d x z 表示计算数据间距离的函数，他可以是不同的度量方式，本文选择欧氏距离度量函数来度量，k 为聚类数目，j z 为j 类样本的聚类中心。

2.1 猫群算法模型 基本流程：猫群算法的基本流程分为以下5步。

具体流程如图1所示。

① 初始化猫群。

② 根据分组率将猫群随机分成搜寻模式和跟踪模式两组。

③ 根据猫的模式标志位所确定的模式进行位置更新，如果猫在搜寻模式下，则执行搜寻模式的行为；否则，执行跟踪模式的行为。

④ 通过适应度函数来计算每一只猫的适应度，记录保留适应度最优的猫。

⑤ 判断是否满足终止条件，若满足则输出最优解，结束程序；否则继续执行步骤 。

3 储层含油性识别问题的聚类分析本文从储层含油性问题入手，以Oilsk81等3口井测井解释成果为例，对储层参数分布特征通过K-means 算法、猫群算法进行了聚类分析，最后与测井原有结果对比，研究比较K-means 算法、猫群算法基于不同数据集以及不同迭代次数的分类准确率。

3.1 样本和指标的选取实验数据来自于江汉油田某区块，该区块有oilsk81等3口井，本文选用的实验数据来分别自于oilsk81、oilsk83、oilsk85井。

其中oilsk81井属性和对应的测井解释结论如表1所示。

表1 oilsk81井测井解释成果表层号 声波(μs/m) 中子 (%) 深测向电阻率 (Ω.m) 孔隙度 (%) 含油饱和度 (%) 渗透率 (mμm 2) 结论1 195 7.5 13.0 6.0 0 0 干层2 225 10.0 7.3 11.0 0 0 水层 3 230 14.0 5.5 12.0 0 0 水层4 220 9.0 25.0 9.0 56 1.3 油层 52258.030.09.0582.3油层 算法开始设定算法参数（如分组率、基因位变化范围等）计算猫的适应度值根据分组率，一部分猫处于搜寻模式，剩下的猫处于跟踪模式判断猫是否处在搜寻模式搜寻模式跟踪模式是否计算适应度值并保留最优解是否满足结束条件？输出最优解，算法结束是否图1 猫群算法的基本流程6 210 7.0 26.0 6.0 0 0 干层7 220 8.0 26.0 10.0 60 2.4 油层8 225 9.0 30.0 10.0 62 2.5 油层9 195 4.0 36.0 5.5 0 0 干层10 220 9.0 30.0 9.0 61 1.7 油层11 217 7.5 50.0 8.0 55 1.1 油层12 210 6.0 130.0 7.0 48 0.7 差油层13 195 4.0 100.0 5.0 0 0 干层14 195 4.0 70.0 5.0 0 0 干层15 200 6.0 90.0 6.0 0 0 干层16 200 4.0 130.0 6.0 0 0 干层17 200 4.0 90.0 5.0 0 0 干层18 215 9.0 25.0 9.0 54 1.6 油层19 195 4.0 70.0 4.0 0 0 干层20 200 6.0 55.0 6.0 0 0 干层21 200 4.0 100.0 5.0 0 0 干层22 240 13.5 12.0 12.0 40 2.4 油层23 212 8.0 36.0 8.0 60 1.5 油层24 197 6.0 50.0 6.0 0 0 干层25 202 6.0 55.0 7.0 52 0.8 差油层26 195 4.5 50.0 6.0 0 0 干层27 203 5.0 45.0 7.0 46 0.6 差油层28 195 6.0 50.0 6.0 0 0 干层29 210 7.5 20.0 8.0 57 1.2 油层30 201 6.0 16.0 7.0 40 0.4 差油层31 213 9.5 12.0 9.0 61 2 油层从表1中的数据可以看出，用于储层含油性识别的属性集合为：声波时差，中子，深测向电阻率，孔隙度，含油饱和度和渗透率。

测并解释结论为：油层，差油层，水层和干层。

3.2 K-means算法的聚类分析本文应用的是matlab软件自带的K-means函数，即传统的K-means算法。

K值是已知的，值为4。

在命令窗口中输入命令“[cid,C,sumD]=Kmeans(x,4)”。

输出参数分别为cid，C，sumD，cid为N*1的向量，存储的是每个点的聚类标号；C为K*P的矩阵，存储的是K个聚类质心位置；sumD 1*K的和向量，存储的是类间所有点与该类质心点距离之和。

x为样本数据的矩阵。

以Oilsk81为样本数据集，结果为{3 3 3 1 1 3 1 1 4 1 1 2 2 4 2 2 2 1 4 4 2 1 1 4 1 4 1 4 1 1 1}。

图3 K-means聚类分析结果图4 最优聚类结果以Oilsk83为样本数据集，聚类分析结果如图：图3 K-means聚类分析结果图4 最优聚类结果以Oilsk85为样本数据集，聚类分析结果如图：图3 K-means聚类分析结果图4 最优聚类结果由于K-means算法采用随机法选取k个初始聚类中心点，随机选择的初始中心点可能导致算法聚类效果不稳定，且使算法常陷入局部最优而聚类结果非全局最优。

从上述K-means聚类分析结果与最优聚类结果的对比图中，可看出K-means算法对初始聚类中心选择具有依赖性。

3.2 猫群算法的聚类分析设猫群数量CatNum=200，记忆池大小SMP=5，启发式因子Ot=1，样本特征值变化概率CDC=1，样本变化值范围SRD=0.2，每个猫个体所属行为模式标志flag=0为搜寻模式，flag=1时为跟踪模式，同时在种群中选择2%个猫执行跟踪模式，其他为搜寻模式。

聚类时以欧氏距离衡量相似性，为消除数值在不同量纲下的差异，对数据进行了归一化处理。

数据集的6个属性全部用于储层含油性的识别。

聚类的结果如表1、表二所示：表2基于不同数据集的聚类正确率井号迭代次数为50 迭代次数为100 迭代次数为200 迭代次数为500 Oilsk81 100% 100% 100% 100%Oilsk83 94% 94% 94% 94%Oilsk85 66.15% 69.23% 70.77% 76.92%表3基于不同数据集的样本聚类错误情况井号迭代次数为50 迭代次数为100 迭代次数为200 迭代次数为500 Oilsk81 无无无无Oilsk82 4,5,6 4,5,6 4,5,6 4,5,6Oilsk85 13,14,16,18,19,20,21,22,23,24,25,26,27,31,34,40,43,49,50,55,58,13,14,15,16,17,18,19,20,21,22,24,25,26,31,34,40,43,49,50,55,58,5,13,14,18,19,20,21,22,24,25,26,31,40,43,46,47,49,50,51,54,57,13,14,15,16,17,18,19,20,21,22,24,25,26,31,34,40,43,49,50,55,58,在猫群算法针对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 算法是聚类分析中一种常用的基于划分的方法，同时存在不足，聚类结果受初始类中心影响较大而过早收敛于次优解。