1 Introduction
-
Using the local best-fit heuristic, we introduce the LBF and SLBF algorithms for HLM. At each point of a randomly chosen subset of the data, they use the best-fit flats of the “optimal” neighborhoods to build a global model with different methods (LBF is based on energy minimization and SLBF is a spectral method).
-
We perform extensive experiments on motion segmentation data (the Hopkins 155 benchmark of Tron and Vidal (2007)), face clustering (the extended Yale face database B), handwritten digits (the MNIST database), and artificial data, showing that both algorithms, in particular SLBF, are accurate on real and synthetic HLM problems, while LBF runs extremely fast (often on the order of ten times faster than most of the previously mentioned methods). For the cropped face data we actually indicate a fundamental problem of local methods like LBF and SLBF, though suggest a workaround that works for this particular data.
-
We demonstrate how the local best-fit heuristic can be used with other algorithms. In particular, we give experimental evidence to show that the K-flats algorithm (Ho et al. 2003) is improved by initialization that is based on the local best-fit heuristic. We also use this heuristic to estimate the main parameters of both RANSAC (for HLM) (Yang et al. 2006) and ALC (Ma et al. 2007).
-
We show how the combination of LBF and the elbow method can quickly determine the number of subspaces.
2 The Local Best-Fit Flats Heuristic and the LBF and SLBF Algorithms
2.1 Choosing the Optimal Neighborhood
2.1.1 Theoretical Justification
2.1.2 The Complexity of Algorithm 1
2.2 The LBF Algorithm
2.2.1 The Complexity and Storage of Algorithm 2
2.3 The SLBF Algorithm
2.3.1 Complexity and Storage of the SLBF Algorithm
2.4 Adaptation of the Proposed Algorithms to Motion Segmentation Data
3 Experimental Results
3.1 Clustering Results on Artificial Data
Linear | 22∈ℝ4
| 42∈ℝ6
| 24∈ℝ4
| 102∈ℝ15
| (4,5,6)∈ℝ10
| (1,5)∈ℝ6
| |||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Outl. % | 0 | 30 | 0 | 30 | 0 | 30 | 0 | 30 | 0 | 30 | 0 | 30 | |
LSCC |
e % | 2.6 | 6.9 |
0.0
| 2.6 |
0.1
| 22.4 | 0.5 | 3.8 | 1.8 | 28.2 | N/A | 34.6 |
t(s) | 1.1 | 0.8 | 1.0 | 1.8 | 1.5 | 2.0 | 13.3 | 5.7 | 5.1 | 8.4 | N/A | 1.9 | |
LSCC-MS |
e % | 2.7 |
10.0
|
0.0
| 4.1 |
0.1
| 36.7 | 0.7 | 31.9 | 1.4 | 19.8 | N/A | 32.9 |
t(s) | 1.1 | 0.5 | 1.1 | 1.4 | 1.7 | 1.5 | 5.1 | 5.6 | 4.0 | 4.6 | N/A | 2.0 | |
LSA |
e % | 18.4 | 19.6 | 0.1 | 12.7 | 0.4 | 21.0 | 0.1 | 9.9 | 5.9 | 6.6 | 27.4 | 35.4 |
t(s) | 6.8 | 16.0 | 7.1 | 20.8 | 23.8 | 54.4 | 11.7 | 31.5 | 20.1 | 54.4 | 6.6 | 13.8 | |
KF |
e % |
2.5
| 15.8 | 2.5 | 18.4 |
0.1
| 34.3 |
0.0
| 33.8 |
1.0
| 30.6 | 20.2 | 23.5 |
t(s) | 0.5 | 0.6 | 0.2 | 0.8 | 0.7 | 1.8 | 0.4 | 1.0 |
0.7
| 2.8 | 0.3 | 0.5 | |
MoPPCA |
e % |
2.5
| 14.2 |
0.0
| 17.7 |
0.1
| 34.2 |
0.0
| 38.8 | 1.6 | 34.7 | 23.4 | 24.0 |
t(s) | 0.3 | 0.5 | 0.2 | 0.7 | 0.7 | 2.0 |
0.2
| 1.1 | 1.1 | 3.3 | 0.5 | 0.5 | |
GPCA |
e % | 6.0 |
2.5
|
0.0
|
2.0
|
0.1
|
6.3
|
0.0
| 14.6 | 14.6 | N/A | 5.9 | N/A |
t(s) | 2.1 | 38.0 | 1.9 | 85.2 | 10.8 | 136.2 | 11.2 | 546.0 | 73.8 | N/A | 0.7 | N/A | |
LBF |
e % | 2.8 | 3.7 |
0.0
| 2.3 |
0.1
| 11.5 |
0.0
|
1.9
| 1.5 |
1.5
| 18.8 | 14.1 |
t(s) | 0.6 | 0.5 | 0.5 | 0.5 | 1.8 | 2.7 | 0.6 | 0.8 | 1.1 | 1.4 | 0.5 | 0.5 | |
LBF-MS |
e % | 2.7 | 3.0 |
0.0
| 2.6 |
0.1
| 11.7 |
0.0
| 2.2 | 1.3 |
1.5
| 19.5 | 13.7 |
t(s) | 0.6 | 0.5 | 0.4 | 0.5 | 1.7 | 2.6 | 0.4 |
0.6
| 0.9 |
1.3
|
0.4
| 0.4 | |
SLBF |
e % | 5.2 | 6.3 | 0.1 | 7.0 |
0.1
| 23.9 |
0.0
| 6.2 | 2.0 | 2.4 | 11.1 | 13.5 |
t(s) | 11.2 | 20.7 | 9.4 | 21.7 | 65.0 | 174.9 | 9.5 | 23.3 | 23.2 | 64.2 | 9.3 | 15.3 | |
SLBF-MS |
e % | 7.8 | 11.7 | 0.1 | 6.6 | 0.2 | 46.6 |
0.0
| 4.8 | 1.9 | 2.6 | 19.7 | 22.1 |
t(s) | 12.0 | 24.0 | 8.8 | 24.4 | 68.1 | 202.0 | 8.4 | 23.5 | 22.0 | 72.4 | 9.8 | 16.3 | |
RANSAC (oracle) |
e % | 2.7 | 2.6 | 2.9 | 2.1 | 8.0 | 9.4 | 0.5 | 5.8 | 1.7 | 1.5 | N/A | 31.6 |
t(s) |
0.1
|
0.1
|
0.1
|
0.2
|
0.1
|
0.2
| 5.9 | 6.7 | 1.5 | 7.1 | N/A |
0.2
| |
RANSAC (ϵ from LBF) |
e % | 3.2 | 2.6 | 2.1 | 2.4 | 7.7 | 9.8 | 0.4 | 6.7 | 1.8 |
1.5
| N/A | 30.6 |
t(s) |
0.1
|
0.1
|
0.1
|
0.2
|
0.1
|
0.2
| 5.9 | 6.7 | 1.5 | 7.0 | N/A | 0.3 | |
ALC (oracle) |
e % | 4.1 | 3.4 | 0.1 | 16.3 |
0.1
| 30.1 | 50.0 | 50.0 | 5.4 | 36.1 |
0.3
| 0.4 |
t(s) | 7.3 | 23.2 | 7.7 | 33.6 | 28.4 | 136.3 | 13.9 | 172.6 | 23.0 | 180.1 | 7.8 | 17.3 | |
ALC (ϵ from LBF) |
e % | 4.5 | 5.7 | 0.1 | 10.0 |
0.1
| 14.0 | 50.0 | 50.0 | 2.5 | 1.8 | 0.4 |
0.3
|
t(s) | 8.0 | 28.0 | 8.1 | 37.9 | 29.6 | 121.9 | 16.6 | 152.4 | 24.0 | 151.6 | 8.3 | 18.1 | |
SSC |
e % | 19.5 | 34.3 | 0.2 | 43.5 | 0.4 | 52.8 | 47.0 | 44.9 | 11.5 | 54.0 | 9.4 | 15.9 |
t(s) | 114.8 | 236.2 | 97.6 | 247.9 | 227.7 | 591.3 | 106.0 | 276.6 | 185.5 | 437.9 | 94.1 | 142.1 | |
SCC |
e % |
0.0
| 0.6 |
0.0
|
0.0
|
0.0
| 0.5 |
0.0
| 0.7 |
0.0
| 5.8 | N/A | N/A |
t(s) | 1.2 | 1.0 | 1.1 | 2.0 | 1.4 | 2.5 | 6.1 | 13.7 | 5.6 | 6.0 | N/A | N/A | |
SCC-MS |
e % |
0.0
| 2.2 |
0.0
| 0.5 |
0.0
| 5.8 |
0.0
|
0.0
|
0.0
| 3.1 | N/A | N/A |
t(s) | 1.2 | 0.7 | 1.2 | 1.6 | 1.7 | 2.2 | 5.4 | 6.0 | 4.6 | 4.8 | N/A | N/A | |
LSA |
e % | 0.1 | 11.0 |
0.0
| 4.7 | 0.4 | 41.7 |
0.0
|
0.0
|
0.0
| 1.1 | 37.5 | 37.9 |
t(s) | 6.7 | 16.1 | 7.1 | 20.8 | 22.2 | 54.0 | 11.7 | 32.2 | 38.3 | 54.0 | 6.6 | 13.9 | |
KF |
e % | 0.2 | 15.1 | 0.1 | 26.0 | 0.3 | 37.1 |
0.0
| 24.9 |
0.0
| 23.5 | 24.8 | 27.1 |
t(s) | 0.8 | 0.6 | 0.4 | 0.7 | 1.0 | 1.4 | 0.6 | 1.7 |
1.0
| 1.4 | 0.5 |
0.5
| |
MoPPCA |
e % | 0.2 | 23.7 | 0.1 | 38.3 | 0.5 | 39.8 |
0.0
| 45.2 |
0.0
| 46.8 | 30.8 | 30.4 |
t(s) | 0.9 | 0.5 | 0.5 | 0.6 | 1.1 | 1.4 | 0.9 | 1.9 | 1.9 | 2.0 | 0.5 |
0.5
| |
GPCA |
e % | 0.2 | 18.4 | 0.2 | 22.2 | 0.4 | 38.1 |
0.0
| 27.9 | 0.3 | N/A | N/A | N/A |
t(s) | 1.8 | 43.7 | 3.3 | 104.0 | 8.3 | 209.3 | 11.8 | 501.1 | 69.1 | N/A | N/A | N/A | |
LBF |
e % |
0.0
| 2.0 |
0.0
| 0.7 |
0.0
| 4.5 |
0.0
| 0.3 |
0.0
|
0.0
| 4.7 | 11.2 |
t(s) | 0.7 | 0.6 | 0.5 | 0.6 | 1.9 | 2.8 | 0.6 | 0.8 | 1.2 | 1.5 |
0.4
| 0.5 | |
LBF-MS |
e % |
0.0
| 2.7 |
0.0
| 1.5 |
0.0
| 5.2 |
0.0
| 0.5 |
0.0
|
0.0
| 3.9 | 10.5 |
t(s) | 0.6 | 0.5 | 0.4 |
0.5
| 1.7 | 2.7 |
0.4
|
0.6
|
1.0
|
1.3
|
0.4
|
0.4
| |
SLBF |
e % |
0.0
| 1.0 |
0.0
|
0.0
|
0.0
|
0.1
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
t(s) | 9.3 | 19.1 | 5.8 | 19.0 | 37.7 | 143.1 | 6.3 | 19.4 | 35.1 | 61.4 | 5.9 | 14.8 | |
SLBF-MS |
e % |
0.0
| 0.1 |
0.0
|
0.0
|
0.0
|
0.1
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
t(s) | 8.8 | 21.7 | 5.6 | 21.9 | 38.0 | 175.5 | 5.9 | 21.1 | 40.1 | 66.7 | 5.9 | 14.3 | |
RANSAC (oracle) |
e % | 13.8 | 11.6 | 9.8 | 9.6 | 30.9 | 27.0 | 1.9 | 8.3 | 1.2 | 3.4 | N/A | 23.6 |
t(s) |
0.1
|
0.2
|
0.4
| 1.8 |
0.4
|
0.8
| 6.4 | 6.8 | 3.7 | 7.4 | N/A |
0.5
| |
RANSAC (ϵ from LBF) |
e % | 13.6 | 11.6 | 11.6 | 10.4 | 29.9 | 28.5 | 1.4 | 9.6 | 1.2 | 2.4 | N/A | 23.1 |
t(s) |
0.1
|
0.2
|
0.4
| 1.9 |
0.4
|
0.8
| 6.4 | 6.7 | 3.7 | 7.4 | N/A |
0.5
| |
ALC (oracle) |
e % |
0.0
|
0.0
|
0.0
|
0.0
|
0.0
| 25.1 |
0.0
| 40.0 |
0.0
| 65.0 |
0.0
|
0.0
|
t(s) | 17.6 | 25.2 | 16.6 | 39.1 | 64.2 | 119.3 | 20.0 | 43.0 | 39.7 | 92.7 | 18.3 | 36.8 | |
ALC (ϵ from LBF) |
e % |
0.0
| 0.4 |
0.0
|
0.0
|
0.0
| 0.3 |
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
t(s) | 18.7 | 26.8 | 17.2 | 29.8 | 65.2 | 113.6 | 24.4 | 55.5 | 47.9 | 85.2 | 18.8 | 38.9 | |
SSC |
e % |
0.0
| 1.9 |
0.0
| 0.1 | 0.1 | 6.4 |
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
t(s) | 135.9 | 226.8 | 176.0 | 134.7 | 283.8 | 592.4 | 187.0 | 311.9 | 338.6 | 504.1 | 127.1 | 183.9 |
3.2 Clustering Results on Motion Segmentation Data
Checker | Traffic | Articulated | All | |||||
---|---|---|---|---|---|---|---|---|
Mean | Median | Mean | Median | Mean | Median | Mean | Median | |
2-motion | ||||||||
GPCA | 6.09 | 1.03 | 1.41 |
0.00
| 2.88 |
0.00
| 4.59 | 0.38 |
LLMC 5 | 4.37 |
0.00
| 0.84 |
0.00
| 6.16 | 1.37 | 3.62 |
0.00
|
LSA 4K
| 2.57 | 0.27 | 5.43 | 1.48 | 4.10 | 1.22 | 3.45 | 0.59 |
LBF(4K,3) | 3.65 |
0.00
| 3.89 |
0.00
| 4.43 | 0.15 | 3.78 |
0.00
|
LBF-MS(4K,3) | 2.90 |
0.00
| 1.64 |
0.00
| 2.51 | 0.06 | 2.54 |
0.00
|
SLBF(2F,3) | 1.59 |
0.00
|
0.20
|
0.00
|
0.80
|
0.00
| 1.16 |
0.00
|
SLBF-MS(2F,3) |
1.28
|
0.00
| 0.21 |
0.00
| 0.94 |
0.00
|
0.98
|
0.00
|
SCC(4K,3) | 2.42 |
0.00
| 4.44 |
0.00
| 9.51 | 2.04 | 3.60 |
0.00
|
SCC-MS(4K,3) | 2.00 |
0.00
| 0.35 |
0.00
| 4.11 | 1.12 | 1.77 |
0.00
|
SSC-N(4K,3) | 1.29 |
0.00
| 0.29 |
0.00
| 0.97 |
0.00
| 1.00 |
0.00
|
MSL | 4.46 |
0.00
| 2.23 |
0.00
| 7.23 |
0.00
| 4.14 |
0.00
|
RANSAC | 6.52 | 1.75 | 2.55 | 0.21 | 7.25 | 2.64 | 5.56 | 1.18 |
3-motion | ||||||||
GPCA | 31.95 | 32.93 | 19.83 | 19.55 | 16.85 | 28.66 | 28.66 | 28.26 |
LLMC 4K
| 12.01 | 9.22 | 7.79 | 5.47 | 9.38 | 9.38 | 11.02 | 6.81 |
LLMC 5 | 10.70 | 9.21 | 2.91 |
0.00
| 5.60 | 5.60 | 8.85 | 3.19 |
LSA 4K
| 5.80 | 1.77 | 25.07 | 23.79 | 7.25 | 7.25 | 9.73 | 2.33 |
LSA 5 | 30.37 | 31.98 | 27.02 | 34.01 | 23.11 | 23.11 | 29.28 | 31.63 |
LBF(4K,3) | 8.50 | 1.26 | 16.31 | 13.52 | 20.75 | 20.75 | 10.77 | 1.70 |
LBF-MS(4K,3) | 6.97 | 1.15 | 7.06 | 0.62 | 21.38 | 21.38 | 7.81 | 0.98 |
SLBF(2F,3) | 4.57 | 0.94 | 0.38 |
0.00
| 2.66 | 2.66 | 3.63 | 0.64 |
SLBF-MS(2F,3) | 3.33 | 0.39 |
0.24
|
0.00
|
2.13
|
2.13
| 2.64 |
0.22
|
SCC(4K,3) | 7.80 | 1.04 | 8.05 | 2.37 | 7.07 | 7.07 | 7.81 | 0.67 |
SCC-MS(4K,3) | 6.28 | 0.80 | 4.09 | 0.58 | 7.22 | 7.22 | 5.89 | 0.68 |
SSC-N(4K,3) |
3.22
|
0.29
| 0.53 |
0.00
|
2.13
|
2.13
|
2.62
|
0.22
|
MSL | 10.38 | 4.61 | 1.80 |
0.00
| 2.71 | 2.71 | 8.23 | 1.76 |
RANSAC | 25.78 | 26.01 | 12.83 | 11.45 | 21.38 | 21.38 | 22.94 | 22.03 |
Checker | Traffic | Articulated | All | |||||
---|---|---|---|---|---|---|---|---|
Mean | Median | Mean | Median | Mean | Median | Mean | Median | |
2-motion | ||||||||
LBF(4K,3) | 0.71 |
0.00
| 1.22 |
0.00
| 1.04 | 0.66 | 0.50 |
0.00
|
LBF-MS(4K,3) | 0.53 |
0.00
| 1.06 |
0.00
| 1.14 | 0.28 | 0.47 |
0.00
|
WLBF(4K,3) | 0.53 |
0.00
| 0.98 |
0.00
| 1.35 |
0.00
| 0.47 |
0.00
|
SLBF-MS(4K,3) |
0.00
|
0.00
|
0.00
|
0.00
|
0.00
|
0.00
|
0.00
|
0.00
|
SCC(4K,3) | 0.27 |
0.00
| 1.51 |
0.00
| 2.34 | 1.52 | 0.38 |
0.00
|
SCC-MS(4K,3) | 0.33 |
0.00
| 0.25 |
0.00
| 1.03 | 0.46 | 0.25 |
0.00
|
SSC-N(4K,3) |
0.00
|
0.00
|
0.00
|
0.00
|
0.00
|
0.00
|
0.00
|
0.00
|
3-motion | ||||||||
LBF(4K,3) | 1.52 | 0.58 | 3.71 | 9.69 | 7.37 | 7.37 | 1.43 | 0.65 |
LBF-MS(4K,3) | 1.48 | 0.45 | 3.81 | 2.35 | 6.59 | 6.59 | 1.42 | 0.40 |
SLBF(4K,3) |
0.00
|
0.00
|
0.00
|
0.00
|
0.00
|
0.00
|
0.00
|
0.00
|
SLBF-MS(4K,3) |
0.00
|
0.00
|
0.00
|
0.00
|
0.00
|
0.00
|
0.00
|
0.00
|
SCC(4K,3) | 1.20 | 0.53 | 5.70 | 7.00 | 1.77 | 1.77 | 1.43 | 0.49 |
SCC-MS(4K,3) | 0.94 | 0.50 | 3.25 | 0.54 | 2.54 | 2.54 | 0.92 | 0.33 |
SSC-N(4K,3) |
0.00
|
0.00
|
0.00
|
0.00
|
0.00
|
0.00
|
0.00
|
0.00
|
RANSAC | LBF-MS(4K,3) | LBF(4K,3) | SCC-MS(4K,3) | SLBF-MS(2F,3) | SLBF(2F,3) | SSC-N(4K,3) |
---|---|---|---|---|---|---|
60 s | 73 s | 91 s | 196 s | 28 min | 31 min | 427 min |
3.3 Clustering Results on the Extended Yale Face Database B
K
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
---|---|---|---|---|---|---|---|---|---|---|
LBF (without whitening) |
e % | 32.49 | 54.42 | 57.45 | 56.00 | 56.24 | 56.94 | 59.53 | 59.66 | 60.74 |
t(s) | 0.24 | 0.48 | 0.82 | 1.26 | 1.93 | 2.97 | 4.18 | 5.81 | 8.05 | |
LBF-MS (without whitening) |
e % | 18.27 | 36.22 | 48.24 | 50.18 | 49.99 | 50.68 | 53.08 | 54.06 | 54.73 |
t(s) | 0.12 | 0.21 | 0.36 | 0.57 | 0.89 | 1.41 | 2.06 | 2.98 | 4.13 | |
LBF |
e % | 7.94 | 8.33 | 12.89 | 17.83 | 27.40 | 31.89 | 35.04 | 38.53 | 38.95 |
t(s) | 0.24 | 0.50 | 0.87 | 1.38 | 2.09 | 3.28 | 4.58 | 6.38 | 8.57 | |
LBF-MS |
e % | 8.40 | 9.51 | 12.18 | 15.57 | 19.18 | 22.88 | 27.20 | 30.39 | 33.17 |
t(s) |
0.12
|
0.22
|
0.37
|
0.58
|
0.89
|
1.41
|
2.07
|
2.94
|
4.02
| |
SLBF |
e % | 11.12 | 14.78 | 20.42 | 26.52 | 32.96 | 36.91 | 40.49 | 42.99 | 46.63 |
t(s) | 4.17 | 12.72 | 25.70 | 44.89 | 72.99 | 111.58 | 165.47 | 226.56 | 310.30 | |
SLBF-MS |
e % | 9.12 | 12.48 | 18.61 | 25.27 | 30.50 | 33.97 | 36.22 | 38.66 | 41.44 |
t(s) | 3.84 | 12.20 | 23.88 | 41.24 | 64.10 | 95.73 | 142.09 | 192.34 | 262.40 | |
ALC (voting with K) |
e % |
3.46
|
6.08
| 14.59 | 29.59 | 67.06 | 69.04 | 76.00 | 73.94 | 77.16 |
t(s) | 42.99 | 122.29 | 258.20 | 451.07 | 699.52 | 1090.96 | 1625.10 | 2384.69 | 3343.93 | |
ALC (ϵ from LBF) |
e % | 10.43 | 15.23 | 32.20 | 42.15 | 58.10 | 62.54 | 70.84 | 81.14 | 84.25 |
t(s) | 0.95 | 2.49 | 5.54 | 11.54 | 24.38 | 45.27 | 78.05 | 132.35 | 211.15 | |
SCC |
e % | 5.39 | 11.82 | 29.39 | 41.96 | 49.56 | 54.51 | 55.49 | 57.24 | 58.94 |
t(s) | 1.62 | 3.85 | 9.52 | 15.37 | 22.71 | 32.45 | 54.54 | 56.91 | 75.92 | |
SCC-MS |
e % | 4.51 | 15.05 | 36.00 | 51.68 | 59.66 | 64.15 | 68.71 | 71.18 | 74.01 |
t(s) | 1.62 | 4.20 | 9.28 | 14.49 | 22.08 | 31.71 | 54.21 | 56.99 | 73.10 | |
SSC |
e % | 6.45 | 8.10 |
10.04
|
10.32
|
11.02
|
11.85
|
12.47
|
13.41
|
15.44
|
t(s) | 28.36 | 46.45 | 67.11 | 92.75 | 128.46 | 182.65 | 259.66 | 340.12 | 612.21 | |
K-flats |
e % | 7.20 | 12.12 | 19.06 | 26.77 | 32.59 | 35.18 | 38.58 | 42.00 | 44.40 |
t(s) | 0.16 | 0.37 | 0.76 | 1.29 | 2.14 | 3.25 | 5.18 | 6.91 | 9.60 |
Real K
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|
LBF (without whitening) | 20.46 | 14.73 | 4.87 | 3.89 | 5.54 | 4.99 | 4.63 | 3.95 | 3.22 |
LBF-MS (without whitening) | 18.23 | 18.77 | 13.40 | 6.74 | 4.52 | 5.51 | 5.31 | 4.90 | 4.14 |
LBF | 5.27 | 3.73 | 7.97 | 9.86 | 11.21 | 10.38 | 8.27 | 6.52 | 6.20 |
LBF-MS | 4.25 |
3.08
| 5.33 | 6.24 | 7.73 | 8.02 | 8.29 | 8.05 | 7.25 |
SLBF | 4.76 | 5.37 | 5.08 | 5.25 | 5.48 | 5.42 | 4.57 | 4.74 | 3.79 |
SLBF-MS | 4.77 | 5.37 | 5.84 | 4.91 | 3.75 | 3.76 |
2.87
|
3.01
|
3.22
|
ALC (voting with K) |
2.21
| 6.93 | 13.87 | 14.89 | 16.84 | 24.71 | 18.05 | 21.62 | 16.98 |
ALC (ϵ from LBF) | 13.14 | 12.96 | 14.91 | 16.40 | 15.22 | 12.22 | 10.89 | 6.76 | 6.10 |
SCC | 5.21 | 11.71 | 14.65 | 10.60 | 6.68 | 5.14 | 4.67 | 4.32 | 5.03 |
SCC-MS | 2.84 | 13.66 | 14.66 | 10.41 | 8.29 | 6.72 | 5.61 | 5.93 | 5.46 |
SSC | 4.57 | 3.76 |
4.52
|
3.82
|
3.59
|
2.87
| 3.18 | 3.45 | 5.21 |
K-flats | 4.67 | 6.86 | 8.53 | 8.89 | 7.29 | 6.41 | 6.67 | 4.84 | 5.43 |
3.4 Clustering Results on MNIST Data Set
Subsets | [1 2] | [1 3] | [1 7] | [4 7] | [2 4 8] | [3 6 8] | [1 2 3] | |
---|---|---|---|---|---|---|---|---|
K
| 2 | 2 | 2 | 2 | 3 | 3 | 3 | |
LBF |
e % | 8.0 | 8.5 | 12.9 | 25.5 | 28.8 | 28.1 | 20.2 |
t(s) | 0.4 | 0.4 | 0.3 | 0.4 | 0.7 | 0.7 | 0.7 | |
LBF-MS |
e % | 9.7 | 7.8 | 8.8 | 24.0 | 40.2 | 33.5 | 21.5 |
t(s) |
0.2
|
0.2
|
0.2
|
0.2
|
0.5
|
0.4
|
0.4
| |
SLBF |
e % | 0.5 |
1.0
|
2.0
|
3.0
|
3.8
|
19.7
|
17.3
|
t(s) | 13.9 | 13.7 | 13.5 | 14.5 | 41.9 | 41.0 | 42.7 | |
SLBF-MS |
e % | 0.5 |
1.0
|
2.0
|
3.0
|
3.8
| 19.7 | 17.3 |
t(s) | 12.8 | 13.7 | 13.0 | 14.6 | 38.6 | 46.3 | 39.0 | |
ALC (voting with K) |
e % |
0.2
| 2.2 | 3.5 | 48.5 | 4.2 | 42.7 | 45.3 |
t(s) | 830.5 | 823.3 | 813.3 | 753.2 | 1789.5 | 1871.8 | 1987.7 | |
ALC (ϵ from LBF) |
e % | 20.3 | 32.0 | 51.8 | 27.5 | 4.0 | 30.3 | 14.5 |
t(s) | 23.2 | 22.5 | 21.6 | 23.0 | 55.6 | 54.7 | 54.0 | |
SCC |
e % | 7.0 | 6.4 | 11.4 | 23.4 | 22.8 | 26.7 | 39.2 |
t(s) | 1.2 | 1.5 | 1.4 | 1.3 | 2.5 | 2.7 | 2.3 | |
SCC-MS |
e % | 6.3 | 7.9 | 10.5 | 23.2 | 23.3 | 26.9 | 32.8 |
t(s) | 0.9 | 0.8 | 1.1 | 1.0 | 1.9 | 1.9 | 1.5 | |
GPCA |
e % | 22.3 | 30.8 | 32.5 | 47.0 | 48.2 | 33.8 | 31.0 |
t(s) | 8.7 | 9.2 | 9.4 | 10.8 | 24.9 | 24.5 | 22.5 | |
K-flats |
e % | 11.1 | 6.8 | 6.3 | 29.1 | 43.9 | 40.7 | 29.2 |
t(s) | 0.4 | 0.4 | 0.4 | 0.4 | 0.9 | 0.8 | 0.6 | |
SSC |
e % | 4.5 | 3.5 | 9.0 | 21.0 | 19.5 | 24.5 | 49.3 |
t(s) | 220.6 | 196.6 | 200.8 | 203.2 | 322.6 | 333.0 | 338.2 |
Subsets | [1 2] | [1 3] | [1 7] | [4 7] | [2 4 8] | [3 6 8] | [1 2 3] | |
---|---|---|---|---|---|---|---|---|
K
| 2 | 2 | 2 | 2 | 3 | 3 | 3 | |
LBF |
e % | 20.5 | 13.1 | 18.2 | 30.2 | 26.3 | 24.1 |
19.2
|
t(s) | 2.8 | 2.8 | 2.6 | 3.1 | 5.2 | 5.1 | 4.7 | |
LBF-MS |
e % | 12.5 | 16.9 | 10.7 | 19.1 | 23.5 | 27.3 | 24.3 |
t(s) | 1.3 | 1.3 | 1.3 | 1.3 | 2.3 | 2.3 | 2.3 | |
SLBF |
e % | 8.3 | 4.3 |
2.3
| 13.8 | 4.3 |
17.5
| 21.7 |
t(s) | 15.1 | 15.0 | 14.6 | 16.8 | 37.5 | 38.5 | 39.5 | |
SLBF-MS |
e % | 5.5 |
3.3
| 5.0 |
5.5
|
3.2
| 18.5 | 21.7 |
t(s) | 11.8 | 12.3 | 12.3 | 12.5 | 34.3 | 36.9 | 34.4 | |
ALC (voting with K) |
e % | 47.0 | 46.0 | 48.8 | 100.0 | 100.0 | 100.0 | 65.3 |
t(s) | 1469.2 | 1445.6 | 1489.2 | 679.0 | 1530.1 | 1528.5 | 3032.4 | |
ALC (ϵ from LBF) |
e % | 50.5 | 50.8 | 50.5 | 99.8 | 99.8 | 99.8 | 67.0 |
t(s) | 93.0 | 93.6 | 91.0 | 9.4 | 18.2 | 17.9 | 163.5 | |
SCC |
e % | 5.8 | 4.9 | 5.3 | 17.1 | 23.0 | 29.7 | 33.6 |
t(s) |
0.9
|
1.0
|
1.1
|
0.9
|
1.6
| 2.0 |
1.7
| |
SCC-MS |
e % |
5.1
| 5.4 | 5.1 | 26.2 | 28.6 | 41.7 | 33.0 |
t(s) |
0.9
|
1.0
| 1.2 | 1.0 | 1.8 |
1.9
| 2.0 | |
GPCA |
e % | N/A | N/A | N/A | N/A | N/A | N/A | N/A |
t(s) | N/A | N/A | N/A | N/A | N/A | N/A | N/A | |
K-flats |
e % | 10.9 | 14.9 | 13.5 | 30.4 | 45.3 | 41.6 | 26.9 |
t(s) | 2.8 | 2.9 | 2.9 | 3.1 | 6.2 | 5.6 | 5.1 | |
SSC |
e % | 16.8 | 2.0 | 3.2 | 20.0 | 11.3 | 17.8 | 45.5 |
t(s) | 411.8 | 402.7 | 395.1 | 396.0 | 760.9 | 763.1 | 777.0 |
Subsets | [1 2] | [1 3] | [1 7] | [4 7] | [2 4 8] | [3 6 8] | [1 2 3] |
---|---|---|---|---|---|---|---|
K
| 2 | 2 | 2 | 2 | 3 | 3 | 3 |
LBF | 3.5 | 4.1 | 10.0 | 11.4 | 11.6 | 8.3 | 9.5 |
LBF-MS | 5.9 | 3.8 | 10.0 | 10.0 | 10.3 | 7.2 | 7.8 |
SLBF |
0.0
|
0.0
|
0.0
|
0.0
| 0.0 |
0.0
|
0.0
|
SLBF-MS |
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
ALC (voting with K) |
0.0
| 0.0 |
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
ALC (ϵ from LBF) |
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
SCC | 2.3 | 2.7 | 4.6 | 9.9 | 9.4 | 7.5 | 11.9 |
SCC-MS | 2.0 | 3.7 | 5.2 | 10.2 | 8.3 | 8.5 | 9.2 |
GPCA |
0.0
| 0.0 |
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
K-flats | 7.6 | 8.5 | 7.8 | 5.7 | 7.4 | 7.5 | 5.9 |
SSC |
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
Subsets | [1 2] | [1 3] | [1 7] | [4 7] | [2 4 8] | [3 6 8] | [1 2 3] |
---|---|---|---|---|---|---|---|
K
| 2 | 2 | 2 | 2 | 3 | 3 | 3 |
LBF | 5.6 | 8.0 | 8.3 | 10.6 | 11.0 | 6.0 | 6.0 |
LBF-MS | 8.7 | 10.5 | 11.4 | 11.2 | 12.3 | 8.9 | 9.1 |
SLBF |
0.0
| 0.0 |
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
SLBF-MS |
0.0
| 0.0 |
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
ALC (voting with K) |
0.0
| 0.0 |
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
ALC (ϵ from LBF) |
0.0
| 0.0 |
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
SCC | 0.6 | 1.0 | 0.9 | 10.3 | 3.7 | 4.3 | 13.9 |
SCC-MS | 0.4 | 0.7 | 0.9 | 15.5 | 5.4 | 4.5 | 5.8 |
GPCA | N/A | N/A | N/A | N/A | N/A | N/A | N/A |
K-flats | 7.2 | 11.3 | 11.1 | 7.5 | 7.3 | 8.1 | 7.7 |
SSC |
0.0
| 0.0 |
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
3.5 Automatic Determination of the Number of Flats
3.5.1 Finding the Number of Clusters on Artificial Data
No minimum angle | Minimum angle =π/8 | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
16∈ℝ5
| 24∈ℝ5
| 33∈ℝ5
| 16∈ℝ3
| 24∈ℝ3
| 33∈ℝ4
| 102∈ℝ15
| 16∈ℝ3
| 24∈ℝ3
| 33∈ℝ4
| 102∈ℝ15
| ||
SOD (LBF) |
e % | 22 | 2 |
0
| 58 | 32 | 12 |
0
| 2 | 6 | 5 |
0
|
t(s) | 10.43 | 13.76 | 14.83 | 9.84 | 13.08 | 14.49 | 34.16 | 9.95 | 13.22 | 14.47 | 34.04 | |
SOD (LBF-MS) |
e % | 13 | 1 | 3 | 67 | 33 | 9 |
0
| 3 | 8 | 6 |
0
|
t(s) | 8.70 | 11.90 | 12.92 | 8.37 | 11.54 | 12.84 | 27.56 | 8.42 | 11.60 | 12.84 | 27.69 | |
SOD (SLBF) |
e % | 75 | 10 | 5 |
0
| 90 | 95 | 55 |
0
| 85 | 90 | 55 |
t(s) | 1097.19 | 2148.06 | 2895.85 | 1076.24 | 1774.74 | 2629.26 | 16124.50 | 1224.96 | 2387.70 | 2830.83 | 16510.13 | |
SOD (SLBF-MS) |
e % | 90 | 95 | 70 |
0
| 90 | 85 | 85 | 0 | 75 | 80 | 80 |
t(s) | 908.76 | 2094.68 | 3141.77 | 927.25 | 1740.03 | 2695.59 | 15754.05 | 990.88 | 2302.66 | 3010.64 | 16493.95 | |
ALC (voting) |
e %(K) | 24 | 12 | 11 | 32 | 30 | 17 | 100 | 5 | 9 | 9 | 100 |
t(s) | 2094.75 | 2700.07 | 3530.26 | 1207.54 | 2346.69 | 3628.24 | 119584.04 | 1184.08 | 2354.19 | 3956.05 | 117353.17 | |
ALC (ϵ from LBF) |
e %(K) |
1
|
0
| 1 | 20 |
20
| 3 | 58 |
0
|
3
|
1
| 63 |
t(s) | 23.72 | 43.50 | 57.50 | 19.76 | 36.67 | 53.25 | 1516.02 | 19.81 | 36.60 | 53.01 | 1770.77 | |
ALC (oracle) |
e %(K) |
1
|
0
|
0
| 34 | 31 |
1
| 16 |
0
| 10 |
1
| 13 |
t(s) | 23.74 | 43.44 | 59.14 | 20.49 | 37.49 | 53.59 | 1370.92 | 20.22 | 37.41 | 54.11 | 1354.11 | |
GPCA |
e %(K) | 88 | 100 | 100 | 27 | 100 | 100 | 100 | 13 | 100 | 100 | 100 |
t(s) |
0.03
|
0.09
|
0.12
|
0.06
|
0.09
|
0.12
|
1.30
|
0.04
|
0.09
|
0.12
|
1.30
| |
SOD (SCC) |
e %(K) | 35 | 21 | 1 | 63 | 39 | 17 |
0
| 9 | 32 | 11 | 1 |
t(s) | 32.09 | 61.26 | 95.79 | 25.83 | 59.41 | 76.13 | 475.45 | 26.74 | 41.95 | 61.53 | 466.79 | |
SOD (SCC-MS) |
e%(K) | 71 | 32 | 2 | 80 | 50 | 12 |
0
| 46 | 33 | 3 |
0
|
t(s) | 31.78 | 67.77 | 111.15 | 22.29 | 55.25 | 74.07 | 475.50 | 24.53 | 51.98 | 75.03 | 471.31 | |
SOD (SSC) |
e %(K) | 10 | 80 | 70 | 100 | 70 | 70 | 100 | 50 | 80 | 80 | 100 |
t(s) | 39.88 | 2634.80 | 3039.55 | 1708.37 | 2447.01 | 2925.27 | 14918.10 | 1452.43 | 2101.84 | 2641.68 | 14227.32 |
3.5.2 Finding the Number of Clusters on the Extended Yale Face Database B
Real K
| 2 | 3 | 4 | 5 | 6 | |
---|---|---|---|---|---|---|
SOD (LBF) |
e %(K) | 62 | 61 | 69 | 78 | 84 |
t(s) | 1.30 | 3.60 | 5.69 | 11.30 | 15.84 | |
SOD (LBF-MS) |
e %(K) | 65 | 75 | 78 | 81 | 80 |
t(s) | 0.67 | 1.65 | 2.49 | 4.90 | 6.83 | |
SOD (SLBF) |
e %(K) | 24 | 60 | 70 | 86 | 98 |
t(s) | 115.97 | 303.02 | 338.35 | 729.74 | 811.40 | |
SOD (SLBF-MS) |
e %(K) |
20
| 60 | 76 | 92 | 96 |
t(s) | 106.87 | 272.88 | 306.22 | 649.50 | 721.42 | |
ALC (voting) |
e %(K) | 100 | 100 | 100 | 100 | 100 |
t(s) | 42.99 | 122.29 | 258.20 | 451.07 | 699.52 | |
ALC (ϵ from LBF) |
e %(K) | 42 | 36 | 76 | 86 | 100 |
t(s) | 0.95 | 2.49 | 5.54 | 11.54 | 24.38 | |
GPCA |
e %(K) | 100 | 100 | 100 | 100 | 100 |
t(s) |
0.07
|
0.13
|
0.52
|
0.71
|
1.02
| |
SOD (SSC) |
e %(K) | 100 |
8
|
12
|
28
|
38
|
t(s) | 172.50 | 389.66 | 567.39 | 1015.99 | 1336.57 |
3.5.3 Finding the Number of Clusters on MNIST Data Set
Subsets | [1 2] | [1 3] | [1 7] | [4 7] | [2 4 8] | [3 6 8] | [1 2 3] | |
---|---|---|---|---|---|---|---|---|
K
| 2 | 2 | 2 | 2 | 3 | 3 | 3 | |
SOD (LBF) |
e % | 16.8 | 3.8 | 50.8 | 50.4 | 75.6 | 70.0 | 54.8 |
t(s) | 3.5 | 3.2 | 3.0 | 3.3 | 7.7 | 7.5 | 7.3 | |
SOD (LBF-MS) |
e % | 9.6 | 6.6 | 33.4 | 68.2 | 80.4 | 76.6 | 44.2 |
t(s) | 1.9 | 1.9 | 1.9 | 1.8 | 4.6 | 4.6 | 4.7 | |
SOD (SLBF) |
e % |
0.0
|
0.0
|
0.0
|
0.0
|
0.0
| 100.0 |
0.0
|
t(s) | 173.9 | 164.6 | 160.3 | 248.6 | 710.1 | 610.9 | 548.5 | |
SOD (SLBF-MS) |
e % |
0.0
|
0.0
|
0.0
|
0.0
|
0.0
| 100.0 |
0.0
|
t(s) | 164.6 | 159.9 | 150.1 | 228.5 | 676.6 | 586.4 | 556.2 | |
ALC (voting) |
e % | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 |
t(s) | 830.4 | 823.2 | 813.2 | 753.2 | 1789.5 | 1871.8 | 1987.5 | |
ALC (ϵ from LBF) |
e % | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 |
0.0
| 100.0 |
t(s) | 23.2 | 22.5 | 21.5 | 22.9 | 55.6 | 54.7 | 54.0 | |
GPCA |
e % | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 |
t(s) |
1.0
|
1.0
|
1.0
|
1.1
|
2.8
|
2.8
|
2.7
| |
SOD (SCC) |
e %(K) | 3.8 | 7.8 | 66.4 | 81.8 | 64.4 | 47.6 | 82.6 |
t(s) | 14.5 | 13.3 | 14.7 | 16.9 | 37.5 | 34.1 | 35.0 | |
SOD (SCC-MS) |
e %(K) | 2.4 | 16.4 | 53.0 | 77.4 | 70.4 | 49.6 | 77.8 |
t(s) | 13.7 | 13.8 | 13.5 | 16.4 | 38.0 | 35.6 | 29.4 | |
SOD (SSC) |
e %(K) |
0.0
|
0.0
|
0.0
| 100.0 |
0.0
| 100.0 | 100.0 |
t(s) | 233.6 | 210.3 | 213.3 | 218.4 | 380.0 | 386.4 | 390.5 |
Subsets | [1 2] | [1 3] | [1 7] | [4 7] | [2 4 8] | [3 6 8] | [1 2 3] | |
---|---|---|---|---|---|---|---|---|
K
| 2 | 2 | 2 | 2 | 3 | 3 | 3 | |
SOD (LBF) |
e % | 45.0 | 35.0 | 54.0 | 79.0 | 72.0 | 67.0 | 60.0 |
t(s) | 22.9 | 23.5 | 22.2 | 24.9 | 56.2 | 54.6 | 51.1 | |
SOD (LBF-MS) |
e % | 32.0 | 22.0 | 38.0 | 66.0 | 44.0 | 82.0 | 58.0 |
t(s) |
12.2
| 12.2 | 12.2 | 12.2 | 29.3 | 29.4 | 29.4 | |
SOD (SLBF) |
e % |
0.0
|
0.0
|
0.0
|
0.0
|
0.0
| 100.0 | 100.0 |
t(s) | 204.2 | 198.1 | 207.8 | 295.8 | 864.5 | 766.5 | 706.1 | |
SOD (SLBF-MS) |
e % |
0.0
|
0.0
| 100.0 |
0.0
|
0.0
| 100.0 | 100.0 |
t(s) | 213.7 | 201.7 | 176.6 | 259.9 | 748.1 | 640.0 | 681.1 | |
ALC (voting) |
e % | 100.0 | 100.0 | 100.0 | 100.0 | 100.00 | 100.0 | 100.0 |
t(s) | 1469.2 | 1445.6 | 1489.2 | 679.0 | 1530.1 | 1528.5 | 3032.4 | |
ALC (ϵ from LBF) |
e % | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 |
t(s) | 93.0 | 93.6 | 91.0 |
9.4
|
18.2
|
17.9
| 163.5 | |
GPCA |
e % | N/A | N/A | N/A | N/A | N/A | N/A | N/A |
t(s) | N/A | N/A | N/A | N/A | N/A | N/A | N/A | |
SOD (SCC) |
e %(K) |
0.0
| 4.0 | 1.0 | 50.5 | 78.8 | 30.3 | 83.8 |
t(s) | 14.9 |
10.6
|
11.6
| 11.6 | 24.7 | 26.2 |
25.4
| |
SOD (SCC-MS) |
e %(K) |
0.0
|
0.0
|
0.0
| 42.4 | 89.9 | 97.0 | 93.9 |
t(s) | 12.6 | 13.0 | 14.7 | 13.9 | 34.0 | 36.8 | 30.7 | |
SOD (SSC) |
e %(K) |
0.0
|
0.0
|
0.0
|
0.0
|
0.0
| 100.0 | 100.0 |
t(s) | 426.4 | 417.6 | 409.3 | 413.5 | 823.8 | 821.2 | 836.8 |