相异度量的k-modes聚类算法研究

论文摘要

聚类分析是数据挖掘的重要研究内容,通过聚类,将繁琐大量的数据集有效的划分成为一系列的子类,使得同一子类中的对象彼此相似,而不同子类中的对象尽量相异性高。在众多的聚类方法中,基于划分的聚类算法是最常见的聚类方法,特别是经典的k-means算法被广泛应用于工业和科学的各个领域。k-means算法对于处理数值型数据有好的聚类效果,但是不能处理常见的字符型数据。因此,对于字符型数据聚类算法的探索和改进,是聚类分析领域重要的课题之一。针对k-means算法无法处理字符型数据这一问题,k-modes聚类算法对其进行了扩展。本文对字符型数据处理的聚类问题进行了研究,并对各种改进的k-modes算法进行了对比和分析。然而,传统k-modes聚类算法中相异度量方法不能反映对象间的潜在的相似关系,特别是当数据量很大或数据集很复杂时,不能更好的区分样本间的差异。本文针对以上问题,对相异度量方法进行了改进,使其能更好的强化类间的相异性。最后,在传统k-modes聚类算法的基础上提出了一种改进的k-modes聚类方法。论文主要工作有以下几个方面：（1）对研究内容的背景知识和基于划分的聚类方法研究现状进行了阐述。（2）介绍了传统聚类分析方法的分类情况,并对聚类分析中的数据结构、相异度度量以及聚类准则函数进行了描述。（3）对传统k-modes算法的思想以及算法过程进行了详细的阐述,并对其优缺点进行了分析。（4）针对原有相异度量不能反映类内部的相似性,本文定义了一个属性值函数,该函数描述了属性值对于该属性的重要性以及类中心对于某一属性的代表程度,量化了对象与属性的内在关系。并基于此提出了本文的相异度量方法,此方法反映出不同对象在相同属性值下的相异程度,强化了类内的相似性。（5）结合改进的相异度度量方法,提出了一种改进的k-modes聚类算法。通过实验对提出的新方法进行验证,实验结果表明,与传统的k-modes聚类方法和Ng提出的k-modes聚类算法相比,改进后的聚类算法有更好的聚类效果。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 算法研究背景和意义
• 1.2 基于划分的聚类方法研究现状
• 1.3 分类属性的研究现状
• 1.4 论文结构
• 第二章 聚类分析
• 2.1 聚类分析概述
• 2.2 传统聚类分析方法分类
• 2.2.1 基于划分的聚类方法
• 2.2.2 基于层次的聚类方法
• 2.2.3 基于密度的聚类方法
• 2.2.4 其他的聚类分析方法
• 2.3 聚类分析中的数据结构
• 2.4 聚类分析的相异度度量
• 2.4.1 聚类数据的标准化
• 2.4.2 聚类分析中的相异度度量
• 2.5 聚类分析中的聚类准则函数
• 2.6 本章小结
• 第三章 k-modes聚类算法分析
• 3.1 k-modes聚类算法介绍
• 3.1.1 k-modes聚类算法思想
• 3.1.2 k-modes聚类算法的相异度量函数
• 3.1.3 k-modes聚类算法的基本流程
• 3.2 传统k-modes算法的优缺点
• 3.3 现有k-modes算法的改进
• 3.3.1 现有基于k-modes算法的扩展算法
• 3.3.2 现有基于相异度度量改进的k-modes算法
• 3.4 本章小结
• 第四章 改进的k-modes聚类算法
• 4.1 一种新的相异度量方法
• 4.2 改进的相异度量k-modes聚类算法
• 4.2.1 改进后的算法思想
• 4.2.2 改进后的聚类准则函数
• 4.2.3 改进后的算法流程
• 4.3 实验及实验结果分析
• 4.3.1 实验环境和测试数据集
• 4.3.2 数据预处理
• 4.3.3 评价方法
• 4.3.4 实验结果分析
• 4.4 本章小结
• 第五章 总结与展望
• 5.1 总结
• 5.2 展望
• 参考文献
• 致谢
• 攻读硕士学位期间发表的学术论文目录