<jupyter_start><jupyter_text>This file represents assignment for K-means and FCM done by Goudarzi-Samimi group.  First part: K-means<jupyter_code>from pyclustering.cluster.kmeans import kmeans, kmeans_visualizer, kmeans_observer
from pyclustering.cluster.center_initializer import kmeans_plusplus_initializer, random_center_initializer
from pyclustering.samples.definitions import FCPS_SAMPLES, SIMPLE_SAMPLES
from pyclustering.utils import read_image, draw_image_color_segments, read_sample, distance_metric, type_metric
from pyclustering.cluster.elbow import elbow, random_center_initializer<jupyter_output><empty_output><jupyter_text>PyClustering is an open source data mining library written in Python and C++ that provides a wide range of clustering algorithms and methodsFor more details and document see :https://pyclustering.github.io/docs/0.9.3/html/index.html This will check whether imported file exists or not:<jupyter_code>from os.path import isfile
file_name = 'sample1.jpg'
if isfile(file_name):
    sample = read_image(file_name)
else:
    raise ImportError('File not found.')<jupyter_output><empty_output><jupyter_text>After, we tried to estimate proper number of clusters using elbow:<jupyter_code>kmin, kmax = 1, 11
elbow_instance = elbow(sample, kmin, kmax)
elbow_instance.process()
amount_clusters = elbow_instance.get_amount()
wce = elbow_instance.get_wce()<jupyter_output><empty_output><jupyter_text>Then, We plot data:<jupyter_code>from matplotlib.pyplot import plot
x = range(kmax - kmin)
chart = plot(x, wce, color='b', linewidth = 3, 
         marker='o', markerfacecolor='red', markersize=12, markevery=[amount_clusters])<jupyter_output><empty_output><jupyter_text>In the next cell we initializ kmean and calculate centers using kmeans_plusplus algorithm and random initializer both<jupyter_code>#manhattan_metric = distance_metric(type_metric.MINKOWSKI, degree=4)
initial_centers_kmeans_plusplus = kmeans_plusplus_initializer(sample, amount_clusters).initialize()
initial_cneters_random = random_center_initializer(sample, amount_clusters).initialize()<jupyter_output><empty_output><jupyter_text>After that its time to initial kmeans instance and process algorithm:<jupyter_code>kmeans_instance_kmeans_plusplus = kmeans(sample, initial_centers_kmeans_plusplus, itermax = 100000)
kmeans_instance_random = kmeans(sample, initial_cneters_random, itermax = 100000)
kmeans_instance_kmeans_plusplus.process()
kmeans_instance_random.process()<jupyter_output><empty_output><jupyter_text>By drawing tool we show result of kmeans for both center initializers<jupyter_code>clusters_kmeans_plusplus = kmeans_instance_kmeans_plusplus.get_clusters()
clusters_random = kmeans_instance_random.get_clusters()
print("The Kmeans plus plus intialized centers:\n")
draw_image_color_segments(file_name, clusters_kmeans_plusplus, hide_axes = False)
print("Random centers:\n")
draw_image_color_segments(file_name, clusters_random, hide_axes = False)<jupyter_output>The Kmeans plus plus intialized centers:<jupyter_text>Now we use the "ground truth" cluster amount and repeat previouse cells:<jupyter_code>ground_truth_filename = 'goudarzi-samimi_edited.png'
if isfile(ground_truth_filename):
    ground_truth = read_image(ground_truth_filename)
else:
    raise ImportError(ground_truth_filename + 'File not found.')<jupyter_output><empty_output><jupyter_text>Now we have list of RGB values of 'ground truth.jpg'. Its time to distribute every pixel among ground clusters:<jupyter_code>seen = []
ground_clusters = []
for i in range (256*256):
    if ground_truth[i] not in seen:
        seen.append(ground_truth[i])
        cluster = []
        cluster.append(i)
        ground_clusters.append(cluster)
    else:
        cluster_index = seen.index(ground_truth[i])
        ground_clusters[cluster_index].append(i)
