 # Exercises

 We have prepared five exercises in this chapter:

 1. Modify the HCM code to work for three groups. This exercise can be divded into four tasks:
     - modify the parameters,
     - modify the calculate_u function,
     - execute the clustering,
     - plot the results.
 2. For density clustering, plot the feature space with all element marked with different color, depending on the cluster that it's assigned to. You should do the following tasks:
     - fill the get_color method,
     - fill the plot code.
 3. Build a method that plot baed on dendrograms_history and pydot, a dendrogram for the divisive clustering method. You should base on agglomerative method, but keep in mind that it works top-down instead of bottom-up. This exercise need just one function to be implemented:
     - show_tree_divisive.
     You should loop over the dendrogram_history variable and loop over childs.
 4. Implement the $s_{2}$ metric
 5. Draw the borders between clusters in the output image

 ## Libraries

 To solve the exercises, we need the following libraries to load in the first place.



```python
import numpy
import random
import numpy as np
import pandas as pd
from math import sqrt

import matplotlib.image as img
import PIL.Image

from matplotlib import pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

from IPython.display import Image

import pydot

```

 ## Load data

 ## Exercise 1: Modify the HCM code to work for three groups

 The obvious part is the variable ```groups```, but the most changes needs to be done here:


```python
get_ipython().run_line_magic('store', '-r data_set')

# change here:
groups = 3

error_margin = 0.01
m = 2
assignation = np.zeros((len(data_set), groups))

# centers = np.array([[0.01229673, 0.25183492],
#                     [0.3689626, 0.61904127],
#                     [0.95732769, 0.45059586]])

centers = np.array([[0.01229673, 0.25183492],
                    [0.3689626, 0.61904127],
                    [0.95732769, 0.45059586]])


def calculate_distance(x, v):
    return sqrt((x[0]-v[0])**2+(x[1]-v[1])**2)


def calculate_new_centers(u):
    new_centers = []
    for c in range(groups):
        u_x_vector = np.zeros(2)
        u_scalar = 0.0
        for i in range(len(data_set)):
            u_scalar = u_scalar+(u[i][c]**m)
            u_x_vector = np.add(
                u_x_vector, np.multiply(u[i][c]**m, data_set[i]))
        new_centers.append(np.divide(u_x_vector, u_scalar))
    return new_centers


def calculate_differences(new_assignation, assignation):
    return np.sum(np.abs(np.subtract(assignation, new_assignation)))


def cluster_hcm(assignation, centers):
    difference_limit_not_achieved = True
    new_centers = centers
    iter = 0
    while difference_limit_not_achieved:
        new_assignation = []
        for i in range(len(data_set)):
            new_assignation.append(calculate_u_three(data_set[i], new_centers))
        new_centers = calculate_new_centers(new_assignation)
        if iter > 0:
            if calculate_differences(new_assignation, assignation) < error_margin:
                difference_limit_not_achieved = False
        assignation = new_assignation
        iter = iter+1
    return new_assignation, new_centers

```

 ### Modify the ``calculate_u`` function

 Fill the gap below to make the function working for more groups than two. The goal here is to calculate the distance between ``x`` and the center of a given group and append the value to ``minimal_distance``.


```python


def calculate_u_three(x, centers):
    u_array = np.zeros(groups)
    minimal_distance = []
    for group in range(groups):
        distance = calculate_distance(x, centers[group])
        minimal_distance.append(distance)
    min_group_id = np.argmin(minimal_distance)
    u_array[min_group_id] = 1
    return u_array

```

 ### Execute the clustering

 As in the previous example we need to cluster it.


```python
new_assignation_hcm3, new_centers_hcm3 = cluster_hcm(assignation, centers)
pd.DataFrame(new_centers_hcm3)

```




<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>0</th>
      <th>1</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>0</th>
      <td>0.078585</td>
      <td>0.178323</td>
    </tr>
    <tr>
      <th>1</th>
      <td>0.496071</td>
      <td>0.692516</td>
    </tr>
    <tr>
      <th>2</th>
      <td>0.958743</td>
      <td>0.955892</td>
    </tr>
  </tbody>
