<jupyter_start><jupyter_text>This code computes the correlation between original Shapley-CMI and the approximated Shapley-CMI variants, referring to Sec. 4.3.1<jupyter_code>import numpy as np
import pandas as pd
import sklearn
import itertools

from sklearn.metrics import ndcg_score
from sklearn.model_selection import train_test_split
# load dataset
def load_dataset(name, feature_num, discret_cat=5):
    datafile = './{}/{}.csv'.format(name, name)
    data_pd = pd.read_csv(datafile)
    feature_names = []
    for i in range (1,feature_num+1):
        feature_name = 'f'+str(i)
        if discret_cat > 0: # need discretization
            data_pd[feature_name+'_c'] = pd.cut(data_pd[feature_name], discret_cat, labels = list(range(discret_cat)))
            feature_name += '_c'
        feature_names.append(feature_name)
    data_pd.head()
    y = data_pd['y']
    x = data_pd[feature_names]
    return x, y, feature_names, name
# for calculating mutual information
from collections import Counter
def entropy(labels): # H(A)
    pro_dict = Counter(labels) #计数
    s = sum(pro_dict.values())#总数
    probs = np.array([i/s for i in pro_dict.values()])#概率
    return - probs.dot(np.log(probs))

def MI_(s1,s2):# 互信息
    s_s_1=["%s%s"%(i,j) for i,j in zip(s1,s2)]
    MI_1=entropy(s1)+entropy(s2)-entropy(s_s_1)
    return MI_1


def features_to_keys (features):
    features_to_keys = features.copy()
    features_to_keys.sort()
    return '*'.join(str(i) for i in features_to_keys)
    
cache_approx_MIs = {}
def approx_MI_(y, data_party_features, data_feature_count, task_party_features, X_train):
    data_party_num = len(data_party_features)
    data_party_combinations = itertools.product(range(data_feature_count), repeat=data_party_num)
    mi = 0
    if data_party_num == 0: # no data parties
        for task_party_feature in task_party_features:
            x_new = X_train[[task_party_feature,]]
            mi += MI_(y,list(x_new.itertuples(index=False)))
    else:
        for data_party_feature_indices in data_party_combinations:
            all_features = []
            for i in range(data_party_num):
                all_features.append(data_party_features[i][data_party_feature_indices[i]])
            if len(task_party_features) == 0:
                feature_keys = features_to_keys(all_features)
                if feature_keys not in cache_approx_MIs:
                    x_new = X_train[all_features]
                    cache_approx_MIs[feature_keys] = MI_(y,list(x_new.itertuples(index=False)))
                mi += cache_approx_MIs[feature_keys]
            else:
                for task_party_feature in task_party_features:
                    all_features.append(task_party_feature)
                    feature_keys = features_to_keys(all_features)
                    if feature_keys not in cache_approx_MIs:
                        x_new = X_train[all_features]
                        cache_approx_MIs[feature_keys] = MI_(y,list(x_new.itertuples(index=False)))
                    mi += cache_approx_MIs[feature_keys]
    return mi

#take all the task party's X features as a whole
def approx_MI_2(y, data_party_features, data_feature_count, task_party_features, X_train):
    data_party_num = len(data_party_features)
    data_party_combinations = itertools.product(range(data_feature_count), repeat=data_party_num)
    mi = 0
    if data_party_num == 0: # no data parties
        x_new = X_train[task_party_features]
        mi = MI_(y,list(x_new.itertuples(index=False)))
    else:
        for data_party_feature_indices in data_party_combinations:
            all_features = []
            for i in range(data_party_num):
                all_features.append(data_party_features[i][data_party_feature_indices[i]])
            all_features.extend(task_party_features)
            x_new = X_train[all_features]
            mi += MI_(y,list(x_new.itertuples(index=False)))
    return mi
        
# get all the permutations of the features and then calculate conditional mutual information regarding Y

#x, y, feature_names, dataset_name = load_dataset('winequality-red', 11)
#x, y, feature_names, dataset_name = load_dataset('winequality-white', 11)
#x, y, feature_names, dataset_name = load_dataset('wine', 13) 
x, y, feature_names, dataset_name = load_dataset('parkinsons', 22)
#x, y, feature_names, dataset_name = load_dataset('spect', 22, 0)
#x, y, feature_names, dataset_name = load_dataset('breast', 30)

