作为数据挖掘中重要的技术一聚类分析,它按照相似原则将数据进行分类.在无监督学习下,聚类的最终结果是将海量的数据有效地划分为各个子类,使得同一个类别中数据对象的相异度尽可能低,不同类别中数据对象的相异度尽可能高.目前,数值型数据的聚类已经取得较好的成果了,如经典的k-means算法已得到广泛的应用和推广.然而在实际生活中,存在大量的分类型数据.由于分类型数据不具有数值型数据的几何特性,所以无法直接进行数值运算.于是,分类型数据的聚类相对来说就变得比较复杂,它是学习算法中重要而又棘手的问题之一.近年来,许多学者针对分类型数据的聚类进行了探索和改进.针对k-means算法不适用于分类型数据这一问题,k-modes算法在此基础上进行了拓展.本文针对了k-modes聚类算法中的若干问题进行了研究,并对比和分析了现有的各种改进后的k-modes算法.传统的k-modes算法采用0-1匹配方法定义每两个对象属性之间的距离,不仅没有将整个数据集的分布考虑进来,而且忽视了属性间的相互关系对距离的影响,导致差异度度量不够准确.针对以上问题,本文的研究成果主要有以下几个方面：(1)从互信息的角度出发,基于相互依存冗余理论定义了同一属性下不同属性值之间的距离,进一步改进了Hong jia提出的距离公式.改进后的距离由内部距离和外部距离两个部分决定,内部距离体现了每两个对象属性值本身的差异度,外部距离体现了其他属性对该属性的影响程度.(2)本文将基于相互依存冗余的距离应用于k-modes算法中,并分析了改进后算法的时间复杂度.与基于其他距离度量的k-modes算法进行实验比较,结果表明基于相互依存冗余度量的k-modes算法不仅能有效处理大规模数据,而且能有效提高算法的聚类精度.(3)从属性值共现的思想出发,基于结构相似性计算模型给出一种新的相异度度量方法,并将其应用于传统的k-modes算法,同时分析了改进后算法的时间复杂度.该方法不仅考虑了属性值它们本身的异同,而且考虑了它们在其他属性下所处的状态.实验结果表明,与传统的k-modes算法和Ahmad算法相比,基于新的相异度度量的k-modes算法不仅具有较好的集群识别能力,而且提高了聚类效果.本文的研究成果不仅丰富了分类型数据相异度度量的研究,而且在一定程度上为分类型数据的聚类提供了新的方法支持.