<jupyter_start><jupyter_text>Metryki w przestrzeni napisów Zadanie dotyczy różnych metryk w przestrzeni napisów.1. Zaimplementuj przynajmniej 3 "metryki" spośród wymienionych: cosinusowa, LCS, DICE, euklidesowa, Levenshteina.2. Zaimplementuj przynajmniej 1 sposoby oceny jakości klasteryzacji (np. indeks Daviesa-Bouldina).3. Stwórz stoplistę najczęściej występujących słów i zastosuj ją jako pre-processing dla nazw. Algorytmy klasteryzacji powinny działać na dwóch wariantach: z pre-processingiem i bez pre-processingu.4. Wykonaj klasteryzację zawartości załączonego pliku (lines.txt) przy użyciu  metryk zaimplementowanych w pkt. 1. Każda linia to adres pocztowy firmy, różne sposoby zapisu tego samego adresu powinny się znaleźć w jednym klastrze.5. Porównaj jakość wyników sposobami zaimplementowanymi w pkt. 2.6. Czy masz jakiś pomysł na poprawę jakości klasteryzacji w tym zadaniu?Sprawozdanie powinno zawierać porównanie wyników wszystkich metryk z użyciem stoplisty i bez.---<jupyter_code>import numpy as np
from math import inf
from collections import Counter
from sklearn.cluster import DBSCAN
from time import perf_counter
import pandas as pd<jupyter_output><empty_output><jupyter_text>**Exercise 1**<jupyter_code>def ngrams(text, n=2):
    ngram = {}
    for i in range(len(text) - n + 1):
        if text[i:i + n] in ngram:
            ngram[text[i:i + n]] += 1
        else:
            ngram[text[i:i + n]] = 1
    return ngram

def ngram_length(ngram):
    result = 0
    for key, value in ngram.items():
        result += value ** 2
    return np.sqrt(result)<jupyter_output><empty_output><jupyter_text>*Cosine metric*<jupyter_code>def cosine_metric(x, y, n=3):
    x_ngrams = ngrams(x, n)
    y_ngrams = ngrams(y, n)
    result = 0
    for key, value in x_ngrams.items():
        if key in y_ngrams:
            result += value * y_ngrams[key]
    if ngram_length(x_ngrams) * ngram_length(y_ngrams) == 0:
        return 1
    return 1 - result / (ngram_length(x_ngrams) * ngram_length(y_ngrams))<jupyter_output><empty_output><jupyter_text>*LCS metric*<jupyter_code>def lcs_metric(x, y):
    tab = np.array([[None for j in range(len(y) + 1)] for i in range(len(x) + 1)])
    max_lcs = 0
    for i in range(len(x) + 1):
        for j in range(len(y) + 1):
            if i == 0 or j == 0:
                tab[i, j] = 0
            else:
                if x[i - 1] == y[j - 1]:
                    tab[i, j] = tab[i - 1, j - 1] + 1
                else:
                    tab[i, j] = 0
            max_lcs = max(max_lcs, tab[i, j])
    return 1 - max_lcs / max(len(x), len(y))<jupyter_output><empty_output><jupyter_text>*Euclidean metric*<jupyter_code>def euclidean_metric(x, y, n=3):
    x_ngrams = ngrams(x, n)
    y_ngrams = ngrams(y, n)
    result = 0
    for ng in x_ngrams:
        if ng in y_ngrams:
            result += (x_ngrams[ng] - y_ngrams[ng]) ** 2
        else:
            result += x_ngrams[ng] ** 2

    for ng in y_ngrams:
        if ng not in x_ngrams:
            result += y_ngrams[ng] ** 2
    return np.sqrt(result)<jupyter_output><empty_output><jupyter_text>**Exercise 2**<jupyter_code>def find_centroid(cluster, metric, *args):
    distances = [0 for _ in range(len(cluster))]
    for i in range(len(cluster)):
        for j in range(i):
            dist = metric(cluster[i], cluster[j], *args)
            distances[i] += dist
            distances[j] += dist
    min_dist = -inf
    index = -1
    for i in range(len(distances)):
        if distances[i] < min_dist:
            min_dist = distances[i]
            index = i
    return cluster[index]
