基于约束的高维数据聚类

Clustering, which helps to find natural structure of data, is an essential content of data minning and plays an important role in many fields. In recent years, massive high-dimensional data has been produced, which poses hugh challenge,called the curse of dimensionality, to traditional clustering algorithms. The challenge is mainly because that in high dimensional data, different clusters are embeded in different subpaces, and the tasks of finding subspaces and detecting clusters are circular dependent. To break the circular dependency, existing algorithms usually make some assumptions on the data set. However, these assumptions do not make sense in most situations. Through numerous studies, we have learned that constraint information could be used to break this kind of circular dependency. Nevertheless, research on constraint based high dimensional data clustering is just the beginning. The only few algorithms are all local improvements on existing unsupervised algorithms. They do not escape from making assumptions on the data set, thus could not really break the circular dependency. In this project, based on our previous results, we introduce the concept of correlation between constraints and subspaces to solve the circular dependency problem of high-dimensional data clustering. We also apply constraints to all procedures of clustering to gain high quality constaint based high-dimensional data clustering algorithms. We aim to solve the curse of dimensionality of high-dimensional data clustering, thus pave the way to establishing basic algorithmic and theoretical framework of constraint based high-dimensional data clustering.

聚类是数据挖掘的基本内容，它帮助发现数据的自然结构，在很多领域起重要作用。近年来产生的大量高维数据给传统聚类算法带来被称为维度灾难的巨大挑战，主要表现为：在高维数据中不同的簇对应于不同的子空间，发现子空间和发现簇这两个任务是循环依赖的。为了打破这种循环依赖关系，现有算法通常对数据集做某种假设，而这些假设在多数情况下是不成立的。通过前期大量研究，我们认识到约束信息可以用来打破这种循环依赖关系。但基于约束的高维数据聚类研究刚刚起步，仅有的几个算法都是对现有无监督算法的局部改进，没有摆脱对数据集的假设，即没有在真正意义上解决循环依赖这个根本问题。本项目在我们前期研究取得进展的基础上，通过引进约束与子空间相关度的概念来解决高维数据聚类的循环依赖问题，并将约束用于聚类的各个环节，获得基于约束的高维数据聚类高质量算法，解决高维数据聚类的维度灾难，为初步建立基于约束的高维数据聚类算法和理论体系奠定基础。

聚类是数据挖掘的基本内容，它帮助发现数据的自然结构，在很多领域起重要作用。近年来产生的大量高维数据给传统聚类算法带来被称为维度灾难的巨大挑战，主要现为：在高维数据中不同的簇对应于不同的子空间，发现子空间和发现簇这两个任务是循环依赖的。为了打破这种循环依赖关系，现有算法通常对数据集做某种假设，而这些假设在多数情况下是不成立的。通过前期大量研究，我们认识到约束信息可以用来打破这种循环依赖关系。但基于约束的高维数据聚类研究刚刚起步，仅有的几个算法都是对现有无监督算法的局部改进，没有摆脱对数据集的假设，即没有在真正意义上解决循环依赖这个根本问题。本项目目标在我们前期工作基础上，探索在不对数据集进行任何假设的条件下，用约束解决高维数据聚类中发现子空间和发现簇的循环依赖这个根本问题，并将约束用于高维数据聚类的各个环节，首先获得基于约束的类似CLIQUE 和PROCLUS 的基础性算法，再进一步发展若干基于约束的高质量高维数据聚类算法。最终本项目高维数据聚类、不确定数据聚类、多视角聚类和多任务聚类等方面取得了大量创新成果。主要创新成果包括： 1）提出基于约束的集成高维数据聚类算法；2）基于约束的高维不确定数据子空间聚类算法；3）提出新的基于密度的不确定数据聚类算法；4）提出基于非负矩阵分解的约束聚类；5）提出谱聚类Nystrom扩展抽样的增量方法和新的分析方法；6）提出聪明的多任务Bregman聚类和多任务核聚类算法；7）提出自适应多任务聚类问题和算法；8）提出多视角数据的局部线性重构算法；9）提出基于多流行正则化非负矩阵分解的多视角聚类算法；10）提出基于约束的不对应数据多视角聚类；11）提出多任务多视角聚类问题和算法。在TKDE、TKDD等国际期刊和IJCAI、AAAI等国际会议上发表论文28篇，由科学出版社出版专著《数据聚类》1部，获教育部自然科学二等奖。