import settings
import numpy as np

from utils import array_2d_to_latex

print(
    r"""\newpage
\section{Завдання 10}
\begin{itemize}
\item Розрахувати матрицю вiдстаней мiж об’єктами (див. додаток Б), використовуючи у якостi мiри схожостi евклiдову метрику у просторi ознак. 
\item Провести класифiкацiю об’єктiв агломеративним методом, використовуючи у
якостi мiри близькостi кластерiв метод «ближнього сусiда». Накреслити дендрограму. На скiльки класiв доцiльно розбити початкову сукупнiсть об’єктiв?
\item Провести класифiкацiю об’єктiв дивiзимним методом. Накреслити дендрограму.
На скільки класів доцільно розбити початкову сукупність об’єктів? 
\item Надати змiстовну iнтерпретацiю результатам кластеризацiї.
\end{itemize}
\subsection{Розв'язання}
Пiд класифiкацiєю ми будемо розумiти розподiл сукупностi об’єктiв або явищ на однорiднi групи або вiднесення кожного iз об’єктiв до одного з вiдомих класiв (груп).\\
Доцiльнiсть i ефективнiсть застосування тих чи iнших методiв класифiкацiї обумовленi математичною постановкою задачi. Визначальним моментом у виборi математичної постановки задачi є вiдповiдь на питання: на якiй апрiорнiй iнформацiї будується модель? \\
При цьому апрiорна iнформацiя складається з двох частин:\\
- з апрiорних знань про дослiджуванi класи;\\
- з апрiорної статистичної iнформацiї, тобто так званих навчальних вибiрок.\\
При наявностi навчальних вибiрок класифiкацiя проводиться методами параметричного i непараметричного дискримiнантного аналiзу. У випадку вiдсутностi навчальних вибiрок використовуються методи кластерного аналiзу, таксономiї i рiзнi статистичнi гiпотези.\\
До розробки апарату багатовимiрного статистичного аналiзу всi методи класифiкацiї базувалися на використаннi комбiнацiйного групування.\\
Уся сукупнiсть об’єктiв спочатку розбивається на групи значеннями першої, найбiльш важливої ознаки. Потiм усерединi кожної видiленої групи утворюють пiдгрупи за значеннями наступної ознаки i так далi. Цей пiдхiд одержав назву монотетичного.\\
Недолiки такого пiдходу полягають у тому, що кiлькiсть утворених груп є досить великою, у той час як деякi з них можуть мати незначну наповнюванiсть, а то i зовсiм порожнiми. Це призводить до ускладнення процесу групування нових об’єктiв та змiстовного аналiзу одержаних груп.\\
Розвиток засобiв комп’ютерної технiки дозволив значно збагатити процес класифiкацiї. Це призвело до розробки нових напрямкiв у розв’язаннi задач класифiкацiї багатовимiрних даних. Одним з них є застосування методiв кластерного аналiзу.\\
На вiдмiну вiд комбiнацiйних угрупувань, кластерний аналiз приводить до розбиття на класи з урахуванням всiх ознак одночасно. Такий пiдхiд до розбиття на класи називається полiтетичним.\\
Якщо вiдсутнi навчальнi вибiрки або апрiорна iнформацiя про розподiл генеральної сукупностi ознак, то класифiкацiю об’єктiв можна робити методами кластерного аналiзу.\\
Методами кластерного аналiзу можна розв’язувати такi задачi:\\
- класифiкацiя з урахуванням ознак, що дає поглибленi знання про сукупнiсть об’єктiв;\\
- перевiрка наявностi деякої структури в сукупностi об’єктiв;\\
- побудова нових класифiкацiй для слабо вивчених явищ, коли необхiдно встановити наявнiсть зв’язку всерединi сукупностi i привнести до неї структуру.\\
Методи кластерного аналiзу вченi подiляють на такi групи:\\
- iєрархiчнi агломеративнi методи;\\
- iєрархiчнi дивiзимнi методи;\\
- iтеративнi методи групування;\\
- методи пошуку згущень;\\
- методи пошуку модальних значень щiльностi;\\
- факторнi методи;\\
- методи, що базуються на теорiї графiв.\\
Слiд зазначити, що iснують методи кластерного аналiзу, що не вписуються у вищезгадану класифiкацiю.\\
Агломеративнi (об’єднуючi) методи послiдовно об’єднують окремi кластери (класи) в новi, а дивiзимнi  (подiляючi) методи, навпаки, розчленовують кластери на окремi групи. Iснують декiлька алгоритмiв реалiзацiї цих методiв.\\
У iтеративних методах процес класифiкацiї починається iз задання деяких початкових умов (кiлькiсть кластерiв, початковi кластери, порiг завершення процесу класифiкацiї i т. д.). Тому якiсть класифiкацiї i швидкiсть збiгу алгоритму залежить вiд iнтуїцiї i вмiння користувача. Буде краще, якщо за початковi кластери взяти результати роботи iєрархiчних агломеративних методiв.\\
При проведеннi класифiкацiї необхiдно ввести поняття схожостi об’єктiв. Для кiлькiсної оцiнки схожостi введемо поняття метрики, тобто вiдстанi мiж об’єктами.\\
У кластерному аналiзу використовуються рiзнi метрики.\\ Ми будемо використовувати \textbf{Евклідову метрику:} \\ \includegraphics[width = 17cm, height = 5cm]{lab10_1.PNG} \\
Оцінка схожості між об’єктами досить сильно залежить від абсолютного значення ознаки і від ступеня її варіації в сукупності. Щоб усунути вплив подібного явища на процедуру класифікації, необхідно значення змінних стандартизувати (нормалізувати) таким чином: \\ \includegraphics[width = 17cm, height = 3cm]{lab10_2.PNG} \\
Подібність між об’єктами може бути визначена за допомогою вибіркових коефіцієнтів кореляції. Однак слід зважувати на те, що коефіцієнт кореляції вимірює лише лінійний зв’язок між об’єктами. У випадку нелінійного зв’язку за міру близькості об’єктів можна брати кореляційне відношення.\\
Рангові коефіцієнти кореляції використовуються для оцінки близькості об’єктів у випадку, якщо ознаки є ранговими даними.\\
Надалі будемо вважати, що вихідні ознаки вимірюються кількісно. \\ \\
Розрахуємо матрицю вiдстаней мiж об’єктами (див. додаток Б), використовуючи у якостi мiри схожостi евклiдову метрику у просторi ознак."""
)