def average_distance(cluster, metric, *args):
    if len(cluster) < 2:
        return 0
    elif len(cluster) == 2:
        return metric(cluster[0], cluster[1], *args)
    dist_sum = 0
    for i in range(len(cluster)):
        for j in range(i):
            dist_sum += metric(cluster[i], cluster[j], *args)
    return dist_sum / ((len(cluster) - 2) * (len(cluster) - 1))<jupyter_output><empty_output><jupyter_text>*Davies–Bouldin index*<jupyter_code>def davies_bouldin_index(clusters, metric, *args):
    centroids = [find_centroid(c, metric, *args) for c in clusters]
    avg_distance = [average_distance(c, metric, *args) for c in clusters]
    tab = [np.max([(avg_distance[i] + avg_distance[j]) / metric(centroids[i], centroids[j], *args)
                   for i in range(len(clusters)) if i != j]) for j in range(len(clusters))]
    return np.sum(tab) / len(clusters)<jupyter_output><empty_output><jupyter_text>**Exercise 3**<jupyter_code>class StopList:
    def __init__(self, text, frequency):
        words = []
        for line in text:
            words += line.split()
        counter = Counter(words)
        self.common = {key for key, value in counter.items() if value >= frequency * len(words)}

    def remove_common(self, text):
        result = []
        for line in text:
            result.append(" ".join([w for w in line.split() if w not in self.common]))
        return result<jupyter_output><empty_output><jupyter_text>**Exercise 4**<jupyter_code>def read_text(file, n):
    with open(file, "r", encoding="UTF-8") as f:
        text = f.read().splitlines()
    return text[:n]
def make_clustering(text, metric_func, eps, stop_list_freq=None, *args):
    working_text = text
    if stop_list_freq is not None:
        stop_list = StopList(text, stop_list_freq)
        working_text = stop_list.remove_common(text)

    def metric(x, y):
        i, j = int(x[0]), int(y[0])
        return metric_func(working_text[i], working_text[j], *args)

    X = np.arange(len(working_text)).reshape(-1, 1)
    clustering = DBSCAN(metric=metric, min_samples=1, eps=eps).fit_predict(X)
    clusters = [[] for _ in range(max(clustering) + 1)]
    for i in range(len(clustering)):
        clusters[clustering[i]].append(text[i])
    return clusters
def print_clusters(clusters, n):
    i = j = 0
    while j < n and i < len(clusters):
        if len(clusters[i]) != -1:
            for line in clusters[i]:
                print(line)
            print("-----------\n")
            j += 1
        i += 1<jupyter_output><empty_output><jupyter_text>**Exercise 5**<jupyter_code>def test(text, metric_test, stop_list, eps, df_result, clusters_result):
    frequency = None
    if stop_list:
        frequency = 0.01
    for i in range(len(metric_test)):
        start = perf_counter()
        clusters = make_clustering(text, metric_test[i], eps[i], frequency)
        end = perf_counter()
        time = end - start
        print(f"Function: {metric_test[i].__name__}")
        print(f"Epsilon: {eps[i]}")
        print(f"Time: {time} s")
        db_index = davies_bouldin_index(clusters, metric_test[i])
        print(f"Davies-Bouldin index: {db_index}")
        print("-------------------------------------\n")
        clusters_result.append(clusters)
        df_result += [metric_test[i].__name__, eps[i], time, db_index, stop_list]
def perform_tests(metric_test, eps, filename, stop_list_clusters, no_stop_list_clusters):
    text = read_text(filename, 100)
    df_result = []
    print("Test with stop list\n\n")
    test(text, metric_test, True, eps, df_result, stop_list_clusters)
    print("Test without a stop list\n\n")
    test(text, metric_test, False, eps, df_result, no_stop_list_clusters)
    df = pd.DataFrame(data={"Function": df_result[::5],
                            "Epsilon": df_result[1::5],
                            "Time [s]": df_result[2::5],
                            "Davies-bouldin index": df_result[3::5],
                            "Is stop list": df_result[4::5]})
    return df
def print_all_clusters(result, metric_test, n):
    for i in range(len(result)):
        print_clusters(result, n)<jupyter_output><empty_output><jupyter_text>**lines.txt**<jupyter_code>metric_test = [cosine_metric, lcs_metric, euclidean_metric]
eps = [0.3, 0.7, 0.5]
stop_list_clusters = []
no_stop_list_clusters = []
lines_df = perform_tests(metric_test, eps, "lines.txt", stop_list_clusters, no_stop_list_clusters)
lines_df<jupyter_output>Test with stop list


Function: cosine_metric
Epsilon: 0.3
Time: 1.6095287630000712 s
Davies-Bouldin index: 0.4657038457766446
-------------------------------------

Function: lcs_metric
Epsilon: 0.7
Time: 52.755016033000175 s
Davies-Bouldin index: 1.2023131568210284
-------------------------------------

