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