Файл: Курсовая работа по дисциплине Технологии обработки информации Вариант 3 Фамилия Мельник.docx

v — собственный вектор, то и αv — тоже собственный вектор. У матрицы A, размерностью (N×N) не может быть больше, чем N собственных значений. Они удовлетворяют характеристическому уравнениюdet(A − λI) = 0,являющемуся алгебраическим уравнением N-го порядка.4) Как связаны между собой сингулярные значения SVD разложения и собственные значения матрицы счетов метода РСА?Метод главных компонент тесно связан с другим разложением – по сингулярным значениям, SVD. В последнем случае исходная матрица X разлагается в произведение трех матриц:X=USV^tЗдесь U – матрица, образованная ортонормированными собственными векторами u_r матрицы XX^t, соответствующим значениям λ_r:XX^tu_r = λ_ru_rV – матрица, образованная ортонормированными собственными векторами v_r матрицы X^tX:X^tXv_r = λ_rv_rS – положительно определенная диагональная матрица, элементами которой являются сингулярные значения σ1≥... ≥σR≥0 равные квадратным корням из собственных значений λ_rСвязь между PCA и SVD определяется следующими простыми соотношениями:T = US P = V5) Какие критерии выбора числа главных компонент используются на практике? Задача метода главных компонент заключается в том, чтобы построить новое пространство признаков меньшей размерности, дисперсия между осями которой будет перераспределена так, чтобы максимизировать дисперсию по каждой из них. Для этого выполняется последовательность следующих действий:

Вычисляется общая дисперсия исходного пространства признаков. Это нельзя сделать простым суммированием дисперсий по каждой переменной, поскольку они, в большинстве случаев, не являются независимыми. Поэтому суммировать нужно взаимные дисперсии переменных, которые определяются из ковариационной матрицы.
Вычисляются собственные векторы и собственные значения ковариационной матрицы, определяющие направления главных компонент и величину связанной с ними дисперсии.
Производится снижение размерности. Диагональные элементы ковариационной матрицы показывают дисперсию по исходной системе координат, а её собственные значения — по новой. Тогда разделив дисперсию, связанную с каждой главной компонентой на сумму дисперсий по всем компонентам, получаем долю дисперсии, связанную с каждой компонентой. После этого отбрасывается столько главных компонент, чтобы доля оставшихся составляла 80-90%.

Задание №2 Кластеризация данных