Function: euclidean_metric
Epsilon: 0.5
Time: 1.1613715779999438 s
Davies-Bouldin index: 0.13368145786394758
-------------------------------------

Test without a stop list


Function: cosine_metric
Epsilon: 0.3
Time: 1.7890331090002292 s
Davies-Bouldin index: 0.4727902854700944
-------------------------------------

Function: lcs_metric
Epsilon: 0.7
Time: 61.71837181899991 s
Davies-Bouldin index: 1.2212013662766585
-------------------------------------

Function: euclidean_metric
Epsilon: 0.5
Time: 1.2460248630000024 s
Davies-Bouldin index: 0.0
-------------------------------------<jupyter_text>Obliczenia zostały wykonane dla skróconego pliku do 100 pierwszych linii tekstu, ponieważ dłuższe teksty zajmowały bardzo dużo czasu. Wartości epsilon zostały dobrane w taki sposób, aby stworzone klastry w jak największym stopniu odpowiadały tym w plikach dołączonych do zadania. Użycie stop listy nie spowodowało znaczących zmian w podziale na klastry. Zmieniło jednak wartości indeksów i różniło się nieco czasem wykonania.Ranking klasteryzacji wg indeksu Davies-Bouldina dla pliku *lines.txt* (metoda euklidesa bez stop listy zwracała wyniki 0 więc ją pominąłem w tym zestawieniu):1. Metryka Euklidesa (ze stoplistą)2. Metryka cosinusowa (ze stoplistą)3. Metryka cosinusowa (bez stoplisty)4. Metryka LCS (ze stop listą)5. Metryka LCS (bez stop listy)Jeśli chodzi o czas to najszybciej wykonywała się metryka Euklidesa, następnie metryka cosinusowa i na najwolniej metryka LCS, można to zaobserwować na powyższych data frameach.<jupyter_code>print("------STOP LIST CLUSTER RESULT------\n")
print_all_clusters(stop_list_clusters, metric_test, 5)
print("------NO STOP LIST CLUSTER RESULT------\n")
print_all_clusters(no_stop_list_clusters, metric_test, 5)<jupyter_output>------NO STOP LIST CLUSTER RESULT------

['/11692589 RD TUNA CANNERS, LTD. PORTION 1004, SIAR NORTH COAST ROAD, P.O.BOX 2113, MADANG, PAPUA NEW GUINEA']
["''PA INTERIOR'' LTD BOLSHAYA LUBYANKA STREET, 16/4 MOSCOW, 101000, RUSSIA INN/KPP 7704550148//770801001 495-984-8611"]
["''SSONTEX''  Sp.ZO.O.IMPORT-EXPORTUL:PRZECLAWSKA 5 03-879 WARSZAWA,POLAND NIP 113-01-17-669", "''SSONTEX''SP.ZO.O.IMPORT-EXPORT UL:PRZECLAWSKA 5 03-879 WARSZAWA,POLAND NIP 113-01-17-669 TEL./FAX.:0048(022)217 6532--", '"SSONTEX" SP.ZO.O IMPORT-EXPORT 03-879 WARSZAWA UL PRZECLAWSKA 5 NIP:113-01-17-669']
["''TOPEX SP. Z O.O.'' SPOLKA KOMANDYTOWA UL. POGRANICZNA 2/4  02-285 WARSZAWA POLAND"]
["'MASTER PLUS CO.,LTD.' 143000,RUSSIA,MO,ODINSOVO, MOJAISKOE, SHOSSE,153G TEL:+7495 7273939"]
['"2TIGERS GROUP LIMITED"  ROOM 504 JINSHAZHOU SHANGSHUI ROAD,  GUANGZHOU 510160']
['"ALDETRANS" LLC, 105066, MOSCOW, RUSSIA, TOKMAKOV LANE, 11. TEL:+7(495)641-03-89']
['"A-LIFT",JSC 1 PROSPEKT MARSHALA ZHUKOVA,MOSCOW 123308,RUSSIA  T: +[...]
{'fraction_non_alphanumeric': 0.14, 'fraction_numerical': 0.042959641255605384, 'mean_word_length': 3.1117256637168142, 'pattern_counts': {'":': 5, '<': 51, '<?xml version=': 0, '>': 48, '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': '12', 'dir': 'jupyter-structured-clean-dedup', 'id': '633424', 'license': 'MIT', 'n_tokens_mistral': 4527, 'n_tokens_neox': 4180, 'n_words': 1006, 'path': 'Lab_6/Lab_6_code.ipynb', 'repo_name': 'Szymon-Budziak/Text_algorithms', 'size': '11150'}