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.math.linearalgebra; 22 23 import de.lmu.ifi.dbs.elki.data.NumberVector; 24 import de.lmu.ifi.dbs.elki.database.ids.DBIDIter; 25 import de.lmu.ifi.dbs.elki.database.ids.DBIDs; 26 import de.lmu.ifi.dbs.elki.database.relation.Relation; 27 import de.lmu.ifi.dbs.elki.database.relation.RelationUtil; 28 import de.lmu.ifi.dbs.elki.utilities.datastructures.BitsUtil; 29 30 /** 31 * Centroid only using a subset of dimensions. 32 * 33 * This class abstracts the mathematics of efficient and numerically stable 34 * computation of projected centroids. 35 * 36 * See {@link de.lmu.ifi.dbs.elki.database.DatabaseUtil DatabaseUtil} for 37 * easier to use APIs. 38 * 39 * @author Erich Schubert 40 * @since 0.4.0 41 */ 42 public class ProjectedCentroid extends Centroid { 43 /** 44 * The selected dimensions. 45 */ 46 private long[] dims; 47 48 /** 49 * Constructor for updating use. 50 * 51 * @param dims Dimensions to use (indexed with 0) 52 * @param dim Full dimensionality 53 */ ProjectedCentroid(long[] dims, int dim)54 public ProjectedCentroid(long[] dims, int dim) { 55 super(dim); 56 this.dims = dims; 57 } 58 59 /** 60 * Add a single value with weight 1.0. 61 * 62 * @param val Value 63 */ 64 @Override put(double[] val)65 public void put(double[] val) { 66 assert (val.length == elements.length); 67 wsum += 1.0; 68 for(int i = BitsUtil.nextSetBit(dims, 0); i >= 0; i = BitsUtil.nextSetBit(dims, i + 1)) { 69 final double delta = val[i] - elements[i]; 70 elements[i] += delta / wsum; 71 } 72 } 73 74 /** 75 * Add data with a given weight. 76 * 77 * @param val data 78 * @param weight weight 79 */ 80 @Override put(double[] val, double weight)81 public void put(double[] val, double weight) { 82 assert (val.length == elements.length); 83 if(weight == 0) { 84 return; // Skip zero weights. 85 } 86 final double nwsum = weight + wsum; 87 for(int i = BitsUtil.nextSetBit(dims, 0); i >= 0; i = BitsUtil.nextSetBit(dims, i + 1)) { 88 final double delta = val[i] - elements[i]; 89 final double rval = delta * weight / nwsum; 90 elements[i] += rval; 91 } 92 wsum = nwsum; 93 } 94 95 /** 96 * Add a single value with weight 1.0. 97 * 98 * @param val Value 99 */ 100 @Override put(NumberVector val)101 public void put(NumberVector val) { 102 assert (val.getDimensionality() == elements.length); 103 wsum += 1.0; 104 for(int i = BitsUtil.nextSetBit(dims, 0); i >= 0; i = BitsUtil.nextSetBit(dims, i + 1)) { 105 final double delta = val.doubleValue(i) - elements[i]; 106 elements[i] += delta / wsum; 107 } 108 } 109 110 /** 111 * Add data with a given weight. 112 * 113 * @param val data 114 * @param weight weight 115 */ 116 @Override put(NumberVector val, double weight)117 public void put(NumberVector val, double weight) { 118 assert (val.getDimensionality() == elements.length); 119 if(weight == 0) { 120 return; // Skip zero weights. 121 } 122 final double nwsum = weight + wsum; 123 for(int i = BitsUtil.nextSetBit(dims, 0); i >= 0; i = BitsUtil.nextSetBit(dims, i + 1)) { 124 final double delta = val.doubleValue(i) - elements[i]; 125 final double rval = delta * weight / nwsum; 126 elements[i] += rval; 127 } 128 wsum = nwsum; 129 } 130 131 /** 132 * Static Constructor from a relation. 133 * 134 * @param dims Dimensions to use (indexed with 0) 135 * @param relation Relation to process 136 * @return Centroid 137 */ make(long[] dims, Relation<? extends NumberVector> relation)138 public static ProjectedCentroid make(long[] dims, Relation<? extends NumberVector> relation) { 139 ProjectedCentroid c = new ProjectedCentroid(dims, RelationUtil.dimensionality(relation)); 140 for(DBIDIter iditer = relation.iterDBIDs(); iditer.valid(); iditer.advance()) { 141 c.put(relation.get(iditer)); 142 } 143 return c; 144 } 145 146 /** 147 * Static Constructor from a relation. 148 * 149 * @param dims Dimensions to use (indexed with 0) 150 * @param relation Relation to process 151 * @param ids IDs to process 152 * @return Centroid 153 */ make(long[] dims, Relation<? extends NumberVector> relation, DBIDs ids)154 public static ProjectedCentroid make(long[] dims, Relation<? extends NumberVector> relation, DBIDs ids) { 155 ProjectedCentroid c = new ProjectedCentroid(dims, RelationUtil.dimensionality(relation)); 156 for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) { 157 c.put(relation.get(iter)); 158 } 159 return c; 160 } 161 }