Projected and semi-supervised clustering for high-dimensional data

聚类是目前主要的无监督数据挖掘方法之一，在应用于自动化设备（如微阵列芯片、传感器、测井设备）大规模收集的高维数据集时面临严峻挑战。数据的稀疏性、全维空间中距离的小方差以及包含大量“不相关”或“随机”维度，使得使用具有常见全维（非）相似性度量的标准聚类算法通常不可能检测到有意义的聚类结构。有意义的结构可以通过考虑低维子空间来检测，或者通过考虑背景知识（通常作为一小部分数据点的“必须链接”或“不能链接”约束）来指导算法获得与该信息一致的特定聚类结构——在一定程度上覆盖在全维空间中派生的信息。

Clustering is one of the major unsupervised data mining methods facing severe challenges when applied to today's high-dimensional data sets, which are collected on a large scale by automatic equipment (e.g. microarray chips, sensors, logging devices). The sparsity of the data, the small variance of distances in the full-dimensional space, and the inclusion of a large number of "irrelevant" or "random" dimensions make it typically impossible to detect a meaningful clustering structure using standard clustering algorithms with common full-dimensional (dis-)similarity measures. Meaningful structure can rather be detected by either considering lower-dimensional subspaces, or, by taking into account background knowledge if it is available (often as "must-link" or "cannot-link" constraints for a small subset of data points) to guide an algorithm to a certain clustering structure that is consistent with this information - overriding to some extent the information derived in the full-dimensional space. Main objectives of the proposed research program: 1) Advancement of the theoretical understanding of clustering methods applied to today's very high-dimensional data sets, particularly for the following relatively recent approaches "projected (or subspace-) clustering" and "semi-supervised clustering". 2) Development of novel and improved algorithms for projected and semi-supervised clustering, overcoming some of their current limitations, extending their applicability, and also combining the concepts of both for a wider range of application areas where such clustering methods can be useful. 3) Demonstration of the usefulness of the proposed methods on some real world data sets including gene expression data, text data, and medical image plus clinical data.