<jupyter_start><jupyter_text>Load and preprocess data<jupyter_code>path_dataset = "../data/data_train.csv"
ratings = load_data(path_dataset)
nF, nU = ratings.shape
print(nF, nU)
viewings = np.zeros((nF, nU))
nnz_rows, nnz_cols = ratings.nonzero()
for f, u in list(zip(nnz_rows, nnz_cols)):
    viewings[f, u] = 1
ratings = np.asarray(ratings.toarray())
user_means = np.sum(ratings, axis=0) / np.sum(viewings, axis=0)
user_stdDevs = (np.sum(ratings * ratings, axis=0) / np.sum(viewings, axis=0)) - user_means * user_means
normalized_ratings = viewings * (ratings - user_means) / user_stdDevs<jupyter_output><empty_output><jupyter_text>Build graph<jupyter_code>similarities = np.zeros((nU, nU))
user_commonViewings = np.zeros((nU, nU))
for f in range(nF):
    if(f % 100 == 0):
        print(f)
    users = np.where(viewings[f,:] == 1)[0]
    nRatings = len(users)
    for i in range(nRatings):
        for j in range(i + 1, nRatings):
            similarities[users[i], users[j]] += normalized_ratings[f, users[i]] * normalized_ratings[f, users[j]]
            similarities[users[j], users[i]] = similarities[users[i], users[j]]
            user_commonViewings[users[i], users[j]] += 1
            user_commonViewings[users[j], users[i]] += 1
def sim_to_dist(x):
    if(x <= 709):
        return 1./(1. + np.exp(x))
    return np.exp(-x)/(1. + np.exp(-x))
distances = np.zeros((nU, nU))
nnz_rows, nnz_cols = user_commonViewings.nonzero()
for ui, uj in list(zip(nnz_rows, nnz_cols)):
    distances[ui, uj] = sim_to_dist(similarities[ui, uj])
neighbors = []
for ui in range(nU):
    n = []
    for uj in range(nU):
        if user_commonViewings[ui, uj] > 0:
            n.append(uj)
    neighbors.append(n)<jupyter_output><empty_output><jupyter_text>Shortest paths from one user vertex<jupyter_code>def get_shortest_paths(user):
    dist_users = -1 * np.ones(nU)
    dist_users[user] = 0
    Q = {user}
    P = {1}
    P.remove(1)
    while len(Q) > 0:
        minDist = 1000000000000
        for u in Q:
            if dist_users[u] < minDist:
                uMin = u
        Q.remove(uMin)
        P.add(uMin)
        for u in neighbors[uMin]:
            if not u in P:
                if dist_users[u] == -1:
                    dist_users[u] = dist_users[uMin] + distances[uMin, u]
                else:
                    dist_users[u] = min(dist_users[u], dist_users[uMin] + distances[uMin, u])
                Q.add(u)
    print(len(P))
    return dist_users
#Problem : the graph is almost complete, and the distance does not satisfy triangular inequality 
# -> length of shortest path is always almost 0
# Fix : assume that in most of the cases the one-ring neighbors are enough, and use k-nn
# Or : be more restrictive on links (enough films in common)<jupyter_output><empty_output><jupyter_text>k nearest neighbors<jupyter_code>sorted_neighbors = []
for ui in range(nU):
    n = [(uj, similarities[ui, uj]) for uj in neighbors[ui]]
    n = sorted(n, key=lambda x : x[1], reverse=1)
    sorted_neighbors.append(n)
def prediction(f, u, k):
    count = 0
    ref_neighbors = []
    n_neighbors = len(sorted_neighbors[u])
    while len(ref_neighbors) < k and count < n_neighbors:
        n = sorted_neighbors[u][count][0]
        if viewings[f, n] == 1 and similarities[u, n] > 0:
            ref_neighbors.append(n)
        count += 1
    if len(ref_neighbors) == 0:
        print("No (correlated) neighbors have seen the film")
        return user_means[u]
    meanGrade = 0
    totWeights = 0
    for n in ref_neighbors:
        meanGrade += (user_means[u] + user_stdDevs[u]*normalized_ratings[f, n]) * similarities[u,n]
        totWeights += similarities[u,n]
    meanGrade /= totWeights
    meanGrade = round(meanGrade)
    meanGrade = min(meanGrade, 5)
    meanGrade = max(meanGrade, 1)
    return meanGrade
kMax = 10
for k in range(1, kMax + 1):
    print('k={}:'.format(k))
    count = 0
    mse = 0
    for u in range(nU):
        if(u % 100 == 0):
            print('User #{}'.format(u + 1))
        for f in range(nF):
            if viewings[f, u] == 1:
                mse += (ratings[f, u] - prediction(f, u, k))**2
                count += 1
    print("RMSE : ")
    print(np.sqrt(mse / count))
            
for k in range(11, 21):
    print('k={}:'.format(k))
    count = 0
    mse = 0
    for u in range(nU):
        if(u % 100 == 0):
            print('User #{}'.format(u + 1))
        for f in range(nF):
            if viewings[f, u] == 1:
                mse += (ratings[f, u] - prediction(f, u, k))**2
                count += 1
    print("RMSE : ")
    print(np.sqrt(mse / count))
ks = [10, 11, nU]
for k in ks:
    print('k={}:'.format(k))
    count = 0
    mse = 0
    for u in range(nU):
        if(u % 100 == 0):
            print('User #{}'.format(u + 1))
        for f in range(nF):
            if viewings[f, u] == 1:
                mse += (ratings[f, u] - prediction(f, u, k))**2
                count += 1
    print("RMSE : ")
    print(np.sqrt(mse / count))<jupyter_output>k=10:
User #1
User #101
User #201
User #301
User #401
User #501
User #601
User #701
User #801
No (correlated) neighbors have seen the film
User #901
RMSE : 
1.0301879223
k=11:
User #1
User #101
User #201
User #301
User #401
User #501
User #601
User #701
User #801
No (correlated) neighbors have seen the film
User #901
RMSE : 
1.02501195514
k=1000:
User #1
User #101
User #201
User #301
User #401
User #501
User #601
User #701
User #801
No (correlated) neighbors have seen the film
User #901
RMSE : 
1.00205237017
{'fraction_non_alphanumeric': 0.14166817441650081, 'fraction_numerical': 0.04016645558168989, 'mean_word_length': 2.658504301786896, 'pattern_counts': {'":': 0, '<': 20, '<?xml version=': 0, '>': 20, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '168285', 'license': 'MIT', 'n_tokens_mistral': 2253, 'n_tokens_neox': 2042, 'n_words': 540, 'path': 'src/notebooks/shortestPath.ipynb', 'repo_name': 'armand33/recommender_system', 'size': '5527'}