核空间次蚁群聚类算法的研究.docVIP

核空间二次蚁群聚类算法的研究 论文摘要：传统的聚类算法在处理复杂特征数据时效果不理想，为此提出使用高斯径向基核函数将原空间上的数据映射到高维特征空间后，再用蚂蚁算法进行第一次聚类，针对第一次聚类结果得到较多簇等问题，提出再用马赛克算法进行二次聚类，得到较为接近真实情况的簇数目。UCI数据集中的鸢尾花数据集，第三类数据由于与其它两类有特征交叉现象，很难被传统聚类算法准确识别，但本文的核空间二次蚂蚁聚类算法在此数据集上取得较为理想的结果。论文关键词：核函数,蚁群聚类,马赛克算法　　（一）引言　　聚类（clustering）分析已经广泛地用于许多应用领域。Deneubourg[2]等于1991年，根据蚂蚁堆积尸体的行为提出了基于蚂蚁的聚类基本模型(DM)，首次将蚁群算法应用于聚类分析。随后，Ramos等人提出了ACLUSTER算法[3]。ACLUSTER算法改进了以往蚂蚁聚类模型中蚂蚁的拾起和放下物体的策略，并且引入信息素模型指导人工蚂蚁的移动，避免了算法中蚂蚁过多地在无物体分布区域耗时的随机有哪些信誉好的足球投注网站，减少了时间开销；引入了对应于多种任务的响应阈值，使得人工蚂蚁在计算拾起或放下概率时考虑了周围的物体数量，更有利于形成簇；去掉了人工蚂蚁的记忆能力并取消了不同速度的蚂蚁，保持了算法模型的简单性，并减少了相应的计算时间和存储空间开销。这些改进有效地改善了聚类的效果，并能应用于文本聚类、图像模式识别、Web挖掘等任务。　　核函数方法能将原空间中的样本映射到未知的高维特征空间，从而优化样本特征，改善学习性能[。本文针对高维数据的特性，将核函数方法引入ACLUSTER蚁群聚类算法，将数据映射到高维特征空间进行聚类，该算法有效地把样本投影成一维的距离数据值，易于聚类。针对ACLUSTER算法收敛速度慢、形成簇过多等问题，本文提出新的聚类策略，通过使用不同参数设置的两次聚类对数据进行聚类。最后通过实验说明，二次快速蚁群聚类算法提高了算法的时间效率，并且改善了聚类的效果。　　（二）核空间两点距离的计算方法　　在原欧几里德空间中，数据对象X和Y之间的距离定义为：　　,其中n为对象的维数。　　将对象X，Y通过核函数映射到核空间，利用核的定义便可以推导在核空间中的距离。特征空间中的欧几里德距离可表示为：　　　　上式展开得：　　　　因为K(x,y)=φ(x)·φ(y)，所以将上式直接用核函数表示为：　　　　代入高斯径向基核函数，可推出特征空间中的欧几里德距离：　　　　即为每个物体的核距离值，决定了物体在聚类空间的位置。程序里使用该公式。　　参数Y、σ的选择：　　(1)Y选坐标原点，容易计算。　　(2)在根号下，因为有平方，X、σ取实数即大于或等于0，但如果σ太大，X变化小，趋于0，趋于1，得到的值的变化和1贴得紧；表达式得到的值就分不开，不易区分物体。如果σ太小，趋于0，同样不易区分物体的核距离值。根据经验，σ取X的中间值即（j,k是物体编号，i是属性号），即找出离原点最近的物体k,算出最小距离；找出离原点最远的物体j，算出最大距离；最小加上最大两个物体的距离，取一半为σ。　　求出每个物体的d(x,y)之后，将物体撒在矩阵上，采用Acluster方法聚类。　　（三）核空间二次蚁群聚类算法　　Acluster聚类结果得到的簇数量较多，得不到准确结果，这样就需要用二次聚类。收集聚类得到的结果，把它们整理出来，放到小空间聚类，方法采用马赛克算法。　　马赛克算法：将这个原25x25的矩阵压缩到13x13矩阵，将大矩阵中划分为2x2一组，每组压缩成新矩阵中1x1的格子，对应地放到新的小矩阵中。规则如下：　　(1)如果2x2的格子里没有或者只有一个物体，则新格子里没有物体。　　(2)如果有2个物体，则计算随机数，为0则新格子没物体，1则有物体，新物体的核距离值为两个物体的平均值，新标号也为平均值。　　(3)如果有3个或4个物体，则新格子里有物体，核距离值和标号都为均值。　　核空间二次蚁群聚类算法工作流程图如下：　　　　图1核空间二次蚁群聚类算法图　　（四）实验结果及分析　　实验平台：PC(配置：CPUIntelPentiumDual2.0GHz，内存DDR2G)，操作系统为WindowsServer2003EnterpriseEdition。算法使用MSVisualBasic.Net2008编程，数据库采用SQLServer2000实现。　　使用UCI数据集中的鸢尾花数据集，该数据集每一行有一朵鸢尾花的萼片长、萼片宽、花瓣长、花瓣宽的数值，一共有150行，分为3种类别：irissetosa（山鸢尾）、irisversicolour（变色鸢尾）、irisvirginica（维吉尼亚鸢尾），每类50行。数据集中