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.