1 /*
2  * This file is part of ELKI:
3  * Environment for Developing KDD-Applications Supported by Index-Structures
4  *
5  * Copyright (C) 2018
6  * ELKI Development Team
7  *
8  * This program is free software: you can redistribute it and/or modify
9  * it under the terms of the GNU Affero General Public License as published by
10  * the Free Software Foundation, either version 3 of the License, or
11  * (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  * GNU Affero General Public License for more details.
17  *
18  * You should have received a copy of the GNU Affero General Public License
19  * along with this program. If not, see <http://www.gnu.org/licenses/>.
20  */
21 package de.lmu.ifi.dbs.elki.utilities.referencepoints;
22 
23 import java.util.ArrayList;
24 import java.util.Collection;
25 
26 import de.lmu.ifi.dbs.elki.data.DoubleVector;
27 import de.lmu.ifi.dbs.elki.data.NumberVector;
28 import de.lmu.ifi.dbs.elki.database.ids.DBIDIter;
29 import de.lmu.ifi.dbs.elki.database.relation.Relation;
30 import de.lmu.ifi.dbs.elki.database.relation.RelationUtil;
31 import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer;
32 import de.lmu.ifi.dbs.elki.utilities.optionhandling.OptionID;
33 import de.lmu.ifi.dbs.elki.utilities.optionhandling.constraints.CommonConstraints;
34 import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameterization.Parameterization;
35 import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.DoubleParameter;
36 import de.lmu.ifi.dbs.elki.utilities.optionhandling.parameters.Flag;
37 
38 /**
39  * Star-based strategy to pick reference points.
40  *
41  * @author Erich Schubert
42  * @since 0.3
43  */
44 public class StarBasedReferencePoints implements ReferencePointsHeuristic {
45   /**
46    * Exclude the center vector.
47    */
48   protected boolean nocenter;
49 
50   /**
51    * Scaling factor.
52    */
53   protected double scale;
54 
55   /**
56    * Constructor.
57    *
58    * @param nocenter Do not include center point
59    * @param scale Scaling factor
60    */
StarBasedReferencePoints(boolean nocenter, double scale)61   public StarBasedReferencePoints(boolean nocenter, double scale) {
62     super();
63     this.nocenter = nocenter;
64     this.scale = scale;
65   }
66 
67   @Override
getReferencePoints(Relation<? extends NumberVector> db)68   public Collection<? extends NumberVector> getReferencePoints(Relation<? extends NumberVector> db) {
69     int dim = RelationUtil.dimensionality(db);
70 
71     // Compute minimum, maximum and centroid
72     double[] centroid = new double[dim];
73     double[] min = new double[dim];
74     double[] max = new double[dim];
75     for(int d = 0; d < dim; d++) {
76       centroid[d] = 0;
77       min[d] = Double.MAX_VALUE;
78       max[d] = -Double.MAX_VALUE;
79     }
80     for(DBIDIter iditer = db.iterDBIDs(); iditer.valid(); iditer.advance()) {
81       NumberVector obj = db.get(iditer);
82       for(int d = 0; d < dim; d++) {
83         double val = obj.doubleValue(d);
84         centroid[d] += val;
85         min[d] = Math.min(min[d], val);
86         max[d] = Math.max(max[d], val);
87       }
88     }
89     // finish centroid, scale min, max
90     for(int d = 0; d < dim; d++) {
91       centroid[d] = centroid[d] / db.size();
92       min[d] = (min[d] - centroid[d]) * scale + centroid[d];
93       max[d] = (max[d] - centroid[d]) * scale + centroid[d];
94     }
95 
96     ArrayList<DoubleVector> result = new ArrayList<>(2 * dim + 1);
97     if(!nocenter) {
98       result.add(DoubleVector.wrap(centroid));
99     }
100     // Plus axis end points through centroid
101     for(int i = 0; i < dim; i++) {
102       double[] vec = centroid.clone();
103       vec[i] = min[i];
104       result.add(DoubleVector.wrap(vec));
105       vec = centroid.clone();
106       vec[i] = max[i];
107       result.add(DoubleVector.wrap(vec));
108     }
109 
110     return result;
111   }
112 
113   /**
114    * Parameterization class.
115    *
116    * @author Erich Schubert
117    */
118   public static class Parameterizer extends AbstractParameterizer {
119     /**
120      * Parameter to specify the grid resolution.
121      */
122     public static final OptionID NOCENTER_ID = new OptionID("star.nocenter", "Do not use the center as extra reference point.");
123 
124     /**
125      * Parameter to specify the extra scaling of the space, to allow
126      * out-of-data-space reference points.
127      */
128     public static final OptionID SCALE_ID = new OptionID("star.scale", "Scale the reference points by the given factor. This can be used to obtain reference points outside the used data space.");
129 
130     /**
131      * Holds the value of {@link #NOCENTER_ID}.
132      */
133     protected boolean nocenter;
134 
135     /**
136      * Holds the value of {@link #SCALE_ID}.
137      */
138     protected double scale;
139 
140     @Override
makeOptions(Parameterization config)141     protected void makeOptions(Parameterization config) {
142       super.makeOptions(config);
143       Flag nocenterF = new Flag(NOCENTER_ID);
144       if(config.grab(nocenterF)) {
145         nocenter = nocenterF.getValue();
146       }
147 
148       DoubleParameter scaleP = new DoubleParameter(SCALE_ID, 1.0) //
149           .addConstraint(CommonConstraints.GREATER_EQUAL_ZERO_DOUBLE);
150       if(config.grab(scaleP)) {
151         scale = scaleP.getValue();
152       }
153     }
154 
155     @Override
makeInstance()156     protected StarBasedReferencePoints makeInstance() {
157       return new StarBasedReferencePoints(nocenter, scale);
158     }
159   }
160 }
161