Repository: keon/algorithms
Pull request #527 (2019-09-30 10:30:57)

Add cosine similarity calculation.
I added the function in `algorithms/maths/cosine_similarity.py` that calculates the cosine similarity between two python lists.

(Put an `X` inside the `[ ]` to denote check mark `[X]`.)


- [x] **If creating a new file :**
  - [X] added links to it in the README files ?
  - [X] included tests with it ?
  - [x] added description (overview of algorithm, time and space complexity, and possible edge case) in docstrings ?

- [ ] **if done some changes :**
  - [ ] wrote short description in the PR explaining what the changes do ?
  - [ ] Fixes #[issue number] if related to any issue

- [ ] **other**



Patch:
diff --git a/README.md b/README.md
index c2c62f2..f30d452 100644
--- a/README.md
+++ b/README.md
@@ -190,6 +190,7 @@ If you want to uninstall algorithms, it is as simple as:
 - [maths](algorithms/maths)
     - [base_conversion](algorithms/maths/base_conversion.py)
     - [combination](algorithms/maths/combination.py)
+    - [cosine_similarity](algorithms/maths/cosine_similarity.py)
     - [decimal_to_binary_ip](algorithms/maths/decimal_to_binary_ip.py)
     - [euler_totient](algorithms/maths/euler_totient.py)
     - [extended_gcd](algorithms/maths/extended_gcd.py)
diff --git a/algorithms/maths/__init__.py b/algorithms/maths/__init__.py
index 7a3fb7b..7028a0a 100644
--- a/algorithms/maths/__init__.py
+++ b/algorithms/maths/__init__.py
@@ -14,3 +14,4 @@ from .pythagoras import *
 from .rabin_miller import *
 from .rsa import *
 from .combination import *
+from .cosine_similarity import *
diff --git a/algorithms/maths/cosine_similarity.py b/algorithms/maths/cosine_similarity.py
new file mode 100644
index 0000000..831e344
--- /dev/null
+++ b/algorithms/maths/cosine_similarity.py
@@ -0,0 +1,42 @@
+"""
+Calculate cosine similarity between given two 1d list.
+Two list must have the same length.
+
+Example:
+cosine_similarity([1, 1, 1], [1, 2, -1])  # output : 0.47140452079103173
+"""
+import math
+
+
+def _l2_distance(vec):
+    """
+    Calculate l2 distance from two given vectors.
+    """
+    norm = 0.
+    for e in vec:
+        norm += e * e
+    norm = math.sqrt(norm)
+    return norm
+
+
+def cosine_similarity(a, b):
+    """
+    Calculate cosine similarity between given two vectors
+    :type a: list
+    :type b: list
+    """
+    if len(a) != len(b):
+        raise ValueError("The two vectors must be the same length. Got shape " + str(len(a)) + " and " + str(len(b)))
+
+    norm_a = _l2_distance(a)
+    norm_b = _l2_distance(b)
+
+    similarity = 0.
+
+    # Calculate the dot product of two vectors
+    for ae, be in zip(a, b):
+        similarity += ae * be
+
+    similarity /= (norm_a * norm_b)
+
+    return similarity


Test patch:
diff --git a/tests/test_maths.py b/tests/test_maths.py
index dd1d0e1..850cd5d 100644
--- a/tests/test_maths.py
+++ b/tests/test_maths.py
@@ -16,6 +16,7 @@ from algorithms.maths import (
     encrypt, decrypt,
     combination, combination_memo,
     hailstone,
+    cosine_similarity,
 )
 
 import unittest
@@ -301,5 +302,21 @@ class TestHailstone(unittest.TestCase):
         self.assertEqual([10, 5, 16, 8, 4, 2, 1], hailstone.hailstone(10))
 
 
+class TestCosineSimilarity(unittest.TestCase):
+    """[summary]
+    Test for the file cosine_similarity.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+    def test_cosine_similarity(self):
+        vec_a = [1, 1, 1]
+        vec_b = [-1, -1, -1]
+        vec_c = [1, 2, -1]
+        self.assertAlmostEqual(cosine_similarity(vec_a, vec_a), 1)
+        self.assertAlmostEqual(cosine_similarity(vec_a, vec_b), -1)
+        self.assertAlmostEqual(cosine_similarity(vec_a, vec_c), 0.4714045208)
+
+
 if __name__ == "__main__":
     unittest.main()