基于算法选择的聚类统一框架研究

聚类分析是数据挖掘、模式识别、机器学习等研究领域对数据进行分析的重要工具之一。目前文献中各类聚类算法层出不穷，但通常一个算法只适合处理某类（或某几类）数据集，且用户对拟分析的数据并不具有先验知识，这导致实际应用中用户难以选择相对适合的聚类算法。研究者试图用多目标优化、集成学习等方法解决之，虽然这些方法在一定程度上提高了聚类方法的普适性，但仍存在方法复杂、稳定性差等缺点。本项目拟用算法选择的方法解决该问题。其思路为：1）构建经典聚类算法空间与典型数据集空间；2）建立数据集空间到算法空间的映射；3）定义数据集之间的相似性测度，并根据该测度将输入数据集分类，从而完成聚类算法的自动选择。其中最关键的科学问题是定义面向聚类算法的数据集之间的相似性测度。本项目的研究不仅仅为解决聚类算法的选择问题，还可以推广应用到分类算法的选择，并力争将聚类分析的框架成功应用到基因表达数据的处理。

1.项目背景.聚类分析是一个病态问题。提高算法普适性的方法有聚类集成与多目标优化。聚类集成的精确度依赖于初始聚类的质量，而多目标优化的聚类算法迄今也只有两个目标函数的优化（紧凑性及连接性），且即使这两个目标函数同时作用也不能处理所有数据集。本项目则试图从数据集的相似性度量入手，对给定数据集自动选择聚类算法。..2.主要研究内容.1）基于数据内在结构的数据集相似性度量.聚类算法的选择框架包含典型数据集空间、经典聚类算法空间及数据集相似性度量准则。其中，典型数据集空间是典型聚类问题集合；经典聚类算法空间是典型聚类问题较适合的聚类算法；数据集相似性度量则是数据集的空间变换、特征提取及相似性准则设计。.2）聚类集成关联矩阵.数据集的相似性度量需要进行空间变换，聚类集成是一个较好的选择。传统的聚类集成关联矩阵存在缺陷，本项目研究的主要研究内容之一是改进该矩阵。.3）最小生成树快速算法.最小生成树在一定程度上可以刻画数据集的骨架，但其算法复杂度不适合用于大规模数据。那么，最小生成树的快速算法是另一个研究内容。..3.重要结果.1）数据集关于聚类分析的相似性可从两方面度量：基于离散化与归一化的数据集变换的度量；基于K-means聚类集成的稳定性度量。.2）同一基类内，数据的同质性可不同；不同基类，数据的同质性也可不同。.3）快速近似最小生成树算法的计算复杂度可达O(N^1.5)。..4.关键数据.1）当离散与归一化后的数据集的相似性、基于K-means聚类集成稳定性的相似性权值分别为0.6与0.4时，算法推荐的精度最高（>=80%）。.2）关联矩阵分别在数据点的层级及基类的层级进行改进，相应的聚类结果在16个测试数据上排名第一。.3）快速近似最小生成树算法对低维数据边的平均错误率为2%，权值的平均错误率为3.5%；对高维数据边的平均错误率为18%，权值的平均错误率为3%。..5.科学意义.本项目的研究表明数据集从整体上具有面向聚类分析的结构特征，这为聚类分析指明了一个有别于传统聚类算法的研究方向，即聚类算法的自动选择。实验数据表明该方向是可行的，当然算法选择的精确度还待提高，还需要挖掘数据集关于聚类相似性的更多有效特征。