Домашнее задание №8
Deadline: 20.05.2017 23:59:59
ФИВТ, АПТ, Курс по машинному обучению, Весна 2017, Модуль Unspervised Learning,
Alexey Romanenko, alexromsput@gmail.com
Дополнительный материал для выполнения дз:
Оформление дз:
ml.course.mipt@gmail.comML2017_fall <номер_группы> <фамилия>, к примеру -- ML2017_fall 496 ivanov<фамилия>_<группа>_task<номер задания>.ipnb, к примеру -- ML2017_496_task1.ipnbВопросы:
ml.course.mipt@gmail.comML2016_fall Question <Содержание вопроса>Ответе на вопросы своими словами (загугленный материал надо пересказать), ответ обоснуйте (напишите и ОБЪЯСНИТЕ формулки если потребуется), если не выходит, то вернитесь к лекции дополнительным материалам:
Вопрос 1: В чём заключается проблема мультиколлинеарности?
Вопрос 2: Какие проблемы при обучении алгоритмов возникают из-за большой разамерности пространства признаков?
Вопрос 3: В чем суть проклятия размерности?
Вопрос 4: Какая связь между решением задачи PCA и SVD-разложение матрицы регрессии?
Вопрос 5: Почему в tSNE расстояние между парамми объектов измеряется "по-стьюденту" и как это помогает решить проблему "скрученности" (crowding problem)?
Вопрос 6: На какой идее базируются алгоритмы аггломеративной кластеризации? Напишите формулу Ланса-Вильма
Вопрос 7: Какие два шага выделяют в алгоритме кластеризации k-means?
Вопрос 8: В чём отличия (основные упрощения) k-means от EM-алгоритма кластеризации?
Вопрос 9 Какой принцип работы графовых алгоритмов кластеризации?
Вопрос 10 В чем некорректность постановки задачи кластеризации?
PS: Если проверяющий не понял ответ на большинство вопросов, то будет пичалька. Пишите так, чтобы можно было разобраться.
Задача 1 Ответьте на вопросы:
1) Как можно не прибегая к визуализации понять, что кластерная структура у данного облака точек отсутствует? 2) Какие из алгоритмов кластеризации могут выделять кластеры с ленточной структурой? 3) Какие алгоритмы кластеризации чувствительны к шуму и перемычкам? 4) Каким образом приближают «центр кластера» в нелинейных пространствах? 5) Каким образом можно определять число кластеров?
Задача 2 Даны пять точек на числовой оси $X = (1; 5; 7; 8; 8)$, число кластеров равно 2. Рассчитайте ответ алгоритма K-means (финальные центры кластеров), если начальные центры кластеров c1 = 1, c2 = 10.
Задача 3 Докажите, что the k-means всегда сходится.
Задача 4
Для сжатия размерности пространства алгоритм PCA применяется датасету с количеством признаков $D = 100$. Наблюдается следующий спектр собственных значений матрицы объектов-признаков.
In [3]:
import numpy as np
import pylab as plt
'''
Performs the Principal Coponent analysis of the Matrix F
Matrix must be n * l dimensions
where n is # features
l is # samples
'''
def PCA(F, varRetained = 0.95, show = False):
# Input
# F - initaial matrix
# Compute Covariance Matrix Sigma
# Input
(n, l) = F.shape
Sigma = 1.0 / l * F * np.transpose(F)
# Compute eigenvectors and eigenvalues of Sigma by SVD
# U, V - matrix, d - array: Sigma = U * np.diag(d) * V
U, d, V = посчитать SVD матрицы Sigma
# compute the value m: number of minumum features that retains the given variance varRetaine
dTot = np.sum(d)
var_i = np.array([np.sum(d[: i + 1]) / \
dTot * 100.0 for i in range(n)])
m = вычислите необходимое число главных компонент
print '%.2f %% variance retained in %m dimensions' % верните число m и точность, которая достигается при этом числе главных компонент
# plot the variance plot
if show:
plt.plot(var_i)
plt.xlabel('Number of Features')
plt.ylabel(' Percentage Variance retained')
plt.title('PCA $\% \sigma^2 $ vs # features')
plt.show()
# compute the reduced dimensional features by projection
U_reduced = только m главных компонент
G = вычислить матрицу в преобразованном пространстве
return G, U_reduced
In [ ]:
# Примените алгоритм к данным MNIST
from sklearn.model_selection import train_test_split
from sklearn.datasets import load_digits
X, y = load_digits(return_X_y=True)
X_train, X_test, Y_train, Y_test = train_test_split(X, y, train_size=0.7)
In [ ]:
#################################################################
# PCA of training set
print 'Performing PCA - Principal COmponent Analysis'
Z, U_reduced = PCA(X.T, varRetained = 0.95, show = True)
In [ ]:
print Z
print U_reduced
На данных из sklearn.datasets.load_digits примените алгоритмы кластеризации (знания о метках классов при кластеризации использовать нельзя):
-- KMeans
-- MeanShift
-- AgglomerativeClustering