Scalable blob building

[yoid2000]

Currently the blob system doesn't scale beyond 10 or so columns. This is because we currently build every possible sub-table.

What is needed instead are smarter sub-tables, where we avoid building sub-tables that have low quality because one or more columns are independent of the others.

[yoid2000]

Basic suggested approach:

Establish a limit on the number of sub-tables (say 10k).

Add a phase whereby we determine which sub-tables we want to build without actually building them. We do this by first building all the 2dim subtables, measuring their dependence, and then using these measures to determine the quality of sub-tables.

We go through a process where we explore the most promising 3dim sub-tables (i.e. start with the highest dependence 2dim sub-tables), then the most promising 4dim etc, In the process, we record what max_weight and merge_thresh would have led to these sub-tables under the current blob-building procedure.

[yoid2000]

Currently we have code like this:

        average_quality = sum(dependency_matrix[col, c] for c in cluster.columns) / len(cluster.columns)

            # Skip if below threshold or above weight limit.
            if average_quality < merge_thresh or (
                len(cluster.columns) > DERIVED_COLS_MIN and cluster.total_entropy + col_weights[col] > capacity
            ):

Context of above code is in a loop that goes through the permutation columns in order, and measures the sub-table quality as it does until quality drops below merge_thresh.

Note merge_thresh is default 0.1. As the number of columns in a sub-table increases, the effect of a single low-dependence pair is reduced. But this might not matter in practice (i.e., we don't need some additional parameter like min_dependence or something)

max_weight is related to the sum of column weights (default 15). This puts some kind of limit on sub-table size. Column weights are computed like this:

col_weights = list(_col_weight(col) for col in context.entropy_1dim)

So, related to the entropy of the column, which basically is determined by the number of distinct vals IIRC.

ok, for now, just try to measure average_quality and col_weights and see how they behave.

[yoid2000]

I suspect the way to do this is to use average_quality to find the best sub-tables in the builder, and then use a solver to find the best clustering in the reader.

[yoid2000]

Look into "mutual information" as a measure of dependency between columns.

From chatgpt:

Absolutely, you're right! Traditional correlation measures like Pearson's only capture linear relationships. Two variables can indeed have a strong non-linear relationship and show little to no correlation. This is where other measures come into play:

Mutual Information: Measures any kind of dependency between variables, not just linear. It captures both linear and non-linear relationships.

Distance Correlation: Captures both linear and non-linear associations, providing a more comprehensive view of dependency between variables.

Copula-based Measures: Capture dependency structures between variables, accounting for non-linearity and tail dependencies.

---

From other information, looks like mutual information is likely the best choice.

[yoid2000]

Ok, mutual information turns out to be quite sensitive to a rare values that happen to fully match between two columns. We don't need this sensitivity. Fortunately, SynDiffix suppresses the rare values, so mutual information is a valid measure when done on the synthetic data.

Note, however, that mutual information can show weak dependence when other measures might show strong dependence, so we don't want to rely on just one measure. The following are additional measures.

• Pearson correlation (only two continuous columns)
• Spearman's rank correlation (only two continuous columns)
• Kendall's tau (redundant with spearman)
• Mutual information (two categorical, or discretize)
• Distance correlation (only continuous)
• Maximal Information Coefficient (MIC) (redundant with mutual information)
• Hoeffding's D Test
• Chi-Square (only categorical)
• Kolmogorov-Smirnov Test (only continuous)
• Cramér's V (redundant with Chi-square)

Another approach is to use ML models, and compare with a baseline. A list of models includes:

Recommended Set of Models
Linear Regression:
Captures linear relationships between continuous variables.
Can be used with categorical variables if they are encoded properly (e.g., one-hot encoding).

Decision Tree Regressor:
Captures non-linear relationships.
Can handle both categorical and continuous variables.

Random Forest Regressor:
An ensemble of decision trees.
Captures non-linear relationships and interactions between variables.
Can handle both categorical and continuous variables.

Gradient Boosting Regressor:
An ensemble method that builds trees sequentially.
Captures complex non-linear relationships.
Can handle both categorical and continuous variables.

Support Vector Regressor (SVR):
Captures linear and non-linear relationships using kernel functions.
Typically used for continuous variables but can handle categorical variables with appropriate encoding.

Logistic Regression (for classification tasks):
Captures linear relationships between categorical variables.
Can be used if the target variable is categorical.

Decision Tree Classifier (for classification tasks):
Captures non-linear relationships.
Can handle both categorical and continuous variables.

Random Forest Classifier (for classification tasks):
An ensemble of decision trees.
Captures non-linear relationships and interactions between variables.
Can handle both categorical and continuous variables.

Gradient Boosting Classifier (for classification tasks):
An ensemble method that builds trees sequentially.
Captures complex non-linear relationships.
Can handle both categorical and continuous variables.

Example Implementation

import numpy as np
import pandas as pd
from sklearn.model_selection import cross_val_score
from sklearn.linear_model import LinearRegression, LogisticRegression
from sklearn.tree import DecisionTreeRegressor, DecisionTreeClassifier
from sklearn.ensemble import RandomForestRegressor, RandomForestClassifier, GradientBoostingRegressor, GradientBoostingClassifier
from sklearn.svm import SVR
from sklearn.dummy import DummyRegressor, DummyClassifier

def check_relationship_ml(df, col1, col2):
    X = df[[col1]].values
    y = df[col2].values
    
    # Determine if the target variable is categorical or continuous
    if pd.api.types.is_numeric_dtype(df[col2]):
        models = {
            'Linear Regression': LinearRegression(),
            'Decision Tree Regressor': DecisionTreeRegressor(),
            'Random Forest Regressor': RandomForestRegressor(),
            'Gradient Boosting Regressor': GradientBoostingRegressor(),
            'Support Vector Regressor': SVR(),
            'Baseline (Mean)': DummyRegressor(strategy='mean')
        }
    else:
        models = {
            'Logistic Regression': LogisticRegression(max_iter=1000),
            'Decision Tree Classifier': DecisionTreeClassifier(),
            'Random Forest Classifier': RandomForestClassifier(),
            'Gradient Boosting Classifier': GradientBoostingClassifier(),
            'Baseline (Most Frequent)': DummyClassifier(strategy='most_frequent')
        }
    
    for name, model in models.items():
        if 'Regressor' in name or 'SVR' in name:
            model_scores = cross_val_score(model, X, y, scoring='r2', cv=5)
        else:
            model_scores = cross_val_score(model, X, y, scoring='accuracy', cv=5)
        
        avg_score = np.mean(model_scores)
        print(f"{name} Average Score: {avg_score}")
        
        if name != 'Baseline (Mean)' and name != 'Baseline (Most Frequent)' and avg_score > 0.5:  # Threshold can be adjusted
            print("Strong relationship detected.")
            return
    
    print("No strong relationship detected.")

# Example usage
# df = pd.DataFrame({'col1': ..., 'col2': ...})
# check_relationship_ml(df, 'col1', 'col2')

And here is some code that combines both statistical and ML approaches (though not sure this is a good idea):

import numpy as np
import pandas as pd
from scipy.stats import pearsonr, spearmanr, chi2_contingency, ks_2samp
from sklearn.metrics import mutual_info_score
from sklearn.model_selection import cross_val_score
from sklearn.linear_model import LinearRegression, LogisticRegression
from sklearn.tree import DecisionTreeRegressor, DecisionTreeClassifier
from sklearn.ensemble import RandomForestRegressor, RandomForestClassifier, GradientBoostingRegressor, GradientBoostingClassifier
from sklearn.svm import SVR
from sklearn.dummy import DummyRegressor, DummyClassifier

def check_relationship(df, col1, col2):
    X = df[[col1]].values
    y = df[col2].values
    
    # Statistical Tests
    print("Statistical Tests:")
    if pd.api.types.is_numeric_dtype(df[col1]) and pd.api.types.is_numeric_dtype(df[col2]):
        # Pearson Correlation
        pearson_corr, _ = pearsonr(df[col1], df[col2])
        print(f"Pearson Correlation: {pearson_corr}")
        if abs(pearson_corr) > 0.5:
            print("Strong relationship detected (Pearson Correlation).")
            return
        
        # Spearman's Rank Correlation
        spearman_corr, _ = spearmanr(df[col1], df[col2])
        print(f"Spearman's Rank Correlation: {spearman_corr}")
        if abs(spearman_corr) > 0.5:
            print("Strong relationship detected (Spearman's Rank Correlation).")
            return
        
        # Kolmogorov-Smirnov Test
        ks_stat, ks_p_value = ks_2samp(df[col1], df[col2])
        print(f"Kolmogorov-Smirnov Test Statistic: {ks_stat}, P-value: {ks_p_value}")
        if ks_stat > 0.5:
            print("Strong relationship detected (Kolmogorov-Smirnov Test).")
            return
    
    # Mutual Information
    mi = mutual_info_score(df[col1], df[col2])
    print(f"Mutual Information: {mi}")
    if mi > 0.5:
        print("Strong relationship detected (Mutual Information).")
        return
    
    # Chi-Square Test of Independence (for categorical variables)
    if not pd.api.types.is_numeric_dtype(df[col1]) or not pd.api.types.is_numeric_dtype(df[col2]):
        contingency_table = pd.crosstab(df[col1], df[col2])
        chi2, chi2_p, _, _ = chi2_contingency(contingency_table)
        print(f"Chi-Square Test Statistic: {chi2}, P-value: {chi2_p}")
        if chi2_p < 0.05:
            print("Strong relationship detected (Chi-Square Test).")
            return
    
    # Machine Learning Models
    print("\nMachine Learning Models:")
    if pd.api.types.is_numeric_dtype(df[col2]):
        models = {
            'Linear Regression': LinearRegression(),
            'Decision Tree Regressor': DecisionTreeRegressor(),
            'Random Forest Regressor': RandomForestRegressor(),
            'Gradient Boosting Regressor': GradientBoostingRegressor(),
            'Support Vector Regressor': SVR(),
            'Baseline (Mean)': DummyRegressor(strategy='mean')
        }
    else:
        models = {
            'Logistic Regression': LogisticRegression(max_iter=1000),
            'Decision Tree Classifier': DecisionTreeClassifier(),
            'Random Forest Classifier': RandomForestClassifier(),
            'Gradient Boosting Classifier': GradientBoostingClassifier(),
            'Baseline (Most Frequent)': DummyClassifier(strategy='most_frequent')
        }
    
    for name, model in models.items():
        if 'Regressor' in name or 'SVR' in name:
            model_scores = cross_val_score(model, X, y, scoring='r2', cv=5)
        else:
            model_scores = cross_val_score(model, X, y, scoring='accuracy', cv=5)
        
        avg_score = np.mean(model_scores)
        print(f"{name} Average Score: {avg_score}")
        
        if name != 'Baseline (Mean)' and name != 'Baseline (Most Frequent)' and avg_score > 0.5:  # Threshold can be adjusted
            print("Strong relationship detected.")
            return
    
    print("No strong relationship detected.")

# Example usage
# df = pd.DataFrame({'col1': ..., 'col2': ...})
# check_relationship(df, 'col1', 'col2')

[yoid2000]

Issues:

• Even on the original data only, sometimes distance_correlation (dc) and adjusted_mutual_information (mi) give very different scores.
• dc can score high in orig and low in syn when rare but strongly correlated values are suppressed in syn. On the other hand, in one particular case, mi was high in both cases. In another case, however, both methods were much too low for syn.
• there is a case where there is strong correlation at extreme values in both columns, but syndiffix flattened the extreme values for both columns. This gave a high original score for mi, but a low score for syndiffix. Note that in this one case, dc gave very similar high scores for orig and syn.
• When a column has only one value, then it scores a 1.0 against other columns. Clearly we want to set these aside, leave them out of clusters, and patch them in at microdata time.