Automatic Model Selection in Subspace Clustering via Triplet Relationships

Jufeng Yang, Jie Liang, Kai Wang, Yongliang Yang, Ming-Ming Cheng

Abstract

This paper addresses both the model selection (i.e. estimating the number of clusters K ) and subspace clustering problems in a unified model. The real data always distribute on a union of low-dimensional sub-manifolds which are embedded in a high-dimensional ambient space. In this regard, the state-ofthe-art subspace clustering approaches firstly learn the affinity among samples, followed by a spectral clustering to generate the segmentation. However, arguably, the intrinsic geometrical structures among samples are rarely considered in the optimization process. In this paper, we propose to simultaneously estimate K and segment the samples according to the local similarity relationships derived from the affinity matrix. Given the correlations among samples, we define a novel data structure termed the Triplet, each of which reflects a high relevance and locality among three samples which are aimed to be segmented into the same subspace. While the traditional pairwise distance can be close between inter-cluster samples lying on the intersection of two subspaces, the wrong assignments can be avoided by the hyper-correlation derived from the proposed triplets due to the complementarity of multiple constraints. Sequentially, we propose to greedily optimize a new model selection reward to estimate K according to the correlations between inter-cluster triplets. We simultaneously optimize a fusion reward based on the similarities between triplets and clusters to generate the final segmentation. Extensive experiments on the benchmark datasets demonstrate the effectiveness and robustness of the proposed approach.
Original languageEnglish
Number of pages8
StateAccepted/In press - 2018
EventAAAI Conference on Artificial Intelligence 2018 -

Conference

ConferenceAAAI Conference on Artificial Intelligence 2018
Period2/02/187/02/18

Fingerprint

Data structures
Fusion reactions
Experiments

Cite this

Yang, J., Liang, J., Wang, K., Yang, Y., & Cheng, M-M. (2018). Automatic Model Selection in Subspace Clustering via Triplet Relationships. Paper presented at AAAI Conference on Artificial Intelligence 2018, .

Automatic Model Selection in Subspace Clustering via Triplet Relationships. / Yang, Jufeng; Liang, Jie; Wang, Kai; Yang, Yongliang; Cheng, Ming-Ming.

2018. Paper presented at AAAI Conference on Artificial Intelligence 2018, .

Research output: Contribution to conferencePaper

Yang, J, Liang, J, Wang, K, Yang, Y & Cheng, M-M 2018, 'Automatic Model Selection in Subspace Clustering via Triplet Relationships' Paper presented at AAAI Conference on Artificial Intelligence 2018, 2/02/18 - 7/02/18, .
Yang J, Liang J, Wang K, Yang Y, Cheng M-M. Automatic Model Selection in Subspace Clustering via Triplet Relationships. 2018. Paper presented at AAAI Conference on Artificial Intelligence 2018, .

Yang, Jufeng; Liang, Jie; Wang, Kai; Yang, Yongliang; Cheng, Ming-Ming / Automatic Model Selection in Subspace Clustering via Triplet Relationships.

2018. Paper presented at AAAI Conference on Artificial Intelligence 2018, .

Research output: Contribution to conferencePaper

@misc{4ac9d9e851504a849ccbf1042932c7e2,
title = "Automatic Model Selection in Subspace Clustering via Triplet Relationships",
abstract = "This paper addresses both the model selection (i.e. estimating the number of clusters K ) and subspace clustering problems in a unified model. The real data always distribute on a union of low-dimensional sub-manifolds which are embedded in a high-dimensional ambient space. In this regard, the state-ofthe-art subspace clustering approaches firstly learn the affinity among samples, followed by a spectral clustering to generate the segmentation. However, arguably, the intrinsic geometrical structures among samples are rarely considered in the optimization process. In this paper, we propose to simultaneously estimate K and segment the samples according to the local similarity relationships derived from the affinity matrix. Given the correlations among samples, we define a novel data structure termed the Triplet, each of which reflects a high relevance and locality among three samples which are aimed to be segmented into the same subspace. While the traditional pairwise distance can be close between inter-cluster samples lying on the intersection of two subspaces, the wrong assignments can be avoided by the hyper-correlation derived from the proposed triplets due to the complementarity of multiple constraints. Sequentially, we propose to greedily optimize a new model selection reward to estimate K according to the correlations between inter-cluster triplets. We simultaneously optimize a fusion reward based on the similarities between triplets and clusters to generate the final segmentation. Extensive experiments on the benchmark datasets demonstrate the effectiveness and robustness of the proposed approach.",
author = "Jufeng Yang and Jie Liang and Kai Wang and Yongliang Yang and Ming-Ming Cheng",
year = "2018",

}

TY - CONF

T1 - Automatic Model Selection in Subspace Clustering via Triplet Relationships

AU - Yang,Jufeng

AU - Liang,Jie

AU - Wang,Kai

AU - Yang,Yongliang

AU - Cheng,Ming-Ming

PY - 2018

Y1 - 2018

N2 - This paper addresses both the model selection (i.e. estimating the number of clusters K ) and subspace clustering problems in a unified model. The real data always distribute on a union of low-dimensional sub-manifolds which are embedded in a high-dimensional ambient space. In this regard, the state-ofthe-art subspace clustering approaches firstly learn the affinity among samples, followed by a spectral clustering to generate the segmentation. However, arguably, the intrinsic geometrical structures among samples are rarely considered in the optimization process. In this paper, we propose to simultaneously estimate K and segment the samples according to the local similarity relationships derived from the affinity matrix. Given the correlations among samples, we define a novel data structure termed the Triplet, each of which reflects a high relevance and locality among three samples which are aimed to be segmented into the same subspace. While the traditional pairwise distance can be close between inter-cluster samples lying on the intersection of two subspaces, the wrong assignments can be avoided by the hyper-correlation derived from the proposed triplets due to the complementarity of multiple constraints. Sequentially, we propose to greedily optimize a new model selection reward to estimate K according to the correlations between inter-cluster triplets. We simultaneously optimize a fusion reward based on the similarities between triplets and clusters to generate the final segmentation. Extensive experiments on the benchmark datasets demonstrate the effectiveness and robustness of the proposed approach.

AB - This paper addresses both the model selection (i.e. estimating the number of clusters K ) and subspace clustering problems in a unified model. The real data always distribute on a union of low-dimensional sub-manifolds which are embedded in a high-dimensional ambient space. In this regard, the state-ofthe-art subspace clustering approaches firstly learn the affinity among samples, followed by a spectral clustering to generate the segmentation. However, arguably, the intrinsic geometrical structures among samples are rarely considered in the optimization process. In this paper, we propose to simultaneously estimate K and segment the samples according to the local similarity relationships derived from the affinity matrix. Given the correlations among samples, we define a novel data structure termed the Triplet, each of which reflects a high relevance and locality among three samples which are aimed to be segmented into the same subspace. While the traditional pairwise distance can be close between inter-cluster samples lying on the intersection of two subspaces, the wrong assignments can be avoided by the hyper-correlation derived from the proposed triplets due to the complementarity of multiple constraints. Sequentially, we propose to greedily optimize a new model selection reward to estimate K according to the correlations between inter-cluster triplets. We simultaneously optimize a fusion reward based on the similarities between triplets and clusters to generate the final segmentation. Extensive experiments on the benchmark datasets demonstrate the effectiveness and robustness of the proposed approach.

M3 - Paper

ER -