X = settings.task_10_classification_rows
Y = np.array([v - 1 for v in settings.task_10_classification_countries])

df = settings.task_10_table_raw

df_s = df.values
n = len(df)

std = df.std(ddof=1)

df_st = (df - df.mean()) / std

D = np.zeros((len(Y), len(Y)))
for i in range(len(Y)):
    for j in range(len(Y)):
        D[i][j] = np.sqrt(((df_st.loc[Y[i]] - df_st.loc[Y[j]]) ** 2).sum())

D = np.round(D, 2)
print(array_2d_to_latex(D, rounding=2))

print(
    r"""\subsubsection{Ієрархічні методи класифікації}
При використанні різних методів класифікації для однієї і тієї самої сукупності об’єктів можемо отримати різні розбиття. На отриману структуру класифікації можуть впливати: набір ознак, вибраний алгоритм, міра схожості.\\ 
\begin{center}
    \textbf{Агломеративні методи}
\end{center}
Серед усіх методів кластерного аналізу найбільш поширеними є ієрархічні агломеративні методи. Їх суть полягає у послідовному об’єднанні двох найбільш подібних кластерів в один до тих пір, поки не буде утворено один кластер, що містить в собі всі об’єкти.\\
На першому кроці кожен об’єкт являє собою окремий кластер. На основі матриці відмінностей (відстаней) між об’єктами знаходять два найбільш близьких кластери, які і об’єднують в один. Новому кластеру присвоюється номер елементу цього кластера з найменшим значенням індексу. Для решти кластерів їх позначення на цьому кроці залишаються незмінними.\\
Далі матриця відмінностей між кластерами, вимірність якої зменшується на одиницю, перераховується, і процес продовжується. Тобто знову знаходяться два найбільш подібних кластери, які будуть об’єднуватись з подальшим перерахуванням матриці відмінностей.\\
Результатом цього процесу і буде утворення одного кластера, який міститиме всі об’єкти сукупності. Однак це не означає, що такий підхід не дозволяє розбити об’єкти на декілька кластерів.\\
Необхідна кількість кластерів, на які розіб’ється вихідна сукупність, визначається шляхом аналізу значення відстані між кластерами, при якій здійснювалося об’єднання кластерів. Наприклад, ця кількість може виявитись на тому етапі, після якого приріст значення відстані між кластерами був найбільшим.\\
Графічно процес об’єднання кластерів можна зобразити у вигляді дендрограми (графа-дерева), яка показує, які кластери і при якому значенні відстані між ними були об’єднані на черговому кроці методу. \\ \\
Проведемо класифікацію об’єктів агломеративним методом, використовуючи у якості міри близькості кластерів метод «ближнього сусіда». \\
Об’єднання кластерiв на кожному кроцi здiйснюється за ознакою їх найбiльшої подiбностi. Правила обчислення вiдстанi мiж кластерами можуть бути рiзними. У даній роботі ми використовували \textbf{Метод ближнього сусiда} - вiдстань мiж кластерами визначається як найменша з усiх вiдстаней мiж об’єктами, що входять до складу двох кластерiв.\\
Матриця відстаней має вигляд \\"""
)