ground_truth_cluster_amount = len(ground_clusters) - 1<jupyter_output><empty_output><jupyter_text>Ground truth cluster amount has been prepared now we continue calculating:<jupyter_code>initial_centers_kmeans_plusplus_gt = kmeans_plusplus_initializer(sample, ground_truth_cluster_amount).initialize()
initial_cneters_random_gt = random_center_initializer(sample, ground_truth_cluster_amount).initialize()<jupyter_output><empty_output><jupyter_text>And again process the algorithm:<jupyter_code>kmeans_instance_kmeans_plusplus_gt = kmeans(sample, initial_centers_kmeans_plusplus_gt)
kmeans_instance_random_gt = kmeans(sample, initial_cneters_random_gt)
kmeans_instance_kmeans_plusplus_gt.process()
kmeans_instance_random_gt.process()<jupyter_output><empty_output><jupyter_text>Here is the results:<jupyter_code>clusters_kmeans_plusplus_gt = kmeans_instance_kmeans_plusplus_gt.get_clusters()
clusters_random_gt = kmeans_instance_random_gt.get_clusters()
print("The Kmeans plus plus intialized centers:\n")
draw_image_color_segments(file_name, clusters_kmeans_plusplus_gt, hide_axes = False)
print("Random centers:\n")
draw_image_color_segments(file_name, clusters_random_gt, hide_axes = False)<jupyter_output>The Kmeans plus plus intialized centers:<jupyter_text>Using top two figures, You can more specifically compare between two methods of center initialization:                         Random center initialization vs kmeans_plusplus center initialization K-means uses Euclidean distance by default, but now we gonna change it to Manhattan distance and compare results: We use manhattan but before we must define cosine first:<jupyter_code>manhattan_metric = distance_metric(type_metric.MANHATTAN)<jupyter_output><empty_output><jupyter_text>Now we process data again:<jupyter_code>initial_centers_manhattan_metric = kmeans_plusplus_initializer(sample, ground_truth_cluster_amount).initialize()

kmeans_instance_manhattan_metric = kmeans(sample, initial_centers_manhattan_metric, metric = manhattan_metric, itermax = 100000)
kmeans_instance_manhattan_metric.process()<jupyter_output><empty_output><jupyter_text>and the last part is drawing the results:<jupyter_code>clusters_manhattan_metric = kmeans_instance_manhattan_metric.get_clusters()
print("Manhattan_metric:\n")
draw_image_color_segments(file_name, clusters_manhattan_metric, hide_axes = False)<jupyter_output>Manhattan_metric:<jupyter_text>We have an idea to improve performance of kmeans but due to feasiblity of making extra overload during calculation of accuracy we just apply it for the last kmeans instance and its Manhattan metric  Idea comes from adding position of pixel to our data to seperate objects in a better way, thus we need another sample:<jupyter_code>sample_5d = sample.copy()<jupyter_output><empty_output><jupyter_text>And then we add extera to dimension to every pixel data(but we devide them by 5 less affect the process) :<jupyter_code>for i in range(len(sample_5d)):
    sample_5d[i].append((i%256)/5)
    sample_5d[i].append(int((i - (i%256))/256)/5)<jupyter_output><empty_output><jupyter_text>Then we do the last process again:<jupyter_code>initial_cneters_manhattan_metric_5d = kmeans_plusplus_initializer(sample_5d, ground_truth_cluster_amount).initialize()
kmeans_instance_manhattan_metric_5d = kmeans(sample_5d, initial_cneters_manhattan_metric_5d, metric = manhattan_metric,
                                             itermax = 100000)
kmeans_instance_manhattan_metric_5d.process()
clusters_manhattan_metric_5d = kmeans_instance_manhattan_metric_5d.get_clusters()
print("Manhattan_metric in 5D:\n")
draw_image_color_segments(file_name, clusters_manhattan_metric_5d, hide_axes = False)<jupyter_output>Manhattan_metric in 5D:<jupyter_text>In the next cell we try to open ground truth image to prepare it for accuracy calculation. First of all we need to define a function to return common members between two list:<jupyter_code>def intersection(in1, in2):
    intersection_count = 0
    for value in in1:
        if value in in2:
            intersection_count += 1
    return intersection_count<jupyter_output><empty_output><jupyter_text>Now for every cluster in "result clusters" we assume the most common in members "ground truth clusers" list as the main cluster detected. This will create a mapping between results and ground clusters:<jupyter_code>methods = [clusters_kmeans_plusplus.copy(),
           clusters_random.copy(),
           clusters_kmeans_plusplus_gt.copy(),
           clusters_random_gt.copy(),
           clusters_manhattan_metric.copy(),
           clusters_manhattan_metric_5d.copy()]