</table>
</div>



 ### Plot the results


```python
red = data_set[np.where(np.array(new_assignation_hcm3)[:, 0] == 1)]
blue = data_set[np.where(np.array(new_assignation_hcm3)[:, 1] == 1)]
green = data_set[np.where(np.array(new_assignation_hcm3)[:, 2] == 1)]

fig, ax = plt.subplots()

ax.scatter(blue[:, 0], blue[:, 1], c='blue')
ax.scatter(red[:, 0], red[:, 1], c='red')
ax.scatter(green[:, 0], green[:, 1], c='green')
ax.scatter(np.array(new_centers_hcm3)[:, 0], np.array(
    new_centers_hcm3)[:, 1], c='black')
ax.set(xlabel='Seats count', ylabel='Distance range (km)',
       title='Aircrafts (clusters)')
ax.grid()
plt.show()

```

 ## Exercise 2: Plot the density clusters

 Use the code below to plot the results. You can play with the max_distance variable to get more or less groups.


```python
get_ipython().run_line_magic('store', '-r new_assignation_density')
get_ipython().run_line_magic('store', '-r data_set')

# print(data_set)
# print(new_assignation_density)

```

 ### Fill the ``get_group_objects`` method

 Only one line needs to be updated. The ``get_group_objects`` function should return the objects of a given group.


```python
colors = ['red', 'blue', 'green', 'orange', 'black', 'yellow']


def get_group_objects(color_id):
    objects = []
    for idx, density in enumerate(new_assignation_density):
        if density == color_id:
            objects.append(data_set[idx])
    return np.array(objects)

```

 ### Fill the plot code

 If done properly the code below should return a plot of two clusters and the noise.


```python
colors = ['red', 'blue', 'green', 'orange', 'black', 'yellow']

fig, ax = plt.subplots()

assigned_groups = new_assignation_density
# print(assigned_groups)
for group in np.unique(assigned_groups):
    small_set = get_group_objects(group)
    ax.scatter(small_set[:, 0], small_set[:, 1], c=colors.pop(0))
    for circle in small_set:
        circle1 = plt.Circle((circle[0], circle[1]),
                             0.25, color='green', fill=False)
        ax.add_artist(circle1)

ax.set(xlabel='Seats count', ylabel='Distance range (km)',
       title='Aircrafts (clusters)')
ax.grid()
plt.show()

```

 ## Exercise 3: Build a dendrogram using dendrograms_history and pydot

 In this exercise we gonna use the variable dendrograms_history and pydot. Below we restore the variable and initialize the dendrogram graph.


```python
get_ipython().run_line_magic('store', '-r dendrogram_hist_diana')

print(dendrogram_hist_diana)

tree = pydot.Dot(graph_type='graph')

```

    [[{'acesor': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 'childs': [[6, 7, 8], [0, 1, 2, 3, 4, 5, 9]]}], [{'acesor': [6, 7, 8], 'childs': [[8], [6, 7]]}], [{'acesor': [0, 1, 2, 3, 4, 5, 9], 'childs': [[9], [0, 1, 2, 3, 4, 5]]}], [{'acesor': [0, 1, 2, 3, 4, 5], 'childs': [[0, 3, 4], [1, 2, 5]]}], [{'acesor': [0, 3, 4], 'childs': [[0], [3, 4]]}], [{'acesor': [1, 2, 5], 'childs': [[2], [1, 5]]}], [{'acesor': [1, 5], 'childs': [[1], [5]]}], [{'acesor': [6, 7], 'childs': [[6], [7]]}], [{'acesor': [3, 4], 'childs': [[3], [4]]}]]


 ### Fill ``show_tree_divisive`` function

 The function show_tree_divisive goes through each child node and build and edge between.


```python
def show_tree_divisive():
    for item in dendrogram_hist_diana:
        for child in item[0]["childs"]:
#             print(child)
            new_edge = pydot.Edge(str(item[0]["acesor"]), str(child))
            tree.add_edge(new_edge)
    tree.write('tree.png', format='png')


show_tree_divisive()
```

 Take a look if you did it properly:


