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