Repository: Rambatino/CHAID

Issue:
Valid splits discounted when most significant split is generated below base size

Discussion:
codecov[bot]: # [Codecov](https://codecov.io/gh/Rambatino/CHAID/pull/83?src=pr&el=h1) Report
> Merging [#83](https://codecov.io/gh/Rambatino/CHAID/pull/83?src=pr&el=desc) into [master](https://codecov.io/gh/Rambatino/CHAID/commit/6a29f62c0ca5cee05eaa9ab512071d5048a85123?src=pr&el=desc) will **decrease** coverage by `0.48%`.
> The diff coverage is `93.33%`.

[![Impacted file tree graph](https://codecov.io/gh/Rambatino/CHAID/pull/83/graphs/tree.svg?token=SkOhpCa986&src=pr&height=150&width=650)](https://codecov.io/gh/Rambatino/CHAID/pull/83?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master      #83      +/-   ##
==========================================
- Coverage   92.67%   92.18%   -0.49%     
==========================================
  Files           7        7              
  Lines         505      512       +7     
==========================================
+ Hits          468      472       +4     
- Misses         37       40       +3
```


| [Impacted Files](https://codecov.io/gh/Rambatino/CHAID/pull/83?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [CHAID/stats.py](https://codecov.io/gh/Rambatino/CHAID/pull/83?src=pr&el=tree#diff-Q0hBSUQvc3RhdHMucHk=) | `98.4% <90%> (-0.21%)` | :arrow_down: |
| [CHAID/column.py](https://codecov.io/gh/Rambatino/CHAID/pull/83?src=pr&el=tree#diff-Q0hBSUQvY29sdW1uLnB5) | `89.09% <96%> (-0.2%)` | :arrow_down: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/Rambatino/CHAID/pull/83?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/Rambatino/CHAID/pull/83?src=pr&el=footer). Last update [6a29f62...66a2080](https://codecov.io/gh/Rambatino/CHAID/pull/83?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).


Patch:
diff --git a/CHAID/column.py b/CHAID/column.py
index ce1a712..444c073 100644
--- a/CHAID/column.py
+++ b/CHAID/column.py
@@ -3,6 +3,14 @@ from math import isnan
 from itertools import combinations
 from .mapping_dict import MappingDict
 
+def is_sorted(ndarr, nan_val=None):
+    store = []
+    for arr in ndarr:
+        if arr == [] or len(arr) == 1: continue
+        if nan_val is not None and nan_val in arr:
+            arr.remove(nan_val)
+        store.append(arr[-1] - arr[0] == len(arr) - 1)
+    return all(store)
 
 class Column(object):
     """
@@ -49,10 +57,27 @@ class Column(object):
 
     def deep_copy(self):
         """
-        Returns a deep copy.
+        Returns a deep copy
         """
         raise NotImplementedError
 
+    def bell_set(self, collection, ordinal=False):
+        """
+        Calculates the Bell set
+        """
+        if len(collection) == 1:
+            yield [ collection ]
+            return
+
+        first = collection[0]
+        for smaller in self.bell_set(collection[1:]):
+            for n, subset in enumerate(smaller):
+                if not ordinal or (ordinal and is_sorted(smaller[:n] + [[ first ] + subset] + smaller[n+1:], self._nan)):
+                    yield smaller[:n] + [[ first ] + subset] + smaller[n+1:]
+
+            if not ordinal or (ordinal and is_sorted([ [ first ] ] + smaller, self._nan)):
+                yield [ [ first ] ] + smaller
+
 
 class NominalColumn(Column):
     """
@@ -124,6 +149,11 @@ class NominalColumn(Column):
     def possible_groupings(self):
         return combinations(self._groupings.keys(), 2)
 
+    def all_combinations(self):
+        bell_set = self.bell_set(sorted(list(self._groupings.keys())))
+        next(bell_set)
+        return bell_set
+
     def group(self, x, y):
         self._groupings[x] += self._groupings[y]
         del self._groupings[y]
@@ -215,6 +245,12 @@ class OrdinalColumn(Column):
                 ]
         return self._possible_groups.__iter__()
 
+    def all_combinations(self):
+        bell_set = self.bell_set(sorted(list(self._groupings.keys())), True)
+        next(bell_set)
+        return bell_set
+
+
     def group(self, x, y):
         self._possible_groups = None
         if y != self._nan:
diff --git a/CHAID/stats.py b/CHAID/stats.py
index 6789241..212923d 100644
--- a/CHAID/stats.py
+++ b/CHAID/stats.py
@@ -76,68 +76,37 @@ class Stats(object):
             if len(list(ind_var.possible_groupings())) == 0:
                 split.invalid_reason = InvalidSplitReason.PURE_NODE
 
-            while next(ind_var.possible_groupings(), None) is not None:
-                choice, highest_p_join, split_chi = None, None, None
-                for comb in ind_var.possible_groupings():
-                    col1_freq = freq[comb[0]]
-                    col2_freq = freq[comb[1]]
-
-                    keys = set(col1_freq.keys()).union(col2_freq.keys())
-
-                    n_ij = np.array([
-                        [col1_freq.get(k, 0) for k in keys],
-                        [col2_freq.get(k, 0) for k in keys]
-                    ])
+            choice, highest_p_join, split_chi, dof = None, None, None, None
+            for comb in ind_var.all_combinations():
+                freqs = [ sum( [ cl.Counter(freq[key]) for key in c ], cl.Counter()) for c in comb ]
+                keys = set(sum([ list(f.keys()) for f in freqs ], []))
 
-                    chi, p_split, dof = chisquare(n_ij, dep.weights is not None)
-
-                    if choice is None or p_split > highest_p_join or (p_split == highest_p_join and chi > split_chi):
-                        choice, highest_p_join, split_chi = comb, p_split, chi
-
-                invalid_reason = None
-                sufficient_split = highest_p_join < self.alpha_merge
-                if not sufficient_split: invalid_reason = InvalidSplitReason.ALPHA_MERGE
-
-                sufficient_split = sufficient_split and all(
-                    # what if a greater p-value on a different grouping would satisfy alpha merge _and_ min_child_node_size?
-                    sum(node_v.values()) >= self.min_child_node_size for node_v in freq.values()
+                n_ij = np.array(
+                    [ [ col.get(k, 0) for k in keys ] for col in freqs ]
                 )
-                if not sufficient_split: invalid_reason = InvalidSplitReason.MIN_CHILD_NODE_SIZE
 
-                if sufficient_split and len(freq.values()) > 1:
-                    n_ij = np.array([
-                        [f[dep_val] for dep_val in all_dep] for f in freq.values()
-                    ])
+                chi, p_split, dof = chisquare(n_ij, dep.weights is not None)
 
-                    dof = (n_ij.shape[0] - 1) * (n_ij.shape[1] - 1)
-                    chi, p_split, dof = chisquare(n_ij, dep.weights is not None)
+                if (choice is None or p_split < highest_p_join or (p_split == highest_p_join and chi > split_chi)) and (n_ij.sum(axis=1) >= self.min_child_node_size).all() and p_split < self.alpha_merge:
+                    choice, highest_p_join, split_chi = comb, p_split, chi
 
-                    temp_split = Split(i, ind_var.groups(), chi, p_split, dof, split_name=ind_var.name)
-                    better_split = not split.valid() or p_split < split.p or (p_split == split.p and chi > split.score)
+            temp_split = Split(i, choice, split_chi, highest_p_join, dof, split_name=ind_var.name)
+            better_split = (not split.valid() or p_split < split.p or (p_split == split.p and chi > split.score)) and choice is not None
+            if better_split: split, temp_split = temp_split, split
 
-                    if better_split:
-                        split, temp_split = temp_split, split
-
-                    chi_threshold = self.split_threshold * split.score
+            if split.valid() and choice is not None:
+                chi_threshold = self.split_threshold * split.score
 
-                    if temp_split.valid() and temp_split.score >= chi_threshold:
-                        for sur in temp_split.surrogates:
-                            if sur.column_id != i and sur.score >= chi_threshold:
-                                split.surrogates.append(sur)
+                if temp_split.valid() and temp_split.score >= chi_threshold:
+                    for sur in temp_split.surrogates:
+                        if sur.column_id != i and sur.score >= chi_threshold:
+                            split.surrogates.append(sur)
 
-                        temp_split.surrogates = []
-                        split.surrogates.append(temp_split)
+                    temp_split.surrogates = []
+                    split.surrogates.append(temp_split)
 
-                    break
-                else:
-                    split.invalid_reason = invalid_reason
+                split.sub_split_values(ind[split.column_id].metadata)
 
-                ind_var.group(choice[0], choice[1])
-                for val, count in freq[choice[1]].items():
-                    freq[choice[0]][val] += count
-                del freq[choice[1]]
-        if split.valid():
-            split.sub_split_values(ind[split.column_id].metadata)
         return split
 
     def best_con_split(self, ind, dep):
diff --git a/README.md b/README.md
index 1982bee..71a197f 100644
--- a/README.md
+++ b/README.md
@@ -60,7 +60,7 @@ cols = [
   NominalColumn(ndarr[:,1], name='b')
   NominalColumn(ndarr[:,2], name='c')
 ]
-tree = Tree.from_numpy(cols, NominalColumn(arr, name='d'), {'min_child_node_size': 5})
+tree = Tree(cols, NominalColumn(arr, name='d'), {'min_child_node_size': 5})
 
 >>> tree.print_tree()
 ([], {1: 5, 2: 5}, ('a', p=0.001565402258, score=10.0, groups=[[1], [2]]), dof=1))


Test patch:
diff --git a/tests/setup_tests.py b/tests/setup_tests.py
index de72e47..c8f7eea 100644
--- a/tests/setup_tests.py
+++ b/tests/setup_tests.py
@@ -13,7 +13,6 @@ sys.path = [ROOT_FOLDER] + sys.path
 
 import CHAID
 
-
 def islist(a):
     return isinstance(a, Iterable) and not isinstance(a, str)
 
diff --git a/tests/test_nominal_column.py b/tests/test_nominal_column.py
index 34e4916..fc81df9 100644
--- a/tests/test_nominal_column.py
+++ b/tests/test_nominal_column.py
@@ -120,6 +120,24 @@ def test_fix_metadata_if_passed_in():
     nominal = CHAID.NominalColumn(arr, metadata={1.0: 'Cat', 2.0: 'Haz', 3.0: 'Cheezburger'})
     assert [nominal.metadata[x] for x in nominal.arr] == ['Cat', 'Haz', 'Cheezburger']
 
+def test_all_combinations():
+    arr = np.array([1.0, 2.0, 3.0, 4.0])
+    nominal = CHAID.NominalColumn(arr)
+    assert [ i for i in nominal.all_combinations()] == [[[0.0], [1.0, 2.0, 3.0]],
+                                          [[0.0, 1.0], [2.0, 3.0]],
+                                          [[1.0], [0.0, 2.0, 3.0]],
+                                          [[0.0], [1.0], [2.0, 3.0]],
+                                          [[0.0, 1.0, 2.0], [3.0]],
+                                          [[1.0, 2.0], [0.0, 3.0]],
+                                          [[0.0], [1.0, 2.0], [3.0]],
+                                          [[0.0, 2.0], [1.0, 3.0]],
+                                          [[2.0], [0.0, 1.0, 3.0]],
+                                          [[0.0], [2.0], [1.0, 3.0]],
+                                          [[0.0, 1.0], [2.0], [3.0]],
+                                          [[1.0], [0.0, 2.0], [3.0]],
+                                          [[1.0], [2.0], [0.0, 3.0]],
+                                          [[0.0], [1.0], [2.0], [3.0]]]
+
 
 class TestDeepCopy(TestCase):
     """ Test fixture class for deep copy method """
diff --git a/tests/test_ordinal_column.py b/tests/test_ordinal_column.py
index 8b7f2ed..60758b9 100644
--- a/tests/test_ordinal_column.py
+++ b/tests/test_ordinal_column.py
@@ -6,6 +6,36 @@ import numpy as np
 from numpy import nan
 from setup_tests import list_ordered_equal, list_unordered_equal, CHAID
 
+def test_all_ordinal_combinations():
+    arr = np.array([1.0, 2.0, 3.0, 4.0])
+    ordinal = CHAID.OrdinalColumn(arr)
+    assert [
+        i for i in ordinal.all_combinations()
+    ] == [[[1], [2, 3, 4]],
+         [[1, 2], [3, 4]],
+         [[1], [2], [3, 4]],
+         [[1, 2, 3], [4]],
+         [[1], [2, 3], [4]],
+         [[1, 2], [3], [4]],
+         [[1], [2], [3], [4]]]
+
+def test_all_ordinal_combinations_with_nan():
+    arr = np.array([1.0, 2.0, 3.0, np.nan])
+    ordinal = CHAID.OrdinalColumn(arr)
+    nan_val = np.array([np.nan]).astype(int)[0]
+    assert [
+        i for i in ordinal.all_combinations()
+    ] == [[[nan_val], [1, 2, 3]],
+          [[nan_val, 1], [2, 3]],
+          [[1], [nan_val, 2, 3]],
+          [[nan_val], [1], [2, 3]],
+          [[nan_val, 1, 2], [3]],
+          [[1, 2], [nan_val, 3]],
+          [[nan_val], [1, 2], [3]],
+          [[nan_val, 1], [2], [3]],
+          [[1], [nan_val, 2], [3]],
+          [[1], [2], [nan_val, 3]],
+          [[nan_val], [1], [2], [3]]]
 
 class TestOrdinalDeepCopy(TestCase):
     """ Test fixture class for deep copy method """
diff --git a/tests/test_tree.py b/tests/test_tree.py
index e411020..1a2cafb 100644
--- a/tests/test_tree.py
+++ b/tests/test_tree.py
@@ -126,7 +126,7 @@ def test_best_split_with_combination():
     assert list_ordered_equal(ndarr, orig_ndarr), 'Calling chaid should have no side affects for original numpy arrays'
     assert list_ordered_equal(arr, orig_arr), 'Calling chaid should have no side affects for original numpy arrays'
     assert split.column_id == 0, 'Identifies correct column to split on'
-    assert list_unordered_equal(split.split_map, [[1], [2], [3]]), 'Correctly identifies catagories'
+    assert list_unordered_equal(split.split_map, [[1], [2, 3]]), 'Correctly identifies categories'
     assert list_unordered_equal(split.surrogates, []), 'No surrogates should be generated'
     assert split.p < 0.015
 
@@ -138,13 +138,13 @@ def test_new_columns_constructor():
     orientation = np.array([0,0,1,1,0,0,1,1,0,0,1,2,2,2,2,2,2,2,2,1])
     age = np.array([0,1,1,0,2,2,2,2,1,1,1,0,0,0,0,0,0,0,0,0])
     income = np.array([0,0,1,1,2,0,1,1,1,0,1,0,0,0,0,0,0,0,0,0])
-
+    metadata = {0: '0-5', 1: '6-10', 2: '11-15'}
     cols = [
-        CHAID.OrdinalColumn(orientation, name="orientation"),
-        CHAID.OrdinalColumn(age, name="age", metadata={0: '0-5', 1: '6-10', 2: '11-15'}),
+        CHAID.OrdinalColumn(orientation, name="orientation", metadata=metadata),
+        CHAID.OrdinalColumn(age, name="age", metadata=metadata),
     ]
     tree = CHAID.Tree(cols, CHAID.NominalColumn(income), {'min_child_node_size': 1})
-    assert tree.tree_store[0].split.groupings == "[['0-5'], ['6-10', '11-15']]"
+    assert tree.tree_store[0].split.groupings == "[['0-5'], ['6-10'], ['11-15']]"
 
 
 class TestSurrogate(TestCase):
@@ -313,7 +313,11 @@ def test_node_predictions():
     ndarr = np.transpose(np.vstack([gender]))
     tree = CHAID.Tree.from_numpy(ndarr, income, alpha_merge=0.9, max_depth=1,
                       min_child_node_size=1, min_parent_node_size=1)
-    assert (tree.node_predictions() == np.array([1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 3, 3, 3., 3, 3, 3, 3, 3, 2])).all() == True
+
+    assert (tree.node_predictions() == np.array([
+        2.0, 2.0, 1.0, 1.0, 2.0, 2.0, 1.0, 1.0, 2.0, 2.0, 1.0, 2.0, 2.0, 2.0,
+        2.0, 2.0, 2.0, 2.0, 2.0, 1.0
+    ])).all() == True
 
 class TestTreeGenerated(TestCase):
     """ Test case class to check that the tree is correcly lazy loaded """
@@ -369,7 +373,7 @@ class TestBugFixes(TestCase):
 
     def test_incorrect_weighted_counts(self):
         """
-        Fix bug wherby the weights was using the class weights
+        Fix bug whereby the weights was using the class weights
         and not the sliced weights in node()
         """
         tree = CHAID.Tree.from_numpy(self.ndarr, self.arr, alpha_merge=0.999, weights=self.wt, max_depth=5, min_parent_node_size=2, min_child_node_size=0)
@@ -389,6 +393,30 @@ class TestBugFixes(TestCase):
             no_exception = False
         assert no_exception, 'Raised error while printing the tree'
 
+    def test_splits_shouldnt_carry_on_splitting_below_min_child_node_size(self):
+        """
+        Fix bug whereby no splits occur when valid split is segmented below
+        min_child_node_size threshold
+        """
+        region = np.array([
+            1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+            1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 2, 3, 2, 2, 2,
+            3, 2, 4, 4, 2, 4, 4, 4, 2, 2, 2, 2, 3, 2, 3, 2, 3, 2, 2, 2])
+        age = np.array([
+            3, 4, 4, 3, 2, 4, 2, 3, 3, 2, 2, 3, 4, 3, 4, 2, 2, 3, 2, 3,
+            2, 4, 4, 3, 2, 3, 1, 2, 4, 4, 3, 4, 4, 3, 2, 4, 2, 3, 3, 2,
+            2, 3, 4, 3, 4, 2, 2, 3, 2, 3, 2, 4, 4, 3, 2, 3, 1, 2, 4, 4])
+        gender = np.array([
+            1, 2, 1, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 2,
+            2, 2, 2, 1, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 2, 2, 2, 1, 2,
+            2, 2, 2, 2, 1, 1, 1, 1, 1, 2, 2, 2, 2, 1, 2, 1, 2, 1, 2, 2])
+        lover = np.array([1] * 25 + [0] * 35)
+        tree = CHAID.Tree.from_numpy(
+            np.vstack([region, age, gender]).transpose(),
+            lover,
+            alpha_merge=0.05
+        )
+        assert len(tree.tree_store) == 3
 
 class TestStoppingRules(TestCase):
     """ Testing that stopping rules are being applied correctly """
@@ -403,7 +431,7 @@ class TestStoppingRules(TestCase):
         Check that minimum child node size causes the tree to
         terminate correctly
         """
-        tree = CHAID.Tree.from_numpy(self.ndarr, self.arr, alpha_merge=0.999, max_depth=5, min_child_node_size=11)
+        tree = CHAID.Tree.from_numpy(self.ndarr, self.arr, alpha_merge=0.999, max_depth=5, min_child_node_size=31)
         assert len(tree.tree_store) == 1
 
     def test_min_child_node_size_does_not_stop_for_unweighted_case(self):
@@ -420,7 +448,8 @@ class TestStoppingRules(TestCase):
         terminate correctly
         """
         tree = CHAID.Tree.from_numpy(self.ndarr, self.arr, alpha_merge=0.999, weights=self.wt, max_depth=5, min_child_node_size=10.7)
-        assert len(tree.tree_store) == 4
+        assert len(tree.tree_store) == 3
+        assert round(tree.tree_store[0].split.p, 5) == 0.00029
 
     def test_min_child_node_size_does_not_stop_for_weighted_case(self):
         """