Some issues related with Unified State Examination in Informatics in Russian Federation: September 2022

Thursday, September 29, 2022

Simple 1D Kernel Density Estimation

Оценка плотности проходит грань между неконтролируемым обучением, проектированием признаков и моделированием данных. Некоторыми из наиболее популярных и полезных методов оценки плотности являются смешанные модели, такие как гауссовские смеси (GaussianMixture), и подходы на основе соседей, такие как оценка плотности ядра (KernelDensity). Гауссовские смеси более подробно обсуждаются в контексте кластеризации, потому что этот метод также полезен в качестве неконтролируемой схемы кластеризации. Хотя в приведенном выше примере для простоты используется одномерный набор данных, оценка плотности ядра может выполняться в любом количестве измерений, хотя на практике проклятие размерности приводит к ухудшению производительности в больших измерениях.

Пример где класс KernelDensity используется для демонстрации принципов оценки плотности ядра в одном измерении.

На первом плоте показана одна из проблем использования гистограмм для визуализации плотности точек в 1D. Интуитивно гистограмму можно представить как схему, в которой единичный «блок» расположен над каждой точкой регулярной сетки. Однако, как показывают две верхние панели, выбор сетки для этих блоков может привести к совершенно разным представлениям об основной форме распределения плотности. Если вместо этого мы центрируем каждый блок по точке, которую он представляет, мы получаем оценку, показанную на нижней левой панели. Это оценка плотности ядра с ядром «цилиндр».

Scikit-learn реализует эффективную оценку плотности ядра с использованием структуры Ball Tree или KD Tree с помощью оценщика KernelDensity. Все доступные ядра показаны на втором плоте.На третьем плоте сравниваются оценки плотности ядра для распределения 100 выборок в 1 измерении. Хотя в этом примере используются одномерные распределения, оценка плотности ядра также легко и эффективно расширяется до более высоких измерений.

(.env) boris@UbuntuLTS:~/PARZEN$ cat plottingKDE1D.py

import numpy as np

import matplotlib.pyplot as plt

from scipy.stats import norm

from sklearn.neighbors import KernelDensity

# Plot the progression of histograms to kernels

np.random.seed(1)

N = 20

X = np.concatenate(

(np.random.normal(0, 1, int(0.3 * N)), np.random.normal(5, 1, int(0.7 * N)))

)[:, np.newaxis]

X_plot = np.linspace(-5, 10, 1000)[:, np.newaxis]

bins = np.linspace(-5, 10, 10)

fig, ax = plt.subplots(2, 2, sharex=True, sharey=True)

fig.subplots_adjust(hspace=0.05, wspace=0.05)

# histogram 1

ax[0, 0].hist(X[:, 0], bins=bins, fc="#AAAAFF", density=True)

ax[0, 0].text(-3.5, 0.31, "Histogram")

# histogram 2

ax[0, 1].hist(X[:, 0], bins=bins + 0.75, fc="#AAAAFF", density=True)

ax[0, 1].text(-3.5, 0.31, "Histogram, bins shifted")

# tophat KDE

kde = KernelDensity(kernel="tophat", bandwidth=0.75).fit(X)

log_dens = kde.score_samples(X_plot)

ax[1, 0].fill(X_plot[:, 0], np.exp(log_dens), fc="#AAAAFF")

ax[1, 0].text(-3.5, 0.31, "Tophat Kernel Density")

# Gaussian KDE

kde = KernelDensity(kernel="gaussian", bandwidth=0.75).fit(X)

log_dens = kde.score_samples(X_plot)

ax[1, 1].fill(X_plot[:, 0], np.exp(log_dens), fc="#AAAAFF")

ax[1, 1].text(-3.5, 0.31, "Gaussian Kernel Density")

for axi in ax.ravel():

axi.plot(X[:, 0], np.full(X.shape[0], -0.01), "+k")

axi.set_xlim(-4, 9)

axi.set_ylim(-0.02, 0.34)

for axi in ax[:, 0]:

axi.set_ylabel("Normalized Density")

for axi in ax[1, :]:

axi.set_xlabel("x")

# Plot all available kernels

X_plot = np.linspace(-6, 6, 1000)[:, None]