X_train,X_test,Y_train,Y_test = train_test_split(x, y, test_size=0.2, random_state=0)

Y_value_list = Y_train.values.tolist()

# multiple parties' approximation performance:
data_party_num = 3
random_permutation_times = 20
orignal_cont = []
approx_cont = []
corrs = []
corrs_v2 = []
corrs_v3 = []
aggndcgs = []
aggndcgs_v2 = []
aggndcgs_v3 = []

print("dataset: {}, data party num: {}".format(dataset_name, data_party_num))

for i in range(random_permutation_times): 
    print("====Permutation {}====".format(i))
    data_parties_features = []
    each_feature_permutation = np.random.permutation(feature_names)
    
    # initial each parties' features
    split_num = int(len(feature_names)/(data_party_num+1)) # one task party + multi data parties
    start_i = 0
    for data_i in range(data_party_num):
        data_parties_features.append(list(each_feature_permutation[start_i:start_i+split_num]))
        start_i += split_num
    task_party_feature = list(each_feature_permutation[start_i:]) 
    
    #print(task_party_feature)
    #print(data_parties_features)
    
    # all party permutations
    all_party_permutations = list(itertools.permutations(range(data_party_num)))
    Y_value_list = Y_train.values.tolist()
    
    # original Shapley-CMI calculation
    contribution = [0] * data_party_num
    
    for each_permutation in all_party_permutations:
        current_feature_set = task_party_feature.copy()
        if len(current_feature_set) > 0:
            x_new = X_train[current_feature_set]
            current_MI = MI_(Y_value_list, list(x_new.itertuples(index=False)))
        else:
            current_MI = 0
        for each_party in each_permutation:
            current_feature_set.extend(data_parties_features[each_party])
            x_new = X_train[current_feature_set]
            new_MI = MI_(Y_value_list, list(x_new.itertuples(index=False)))
            contr = new_MI - current_MI # conditional CMI of the current feature in the specific permutation
            contribution[each_party] += contr/len(all_party_permutations) # add the CMI together in all the permutations
            current_MI = new_MI

    print('original', contribution)
    
#     # Shapley-CMI approxmiation
#     contribution_approx = [0] * data_party_num
    
#     for each_permutation in all_party_permutations:
#         current_feature_set = task_party_feature.copy()
#         if len(current_feature_set) > 0:
#             x_new = X_train[current_feature_set]
#             current_MI = MI_(Y_value_list, list(x_new.itertuples(index=False)))
#         else:
#             current_MI = 0
#         for each_party in each_permutation:
#             new_MI = 0
#             for each_feature in data_parties_features[each_party]:
#                 x_new = X_train[current_feature_set + [each_feature,]]
#                 new_MI += MI_(Y_value_list, list(x_new.itertuples(index=False)))
#             contr = new_MI - current_MI # conditional CMI of the current feature in the specific permutation
#             contribution_approx[each_party] += contr/len(all_party_permutations) # add the CMI together in all the permutations
#             current_MI = new_MI
#             current_feature_set.extend(data_parties_features[each_party])
            
