<jupyter_start><jupyter_text>KDE-SORTJupyter Notebook explaining how to use Kernel Density Estimation to infer the true position of an item from a list of positions by other users.<jupyter_code>import numpy as np
import matplotlib.pyplot as plt
from scipy.special import gamma # Generalized factorial to real numbers
from scipy.special import factorial
from ipywidgets import interact<jupyter_output><empty_output><jupyter_text>First let's define the categories we are going to use. There are 5 tiers in our example: S,A,B,C and D, in decreasig order of relevance. We want to know how relevant a given item is, based on individual rankings of other users.<jupyter_code>tiers = {"S":0.5,"A":1.5,"B":2.5,"C":3.5,"D":4.5}<jupyter_output><empty_output><jupyter_text>Let's say 3 people have already categorized the item:<jupyter_code>item_rankings = ["S","A","C"]<jupyter_output><empty_output><jupyter_text>Let's plot this ranks:<jupyter_code>for ranking in item_rankings:
    plt.bar(tiers[ranking],1)

plt.title("Rankings")
plt.xlabel("Tiers")
plt.ylabel("Count")

x_ticks = []
x_ticks_labels = []
for tier in tiers:
    x_ticks.append(tiers[tier])
    x_ticks_labels.append(tier)
    
plt.xticks(x_ticks,x_ticks_labels)

plt.show()<jupyter_output><empty_output><jupyter_text>Now, to do the Kernel Density Estimation, we need to generate a distribution of probability for each individual position. Let's do it using a Gaussian probability distribution (normalized for the interval).<jupyter_code>def gaussian(x, mu, sig):
    return np.exp(-np.power(x - mu, 2.) / (2 * np.power(sig, 2.)))

xrange = np.linspace(0,5,1000)
for i,item in enumerate(item_rankings):
    distribution = gaussian(xrange, mu = tiers[item], sig = 1.0)
    distribution /= np.sum(distribution)
    plt.plot(xrange,distribution, label = "Ranking " + str(i))


plt.title("Rankings")
plt.xlabel("Tiers")
plt.ylabel("Probability")
plt.xticks(x_ticks,x_ticks_labels)

plt.legend()    
plt.show()<jupyter_output><empty_output><jupyter_text>Let's compute the sum of all this individual probability distributions<jupyter_code>sum_distribution = np.zeros(1000)

xrange = np.linspace(0,5,1000)
for i,item in enumerate(item_rankings):
    distribution = gaussian(xrange, mu = tiers[item], sig = 1.0)
    distribution /= np.sum(distribution)
    sum_distribution += distribution

sum_distribution /= np.sum(sum_distribution)

plt.title("Rankings")
plt.xlabel("Tiers")
plt.ylabel("Probability")
plt.xticks(x_ticks,x_ticks_labels)
    
plt.plot(xrange,sum_distribution, color = "red", linewidth = 2)
plt.fill_between(xrange,np.zeros(1000),sum_distribution, color = "red", alpha = 0.1)
plt.show()<jupyter_output><empty_output><jupyter_text>Now, we want to know the median value of the distribution.<jupyter_code>percentile = 0

for i,bin in enumerate(sum_distribution):
    percentile += bin
    if percentile >= 0.5:
        plt.axvline(xrange[i], linewidth = 1, linestyle = "--", color = "red", label = "50% percentile")
        break;

plt.title("Rankings")
plt.xlabel("Tiers")
plt.ylabel("Probability")
plt.xticks(x_ticks,x_ticks_labels)
    
plt.plot(xrange,sum_distribution, color = "red", linewidth = 2)
plt.fill_between(xrange,np.zeros(1000),sum_distribution, color = "red", alpha = 0.1)
plt.legend()
plt.show()<jupyter_output><empty_output><jupyter_text>Let's combine all of this into a single interactive algorithm.<jupyter_code>@interact(ranking_0 = ["S","A","B","C","D"], ranking_1 = ["S","A","B","C","D"],
            ranking_2 = ["S","A","B","C","D"], error = (0.5,2.5,0.1))

def KDESort(ranking_0 = "S", ranking_1 = "A",ranking_2 = "C", error = 1.0):
    
    xrange = np.linspace(-5,10,1000)
    sum_distribution = np.zeros(1000)
    for i,item in enumerate([ranking_0,ranking_1,ranking_2]):
        distribution = gaussian(xrange, mu = tiers[item], sig = error)
        distribution /= np.sum(distribution)
        sum_distribution += distribution
        plt.plot(xrange,distribution)
    
    plt.plot(xrange,sum_distribution, color = "red", linewidth = 2)
    plt.fill_between(xrange,np.zeros(1000),sum_distribution, color = "red", alpha = 0.1)
    
    percentile = 0

    for i,bin in enumerate(sum_distribution/np.sum(sum_distribution)):
        percentile += bin
        if percentile >= 0.5:
            plt.axvline(xrange[i], linewidth = 1, linestyle = "--", color = "red", label = "50% percentile")
            break;
    
    plt.xlim(-1,6)
    
    plt.title("Rankings")
    plt.xlabel("Tiers")
    plt.ylabel("Probability")
    plt.xticks(x_ticks,x_ticks_labels)
    
    plt.legend()    
    plt.show()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.13988739714161974, 'fraction_numerical': 0.02143785188393244, 'mean_word_length': 4.802763819095477, 'pattern_counts': {'":': 5, '<': 33, '<?xml version=': 0, '>': 35, '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': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '621016', 'license': 'MIT', 'n_tokens_mistral': 1746, 'n_tokens_neox': 1618, 'n_words': 354, 'path': 'main.ipynb', 'repo_name': 'Androp0v/KDE-Sort', 'size': '4618'}