<jupyter_start><jupyter_text>Graph creation<jupyter_code>G=nx.Graph()

for y in range(np_map.shape[0]):
    for x in range(np_map.shape[1]):
        if np_map[y,x]:
            continue
        
        if y+1 < np_map.shape[0] and np_map[y+1,x] == 0:
            G.add_edge((y,x),(y+1,x))
        
        if y-1 >= 0 and  np_map[y-1,x] == 0:
            G.add_edge((y,x),(y-1,x))
        
        if x+1 < np_map.shape[1] and  np_map[y,x+1] == 0:
            G.add_edge((y,x),(y,x+1))
        
        if x-1 >= 0 and  np_map[y,x-1] == 0:
            G.add_edge((y,x),(y,x-1))
        
paths = nx.shortest_path(G)<jupyter_output><empty_output><jupyter_text>10.2 - K-medoids clustering<jupyter_code>import random

klusters_n = 4
centroids = []

def get_dist_graph(G, v1, v2):
    return len(paths[v1][v2])

for i in range(klusters_n):
    centroids.append(random.choice(list(G.nodes())))

print(centroids)
    
for epoch in range(50):
    clusters = [set() for _ in range(len(centroids))]
    # Loop over the nodes
    for node in G.nodes():
        # Get closest distance to centroid i
        
        min_dist = np.inf
        min_centr = ()
        
        for centr in centroids:
            dist = get_dist_graph(G, node, centr)
            # Save min centroid
            if dist < min_dist:
                min_dist = dist
                min_centr = centr
        
        # Add node to correct cluster
        idx = centroids.index(min_centr)
        clusters[idx].add(node)

    for idx, clust_set in enumerate(clusters):
        min_dist = np.inf
        min_centr = ()
        for node in clust_set:
            sum_dist = sum(get_dist_graph(G, node, node2) for node2 in clust_set)
            if sum_dist < min_dist:
                min_dist = sum_dist
                min_centr = node

        centroids[idx] = min_centr    
print(centroids)        
map_clustered = np_map.copy()
for y in range(np_map.shape[0]):
    for x in range(np_map.shape[1]):
        node = np_map[y,x]
        if node == 0:
            for idx, clust_set in enumerate(clusters):
                if (y,x) in clust_set:
                    map_clustered[y, x] = idx + 1
        else:
            map_clustered[y, x] = 0
plt.matshow(map_clustered, cmap='viridis', interpolation='nearest')
plt.show()<jupyter_output><empty_output><jupyter_text>10.3 - Spectral clustering<jupyter_code>klusters_n = 4

# Adiacent matrix
A = nx.convert_matrix.to_numpy_matrix(G)

# Degree matrix
D = np.zeros_like(A)
# Asssignment of the degrees
for i in range(A.shape[0]):
    D[i,i] = A[i].sum()

# Laplacian matrix
L = D - A

# Eigenvalue decomposition  
e_values, e_vectors = np.linalg.eigh(L)

idx = e_values.argsort()
e_vectors = e_vectors[idx]

W = e_vectors[:,1:klusters_n+1]<jupyter_output><empty_output><jupyter_text>K-means clustering over eigenvectors<jupyter_code>import random

centroids = []

def get_dist(x1, x2):
    return (np.sum((x1 - x2)**2))**(1/2)

for i in range(klusters_n):
    idx = np.random.randint(W.shape[0])
    centr = np.squeeze(np.asarray(W[idx]))
    centroids.append(centr)

print(centroids)
    
for epoch in range(10):
    clusters = [list() for _ in range(len(centroids))]
    # Loop over the nodes
    for i in range(W.shape[0]):
        # Get closest distance to centroid i
        
        min_dist = np.inf
        min_centr = ()
        node = np.squeeze(np.asarray(W[i]))

        for centr in centroids:
            dist = get_dist(node, centr)
            # Save min centroid
            if dist < min_dist:
                min_dist = dist
                min_centr = centr

        # Add node to correct cluster
        idx = [idx for idx, centr in enumerate(centroids) if np.allclose(centr,min_centr)][0]
        clusters[idx].append(node)

    for idx, clust_set in enumerate(clusters):
        sum_nodes = 0
        for node in clust_set:
            sum_nodes += node
        mean = sum_nodes / len(clust_set)
        centroids[idx] = mean  
list_nodes = list(G.nodes())
map_clustered = np.zeros_like(np_map)

for idx, cluster_nodes in enumerate(clusters):
    for node in cluster_nodes:
        i, _ = np.where(np.isclose(W, node).all(axis=1))
        (y,x) = list_nodes[i[0]]
        map_clustered[y,x] = idx + 1

plt.matshow(map_clustered, cmap='viridis', interpolation='nearest')
plt.show()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1240506329113924, 'fraction_numerical': 0.014269275028768699, 'mean_word_length': 2.353395061728395, 'pattern_counts': {'":': 0, '<': 22, '<?xml version=': 0, '>': 19, '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': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '316517', 'license': 'Unlicense', 'n_tokens_mistral': 1666, 'n_tokens_neox': 1588, 'n_words': 340, 'path': '10_k-medoids_spectral/ass10.ipynb', 'repo_name': 'AleRiccardi/game-ai-course', 'size': '4345'}