#     print('approx', contribution_approx)
#     corr = np.corrcoef(contribution, contribution_approx)[0,1]
#     corrs.append(corr)
#     print('corr', corr)
#     aggndcg = (ndcg_score([contribution], [contribution_approx])+ndcg_score([contribution_approx], [contribution]))/2
#     aggndcgs.append(aggndcg)
#     print('AggNDCG', aggndcg)
    
    # Shapley-CMI approximation v2 (feature independence on task and data parties, denoted as Approx-FI-full in the paper)
    contribution_approx2 = [0] * data_party_num
    for each_permutation in all_party_permutations:
        current_MI = approx_MI_(Y_value_list, [], 0, task_party_feature, X_train)
        new_data_parties_features = []
        for each_party in each_permutation:
            new_data_parties_features.append(data_parties_features[each_party])
            new_MI = approx_MI_(Y_value_list, new_data_parties_features, split_num, task_party_feature, X_train)
            contr = new_MI - current_MI # conditional CMI of the current feature in the specific permutation
            contribution_approx2[each_party] += contr/len(all_party_permutations) # add the CMI together in all the permutations
            current_MI = new_MI
            
    print('approx_v2', contribution_approx2)
    corr = np.corrcoef(contribution, contribution_approx2)[0,1]
    corrs_v2.append(corr)
    print('corr_v2', corr)
    aggndcg = (ndcg_score([contribution], [contribution_approx2])+ndcg_score([contribution_approx2], [contribution]))/2
    aggndcgs_v2.append(aggndcg)
    print('AggNDCG_v2', aggndcg) 
    
    # Shapley-CMI approximation v3 (feature independence only in data parties, denoted as Approx-FI-data)
    contribution_approx3 = [0] * data_party_num
    for each_permutation in all_party_permutations:
        current_MI = approx_MI_2(Y_value_list, [], 0, task_party_feature, X_train)
        new_data_parties_features = []
        for each_party in each_permutation:
            new_data_parties_features.append(data_parties_features[each_party])
            new_MI = approx_MI_2(Y_value_list, new_data_parties_features, split_num, task_party_feature, X_train)
            contr = new_MI - current_MI # conditional CMI of the current feature in the specific permutation
            contribution_approx3[each_party] += contr/len(all_party_permutations) # add the CMI together in all the permutations
            current_MI = new_MI
            
    print('approx_v3', contribution_approx3)
    corr = np.corrcoef(contribution, contribution_approx3)[0,1]
    corrs_v3.append(corr)
    print('corr_v3', corr)
    aggndcg = (ndcg_score([contribution], [contribution_approx3])+ndcg_score([contribution_approx3], [contribution]))/2
    aggndcgs_v3.append(aggndcg)
    print('AggNDCG_v3', aggndcg) 

#print("avg corr", np.nanmean(corrs))
#print("avg aggndcg", np.nanmean(aggndcgs))
print("avg corr_v2 (Approx-FI-full)", np.nanmean(corrs_v2))
#print("avg aggndcg_v2 (Approx-FI-full)", np.nanmean(aggndcgs_v2))
print("avg corr_v3 (Approx-FI-data)", np.nanmean(corrs_v3))
#print("avg aggndcg_v3 (Approx-FI-data)", np.nanmean(aggndcgs_v3))<jupyter_output>dataset: parkinsons, data party num: 3
====Permutation 0====
original [0.02425636530094266, 0.02257928791708208, 0.03314286761581409]
approx [0.7754263734917725, 0.7524550982452597, 0.7728272381833872]
corr 0.5382467154083174
AggNDCG 0.9722556869100367
approx_v2 [114.82099921430768, 113.76239984009392, 115.66941912941839]
corr_v2 0.9052217257752514
AggNDCG_v2 1.0
approx_v3 [21.505274866511435, 21.408024456443414, 21.49915453797015]
corr_v3 0.5774770431346553
AggNDCG_v3 0.9725236045837357
====Permutation 1====
original [0.12402956822131134, 0.0659585738932432, 0.035996204153192345]
approx [0.9092302006507975, 0.7777326326395176, 0.7356623752282581]
corr 0.9942986962397108
AggNDCG 1.0
approx_v2 [107.5530049782664, 103.52229935841484, 102.41969568022813]
corr_v2 0.9907875762270224
AggNDCG_v2 1.0
approx_v3 [18.503422913041152, 17.997609256183612, 17.771715635884597]
corr_v3 0.9993847201410228
AggNDCG_v3 1.0
====Permutation 2====
original [0.022923190703682504, 0.027366441861117988, 0.04572[...]
{'fraction_non_alphanumeric': 0.09743936448914053, 'fraction_numerical': 0.06067776557086115, 'mean_word_length': 3.7373899119295437, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '307046', 'license': 'Apache-2.0', 'n_tokens_mistral': 4525, 'n_tokens_neox': 4033, 'n_words': 762, 'path': '.ipynb_checkpoints/Shapley-CMI valuation approx-checkpoint.ipynb', 'repo_name': 'wangleye/FedValue', 'size': '11833'}