密度蚂蚁思想的Ｋ—Ｍｅａｎｓ算法的研究
ＯｎＫ－Ｍｅａｎｓｃｌｕｓｔｅｒｉｎｇａｎａｌｙｓｉｓｃｏｍｂｉｎｅｄｗｉｔｈａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ
何健，张聪
ＨＥＪｉａｎ．ＺＨＡＮＧＣｏｎｇ
（武汉工业学院计算机与信息工程系，武汉４３００２３）
摘要：遗传算法具有快速良好的全局搜索能力，而蚁群聚类算法具有良好的分布式并行性和正反馈能力。Ｋ—Ｍｅａｎｓ、基于密度的聚类是常见的基于分割的聚类方法，它在处理空间数据时具有快速、有效处理噪声点和发现任意形状的聚类等优点。聚类算法概述聚类分析是数据挖掘领域中的一项重要的研究课题，本文主要研究是将遗传算法，蚂蚁算法、Ｋ—Ｍｅａｎｓ算法、密度思想结合在一起，提出了一种基于密度蚂蚁思想的Ｋ—Ｍｅａｎｓ算法，采用密度函数法的多中心聚类并结合小类合并运算的聚类结果明显优于Ｋ－ｍｅａｎｓ的聚类结果，提高了聚类的质量。再结合密度思想，使蚂蚁有选择地遍历，提高了算法效率，并克服了基于密度的算法不能发现任意形状聚类的问题。
关键词：聚类分析；蚂蚁算法；Ｋ—Ｍｅａｎｓ；密度；数据
中图分类号：ＴＰ３９１文献标识码：Ａ文章编号：１００９－０１３４（２０１２）２（下）－０００１—０３Ｄｏｉ：１０．３９６９／Ｊ．ｉｓｓｎ．１００９－０１３４．２０１２．２（下）．０１
０引言
聚类就是将整个数据分成不同的组，并使组与组之间的差距尽可能大，组内数据的差异尽可能小。几种典型的聚类方法包括：划分方法ｋ一平均（ｋ－ｍｅａｎｓ）和ＰＡＭ、层次聚类方法ＡＧＮＥＳ和ＤＩＡＮＡ、密度聚类方法ＤＢＳＣＡＮ等等。
聚类分析是数据挖掘研究和应用中一个重要的部分。简单地讲，聚类分析就是将数据对象分组成多个类或簇（ｃｌｕｓｔｅｒ），在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。从机器学习的观点来看，聚类是一种无指导的学习，因为它没有关于分类的先验知识。从实际应用的观点来看，聚类分析在科学数据探测、图像处理、模式识别、医疗诊断、计算生物学、文档检索和Ｗｅｂ分析等领域起着非常重要的作用，它已经成为当前数据挖掘研究领域中一个非常活跃的研究课题。
１基于蚂蚁算法的Ｋ－ｍｅａｎｓ算法蚁群算法（ａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ）是最新发展的一种模拟蚂蚁群体智能行为的仿生优化算法Ｈ１，由意大利学者ＤｏｒｉｇｏＭ于１９９１年提出。从蚂蚁的这种自然行为上，很自然地联想到聚类，聚类是将数据库中的数据进行分类，同一类中的数据尽可能相似，不同类中的数据尽可能不同。运用基于蚂蚁的聚类算法对数据进行聚类，把数据分割成个小堆１，２，…，然后利用这个堆作为Ｋ—Ｍｅａｎｓ的输入，把堆＝１，２，…的中心作为初始的聚类中心，用Ｋ—Ｍｅａｎｓ算法进行聚类。
基于蚁群算法的聚类方法从原理上可以分为两种：一种是基于蚁堆形成原理来实现数据聚类，另一种是运用蚁群觅食的原理，利用信息素（ｐｈｅｒｏｍｏｎｅ）来实现聚类分析。基于蚂蚁算法的Ｋ—Ｍｅａｎｓ主要步骤如下：
１）用蚂蚁算法对数据进行聚类，把数据分割成个小堆１，２，…；
２）把第一步中的值作为Ｋ—Ｍｅａｎｓ的输入，把堆＝１，２，…的中心作为初始的聚类中心，用Ｋ＿］Ｖ［ｅａｎｓ算法进行聚类；
３）再一次运用基于蚂蚁的聚类算法，但是这次进行聚类的对象不是单个数据对象，而是对上两步形成的堆进行层次聚类；
敢稿日期：２０１１—０９—２３
基金项目：２０１０年湖北省教育厅科研项目：面向３Ｇ通信的移动音频关键技术研究（Ｄ２０１０１７０４）
作者简介：何健（１９７５一），男，湖北武汉人，本科，研究方向为成数据挖掘和信息检索。
第３４卷第２期２０１２—２（下）［１１万方数据