steps = []

a = []
used = []
for i in range(10):
    b = [i]
    a.append(b)
    used.append(True)

DD = D

for i in range(n, 2, -1):
    in1 = 0
    in2 = 0
    m = 1e9
    for j in range(i):
        for k in range(j + 1, i):
            if DD[j][k] < m:
                m = DD[j][k]
                in1 = j
                in2 = k
    if in1 > in2:
        t = in1
        in1 = in2
        in2 = t

    right_in1 = 0
    right_in2 = 0
    t = -1
    for j in range(n):
        if used[j]:
            t += 1
        if t == in1:
            right_in1 = j
            break
    t = -1
    for j in range(n):
        if used[j]:
            t += 1
        if t == in2:
            right_in2 = j
            break
    # print(right_in1, right_in2)
    in1 = right_in1
    in2 = right_in2
    # print(m)
    used[in2] = False
    for j in range(len(a[in2])):
        a[in1].append(a[in2][j])
    D1 = []
    for j in range(n):
        d = []
        if used[j] == False:
            continue
        for k in range(n):
            if used[k] and used[j]:
                mi = 1e9
                for j1 in range(len(a[j])):
                    for k1 in range(len(a[k])):
                        mi = min(
                            mi,
                            np.sqrt(
                                (
                                    (df_st.loc[Y[a[j][j1]]] - df_st.loc[Y[a[k][k1]]])
                                    ** 2
                                ).sum()
                            ),
                        )
                d.append(mi)
        D1.append(d)
        np.array(D1)
    DD = D1
    # print(array_2d_to_latex(np.array(D1), rounding=2))
    steps.append(((right_in1, right_in2), np.array(D1)))
    vv = []
    for j in range(n):
        if used[j]:
            vv.append(a[j])
    # print(vv)

for (l, r), arr in steps:
    print(
        r"""Найменша відстань між класами $k_"""
        + f"{l}"
        + r"""$ і $k_"""
        + f"{r}"
        + r""",$ Класи $k_"""
        + f"{l}"
        + r"""$ і $k_"""
        + f"{r}"
        + r"""$ об’єднуємо в один і даємо йому номер $\min ("""
        + f"{l}"
        + r""","""
        + f"{r}"
        + r""")= """
        + f"{min(l, r)}"
        + r""".$\\
    Тепер розраховуємо матрицю відстаней між новими класами.\\ Відстань між класами дорівнює мінімальній відстані між об’єктами цих класів (метод ближнього сусіда).\\ Отже, матриця відстаней має вигляд:"""
    )
    print(array_2d_to_latex(arr, rounding=2))

print(
    r"""Необхідна кількість кластерів, на які розіб’ється вихідна сукупність, визначається шляхом аналізу значення відстані між кластерами, при якій здійснювалося об’єднання кластерів. Наприклад, ця кількість може виявитись на тому етапі, після якого приріст значення відстані між кластерами був найбільшим.\\ """
)

from scipy.cluster.hierarchy import linkage, dendrogram
from matplotlib import pyplot as plt
import os

dend = dendrogram(linkage(df_s, method="single", metric="euclidean"))
plt.savefig(os.path.join(settings.overleaf_project_directory, "dend.png"))

print(
    r"""\begin{center}
    \includegraphics[width = 10cm, height = 5cm]{dend.png}
\end{center}"""
)