ground_clusters.sort(key=lambda a:len(a), reverse=True)
currect_detected_pixels = []<jupyter_output><empty_output><jupyter_text>Running next cell may take so long :)<jupyter_code>for j in range(len(methods)):
    forbidden_clusters = [] 
    currect_detected_pixels.append(0)
    for i in range(len(methods[j])):
        intersection_counts_max = 0
        remove_cluster = -1
        if forbidden_clusters == len(methods[j]):
            break
        for cluster in ground_clusters:
            if i in forbidden_clusters:
                continue
            intersection_count = intersection(cluster, methods[j][i])
            if intersection_count > intersection_counts_max:
                intersection_counts_max = intersection_count
                remove_cluster = i
        forbidden_clusters.append(remove_cluster)
        currect_detected_pixels[j] += intersection_counts_max
print('\033[1m' + 'Accuracy' + '\033[0m')
print ('For kmeans algorithm using Elbow and kmeans plus plus:\n', currect_detected_pixels[0]*100/(256*256), ' %')
print ('For kmeans algorithm using Elbow and random center initialize:\n', currect_detected_pixels[1]*100/(256*256), ' %')
print ('For kmeans algorithm using ground truth cluster amount and kmeans plus plus:\n',
       currect_detected_pixels[2]*100/(256*256), ' %')
print ('For kmeans algorithm using ground truth cluster amount and random center initialize:\n',
       currect_detected_pixels[3]*100/(256*256), ' %')
print ('For kmeans algorithm using ground truth cluster ampunt and kmeans plus plus and manhattan metric:\n',
       currect_detected_pixels[4]*100/(256*256), ' %')
