4
\$\begingroup\$

Having read "Effective Java" and "Clean Code" I wanted to apply these principles in a manageable scenario. To this end I refactored a Java library that calculates similarities between strings.

The code below is that of a cosine metric. Documents are tokenized into multisets of strings. These are passed onto the metric which calculates their magnitude and dot product by treating the multisets as if they were (sparse) vectors.

package org.simmetrics.metrics;

import static com.google.common.collect.Multisets.union;
import static java.lang.Math.sqrt;

import org.simmetrics.MultisetMetric;

import com.google.common.collect.Multiset;

/**
 * Calculates the cosine similarity over two multisets. The similarity is
 * defined as the cosine of the angle between the multisets expressed as sparse
 * vectors.
 * <p>
 * <code>
 * similarity(a,b) = a·b / (||a|| * ||b||)
 * </code>
 * 
 * <p>
 * The cosine similarity is identical to the Tanimoto coefficient, but unlike
 * Tanimoto the occurrence (cardinality) of an entry is taken into account. E.g.
 * {@code [hello, world]} and {@code [hello, world, hello, world]} would be
 * identical when compared with Tanimoto but are dissimilar when the cosine
 * similarity is used.
 * <p>
 * This class is immutable and thread-safe.
 * 
 * @see TanimotoCoefficient
 * @see <a href="http://en.wikipedia.org/wiki/Cosine_similarity">Wikipedia
 *      Cosine similarity</a>
 * 
 * @param <T>
 *            type of the token
 */
public final class CosineSimilarity<T> implements MultisetMetric<T> {

    @Override
    public float compare(Multiset<T> a, Multiset<T> b) {

        if (a.isEmpty() && b.isEmpty()) {
            return 1.0f;
        }

        if (a.isEmpty() || b.isEmpty()) {
            return 0.0f;
        }

        float dotProduct = 0;
        float magnitudeA = 0;
        float magnitudeB = 0;

        // Lager set first for performance improvement. 
        // See: MultisetUnionSize benchmark
        if(a.size() < b.size()){
            final Multiset<T> swap = a; a = b; b = swap;
        }

        for (T entry : union(a, b).elementSet()) {
            float aCount = a.count(entry);
            float bCount = b.count(entry);

            dotProduct += aCount * bCount;
            magnitudeA += aCount * aCount;
            magnitudeB += bCount * bCount;
        }

        //  a·b / (||a|| * ||b||)
        return (float) (dotProduct / (sqrt(magnitudeA) * sqrt(magnitudeB)));
    }

    @Override
    public String toString() {
        return "CosineSimilarity";
    }

}
\$\endgroup\$
  • \$\begingroup\$ Just a random note: float is pretty imprecise and usually not faster than double. In case of arrays, there may be differences due to memory footprint; in case of vectorized code, there may be a nearly factor, but I don't think this is the case here. So I'd definitely go for double`. \$\endgroup\$ – maaartinus Mar 5 '18 at 3:03
  • \$\begingroup\$ Good point. Cheers. \$\endgroup\$ – mpkorstanje Mar 7 '18 at 9:18
3
\$\begingroup\$

This is pretty good, but two things come immediately to mind:

  1. Declare variables closest to where they're being used. Declare dotProduct, magnitudeA, and magnitudeB right above your loop.
  2. Don't reassign method arguments. That's really confusing six months down the road. In this case, use a helper method which takes the larger and smaller sets in a specific order.

Example:

import static java.lang.Math.sqrt;

/**
 * [Excluded for brevity]
 *
 * @param <T>
 * type of the token
 */
public final class CosineSimilarity<T> implements MultisetMetric<T> {

    @Override
    public float compare(final Multiset<T> a, final Multiset<T> b) {

        if (a.isEmpty() && b.isEmpty()) {
            return 1.0f;
        }

        if (a.isEmpty() || b.isEmpty()) {
            return 0.0f;
        }

        if (a.size() >= b.size()) {
            return this.determineSimilarity(a, b);
        } else {
            return this.determineSimilarity(b, a);
        }
    }

    private float determineSimilarity(final Multiset<T> largerSet, final Multiset<T> smallerSet) {
        float dotProduct = 0;
        float magnitudeA = 0;
        float magnitudeB = 0;

        for (final T entry : union(largerSet, smallerSet).elementSet()) {
            final float aCount = largerSet.count(entry);
            final float bCount = smallerSet.count(entry);

            dotProduct += aCount * bCount;
            magnitudeA += aCount * aCount;
            magnitudeB += bCount * bCount;
        }

        // a·b / (||a|| * ||b||)
        return (float) (dotProduct / (sqrt(magnitudeA) * sqrt(magnitudeB)));
    }

    @Override
    public String toString() {
        return "CosineSimilarity";
    }
}
\$\endgroup\$
  • \$\begingroup\$ Cheers! Excellent point. Adding the extra method kinda banged up the look so I replaced Multisets.union with Math.union (a package utility class) which swaps as needed. This also allowed me to remove some duplicate code and apply the benchmarks directly to the Multisets.union and Math.union for future validation. \$\endgroup\$ – mpkorstanje Nov 24 '15 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.