Исследовать возможности классификации данных с использованием алгоритмов t-SNE и UMAP.Исходные данные для анализа загрузить из ресурса Wine Quality (http://archive.ics.uci.edu/ml/machine-learning-databases/wine-quality) репозитария. Варианты заданий (номер варианта определяется последней цифрой номера зачетки) приведены в табл. 1.Таблица 1Анализируемые данные включают 11 объективных параметров различных сортов вина:- фиксированная кислотность;- летучая кислотность;- лимонная кислота;- остаточный сахар;- хлориды;- свободный диоксид серы;- общий диоксид серы;- плотность;- pH;- сульфаты;- спирт.Последний, 12-ый параметр является субъективной оценкой качества, проставляемой экспертом, и имеет несколько градаций.Основная задача исследования состоит в определении качества субъективной оценки экспертов и формированию обоснованной кластеризации вин. Исследование должно содержать:- описание исследуемого набора данных,- подготовку данных для анализа,- план и решаемые задачи,- выбор используемых функций и описание их параметров,- результаты исследования,- аргументированные выводы.Программный код должен быть снабжен подробным комментарием.

Загрузка и подготовка исходных данных для анализа

Согласно варианту задания был загружен датасет оценки качества красного вина. Реализовано это было с помощью функции чтения данных, разделенных разделителем, в данном случае символом точки с запятой read.delim. После этого необходимо было определить фактором столбец качества вина.library("readr")library("Rtsne")library("magrittr")library("data.table")library("dplyr")library("ggplot2")library("umap")#чтение файлаdata <- read.delim('/Users/viktoriazw/Desktop/БОНЧ 2022-2023 учебный год/Подработки 2022-2023/2023/Курсовой ТОИ/Мельник/zadanie2/winequality-white.csv', sep=';')#определить фактором столбец качества винаdata$quality <- factor(data$quality, ordered = T)#задаем начальную фазу генератора случайных чисел - для воспроизводимостиset.seed(1)#подготовка визуализации графиков в 2 строки по 2 графикаpar(mfrow=c(2,2))Листинг 4Поскольку данные не содержали пропусков или прочих некорректных данных, то последним шагом в подготовке их к работе с алгоритмами кластеризации было перемешивание и определение обучающей выборки.

Эта операция идентичная как для tSNE так и для UMAP

Главные теоретические положения

t-распределенное стохастическое соседнее вложение t-SNE (t-Distributed Stochastic Neighbor Embedding) — это алгоритм нелинейного уменьшения размерности, используемый для исследования данных большой размерности [1]. Он отображает многомерные данные в двух или более измерениях, подходящих для наблюдения человеком. Алгоритм t-SNE (2008), в ряде случаев намного эффективнее PCA (1933). Важно подчеркнуть, что большинство нелинейных методов, кроме t-SNE, не способны одновременно сохранять локальную и глобальную структуру данных [5].SNE начинается с преобразования многомерной евклидовой дистанции между точками в условные вероятности, отражающие сходство точек. Математически это выглядит следующим образом: (4)Формула (4) показывает, насколько точка x_j близка к точке x_i при гауссовом распределении вокруг x_i с заданным отклонением σ. Сигма будет различной для каждой точки. Она выбирается так, чтобы точки в областях с большей плотностью имели меньшую дисперсию. Для этого используется оценка перплексии (perplexity): (5)г де - энтропия Шеннона (6)

Решение поставленной задачи

После генерации обучающей выборки следующим этапом было проверить работу алгоритма для разных значений перплексии.#организуем цикл для 4-х значений реплексииfor (k in c(5,10,25,50)) {res.tsne <- Rtsne(data[,-1], dims=2, perplexity=k, verbose=TRUE, max_iter=500,check_duplicates=FALSE)colors = rainbow(length(unique(data$quality)))plot(res.tsne$Y, t='n', main=paste('tSNE::per',k), xlab='tSNE dim 1', ylab='tSNE dim 2')text(res.tsne$Y, labels=data$quality, col=colors[data$quality])print('======')}Листинг 5Кластеры должны окрашиваться в то количество цветов, которое совпадает с количеством уникальных значений в факторном столбце. Текущий цикл перебирает значения перплексии [5, 10, 25, 50] и графический результат представлен на рисунке 4.Рисунок 4. Вид кластеров tSNE при различной перплексииЕсли рассматривать отдельно результат кластеризации

, например для значения перплексии 50, можно увидеть, что присутствует динамика в сторону увеличения похожих на полноценные кластеры совокупностей точек, что в свою очередь может свидетельствовать о положительной возможности использовать алгоритм понижения размерности tSNE в задачах кластеризации и в искомом датасете в частности.

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

#UMAP

rows.umap <- sample(1:nrow(data), nrow(data)*0.7)

data.umap <- data[rows.umap,]

res.umap <- umap(data.umap[,-ncol(data.umap)])

colors=rainbow(10)
par(mfrow=c(1,1))

plot(res.umap$layout, t='n', main='UMAP wine Q', xlab='UMAP dim 1', ylab='UMAP dim 2',

'cex.main'=2, 'cex.lab'=1.5)

text(res.umap$layout, labels=data$quality, col=colors[data$quality])

Листинг 6

Рисунок 5. Вид кластеров UMAP

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

Программный код

install.packages("readr")install.packages("Rtsne")install.packages("magrittr")install.packages("data.table")install.packages("dplyr")install.packages("ggplot2")install.packages("umap")library("readr")library("Rtsne")library("magrittr")library("data.table")library("dplyr")library("ggplot2")library("umap")#чтение файлаdata <- read.delim('/Users/viktoriazw/Desktop/БОНЧ 2022-2023 учебный год/Подработки 2022-2023/2023/Курсовой ТОИ/Мельник/zadanie2/winequality-white.csv', sep=';')#определить фактором столбец качества винаdata$quality <- factor(data$quality, ordered = T)#задаем начальную фазу генератора случайных чисел - для воспроизводимостиset.seed(1)#подготовка визуализации графиков в 2 строки по 2 графикаpar(mfrow=c(2,2))#перемешивание и определение обучающей выборкиrows.tsne <- sample(1:nrow(data), nrow(data)*0.7)#организуем цикл для 4-х значений реплексииfor (k in c(5,10,25,50)) {res.tsne <- Rtsne(data[,-1], dims=2, perplexity=k, verbose=TRUE, max_iter=500,check_duplicates=FALSE)colors = rainbow(length(unique(data$quality)))plot(res.tsne$Y, t='n', main=paste('tSNE::per',k), xlab='tSNE dim 1', ylab='tSNE dim 2')text(res.tsne$Y, labels=data$quality, col=colors[data$quality])print('======')}#UMAProws.umap <- sample(1:nrow(data), nrow(data)*0.7)data.umap <- data[rows.umap,]res.umap <- umap(data.umap[,-ncol(data.umap)])colors=rainbow(10)par(mfrow=c(1,1))plot(res.umap$layout, t='n', main='UMAP wine Q', xlab='UMAP dim 1', ylab='UMAP dim 2', 'cex.main'=2, 'cex.lab'=1.5)text(res.umap$layout, labels=data$quality, col=colors[data$quality])

Заключение

В данном разделе были получены теоретические знания и практические навыке в работе с алгоритмами понижения размерности tSNE и UMAP в задачах кластеризации.

Список использованных источников

Филиппов Ф.В., Технологии обработки информации, методическое пособие для курсовой работы, СПб., 2021. – 27
Препарируем t-SNE https://habr.com/ru/post/267041/

Контрольные вопросы

1) Как можно интерпретировать назначение и выбирать адекватное значение перплексии при использовании алгоритма t-SNE?Перплексия может быть интерпретирована как сглаженная оценка эффективного количества «соседей» для точки x_i. Она задается в качестве параметра метода t-SNE и рекомендуется использовать ее значение в интервале от 5 до 50. Сигма определяется для каждой пары x_i и x_j при помощи алгоритма бинарного поиска. 2) Как решается проблема скученности точек в пространстве отображения в алгоритме t-SNE?Использование классического SNE позволяет получить неплохие результаты, но может быть связано с трудностями в оптимизации функции потерь и проблемой скученности (в оригинале – crowding problem). t-SNE если и не решает эти проблемы совсем, то существенно облегчает. Функция потерь t-SNE имеет два принципиальных отличая. Во-первых, у t-SNE симметричная форма сходства в многомерном пространстве и более простой вариант градиента. Во-вторых, вместо гауссова распределения для точек из пространства отображения используется t-распределение (Стьюдента), «тяжелые» хвосты которого облегчают оптимизацию и решают проблему скученности. [2] 3) Чем распределение Стьюдента отличается от нормального распределения?Форма распределения Стьюдента похожа на форму нормального распределения. Отличием является то, что «хвосты» распределения Стьюдента медленнее стремятся к нулю, чем «хвосты» нормального распределения. 4) Что пытается сохранить алгоритм UMAP: глобальную структуру анализируемых данных или локальные расстояния между отдельными точками?Алгоритм UMAP относится к группе алгоритмов, которые пытаются сохранить локальные расстояния между отдельными точками, в отличие от PCA.

Задание №3 Обработка графической информации

Визуализировать отрывок сказки К.И.Чуковского «Муха-цокотуха» с использованием технологии SVG, соответствующий номеру фрагмента. Номер своего фрагмента определяется последней цифрой номера зачетной книжки:

Вдруг какой-то старичок

Паучок
Нашу Муху в уголок

Поволок -
Хочет бедную убить, Цокотуху погубить!

"Дорогие гости, помогите!

Паука-злодея зарубите! И кормила я вас,
И поила я вас,

Не покиньте меня
В мой последний час!"