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 }