print(
    r"""\subsubsection{Дивізимний метод }
Цей метод за процесом розрахунків є протилежним агломеративному. Початковими даними для розрахунків є матриця відмінностей (відстаней) об’єктів. Розглянемо алгоритм методу.\\
Спочатку вважаємо, що об’єкти належать одному класові. Знаходимо два об’єкти, відмінність між якими найбільша. Отримані об’єкти і будуть центрами нових двох класів. Інші об’єкти розподіляються по цих класах за ступенем близькості до їх центрів. Тобто якщо центрами класів є об’єкти $n_i$ та $n_j$, що утворюють класи $k_i$ та $k_j$ , то об’єкт $n_p$ увійде до класу $k_i$, якщо відстань від нього до об’єкту $n_i$ менша за відстань до об’єкту $n_j$, або до класу $k_j$ в протилежному випадку. У результаті всі об’єкти будуть розподілені між цими двома класами.\\
Далі обирається для поділу той клас, який містить два найбільш віддалені об’єкти. Поділ класу відбувається за аналогічною процедурою.\\
Процес поділу відбувається до тих пір, поки в кожному із класів не залишиться по одному об’єктові. Найбільш доцільна кількість класів визначається на тому кроці, після якого зменшення відстані між класами було найбільшим.\\
Зазначимо, що дивізимний метод на кожному кроці не використовує явного перерахунку матриці відстаней. Цим він вигідно відрізняється від агломеративного методу. \\ \\
Проведемо класифiкацiю 10 об’єктiв дивiзимним методом. Наведемо у таблиці матрицю відстаней між об’єктами.\\"""
)

import copy

steps = []

cl = {}
cl[-1] = np.array(range(n))
while len(cl) != n:
    m = 0
    in1 = 0
    in2 = 0
    keyy = 0
    ee = []
    for key, e in cl.items():
        if len(e) == 1:
            continue
        for j in range(len(e)):
            for k in range(len(e)):
                if D[e[j]][e[k]] > m:
                    m = D[e[j]][e[k]]
                    in1 = e[j]
                    in2 = e[k]
                    keyy = key
                    ee = e
    # print(m)
    del cl[keyy]
    cl[in1] = [in1]
    cl[in2] = [in2]
    for j in range(len(ee)):
        if ee[j] != in1 and ee[j] != in2:
            if D[in1][j] < D[in2][j]:
                cl[in1].append(ee[j])
            else:
                cl[in2].append(ee[j])
    # print(cl)
    steps.append(((in1, in2), m, copy.deepcopy(cl), keyy))


print(
    r"Спочатку об’єкти належать одному класу $k = \{n_1, n_2, n_3, n_4, n_5, n_6, n_7, n_8, n_9, n_{10}\}$.\\"
)

for (l, r), d, cl, prev_c in steps:
    print(
        r"""Розбиваємо той клас, до якого входять об’єкти з найбільшою відстанню.\\
Найбільша відстань $d_{"""
        + f"{l}{r}"
        + r"""} = """
        + f"{d}"
        + r"""$ між об’єктами $n_"""
        + f"{l}"
        + r"""$ і $n_"""
        + f"{r}"
        + r"""$, що знаходяться в класі $k_"""
        + f"{prev_c}"
        + r""".$\\
Отже, будемо розбивати клас $k_"""
        + f"{prev_c}"
        + r"""$ на два класи, центрами яких будуть відповідно об’єкти $n_"""
        + f"{l}"
        + r"""$ і $n_"""
        + f"{r}"
        + r""".$\\
Далі отримаємо такі класи:"""
    )
    for key, val in cl.items():
        print(f"$$k_{{{key}}} = \\{{{', '.join([str(v) for v in val])}\\}}$$")


print(
    r"""\subsection{Висновки}
НЕ ГЕНЕРИРУЕТСЯ! Після застосування агломеративного та дивізимного методу, ми прийшли до висновку, що найдоцільніше буде розбити початкові дані на два класи.
Останній метод вказує на те, що дивлячись на наступні соціально-економічні показники 10 країн світу: 
\begin{itemize}
    \item $x_1$ - ВВП на душу населення (у дол. США за купівельною спроможністю валют),
    \item  $x_2$ - Відсоток міського населення,
    \item $x_3$ - Відсоток грамотних,
    \item $x_4$ - Тривалість життя чоловіків (у роках).
\end{itemize}
можна зробии наступний висновок, такі країни як 
\begin{itemize}
\item Норвегія
\item ОАЕ (Об'єднані Арабські Емірати )
\item Сінгапур
\end{itemize}
можна об'єднати в один клас з урахуванням безлічі ознак, так як ці об'єкти мають найбільшу схожість один з одним з точки зору спостережуваних змінних. Решта країн(ПАР,Південна Корея,Північна Корея,Польща,Португалія,Росія,Саудівська Аравія) утворюють другий клас, так як мають найбільшу схожість одна з одною з урахуванням наведених ознак. """
)