```python
Image(filename='tree.png')
```

 ## Exercise 4: Implement the $s_{2}$ metric

 The $s_{2}$ metric gives a better understanding of the distances between centers.

 \begin{equation}
  s_{2}(c_{i},c_{j})=d(c_{i},c_{j}).
 \end{equation}

 Let's restore the centers from HCM grouped by two and initialize the values for three groups as below.


```python
get_ipython().run_line_magic('store', '-r new_centers_hcm')

new_centers_hcm = np.array(new_centers_hcm)
new_centers_hcm3 = np.array(
    [[0.42239686, 0.38503185], [0.07858546, 0.17832272], [0.82907662, 0.97059448]])


print(new_centers_hcm)
print(new_centers_hcm3)
```

    [[0.82907662 0.97059448]
     [0.12770138 0.20785259]]
    [[0.42239686 0.38503185]
     [0.07858546 0.17832272]
     [0.82907662 0.97059448]]


 Measure the distance between each center.


```python
def calculate_s_2(centers):
    s2 = []
    for center_1 in range(len(centers)):
        for center_2 in range(len(centers)):
            if center_1 == center_2:
                break
            s2.append(calculate_distance(centers[center_1], centers[center_2]))            
            # fill the code here (3 lines)
    return s2
```

Test:


```python
print(calculate_s_2(new_centers_hcm))
print(calculate_s_2(new_centers_hcm3))
```

    [1.0361961303876361]
    [0.40116697670087065, 0.7129319889345509, 1.0912980907761376]



## Exercise 5: Modify the output image with borders between clusters

 We use the ``Segmentation`` class as in previous example.


```python


class Segmentation:

    def __init__(self, feature_matrix, groups):
        self.__data_set = feature_matrix
        self.__groups = groups
        self.__space = [[0, 255], [0, 255], [0, 255]]
        self.__error_margin = 0.5
        self.assignation = np.zeros((len(self.__data_set), self.__groups))
        self.centers = []
        self.select_centers()

    def select_centers(self):
        if len(self.centers) == 0:
            iter = 0
            while iter < self.__groups:
                self.centers.append(((random.randrange(0, 255)*1.0/255),
                                     (random.randrange(0, 255)*1.0/255),
                                     (random.randrange(0, 255)*1.0/255)))
                iter = iter+1

    def calculate_distance(self, x, v):
        return sqrt((x[0]-v[0])**2+(x[1]-v[1])**2+(x[2]-v[2])**2)

    def calculate_u(self, x, i):
        smallest_distance = float(self.calculate_distance(x, self.centers[0]))
        smallest_id = 0
        for i in range(1, self.__groups):
            distance = self.calculate_distance(x, self.centers[i])
            if distance < smallest_distance:
                smallest_id = i
                smallest_distance = distance
        distance = np.zeros(self.__groups)
        distance[smallest_id] = 1
        return distance

    def calculate_new_centers(self, u):
        new_centers = []
        for c in range(self.__groups):
            u_x_vector = np.zeros(len(self.centers[0]))
            u_scalar = 0
            for i in range(len(u)):
                u_scalar = u_scalar + u[i][c]
                u_x_vector = np.add(u_x_vector, np.multiply(
                    u[i][c], self.__data_set[i]))
            new_centers.append(np.divide(u_x_vector, u_scalar))
        self.centers = new_centers

    def calculate_differences(self, new_assignation):
        diff = 0
        for i in range(len(self.assignation)):
            for j in range(self.__groups):
                diff = diff + \
                    abs(float(new_assignation[i][j]) -
                        float(self.assignation[i][j]))
        return diff

    def do_segmentation(self):
        difference_limit_not_achieved = True
        iter = 0
        while difference_limit_not_achieved:
            new_assignation = []
            for i in range(len(self.__data_set)):
                new_assignation.append(
                    self.calculate_u(self.__data_set[i], iter))
            self.calculate_new_centers(new_assignation)

            if iter > 0:
                if self.calculate_differences(new_assignation) < self.__error_margin:
                    difference_limit_not_achieved = False
            self.assignation = new_assignation
            iter = iter + 1

    def get_results(self):
        return self.centers, self.assignation

```

 ### Change ``save_image`` method

 Add an if statement in the code below. It should consider the change of ``current_pixel`` variable. Please keep in mind that there should be three states considered.


