1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.text.similarity;
18
19 import java.util.HashSet;
20 import java.util.Map;
21 import java.util.Set;
22
23 /**
24 * Measures the Cosine similarity of two vectors of an inner product space and compares the angle between them.
25 * <p>
26 * For further explanation about the Cosine Similarity, refer to https://en.wikipedia.org/wiki/Cosine_similarity.
27 * </p>
28 * <p>
29 * Instances of this class are immutable and are safe for use by multiple concurrent threads.
30 * </p>
31 *
32 * @since 1.0
33 */
34 public class CosineSimilarity {
35
36 /**
37 * Singleton instance.
38 */
39 static final CosineSimilarity INSTANCE = new CosineSimilarity();
40
41 /**
42 * Calculates the cosine similarity for two given vectors.
43 *
44 * @param leftVector left vector
45 * @param rightVector right vector
46 * @return cosine similarity between the two vectors
47 */
48 public Double cosineSimilarity(final Map<CharSequence, Integer> leftVector,
49 final Map<CharSequence, Integer> rightVector) {
50 if (leftVector == null || rightVector == null) {
51 throw new IllegalArgumentException("Vectors must not be null");
52 }
53
54 final Set<CharSequence> intersection = getIntersection(leftVector, rightVector);
55
56 final double dotProduct = dot(leftVector, rightVector, intersection);
57 double d1 = 0.0d;
58 for (final Integer value : leftVector.values()) {
59 d1 += Math.pow(value, 2);
60 }
61 double d2 = 0.0d;
62 for (final Integer value : rightVector.values()) {
63 d2 += Math.pow(value, 2);
64 }
65 final double cosineSimilarity;
66 if (d1 <= 0.0 || d2 <= 0.0) {
67 cosineSimilarity = 0.0;
68 } else {
69 cosineSimilarity = dotProduct / (Math.sqrt(d1) * Math.sqrt(d2));
70 }
71 return cosineSimilarity;
72 }
73
74 /**
75 * Computes the dot product of two vectors. It ignores remaining elements. It means
76 * that if a vector is longer than other, then a smaller part of it will be used to compute
77 * the dot product.
78 *
79 * @param leftVector left vector
80 * @param rightVector right vector
81 * @param intersection common elements
82 * @return The dot product
83 */
84 private double dot(final Map<CharSequence, Integer> leftVector, final Map<CharSequence, Integer> rightVector,
85 final Set<CharSequence> intersection) {
86 long dotProduct = 0;
87 for (final CharSequence key : intersection) {
88 dotProduct += leftVector.get(key) * (long) rightVector.get(key);
89 }
90 return dotProduct;
91 }
92
93 /**
94 * Returns a set with keys common to the two given maps.
95 *
96 * @param leftVector left vector map
97 * @param rightVector right vector map
98 * @return common strings
99 */
100 private Set<CharSequence> getIntersection(final Map<CharSequence, Integer> leftVector,
101 final Map<CharSequence, Integer> rightVector) {
102 final Set<CharSequence> intersection = new HashSet<>(leftVector.keySet());
103 intersection.retainAll(rightVector.keySet());
104 return intersection;
105 }
106
107 }