Repository: alteryx/woodwork
Pull request #1501 (2022-08-16 21:35:02)

Heuristics for Mutual Information
Doc on chosen heuristic has been shared.

codecov[bot]: # [Codecov](https://codecov.io/gh/alteryx/woodwork/pull/1501?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=alteryx) Report
> Merging [#1501](https://codecov.io/gh/alteryx/woodwork/pull/1501?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=alteryx) (8a8caf3) into [main](https://codecov.io/gh/alteryx/woodwork/commit/66352cc8bb370610d6defed28f176e7a138d4560?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=alteryx) (66352cc) will **decrease** coverage by `80.41%`.
> The diff coverage is `1.85%`.

> :exclamation: Current head 8a8caf3 differs from pull request most recent head 39065cd. Consider uploading reports for the commit 39065cd to get more accurate results

```diff
@@             Coverage Diff             @@
##             main    #1501       +/-   ##
===========================================
- Coverage   98.70%   18.28%   -80.42%     
===========================================
  Files          95       95               
  Lines       10708    10761       +53     
===========================================
- Hits        10569     1968     -8601     
- Misses        139     8793     +8654     
```


| [Impacted Files](https://codecov.io/gh/alteryx/woodwork/pull/1501?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=alteryx) | Coverage Δ | |
|---|---|---|
| [woodwork/table\_accessor.py](https://codecov.io/gh/alteryx/woodwork/pull/1501/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=alteryx#diff-d29vZHdvcmsvdGFibGVfYWNjZXNzb3IucHk=) | `51.68% <ø> (-48.32%)` | :arrow_down: |
| [woodwork/tests/accessor/test\_statistics.py](https://codecov.io/gh/alteryx/woodwork/pull/1501/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=alteryx#diff-d29vZHdvcmsvdGVzdHMvYWNjZXNzb3IvdGVzdF9zdGF0aXN0aWNzLnB5) | `0.00% <0.00%> (-100.00%)` | :arrow_down: |
| [woodwork/statistics\_utils/\_get\_dependence\_dict.py](https://codecov.io/gh/alteryx/woodwork/pull/1501/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=alteryx#diff-d29vZHdvcmsvc3RhdGlzdGljc191dGlscy9fZ2V0X2RlcGVuZGVuY2VfZGljdC5weQ==) | `12.62% <5.26%> (-87.38%)` | :arrow_down: |
| [woodwork/tests/test\_config.py](https://codecov.io/gh/alteryx/woodwork/pull/1501/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=alteryx#diff-d29vZHdvcmsvdGVzdHMvdGVzdF9jb25maWcucHk=) | `0.00% <0.00%> (-100.00%)` | :arrow_down: |
| [woodwork/tests/test\_version.py](https://codecov.io/gh/alteryx/woodwork/pull/1501/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=alteryx#diff-d29vZHdvcmsvdGVzdHMvdGVzdF92ZXJzaW9uLnB5) | `0.00% <0.00%> (-100.00%)` | :arrow_down: |
| [woodwork/tests/utils/test\_utils.py](https://codecov.io/gh/alteryx/woodwork/pull/1501/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=alteryx#diff-d29vZHdvcmsvdGVzdHMvdXRpbHMvdGVzdF91dGlscy5weQ==) | `0.00% <0.00%> (-100.00%)` | :arrow_down: |
| [woodwork/tests/utils/test\_concat.py](https://codecov.io/gh/alteryx/woodwork/pull/1501/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=alteryx#diff-d29vZHdvcmsvdGVzdHMvdXRpbHMvdGVzdF9jb25jYXQucHk=) | `0.00% <0.00%> (-100.00%)` | :arrow_down: |
| [woodwork/tests/type\_system/conftest.py](https://codecov.io/gh/alteryx/woodwork/pull/1501/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=alteryx#diff-d29vZHdvcmsvdGVzdHMvdHlwZV9zeXN0ZW0vY29uZnRlc3QucHk=) | `0.00% <0.00%> (-100.00%)` | :arrow_down: |
| [woodwork/tests/utils/test\_read\_file.py](https://codecov.io/gh/alteryx/woodwork/pull/1501/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=alteryx#diff-d29vZHdvcmsvdGVzdHMvdXRpbHMvdGVzdF9yZWFkX2ZpbGUucHk=) | `0.00% <0.00%> (-100.00%)` | :arrow_down: |
| [woodwork/tests/accessor/test\_indexers.py](https://codecov.io/gh/alteryx/woodwork/pull/1501/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=alteryx#diff-d29vZHdvcmsvdGVzdHMvYWNjZXNzb3IvdGVzdF9pbmRleGVycy5weQ==) | `0.00% <0.00%> (-100.00%)` | :arrow_down: |
| ... and [59 more](https://codecov.io/gh/alteryx/woodwork/pull/1501/diff?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=alteryx) | |

Help us with your feedback. Take ten seconds to tell us [how you rate us](https://about.codecov.io/nps?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=alteryx). Have a feature suggestion? [Share it here.](https://app.codecov.io/gh/feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=alteryx)


Patch:
diff --git a/docs/source/release_notes.rst b/docs/source/release_notes.rst
index 15e20a3..126ab1f 100644
--- a/docs/source/release_notes.rst
+++ b/docs/source/release_notes.rst
@@ -6,6 +6,7 @@ Release Notes
 Future Release
 ==============
     * Enhancements
+        * Updated ``dependence_dict`` and ``mutual_information`` to drop to drop Categorical columns with a large number of unique values during mutual information calculation, non-dask only. (:pr:`1501`)
     * Fixes
         * Fix applying LatLong.transform to empty dask data (:pr:`1507`)
     * Changes
@@ -16,7 +17,7 @@ Future Release
         * Update development requirements and use latest for documentation (:pr:`1499`)
 
     Thanks to the following people for contributing to this release:
-    :user:`gsheni`, :user:`ParthivNaresh`, :user:`rwedge`
+    :user:`gsheni`, :user:`ParthivNaresh`, :user:`rwedge`, :user:`bchen1116`
 
 v0.17.2 August 5, 2022
 ======================
diff --git a/woodwork/statistics_utils/_get_dependence_dict.py b/woodwork/statistics_utils/_get_dependence_dict.py
index b81c444..670c4f5 100644
--- a/woodwork/statistics_utils/_get_dependence_dict.py
+++ b/woodwork/statistics_utils/_get_dependence_dict.py
@@ -1,3 +1,4 @@
+import warnings
 from collections import defaultdict
 from timeit import default_timer as timer
 
@@ -30,6 +31,7 @@ def _get_dependence_dict(
     extra_stats=False,
     min_shared=25,
     random_seed=0,
+    max_nunique=6000,
 ):
     """Calculates dependence measures between all pairs of columns in the DataFrame that
     support measuring dependence. Supports boolean, categorical, datetime, and numeric data.
@@ -74,6 +76,9 @@ def _get_dependence_dict(
             to measure accurately and will return a NaN value. Must be
             non-negative. Defaults to 25.
         random_seed (int): Seed for the random number generator. Defaults to 0.
+        max_nunique (int): The total maximum number of unique values for all large categorical columns (> 800 unique values).
+                Categorical columns will be dropped until this number is met or until there is only one large categorical column.
+                Defaults to 6000.
     Returns:
         list(dict): A list containing dictionaries that have keys `column_1`,
         `column_2`, and keys for the specified dependence measures. The list is
@@ -95,7 +100,19 @@ def _get_dependence_dict(
         valid_columns = pearson_columns
     if "mutual_info" in calc_order:
         mi_types = get_valid_mi_types()
-        mutual_columns = _get_valid_columns(dataframe, mi_types)
+        cols_to_drop = _find_large_categorical_columns(dataframe, max_nunique)
+        if len(cols_to_drop):
+            warnings.warn(
+                "Dropping columns {} to allow mutual information to run faster".format(
+                    cols_to_drop,
+                ),
+                UserWarning,
+            )
+        mutual_columns = [
+            col
+            for col in _get_valid_columns(dataframe, mi_types)
+            if col not in cols_to_drop
+        ]
         # pearson columns are a subset of mutual columns
         valid_columns = mutual_columns
 
@@ -203,3 +220,34 @@ def _get_valid_columns(dataframe, valid_types):
         if type(col.logical_type) in valid_types
     ]
     return valid_columns
+
+
+def _find_large_categorical_columns(datatable, total_unique=6000):
+    """Finds the categorical columns to drop to speed up mutual information calculations."""
+
+    def categorical_column_drop_helper(df):
+        cols_to_drop = []
+        cols_greater = df.columns[df.nunique().values > 800]
+        if len(cols_greater) < 2:
+            return cols_to_drop
+
+        df_uniques = df[cols_greater].nunique()
+        total = sum(df_uniques.to_numpy())
+        if total > total_unique:
+            # try to use mergesort to keep the order of the columns
+            if not _is_spark_dataframe(df):
+                drop = df_uniques.sort_values(ascending=False, kind="mergesort").index[
+                    0
+                ]
+            else:
+                drop = df_uniques.sort_values(ascending=False).index.tolist()[0]
+            cols_to_drop.append(drop)
+            df = df.drop(cols_to_drop, axis=1)
+            cols_to_drop += categorical_column_drop_helper(df)
+        return cols_to_drop
+
+    categoricals = datatable.ww.select("category").columns
+    # dask dataframe does not have support for `nunique`, but it should be a feature coming in a future release
+    if len(categoricals) and not _is_dask_dataframe(datatable):
+        return categorical_column_drop_helper(datatable[categoricals])
+    return []
diff --git a/woodwork/table_accessor.py b/woodwork/table_accessor.py
index d7cc093..d727215 100644
--- a/woodwork/table_accessor.py
+++ b/woodwork/table_accessor.py
@@ -891,6 +891,7 @@ class WoodworkTableAccessor:
         extra_stats=False,
         min_shared=25,
         random_seed=0,
+        max_nunique=6000,
     ):
         """
         Calculates mutual information between all pairs of columns in the DataFrame that
@@ -921,6 +922,9 @@ class WoodworkTableAccessor:
                 to measure accurately and will return a NaN value. Must be
                 non-negative. Defaults to 25.
             random_seed (int): Seed for the random number generator. Defaults to 0.
+            max_nunique (int): The total maximum number of unique values for all large categorical columns (> 800 unique values).
+                Categorical columns will be dropped until this number is met or until there is only one large categorical column.
+                Defaults to 6000.
         Returns:
             list(dict): A list containing dictionaries that have keys `column_1`,
             `column_2`, and `mutual_info` that is sorted in decending order by mutual info.
@@ -937,6 +941,7 @@ class WoodworkTableAccessor:
             extra_stats=extra_stats,
             min_shared=min_shared,
             random_seed=random_seed,
+            max_nunique=max_nunique,
         )
 
     def mutual_information(
@@ -948,6 +953,7 @@ class WoodworkTableAccessor:
         extra_stats=False,
         min_shared=25,
         random_seed=0,
+        max_nunique=6000,
     ):
         """Calculates mutual information between all pairs of columns in the DataFrame that
         support mutual information. Call woodwork.utils.get_valid_mi_types to see which Logical Types support
@@ -977,6 +983,9 @@ class WoodworkTableAccessor:
                 to measure accurately and will return a NaN value. Must be
                 non-negative. Defaults to 25.
             random_seed (int): Seed for the random number generator. Defaults to 0.
+            max_nunique (int): The total maximum number of unique values for all large categorical columns (> 800 unique values).
+                Categorical columns will be dropped until this number is met or until there is only one large categorical column.
+                Defaults to 6000.
         Returns:
             pd.DataFrame: A DataFrame containing mutual information with columns `column_1`,
             `column_2`, and `mutual_info` that is sorted in decending order by mutual info.
@@ -991,6 +1000,7 @@ class WoodworkTableAccessor:
             extra_stats=extra_stats,
             min_shared=min_shared,
             random_seed=random_seed,
+            max_nunique=max_nunique,
         )
         return pd.DataFrame(mutual_info)
 
@@ -1108,6 +1118,7 @@ class WoodworkTableAccessor:
         extra_stats=False,
         min_shared=25,
         random_seed=0,
+        max_nunique=6000,
     ):
         """Calculates dependence measures between all pairs of columns in the DataFrame that
         support measuring dependence. Supports boolean, categorical, datetime, and numeric data.
@@ -1152,6 +1163,9 @@ class WoodworkTableAccessor:
                 to measure accurately and will return a NaN value. Must be
                 non-negative. Defaults to 25.
             random_seed (int): Seed for the random number generator. Defaults to 0.
+            max_nunique (int): The total maximum number of unique values for all large categorical columns (> 800 unique values).
+                Categorical columns will be dropped until this number is met or until there is only one large categorical column.
+                Defaults to 6000.
         Returns:
             list(dict): A list containing dictionaries that have keys `column_1`,
             `column_2`, and keys for the specified dependence measures. The list is
@@ -1170,6 +1184,7 @@ class WoodworkTableAccessor:
             extra_stats=extra_stats,
             min_shared=min_shared,
             random_seed=random_seed,
+            max_nunique=max_nunique,
         )
 
     def dependence(
@@ -1182,6 +1197,7 @@ class WoodworkTableAccessor:
         extra_stats=False,
         min_shared=25,
         random_seed=0,
+        max_nunique=6000,
     ):
         """Calculates dependence measures between all pairs of columns in the DataFrame that
         support measuring dependence. Supports boolean, categorical, datetime, and numeric data.
@@ -1226,6 +1242,9 @@ class WoodworkTableAccessor:
                 to measure accurately and will return a NaN value. Must be
                 non-negative. Defaults to 25.
             random_seed (int): Seed for the random number generator. Defaults to 0.
+            max_nunique (int): The maximum number of unique values for large categorical columns (> 800 unique values).
+                Categorical columns will be dropped until this number is met or until there is only one large categorical column.
+                Defaults to 6000.
         Returns:
             pd.DataFrame: A DataFrame with the columns `column_1`,
             `column_2`, and keys for the specified dependence measures. The rows
@@ -1245,6 +1264,7 @@ class WoodworkTableAccessor:
             extra_stats=extra_stats,
             min_shared=min_shared,
             random_seed=random_seed,
+            max_nunique=max_nunique,
         )
         return pd.DataFrame(dep_dict)
 


Test patch:
diff --git a/woodwork/tests/accessor/test_statistics.py b/woodwork/tests/accessor/test_statistics.py
index 0fb9d59..0ce9544 100644
--- a/woodwork/tests/accessor/test_statistics.py
+++ b/woodwork/tests/accessor/test_statistics.py
@@ -506,6 +506,133 @@ def test_dependence_dropna():
     assert mi_df.equals(expected_df)
 
 
+@pytest.mark.parametrize(
+    "logical_types",
+    [
+        {"a_column": "Unknown"},
+        {"a_column": "Categorical"},
+        {"a_column": "SubRegionCode"},
+    ],
+)
+def test_dependence_drop_columns(logical_types):
+    log_types = {
+        "b_column": "Categorical",
+        "c_column": "Categorical",
+        "d_column": "Categorical",
+        **logical_types,
+    }
+    cat_values = {"a_column": [], "b_column": [], "c_column": [], "d_column": []}
+    categoricals_string = "some categorical_{}_{}"
+    for k in cat_values.keys():
+        num = 3001 if k in ["c_column", "d_column"] else 100
+        for n in range(4000):
+            # `a_column`, `c_column`, `d_column` all have 3001 unique values, while `b_column` has 100
+            cat_values[k].append(categoricals_string.format(k, n % num))
+
+    df = pd.DataFrame(cat_values)
+    df.ww.init(logical_types=log_types)
+    string_warning = r"Dropping columns \['c_column'\] to allow mutual information"
+    with pytest.warns(UserWarning, match=string_warning):
+        for dep_dict_str in [
+            str(df.ww.dependence_dict()),
+            str(df.ww.mutual_information_dict()),
+        ]:
+            # based on natural column ordering, "c_column" will be missing rather than "d_column"
+            # even though both have same number of uniques
+            assert "c_column" not in dep_dict_str
+            assert "d_column" in dep_dict_str
+            if logical_types["a_column"] == "Unknown":
+                assert "a_column" not in dep_dict_str
+            else:
+                assert "a_column" in dep_dict_str
+
+
+@pytest.mark.parametrize("nunique", [1000, 2001])
+def test_dependence_drop_columns_nunique(nunique):
+    log_types = {
+        "b_column": "Categorical",
+        "c_column": "Categorical",
+        "d_column": "Categorical",
+        "a_column": "Integer",
+    }
+    cat_values = {
+        "a_column": range(1000),
+        "b_column": [],
+        "c_column": [],
+        "d_column": [],
+    }
+    categoricals_string = "some categorical_{}_{}"
+    for k in ["b_column", "c_column", "d_column"]:
+        num = 1000 if k in ["c_column", "d_column"] else 100
+        for n in range(1000):
+            # `a_column`, `c_column`, `d_column` all have 1000 unique values, while `b_column` has 100
+            cat_values[k].append(categoricals_string.format(k, n % num))
+
+    df = pd.DataFrame(cat_values)
+    df.ww.init(logical_types=log_types)
+    for dep_dict_str in [
+        str(df.ww.dependence(max_nunique=nunique)),
+        str(df.ww.mutual_information(max_nunique=nunique)),
+    ]:
+        # based on natural column ordering, "c_column" will be missing rather than "d_column"
+        # even though both have same number of uniques
+        assert "d_column" in dep_dict_str
+        assert "a_column" in dep_dict_str
+        assert "b_column" in dep_dict_str
+        if nunique == 2001:
+            assert "c_column" in dep_dict_str
+        else:
+            assert "c_column" not in dep_dict_str
+
+
+@pytest.mark.parametrize("df_type", ["pandas", "dask", "spark"])
+def test_dependence_drop_columns_dask_spark(df_type):
+    log_types = {
+        "b_column": "Categorical",
+        "c_column": "Categorical",
+        "a_column": "Categorical",
+    }
+    cat_values = {
+        "a_column": [],
+        "b_column": [],
+        "c_column": [],
+    }
+    categoricals_string = "some categorical_{}_{}"
+    for k in cat_values.keys():
+        num = 1000 if k in ["a_column", "c_column"] else 100
+        for n in range(1000):
+            # `a_column`, `c_column`, all have 1000 unique values, while `b_column` has 100
+            cat_values[k].append(categoricals_string.format(k, n % num))
+
+    df = pd.DataFrame(cat_values)
+    if df_type == "dask":
+        dd = pytest.importorskip(
+            "dask.dataframe",
+            reason="Dask not installed, skipping",
+        )
+        df = dd.from_pandas(df, npartitions=1)
+    elif df_type == "spark":
+        ps = pytest.importorskip(
+            "pyspark.pandas",
+            reason="Spark not installed, skipping",
+        )
+        df = ps.from_pandas(df)
+
+    df.ww.init(logical_types=log_types)
+    for dep_dict_str in [
+        str(df.ww.dependence(max_nunique=1000)),
+        str(df.ww.mutual_information(max_nunique=1000)),
+    ]:
+        # based on natural column ordering, "a_column" will be missing rather than "c_column"
+        # even though both have same number of uniques
+        assert "c_column" in dep_dict_str
+        if df_type == "dask":
+            assert "a_column" in dep_dict_str
+        else:
+            assert "a_column" not in dep_dict_str
+        assert "b_column" in dep_dict_str
+
+
 @patch("woodwork.table_accessor._get_dependence_dict")
 def test_pearson_dict(_get_dependence_dict, df_mi, mock_callback):
     df_mi.ww.init()
@@ -575,6 +702,7 @@ def test_mutual_dict(_get_dependence_dict, df_mi, mock_callback):
         extra_stats=True,
         min_shared=25,
         random_seed=5,
+        max_nunique=6000,
     )
 
 
@@ -599,6 +727,7 @@ def test_mutual(df_mi, mock_callback):
         extra_stats=True,
         min_shared=25,
         random_seed=5,
+        max_nunique=6000,
     )
 
 
@@ -1281,7 +1410,7 @@ def test_value_counts(categorical_df):
         updated_results = []
         for items in expected_cat1:
             updated_results.append(
-                {k: (str(v) if k == "value" else v) for k, v in items.items()}
+                {k: (str(v) if k == "value" else v) for k, v in items.items()},
             )
         expected_cat1 = updated_results