1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
|
package de.lmu.ifi.dbs.elki.math.linearalgebra.pca;
/*
This file is part of ELKI:
Environment for Developing KDD-Applications Supported by Index-Structures
Copyright (C) 2012
Ludwig-Maximilians-Universität München
Lehr- und Forschungseinheit für Datenbanksysteme
ELKI Development Team
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU Affero General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU Affero General Public License for more details.
You should have received a copy of the GNU Affero General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
import java.util.ArrayList;
import java.util.List;
import de.lmu.ifi.dbs.elki.math.linearalgebra.EigenPair;
import de.lmu.ifi.dbs.elki.math.linearalgebra.SortedEigenPairs;
import de.lmu.ifi.dbs.elki.utilities.documentation.Description;
import de.lmu.ifi.dbs.elki.utilities.documentation.Title;
import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer;
import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.GreaterEqualConstraint;
import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization;
import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.DoubleParameter;
/**
* The SignificantEigenPairFilter sorts the eigenpairs in descending order of
* their eigenvalues and chooses the contrast of an Eigenvalue to the remaining
* Eigenvalues is maximal.
*
* It is closely related to the WeakEigenPairFilter and RelativeEigenPairFilter.
* But while the RelativeEigenPairFilter chooses the highest dimensionality that
* satisfies the relative alpha levels, the SignificantEigenPairFilter will
* chose the local dimensionality such that the 'contrast' is maximal.
*
* There are some situations where one or the other is superior, especially when
* it comes to handling nested clusters and strong global correlations that are
* not too interesting. These benefits usually only make a difference at higher
* dimensionalities.
*
* @author Erich Schubert
*/
@Title("Significant EigenPair Filter")
@Description("Sorts the eigenpairs in decending order of their eigenvalues and looks for the maxmimum contrast of current Eigenvalue / average of remaining Eigenvalues.")
public class SignificantEigenPairFilter implements EigenPairFilter {
/**
* The default value for walpha. Not used by default, we're going for maximum
* contrast only.
*/
public static final double DEFAULT_WALPHA = 0.0;
/**
* The noise tolerance level for weak eigenvectors
*/
private double walpha;
/**
* Constructor.
*
* @param walpha
*/
public SignificantEigenPairFilter(double walpha) {
super();
this.walpha = walpha;
}
@Override
public FilteredEigenPairs filter(SortedEigenPairs eigenPairs) {
// init strong and weak eigenpairs
List<EigenPair> strongEigenPairs = new ArrayList<EigenPair>();
List<EigenPair> weakEigenPairs = new ArrayList<EigenPair>();
// default value is "all strong".
int contrastMaximum = eigenPairs.size() - 1;
double maxContrast = 0.0;
// calc the eigenvalue sum.
double eigenValueSum = 0.0;
for (int i = 0; i < eigenPairs.size(); i++) {
EigenPair eigenPair = eigenPairs.getEigenPair(i);
eigenValueSum += eigenPair.getEigenvalue();
}
double weakEigenvalue = eigenValueSum / eigenPairs.size() * walpha;
// now find the maximum contrast.
double currSum = eigenPairs.getEigenPair(eigenPairs.size() - 1).getEigenvalue();
for (int i = eigenPairs.size() - 2; i >= 0; i--) {
EigenPair eigenPair = eigenPairs.getEigenPair(i);
currSum += eigenPair.getEigenvalue();
// weak?
if (eigenPair.getEigenvalue() < weakEigenvalue) {
continue;
}
double contrast = eigenPair.getEigenvalue() / (currSum / (eigenPairs.size() - i));
if (contrast > maxContrast) {
maxContrast = contrast;
contrastMaximum = i;
}
}
for (int i = 0; i <= contrastMaximum /* && i < eigenPairs.size() */; i++) {
EigenPair eigenPair = eigenPairs.getEigenPair(i);
strongEigenPairs.add(eigenPair);
}
for (int i = contrastMaximum + 1; i < eigenPairs.size(); i++) {
EigenPair eigenPair = eigenPairs.getEigenPair(i);
weakEigenPairs.add(eigenPair);
}
return new FilteredEigenPairs(weakEigenPairs, strongEigenPairs);
}
/**
* Parameterization class.
*
* @author Erich Schubert
*
* @apiviz.exclude
*/
public static class Parameterizer extends AbstractParameterizer {
private double walpha;
@Override
protected void makeOptions(Parameterization config) {
super.makeOptions(config);
DoubleParameter walphaP = new DoubleParameter(WeakEigenPairFilter.EIGENPAIR_FILTER_WALPHA, DEFAULT_WALPHA);
walphaP.addConstraint(new GreaterEqualConstraint(0.0));
if (config.grab(walphaP)) {
walpha = walphaP.getValue();
}
}
@Override
protected SignificantEigenPairFilter makeInstance() {
return new SignificantEigenPairFilter(walpha);
}
}
}
|