5-clustering/zad5.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "productive-integral",
   "metadata": {},
   "source": [
    "# Zadanie nr 5 - Metryki w przestrzeni napisów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "front-directory",
   "metadata": {},
   "outputs": [],
   "source": [
    "import sklearn.cluster\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from math import inf\n",
    "from collections import Counter"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "choice-morocco",
   "metadata": {},
   "source": [
    "## 1. Metryki"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "hired-internet",
   "metadata": {},
   "source": [
    "<i>Zaimplementuj przynajmniej 3 metryki spośród wymienionych: cosinusowa, LCS, DICE, euklidesowa.</i>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "future-pasta",
   "metadata": {},
   "source": [
    "x, y - napisy/listy, których odległość szukamy. oznaczenie odpowiada temu w slajdach z laboratorium"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "talented-musician",
   "metadata": {},
   "source": [
    "* LCS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "quality-elements",
   "metadata": {},
   "outputs": [],
   "source": [
    "def lcs(x, y):\n",
    "    common = [[0 for _ in range(len(y)+1)] for _ in range(len(x)+1)]\n",
    "    max_lcs = 0\n",
    "\n",
    "    for i in range(1, len(x) + 1):\n",
    "        for j in range(1, len(y)+1):\n",
    "            common[i][j] = common[i-1][j-1] + 1 if x[i-1] == y[j-1] else 0\n",
    "            max_lcs = max(max_lcs, common[i][j])\n",
    "\n",
    "    return 1 - max_lcs/max(len(x), len(y))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "taken-penny",
   "metadata": {},
   "source": [
    "#### ngramy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "separate-accused",
   "metadata": {},
   "outputs": [],
   "source": [
    "def ngrams(x, n):\n",
    "    ngrams = [x[i:i+n] for i in range(len(x)-n+1)]\n",
    "    return Counter(ngrams)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "coastal-detector",
   "metadata": {},
   "source": [
    "* Sorensena-Dice'a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "august-producer",
   "metadata": {},
   "outputs": [],
   "source": [
    "def dice(x, y, n=2):\n",
    "    n = min([n, len(x), len(y)])\n",
    "    ngrams_x, ngrams_y = set(ngrams(x, n).keys()), set(ngrams(y, n).keys())\n",
    "    return 1 - 2*len(ngrams_x & ngrams_y)/(len(ngrams_x)+len(ngrams_y))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "private-oklahoma",
   "metadata": {},
   "source": [
    "* euklidesowa"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "naughty-feature",
   "metadata": {},
   "outputs": [],
   "source": [
    "def euclides(x, y, n=2):\n",
    "    n = min([n, len(x), len(y)])\n",
    "    ngrams_x, ngrams_y = ngrams(x, n), ngrams(y, n)\n",
    "\n",
    "    keys = set(ngrams_x.keys()) | set(ngrams_y.keys())\n",
    "    dist = sum((ngrams_x.get(key, 0) - ngrams_y.get(key, 0))**2 for key in keys) \n",
    "    len_x = sum(count**2 for key, count in ngrams_x.items())\n",
    "    len_y = sum(count**2 for key, count in ngrams_y.items())\n",
    "\n",
    "    return (dist/(len_x + len_y))**0.5"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "durable-increase",
   "metadata": {},
   "source": [
    "* cosinusowa"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "artificial-wireless",
   "metadata": {},
   "outputs": [],
   "source": [
    "def cosine(x, y, n=2):\n",
    "    n = min([n, len(x), len(y)])\n",
    "    ngrams_x, ngrams_y = ngrams(x, n), ngrams(y, n)\n",
    "    dot = lambda n_x, n_y: sum(n_x[key]*n_y[key] for key in n_x.keys() & n_y.keys())\n",
    "    return 1 - dot(ngrams_x, ngrams_y)/(dot(ngrams_x, ngrams_x)\n",
    "                                        *dot(ngrams_y, ngrams_y))**0.5"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "crucial-circuit",
   "metadata": {},
   "source": [
    "* Levenshteina"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "pointed-witness",
   "metadata": {},
   "outputs": [],
   "source": [
    "def levenshtein(x, y):\n",
    "    edit = [[max(i, j) for i in range(len(y) + 1)]\n",
    "            for j in range(len(x) + 1)]\n",
    "\n",
    "    def delta(char_a, char_b): \n",
    "        return 0 if char_a == char_b else 1\n",
    "    \n",
    "    for i in range(1, len(x)+1):\n",
    "        for j in range(1, len(y)+1):\n",
    "            edit[i][j] = min(edit[i-1][j] + 1, edit[i][j-1] + 1,\n",
    "                       edit[i-1][j-1] + delta(x[i-1], y[j-1]))\n",
    "\n",
    "    return edit[len(x)][len(y)]/max(len(x), len(y))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "pleasant-contrast",
   "metadata": {},
   "source": [
    "#### test metryk"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "daily-grenada",
   "metadata": {},
   "source": [
    "Poniżej znajduję wartości poszczególnych metryk w trzech przypadkach dobranych tekstów. \n",
    "\n",
    "Wartości dla poszczególnych metryk często różnią się między sobą, jednak funkcje zostały zaimplementowane w taki sposób, aby wartości te były mniej więcej porównywalne. Dlatego w przypadku metryki Levenshteina odległość edycyjną dzielę przez maksymalną długość obydwu tekstów, natomiast odległość euklidesową znormalizowałem przez pierwiastek sumy kwadratów długości wektorów otrzymanych z liczby wystąpień poszczególnych ngramów. Dzięki temu dla każdej z metryk spełniony jest fakt, iż przyjmuje ona wartość 0 dla tożsamych napisów oraz wartość 1 dla zupełnie różniących się (w rozumieniu danej metryki)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "selected-transsexual",
   "metadata": {},
   "source": [
    "* podobne napisy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "ranging-mississippi",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "lcs:  0.5\n",
      "dice:  0.5\n",
      "euclides:  0.7071067811865476\n",
      "cosine:  0.4836022205056778\n",
      "levenshtein:  0.3333333333333333\n"
     ]
    }
   ],
   "source": [
    "x = 'BCDF'\n",
    "y = 'ABCDEF'\n",
    "\n",
    "print('lcs: ', lcs(x, y))\n",
    "print('dice: ', dice(x, y))\n",
    "print('euclides: ', euclides(x, y))\n",
    "print('cosine: ', cosine(x, y))\n",
    "print('levenshtein: ', levenshtein(x, y))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "available-boundary",
   "metadata": {},
   "source": [
    "* napisy zupełnie różne"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "driving-alcohol",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "lcs:  1.0\n",
      "dice:  1.0\n",
      "euclides:  1.0\n",
      "cosine:  1.0\n",
      "levenshtein:  1.0\n"
     ]
    }
   ],
   "source": [
    "x = 'BCDF'\n",
    "y = 'A'\n",
    "\n",
    "print('lcs: ', lcs(x, y))\n",
    "print('dice: ', dice(x, y))\n",
    "print('euclides: ', euclides(x, y))\n",
    "print('cosine: ', cosine(x, y))\n",
    "print('levenshtein: ', levenshtein(x, y))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "durable-madagascar",
   "metadata": {},
   "source": [
    "* napisy tożsame"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "ready-pitch",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "lcs:  0.0\n",
      "dice:  0.0\n",
      "euclides:  0.0\n",
      "cosine:  0.0\n",
      "levenshtein:  0.0\n"
     ]
    }
   ],
   "source": [
    "x = 'BCDF'\n",
    "y = 'BCDF'\n",
    "\n",
    "print('lcs: ', lcs(x, y))\n",
    "print('dice: ', dice(x, y))\n",
    "print('euclides: ', euclides(x, y))\n",
    "print('cosine: ', cosine(x, y))\n",
    "print('levenshtein: ', levenshtein(x, y))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "explicit-soldier",
   "metadata": {},
   "source": [
    "## 2. Sposoby oceny jakości klasteryzacji"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "postal-spare",
   "metadata": {},
   "source": [
    "<i>Zaimplementuj przynajmniej 2 sposoby oceny jakości klasteryzacji (np. indeks Daviesa-Bouldina).</i>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "descending-agency",
   "metadata": {},
   "source": [
    "* indeks Daviesa-Bouldina"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "facial-field",
   "metadata": {},
   "outputs": [],
   "source": [
    "def average_distance_in_cluster(cluster, metric):\n",
    "    sum_ = 0\n",
    "    n = len(cluster)\n",
    "    if n == 1: return 0\n",
    "    \n",
    "    for i, text_i in enumerate(cluster):\n",
    "        for text_j in cluster[i+1:]:\n",
    "                sum_ += metric(text_i, text_j)\n",
    "                \n",
    "    return sum_ /(n*(n-1)/2)\n",
    "\n",
    "def cluster_distance(cluster_a, cluster_b, metric):\n",
    "    sum_ = 0\n",
    "    \n",
    "    return sum(metric(text_a, text_b) \n",
    "               for text_a in cluster_a \n",
    "               for text_b in cluster_b)/(len(cluster_a)\n",
    "                                         *len(cluster_b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "discrete-reynolds",
   "metadata": {},
   "outputs": [],
   "source": [
    "def davies_bouldin(clusters, metric):\n",
    "    index = 0\n",
    "    sigmas = [average_distance_in_cluster(cluster, metric) for cluster in clusters]\n",
    "    \n",
    "    for i, cluster_i in enumerate(clusters):\n",
    "        max_ = 0\n",
    "        for j, cluster_j in enumerate(clusters):\n",
    "            if i == j: continue\n",
    "            max_ = max(max_, (sigmas[i] + sigmas[j])/cluster_distance(cluster_i, cluster_j, metric))\n",
    "        index += max_\n",
    "        \n",
    "    return index/len(clusters)        "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "played-tradition",
   "metadata": {},
   "source": [
    "* indeks Dunna"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "absent-wisdom",
   "metadata": {},
   "outputs": [],
   "source": [
    "def cluster_size(cluster, metric):\n",
    "    if len(cluster) == 1: return 0\n",
    "    return max(metric(text_i, text_j) for i, text_i in enumerate(cluster) for text_j in cluster[i+1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "medical-import",
   "metadata": {},
   "outputs": [],
   "source": [
    "def dunn(clusters, metric):\n",
    "    min_dist = min(cluster_distance(cluster_a, cluster_b, metric)\n",
    "                   for i, cluster_a in enumerate(clusters)\n",
    "                   for cluster_b in clusters[i+1:])\n",
    "    max_size = max(cluster_size(cluster, metric)\n",
    "                    for cluster in clusters)\n",
    "    \n",
    "    if max_size == 0: \n",
    "        return inf\n",
    "    \n",
    "    return min_dist/max_size"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "unique-interview",
   "metadata": {},
   "source": [
    "#### test indeksów"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "designed-liverpool",
   "metadata": {},
   "source": [
    "* odległe klastry"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "vital-burner",
   "metadata": {},
   "outputs": [],
   "source": [
    "clusters = [[\"AB\", \"CD\"], [\"xy\", \"wt\"]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "future-serbia",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\tdavies-bouldin index:  2.0\n",
      "\t          dunn index:  1.0\n"
     ]
    }
   ],
   "source": [
    "print('\\tdavies-bouldin index: ', davies_bouldin(clusters, cosine))\n",
    "print('\\t          dunn index: ', dunn(clusters, cosine))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dress-fundamentals",
   "metadata": {},
   "source": [
    "* bliskie klastry"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "surface-ribbon",
   "metadata": {},
   "outputs": [],
   "source": [
    "clusters = [[\"AB\", \"CD\"], [\"ABc\", \"CDe\"]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "minimal-spiritual",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\tdavies-bouldin index:  3.0938363213560542\n",
      "\t          dunn index:  0.6464466094067263\n"
     ]
    }
   ],
   "source": [
    "print('\\tdavies-bouldin index: ', davies_bouldin(clusters, cosine))\n",
    "print('\\t          dunn index: ', dunn(clusters, cosine))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "tired-campbell",
   "metadata": {},
   "source": [
    "* odległe elementy w klastrze"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "cardiovascular-disabled",
   "metadata": {},
   "outputs": [],
   "source": [
    "clusters = [[\"ABC\", \"XYZ\"], [\"abc\", \"xyz\"]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "appropriate-crack",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\tdavies-bouldin index:  2.0\n",
      "\t          dunn index:  1.0\n"
     ]
    }
   ],
   "source": [
    "print('\\tdavies-bouldin index: ', davies_bouldin(clusters, cosine))\n",
    "print('\\t          dunn index: ', dunn(clusters, cosine))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "motivated-outline",
   "metadata": {},
   "source": [
    "* bliskie elementy w klastrze"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "individual-preference",
   "metadata": {},
   "outputs": [],
   "source": [
    "clusters = [[\"ABCE\", \"ABCD\"], [\"abce\", \"abce\"]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "limiting-consent",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\tdavies-bouldin index:  0.33333333333333337\n",
      "\t          dunn index:  2.9999999999999996\n"
     ]
    }
   ],
   "source": [
    "print('\\tdavies-bouldin index: ', davies_bouldin(clusters, cosine))\n",
    "print('\\t          dunn index: ', dunn(clusters, cosine))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "seeing-waterproof",
   "metadata": {},
   "source": [
    "Z powyższych testów możemy zauważyć, iż im większa wartość indeksu Dunna tym lepsza jakość klasteryzacji, natomiast w przypadku indeksu Daviesa-Bouldina lepsza jest mniejsza wartość.\n",
    "\n",
    "Klasteryzacja jest uznawana za lepszą, gdy elementy w poszczególnych klastrach są blisko siebie, a za to klastry daleko od siebie nawzajem."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "listed-daughter",
   "metadata": {},
   "source": [
    "## 3. Stoplista"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "soviet-blowing",
   "metadata": {},
   "source": [
    "<i> Stwórz stoplistę najczęściej występujących słów. </i>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "wrong-somalia",
   "metadata": {},
   "source": [
    "Stoplistę tworzę dzieląc linijki na słowa, a następnie znajdując najczęściej powtarzające się słowa we wszystkich linijkach."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "meaningful-escape",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_stop_words(lines, min_count):\n",
    "    word_count = Counter(word for line in lines for word in line.replace('.', ' ').split(' '))\n",
    "    word_count = list(word_count.items())\n",
    "    word_count.sort(key=lambda x: x[1], reverse=True)\n",
    "    return [word for word, count in word_count if count >= min_count]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "contemporary-colon",
   "metadata": {},
   "outputs": [],
   "source": [
    "def remove_common(lines, min_count):\n",
    "    stop_list = get_stop_words(lines, min_count)\n",
    "    return [' '.join([word for word in line.split(' ') if word not in stop_list]) for line in lines], stop_list"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dental-secretary",
   "metadata": {},
   "source": [
    "## 4. Klasteryzacja"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "accepted-adapter",
   "metadata": {},
   "source": [
    "<i> Wykonaj klasteryzację zawartości załączonego pliku (lines.txt) przy użyciu metryk zaimplementowanych w pkt. 1. i metryki Levenshteina. Każda linia to adres pocztowy firmy, różne sposoby zapisu tego samego adresu powinny się znaleźć w jednym klastrze. </i>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "systematic-leisure",
   "metadata": {},
   "source": [
    "Do klasteryzacji używam funkcji DBSCAN z biblioteki sklearn.cluster."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "younger-climb",
   "metadata": {},
   "outputs": [],
   "source": [
    "def cluster(lines, metric, eps=0.86):\n",
    "    distances = [[metric(line_a, line_b) for line_a in lines] for line_b in lines]\n",
    "    clustering = sklearn.cluster.DBSCAN(eps=eps, min_samples=1).fit(distances)\n",
    "    return clustering.labels_"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "otherwise-mills",
   "metadata": {},
   "source": [
    "## 5. Testy"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "applied-night",
   "metadata": {},
   "source": [
    "<i> Porównaj jakość wyników sposobami zaimplementowanymi w pkt. 2. </i>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ordered-flooring",
   "metadata": {},
   "source": [
    "#### odczytanie danych testowych"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "controlled-fence",
   "metadata": {},
   "source": [
    "Z uwagi na duży czas działania programu, korzystam tylko ze 100 linijek. Dzięki temu najwolniejsze metody (lcs, levenshtein) nie działają dłużej niż parę minut."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "horizontal-marshall",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_example_lines(num):\n",
    "    with open('lines.txt', 'r') as file:\n",
    "        lines = list(file)\n",
    "        \n",
    "    lines = lines[:num]\n",
    "\n",
    "    with open('clusters.txt', 'r') as file:\n",
    "        clusters = list(file)\n",
    "    \n",
    "    correct_clustering = []\n",
    "    cluster_num = 0\n",
    "    \n",
    "    for line in lines:\n",
    "        cluster = 0\n",
    "        for cluster_line in clusters:\n",
    "            if cluster_line[0] == '#':\n",
    "                cluster += 1\n",
    "            elif cluster_line == line:\n",
    "                correct_clustering.append(cluster)\n",
    "                break\n",
    "    \n",
    "    return lines, np.array(correct_clustering)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "advised-recruitment",
   "metadata": {},
   "outputs": [],
   "source": [
    "lines, correct_labels = get_example_lines(100)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "similar-capital",
   "metadata": {},
   "source": [
    "#### testy krok po kroku"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "increasing-annex",
   "metadata": {},
   "source": [
    "* klasteryzacja - znalezienie listy z indeksami klastrów poszczególnych linii danych:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "wound-annex",
   "metadata": {},
   "outputs": [],
   "source": [
    "labels = cluster(lines, cosine)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "quality-clinton",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 0  1  2  2  3  4  5  6  7  8  9 10 11 11 11 11 11 11 11 12 12 13 14 15\n",
      " 16 17 18 19 19 20 21 22 23 23 24 25 26 27 17 28 29 30 31 32 33 34 35 36\n",
      " 37 37 17 38 38 38 39 40 39 40 41 41 41 41 41 41 11 11 11 42 42 42 43 44\n",
      " 45 46 47 48 49 50 51 15 52 52 17 53 53 54 17 55  2 17 56 57 17 58 59 58\n",
      " 60 60 60 60]\n"
     ]
    }
   ],
   "source": [
    "print(labels)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "animal-thompson",
   "metadata": {},
   "source": [
    "Dla porównania wypisuję poprawne przyporządkowanie linijek na podstawie załączonego pliku (wartości mogą się różnić, ważna jest równość etykiet poszczególnych elementów)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "hundred-portsmouth",
   "metadata": {},
   "outputs": [],
   "source": [
    "def renumber_labels(labels):\n",
    "    seen = {}\n",
    "    current = 0\n",
    "    new_labels = []\n",
    "    for label in labels:\n",
    "        if label in seen:\n",
    "            new_labels.append(seen[label])\n",
    "        else:\n",
    "            new_labels.append(current)\n",
    "            seen[label] = current\n",
    "            current += 1\n",
    "    \n",
    "    return np.array(new_labels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "negative-completion",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 0  1  2  2  3  4  5  6  7  8  9 10 11 11 11 11 11 11 11 12 12 13 14 14\n",
      " 15 16 17 18 18 19 20 21 22 22 23 24 25 26 27 28 29 29 30 31 32 33 34 35\n",
      " 36 36 37 38 38 38 39 39 39 39 40 40 40 40 40 40 41 41 41 42 42 42 43 44\n",
      " 45 46 47 48 49 50 51 52 53 54 55 56 56 57 58 59  2 60 61 62 63 64 63 64\n",
      " 65 65 65 65]\n"
     ]
    }
   ],
   "source": [
    "print(renumber_labels(correct_labels))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "talented-pipeline",
   "metadata": {},
   "source": [
    "* podzielenie linijek na klastry na podstawie etykiet"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "occupied-nebraska",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_clusters_from_labels(lines, labels):\n",
    "    clusters = {}\n",
    "    for i, label in enumerate(labels):\n",
    "        clusters[label] = clusters.get(label, []) + [lines[i]]\n",
    "        \n",
    "    return list(clusters.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "anonymous-mention",
   "metadata": {},
   "outputs": [],
   "source": [
    "clusters = get_clusters_from_labels(lines, labels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "canadian-advance",
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_clustering(clusters):\n",
    "    for cluster in clusters:\n",
    "        print('##########')\n",
    "        for line in cluster:\n",
    "            print(line)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "nonprofit-examination",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "##########\n",
      "/11692589 RD TUNA CANNERS, LTD. PORTION 1004, SIAR NORTH COAST ROAD, P.O.BOX 2113, MADANG, PAPUA NEW GUINEA\n",
      "\n",
      "##########\n",
      "''PA INTERIOR'' LTD BOLSHAYA LUBYANKA STREET, 16/4 MOSCOW, 101000, RUSSIA INN/KPP 7704550148//770801001 495-984-8611\n",
      "\n",
      "##########\n",
      "''SSONTEX''  Sp.ZO.O.IMPORT-EXPORTUL:PRZECLAWSKA 5 03-879 WARSZAWA,POLAND NIP 113-01-17-669\n",
      "\n",
      "''SSONTEX''SP.ZO.O.IMPORT-EXPORT UL:PRZECLAWSKA 5 03-879 WARSZAWA,POLAND NIP 113-01-17-669 TEL./FAX.:0048(022)217 6532--\n",
      "\n",
      "\"SSONTEX\" SP.ZO.O IMPORT-EXPORT 03-879 WARSZAWA UL PRZECLAWSKA 5 NIP:113-01-17-669\n",
      "\n",
      "##########\n",
      "''TOPEX SP. Z O.O.'' SPOLKA KOMANDYTOWA UL. POGRANICZNA 2/4  02-285 WARSZAWA POLAND\n",
      "\n",
      "##########\n",
      "'MASTER PLUS CO.,LTD.' 143000,RUSSIA,MO,ODINSOVO, MOJAISKOE, SHOSSE,153G TEL:+7495 7273939\n",
      "\n",
      "##########\n",
      "\"2TIGERS GROUP LIMITED\"  ROOM 504 JINSHAZHOU SHANGSHUI ROAD,  GUANGZHOU 510160\n",
      "\n",
      "##########\n",
      "\"ALDETRANS\" LLC, 105066, MOSCOW, RUSSIA, TOKMAKOV LANE, 11. TEL:+7(495)641-03-89\n",
      "\n",
      "##########\n",
      "\"A-LIFT\",JSC 1 PROSPEKT MARSHALA ZHUKOVA,MOSCOW 123308,RUSSIA  T: +7(495)784-7961\n",
      "\n",
      "##########\n",
      "\"ALISA\" LTD, 1/5 Derbenevskaya str., Moscow, Russia Tel./Fax: (495) 987-13-07 postal code: 115114\n",
      "\n",
      "##########\n",
      "\"ALLIANCE-TRADE\" LLC INN: 7816391055 / KPP: 784601001 190020, Saint Petersburg, quay of the Obvodny channel, 138, bulk 1, liter.B\n",
      "\n",
      "##########\n",
      "\"ALTAIR\" LIMITED COMPANY 199004,SAINT-PETERSBURG, 1 LINE,H.20 LIT A,OF.8-H\n",
      "\n",
      "##########\n",
      "\"ARIVIST\", 198035,RUSSIA,SAINT-PETERSBURG, GAPSALSKAYA STR.,5,OFFICE 1-3; TEL:+78123277732,FAX:+781 23277729.VOLOKNO@YAHOO.COM\n",
      "\n",
      "\"ARIVIST\", 198035,RUSSIA,SAINT-PETERSBURG, GAPSALSKAYA STR.,5,OFFICE 1-3; TEL.:+78123277732,FAX+ 78123277729.\n",
      "\n",
      "\"ARIVIST\", 198035,RUSSIA,SAINT-PETERSBURG,  GAPSALSKAYA STR.,5,OFFICE1-3; TEL.:+78123277732,FAX+ 78123277729.\n",
      "\n",
      "\"ARIVIST\", 198035,RUSSIA,SAINT-PETERSBURG,  GAPSALSKAYA STR.,5,OFFICE1-3; TEL.:+78123277732,FAX + 78123277729.\n",
      "\n",
      "\"ARIVIST\", 198035, RUSSIA,  SAINT-PETERSBURG,  GAPSALSKAYA STR.,5,OFFICE1-3;  TEL.+78123277732, FAX  +78123277729.\n",
      "\n",
      "\"ARIVIST\", 198035, RUSSIA, SAINT-PETERSBURG, GAPSALSKAYA STR.,5, OFFICE1-3; TEL.+78123277732, FAX +78123277729. VOLOKNO@YAHOO.COM\n",
      "\n",
      "\"ARIVIST\", 198035, RUSSIA, SAINT-PETERSBURG. GAPSALSKAYA STR.,5. OFFICE1-3; TEL.+78123277732, FAX+78123277729. VOLOKNO@YAHOO.COM\n",
      "\n",
      "\"NFC\" LTD GAPSALSKAYA STR., 5 198035 ST. PETERSBURG, RUSSIA TEL: +7 812 327 77 41  FAX: +7 812 327 77 29\n",
      "\n",
      "\"NFC\"LTD GAPSALSKAYA STR., 5 198035ST.PETERSBURG,RUSSIA TEL.+78123277741 FAX +78123277729\n",
      "\n",
      "\"NFC\" LTD GAPSALSKAYA STR., 5 198035 ST.PETERSBURG, RUSSIA TEL. +7 812327 77 41 FAX +7 812 327 77 29\n",
      "\n",
      "##########\n",
      "\"AVANPORT\"  LLC INN: 7839413675 KPP: 783901001 190020, SAINT PETERSBURG, QUAY OF THE OBVODNY CHANNEL, 134-136-138, BUILD. 101, LIT. A\"\n",
      "\n",
      "\"AVANPORT\"  LLC INN: 7839413675 KPP: 783901001 190020, SAINT PETERSBURG, QUAY OF  THE OBVODNY CHANNEL,134-136-138,  BUILD. 101, LIT. A\"\n",
      "\n",
      "##########\n",
      "\"AVENTA\"LTD. ADDRESS:129 110,MOSCOW,PROSPEKT MIRA,H.52,STR.3,POM,III Tel: 8-968-808-80-11\n",
      "\n",
      "##########\n",
      "\"AVSON-GROUP\" COMPANY LIMITED 190008, ST. PETERSBURG,  RIMSKOGO-KORSAKOVA,  73/33, LIT. A-1\n",
      "\n",
      "##########\n",
      "\"Avson-group\" Company Limited  190008, St. Petersburg, Rimskogo-Korsakova, 73/33, lit. A-1\n",
      "\n",
      "\"Rimal\" LTD \"Grazdansky prospect, 22.  St. Petersburg, 195220,  Russian Federation\"\n",
      "\n",
      "##########\n",
      "\"BIO plus LTD\" INN 7805166210 198303, S-Petersburg, Leninskiy Pr.,110/1, lit B, app.53-H, RUSSIA\n",
      "\n",
      "##########\n",
      "\"CARGOIMPORT\" LTD VNUKOVSKAYA STREET, BUILDING 2, R.43-H-1, SAINT-PETERSBURG, RUSSIA .\n",
      "\n",
      "\"FMG SHIPPING AND FORWARDING, LTD.\"190020 ST.PETERSBURG, RUSSIA BUMAZHNAYA STR., 18, OFF. 310\n",
      "\n",
      "\"KONTUR\" LLC STR. SHPALERNAYA 51, LIT. A, APP. 2-N 191015 ST. PETERSBURG, RUSSIA INN 7842437789\n",
      "\n",
      "\"SERVICE-EXPRESS\" LTD 197110, RUSSIA, SAINT-PETERSBURG, GLUHAYA ZELENINA STREET,H.4, LIT B,OFFICE 19-H\n",
      "\n",
      "\"SILMET\" COMPANY LIMITED 196084, RUSSIA, ST.PETERSBURG, ZAOZERNAYA STR., 4. LETTER A, 9H. TEL /FAX: 7 812334 35 74\n",
      "\n",
      "\"STEP TRADE\" LLC KUBINSKAYA ST., 38, BUILDING A, ROOM 4-H,ST.PETERSBURG, 196247, RUSSIAN FEDERATION\n",
      "\n",
      "\"SUNTIRE\" CO. LTD, M. BALKANSKAYA STREET, 58, LIT.A 192289, ST.-PETERSBURG, RUSSIA\n",
      "\n",
      "##########\n",
      "\"COLOS\"COMPLEX LOGISTICS,SOLUTIONSPIOTR KACZMAREK I PAWEL WILK SP.J.ZACHODNIA STREET NO 3 55-011 SIECHNICE POLAND\n",
      "\n",
      "##########\n",
      "\"ELECTROGROUP\" (OOO),190068.RUSSIA,SAINT-PETERSBURG,UL.BOLSHAYA PODYACHESKAYA,5,LIT.A,POM.4-N\n",
      "\n",
      "\"ELECTROGROUP\" (OOO),190068.RUSSIA,SAINT-PETERSBURG,UL.BOLSHAYA  PODYACHESKAYA,5,LIT.A,POM.4-N\n",
      "\n",
      "##########\n",
      "\"ELEKTROAPPARAT\" PLC   24th LiniyaV.O.,St.Petersburg. Sup.office No.1of Kirovsky RUSSIA TEL: 0079-219646264\n",
      "\n",
      "##########\n",
      "\"ENS\" LTD ADDRESS: STAROPETROVSKIYPASSAGE, BLD 7A,  CONSTRUCTION 3 125130, MOSCOW, RUSSIA TEL: (499) 130-7336\n",
      "\n",
      "##########\n",
      "\"EVROTRANSIT\" LLC 105005, RUSSIAN FEDERATION, MOSCOW, BAUMANSKAYA STR., 33/2, BLD.1 E-MAIL:EVROTRANZIT-LOGL@INBOX.RU TEL:8-495-665-34-68\n",
      "\n",
      "##########\n",
      "\"EXPRESS CO. LTD.\" RUSSIA 155101 IVANOVSKAYA REGION, LEZHNEVSKIY RAION, D. KOROVIHA, CENTRALNAYA STR. 4ARUSSIA\n",
      "\n",
      "\"EXPRESS CO. LTD.\"  RUSSIA 155101 IVANOVSKAYA REGION, LEZHNEVSKIY RAION, D. KOROVIHA, CENTRALNAYA STR. 4ARUSSIA\n",
      "\n",
      "##########\n",
      "\"FILITA\" LTD, UKRAINE, 83004, DONETSK, ARTEMA STR. 193G    TEL/FAX:+380563705563\n",
      "\n",
      "##########\n",
      "\"FILLOGISTIK\" PP ZHOVKIVSKA 22 STREET 79019 LVOV,UKRAINE TEL:+380322458030 FAX:+380322458030\n",
      "\n",
      "##########\n",
      "\"FINANS AKTIV\",LTD. 111250,RUSSIA,MOSCOW, KRASNOKAZARMENNAYA STR.11+7495 665 6001\n",
      "\n",
      "##########\n",
      "\"FMG SHIPPING AND FORWARDING, LTD.\"190020, SAINT PETERSBURG,LIFLYANDSKAYA STR., 6,LITERA \"A\",BUILDING 31H,OFFICE 310 POST CODE:190020 TEL:+7 812 448 82 83 FAX:+7 812 448 04 9\n",
      "\n",
      "##########\n",
      "\"FORWARD EXPEDITION LIMITED HKG\" SUCCES COMM.BLDG.,6B,251, HENNESSY ROAD, HONGKONG ARRIVAL@FORWARD-HKG.COM\n",
      "\n",
      "##########\n",
      "\"FRUITIMPEX\" LLC 121170, Moscow, Russia, Kulneva st, 3 bld. 1 INN 7737514219 KPP773001001\n",
      "\n",
      "##########\n",
      "\"FRUITIMPEX\" LLC TEL. (495) 926-74-49\n",
      "\n",
      "##########\n",
      "\"FT-LINE\"LLC RUSSIA 115230,MOSCOW,ELECTROLYTNIY PROEZD,3G/2 TEL:+79851607522\n",
      "\n",
      "##########\n",
      "\"GARANTTRANS SERVICE\" MOSCOW,RUSSIAUl.GILYAROVSKOGO,57.OFFICE 514 TEL:(495) 748 02 87 FAX:(495) 684 12 01\n",
      "\n",
      "##########\n",
      "\"Goldens\" LLC\n",
      "\n",
      "##########\n",
      "\"INTERLINK LTD SP ZOO UI.  POMORSKA50A 81-314 GDYNIA BIELSKA@INTERLINK.BIZ.PL SIEJKOWSKA@INTERLINK.BIZ.PL...+++\n",
      "\n",
      "##########\n",
      "\"INTERTRANS\" CO LTD. ST.PETERSBURG,198035,RUSSIA GAPSALSKAIA STREET,OFFICE 502, TEL 3242144, FAX:3242145\n",
      "\n",
      "##########\n",
      "\"KM\" LTD 197183 RUSSIA,ST. PETERSBURG,SABIROVSKAYA STR.,50,OFF,115 OLEG TEREKHOV ZIP CODE:197183 PHONE:7911239-3109  FAX:7911239-3109\n",
      "\n",
      "##########\n",
      "\"KOBI-LIGHT\" SPOLKA KOMANDYTOWA UL.T.BOYA ZELENSKIEGO 25 35-105 RZESZOW,POLAND NIP:813-34-99-669\n",
      "\n",
      "\"KOBI-LIGHT\" SPOLKA KOMANDYTOWA UL.T.BOYA ZELENSKIEGO 25 35-105 RZESZOW,POLAND NIP:813-34-99-699\n",
      "\n",
      "##########\n",
      "\"LIGA-IMPORT\" LTD DOROGA NA TURUHTANNIE OSTROVA, D.24, KORP.5, SAINT-PETERSBURG, 198096, RUSSIA\n",
      "\n",
      "\"LIGA-IMPORT\" LTD DOROGA NA TURUHTANNIE OSTROVA, D.24, KORP.5, SAINT-PETERSBURG, 198096, RUSSIA TEL/FAX:+7 (911) 812 89 88\n",
      "\n",
      "\"LIGA-IMPORT\" LTD DOROGA NA TURUHTANNIE OSTROVA, D. 24, KORP. 5, SAINT-PETERSBURG, 198096, RUSSIA TEL/FAX:+7 (911) 812 89 88\n",
      "\n",
      "##########\n",
      "\"LTC SOLUTION OY\" FINLAND, HAMINA 49420, PILARITIE 2 ON BEHALF \"AETZ REKORD\" CO., LTD 2, GAGARINA STR., ALEXANDROV,--\n",
      "\n",
      "\"LTC SOLUTION OY\" FINLAND, HAMINA 49420, SYVASATAMANTIE 18 ON BEHALF \"AETZ REKORD\" CO., LTD--\n",
      "\n",
      "##########\n",
      "\"LTC SOLUTION OY\" FINLAND, HAMINA 49420, PILARITIE 2 TEL. +358 (0) 522-66-130 FAX: +358 (0) 522-66-120\n",
      "\n",
      "\"LTC SOLUTION OY\" FINLAND, HAMINA 49420, SYVASATAMANTIE 18 TEL. +358 (0) 522-66-130 FAX: +358 (0) 522-66-120\n",
      "\n",
      "##########\n",
      "\"MEAT TRADE COMPANY \"ST.PETERSBURG\"LTD.  191015 SAINT-PETERSBURG, SHPALERNAYA STREET, 51 RUSSIAN FEDERATION\n",
      "\n",
      "\"MEAT TRADE COMPANY \"ST.PETERSBURG\"LTD. 191015 SAINT-PETERSBURG,  SHPALERNAYA STREET, 51 RUSSIAN FEDERATION TEL +7 (812) 329-42-62 PYLAEVATATIANA\n",
      "\n",
      "\"MEAT TRADE COMPANY \"ST.PETERSBURG\"LTD 191015 SAINT-PETERSBURG, SHPALERNAYA STREET, 51 RUSSIAN FEDERATION\n",
      "\n",
      "\"MEAT TRADE COMPANY \"ST.PETERSBURG\"LTD 191015 SAINT-PETERSBURG, SHPALERNAYA STREET, 51 RUSSIAN FEDERATION INN 7842339206\n",
      "\n",
      "\"MEAT TRADE COMPANY \"ST.PETERSBURG\"LTD 191015 SAINT-PETERSBURG, SHPALERNAYA STREET, 51 RUSSIAN FEDERATION TEL +7 (812) 329-42-62 PASHKEVICHANNA\n",
      "\n",
      "\"MEAT TRADE COMPANY \"ST.PETERSBURG\"LTD 191015 SAINT-PETERSBURG, SHPALERNAYA STREET, 51 RUSSIAN FEDERATION TEL +7 (812) 329-42-62 PYLAEVA TATIANA\n",
      "\n",
      "##########\n",
      "\"OCEAN WORLD\" LLC 198099 RUSSIA, ST.PETERSBURG KALININ STREET, 57, LIT.A, OF.307 LEDENEVA ELENA. TEL./FAX.+7-812-336-65-88\n",
      "\n",
      "\"OCEAN WORLD\" LLC KALININ STREET, 57, LIT. A, OFFICE 307, ST. PETERSBURG, RUSSIA, 198099 LEDENEVA ELENA.TEL./FAX.+7-812-336-65-88\n",
      "\n",
      "\"OCEAN WORLD\" LLC LIT A, OF 307, 57KALININ STREET ST PETERSBURG 198099, RUSSIA MERKOVA MARIYA TEL/FAX: +7-812-336-65-88\n",
      "\n",
      "##########\n",
      "\"OMEGA TOYS GRUP\"CO.,LTD. AVTOZAVODSKAY STR.23,STRUCTURE 8 MOSCOW,RUSSIAN FEDERATION,P.O.X:115280 TEL/FAX:+7-495-674-60-62 TITARENKO ALEXANDR E-mail serinity-toys@mail.ru INN\n",
      "\n",
      "##########\n",
      "\"OOO\" BALTIYSKIY EKSPEDITOR\" EUGENIY KOMRAKOV (812) 676-16-03\"\n",
      "\n",
      "##########\n",
      "\"OOO\" TECHNOLINE\" 191123,ST.-PETERSBURG,UL. FURSCHTATSKAYA 48,LITER A\"\n",
      "\n",
      "##########\n",
      "\"OTL\" LLC KOROTIN@OTLSPB.RU TEL: +7(812) 326-42-52 VIP 13171-1 ST.PETERSBURG\n",
      "\n",
      "##########\n",
      "\"OY VAER LOG LTD\"  Y-TUNNUS:2066533-3  Adres: Merituulentie, 424  48310, Kotka  TEL: +358 5 21 21 33  Fax: +358 5 21 21 30  Vanhala Olga  Ershova Ekaterina\n",
      "\n",
      "##########\n",
      "\"PARTNER\" LTD INN/KPP 7801080258/780101001 POM/1-N, HOUSE 1-2, 1-LINE;V. 0. , ST. PETERSBURG, 199053, RUSSIA TEL. : +7 812 600 20 22 FAX: +7 812 600 20 33\n",
      "\n",
      "##########\n",
      "\"PETERSBURG CHEMICAL COMPANY\" COMPANY LIMITED(<<PCC>>CO.,LTD.) 197374,RUSSIAN FEDERATION,SAINT PETERSBURG,TORFYANAYA ROAD, 7,LIT.F OFFICE 925.\n",
      "\n",
      "##########\n",
      "\"PO\"SVET \"LTD PODREZOVA STR.,16,LIT.A,ROOM 5-H 197136 SAINT-PETERSBURG,RUSSIA. ITN 7813445827 TEL:+7-812-716-21-76\n",
      "\n",
      "##########\n",
      "\"PRANT\" LLC 603159 RUSSIA, NIZHNY NOVGOROD AKIMOVA-STR. 41, SUITE 63 INN 5257120394 KPP 525701001 TEL/FAX. +7 (831) 423-45-33\n",
      "\n",
      "##########\n",
      "\"SAME AS CONSIGNEE\"\n",
      "\n",
      "\"SAME AS CONSIGNEE\"  AS AGENT OF BLUE ANCHOR LINE\n",
      "\n",
      "##########\n",
      "\"SEVROLL-SYSTEM\" SP.Z O.O. PLAC CZERWCA 1976 ROKU NR 1B  02-495 WARSZAWA URSUS  TEL: (022) 312-31-39\n",
      "\n",
      "\"SEVROLL-SYSTEM\" SP.Z O.O. PLAC CZERWCA 1976 ROKU NR 1B  02-495 WARSZAWA URSUS   TEL: (022) 312-31-39\n",
      "\n",
      "##########\n",
      "\"SHIP-MASTER DELTA\"LLC RIGSKY PR.,19,SAINT-PETERSBURG, 190103,RUSSIA TEL:+7(812)251-81-11; +7(812)575-33-38;+7(812)251-73-03 FAX: +7 (812) 575-33-40\n",
      "\n",
      "##########\n",
      "\"Spike Rus\" Limited Liability Company, The Yakovlevskyi per., H.8 a of. 5-n, 196105 S.Petersburg, Russia.TEL: 007-812-476-15-62 FAX: 007-812-476-15-62\n",
      "\n",
      "##########\n",
      "\"STEVECO OY\" STEVECO LOGISTICS MERITUULENTIE 424 48310 KOTKA, FONLANDPIC: ANNE LEPPANEN\n",
      "\n",
      "##########\n",
      "\"STUDIO MODERNA\" UL. PERERVA 54 109369 MOSCOW RUSSIA\n",
      "\n",
      "##########\n",
      "\"SUNTIRE\" CO. LTD. TEL.: + 7 (812)458 54 38 E-MAIL: CLIENT@S-LOGISTIC.RU\n",
      "\n",
      "\"SUNTIRE\"CO.LTD TEL:+7(812)458 54 38 E-MAIL:CLIENT@S-LOGISTIC.RU\n",
      "\n",
      "##########\n",
      "\"SUNTIRE\"CO.LTD M.BALKANSKAYA STREET,58,LIT.A 192289,ST.PETERSBURG,RUSSIA\n",
      "\n",
      "##########\n",
      "\"TC \"\"UNOTRANS\"\" LTD\" \"190020 ST.PETERSBURG,\" \"BUMAZHNAYA STR.9, K.1,OFFICE 305\" \"TEL/FAX: +7 812 445 2843\"\n",
      "\n",
      "\"TC\"UNOTRANS\"LTD 190020 ST.PETERSBURG,BUMAZHNAYA STR.9,K.1,OFF.305 TEL/FAX:+7 812 445 28 43\n",
      "\n",
      "\"TC\"UNOTRANS\"LTD 190020 ST.PETERSBURG, BUMAZHNAYA STR.9,K.1,OFF.305 TEL/FAX:+7 812 445 28 43\n",
      "\n",
      "\"TC \"UNOTRANS\" LTD 190020 ST.PETERSBURG, BUMAZHNAYA STR.9, K.1, OFF. 305 TEL/FAX: +7 812 445 28 43\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print_clustering(clusters)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dynamic-census",
   "metadata": {},
   "source": [
    "* ocena klasteryzacji, znalezienie wartości obydwu indeksów"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "arabic-copper",
   "metadata": {},
   "source": [
    "dla znalezionych klastrów:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "alternate-ordinance",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\tdavies-bouldin index:  0.7477794160582196\n",
      "\t          dunn index:  0.7400810281179782\n"
     ]
    }
   ],
   "source": [
    "print('\\tdavies-bouldin index: ', davies_bouldin(clusters, cosine))\n",
    "print('\\t          dunn index: ', dunn(clusters, cosine))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "hispanic-today",
   "metadata": {},
   "source": [
    "dla poprawnych klastrów:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "pacific-enterprise",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\tdavies-bouldin index:  0.9600618831700587\n",
      "\t          dunn index:  0.4148461875933154\n"
     ]
    }
   ],
   "source": [
    "correct_clusters = get_clusters_from_labels(lines, correct_labels)\n",
    "print('\\tdavies-bouldin index: ', davies_bouldin(correct_clusters, cosine))\n",
    "print('\\t          dunn index: ', dunn(correct_clusters, cosine))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "thrown-translator",
   "metadata": {},
   "source": [
    "Poprawna klasteryzacja ma gorsze wartości indeksów niż uzyskana. Może to oznaczać, iż użyta metryka nie najlepiej opisuje podobieństwo powiązanych linijek."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "satisfactory-ability",
   "metadata": {},
   "source": [
    "#### wersja z zastosowaniem stoplisty "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "split-cemetery",
   "metadata": {},
   "source": [
    "* usunięcie słów ze stoplisty"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "varied-territory",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "removed words:  ['', 'STR', 'LTD', 'TEL', 'ST', 'RUSSIA', ',', 'LLC', 'SAINT-PETERSBURG,', 'PETERSBURG,', '812', '+7', 'O', 'STREET,', 'COMPANY', 'LIT', 'GAPSALSKAYA', 'RUSSIA,', '5', 'CO', 'TEL:', 'RUSSIAN']\n"
     ]
    }
   ],
   "source": [
    "lines_stop, common_words = remove_common(lines, 8)\n",
    "print('removed words: ', common_words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "urban-upgrade",
   "metadata": {},
   "outputs": [],
   "source": [
    "def show_differences(lines, lines_stop):\n",
    "    for line, line_stop in zip(lines, lines_stop):\n",
    "        if line != line_stop:\n",
    "            print(line)\n",
    "            print(line_stop, '\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "alpha-software",
   "metadata": {},
   "source": [
    "* klasteryzacja"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "commercial-cloud",
   "metadata": {},
   "outputs": [],
   "source": [
    "labels = cluster(lines_stop, cosine)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "taken-number",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 0  1  2  2  3  4  5  6  7  8  9 10 11 11 11 11 11 11 11 12 12 13 14 15\n",
      " 16 17 18 19 19 20 21 22 23 23 24 25 26 27 27 28 29 30 31 32 33 34 35 36\n",
      " 37 37 38 39 39 39 40 41 40 41 42 42 42 42 42 42 43 11 11 44 44 44 45 46\n",
      " 47 48 49 50 51 52 53 54 55 55 56 57 57 58 59 60  2 61 62 63 64 65 66 65\n",
      " 67 67 67 67]\n"
     ]
    }
   ],
   "source": [
    "print(labels)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "taken-miller",
   "metadata": {},
   "source": [
    "* podzielenie linijek na klastry w postaci zbiorów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "willing-sodium",
   "metadata": {},
   "outputs": [],
   "source": [
    "clusters = get_clusters_from_labels(lines_stop, labels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "chief-visiting",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_clusters_from_labels(lines, labels):\n",
    "    clusters = {}\n",
    "    for i, label in enumerate(labels):\n",
    "        clusters[label] = clusters.get(label, []) + [lines[i]]\n",
    "        \n",
    "    return list(clusters.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "modified-shift",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "##########\n",
      "/11692589 RD TUNA CANNERS, LTD. PORTION 1004, SIAR NORTH COAST ROAD, P.O.BOX 2113, MADANG, PAPUA NEW GUINEA\n",
      "\n",
      "##########\n",
      "''PA INTERIOR'' BOLSHAYA LUBYANKA 16/4 MOSCOW, 101000, INN/KPP 7704550148//770801001 495-984-8611\n",
      "\n",
      "##########\n",
      "''SSONTEX'' Sp.ZO.O.IMPORT-EXPORTUL:PRZECLAWSKA 03-879 WARSZAWA,POLAND NIP 113-01-17-669\n",
      "\n",
      "''SSONTEX''SP.ZO.O.IMPORT-EXPORT UL:PRZECLAWSKA 03-879 WARSZAWA,POLAND NIP 113-01-17-669 TEL./FAX.:0048(022)217 6532--\n",
      "\n",
      "\"SSONTEX\" SP.ZO.O IMPORT-EXPORT 03-879 WARSZAWA UL PRZECLAWSKA NIP:113-01-17-669\n",
      "\n",
      "##########\n",
      "''TOPEX SP. Z O.O.'' SPOLKA KOMANDYTOWA UL. POGRANICZNA 2/4 02-285 WARSZAWA POLAND\n",
      "\n",
      "##########\n",
      "'MASTER PLUS CO.,LTD.' 143000,RUSSIA,MO,ODINSOVO, MOJAISKOE, SHOSSE,153G TEL:+7495 7273939\n",
      "\n",
      "##########\n",
      "\"2TIGERS GROUP LIMITED\" ROOM 504 JINSHAZHOU SHANGSHUI ROAD, GUANGZHOU 510160\n",
      "\n",
      "##########\n",
      "\"ALDETRANS\" LLC, 105066, MOSCOW, TOKMAKOV LANE, 11. TEL:+7(495)641-03-89\n",
      "\n",
      "##########\n",
      "\"A-LIFT\",JSC 1 PROSPEKT MARSHALA ZHUKOVA,MOSCOW 123308,RUSSIA T: +7(495)784-7961\n",
      "\n",
      "##########\n",
      "\"ALISA\" LTD, 1/5 Derbenevskaya str., Moscow, Russia Tel./Fax: (495) 987-13-07 postal code: 115114\n",
      "\n",
      "##########\n",
      "\"ALLIANCE-TRADE\" INN: 7816391055 / KPP: 784601001 190020, Saint Petersburg, quay of the Obvodny channel, 138, bulk 1, liter.B\n",
      "\n",
      "##########\n",
      "\"ALTAIR\" LIMITED 199004,SAINT-PETERSBURG, 1 LINE,H.20 A,OF.8-H\n",
      "\n",
      "##########\n",
      "\"ARIVIST\", 198035,RUSSIA,SAINT-PETERSBURG, STR.,5,OFFICE 1-3; TEL:+78123277732,FAX:+781 23277729.VOLOKNO@YAHOO.COM\n",
      "\n",
      "\"ARIVIST\", 198035,RUSSIA,SAINT-PETERSBURG, STR.,5,OFFICE 1-3; TEL.:+78123277732,FAX+ 78123277729.\n",
      "\n",
      "\"ARIVIST\", 198035,RUSSIA,SAINT-PETERSBURG, STR.,5,OFFICE1-3; TEL.:+78123277732,FAX+ 78123277729.\n",
      "\n",
      "\"ARIVIST\", 198035,RUSSIA,SAINT-PETERSBURG, STR.,5,OFFICE1-3; TEL.:+78123277732,FAX + 78123277729.\n",
      "\n",
      "\"ARIVIST\", 198035, STR.,5,OFFICE1-3; TEL.+78123277732, FAX +78123277729.\n",
      "\n",
      "\"ARIVIST\", 198035, STR.,5, OFFICE1-3; TEL.+78123277732, FAX +78123277729. VOLOKNO@YAHOO.COM\n",
      "\n",
      "\"ARIVIST\", 198035, SAINT-PETERSBURG. STR.,5. OFFICE1-3; TEL.+78123277732, FAX+78123277729. VOLOKNO@YAHOO.COM\n",
      "\n",
      "\"NFC\"LTD STR., 198035ST.PETERSBURG,RUSSIA TEL.+78123277741 FAX +78123277729\n",
      "\n",
      "\"NFC\" STR., 198035 ST.PETERSBURG, TEL. 812327 77 41 FAX 327 77 29\n",
      "\n",
      "##########\n",
      "\"AVANPORT\" INN: 7839413675 KPP: 783901001 190020, SAINT QUAY OF THE OBVODNY CHANNEL, 134-136-138, BUILD. 101, LIT. A\"\n",
      "\n",
      "\"AVANPORT\" INN: 7839413675 KPP: 783901001 190020, SAINT QUAY OF THE OBVODNY CHANNEL,134-136-138, BUILD. 101, LIT. A\"\n",
      "\n",
      "##########\n",
      "\"AVENTA\"LTD. ADDRESS:129 110,MOSCOW,PROSPEKT MIRA,H.52,STR.3,POM,III Tel: 8-968-808-80-11\n",
      "\n",
      "##########\n",
      "\"AVSON-GROUP\" LIMITED 190008, ST. RIMSKOGO-KORSAKOVA, 73/33, LIT. A-1\n",
      "\n",
      "##########\n",
      "\"Avson-group\" Company Limited 190008, St. Petersburg, Rimskogo-Korsakova, 73/33, lit. A-1\n",
      "\n",
      "##########\n",
      "\"BIO plus LTD\" INN 7805166210 198303, S-Petersburg, Leninskiy Pr.,110/1, lit B, app.53-H, RUSSIA\n",
      "\n",
      "##########\n",
      "\"CARGOIMPORT\" VNUKOVSKAYA BUILDING 2, R.43-H-1, .\n",
      "\n",
      "##########\n",
      "\"COLOS\"COMPLEX LOGISTICS,SOLUTIONSPIOTR KACZMAREK I PAWEL WILK SP.J.ZACHODNIA STREET NO 3 55-011 SIECHNICE POLAND\n",
      "\n",
      "##########\n",
      "\"ELECTROGROUP\" (OOO),190068.RUSSIA,SAINT-PETERSBURG,UL.BOLSHAYA PODYACHESKAYA,5,LIT.A,POM.4-N\n",
      "\n",
      "\"ELECTROGROUP\" (OOO),190068.RUSSIA,SAINT-PETERSBURG,UL.BOLSHAYA PODYACHESKAYA,5,LIT.A,POM.4-N\n",
      "\n",
      "##########\n",
      "\"ELEKTROAPPARAT\" PLC 24th LiniyaV.O.,St.Petersburg. Sup.office No.1of Kirovsky 0079-219646264\n",
      "\n",
      "##########\n",
      "\"ENS\" ADDRESS: STAROPETROVSKIYPASSAGE, BLD 7A, CONSTRUCTION 3 125130, MOSCOW, (499) 130-7336\n",
      "\n",
      "##########\n",
      "\"EVROTRANSIT\" 105005, FEDERATION, MOSCOW, BAUMANSKAYA STR., 33/2, BLD.1 E-MAIL:EVROTRANZIT-LOGL@INBOX.RU TEL:8-495-665-34-68\n",
      "\n",
      "##########\n",
      "\"EXPRESS CO. LTD.\" 155101 IVANOVSKAYA REGION, LEZHNEVSKIY RAION, D. KOROVIHA, CENTRALNAYA STR. 4ARUSSIA\n",
      "\n",
      "\"EXPRESS CO. LTD.\" 155101 IVANOVSKAYA REGION, LEZHNEVSKIY RAION, D. KOROVIHA, CENTRALNAYA STR. 4ARUSSIA\n",
      "\n",
      "##########\n",
      "\"FILITA\" LTD, UKRAINE, 83004, DONETSK, ARTEMA STR. 193G TEL/FAX:+380563705563\n",
      "\n",
      "##########\n",
      "\"FILLOGISTIK\" PP ZHOVKIVSKA 22 STREET 79019 LVOV,UKRAINE TEL:+380322458030 FAX:+380322458030\n",
      "\n",
      "##########\n",
      "\"FINANS AKTIV\",LTD. 111250,RUSSIA,MOSCOW, KRASNOKAZARMENNAYA STR.11+7495 665 6001\n",
      "\n",
      "##########\n",
      "\"FMG SHIPPING AND FORWARDING, LTD.\"190020, SAINT PETERSBURG,LIFLYANDSKAYA STR., 6,LITERA \"A\",BUILDING 31H,OFFICE 310 POST CODE:190020 TEL:+7 448 82 83 FAX:+7 448 04 9\n",
      "\n",
      "\"FMG SHIPPING AND FORWARDING, LTD.\"190020 ST.PETERSBURG, BUMAZHNAYA STR., 18, OFF. 310\n",
      "\n",
      "##########\n",
      "\"FORWARD EXPEDITION LIMITED HKG\" SUCCES COMM.BLDG.,6B,251, HENNESSY ROAD, HONGKONG ARRIVAL@FORWARD-HKG.COM\n",
      "\n",
      "##########\n",
      "\"FRUITIMPEX\" 121170, Moscow, Russia, Kulneva st, 3 bld. 1 INN 7737514219 KPP773001001\n",
      "\n",
      "##########\n",
      "\"FRUITIMPEX\" TEL. (495) 926-74-49\n",
      "\n",
      "##########\n",
      "\"FT-LINE\"LLC 115230,MOSCOW,ELECTROLYTNIY PROEZD,3G/2 TEL:+79851607522\n",
      "\n",
      "##########\n",
      "\"GARANTTRANS SERVICE\" MOSCOW,RUSSIAUl.GILYAROVSKOGO,57.OFFICE 514 TEL:(495) 748 02 87 FAX:(495) 684 12 01\n",
      "\n",
      "##########\n",
      "\"Goldens\" LLC\n",
      "\n",
      "##########\n",
      "\"INTERLINK SP ZOO UI. POMORSKA50A 81-314 GDYNIA BIELSKA@INTERLINK.BIZ.PL SIEJKOWSKA@INTERLINK.BIZ.PL...+++\n",
      "\n",
      "##########\n",
      "\"INTERTRANS\" LTD. ST.PETERSBURG,198035,RUSSIA GAPSALSKAIA STREET,OFFICE 502, 3242144, FAX:3242145\n",
      "\n",
      "##########\n",
      "\"KM\" 197183 RUSSIA,ST. PETERSBURG,SABIROVSKAYA STR.,50,OFF,115 OLEG TEREKHOV ZIP CODE:197183 PHONE:7911239-3109 FAX:7911239-3109\n",
      "\n",
      "##########\n",
      "\"KOBI-LIGHT\" SPOLKA KOMANDYTOWA UL.T.BOYA ZELENSKIEGO 25 35-105 RZESZOW,POLAND NIP:813-34-99-669\n",
      "\n",
      "\"KOBI-LIGHT\" SPOLKA KOMANDYTOWA UL.T.BOYA ZELENSKIEGO 25 35-105 RZESZOW,POLAND NIP:813-34-99-699\n",
      "\n",
      "##########\n",
      "\"KONTUR\" STR. SHPALERNAYA 51, LIT. A, APP. 2-N 191015 ST. INN 7842437789\n",
      "\n",
      "##########\n",
      "\"LIGA-IMPORT\" DOROGA NA TURUHTANNIE OSTROVA, D.24, KORP.5, 198096, RUSSIA\n",
      "\n",
      "\"LIGA-IMPORT\" DOROGA NA TURUHTANNIE OSTROVA, D.24, KORP.5, 198096, TEL/FAX:+7 (911) 89 88\n",
      "\n",
      "\"LIGA-IMPORT\" DOROGA NA TURUHTANNIE OSTROVA, D. 24, KORP. 5, 198096, TEL/FAX:+7 (911) 89 88\n",
      "\n",
      "##########\n",
      "\"LTC SOLUTION OY\" FINLAND, HAMINA 49420, PILARITIE 2 ON BEHALF \"AETZ REKORD\" CO., 2, GAGARINA STR., ALEXANDROV,--\n",
      "\n",
      "\"LTC SOLUTION OY\" FINLAND, HAMINA 49420, SYVASATAMANTIE 18 ON BEHALF \"AETZ REKORD\" CO., LTD--\n",
      "\n",
      "##########\n",
      "\"LTC SOLUTION OY\" FINLAND, HAMINA 49420, PILARITIE 2 TEL. +358 (0) 522-66-130 FAX: +358 (0) 522-66-120\n",
      "\n",
      "\"LTC SOLUTION OY\" FINLAND, HAMINA 49420, SYVASATAMANTIE 18 TEL. +358 (0) 522-66-130 FAX: +358 (0) 522-66-120\n",
      "\n",
      "##########\n",
      "\"MEAT TRADE \"ST.PETERSBURG\"LTD. 191015 SHPALERNAYA 51 FEDERATION\n",
      "\n",
      "\"MEAT TRADE \"ST.PETERSBURG\"LTD. 191015 SHPALERNAYA 51 FEDERATION (812) 329-42-62 PYLAEVATATIANA\n",
      "\n",
      "\"MEAT TRADE \"ST.PETERSBURG\"LTD 191015 SHPALERNAYA 51 FEDERATION\n",
      "\n",
      "\"MEAT TRADE \"ST.PETERSBURG\"LTD 191015 SHPALERNAYA 51 FEDERATION INN 7842339206\n",
      "\n",
      "\"MEAT TRADE \"ST.PETERSBURG\"LTD 191015 SHPALERNAYA 51 FEDERATION (812) 329-42-62 PASHKEVICHANNA\n",
      "\n",
      "\"MEAT TRADE \"ST.PETERSBURG\"LTD 191015 SHPALERNAYA 51 FEDERATION (812) 329-42-62 PYLAEVA TATIANA\n",
      "\n",
      "##########\n",
      "\"NFC\" STR., 198035 ST. 327 77 41 FAX: 327 77 29\n",
      "\n",
      "##########\n",
      "\"OCEAN WORLD\" 198099 ST.PETERSBURG KALININ 57, LIT.A, OF.307 LEDENEVA ELENA. TEL./FAX.+7-812-336-65-88\n",
      "\n",
      "\"OCEAN WORLD\" KALININ 57, LIT. A, OFFICE 307, ST. 198099 LEDENEVA ELENA.TEL./FAX.+7-812-336-65-88\n",
      "\n",
      "\"OCEAN WORLD\" A, OF 307, 57KALININ STREET PETERSBURG 198099, MERKOVA MARIYA TEL/FAX: +7-812-336-65-88\n",
      "\n",
      "##########\n",
      "\"OMEGA TOYS GRUP\"CO.,LTD. AVTOZAVODSKAY STR.23,STRUCTURE 8 MOSCOW,RUSSIAN FEDERATION,P.O.X:115280 TEL/FAX:+7-495-674-60-62 TITARENKO ALEXANDR E-mail serinity-toys@mail.ru INN\n",
      "\n",
      "##########\n",
      "\"OOO\" BALTIYSKIY EKSPEDITOR\" EUGENIY KOMRAKOV (812) 676-16-03\"\n",
      "\n",
      "##########\n",
      "\"OOO\" TECHNOLINE\" 191123,ST.-PETERSBURG,UL. FURSCHTATSKAYA 48,LITER A\"\n",
      "\n",
      "##########\n",
      "\"OTL\" KOROTIN@OTLSPB.RU +7(812) 326-42-52 VIP 13171-1 ST.PETERSBURG\n",
      "\n",
      "##########\n",
      "\"OY VAER LOG LTD\" Y-TUNNUS:2066533-3 Adres: Merituulentie, 424 48310, Kotka +358 21 21 33 Fax: +358 21 21 30 Vanhala Olga Ershova Ekaterina\n",
      "\n",
      "##########\n",
      "\"PARTNER\" INN/KPP 7801080258/780101001 POM/1-N, HOUSE 1-2, 1-LINE;V. 0. ST. 199053, TEL. : 600 20 22 FAX: 600 20 33\n",
      "\n",
      "##########\n",
      "\"PETERSBURG CHEMICAL COMPANY\" LIMITED(<<PCC>>CO.,LTD.) 197374,RUSSIAN FEDERATION,SAINT PETERSBURG,TORFYANAYA ROAD, 7,LIT.F OFFICE 925.\n",
      "\n",
      "##########\n",
      "\"PO\"SVET \"LTD PODREZOVA STR.,16,LIT.A,ROOM 5-H 197136 SAINT-PETERSBURG,RUSSIA. ITN 7813445827 TEL:+7-812-716-21-76\n",
      "\n",
      "##########\n",
      "\"PRANT\" 603159 NIZHNY NOVGOROD AKIMOVA-STR. 41, SUITE 63 INN 5257120394 KPP 525701001 TEL/FAX. (831) 423-45-33\n",
      "\n",
      "##########\n",
      "\"Rimal\" \"Grazdansky prospect, 22. St. Petersburg, 195220, Russian Federation\"\n",
      "\n",
      "##########\n",
      "\"SAME AS CONSIGNEE\"\n",
      "\n",
      "\"SAME AS CONSIGNEE\" AS AGENT OF BLUE ANCHOR LINE\n",
      "\n",
      "##########\n",
      "\"SERVICE-EXPRESS\" 197110, GLUHAYA ZELENINA STREET,H.4, B,OFFICE 19-H\n",
      "\n",
      "##########\n",
      "\"SEVROLL-SYSTEM\" SP.Z O.O. PLAC CZERWCA 1976 ROKU NR 1B 02-495 WARSZAWA URSUS (022) 312-31-39\n",
      "\n",
      "\"SEVROLL-SYSTEM\" SP.Z O.O. PLAC CZERWCA 1976 ROKU NR 1B 02-495 WARSZAWA URSUS (022) 312-31-39\n",
      "\n",
      "##########\n",
      "\"SHIP-MASTER DELTA\"LLC RIGSKY PR.,19,SAINT-PETERSBURG, 190103,RUSSIA TEL:+7(812)251-81-11; +7(812)575-33-38;+7(812)251-73-03 FAX: (812) 575-33-40\n",
      "\n",
      "##########\n",
      "\"SILMET\" LIMITED 196084, ST.PETERSBURG, ZAOZERNAYA STR., 4. LETTER A, 9H. /FAX: 7 812334 35 74\n",
      "\n",
      "##########\n",
      "\"Spike Rus\" Limited Liability Company, The Yakovlevskyi per., H.8 a of. 5-n, 196105 S.Petersburg, Russia.TEL: 007-812-476-15-62 FAX: 007-812-476-15-62\n",
      "\n",
      "##########\n",
      "\"STEP TRADE\" KUBINSKAYA ST., 38, BUILDING A, ROOM 4-H,ST.PETERSBURG, 196247, FEDERATION\n",
      "\n",
      "##########\n",
      "\"STEVECO OY\" STEVECO LOGISTICS MERITUULENTIE 424 48310 KOTKA, FONLANDPIC: ANNE LEPPANEN\n",
      "\n",
      "##########\n",
      "\"STUDIO MODERNA\" UL. PERERVA 54 109369 MOSCOW RUSSIA\n",
      "\n",
      "##########\n",
      "\"SUNTIRE\" CO. LTD, M. BALKANSKAYA 58, LIT.A 192289, ST.-PETERSBURG, RUSSIA\n",
      "\n",
      "##########\n",
      "\"SUNTIRE\" CO. LTD. TEL.: + 7 (812)458 54 38 E-MAIL: CLIENT@S-LOGISTIC.RU\n",
      "\n",
      "\"SUNTIRE\"CO.LTD TEL:+7(812)458 54 38 E-MAIL:CLIENT@S-LOGISTIC.RU\n",
      "\n",
      "##########\n",
      "\"SUNTIRE\"CO.LTD M.BALKANSKAYA STREET,58,LIT.A 192289,ST.PETERSBURG,RUSSIA\n",
      "\n",
      "##########\n",
      "\"TC \"\"UNOTRANS\"\" LTD\" \"190020 ST.PETERSBURG,\" \"BUMAZHNAYA STR.9, K.1,OFFICE 305\" \"TEL/FAX: 445 2843\"\n",
      "\n",
      "\"TC\"UNOTRANS\"LTD 190020 ST.PETERSBURG,BUMAZHNAYA STR.9,K.1,OFF.305 TEL/FAX:+7 445 28 43\n",
      "\n",
      "\"TC\"UNOTRANS\"LTD 190020 ST.PETERSBURG, BUMAZHNAYA STR.9,K.1,OFF.305 TEL/FAX:+7 445 28 43\n",
      "\n",
      "\"TC \"UNOTRANS\" 190020 ST.PETERSBURG, BUMAZHNAYA STR.9, K.1, OFF. 305 TEL/FAX: 445 28 43\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print_clustering(clusters)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dirty-yemen",
   "metadata": {},
   "source": [
    "* ocena klasteryzacji, znalezienie wartości obydwu indeksów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "eleven-perception",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\tdavies-bouldin index:  0.4823673943365842\n",
      "\t          dunn index:  0.5312993284234436\n"
     ]
    }
   ],
   "source": [
    "print('\\tdavies-bouldin index: ', davies_bouldin(clusters, cosine))\n",
    "print('\\t          dunn index: ', dunn(clusters, cosine))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "relevant-evidence",
   "metadata": {},
   "source": [
    "W tym przypadku, nie możemy jednoznacznie stwierdzić, czy usunięcie niektórych słów poprawiło jakość klasteryzacji."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "compatible-aberdeen",
   "metadata": {},
   "source": [
    "#### porównanie wyników dla różnych metryk"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "paperback-permit",
   "metadata": {},
   "outputs": [],
   "source": [
    "def test(lines, metric):\n",
    "    print(metric.__name__)\n",
    "    labels = cluster(lines, metric)\n",
    "    clusters = get_clusters_from_labels(lines, labels)\n",
    "    \n",
    "    davies_index = davies_bouldin(clusters, metric)\n",
    "    dunn_index = dunn(clusters, metric)\n",
    "    print('\\tdavies-bouldin index: ', davies_index)\n",
    "    print('\\t          dunn index: ', dunn_index)\n",
    "    \n",
    "    return davies_index, dunn_index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "instrumental-float",
   "metadata": {},
   "outputs": [],
   "source": [
    "def compare_metrics(lines, metrics):\n",
    "    davies_indices = []\n",
    "    dunn_indices = []\n",
    "    \n",
    "    for metric in metrics:\n",
    "        davies, dunn = test(lines, metric)\n",
    "        davies_indices.append(davies)\n",
    "        dunn_indices.append(dunn)\n",
    "        \n",
    "    print('\\n\\n---with stoplist---')\n",
    "    lines_stop, _ = remove_common(lines, 8)\n",
    "    for metric in metrics:\n",
    "        davies, dunn = test(lines_stop, metric)\n",
    "        davies_indices.append(davies)\n",
    "        dunn_indices.append(dunn)\n",
    "    \n",
    "    return davies_indices, dunn_indices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "blessed-silver",
   "metadata": {},
   "outputs": [],
   "source": [
    "metrics = [dice, cosine, euclides, levenshtein, lcs]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "governmental-reaction",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "dice\n",
      "\tdavies-bouldin index:  0.7667990839471491\n",
      "\t          dunn index:  0.7613930140572199\n",
      "cosine\n",
      "\tdavies-bouldin index:  0.7477794160582196\n",
      "\t          dunn index:  0.7400810281179782\n",
      "euclides\n",
      "\tdavies-bouldin index:  0.5997238554017978\n",
      "\t          dunn index:  0.9426037036635696\n",
      "levenshtein\n",
      "\tdavies-bouldin index:  0.6107574836919204\n",
      "\t          dunn index:  0.857097238804556\n",
      "lcs\n",
      "\tdavies-bouldin index:  0.6480094789187549\n",
      "\t          dunn index:  0.8795031055900621\n",
      "\n",
      "\n",
      "---with stoplist---\n",
      "dice\n",
      "\tdavies-bouldin index:  0.5832760255640013\n",
      "\t          dunn index:  0.8548269230769229\n",
      "cosine\n",
      "\tdavies-bouldin index:  0.4823673943365842\n",
      "\t          dunn index:  0.5312993284234436\n",
      "euclides\n",
      "\tdavies-bouldin index:  0.632246911690487\n",
      "\t          dunn index:  0.8688212214193677\n",
      "levenshtein\n",
      "\tdavies-bouldin index:  0.6251224709456794\n",
      "\t          dunn index:  0.8809980082085949\n",
      "lcs\n",
      "\tdavies-bouldin index:  0.7106617779346485\n",
      "\t          dunn index:  0.8041425525434055\n"
     ]
    }
   ],
   "source": [
    "davies_indices, dunn_indices = compare_metrics(lines, metrics)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "turkish-resort",
   "metadata": {},
   "source": [
    "* wzorcowa klasteryzacja z pliku"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "dried-possession",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_indices_correct_clustering(lines, correct_labels, metrics):\n",
    "    correct_clusters = get_clusters_from_labels(lines, correct_labels)\n",
    "    correct_davies = []\n",
    "    correct_dunn = []\n",
    "    \n",
    "    for metric in metrics:\n",
    "        davies_index = davies_bouldin(correct_clusters, metric)\n",
    "        dunn_index = dunn(correct_clusters, metric)\n",
    "        print(metric.__name__)\n",
    "        print('\\tdavies-bouldin index: ', davies_index)\n",
    "        print('\\t          dunn index: ', dunn_index)\n",
    "        correct_davies.append(davies_index)\n",
    "        correct_dunn.append(dunn_index)\n",
    "    \n",
    "    return correct_davies, correct_dunn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "italic-leadership",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "dice\n",
      "\tdavies-bouldin index:  0.8892659116999325\n",
      "\t          dunn index:  0.5504428023309978\n",
      "cosine\n",
      "\tdavies-bouldin index:  0.9600618831700587\n",
      "\t          dunn index:  0.4148461875933154\n",
      "euclides\n",
      "\tdavies-bouldin index:  1.0630485855555134\n",
      "\t          dunn index:  0.6972860692469977\n",
      "levenshtein\n",
      "\tdavies-bouldin index:  0.947804783049698\n",
      "\t          dunn index:  0.6948018528049409\n",
      "lcs\n",
      "\tdavies-bouldin index:  1.0905759199429839\n",
      "\t          dunn index:  0.695609756097561\n"
     ]
    }
   ],
   "source": [
    "correct_davies, correct_dunn = get_indices_correct_clustering(lines, correct_labels, metrics)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "harmful-prefix",
   "metadata": {},
   "source": [
    "* wykres"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "united-voice",
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_comparison(metrics, davies_indices, dunn_indices, correct_davies, correct_dunn):\n",
    "    fig, ax = plt.subplots(1, 2, figsize=(15,8))\n",
    "    \n",
    "    metric_names = list(map(lambda x: x.__name__, metrics))\n",
    "    \n",
    "    x = np.arange(len(metrics))\n",
    "    width = 0.3\n",
    "    \n",
    "    ax[0].bar(x-width, davies_indices[:len(metrics)], color='coral', width=width, label='dbscam clustering')\n",
    "    ax[0].bar(x, davies_indices[len(metrics):], color='orange', width=width, label='dbscan with stoplist')\n",
    "    ax[0].bar(x+width, correct_davies, color='goldenrod', width=width, label='correct labels from the file')\n",
    "    \n",
    "    ax[1].bar(x-width, dunn_indices[:len(metrics)], color='royalblue', width=width, label='dbscan clustering')\n",
    "    ax[1].bar(x, dunn_indices[len(metrics):], color='cornflowerblue', width=width, label='dbscan with stoplist')\n",
    "    ax[1].bar(x+width, correct_dunn, color='cadetblue', width=width, label='correct labels from the file')\n",
    "    \n",
    "    ax[0].set_xticks(x)\n",
    "    ax[0].set_xticklabels(metric_names)\n",
    "    \n",
    "    ax[1].set_xticks(x)\n",
    "    ax[1].set_xticklabels(metric_names)\n",
    "    \n",
    "    ax[0].legend()\n",
    "    ax[1].legend()\n",
    "    ax[0].set_title('Davies-Bouldin')\n",
    "    ax[1].set_title('Dunn')\n",
    "    \n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "quality-theorem",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAA2oAAAHiCAYAAACZVz+XAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8QVMy6AAAACXBIWXMAAAsTAAALEwEAmpwYAAA/SklEQVR4nO3deXRV9b3//+ebWQWxSmytiGAvWoaQgEFFxAEnRMWhOOBQ0VavUqW/ekul1aVea3vx6q2tVrRalWpVFL9VqaVXa8GKQ5XBoIIgoCioVwEFwQEBP78/ziENkEAIGXbI87FWlufs/clnv8/mmPd6nT2cSCkhSZIkScqOJvVdgCRJkiRpfQY1SZIkScoYg5okSZIkZYxBTZIkSZIyxqAmSZIkSRljUJMkSZKkjDGoSZWIiJURsVd911FVEfF0RHy/knUdIyJFRLP8879GxDl1W6EkSZKqyqCmBi0iFkTE5xGxIiKWRcTzEXFhRGz1ezul1Dql9GZN1LlOuXpXRsTHEfGXiNijJrdRFSmlY1JKf6jr7UqStm212Zelxsb/abQtOD6l1AbYExgFXAbcWb8lbdLxKaXWwG7AB8DN9VyPJEk1qaH1ZSmTDGraZqSUlqeUxgOnAedERPeIODYiXo6ITyJiYURcvW58/vS/i8vPEREzIuLk/OMUEf+Wf9wyIm6IiHci4oOIuC0itsuvaxcRj+c/OfwoIiZX5ZPDlNIXwMNA13LbbxsR90TE4oh4OyKuWDdXRFwdEX8sN3a90xk3eB1N8/UuiYg3gWM3WF92mmREDI2IZ/PjP46ItyLimM3VL0nSplTSl9c7TX9dDyr3POWPwM3N99VbIiLKj7VfqbEwqGmbk1J6CVgE9AM+Bb4L7EQurFwUESfmhz4ADFn3exHRldynf3+pYNpRwN5AMfBvwO7Alfl1/5HfXgHwdeBnQNpcnRGxPbnm9c9yi28G2gJ7AYfkaz93c3NV4HzgOKAnUAIM3sz4/YE5QDvgv4E71zVGSZK2xgZ9uSqOA3oDPYBTgaPLrbNfqdEwqGlb9R6wc0rp6ZTSqymlr1JKr5ALZ4fkxzwCFEfEnvnnZwJ/SimtKj9RvgFcAPwopfRRSmkF8Evg9PyQ1eROY9wzpbQ6pTQ5pbSpoPZoRCwDlgNHAtfnt9M0P+dPU0orUkoLgP8Bzq7G6z8V+HVKaWFK6SPgvzYz/u2U0h0ppbXAH/Kv5+vV2K4kSRV5D9i5imNHpZSWpZTeASaR+5B0HfuVGg2DmrZVuwMfRcT+ETEpfyrhcuBCcp/CkQ9cf+FfgWsIcF8FcxUA2wPT8qdhLAP+N78cckFrHvBkRLwZESMBIuLM/E1DVkbEX8vNd2JKaSegFXAx8I+I+Ea+rubA2+XGvp1/LVvqm8DCDebZlP9b9yCl9Fn+YetqbFeSpIrsDnxUxbH/V+7xZ6zfj+xXajQMatrmRERvcg3hWeB+YDywR0qpLXAbUP4UiQeAIRHRh1xwmlTBlEuAz4FuKaWd8j9t8zcEIX/06z9SSnsBg4BLI+LwlNJ9+TtHtk4pbXQOfUppbUrpT8Ba4KD8dlaTO/1ynQ7Au/nHn5ILjOt8YxO74X2g/N0kO2xirCRJtWaDvrwlvUxq1Axq2mZExI4RcRwwFvhjSulVoA3wUUrpi4jYDzhjg1+bQC4YXQM8mFL6asN588vuAG6MiF3z29o9Io7OPz4uIv4tf4rkcnLBa6N5Kqg3IuIE4GvA6/nTOB4CfhERbfKnZF4KrLuBSClwcER0iIi2wE83Mf1DwPCIaB8RXwNGbq4eSZJqUiV9uRQ4OSK2z9+w63v1WaOUZQY1bQv+HBEryJ3qdznwK/51A45hwDX59VeSCzBl8tej/Qk4gtzRt8pcRu70xn9GxCfAU8A++XWd889XAi8Ao1NKFR2ZK1/vSuAT4BfAOSmlmfl1l5D7tPFN/nVE8K58rX8DHgReAaYBj29iG3cATwAzgOn51yhJUl3YVF++EfiS3NfT/IGKLzmQBMSm73kgSZIkSaprHlGTJEmSpIwxqEmSJElSxhjUJEmSJCljDGqSJEmSlDEGNUmSJEnKmGb1teF27dqljh071tfmJUl1aNq0aUtSSgX1XUdDYY+UpMZhU/2x3oJax44dmTp1an1tXpJUhyLi7fquoSGxR0pS47Cp/uipj5IkSZKUMQY1SZIkScoYg5okSZIkZUy9XaNWkdWrV7No0SK++OKL+i5FWk+rVq1o3749zZs3r+9SJDVS9khlkf1Rqj2ZCmqLFi2iTZs2dOzYkYio73IkAFJKLF26lEWLFtGpU6f6LkdSI2WPVNbYH6XalalTH7/44gt22WUXG5AyJSLYZZdd/BRbUr2yRypr7I9S7cpUUANsQMok35eSssC/Rcoa35NS7clcUMuSq6++mhtuuAGAQw89NPPfafP0009z3HHHVet3f/3rX/PZZ59t8e9deeWVPPXUU9XapiSp4WoIPbJ8jVti2bJljB49ulrbHDhwIMuWLavW70pSeZm6Rm0jV59Uw/M9UrPzbUN+/etfc9ZZZ7H99ttX+XfWrl3LNddcU4tVSZIq03/YOzU638TRHWp0voZsXVAbNmxYlX8npURKiQkTJtRiZZIaE4+obeAXv/gFe++9NwcddBBz5sxZb929995LcXEx3bt356WXXgLgH//4B8XFxRQXF9OzZ09WrFgBwHXXXUdhYSFFRUWMHDkSgDvuuIPevXtTVFTEd77znbIjWEOHDuWiiy7igAMOYK+99uLpp5/mvPPOo0uXLgwdOrTCOqdMmcKBBx5IUVER++23X9l219nwU8Tu3buzYMECPv30U4499liKioro3r07Dz74IDfddBPvvfcehx12GIcddhgATz75JH369KFXr16ccsoprFy5EoCOHTty2WWX0atXL8aNG8fQoUN5+OGHy9ZdddVV9OrVi8LCQmbPng3A4sWLOfLII+nWrRvf//732XPPPVmyZEm1/40kSfWjvnrk8OHDOfDAA9lrr73Kes6G7rnnHnr06EFRURFnn332RuvLH/VbsmQJHTt2BGDmzJnst99+FBcX06NHD+bOncvIkSOZP38+xcXFjBgxAoDrr7+e3r1706NHD6666ioAFixYwD777MN3v/tdunfvzsKFC+nYsSNLlixhwYIFdOnShfPPP59u3bpx1FFH8fnnnwO5Ht6jR4+y+bt3717tfxNJ2y6DWjnTpk1j7NixlJaWMmHCBKZMmbLe+s8++4zS0lJGjx7NeeedB8ANN9zALbfcQmlpKZMnT2a77bbjr3/9K4899hgvvvgiM2bM4Cc/+QkAJ598MlOmTGHGjBl06dKFO++8s2zujz/+mBdeeIEbb7yRQYMG8aMf/YiZM2fy6quvUlpaul4dX375Jaeddhq/+c1vmDFjBk899RTbbbddlV7j//7v//LNb36TGTNm8NprrzFgwACGDx/ON7/5TSZNmsSkSZNYsmQJ1157LU899RTTp0+npKSEX/3qV2Vz7LLLLkyfPp3TTz99o/nbtWvH9OnTueiii8qC4n/+53/Sv39/Zs6cyeDBg3nnnZr9FFiSVPvqs0e+//77PPvsszz++ONlwa68mTNncu211zJx4kRmzJjBb37zmyq/rttuu40f/vCHlJaWMnXqVNq3b8+oUaP41re+RWlpKddffz1PPvkkc+fO5aWXXqK0tJRp06bxzDPPADB37lyGDRvGzJkz2XPPPdebe+7cufzgBz9g5syZ7LTTTvy///f/ADj33HP53e9+R2lpKU2bNq1yrZIaF4NaOZMnT+akk05i++23Z8cdd2TQoEHrrR8yZAgABx98MJ988gnLli2jb9++XHrppdx0000sW7aMZs2a8dRTT3HuueeWnUa48847A/Daa6/Rr18/CgsLue+++5g5c2bZ3McffzwRQWFhIV//+tcpLCykSZMmdOvWjQULFqxXx5w5c9htt93o3bs3ADvuuCPNmlXtLNbCwkL+9re/cdlllzF58mTatm270Zh//vOfzJo1i759+1JcXMwf/vAH3n777bL1p512WqXzn3zyyQDsu+++ZXU/++yzZaFuwIABfO1rX6tSrZKk7KjPHnniiSfSpEkTunbtygcffLBRbRMnTuSUU06hXbt2681ZFX369OGXv/wl1113HW+//XaFH3w++eSTPPnkk/Ts2ZNevXoxe/Zs5s6dC8Cee+7JAQccUOHcnTp1ori4GPhXX1y2bBkrVqygT58+AJxxxhlVrlVS42JQ2wIb3tkoIhg5ciS///3v+fzzz+nbt2/Z6X4VGTp0KL/97W959dVXueqqq9a7nW3Lli0BaNKkSdnjdc/XrFmzxbU2a9aMr776quz5um3tvffeTJ8+ncLCQq644ooKrzFLKXHkkUdSWlpKaWkps2bNWu+TzR122KHS7a6rvWnTptWqW5LUMNVFj4Rcj6qO8n2x/NxnnHEG48ePZ7vttmPgwIFMnDhxo99NKfHTn/60rC/OmzeP733ve0DVeiLYFyVtOYNaOQcffDCPPvoon3/+OStWrODPf/7zeusffPBBIHeEqG3btrRt25b58+dTWFjIZZddRu/evZk9ezZHHnkkd999d9n59R999BEAK1asYLfddmP16tXcd9991a5zn3324f333y877WTFihUb/fHv2LEj06dPB2D69Om89dZbALz33ntsv/32nHXWWYwYMaJsTJs2bcquHTjggAN47rnnmDdvHgCffvopb7zxRrXr7du3Lw899BCQ+1Ty448/rvZckqT6keUe2b9/f8aNG8fSpUvXm7O8jh07Mm3aNID1rnN788032WuvvRg+fDgnnHACr7zyyno9EeDoo4/mrrvuKrte+9133+XDDz/cohrX2WmnnWjTpg0vvvgiAGPHjq3WPJK2fdm+62Md69WrF6eddhpFRUXsuuuuZacWrtOqVSt69uzJ6tWrueuuu4Dc3RInTZpUdpriMcccQ8uWLSktLaWkpIQWLVowcOBAfvnLX/Lzn/+c/fffn4KCAvbff/+NbgBSVS1atODBBx/kkksu4fPPP2e77bbb6Bb53/nOd7jnnnvo1q0b+++/P3vvvTcAr776KiNGjKBJkyY0b96cW2+9FYALLriAAQMGlF2rNmbMGIYMGcKqVasAuPbaa8vm2FJXXXUVQ4YM4d5776VPnz584xvfoE2bNtWaS5JUP7LcI7t168bll1/OIYccQtOmTenZsydjxoxZb8yPf/xjTj31VG6//XaOPfbYsuUPPfQQ9957L82bN+cb3/gGP/vZz9h5553p27cv3bt355hjjuH666/n9ddfLztdsXXr1vzxj3+s9vVld955J+effz5NmjThkEMOqfAyBEmK6p5CsLVKSkrSht+58vrrr9OlS5d6qUe1Z9WqVTRt2pRmzZrxwgsvcNFFF210g5SGwPenVH0RMS2lVFLfdTQU9sht28qVK2ndujUAo0aN4v3339+iG6Bkje9Nqfo21R89oqZa984773Dqqafy1Vdf0aJFC+644476LkmSpHrzl7/8hf/6r/9izZo17Lnnnhsd/ZMkMKipDnTu3JmXX365vsuQJCkTTjvttE3eQVmSwJuJSJIkSVLmeERNkrYRc+/vVONzdj7jrRqfU1I2zXl7VbV+74Ola/jBsHcqXDdxdIetKUlq1DyiJkmSJEkZY1CTJEmSpIwxqG3C1VdfzQ033ADAoYceyoa3Ss6agQMHsmzZMpYtW8bo0aPLlj/99NMcd9xx1Zrz6aef5vnnn692TeW3PX78eEaNGlXp2NLSUiZMmFDtbUmS6o490h4pqXZl+xq1+6Nm5zujfr4zrq6s+wO+YMECRo8ezbBhw7Z6zqeffprWrVtz4IEHbvVcgwYNYtCgQZWuLy0tZerUqQwcOHCrtyVJ27rzR39Uo/PdMWznGp0va+yRkhoaj6ht4Be/+AV77703Bx10EHPmzFlv3b333ktxcTHdu3fnpZdeAuAf//gHxcXFFBcX07NnT1asWAHAddddR2FhIUVFRYwcORKAO+64g969e1NUVMR3vvMdPvvsMwCGDh3K8OHDOfDAA9lrr714+OGHN6rr+uuv56abbgLgRz/6Ef379wdg4sSJnHnmmQB07NiRJUuWMHLkSObPn09xcTEjRowAcl+uOXjwYL797W9z5plnUtEXnd9000107dqVHj16cPrpp7NgwQJuu+02brzxRoqLi5k8eTILFiygf//+9OjRg8MPP5x33nmn7DVceOGFlJSUsPfee/P4449vNP+YMWO4+OKLARg3bhzdu3enqKiIgw8+mC+//JIrr7ySBx98kOLiYh588MEt+WeTJNUBe6Q9UlLdyfYRtTo2bdo0xo4dS2lpKWvWrKFXr17su+++Zes/++wzSktLeeaZZzjvvPN47bXXuOGGG7jlllvo27cvK1eupFWrVvz1r3/lscce48UXX2T77bfno49yn3qefPLJnH/++QBcccUV3HnnnVxyySUAvP/++zz77LPMnj2bQYMGMXjw4PVq69evH//zP//D8OHDmTp1KqtWrWL16tVMnjyZgw8+eL2xo0aN4rXXXqO0tBTIfeL38ssvM3PmTL75zW/St29fnnvuOQ466KCNfu+tt96iZcuWLFu2jJ122okLL7yQ1q1b8+Mf/xiA448/nnPOOYdzzjmHu+66i+HDh/Poo48CuU8pX3rpJebPn89hhx3GvHnzKt3X11xzDU888QS77747y5Yto0WLFlxzzTVMnTqV3/72t1v4LydJqm32SHukpLrlEbVyJk+ezEknncT222/PjjvuuNEpCEOGDAHg4IMP5pNPPmHZsmX07duXSy+9lJtuuolly5bRrFkznnrqKc4991y23357AHbeOXc6yWuvvUa/fv0oLCzkvvvuY+bMmWVzn3jiiTRp0oSuXbvywQcfbFTbvvvuy7Rp0/jkk09o2bIlffr0YerUqUyePJl+/fpt9rXtt99+tG/fniZNmlBcXMyCBQs2GtOjRw/OPPNM/vjHP9KsWcUZ/oUXXuCMM84A4Oyzz+bZZ58tW3fqqafSpEkTOnfuzF577cXs2bMrradv374MHTqUO+64g7Vr1262fklS/bJH2iMl1S2D2haIiI2ejxw5kt///vd8/vnn9O3bd5N/eIcOHcpvf/tbXn31Va666iq++OKLsnUtW7Yse1zRKRfNmzenU6dOjBkzhgMPPJB+/foxadIk5s2bR5cuXTZbe/n5mzZtypo1azYa85e//IUf/OAHTJ8+nd69e1c4ZlMq2j+Vue2227j22mtZuHAh++67L0uXLt2ibUmSssUeuWn2SElbyqBWzsEHH8yjjz7K559/zooVK/jzn/+83vp154Q/++yztG3blrZt2zJ//nwKCwu57LLL6N27N7Nnz+bII4/k7rvvLju/ft1pHStWrGC33XZj9erV3HfffVtcX79+/bjhhhs4+OCD6devH7fddhs9e/bc6I99mzZtyq4DqKqvvvqKhQsXcthhh3HdddexfPlyVq5cudFcBx54IGPHjgXgvvvuW++TynHjxvHVV18xf/583nzzTfbZZ59Ktzd//nz2339/rrnmGgoKCli4cGG16pYk1Q17pD1SUt3yGrVyevXqxWmnnUZRURG77rorvXv3Xm99q1at6NmzJ6tXr+auu+4C4Ne//jWTJk2iSZMmdOvWjWOOOYaWLVtSWlpKSUkJLVq0YODAgfzyl7/k5z//Ofvvvz8FBQXsv//+W/wHt1+/fvziF7+gT58+7LDDDrRq1arCUzp22WUX+vbtS/fu3TnmmGM49thjNzv32rVrOeuss1i+fDkpJYYPH85OO+3E8ccfz+DBg3nssce4+eabufnmmzn33HO5/vrrKSgo4O677y6bo0OHDuy333588skn3HbbbbRq1arS7Y0YMYK5c+eSUuLwww+nqKiIDh06MGrUKIqLi/npT3/KaaedtkX7Z1sz9/5ONT5n5zPeqvE5JTUO9kh7pKS6FRWdQlAXSkpK0obfufL6669X6RQFZc/QoUM57rjjNrrAe1tS1+9Pg5q2VJbfMxExLaVUUiOTNQL2yG1LQ+mRc95eVa3fe3/hG1xzf9sK100c3WFrSpK2eZvqj576KEmSJEkZ46mPqhFjxoyp7xIkScoke6Sk6vCImiRJkiRljEFNkiRJkjLGoCZJkiRJGWNQkyRJkqSMMahlxLJlyxg9enSl61u3br3J31+wYAHdu3ffom0OHTqUhx9+uEpjV61axRFHHEFxcXHZl5rWhgULFnD//feXPR8zZgwXX3xxteebPXs2xcXF9OzZk/nz53PggQeWbWdL95ckqX7YI3Nqu0eefvKhACxauIDjj+q1teVK2kqZvutjTX8nUG1+h9SaNWto1qxZpc83Z10TGjZsWG2Ut9VefvllAEpLSzdat3btWpo2bVoj21nXhM4444wame/RRx9l8ODBXHHFFQA8//zzNTKvJNW3oXf/oUbnG3PuOTU6X3n2yIbRI8f+6ekamVdSzfCI2gbuueceevToQVFREWeffTaQ+8PYv39/evToweGHH84777wD5D5tu/DCC9l///35yU9+stHz+fPnM2DAAPbdd1/69evH7NmzAfjggw846aSTKCoqoqioiOeff56RI0cyf/58iouLGTFiRKX1rVy5ksMPP5xevXpRWFjIY489VrZuzZo1nHnmmXTp0oXBgwfz2WefATBt2jQOOeQQ9t13X44++mjef//9jeYdOXIkXbt2pUePHvz4xz9eb92HH37IWWedxZQpUyguLmb+/Pl07NiRyy67jF69ejFu3DgeeOABCgsL6d69O5dddlnZ77Zu3ZoRI0bQrVs3jjjiCF566SUOPfRQ9tprL8aPH19hHZMnT6a4uJgbb7wRgPfee48BAwbQuXNnfvKTn5SNffLJJ+nTpw+9evXilFNOYeXKlevNNWHCBH79619z6623cthhh5XVs6G1a9cyYsQIevfuTY8ePfjd735X6f6XpMbMHrlt98heXXfZaJtr167lv3/5UwYP6sugASWMve+OSve/pJqV6SNqdW3mzJlce+21PP/887Rr146PPvoIgEsuuYRzzjmHc845h7vuuovhw4fz6KOPArBo0SKef/55mjZtytChQ9d7fvjhh3PbbbfRuXNnXnzxRYYNG8bEiRMZPnw4hxxyCI888ghr165l5cqVjBo1itdee63CT+PKa9WqFY888gg77rgjS5Ys4YADDmDQoEEAzJkzhzvvvJO+ffty3nnnMXr0aH74wx9yySWX8Nhjj1FQUMCDDz7I5Zdfzl133VU259KlS3nkkUeYPXs2EcGyZcvW2+auu+7K73//e2644QYef/zxsuW77LIL06dP57333uOAAw5g2rRpfO1rX+Ooo47i0Ucf5cQTT+TTTz+lf//+XH/99Zx00klcccUV/O1vf2PWrFmcc845ZbWvM2rUqPW2M2bMGEpLS3n55Zdp2bIl++yzD5dccgnbbbcd1157LU899RQ77LAD1113Hb/61a+48sory+YaOHAgF154Ia1bt96osZZ355130rZtW6ZMmcKqVavo27cvRx11FJ061ewRXUlqyOyRjbNHPvzg3bRpsyMPj3+OL1etYsjgwzjo4CNov4c9UqptBrVyJk6cyCmnnEK7du0A2HnnnQF44YUX+NOf/gTA2Wefvd4nVqeccsp6pzSse75y5Uqef/55TjnllLJ1q1atKtvOPffcA0DTpk1p27YtH3/8cZVqTCnxs5/9jGeeeYYmTZrw7rvv8sEHHwCwxx570LdvXwDOOussbrrpJgYMGMBrr73GkUceCeQ+Gdttt93Wm7Nt27a0atWK733vexx33HEcd9xxVarltNNOA2DKlCkceuihFBQUAHDmmWfyzDPPcOKJJ9KiRQsGDBgAQGFhIS1btqR58+YUFhayYMGCKm3n8MMPp23btgB07dqVt99+m2XLljFr1qyy1/vll1/Sp0+fKs23oSeffJJXXnml7FqE5cuXM3fuXIOaJJVjj2ycPfK5yX9nzuxXeWLCIwCsWLGcBW/NM6hJdcCgtpV22GGHCp9/9dVX7LTTTpv99G9L3XfffSxevJhp06bRvHlzOnbsyBdffAFARKw3NiJIKdGtWzdeeOGFSuds1qwZL730En//+995+OGH+e1vf8vEiRM3W8uGr70izZs3L6urSZMmtGzZsuzxmjVrNvv7QNnvQK5pr1mzhpQSRx55JA888ECV5tiUlBI333wzRx999FbPJUn6F3vkpjWUHnnF1TfS75Ajt3ouSVvGa9TK6d+/P+PGjWPp0qUAZad1HHjggYwdOxbINYF+/fptdq4dd9yRTp06MW7cOCD3h27GjBlA7tOvW2+9Fch9erd8+XLatGnDihUrNjvv8uXL2XXXXWnevDmTJk3i7bffLlv3zjvvlDWb+++/n4MOOoh99tmHxYsXly1fvXo1M2fOXG/OlStXsnz5cgYOHMiNN95YVmdV7bfffvzjH/9gyZIlrF27lgceeIBDDjlki+ZYp6r74YADDuC5555j3rx5AHz66ae88cYb1drm0Ucfza233srq1asBeOONN/j000+rNZckbavskY2zRx508BGM/ePtZT3yrTfn8tln9kipLhjUyunWrRuXX345hxxyCEVFRVx66aUA3Hzzzdx999306NGDe++9l9/85jdVmu++++7jzjvvpKioiG7dupVd1Pyb3/yGSZMmUVhYyL777susWbPYZZdd6Nu3L927d9/khdJnnnkmU6dOpbCwkHvuuYdvf/vbZev22WcfbrnlFrp06cLHH3/MRRddRIsWLXj44Ye57LLLKCoqori4eKM7H65YsYLjjjuOHj16cNBBB/GrX/1qi/bbbrvtxqhRozjssMMoKipi33335YQTTtiiOdbp0aMHTZs2paioqOxC6YoUFBQwZswYhgwZQo8ePejTp0/Zhehb6vvf/z5du3alV69edO/enX//93+v8ieZktRY2CMbZ4885fTz+Fbnb3PycQdw/FG9uOpnP2CtPVKqE5FSqpcNl5SUpKlTp6637PXXX6dLly71Uo+0OXX9/qzpr6eA2v2KCtW/LL9nImJaSqmkRiZrBOyRqg9z3l5Vrd97f+EbXHN/2wrXTRzdYWtKkrZ5m+qPXqMmSZIk1bHzR39U43PeMWznGp9zU/oPe6fG5zTc/4unPkqSJElSxhjUJEmSJCljNhvUIuKuiPgwIl6rZH1ExE0RMS8iXomIXltTUH1dMydtiu9LSVng3yJlTUqJr+q7CGkbVZUjamOAAZtYfwzQOf9zAXBrdYtp1aoVS5cutREpU1JKLF26lFatWtV3KZIaMXuksialxKrPl/F/HzXd/GBJW2yzNxNJKT0TER03MeQE4J6U6xz/jIidImK3lNL7W1pM+/btWbRoEYsXL97SX5VqVatWrWjfvn19lyGpEbNHqrZ9sHTLbrv/FfB/HzXlgae3r3TMtnDDDKm+1MRdH3cHFpZ7vii/bIuDWvPmzenUqeZvLy1JUkNnj1Rt+0Et3MFPUvXV6c1EIuKCiJgaEVP9RFCSJEmSKlYTQe1dYI9yz9vnl20kpXR7SqkkpVRSUFBQA5uWJEmSpG1PTQS18cB383d/PABYXp3r0yRJkiRJOZu9Ri0iHgAOBdpFxCLgKqA5QErpNmACMBCYB3wGnFtbxUqSJEl1rX8tXL/3re6ta3xObVuqctfHIZtZn4Af1FhFkiQpk7yDnyTVnTq9mYgkSZIkafMMapIkSZKUMQY1SZIkScoYg5okSZIkZYxBTZIkSZIyxqAmSZIkSRljUJMkSZKkjDGoSZIkSVLGGNQkSZIkKWMMapIkSZKUMc3quwA1bnPv71Tjc3Y+460an1OSJEmqSx5RkyRJkqSMMahJkiRJUsYY1CRJkiQpYwxqkiRJkpQx3kxEUoNSGzegAW9CI0mSssUjapIkSZKUMQY1SZIkScoYg5okSZIkZYxBTZIkSZIyxqAmSVI1RcSAiJgTEfMiYmQF6ztExKSIeDkiXomIgfVRpySp4fGuj5IkVUNENAVuAY4EFgFTImJ8SmlWuWFXAA+llG6NiK7ABKBjnRcrSQ3E+aM/qpV57xi2c63MW5s8oiZJUvXsB8xLKb2ZUvoSGAucsMGYBOyYf9wWeK8O65MkNWAGNUmSqmd3YGG554vyy8q7GjgrIhaRO5p2SWWTRcQFETE1IqYuXry4pmuVJDUwBjVJkmrPEGBMSqk9MBC4NyIq7L0ppdtTSiUppZKCgoI6LVKSlD0GNUmSquddYI9yz9vnl5X3PeAhgJTSC0AroF2dVCdJatAMapIkVc8UoHNEdIqIFsDpwPgNxrwDHA4QEV3IBTXPa5QkbZZBTZKkakgprQEuBp4AXid3d8eZEXFNRAzKD/sP4PyImAE8AAxNKaX6qViS1JB4e35JkqoppTSB3E1Cyi+7stzjWUDfuq5LktTweURNkiRJkjLGoCZJkiRJGWNQkyRJkqSMMahJkiRJUsYY1CRJkiQpYwxqkiRJkpQxBjVJkiRJyhiDmiRJkiRljF94XUfm3t+pxufsfMZbNT6nJEmSpPrnETVJkiRJyhiDmiRJkiRljKc+SpK0Deo/7J0an/Nb3VvX+JySpIp5RE2SJEmSMsagJkmSJEkZY1CTJEmSpIwxqEmSJElSxhjUJEmSJCljDGqSJEmSlDEGNUmSJEnKGIOaJEmSJGWMQU2SJEmSMqZZfRcgSZJUV/oPe6dW5p04ukOtzCup8fKImiRJkiRljEFNkiRJkjLGoCZJkiRJGWNQkyRJkqSMMahJkiRJUsYY1CRJkiQpYwxqkiRJkpQxBjVJkiRJyhiDmiRJkiRljEFNkiRJkjLGoCZJkiRJGWNQkyRJkqSMMahJkiRJUsYY1CRJkiQpYwxqkiRJkpQxBjVJkiRJypgqBbWIGBARcyJiXkSMrGB9h4iYFBEvR8QrETGw5kuVJEmSpMah2eYGRERT4BbgSGARMCUixqeUZpUbdgXwUErp1ojoCkwAOtZCvZIkSWrEht79h1qZd8y559TKvFJ1bTaoAfsB81JKbwJExFjgBKB8UEvAjvnHbYH3arJISZIkSaqu2gj4tR3uqxLUdgcWlnu+CNh/gzFXA09GxCXADsARNVKdJEmSpCppiGFElaupm4kMAcaklNoDA4F7I2KjuSPigoiYGhFTFy9eXEObliRJkqRtS1WC2rvAHuWet88vK+97wEMAKaUXgFZAuw0nSindnlIqSSmVFBQUVK9iSZIkSdrGVSWoTQE6R0SniGgBnA6M32DMO8DhABHRhVxQ85CZJEmSJFXDZoNaSmkNcDHwBPA6ubs7zoyIayJiUH7YfwDnR8QM4AFgaEop1VbRkiRJkrQtq8rNREgpTSB3y/3yy64s93gW0LdmS5MkSZKkxqmmbiYiSZIkSaohBjVJkiRJyhiDmiRJkiRljEFNkiRJkjLGoCZJkiRJGWNQkyRJkqSMMahJkiRJUsYY1CRJkiQpY6r0hdeZdfVJtTTvI7UzryRJkiRVgUfUJEmSJCljDGqSJEmSlDEGNUmSJEnKGIOaJEmSJGWMQU2SJEmSMsagJkmSJEkZ07Bvz6/K1cZXF/i1BZIkSVKd8IiaJEmSJGWMQU2SJEmSMsagJkmSJEkZY1CTJEmSpIwxqEmSJElSxhjUJEmSJCljDGqSJEmSlDEGNUmSJEnKGIOaJEmSJGWMQU2SJEmSMsagJkmSJEkZY1CTJEmSpIwxqEmSJElSxjSr7wIkqVG6P2ph0o61MKckSaoPHlGTJEmSpIwxqEmSVE0RMSAi5kTEvIgYWcmYUyNiVkTMjIj767pGSVLD5KmPkiRVQ0Q0BW4BjgQWAVMiYnxKaVa5MZ2BnwJ9U0ofR8Su9VOtJKmh8YiaJEnVsx8wL6X0ZkrpS2AscMIGY84HbkkpfQyQUvqwjmuUJDVQBjVJkqpnd2BhueeL8svK2xvYOyKei4h/RsSAOqtOktSgeeqjJEm1pxnQGTgUaA88ExGFKaVlGw6MiAuACwA6dOhQhyVKkrLII2qSJFXPu8Ae5Z63zy8rbxEwPqW0OqX0FvAGueC2kZTS7SmlkpRSSUFBQa0ULElqOAxqkiRVzxSgc0R0iogWwOnA+A3GPEruaBoR0Y7cqZBv1mGNkqQGyqAmSVI1pJTWABcDTwCvAw+llGZGxDURMSg/7AlgaUTMAiYBI1JKS+unYklSQ+I1apIkVVNKaQIwYYNlV5Z7nIBL8z+SJFWZR9QkSZIkKWMMapIkSZKUMQY1SZIkScoYg5okSZIkZYxBTZIkSZIyxqAmSZIkSRljUJMkSZKkjDGoSZIkSVLGGNQkSZIkKWMMapIkSZKUMQY1SZIkScoYg5okSZIkZYxBTZIkSZIypll9FyBJmXf1STU/5941P6UkSdp2eERNkiRJkjLGoCZJkiRJGWNQkyRJkqSM8Ro1SZJUb4be/Ycan3PMuefU+JySVNc8oiZJkiRJGeMRNakm3B+1MGnHWphTkiRJDYFH1CRJkiQpYzyiJqn2eKRRkiSpWjyiJkmSJEkZY1CTJEmSpIwxqEmSJElSxniNmiRJ0lY6f/RHNT7nHcN2rvE5JTUcHlGTJEmSpIyp0hG1iBgA/AZoCvw+pTSqgjGnAlcDCZiRUjqjBuuUVNuuPqnm59y75qeUJElqDDYb1CKiKXALcCSwCJgSEeNTSrPKjekM/BTom1L6OCJ2ra2CJUmSJGlbV5VTH/cD5qWU3kwpfQmMBU7YYMz5wC0ppY8BUkof1myZkiRJktR4VCWo7Q4sLPd8UX5ZeXsDe0fEcxHxz/ypkpIkSZKkaqipuz42AzoDhwLtgWciojCltKz8oIi4ALgAoEOHDjW0aWkLeS2WJEmSMq4qR9TeBfYo97x9fll5i4DxKaXVKaW3gDfIBbf1pJRuTymVpJRKCgoKqluzJEmSJG3TqhLUpgCdI6JTRLQATgfGbzDmUXJH04iIduSOL7xZc2VKkiRJUuOx2aCWUloDXAw8AbwOPJRSmhkR10TEoPywJ4ClETELmASMSCktra2iJUmSJGlbVqVr1FJKE4AJGyy7stzjBFya/5EkSZIkbYWqnPooSZIkSapDNXXXx23L/VELk3ashTklSZIkbYs8oiZJkiRJGWNQkyRJkqSMMahJkiRJUsYY1CRJkiQpYwxqkiRJkpQxBjVJkiRJyhiDmiRJkiRljEFNkiRJkjLGoCZJkiRJGWNQkyRJkqSMMahJkiRJUsYY1CRJkiQpYwxqkiRJkpQxBjVJkiRJyhiDmiRJkiRljEFNkiRJkjLGoCZJkiRJGWNQkyRJkqSMMahJkiRJUsYY1CRJkiQpYwxqkiRJkpQxBjVJkiRJyhiDmiRJkiRljEFNkiRJkjLGoCZJkiRJGWNQkyRJkqSMMahJkiRJUsYY1CRJkiQpYwxqkiRJkpQxBjVJkiRJyhiDmiRJkiRljEFNkiRJkjLGoCZJkiRJGWNQkyRJkqSMMahJkiRJUsYY1CRJkiQpYwxqkiRJkpQxBjVJkiRJyphm9V2AGpD7oxYm7VgLc0qSJEkNm0FNkiQpg4be/Ycan3PMuefU+JySaoenPkqSJElSxhjUJEmqpogYEBFzImJeRIzcxLjvRESKiJK6rE+S1HAZ1CRJqoaIaArcAhwDdAWGRETXCsa1AX4IvFi3FUqSGjKDmiRJ1bMfMC+l9GZK6UtgLHBCBeN+DlwHfFGXxUmSGjaDmiRJ1bM7sLDc80X5ZWUiohewR0rpL3VZmCSp4TOoSZJUCyKiCfAr4D+qOP6CiJgaEVMXL15cu8VJkjLPoCZJUvW8C+xR7nn7/LJ12gDdgacjYgFwADC+shuKpJRuTymVpJRKCgoKaqlkSVJDYVCTJKl6pgCdI6JTRLQATgfGr1uZUlqeUmqXUuqYUuoI/BMYlFKaWj/lSpIaEoOaJEnVkFJaA1wMPAG8DjyUUpoZEddExKD6rU6S1NA1q+8CJElqqFJKE4AJGyy7spKxh9ZFTZKkbYNH1CRJkiQpYwxqkiRJkpQxBjVJkiRJyhiDmiRJkiRljEFNkiRJkjLGoCZJkiRJGWNQkyRJkqSMMahJkiRJUsYY1CRJkiQpYwxqkiRJkpQxBjVJkiRJyhiDmiRJkiRljEFNkiRJkjLGoCZJkiRJGWNQkyRJkqSMqVJQi4gBETEnIuZFxMhNjPtORKSIKKm5EiVJkiSpcdlsUIuIpsAtwDFAV2BIRHStYFwb4IfAizVdpCRJkiQ1JlU5orYfMC+l9GZK6UtgLHBCBeN+DlwHfFGD9UmSJElSo1OVoLY7sLDc80X5ZWUiohewR0rpLzVYmyRJkiQ1Slt9M5GIaAL8CviPKoy9ICKmRsTUxYsXb+2mJUmSJGmbVJWg9i6wR7nn7fPL1mkDdAeejogFwAHA+IpuKJJSuj2lVJJSKikoKKh+1ZIkSZK0DatKUJsCdI6IThHRAjgdGL9uZUppeUqpXUqpY0qpI/BPYFBKaWqtVCxJkiRJ27jNBrWU0hrgYuAJ4HXgoZTSzIi4JiIG1XaBkiRJktTYNKvKoJTSBGDCBsuurGTsoVtfliRJkiQ1Xlt9MxFJkiRJUs0yqEmSJElSxhjUJEmSJCljDGqSJEmSlDEGNUmSJEnKGIOaJEmSJGWMQU2SJEmSMsagJkmSJEkZY1CTJEmSpIwxqEmSJElSxhjUJEmSJCljDGqSJEmSlDEGNUmSJEnKGIOaJEmSJGWMQU2SJEmSMsagJkmSJEkZY1CTJEmSpIwxqEmSJElSxhjUJEmSJCljDGqSJEmSlDEGNUmSJEnKGIOaJEmSJGWMQU2SJEmSMsagJkmSJEkZY1CTJEmSpIwxqEmSJElSxhjUJEmSJCljDGqSJEmSlDEGNUmSJEnKGIOaJEmSJGWMQU2SJEmSMsagJkmSJEkZY1CTJEmSpIwxqEmSJElSxhjUJEmSJCljDGqSJEmSlDEGNUmSJEnKGIOaJEmSJGWMQU2SJEmSMsagJkmSJEkZY1CTJEmSpIwxqEmSJElSxhjUJEmSJCljDGqSJEmSlDEGNUmSJEnKGIOaJEmSJGWMQU2SJEmSMsagJkmSJEkZY1CTJEmSpIwxqEmSJElSxhjUJEmSJCljDGqSJEmSlDEGNUmSJEnKGIOaJEmSJGWMQU2SJEmSMsagJklSNUXEgIiYExHzImJkBesvjYhZEfFKRPw9IvasjzolSQ2PQU2SpGqIiKbALcAxQFdgSER03WDYy0BJSqkH8DDw33VbpSSpoTKoSZJUPfsB81JKb6aUvgTGAieUH5BSmpRS+iz/9J9A+zquUZLUQBnUJEmqnt2BheWeL8ovq8z3gL/WakWSpG1Gs/ouQJKkbV1EnAWUAIdsYswFwAUAHTp0qKPKJElZ5RE1SZKq511gj3LP2+eXrScijgAuBwallFZVNllK6faUUklKqaSgoKDGi5UkNSwGNUmSqmcK0DkiOkVEC+B0YHz5ARHRE/gduZD2YT3UKElqoAxqkiRVQ0ppDXAx8ATwOvBQSmlmRFwTEYPyw64HWgPjIqI0IsZXMp0kSevxGjVJkqoppTQBmLDBsivLPT6izouSJG0TPKImSZIkSRljUJMkSZKkjDGoSZIkSVLGVCmoRcSAiJgTEfMiYmQF6y+NiFkR8UpE/D0i9qz5UiVJkiSpcdhsUIuIpsAtwDFAV2BIRHTdYNjLQElKqQfwMPDfNV2oJEmSJDUWVTmith8wL6X0ZkrpS2AscEL5ASmlSSmlz/JP/0nuSz8lSZIkSdVQlaC2O7Cw3PNF+WWV+R7w160pSpIkSZIasxr9HrWIOAsoAQ6pZP0FwAUAHTp0qMlNS5IkSdI2oypH1N4F9ij3vH1+2Xoi4gjgcmBQSmlVRROllG5PKZWklEoKCgqqU68kSZIkbfOqEtSmAJ0jolNEtABOB8aXHxARPYHfkQtpH9Z8mZIkSZLUeGw2qKWU1gAXA08ArwMPpZRmRsQ1ETEoP+x6oDUwLiJKI2J8JdNJkiRJkjajSteopZQmABM2WHZlucdH1HBdkiRJktRoVekLryVJkiRJdcegJkmSJEkZY1CTJEmSpIwxqEmSJElSxhjUJEmSJCljDGqSJEmSlDEGNUmSJEnKGIOaJEmSJGWMQU2SJEmSMsagJkmSJEkZY1CTJEmSpIwxqEmSJElSxhjUJEmSJCljDGqSJEmSlDEGNUmSJEnKGIOaJEmSJGWMQU2SJEmSMsagJkmSJEkZY1CTJEmSpIwxqEmSJElSxhjUJEmSJCljDGqSJEmSlDEGNUmSJEnKGIOaJEmSJGWMQU2SJEmSMsagJkmSJEkZY1CTJEmSpIwxqEmSJElSxhjUJEmSJCljDGqSJEmSlDEGNUmSJEnKGIOaJEmSJGWMQU2SJEmSMsagJkmSJEkZY1CTJEmSpIwxqEmSJElSxhjUJEmSJCljDGqSJEmSlDEGNUmSJEnKGIOaJEmSJGWMQU2SJEmSMsagJkmSJEkZY1CTJEmSpIwxqEmSJElSxhjUJEmSJCljDGqSJEmSlDEGNUmSJEnKGIOaJEmSJGWMQU2SJEmSMsagJkmSJEkZY1CTJEmSpIwxqEmSJElSxhjUJEmSJCljDGqSJEmSlDEGNUmSJEnKGIOaJEmSJGWMQU2SJEmSMsagJkmSJEkZY1CTJEmSpIwxqEmSJElSxhjUJEmSJCljDGqSJEmSlDEGNUmSJEnKGIOaJEmSJGWMQU2SJEmSMsagJkmSJEkZY1CTJEmSpIypUlCLiAERMSci5kXEyArWt4yIB/PrX4yIjjVeqSRJGWN/lCTVls0GtYhoCtwCHAN0BYZERNcNhn0P+Dil9G/AjcB1NV2oJElZYn+UJNWmqhxR2w+Yl1J6M6X0JTAWOGGDMScAf8g/fhg4PCKi5sqUJClz7I+SpFpTlaC2O7Cw3PNF+WUVjkkprQGWA7vURIGSJGWU/VGSVGsipbTpARGDgQEppe/nn58N7J9SurjcmNfyYxbln8/Pj1mywVwXABfkn+4DzKmpF1JP2gFLNjuqcXLfVMz9Ujn3TcW2lf2yZ0qpoL6LqEk12R/z6+yRjYP7pXLum4q5Xyq3LeybSvtjsyr88rvAHuWet88vq2jMoohoBrQFlm44UUrpduD2qlTcEETE1JRSSX3XkUXum4q5XyrnvqmY+yXTaqw/gj2ysXC/VM59UzH3S+W29X1TlVMfpwCdI6JTRLQATgfGbzBmPHBO/vFgYGLa3KE6SZIaNvujJKnWbPaIWkppTURcDDwBNAXuSinNjIhrgKkppfHAncC9ETEP+Ihcs5IkaZtlf5Qk1aaqnPpISmkCMGGDZVeWe/wFcErNltYgbDOnqNQC903F3C+Vc99UzP2SYfbHTfK9WzH3S+XcNxVzv1Rum943m72ZiCRJkiSpblXlGjVJkiRJUh0yqFVBRFwdET+OiGsi4oj6rqchiIiSiLipvuvIiohYmf/vNyPi4UrGPB0Rmblz0bqa63H7V0fEjytYvlNEDKviHM/XfGW1p773uVQd9sgtZ49cX0PrkfX9t9r+2HhU6Ro15ZS/7kCbllKaCkyt7zqyJqX0Hrk7v6n6dgKGAaM3NzCldGCtVyMJsEduCXtkxeyRW20n7I/bFI+oVSIiLo+INyLiWXJfPEpEjMl/wSkR0Tsino+IGRHxUkS0iYimEXF9REyJiFci4t/r9UVspYj4bv51zIiIeyOiY0RMzC/7e0R0yI87JSJey497Jr/s0Ih4PP/46oi4K/9p2JsRMbzcNs7K77/SiPhdRDStn1dbuYpqLP/JTkQMjogx+cdfj4hH8vtiRkQcuMFcHfNfgEtEbBcRYyPi9Yh4BNiu3LijIuKFiJgeEeMionV++aiImJX/N7ihLl5/frsjyr2v/7NcLT8oN6bsE75KxnfMv9Y7ImJmRDwZEdvl1w0v97rGltt01wreN6OAb+X/Pa6vbHv55es+pT00P8/DETE7Iu6LiKjFXbbVIuKyiHg1/z4alV9W2X6S6pQ90h65TmPvkfbHuteo+mNKyZ8NfoB9gVeB7YEdgXnAj4Ex5D7paQG8CfTOj9+R3NHJC4Ar8stakvu0rFN9v55q7oNuwBtAu/zznYE/A+fkn58HPJp//Cqwe/7xTvn/Hgo8nn98NfB8fp+0I/dlr82BLvk5m+fHjQa+W9+vfYP9UGGNwMpyYwYDY/KPHwT+v/zjpkDb/OOV+f92BF7LP76U3O28AXoAa4CS/D56Btghv+4y4EpgF2AO/7oJ0E61/NrX1XwUubsqBbkPdx4HDgZ6Av8oN34WuS/2rWx8x/xrLM6Pfwg4K//4PaDlBu+hyt43ZftwU/Vt8BoOBZaT+0LiJsALwEH1/f7axD4/Jv/at1/3/19l+8kff+r6B3sk2CPX7YdG2SOxP9bHe61R9kdPfaxYP+CRlNJnABGx4ReY7gO8n1KaApBS+iQ/7iigx7pPFIG2QGfgrTqpumb1B8allJYApJQ+iog+wMn59fcC/51//BwwJiIeAv5UyXx/SSmtAlZFxIfA14HDyTX8KfkPb7YDPqyNF7MVtrTG/uSaFCmlteT++FXmYOCm/NhXIuKV/PIDgK7Ac/lttiD3h3M58AVwZ/6T2Mer95K22FH5n5fzz1sDnVNKd0bErhHxTaAA+DiltDAifljReOAd4K2UUml++TRyTQXgFeC+iHgUeLTctit631SpPnKNvLyXUkqLACKiNL/tZ6u0B+reEcDd6/4GpZQ+yi+vbD9JdckeaY9cp7H3SPtj3WtU/dGgVrMCuCSl9ER9F1KXUkoXRsT+wLHAtIjYt4Jhq8o9XkvuvRfAH1JKP62DMqurwhoj4j/KPW1VC9v8W0ppyEYrIvYj1xgHAxeTa3q1LYD/Sin9roJ14/K1fIPcJ6WVjo+Ijmz8Plh3Ksux5Jry8cDlEVGYX17R+2ZL6iuvKnNl3Ub7KaW0pp5rkqrKHmmPrKltZqVH2h+zY5vsj16jVrFngBPz50e3IfePXt4cYLeI6A0QuXPvmwFPABdFRPP88r0jYoe6LLwGTQROiYhdACJiZ3KHmk/Prz8TmJxf962U0ospdyH5YnKH96vi78DgiNh13TYiYs8afA01obIaP4iILhHRBDhpg/EX5cc2jYi2m5j7GeCM/Nju5E7tAPgn0Dci/i2/bof8e6k1udNEJgA/Aopq7FVu2hPAefGvawB2X7c/yDWf08k1o3FVGL+R/D7cI6U0idwpLG3JfepXmRVAmyrW11D9DTg3IraHsvfdlu4nqbbYI+2R6zT2Hml/rHuNqj82xMRc61JK0yPiQWAGuUP4UzZY/2VEnAbcHLmLPT8ndyj29+QOF0+P3PH4xcCJdVh6jUkpzYyIXwD/iIi15A6bXwLcHREjyL22c/PDr4+IzuQ+ufk7uf12SBW2MSsirgCezP9Pthr4AfB2jb+gatpEjSPJnVaxmNx1Fuv+IPwQuD0ivkfuU6mLyJ2SUZFbye3P14HXyZ3qQEppcUQMBR6IiJb5sVeQ+wP8WES0IrevL63J11qZlNKTEdEFeCF/mslK4Czgw/z7pA3wbkrp/c2MX1vJJpoCf8w37ABuSikti0quZU4pLY2I5yJ3wflfU0ojKquvJl5/fUgp/W9EFANTI+JLYAJwFRXsp/qrUo2VPdIeuU5j75H2x7rX2PrjugsuJUmSJEkZ4amPkiRJkpQxBjVJkiRJyhiDmiRJkiRljEFNkiRJkjLGoCZJkiRJGWNQkyRJkqSMMahJkiRJUsYY1CRJkiQpY/5/AiwN6YuROSYAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 1080x576 with 2 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plot_comparison(metrics, davies_indices, dunn_indices, correct_davies, correct_dunn)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "allied-evanescence",
   "metadata": {},
   "source": [
    "Z powyższej zależności możemy zauważyć, iż zastosowanie stoplisty zmieniło w pewnym stopniu jakość klasteryzacji, jednak nie zawsze na lepsze, zależy od konretnego przypadku.\n",
    "\n",
    "Porównując wartości indeksów dla klasteryzacji otrzymanej algorytmem DBSCAN a klasteryzacją z pliku, zawsze lepiej wypada klasteryzacja znaleziona algorytmicznie. Wynika to z faktu, że żadna metryka nie przedstawia w pełni rzeczywistego podobieństwa tekstów. Dlatego dla danej metryki znaleziona klasteryzacja procedurą biblioteczną jest możliwie najbardziej optymalna, zakładając skuteczność algorytmu. \n",
    "\n",
    "Z wykresu można by chcieć wnioskować, iż do klasteryzacji najlepiej sprawdziły się metryki LCS, euklidesowa i przede wszystkim Levenshteina, jednak obliczając indeksy dla tych metryk korzystamy z odległości wyznaczonych tymże metodami, co nie pozwala jednoznacznie ich porównać. Indeksy dobrze sprawdzają się do porównania różnych algorytmów klasteryzacji."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "accredited-clause",
   "metadata": {},
   "source": [
    "<i>Czy masz jakiś pomysł na poprawę jakości klasteryzacji w tym zadaniu? </i>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "adequate-feeding",
   "metadata": {},
   "source": [
    "* Przeprowadzenie preprocessingu pliku wejściowego. Usunięcię niepotrzebnych białych znaków, cudzysłowów, kropek itd.\n",
    "* Lepsze dobranie parametrów modelu. W powyższych rozważaniach dla każdej metryki zostały użyte te same parametry modelu. Lepsze wyniki uzyskalibyśmy analizując wartości w macierzy odległości i wybierając odpowiednią wartość chociażby parametru eps. Moglibyśmy także przetestować wyniki dla zmieniających się parametrów i wybrać najlepszy rezultat."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "liked-concert",
   "metadata": {},
   "source": [
    "## Wnioski"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "formed-hurricane",
   "metadata": {},
   "source": [
    "- Skuteczność klasteryzacji zależy od doboru metryki, jak również dobranych do niej parametrów.\n",
    "\n",
    "- Skuteczność tę można zwiększyć stosując stoplistę najczęściej występujących elementów, jednak nie w każdym przypadku ma to sens, zależy to od rodzaju danych z jakimi mamy do czynienia\n",
    "\n",
    "- Stosowanie zagadnienia klasteryzacji dla tekstów jest problematyczne. Nie dysponujemy łatwą do znalezienia lokalizacją centroidy klastra czy rozmiaru klastra, wymagana jest spora złożoność czasowa lub odpowiednie heurystyczne podejście, które mogłoby przybliżyć te wartości."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "explicit-anime",
   "metadata": {},
   "source": [
    "M. Hawryluk 21.05.2021"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}