```python
class ImageConversion:

    def get_image_from_url(self, img_url):
        image = open(img_url, 'rb')
        return img.imread(image)

    def get_unique_colours(self, image_matrix):
        feature_matrix = []
        for i in range(len(image_matrix)):
            for j in range(len(image_matrix[0])):
                feature_matrix.append(image_matrix[i, j])
        feature_matrix_np = np.array(feature_matrix)
        uniques, index = np.unique(
            [str(i) for i in feature_matrix_np], return_index=True)
        return feature_matrix_np[index], feature_matrix

    def save_image(self, size, pixel_matrix, unique_matrix, assignation_matrix, colours, output):
        image_out = PIL.Image.new("RGB", size)
        pixels = []
        current_pixel = None  # added
        for i in range(len(pixel_matrix)):
            pixel_list = pixel_matrix[i].tolist()
            for j in range(len(unique_matrix)):
                if (pixel_list == unique_matrix[j].tolist()):
                    for k in range(len(colours)):
                        if assignation_matrix[j][k] == 1:
                            segmented_colours = [int(i) for i in (colours[k] * 255)]
                            if current_pixel is not None and current_pixel != k:
                                segmented_colours = [0,0,0]
                            current_pixel = k
                            pixels.append(tuple(segmented_colours))
                            # fill here (about 6-7 lines)
        image_out.putdata(pixels)
        image_out.save(output)

    def do_segmentation(self):
        difference_limit_not_achieved = True
        iter = 0
        while difference_limit_not_achieved:
            new_assignation = []
            for i in range(len(self.__data_set)):
                new_assignation.append(
                    self.calculate_u(self.__data_set[i], iter))
            self.calculate_new_centers(new_assignation)
            if iter > 0:
                if self.calculate_differences(new_assignation) < self.__error_margin:
                    difference_limit_not_achieved = False
            self.assignation = new_assignation
            iter = iter + 1

    def get_results(self):
        return self.centers, self.assignation

```

 Execute segmentation without any changes:


```python
image_to_segment = "images/logo_krakow.png"
image_converter = ImageConversion()
image_data = image_converter.get_image_from_url(image_to_segment)
unique_image_data, image_data_list = image_converter.get_unique_colours(
    image_data)

groups = 3

segmentation = Segmentation(unique_image_data, groups)
segmentation.do_segmentation()
centers, assignation_matrix = segmentation.get_results()

image_size = (232, 258)
# image_converter.save_image(image_size, image_data_list, unique_image_data, assignation_matrix, centers, "images/segmented_hw.png")

```


```python
image_converter.save_image(image_size, image_data_list, unique_image_data, assignation_matrix, centers, "images/segmented_hw.png")
```

 The image should have black broders between one and the other segment.


```python
Image("images/segmented_hw.png")
```


```python

```

12c5f90c7fd7ddcc314b1ff98179facbb181e55a
ipynb
Jupyter Notebook
Lab4/hw/hw-047Clustering_Exercises.ipynb
M1nified/UJ-MachineLearning
9ccbcf86082eba359f65a8aa17009c59010cede8
MIT
Lab4/hw/hw-047Clustering_Exercises.ipynb
M1nified/UJ-MachineLearning
9ccbcf86082eba359f65a8aa17009c59010cede8
MIT
Lab4/hw/hw-047Clustering_Exercises.ipynb
M1nified/UJ-MachineLearning
9ccbcf86082eba359f65a8aa17009c59010cede8
MIT
Qwen/Qwen-72B
1. YES
2. YES