Merge pull request keon#379 from christianbender/add_machine_learning

Christian Bender · web-flow · commit 010dce374b52 · 2018-08-02T15:09:21.000+02:00
added nearest neighbor algorithm - machine-learning
diff --git a/README.md b/README.md
@@ -350,6 +350,8 @@ If you want to uninstall algorithms, it is as simple as:
         - [simplify_path](algorithms/unix/path/simplify_path.py)
 - [union-find](algorithms/union-find)
     - [count_islands](algorithms/union-find/count_islands.py)
+- [machine-learning](algorithms/machine-learning)
+    - [nearest neighbor classification](algorithms/machine-learning/nearest_neighbor.py)
 
 ## Contributors
 The repo is maintained by
diff --git a/algorithms/ml/nearest_neighbor.py b/algorithms/ml/nearest_neighbor.py
@@ -0,0 +1,41 @@
+import math
+
+def distance(x,y):
+    """[summary]
+    HELPER-FUNCTION
+    calculates the (eulidean) distance between vector x and y.
+
+    Arguments:
+        x {[tuple]} -- [vector]
+        y {[tuple]} -- [vector]
+    """
+    assert len(x) == len(y), "The vector must have same length"
+    result = ()
+    sum = 0
+    for i in range(len(x)):
+        result += (x[i] -y[i],)
+    for component in result:
+        sum += component**2
+    return math.sqrt(sum)
+
+
+def nearest_neighbor(x, tSet):
+    """[summary]
+    Implements the nearest neighbor algorithm
+
+    Arguments:
+        x {[tupel]} -- [vector]
+        tSet {[dict]} -- [training set]
+
+    Returns:
+        [type] -- [result of the AND-function]
+    """
+    assert isinstance(x, tuple) and isinstance(tSet, dict)
+    current_key = ()
+    min_d = float('inf')
+    for key in tSet:
+        d = distance(x, key)
+        if d < min_d:
+            min_d = d
+            current_key = key
+    return tSet[current_key]
diff --git a/tests/test_ml.py b/tests/test_ml.py
@@ -0,0 +1,31 @@
+from algorithms.ml.nearest_neighbor import (
+    distance,
+    nearest_neighbor
+)
+
+import unittest
+
+class TestML(unittest.TestCase):
+    def setUp(self):
+        # train set for the AND-function
+        self.trainSetAND = {(0,0) : 0, (0,1) :0, (1,0) : 0, (1,1) : 1} 
+
+        # train set for light or dark colors
+        self.trainSetLight = {(11, 98, 237) : 'L', (3, 39, 96) : 'D', (242, 226, 12) : 'L', (99, 93, 4) : 'D',
+        (232, 62, 32) : 'L', (119, 28, 11) : 'D', (25, 214, 47) : 'L', (89, 136, 247) : 'L',
+        (21, 34, 63) : 'D', (237, 99, 120) : 'L', (73, 33, 39) : 'D'}
+    def test_nearest_neighbor(self):
+        # AND-function
+        self.assertEqual(nearest_neighbor((1,1), self.trainSetAND), 1)
+        self.assertEqual(nearest_neighbor((0,1), self.trainSetAND), 0)
+
+        # dark/light color test
+        self.assertEqual(nearest_neighbor((31, 242, 164), self.trainSetLight), 'L')
+        self.assertEqual(nearest_neighbor((13, 94, 64), self.trainSetLight), 'D')
+        self.assertEqual(nearest_neighbor((230, 52, 239), self.trainSetLight), 'L')
+    def test_distance(self):
+        self.assertAlmostEqual(distance((1,2,3), (1,0,-1)), 4.47, 2)
+
+        
+if __name__ == "__main__":
+    unittest.main()
