论文部分内容阅读
受大自然启发,基于仿真蚂蚁的无监督聚类技术在处理许多聚类问题上面取得成功。基于群体智能的方法在处理数据分析的问题上体现出来的潜力,吸引了大批研究人员。过去的研究主要集中在算法性能的提高,收敛性的证明,函数优化,组合优化等方面。在这样的背景下,本文创造性的利用群体智能的想法进行数据的挖掘分析,丰富了群体智能的应用领域。半监督信息的两种类别:一是少量数据点被标记,二是少量数据点被must-link和cannot-link约束。针对这两类信息,我们提出蚂蚁约束聚类,给蚁群聚类算法框架扩展了可以处理先验信息的能力,同时也提出了新的约束分类模型:蚂蚁约束分类即蚁群直推学习。聚类和分类是数据挖掘领域中一个非常重要的数据分析手段。约束聚类和约束分类主要处理学习问题的方式间于无监督学习和监督学习。在现实世界中,获得无先验类属信息的数据相对而言是比较廉价的,而给出数据点的类属信息和相关性往往要付出昂贵的代价。于是在拥有少量先验信息的情况下,改善聚类结果成为迫切需要。通常这样的学习问题也被称为半监督学习。半监督学习在处理现实世界中的问题时,表现出了良好的作用。与监督学习相比要节约更多的成本,同时比起完全无监督的学习策略,又能提高可观的学习精度。在学术界也吸引着大量学者的关注。本论文的具体贡献如下:(1)蚂蚁约束聚类。针对半监督信息以约束对出现的情况,将蚂蚁睡眠模型扩展成能处理must-link和cannot-link约束信息的约束聚类框架。根据nust-link和cannot-link约束限制采取最大最小策略修正数据点的相似度矩阵,我们提出了朴素蚂蚁约束聚类方法以及引入了吸引子和排斥子处理约束信息,我们提出了约束移动的蚂蚁约束聚类方法。(2)启发式蚂蚁聚类算法及其约束聚类问题推广。对RWAC算法进行了扩展和改善,蚂蚁在网格上随机游走之前,引入了启发式游走策略,并在启发式游走策略的选择过程中采用了最近邻最远邻的思想,融入半监督约束信息而提出了速度和精度都更加优秀的启发式蚂蚁聚类算法,并推广到处理约束聚类。(3)蚂蚁约束分类。这是针对半监督信息以少量已标记数据点出现的情况,提出了新的蚂蚁约束分类框架。在数据点构成的无向完全图上,每个数据顶点分配蚂蚁进行自避免的随机游走,碰到已标记的顶点则停止游走并更新标号向量。由多个蚂蚁的协作完成约束分类或者直推学习的任务。