Efficient discriminative clustering via QR decomposition-based Linear Discriminant Analysis

摘要

Discriminative Clustering (DC) can effectively cluster high dimension data sets. It performs in the iterative Linear Discriminant Analysis (LDA) dimensionality reduction and clustering process. However, most existing algorithms for DC have high computational complexity and are not feasible to apply in practical problems. In order to improve the efficiency of DC, we first present a variant of QR decomposition based LDA (LDA/QR) algorithm by making a minor modification to it. The proposed algorithm inherits the high efficiency of the initial LDA/QR, and has a better adaptability to data due to its ability of making full use of the discriminative information in data. We also present an objective function for the proposed variant of LDA/QR, and the proposed variant of LDA/QR can solve this objective function approximately. We then combine the proposed variant of LDA/QR and K-means (KM) into a single clustering algorithm, and obtain an efficient algorithm for DC: LDA/QR guided KM (LDA/QR-KM). Finally, in order to make LDA/QR-KM escape local minima, we adopt anomalous cluster based intelligent KM (IKM) to initialize it. Extensive experiments on a collection of benchmark data sets are presented to show the effectiveness and efficiency of the proposed LDA/QR-KM algorithm.