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.distance.distancefunction.probabilistic;
22 
23 import de.lmu.ifi.dbs.elki.data.NumberVector;
24 import de.lmu.ifi.dbs.elki.data.spatial.SpatialComparable;
25 import de.lmu.ifi.dbs.elki.distance.distancefunction.AbstractNumberVectorDistanceFunction;
26 import de.lmu.ifi.dbs.elki.distance.distancefunction.SpatialPrimitiveDistanceFunction;
27 import de.lmu.ifi.dbs.elki.utilities.Alias;
28 import de.lmu.ifi.dbs.elki.utilities.documentation.Reference;
29 import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer;
30 import net.jafama.FastMath;
31 
32 /**
33  * Jeffrey Divergence for {@link NumberVector}s is a symmetric, smoothened
34  * version of the {@link KullbackLeiblerDivergenceAsymmetricDistanceFunction}.
35  * Topsøe called this "capacitory discrimination".
36  * <p>
37  * \[JD(\vec{x},\vec{y}):= \sum\nolimits_i
38  * x_i\log\tfrac{2x_i}{x_i+y_i}+y_i\log\tfrac{2y_i}{x_i+y_i}
39  * = KL(\vec{x},\tfrac12(\vec{x}+\vec{y}))
40  * + KL(\vec{y},\tfrac12(\vec{x}+\vec{y}))\]
41  * <p>
42  * Reference:
43  * <p>
44  * H. Jeffreys<br>
45  * An invariant form for the prior probability in estimation problems<br>
46  * Proc. Royal Society A: Mathematical, Physical and Engineering Sciences
47  * 186(1007)
48  * <p>
49  * J. Puzicha, J. M. Buhmann, Y. Rubner, C. Tomasi<br>
50  * Empirical evaluation of dissimilarity measures for color and texture<br>
51  * Proc. 7th IEEE International Conference on Computer Vision
52  * <p>
53  * F. Topsøe<br>
54  * Some inequalities for information divergence and related measures of
55  * discrimination<br>
56  * IEEE Transactions on information theory, 46(4)
57  * <p>
58  * D. M. Endres, J. E. Schindelin<br>
59  * A new metric for probability distributions<br>
60  * IEEE Transactions on Information Theory 49(7)
61  * <p>
62  * TODO: add support for sparse vectors + varying length
63  *
64  * @author Erich Schubert
65  * @since 0.5.0
66  */
67 @Reference(authors = "H. Jeffreys", //
68     title = "An invariant form for the prior probability in estimation problems", //
69     booktitle = "Proc. Royal Society A: Mathematical, Physical and Engineering Sciences 186(1007)", //
70     url = "https://doi.org/10.1098/rspa.1946.0056", //
71     bibkey = "doi:10.1098/rspa.1946.0056")
72 @Reference(authors = "J. Puzicha, J. M. Buhmann, Y. Rubner, C. Tomasi", //
73     title = "Empirical evaluation of dissimilarity measures for color and texture", //
74     booktitle = "Proc. 7th IEEE International Conference on Computer Vision", //
75     url = "https://doi.org/10.1109/ICCV.1999.790412", //
76     bibkey = "DBLP:conf/iccv/PuzichaRTB99")
77 @Reference(authors = "F. Topsøe", //
78     title = "Some inequalities for information divergence and related measures of discrimination", //
79     booktitle = "IEEE Transactions on information theory, 46(4)", //
80     url = "https://doi.org/10.1109/18.850703", //
81     bibkey = "DBLP:journals/tit/Topsoe00")
82 @Reference(authors = "D. M. Endres, J. E. Schindelin", //
83     title = "A new metric for probability distributions", //
84     booktitle = "IEEE Transactions on Information Theory 49(7)", //
85     url = "https://doi.org/10.1109/TIT.2003.813506", //
86     bibkey = "DBLP:journals/tit/EndresS03")
87 @Alias({ "j-divergence" })
88 public class JeffreyDivergenceDistanceFunction extends AbstractNumberVectorDistanceFunction implements SpatialPrimitiveDistanceFunction<NumberVector> {
89   /**
90    * Static instance. Use this!
91    */
92   public static final JeffreyDivergenceDistanceFunction STATIC = new JeffreyDivergenceDistanceFunction();
93 
94   /**
95    * Constructor for the Jeffrey divergence - use {@link #STATIC} instead.
96    *
97    * @deprecated Use static instance!
98    */
99   @Deprecated
JeffreyDivergenceDistanceFunction()100   public JeffreyDivergenceDistanceFunction() {
101     super();
102   }
103 
104   @Override
distance(NumberVector v1, NumberVector v2)105   public double distance(NumberVector v1, NumberVector v2) {
106     final int dim = dimensionality(v1, v2);
107     double agg = 0.;
108     for(int d = 0; d < dim; d++) {
109       final double xd = v1.doubleValue(d), yd = v2.doubleValue(d);
110       if(xd == yd) {
111         continue;
112       }
113       final double md = .5 * (xd + yd);
114       if(!(md > 0.)) {
115         continue;
116       }
117       agg += (xd > 0 ? xd * FastMath.log(xd / md) : 0) //
118           + (yd > 0 ? yd * FastMath.log(yd / md) : 0);
119     }
120     return agg;
121   }
122 
123   @Override
minDist(SpatialComparable mbr1, SpatialComparable mbr2)124   public double minDist(SpatialComparable mbr1, SpatialComparable mbr2) {
125     final int dim = dimensionality(mbr1, mbr2);
126     double agg = 0;
127     for(int d = 0; d < dim; d++) {
128       final double min1 = mbr1.getMin(d), min2 = mbr2.getMin(d);
129       final double md = .5 * (mbr1.getMax(d) + mbr2.getMax(d));
130       if(!(md > 0.)) {
131         continue;
132       }
133       agg += (min1 > 0 ? min1 * FastMath.log(min1 / md) : 0) //
134           + (min2 > 0 ? min2 * FastMath.log(min2 / md) : 0);
135     }
136     return agg > 0 ? agg : 0;
137   }
138 
139   @Override
isSquared()140   public boolean isSquared() {
141     return true;
142   }
143 
144   @Override
toString()145   public String toString() {
146     return "JeffreyDivergenceDistance";
147   }
148 
149   @Override
equals(Object obj)150   public boolean equals(Object obj) {
151     return obj == this || (obj != null && this.getClass().equals(obj.getClass()));
152   }
153 
154   @Override
hashCode()155   public int hashCode() {
156     return getClass().hashCode();
157   }
158 
159   /**
160    * Parameterization class, using the static instance.
161    *
162    * @author Erich Schubert
163    */
164   public static class Parameterizer extends AbstractParameterizer {
165     @Override
makeInstance()166     protected JeffreyDivergenceDistanceFunction makeInstance() {
167       return STATIC;
168     }
169   }
170 }
171