基于最大似然原理的分层聚类算法研究

由于本身结构的特点导致分层聚类算法聚类质量差。鉴于最大似然法在进化树重构领域的良好表现，本项目研究一种基于最大似然原理的分层聚类算法以解决现有分层聚类算法聚类质量差的问题。基于最大似然原理的分层聚类算法的整体结构不同于现有分层聚类算法，其基本思想是首先根据属性状态转换模型计算每一个可能的聚类结果(树状图)的最大似然值，然后从中选择最大似然值最大的一个作为最终结果。本项目首先研究一种属性状态转换模型；接下来由于基于最大似然原理的分层聚类算法的时间复杂度较高，建立一种基于免疫粒子群的分层聚类方法和一种基于分治策略的最大似然分层聚类方法。本项目的研究将会对分层聚类算法的研究做出积极的贡献。

聚类是进行数据分析的一种重要手段和方法。根据聚类过程的不同，聚类算法主要分为划分聚类和分层聚类两大类。与划分聚类算法相比，分层聚类算法具有得到的结果包含的信息更多、无须用户指定任何参数以及聚类过程是确定的，不需要任何回溯等优点。但是恰恰由于不能回溯，分层聚类算法聚类质量差。.另一方面，现有的聚类算法(包括划分聚类和分层聚类)，其基本策略都是通过距离函数将原始数据转换为表示两两距离的距离矩阵，然后再对距离矩阵做进一步处理。研究表明，采用不同的距离计算函数对聚类结果的影响很大，而且目前对于距离函数的选取也没有指导标准。尤其是对于用分类属性表示的聚类数据，很难找到合适的距离计算函数。而在实际应用中需要聚类的数据在很多情况下都是由分类属性表示的。通过本课题的研究，我们借鉴生物学中构建进化树的先进经验，利用最大似然法构建进化树的重要结论，提出了新的基于最大似然原理的分类属性数据分层聚类算法。该算法不仅能直接处理分类属性数据而不依赖于距离函数，并且克服了分层聚类不能回溯的缺点。测试结果表明新算法的聚类准确率均高于经典的ROCK算法和K-Modes算法。.为了进一步改善聚类效果，提出了两种启发式的最大似然层次聚类算法：基于免疫粒子群的分层聚类方法和基于分治策略的最大似然分层聚类方法，取得了较好的效果。