Домашнее задание №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) Каким образом можно определять число кластеров?
Можно запускать алгоритм кластеризации с различным числом кластеров и остановиться на том, при котором получается максимальное качество алгоритма. Также можно попробовать алгоритмы, оценивающие оптимальное число кластеров (например, MeanShift).
Задача 2 Даны пять точек на числовой оси $X = (1; 5; 7; 8; 8)$, число кластеров равно 2. Рассчитайте ответ алгоритма K-means (финальные центры кластеров), если начальные центры кластеров c1 = 1, c2 = 10.
Ответ:
Задача 3 Докажите, что the k-means всегда сходится.
Количество возможных разбиений выборки конечно, поэтому разбиение, при котором центры кластеров на очередной итерации не изменяются, будет достигнуто за конечное число шагов.
Задача 4
Для сжатия размерности пространства алгоритм PCA применяется к датасету с количеством признаков $D = 100$. Наблюдается следующий спектр собственных значений матрицы объектов-признаков.
In [12]:
import numpy as np
d = np.linspace(1.6, 0.5, 100) # аппроксимируем эту прямую
dTot = np.sum(d)
n = 100
var_i = np.array([np.sum(d[: i + 1]) / \
dTot * 100.0 for i in range(n)])
m = sum(var_i < 0.95 * 100)
print m
Понижение размерности с помощью PCA до примерно 90 не приведет к значительному сокращению размерности, поэтому делать это, скорее всего, не нужно, хотя потеря точности составит не более 5%.
In [5]:
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.dot(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 = np.linalg.svd(F.T) # !!! посчитать SVD матрицы Sigma
# compute the value m: number of minumum features that retains the given variance varRetaine
d = d**2
dTot = np.sum(d)
var_i = np.array([np.sum(d[: i + 1]) / \
dTot * 100.0 for i in range(n)])
m = sum(var_i < varRetained * 100) # !!! вычислите необходимое число главных компонент
print '%.2f %% variance retained in %d dimensions' % (var_i[m], m) # !!! верните число 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 = V.T[:, :m] # !!! только m главных компонент
G = F.T.dot(U_reduced) # !!! вычислить матрицу в преобразованном пространстве
return G, U_reduced
In [6]:
# Примените алгоритм к данным 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 [8]:
#################################################################
# PCA of training set
print 'Performing PCA - Principal COmponent Analysis'
Z, U_reduced = PCA(X.T, varRetained = 0.95, show = True)
In [9]:
print Z.shape
print U_reduced.shape
In [10]:
print Z
print U_reduced
На данных из sklearn.datasets.load_digits примените алгоритмы кластеризации (знания о метках классов при кластеризации использовать нельзя):
In [8]:
from sklearn.decomposition import PCA
from sklearn.cluster import DBSCAN
from sklearn import metrics
import numpy as np
import matplotlib.pyplot as plt
from sklearn.manifold import TSNE
from sklearn.decomposition import PCA
%matplotlib inline
In [9]:
np.random.seed(1)
digits = load_digits()
data = (digits.data)
target = digits.target
In [10]:
tsne = TSNE(n_components=2)
twod_data = tsne.fit_transform(data)
In [11]:
plt.figure(figsize=(10, 16))
colors = plt.cm.Spectral(np.linspace(0, 1, 10))
for i, color in enumerate(colors):
X_i = twod_data[target == i]
plt.scatter(X_i[:, 0], X_i[:, 1], c=color, label=str(i))
plt.legend(loc='best')
plt.title('clusters after t-SNE')
plt.show()
In [12]:
n_samples, n_features = data.shape
n_digits = len(np.unique(digits.target))
labels_true = digits.target
print 'n_digits: {}, n_samples {}, n_features {}'.format(n_digits, n_samples, n_features)
def run_dbscan(eps, min_samples):
db = DBSCAN(eps=eps, min_samples=min_samples).fit(twod_data)
core_samples_mask = np.zeros_like(db.labels_, dtype=bool)
core_samples_mask[db.core_sample_indices_] = True
labels = db.labels_
n_clusters_ = n_digits
return (db,
metrics.adjusted_rand_score(labels_true, labels),
metrics.adjusted_mutual_info_score(labels_true, labels))
In [13]:
from itertools import product
def get_best_params(eps_, min_samples_):
quality = []
for eps, min_sample in product(eps_, min_samples_):
r = run_dbscan(eps, min_sample)
quality.append(r[1]**2 + r[2]**2)
return list(product(eps_, min_samples_))[np.argmax(quality)]
In [14]:
best_params = get_best_params(np.arange(1, 5, 0.01), np.arange(5, 20))
print best_params
In [15]:
db = run_dbscan(*best_params)[0]
print run_dbscan(*best_params)
In [16]:
len(np.unique(db.labels_))
Out[16]:
In [17]:
colors = plt.cm.Spectral(np.linspace(0, 1, len(np.unique(db.labels_))))
plt.figure(figsize=(10, 16))
for i, label in enumerate(np.unique(db.labels_)):
X_i = twod_data[db.labels_ == label]
plt.scatter(X_i[:, 0], X_i[:, 1], c=colors[i], label=str(label))
plt.legend(loc='best')
plt.show()
In [18]:
cores_n = len(db.core_sample_indices_)
print 'number of core points: {}'.format(cores_n)
plt.figure(figsize=(10, 20))
for i in xrange(100):
plt.subplot(10, 10, i + 1)
plt.imshow(digits.images[db.core_sample_indices_[i]], cmap='binary')
plt.show()
In [19]:
noise = [i for i, x in enumerate(db.labels_) if x == -1]
print 'number of noise points: {}'.format(len(noise))
plt.figure(figsize=(10, 20))
for i, x in enumerate(noise[:100]):
plt.subplot(10, 10, i + 1)
plt.imshow(digits.images[x], cmap='binary')
plt.show()
Судя по результатам можно заключить, что понижение размерности t-SNE и использование DBSCAN оправдано.
-- KMeans
-- MeanShift
-- AgglomerativeClustering
In [1]:
import matplotlib.pyplot as plt
img = plt.imread('two-birds.jpg')
plt.figure(figsize=(10, 16))
plt.imshow(img)
plt.axis('off')
plt.show()
In [2]:
from skimage.measure import compare_ssim
from sklearn.cluster import KMeans, AgglomerativeClustering, MeanShift
In [9]:
def run(clusterization, img):
img_data = np.copy(img).reshape(-1, 3)
clusters = clusterization.fit_predict(img_data)
for i, x in enumerate(np.unique(clusters)):
current_cluster = img_data[clusters == x]
img_data[clusters == x] = np.mean(current_cluster, axis=0)
new_img = img_data.reshape(img.shape)
plt.figure(figsize=(10, 10))
plt.title('clusters = {}'.format(len(np.unique(clusters))))
plt.imshow(new_img)
plt.show()
return new_img, compare_ssim(img, new_img, multichannel=True)
In [23]:
K = [2, 3, 10, 20]
for k in K:
print '\nSSIM = {:.3f}\n'.format(run(KMeans(n_clusters=k), img)[1])
In [24]:
from sklearn.cluster import estimate_bandwidth
img_data = np.copy(img).reshape(-1, 3)
quants = [0.2, 0.17, 0.055, 0.028] # for needed K
for q in quants:
bandwidth = estimate_bandwidth(img_data,
quantile=q,
n_samples=1000)
ms = MeanShift(bandwidth=bandwidth, bin_seeding=True)
print '\nSSIM = {}\n'.format(run(ms, img)[1])
In [6]:
from sklearn.neighbors import kneighbors_graph
import numpy as np
img = plt.imread('two-birds.jpg')
img_data = np.copy(img).reshape(-1, 3)
In [10]:
graph = kneighbors_graph(img_data, 30, include_self=False)
K = [2, 3, 10, 20]
for k in K:
print '\nSSIM = {:.3f}\n'.format(run(AgglomerativeClustering(n_clusters=k, connectivity=graph), img)[1])
Лучший результат на данной картинке показал алгоритм KMeans
In [ ]: