<jupyter_start><jupyter_text>How to Find Your Neighbor?In neighborhood based collaborative filtering, it is incredibly important to be able to identify an individual's neighbors.  Let's look at a small dataset in order to understand, how we can use different metrics to identify close neighbors.<jupyter_code>%load_ext lab_black
from itertools import product

import numpy as np
import pandas as pd
from scipy.stats import spearmanr, kendalltau
import matplotlib.pyplot as plt
import tests as t
import helper as h

%matplotlib inline

play_data = pd.DataFrame(
    {
        "x1": [-3, -2, -1, 0, 1, 2, 3],
        "x2": [9, 4, 1, 0, 1, 4, 9],
        "x3": [1, 2, 3, 4, 5, 6, 7],
        "x4": [2, 5, 15, 27, 28, 30, 31],
    }
)

# create play data dataframe
play_data = play_data[["x1", "x2", "x3", "x4"]]<jupyter_output><empty_output><jupyter_text>Measures of SimilarityThe first metrics we will look at have similar characteristics:1. Pearson's Correlation Coefficient2. Spearman's Correlation Coefficient3. Kendall's TauLet's take a look at each of these individually. Pearson's CorrelationFirst, **Pearson's correlation coefficient** is a measure related to the strength and direction of a **linear** relationship.  If we have two vectors **x** and **y**, we can compare their individual elements in the following way to calculate Pearson's correlation coefficient:$$CORR(\textbf{x}, \textbf{y}) = \frac{\sum\limits_{i=1}^{n}(x_i - \bar{x})(y_i - \bar{y})}{\sqrt{\sum\limits_{i=1}^{n}(x_i-\bar{x})^2}\sqrt{\sum\limits_{i=1}^{n}(y_i-\bar{y})^2}} $$where $$\bar{x} = \frac{1}{n}\sum\limits_{i=1}^{n}x_i$$1. Write a function that takes in two vectors and returns the Pearson correlation coefficient.  You can then compare your answer to the built in function in numpy by using the assert statements in the following cell.<jupyter_code>def pearson_corr(x, y):
    """
    INPUT
    x - an array of matching length to array y
    y - an array of matching length to array x
    OUTPUT
    corr - the pearson correlation coefficient for comparing x and y
    """
    numerator = (x - np.mean(x)) @ (y - np.mean(y))
    denominator = np.sqrt(np.sum((x - np.mean(x)) ** 2)) * np.sqrt(
        np.sum((y - np.mean(y)) ** 2)
    )
    corr = numerator / denominator

    return corr
# This cell will test your function against the built in numpy function
assert (
    pearson_corr(play_data["x1"], play_data["x2"])
    == np.corrcoef(play_data["x1"], play_data["x2"])[0][1]
), "Oops!  The correlation between the first two columns should be 0, but your function returned {}.".format(
    pearson_corr(play_data["x1"], play_data["x2"])
)
assert (
    round(pearson_corr(play_data["x1"], play_data["x3"]), 2)
    == np.corrcoef(play_data["x1"], play_data["x3"])[0][1]
), "Oops!  The correlation between the first and third columns should be {}, but your function returned {}.".format(
    np.corrcoef(play_data["x1"], play_data["x3"])[0][1],
    pearson_corr(play_data["x1"], play_data["x3"]),
)
assert round(pearson_corr(play_data["x3"], play_data["x4"]), 2) == round(
    np.corrcoef(play_data["x3"], play_data["x4"])[0][1], 2
), "Oops!  The correlation between the first and third columns should be {}, but your function returned {}.".format(
    np.corrcoef(play_data["x3"], play_data["x4"])[0][1],
    pearson_corr(play_data["x3"], play_data["x4"]),
)
print(
    "If this is all you see, it looks like you are all set!  Nice job coding up Pearson's correlation coefficient!"
)<jupyter_output>If this is all you see, it looks like you are all set!  Nice job coding up Pearson's correlation coefficient!<jupyter_text>`2.` Now that you have computed **Pearson's correlation coefficient**, use the below dictionary to identify statements that are true about **this** measure.<jupyter_code>a = True
b = False
c = "We can't be sure."


pearson_dct = {
    "If when x increases, y always increases, Pearson's correlation will be always be 1.": False,  # Letter here,
    "If when x increases by 1, y always increases by 3, Pearson's correlation will always be 1.": True,  # Letter here,
    "If when x increases by 1, y always decreases by 5, Pearson's correlation will always be -1.": True,  # Letter here,
    "If when x increases by 1, y increases by 3 times x, Pearson's correlation will always be 1.": False,  # Letter here
}

t.sim_2_sol(pearson_dct)<jupyter_output>That's right!  Pearson's correlation relates to a linear relationship.  The second and third cases are examples of perfect linear relationships, where we would receive values of 1 and -1.  Only having an increase or decrease that are directly related will not lead to a Pearson's correlation coefficient of 1 or -1.  You can see this by testing out your function using the examples above without using assert statements.<jupyter_text>Spearman's CorrelationNow, let's look at **Spearman's correlation coefficient**.  Spearman's correlation is what is known as a [non-parametric](https://en.wikipedia.org/wiki/Nonparametric_statistics) statistic, which is a statistic who's distribution doesn't depend parameters (statistics that follow normal distributions or binomial distributions are examples of parametric statistics).  Frequently non-parametric statistics are based on the ranks of data rather than the original values collected.  This happens to be the case with Spearman's correlation coefficient, which is calculated similarly to Pearson's correlation.  However, instead of using the raw data, we use the rank of each value.You can quickly change from the raw data to the ranks using the **.rank()** method as shown here:<jupyter_code>print(
    "The ranked values for the variable x1 are: {}".format(
        np.array(play_data["x1"].rank())
    )
)
print(
    "The raw data values for the variable x1 are: {}".format(np.array(play_data["x1"]))
)<jupyter_output>The ranked values for the variable x1 are: [1. 2. 3. 4. 5. 6. 7.]
The raw data values for the variable x1 are: [-3 -2 -1  0  1  2  3]<jupyter_text>If we map each of our data to ranked data values as shown above:$$\textbf{x} \rightarrow \textbf{x}^{r}$$$$\textbf{y} \rightarrow \textbf{y}^{r}$$Here, we let the **r** indicate these are ranked values (this is not raising any value to the power of r).  Then we compute Spearman's correlation coefficient as:$$SCORR(\textbf{x}, \textbf{y}) = \frac{\sum\limits_{i=1}^{n}(x^{r}_i - \bar{x}^{r})(y^{r}_i - \bar{y}^{r})}{\sqrt{\sum\limits_{i=1}^{n}(x^{r}_i-\bar{x}^{r})^2}\sqrt{\sum\limits_{i=1}^{n}(y^{r}_i-\bar{y}^{r})^2}} $$where $$\bar{x}^r = \frac{1}{n}\sum\limits_{i=1}^{n}x^r_i$$`3.` Write a function that takes in two vectors and returns the Spearman correlation coefficient.  You can then compare your answer to the built in function in scipy stats by using the assert statements in the following cell.<jupyter_code>def corr_spearman(x, y):
    """
    INPUT
    x - an array of matching length to array y
    y - an array of matching length to array x
    OUTPUT
    corr - the spearman correlation coefficient for comparing x and y
    """
    x = x.rank()
    y = y.rank()
    numerator = (x - np.mean(x)) @ (y - np.mean(y))
    denominator = np.sqrt(np.sum((x - np.mean(x)) ** 2)) * np.sqrt(
        np.sum((y - np.mean(y)) ** 2)
    )
    corr = numerator / denominator
    return corr
# This cell will test your function against the built in scipy function
assert (
    corr_spearman(play_data["x1"], play_data["x2"])
    == spearmanr(play_data["x1"], play_data["x2"])[0]
), "Oops!  The correlation between the first two columns should be 0, but your function returned {}.".format(
    compute_corr(play_data["x1"], play_data["x2"])
)
assert (
    round(corr_spearman(play_data["x1"], play_data["x3"]), 2)
    == spearmanr(play_data["x1"], play_data["x3"])[0]
), "Oops!  The correlation between the first and third columns should be {}, but your function returned {}.".format(
    np.corrcoef(play_data["x1"], play_data["x3"])[0][1],
    compute_corr(play_data["x1"], play_data["x3"]),
)
assert round(corr_spearman(play_data["x3"], play_data["x4"]), 2) == round(
    spearmanr(play_data["x3"], play_data["x4"])[0], 2
), "Oops!  The correlation between the first and third columns should be {}, but your function returned {}.".format(
    np.corrcoef(play_data["x3"], play_data["x4"])[0][1],
    compute_corr(play_data["x3"], play_data["x4"]),
)
print(
    "If this is all you see, it looks like you are all set!  Nice job coding up Spearman's correlation coefficient!"
)
a = True
b = False
c = "We can't be sure."


spearman_dct = {
    "If when x increases, y always increases, Spearman's correlation will be always be 1.": a,  # Letter here,
    "If when x increases by 1, y always increases by 3, Pearson's correlation will always be 1.": a,  # Letter here,
    "If when x increases by 1, y always decreases by 5, Pearson's correlation will always be -1.": a,  # Letter here,
    "If when x increases by 1, y increases by 3 times x, Pearson's correlation will always be 1.": a,  # Letter here
}

t.sim_4_sol(spearman_dct)<jupyter_output>That's right!  Unlike Pearson's correlation, Spearman's correlation can have perfect relationships (1 or -1 values) that aren't linear relationships.  You will notice that neither Spearman or Pearson correlation values suggest a relation when there are quadratic relationships.<jupyter_text>Kendall's TauKendall's tau is quite similar to Spearman's correlation coefficient.  Both of these measures are nonparametric measures of a relationship.  Specifically both Spearman and Kendall's coefficients are calculated based on ranking data and not the raw data.  Similar to both of the previous measures, Kendall's Tau is always between -1 and 1, where -1 suggests a strong, negative relationship between two variables and 1 suggests a strong, positive relationship between two variables.Though Spearman's and Kendall's measures are very similar, there are statistical advantages to choosing Kendall's measure in that Kendall's Tau has smaller variability when using larger sample sizes.  However Spearman's measure is more computationally efficient, as Kendall's Tau is O(n^2) and Spearman's correlation is O(nLog(n)). You can find more on this topic in [this thread](https://www.researchgate.net/post/Does_Spearmans_rho_have_any_advantage_over_Kendalls_tau).Let's take a closer look at exactly how this measure is calculated.  Again, we want to map our data to ranks:$$\textbf{x} \rightarrow \textbf{x}^{r}$$$$\textbf{y} \rightarrow \textbf{y}^{r}$$Then we calculate Kendall's Tau as:$$TAU(\textbf{x}, \textbf{y}) = \frac{2}{n(n -1)}\sum_{i < j}sgn(x^r_i - x^r_j)sgn(y^r_i - y^r_j)$$Where $sgn$ takes the the sign associated with the difference in the ranked values.  An alternative way to write $$sgn(x^r_i - x^r_j)$$ is in the following way:$$ \begin{cases}       -1  & x^r_i < x^r_j \\      0 & x^r_i = x^r_j \\      1 & x^r_i > x^r_j    \end{cases}$$Therefore the possible results of $$sgn(x^r_i - x^r_j)sgn(y^r_i - y^r_j)$$are only 1, -1, or 0, which are summed to give an idea of the propotion of times the ranks of **x** and **y** are pointed in the right direction.`5.` Write a function that takes in two vectors and returns Kendall's Tau.  You can then compare your answer to the built in function in scipy stats by using the assert statements in the following cell.<jupyter_code>def kendalls_tau(x, y):
    """
    INPUT
    x - an array of matching length to array y
    y - an array of matching length to array x
    OUTPUT
    tau - the kendall's tau for comparing x and y
    """
    x = x.rank()
    y = y.rank()

    normalization = 2 / (len(x) * (len(x) - 1))
    indeces = filter(lambda x: x[0] < x[1], product(range(len(x)), range(len(y))))
    indeces = list(map(list, zip(*indeces)))
    indeces_i = indeces[0]
    indeces_j = indeces[1]

    tau = np.sum(
        np.sign(x.iloc[indeces_i].values - x.iloc[indeces_j].values)
        * np.sign(y.iloc[indeces_i].values - y.iloc[indeces_j].values)
    )

    return tau * normalization
%%timeit
kendalls_tau(play_data["x1"], play_data["x2"])
# This cell will test your function against the built in scipy function
assert (
    kendalls_tau(play_data["x1"], play_data["x2"])
    == kendalltau(play_data["x1"], play_data["x2"])[0]
), "Oops!  The correlation between the first two columns should be 0, but your function returned {}.".format(
    kendalls_tau(play_data["x1"], play_data["x2"])
)
assert (
    round(kendalls_tau(play_data["x1"], play_data["x3"]), 2)
    == kendalltau(play_data["x1"], play_data["x3"])[0]
), "Oops!  The correlation between the first and third columns should be {}, but your function returned {}.".format(
    kendalltau(play_data["x1"], play_data["x3"])[0][1],
    kendalls_tau(play_data["x1"], play_data["x3"]),
)
assert round(kendalls_tau(play_data["x3"], play_data["x4"]), 2) == round(
    kendalltau(play_data["x3"], play_data["x4"])[0], 2
), "Oops!  The correlation between the first and third columns should be {}, but your function returned {}.".format(
    kendalltau(play_data["x3"], play_data["x4"])[0][1],
    kendalls_tau(play_data["x3"], play_data["x4"]),
)
print(
    "If this is all you see, it looks like you are all set!  Nice job coding up Kendall's Tau!"
)<jupyter_output>If this is all you see, it looks like you are all set!  Nice job coding up Kendall's Tau!<jupyter_text>`6.` Use your functions (and/or your knowledge of each of the above coefficients) to accurately identify each of the below statements as True or False.  **Note:** There may be some rounding differences due to the way numbers are stored, so it is recommended that you consider comparisons to 4 or fewer decimal places.<jupyter_code>a = True
b = False
c = "We can't be sure."


corr_comp_dct = {
    "For all columns of play_data, Spearman and Kendall's measures match.": a,  # Letter here,
    "For all columns of play_data, Spearman and Pearson's measures match.": b,  # Letter here,
    "For all columns of play_data, Pearson and Kendall's measures match.": b,  # Letter here
}

t.sim_6_sol(corr_comp_dct)<jupyter_output>That's right!  Pearson does not match the other two measures, as it looks specifically for linear relationships.  However, Spearman and Kenall's measures are exactly the same to one another in the cases related to play_data.<jupyter_text>Distance MeasuresEach of the above measures are considered measures of correlation.  Similarly, there are distance measures (of which there are many).  [This is a great article](http://dataaspirant.com/2015/04/11/five-most-popular-similarity-measures-implementation-in-python/) on some popular distance metrics.  In this notebook, we will be looking specifically at two of these measures.  1. Euclidean Distance2. Manhattan DistanceDifferent than the three measures you built functions for, these two measures take on values between 0 and potentially infinity.  Measures that are closer to 0 imply that two vectors are more similar to one another.  The larger these values become, the more dissimilar two vectors are to one another.Choosing one of these two `distance` metrics vs. one of the three `similarity` above is often a matter of personal preference, audience, and data specificities.  You will see in a bit a case where one of these measures (euclidean or manhattan distance) is optimal to using Pearson's correlation coefficient. Euclidean DistanceEuclidean distance can also just be considered as straight-line distance between two vectors.For two vectors **x** and **y**, we can compute this as:$$ EUC(\textbf{x}, \textbf{y}) = \sqrt{\sum\limits_{i=1}^{n}(x_i - y_i)^2}$$ Manhattan DistanceDifferent from euclidean distance, Manhattan distance is a 'manhattan block' distance from one vector to another.  Therefore, you can imagine this distance as a way to compute the distance between two points when you are not able to go through buildings.Specifically, this distance is computed as:$$ MANHATTAN(\textbf{x}, \textbf{y}) = \sqrt{\sum\limits_{i=1}^{n}|x_i - y_i|}$$Using each of the above, write a function for each to take two vectors and compute the euclidean and manhattan distances.You can see in the above image, the **blue** line gives the **Manhattan** distance, while the **green** line gives the **Euclidean** distance between two points.`7.` Use the below cell to complete a function for each distance metric.  Then test your functions against the built in values using the below.<jupyter_code>def eucl_dist(x, y):
    """
    INPUT
    x - an array of matching length to array y
    y - an array of matching length to array x
    OUTPUT
    euc - the euclidean distance between x and y
    """
    return np.sqrt(np.sum((x - y) ** 2))


def manhat_dist(x, y):
    """
    INPUT
    x - an array of matching length to array y
    y - an array of matching length to array x
    OUTPUT
    manhat - the manhattan distance between x and y
    """
    return np.sum(np.abs(x - y))
# Test your functions
assert h.test_eucl(play_data["x1"], play_data["x2"]) == eucl_dist(
    play_data["x1"], play_data["x2"]
)
assert h.test_eucl(play_data["x2"], play_data["x3"]) == eucl_dist(
    play_data["x2"], play_data["x3"]
)
assert h.test_manhat(play_data["x1"], play_data["x2"]) == manhat_dist(
    play_data["x1"], play_data["x2"]
)
assert h.test_manhat(play_data["x2"], play_data["x3"]) == manhat_dist(
    play_data["x2"], play_data["x3"]
)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12045834053089192, 'fraction_numerical': 0.015719467956469165, 'mean_word_length': 4.370439084724799, 'pattern_counts': {'":': 15, '<': 30, '<?xml version=': 0, '>': 28, 'https://': 2, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '11534', 'license': 'MIT', 'n_tokens_mistral': 5669, 'n_tokens_neox': 5286, 'n_words': 2099, 'path': 'lessons/Recommendations/1_Intro_to_Recommendations/3_Measuring Similarity.ipynb', 'repo_name': 'aauss/DSND_Term2', 'size': '17367'}