print ('For kmeans algorithm using ground truth cluster ampunt and kmeans plus plus and manhattan metric + adding two dimensions:\n',
       currect_detected_pixels[5]*100/(256*256), ' %')<jupyter_output>[1mAccuracy[0m
For kmeans algorithm using Elbow and kmeans plus plus:
 55.657958984375  %
For kmeans algorithm using Elbow and random center initialize:
 56.1737060546875  %
For kmeans algorithm using ground truth cluster amount and kmeans plus plus:
 62.225341796875  %
For kmeans algorithm using ground truth cluster amount and random center initialize:
 60.4644775390625  %
For kmeans algorithm using ground truth cluster ampunt and kmeans plus plus and manhattan metric:
 60.05401611328125  %
For kmeans algorithm using ground truth cluster ampunt and kmeans plus plus and manhattan metric + adding two dimensions:
 68.50128173828125  %<jupyter_text>Second Part: Fuzzy C-means<jupyter_code>from pyclustering.cluster.fcm import fcm<jupyter_output><empty_output><jupyter_text>We have initialized the centers for kmeans part thus we dont need to do its again and lets go straight to the process part:<jupyter_code># center initialized by kmeans plus plus and cluster amount as Elbow returned:
fcm_instance_kmeans_plusplus = fcm(sample, initial_centers_kmeans_plusplus)
fcm_instance_kmeans_plusplus.process()
clusters_fcm_kmeans_plusplus = fcm_instance_kmeans_plusplus.get_clusters()
print("center initialized by kmeans plus plus and cluster amount as Elbow returned:\n")
draw_image_color_segments(file_name, clusters_fcm_kmeans_plusplus, hide_axes = False)

# center initialized by random initializer and cluster amount as Elbow returned:
fcm_instance_random = fcm(sample, initial_cneters_random)
fcm_instance_random.process()
clusters_fcm_random = fcm_instance_random.get_clusters()
print("center initialized by random initializer and cluster amount as Elbow returned:\n")
draw_image_color_segments(file_name, clusters_fcm_random, hide_axes = False)

# center initialized by kmeans plus plus and cluster amount as ground truth clusters:
fcm_instace_kmeans_plusplus_gt = fcm(sample, initial_centers_kmeans_plusplus_gt)
fcm_instace_kmeans_plusplus_gt.process()
clusters_fcm_kmeans_plusplus_gt = fcm_instace_kmeans_plusplus_gt.get_clusters()
print("center initialized by kmeans plus plus and cluster amount as ground truth clusters:\n")
draw_image_color_segments(file_name, clusters_fcm_kmeans_plusplus_gt, hide_axes = False)

# center initialized by random initializer and cluster amount as ground truth clusters:
fcm_instance_random_gt = fcm(sample, initial_cneters_random_gt)
fcm_instance_random_gt.process()
clusters_fcm_random_gt = fcm_instance_random_gt.get_clusters()
print("center initialized by random initializer and cluster amount as ground truth clusters:\n")
draw_image_color_segments(file_name, clusters_fcm_random_gt, hide_axes = False)

# center initialized by kmeans plus plus and cluster amount as ground truth clusters in 5D:
initial_centers_kmeans_plusplus_gt_5d = initial_cneters_manhattan_metric_5d
fcm_instace_kmeans_plusplus_gt_5d = fcm(sample, initial_centers_kmeans_plusplus_gt_5d)
fcm_instace_kmeans_plusplus_gt_5d.process()
clusters_fcm_kmeans_plusplus_gt_5d = fcm_instace_kmeans_plusplus_gt_5d.get_clusters()
print("center initialized by kmeans plus plus and cluster amount as ground truth clusters:\n")
draw_image_color_segments(file_name, clusters_fcm_kmeans_plusplus_gt_5d, hide_axes = False)<jupyter_output>center initialized by kmeans plus plus and cluster amount as Elbow returned:<jupyter_text>Now let measure accuract of FCM and compare it to K means:<jupyter_code>methods = [clusters_fcm_kmeans_plusplus.copy(), 
           clusters_fcm_random.copy(), 
           clusters_fcm_kmeans_plusplus_gt.copy(), 
           clusters_fcm_random_gt.copy(), 
           clusters_fcm_kmeans_plusplus_gt_5d.copy()]
currect_detected_pixels = []
for j in range(len(methods)):
    forbidden_clusters = [] 
    currect_detected_pixels.append(0)
    for i in range(len(methods[j])):
        intersection_counts_max = 0
        remove_cluster = -1
        if forbidden_clusters == len(methods[j]):
            break
        for cluster in ground_clusters:
            if i in forbidden_clusters:
                continue
            intersection_count = intersection(cluster, methods[j][i])
            if intersection_count > intersection_counts_max:
                intersection_counts_max = intersection_count
                remove_cluster = i
        forbidden_clusters.append(remove_cluster)
        currect_detected_pixels[j] += intersection_counts_max
print('\033[1m' + 'Accuracy' + '\033[0m')
print ('For FCM algorithm using Elbow and kmeans plus plus:\n', currect_detected_pixels[0]*100/(256*256), ' %')
print ('For FCM algorithm using Elbow and random center initialize:\n', currect_detected_pixels[1]*100/(256*256), ' %')
print ('For FCM algorithm using ground truth cluster amount and kmeans plus plus:\n',
       currect_detected_pixels[2]*100/(256*256), ' %')
print ('For FCM algorithm using ground truth cluster amount and random center initialize:\n',
       currect_detected_pixels[3]*100/(256*256), ' %')
print ('For FCM algorithm using ground truth cluster ampunt and kmeans plus plus + adding two dimensions:\n',
       currect_detected_pixels[4]*100/(256*256), ' %')<jupyter_output>[1mAccuracy[0m
For FCM algorithm using Elbow and kmeans plus plus:
 58.03375244140625  %
For FCM algorithm using Elbow and random center initialize:
 58.03375244140625  %
For FCM algorithm using ground truth cluster amount and kmeans plus plus:
 71.81243896484375  %
For FCM algorithm using ground truth cluster amount and random center initialize:
 73.0804443359375  %
For FCM algorithm using ground truth cluster ampunt and kmeans plus plus + adding two dimensions:
 71.8170166015625  %
{'fraction_non_alphanumeric': 0.07486294032390195, 'fraction_numerical': 0.024576217783099125, 'mean_word_length': 6.17774762550882, 'pattern_counts': {'":': 0, '<': 90, '<?xml version=': 0, '>': 92, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '24', 'dir': 'jupyter-structured-clean-dedup', 'id': '51026', 'license': 'MIT', 'n_tokens_mistral': 5282, 'n_tokens_neox': 4867, 'n_words': 1233, 'path': 'Untitled.ipynb', 'repo_name': 'mahdisamimi/Semantic-Segmentation', 'size': '15869'}