X_src = np.zeros((1, 1))

fig, ax = plt.subplots(2, 3, sharex=True, sharey=True)

fig.subplots_adjust(left=0.05, right=0.95, hspace=0.05, wspace=0.05)

def format_func(x, loc):

if x == 0:

return "0"

elif x == 1:

return "h"

elif x == -1:

return "-h"

else:

return "%ih" % x

for i, kernel in enumerate(

["gaussian", "tophat", "epanechnikov", "exponential", "linear", "cosine"]

axi = ax.ravel()[i]

log_dens = KernelDensity(kernel=kernel).fit(X_src).score_samples(X_plot)

axi.fill(X_plot[:, 0], np.exp(log_dens), "-k", fc="#AAAAFF")

axi.text(-2.6, 0.95, kernel)

axi.xaxis.set_major_formatter(plt.FuncFormatter(format_func))

axi.xaxis.set_major_locator(plt.MultipleLocator(1))

axi.yaxis.set_major_locator(plt.NullLocator())

axi.set_ylim(0, 1.05)

axi.set_xlim(-2.9, 2.9)

ax[0, 1].set_title("Available Kernels")

# Plot a 1D density example

N = 100

np.random.seed(1)

X = np.concatenate(

(np.random.normal(0, 1, int(0.3 * N)), np.random.normal(5, 1, int(0.7 * N)))

)[:, np.newaxis]

X_plot = np.linspace(-5, 10, 1000)[:, np.newaxis]

true_dens = 0.3 * norm(0, 1).pdf(X_plot[:, 0]) + 0.7 * norm(5, 1).pdf(X_plot[:, 0])

fig, ax = plt.subplots()

ax.fill(X_plot[:, 0], true_dens, fc="black", alpha=0.2, label="input distribution")

colors = ["navy", "cornflowerblue", "darkorange"]

kernels = ["gaussian", "tophat", "epanechnikov"]

lw = 2

for color, kernel in zip(colors, kernels):

kde = KernelDensity(kernel=kernel, bandwidth=0.5).fit(X)

log_dens = kde.score_samples(X_plot)

ax.plot(

X_plot[:, 0],

np.exp(log_dens),

color=color,

lw=lw,

linestyle="-",

label="kernel = '{0}'".format(kernel),

)

ax.text(6, 0.38, "N={0} points".format(N))

ax.legend(loc="upper left")

ax.plot(X[:, 0], -0.005 - 0.01 * np.random.random(X.shape[0]), "+k")

ax.set_xlim(-4, 9)

ax.set_ylim(-0.02, 0.4)

plt.show()

Histograms and Density Plots in Python

==============================

Гистограмма — это графическое представление, которое упорядочивает группу точек данных в указанном диапазоне. Создание гистограммы обеспечивает визуальное представление распределения данных. Используя гистограмму, мы можем представить большой объем данных и их частоту.

График плотности — это непрерывная и сглаженная версия гистограммы, рассчитанная по данным. Это оценивается с помощью оценки плотности ядра.

В этом методе ядро (непрерывная кривая) рисуется в каждой отдельной точке данных, а затем все эти кривые складываются вместе, чтобы получить единую сглаженную оценку плотности. Гистограмма терпит неудачу, когда мы хотим сравнить распределение данных одной переменной по нескольким категориям в то время, когда график плотности полезен для визуализации данных.

Подход:

Импортируйте необходимые библиотеки.

Создайте или импортируйте набор данных из морской библиотеки.

Выберите столбец, для которого мы должны сделать график.

Для построения графика мы используем функцию distplot(), предоставляемую библиотекой seaborn, для совместного построения гистограммы и графика плотности, в которую мы должны передать столбец набора данных.

Мы также можем сделать гистограмму и график плотности по отдельности, используя функцию distplot() в соответствии с нашими потребностями.

Для индивидуального создания гистограммы мы должны передать hist=False в качестве параметра функции distplot().

Для индивидуального создания графика плотности мы должны передать kde=False в качестве параметра функции distplot().

Теперь, после создания графика, мы должны его визуализировать, поэтому для визуализации мы должны использовать функцию show(), предоставляемую библиотекой matplotlib.pyplot.

Для совместного построения графиков гистограммы и плотности мы используем набор данных алмазов и радужной оболочки, предоставленный библиотекой Seaborn.

(.env) boris@UbuntuLTS:~/KDE3D$ cat plotHistKDE.py

# importing libraries

import seaborn as sns

import matplotlib.pyplot as plt

import warnings

warnings.filterwarnings('ignore')

# importing diamond dataset from the library

df = sns.load_dataset('diamonds')

# plotting histogram and density plot

# for carat using distplot() by setting color

sns.distplot(a=df.carat, bins=40, color='purple',

hist_kws={"edgecolor": 'black'})

# visualizing plot using matplotlib.pyplot library

plt.show()

# importing libraries

import seaborn as sns

import matplotlib.pyplot as plt

# importing iris dataset from the library

df2 = sns.load_dataset('iris')

# plotting histogram and density plot for

# petal length using distplot() by setting color

sns.distplot(a=df2.petal_length, color='green',

hist_kws={"edgecolor": 'black'})

# visualizing plot using matplotlib.pyplot library

plt.show()

Parzen Windows density estimation technique

Формулa алгоритма классификации в методе окна Парзена. Классификатор Парзена оценивает плотность вероятности для каждого класса, используя непараметрический подход на основе сохраненных обучающих примеров. При вычислении выходных данных для нового наблюдения вклад каждого обучающего примера интегрируется. Оценка плотности ядра (KDE) — это непараметрический метод оценки функции плотности вероятности заданной случайной величины. Он также упоминается по своему традиционному названию, метод окна Парцена-Розенблатта. Учитывая выборку независимых, одинаково распределенных наблюдений (x1,x2,x3.....,xn)

где К(а)является функцией ядра и

h — параметр сглаживания, также называемый пропускной способностью.

Рассмотрим следующий пример

Oкно Парзена — это метод непараметрической оценки плотности. Оценка плотности в распознавании образов может быть достигнута с использованием подхода Parzen Windows. Метод оценки плотности окна Парзена является своего рода обобщением метода гистограмм. Он используется для получения функции плотности f(x) . f(x) используется для реализации байесовского классификатора. Когда у нас есть новый образец признака x и когда есть необходимость вычислить значение условной плотности класса, используется f(x). f(x) принимает значение выборки входных данных и возвращает оценку плотности данной выборки данных. Рассматривается n-мерный гиперкуб, который, как предполагается, имеет k выборок данных. Длина ребра гиперкуба считается равной h(n). Следовательно, объем гиперкуба равен: V(n) = h(n)^d

Мы определяем оконную функцию гиперкуба, φ(u), которая является индикаторной функцией единичного гиперкуба с центром в начале координат:

φ(u) = 1, если |u(i)| <= 0,5

φ(u) = 0 в противном случае

Здесь u — вектор, u = (u1, u2, …, ud)T.

φ(u) должно удовлетворять следующему:

Поскольку φ(u) центрированa в начале координат, онa симметричнa.

ф(u) = ф(-u)

Далее

φ((u-u0)/h) — гиперкуб размера h с центром в точке u0

Для любого х,φ((х-хi)/h) будет 1, только если xi попадает в гиперкуб стороны h с центром в x. Пусть D = {x1, x2, …, xn} — образцы данных. Следовательно, количество точек данных, попадающих в гиперкуб со стороной h с центром в x, равно

k = Sigma{φ((х-хi)/h}

i=1

Wednesday, September 21, 2022

Linear Discriminant Analysis

Линейный дискриминантный анализ (обычно сокращенно LDA, и его не следует путать с другим LDA) является очень распространенным методом уменьшения размерности для задач классификации. Однако это немного преуменьшение: он делает гораздо больше, чем «просто» уменьшение размерности.

Проще говоря, если у вас есть многомерные данные (т. е. большое количество признаков), по которым вы хотите классифицировать наблюдения, LDA поможет вам преобразовать ваши данные, чтобы сделать классы как можно более разными. Более строго, LDA найдет линейную проекцию ваших данных в подпространство более низкого измерения, которое оптимизирует некоторую меру разделения классов. Размерность этого подпространства обязательно строго меньше числа классов.

Это свойство LDA максимизировать разделение делает его настолько хорошим в своей работе, что иногда его считают классификационным алгоритмом сам по себе, что приводит к некоторой путанице. Линейный дискриминантный анализ — это форма уменьшения размерности, но с несколькими дополнительными предположениями его можно превратить в классификатор. (Отказ от этих предположений дает относительный, квадратичный дискриминантный анализ )

LDA как алгоритм: что он делает и как он это делает?

LDA как теорема: математический вывод LDA

LDA как метод машинного обучения.

Постановка задачи

Прежде чем мы углубимся в LDA, полезно получить интуитивное представление о том, чего пытается достичь LDA.Предположим, что: У вас многомерные данные, и Вы имеете дело с проблемой классификации. Это может означать, что количество объектов больше, чем количество наблюдений, или это может означать, что вы подозреваете наличие зашумленных объектов, которые содержат мало информации, или что-то среднее между ними.

Вы хотите выполнить две вещи:

1.Уменьшите количество функций (т.е. уменьшите размерность вашего пространства функций) и

2.Сохранить (или даже увеличьте!) «различимость» ваших классов или «отделенность» классов в вашем пространстве признаков.

Сначала несколько определений:

n - количество классов

μ — среднее значение всех наблюдений

Ni — количество наблюдений в i-м классе

µi — среднее значение i-го класса

Σi — матрица рассеяния i-го класса

Матрица рассеяния внутри класса SW

В качестве альтернативы можно использовать ковариационные матрицы классов путем добавления коэффициента масштабирования к матрице рассеяния внутри класса 1/(N-1) внутри класса

определим SB как матрицу рассеяния между классами, заданную формулой

Диагонализируйте SW^(-1)*SB, чтобы получить его собственные значения и собственные векторы cледующим образом:

Вычислите d-мерные средние векторы для различных классов из набора данных. Вычислите матрицы рассеяния (межклассовые и внутриклассовые матрицы рассеяния).

Вычислите собственные векторы (e1,e2,...,ed) и соответствующие собственные значения (λ1,λ2,...,λd) для матриц рассеяния.

Отсортируйте собственные векторы по убыванию собственных значений и выберите k собственных векторов с наибольшими собственными значениями, чтобы сформировать матрицу размерности d × k: W (где каждый столбец представляет собственный вектор).

Используйте эту матрицу собственных векторов d×k, чтобы преобразовать выборки в новое подпространство. Это можно резюмировать путем умножения матриц: Y=X*W (где X - это n×d-мерная матрица, представляющая n отсчетов, а Y - преобразованные n×k-мерные отсчеты в новом подпространстве)

W позволит нам преобразовать наши наблюдения в новое подпространство с помощью уравнения y=ATx, где y — наше преобразованное наблюдение, а x — наше исходное наблюдение.

Есть еще одна особенность LDA, о которой очень важно знать. Предположим, у вас есть 10 классов и вы запускаете LDA. Получается, что максимальное количество функций, которые может дать вам LDA, на единицу меньше, чем количество классов, то есть в данном случае 9!

Утверждение:

SW^(−1)*SB имеет не более n−1 ненулевых собственных значений, из чего следует, что LDA должен уменьшить размерность по крайней мере до n−1.

=====================================

Алгоритм выше реализованный на Пайтон

=====================================

Линейный дискриминантный анализ можно разбить на следующие этапы:

1.Вычислите матрицы рассеяния внутри класса и между классами

2.Вычислите собственные векторы и соответствующие собственные значения для матриц рассеяния

3.Отсортируйте собственные значения и выберите лучший k

4.Создайте новую матрицу, содержащую собственные векторы, которые сопоставляются с собственными значениями k

5.Получите новые функции (например, компоненты LDA), взяв скалярное произведение данных и матрицы из шага 4.

(.env) boris@UbuntuLTS:~/LDA$ cat AnalysisLDA1.py

from sklearn.datasets import load_wine

import pandas as pd

import numpy as np

np.set_printoptions(precision=4)

from matplotlib import pyplot as plt

import seaborn as sns

sns.set()

from sklearn.preprocessing import LabelEncoder

from sklearn.tree import DecisionTreeClassifier

from sklearn.model_selection import train_test_split

from sklearn.metrics import confusion_matrix

import warnings

warnings.simplefilter(action='ignore', category=FutureWarning)

wine = load_wine()

X = pd.DataFrame(wine.data, columns=wine.feature_names)

y = pd.Categorical.from_codes(wine.target, wine.target_names)

print(X.shape)

print(X.head())

print(wine.target_names)

df = X.join(pd.Series(y, name='class'))

class_feature_means = pd.DataFrame(columns=wine.target_names)

for c, rows in df.groupby('class'):

class_feature_means[c] = rows.mean()

print(class_feature_means)

within_class_scatter_matrix = np.zeros((13,13))

for c, rows in df.groupby('class'):

rows = rows.drop(['class'], axis=1)

s = np.zeros((13,13))

for index, row in rows.iterrows():

x, mc = row.values.reshape(13,1), class_feature_means[c].values.reshape(13,1)

s += (x - mc).dot((x - mc).T)

within_class_scatter_matrix += s

feature_means = df.mean()

between_class_scatter_matrix = np.zeros((13,13))

for c in class_feature_means:

n = len(df.loc[df['class'] == c].index)

mc, m = class_feature_means[c].values.reshape(13,1), feature_means.values.reshape(13,1)

between_class_scatter_matrix += n * (mc - m).dot((mc - m).T)

# Getting eigen_values, eigen_vectors

eigen_values, eigen_vectors = np.linalg.eig(np.linalg.inv(within_class_scatter_matrix).dot(between_class_scatter_matrix))

pairs = [(np.abs(eigen_values[i]), eigen_vectors[:,i]) for i in range(len(eigen_values))]

pairs = sorted(pairs, key=lambda x: x[0], reverse=True)

for pair in pairs:

print(pair[0])

eigen_value_sums = sum(eigen_values)

print('Explained Variance')

for i, pair in enumerate(pairs):

print('Eigenvector {}: {}'.format(i, (pair[0]/eigen_value_sums).real))

w_matrix = np.hstack((pairs[0][1].reshape(13,1), pairs[1][1].reshape(13,1))).real

X_lda = np.array(X.dot(w_matrix))

le = LabelEncoder()

y = le.fit_transform(df['class'])

plt.xlabel('LD1')

plt.ylabel('LD2')

plt.scatter(

X_lda[:,0],

X_lda[:,1],

c=y,

cmap = 'rainbow',

alpha=0.7,

edgecolors='b'

)

plt.show()

"""

Вместо того, чтобы каждый раз реализовывать алгоритм линейного дискриминантного анализа с нуля, мы можем использовать предопределенный класс LinearDiscriminantAnalysis, предоставленный нам библиотекой scikit-learn.

"""

from sklearn.discriminant_analysis import LinearDiscriminantAnalysis

lda = LinearDiscriminantAnalysis()

X_lda = lda.fit_transform(X, y)

plt.xlabel('LD1')

plt.ylabel('LD2')

plt.scatter(

X_lda[:,0],

X_lda[:,1],

c=y,

cmap='rainbow',

alpha=0.7,

edgecolors='b'

)

plt.show()

Tuesday, September 20, 2022

How to Create Dynamic Pivot Tables in MySQL

Загрузка данных в таблицу:

boris@UbuntuLTS:~$ mysql -u root -p

Enter password:

Welcome to the MySQL monitor. Commands end with ; or \g.

Your MySQL connection id is 15

Server version: 8.0.30-0ubuntu0.22.04.1 (Ubuntu)

Oracle is a registered trademark of Oracle Corporation and/or its

affiliates. Other names may be trademarks of their respective

owners.

Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.

mysql> create database dynamic;

Query OK, 1 row affected (0,14 sec)

mysql> use dynamic;

Database changed

mysql> show databases ;

+--------------------+

| Database |

+--------------------+

| dynamic |

| information_schema |

| mysql |

| performance_schema |

| sys |

+--------------------+

5 rows in set (0,00 sec)

mysql> CREATE TABLE Meeting

-> (

-> ID INT,

-> Meeting_id INT,

-> field_key VARCHAR(100),

-> field_value VARCHAR(100)

-> );

Query OK, 0 rows affected (0,80 sec)